Search

In urban scenes, many of the surfaces are planar and bounded by simple shapes. In a laser scan of such a scene, these simple shapes can still be identified. We present a one-parameter algorithm that can identify point sets on a plane for which a rectangle is a fitting boundary. These rectangles have a guaranteed density: no large part of the rectangle is empty of points. We prove that our algorithm identifies all angles for which a rectangle fits the point set of size n in O(nlogn) time. We evaluate our method experimentally on 13 urban data sets and we compare the rectangles found by our algorithm to the @a@?shape as a surface boundary.

This paper compares fixed partitioning and salient points schemes for dividing an image into patches, in combination with low-level MPEG-7 visual descriptors to represent the patches with particular patterns. A clustering technique is applied to construct a compact representation by grouping similar patterns into a cluster codebook. The codebook will then be used to encode the patterns into visual keywords. In order to obtain high-level information about the relational context of an image, a correlogram is constructed from the spatial relations between visual keyword indices in an image. For classifying images a k-nearest neighbors (k-NN) and a support vector machine (SVM) algorithm are used and compared. The techniques are compared to other methods on two well-known datasets, namely Corel and PASCAL. To measure the performance of the proposed algorithms, average precision, a confusion matrix, and ROC-curves are used. The results show that the cluster correlogram outperforms the cluster histogram. The saliency based scheme performs similarly to the fixed partitioning scheme and the SVM significantly outperforms the k-NN classifier. Finally, we demonstrate the robustness to noise, photometric, and geometric distortions. (C) 2009 Elsevier Ltd. All rights reserved.

With ever growing databases containing multimedia data, indexing has become a necessity to avoid a linear search. We propose a novel technique for indexing multimedia databases in which entries can be represented as graph structures. In our method, the topological structure of a graph as well as that of its subgraphs are represented as vectors whose components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. Given the laplacian spectrum of graph G, we draw from recently developed techniques in the field of spectral integral variation to generate the laplacian spectrum of graph G+e without computing its eigendecomposition, where G+e is a graph obtained by adding edge e to graph G. This process improves the performance of the system for generating the subgraph signatures for 1.8% and 6.5% in datasets of size 420 and 1400, respectively. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. Given a query graph, a voting schema ranks database graphs into an indexing hypothesis to which a final matching process can be applied. The novelties of the proposed method come from the powerful representation of the graph topology and successfully adopting the concept of spectral integral variation in an indexing algorithm. To examine the fitness of the new indexing framework, we have performed a number of experiments using an extensive set of recognition trials in the domain of 2D and 3D object recognition. The experiments, including a comparison with a competing indexing method using two different graph-based object representations, demonstrate both the robustness and efficacy of the overall approach.

This article describes how transportation distances such as the Earth Mover's Distance can be used for measuring melodic similarity for notated music. We represent music notation as weighted point sets in a two-dimensional space of onset time and pitch. The Earth Mover's Distance can then be used for comparing point sets by determining how much work it would take to convert one of the point sets into the other by moving weight between the point sets. For evaluating how well this method and other methods agree with human perception of melodic similarity, we established a ground truth for the RISM A/II collection based on the opinions of human experts. The RISM A/II collection contains about half a million musical incipits. For 22 queries, we filtered the collection so that about 50 candidates per query were left, each of which we then presented to about 30 human experts (out of a group of 37 experts) for a final ranking. We present our filtering methods, the experiment design, the resulting ground truth, and a new measure (called “Average Dynamic Recall”) that can be used for comparing different similarity measures with the ground truth.

Median filtering the intermediate flow fields during optimization has been demonstrated to be very useful for improving the estimation accuracy. By formulating the median filtering heuristic as non-local term in the objective function, and modifying the new term to include flow and image information that according to spatial distance, color similarity as well as the occlusion state, a weighted non-local term (a practical weighted median filter) reduces errors that are produced by median filtering and better preserves motion details. However, the color similarity measure, which is the most powerful cue, can be easily perturbed by noisy pixels. To increase robustness of the weighted median filter to noise, we introduce the idea of non-local patch denoising method to compute the color similarity in terms of patch difference. Most importantly, we propose an improved color patch similarity measure (ICPSM) to modify the traditional patch manner based measure from three aspects. Comparative experimental results on different optical flow benchmarks show that our method can denoise the flow field more effectively and outperforms the state-of-the art methods, especially for heavy noise sequences.

The shape of natural objects can be so complicated that only a sampling point set can accurately represent them. Analytic descriptions are too complicated or impossible. Natural objects can be vague and rough with many holes. For this kind of modelling, α-complexes offer advantages over triangulations and hulls at only little extra cost. Geometric and topological descriptions are well formalised, with the flexibility to capture holes and separations. Careful layout of the input sampling point set and the attachment of weights make ‘special modelling effects’ possible. Our approach assumes modelling-by-example: start with a sampling point set from a physical example and take the modelling from there. We explore in this paper the merits of geometric modelling with α-complexes, with emphasis on practical values. We discuss the α-complex as a model description and as a representation scheme. We also show how to run FEM computations on α-complexes.

We describe a new indexing structure for general image retrieval that relies solely on a distance function giving the similarity between two images. For each image object in the database, its distance to a set of m predetermined vantage objects is calculated; the m-vector of these distances specifies a point in the m-dimensional vantage space. The database objects that are similar (in terms of the distance function) to a given query object can be determined by means of an efficient nearest-neighbor search on these points. We demonstrate the viability of our approach through experimental results obtained with two image databases, one consisting of about 5200 raster images of stamps, the other containing about 72,000 hieroglyphic polylines.

Evaluation routines are essential for any application that uses triangular B-spline surfaces. This paper describes an algorithm to efficiently evaluate triangular B-spline surfaces with arbitrary many variables. The novelty of the algorithm is its generality: there is no restriction on the degree of the B-spline surfaces or on the dimension of the domain. Constructing an evaluation graph allows us to reuse partial results and hence, to decrease computation time. Computation time gets reduced even more by making choices in unfolding the recurrence relation of simplex splines such that the evaluation graph becomes smaller. The complexity of the algorithm is measured by the number of leaves of the graph.

Affine invariant pattern metrics are useful for shape recognition. It is important that such a metric is robust for various defects. We formalize these types of robustness using four axioms. Then, we present the reflection metric. This is an affine invariant metric defined for the large family of "boundary patterns". A boundary pattern is a finite union of n-1 dimensional algebraic surface patches in ℝn. Such a pattern may have multiple connected components. We prove that the reflection metric satisfies the four robustness axioms.

This paper presents a method for the (re)construction of a simple closed polygon (2D) or polyhedron (3D) passing through all the points of a given set. The points are assumed to lie on the boundary of a closed object without through-passages and inner voids. No a priori knowledge about any topological relation between the points, or additional information such as sample density or normal vectors, is used. The construction technique is based on a parameterized geometric graph, the γ-Neighborhood Graph. The hull of the γ-Neighborhood Graph is iteratively constricted, exploiting geometric information incorporated in the graph. This constriction technique provides a uniform approach for 2D and 3D.

A constrained variational curve is a curve that minimizes some energy functional under certain interpolation constraints. Modeling curves using constrained variational principles is attractive, because the designer is not bothered with the precise representation of the curve (e.g. control points). Until now, the modeling of variational curves is mainly done by means of constraints. If such a curve of least energy is deformed locally (e.g. by moving its control points) the concept of energy minimization is lost. In this paper we introduce deform operators with built-in energy terms. We have tested our ideas in a prototype system for modeling uniform B-spline curves. Through the use of widgets, the user can interactively modify the range of influence and other properties of the operators. Experiments show that these operators offer a very intuitive way of modeling.

We present a comparison between two recent approaches to the harmonic similarity of musical chords sequences. In contrast to earlier work that mainly focuses on the similarity of musical notation or musical audio, in this paper we specifically use on the symbolic chord description as the primary musical representation. For an experiment, a large chord sequence corpus was created. In this experiment we compare a geometrical and an alignment approach to harmonic similarity, and measure the effects of chord description detail and a priori key information on retrieval performance. The results show that an alignment approach significantly outperforms a geometrical approach in most cases, but that the geometrical approach is computationally more efficient than the alignment approach. Furthermore, the results demonstrate that a priori key information boosts retrieval performance, and that using a triadic chord representation yields significantly better results than a simpler or more complex chord representation.

This paper presents a novel two-parameter geometric graph, the γ-neighborhood graph. This graph unifies a number of geometric graphs such as the convex hull, the Delaunay triangulation, and in 2D also the Gabriel graph and the circle-based β-skeleton, into a continuous spectrum of geometric graphs that ranges from the void to the complete graph. The two parameters provide for a great flexibility in the analysis of a set of sites. For specific ranges of the parameters, the corresponding graph can be efficiently constructed.

Among the many 3D face matching techniques that have been developed, are variants of 3D facial curve matching, which reduce the amount of face data to one or a few 3D curves. The face's central profile, for instance, proved to work well. However, the selection of the optimal set of 3D curves and the best way to match them has not been researched systematically. We propose a 3D face matching framework that allows profile and contour based face matching. Using this framework we evaluate profile and contour types including those described in the literature, and select subsets of facial curves for effective and efficient face matching. With a set of eight geodesic contours we achieve a mean average precision (MAP) of 0.70 and 92.5% recognition rate (RR) on the 3D face retrieval track of the Shape Retrieval Contest (SHREC'08), and a MAP of 0.96 and 97.6% RR on the University of Notre Dame (UND) test set. Face matching with these curves is time-efficient and performs better than other sets of facial curves and depth map comparison.

In this work we compute the similarity of 3D faces using a set of eight contour curves. These contours were selected and matched using our 3D face matching framework. In previous work, we performed extensive research to the selection of distinctive facial curves for 3D face matching. To relate the performance of several of these curves to other face matching methods, we participated the Shape Retrieval Contest (SHREC) of 3D face scans. Within this contest we have used a set of eight C-contours and tested their face retrieval performance using two different distance measures. In an attempt to increase the expression invariance of these curves, we employed our 3D face matching framework to match either 100% of the selected features or the subset of the best 60% of the selected features. Results show that the selected distance measure can have a great influence on the distinctiveness of facial curves. In case of large variations in facia) expressiveness, the subset of the best 60% of the features increases the overall performance. With a recognition rate of 91.1% and a mean average precision of 0.693 our method performs reasonably well compared to other methods.

Three-Dimensional face recognition is a challenging task with a large number of proposed solutions [1, 2]. With variations in pose and expression the identification of a face scan based on 3D geometry is difficult. To improve on this task and to evaluate existing face matching methods large sets of 3D faces were constructed, such as the FRGC [3], BU-3DFE [4], and the GavabDB [5] database. When used in the same experimental way, these publicly available sets allow for a fair comparison of different methods. Usually, researchers compare the recognition rates (or identification rates) of different methods. To identify a person, its 3D face scan is enrolled as query in the database and if the most similar scan (other than the query) in the database belongs to the same person, he or she is identified correctly. For a set of queries, the recognition rate is computed as the average of zeros (no identification) and ones (correct identification). However, the recognition rate is a limited evaluation measure, because it considers merely the closest match of each query. In case you are using a database that contains two scans per expression per subject and you use each scan as query once, you are bound to find the similar scan on top of the ranked list. Such an experiment boosts the recognition rate, but gives no insight of the expression invariance of different methods. For that, an evaluation measure is required that takes a larger part of the ranked list into account. In this contest we compare different face matching methods using a large number of performance measures. As a test set we have used a processed subset of the GavabDB [5], which contains several expressions and pose variations per subject. 2 DATABASE For the retrieval contest of 3D faces we have used a subset of the GavabDB [5]. The GavabDB consists of Minolta Vi-700 laser range scans from 61 different subjects. The subjects, of which 45 are male and 16 are female, are all Caucasian. Each subject was scanned nine times for different poses and expressions, namely six neutral expression scans and three scans with an expression. The neutral scans include two different frontal scans, one scan while looking up ( +35 ), one scan while looking down ( -35 ), one scan from the right side ( +90 ), and one from the left side ( -90 ). The expression scans include one with a smile, one with a pronounced laugh, and an “arbitrary expression” freely chosen by the subject.

Adjacency and Laplacian matrices are popular structures to use as representations of shape graphs, because their sorted sets of eigenvalues (spectra) can be used as signatures for shape retrieval. Unfortunately, the descriptiveness of these spectra is limited, and handling graphs of different size remains a challenge. In this work, we propose a new framework in which the shapes (3D models in our test corpus) are represented by multi-labeled graphs. A Hermitian matrix is associated to each graph, in which the entries are defined such that they contain all information stored in the graph edges. Additional constraints ensure that this Hermitian matrix mimics the well-studied spectral behaviour of the Laplcian matrix. We therefore use the Hermitian Fiedler vector as shape signature during retrieval. To deal with graphs of different size, we efficiently reuse the calculated Fiedler vector to decompose the graph into a limited number of non-overlapping, meaningful subgraphs. Retrieval results are based on both complete matching and subgraph matching.

With ever growing databases containing multimedia data, indexing has become a necessity to avoid a linear search. We propose a novel technique for indexing multimedia databases, whose entries can be represented as graph structures. In our method, the topological structure of a graph as well as that of its subgraphs are represented as vectors in which the components correspond to the sorted Laplacian eigenvalues of the graph or subgraphs. We draw from recently-developed techniques in the field of spectral integral variation to overcome the problem of computing the Laplacian spectrum for every subgraph individually. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. The novelties of the proposed method come from the powerful representation of the graph topology and successfully adopting the concept of spectral integral variation in an indexing algorithm. Our experiments, consisting of recognition trials in the domain of 2D and 3D object recognition, including a comparison with a competing indexing method, demonstrate both the robustness and efficacy of the approach.

This paper presents a new multiview alignment algorithm that performs both the coarse and fine alignment of unordered sets of range scans. Our algorithm selects quadruples of range scans, which have feature points of their 2D projections in common. These quadruples are then verified using an iterative closest point (ICP) algorithm. The accepted quadruples form incomplete models of an object that can be aligned using isometries of the principal component analysis (PCA) in combination with an ICP algorithm. The output of our method is a set of finely aligned meshes. Our method was applied to range scans of different clusters of objects varying in the type of acquisition system, the number of range scans, the scan resolution, and scan accuracy. Results show that our method is both effective and efficient for the alignment of meshes: it is capable of aligning object meshes with various properties, aligns the majority of meshes without a priori knowledge, and doesn't require a multiview ICP algorithm to improve the final alignment.

This paper gives an overview of shape dissimilarity measure properties, such as metric and robustness properties, and of retrieval performance measures. Fifteen shape similarity measures are shortly described and compared. Their retrieval results on the MPEG-7 Core Experiment CE-Shape-1 test set as reported in the literature and obtained by a reimplementation are compared and discussed.

The Earth Mover's Distance (EMD) on weighted point sets is a distance measure with many applications. Since there are no known exact algorithms to compute the minimum EMD under transformations, it is useful to estimate the minimum EMD under various classes of transformations. For weighted point sets in the plane, we will show a 2-approximation algorithm for translations, a 4-approximation algorithm for rigid motions and an 8-approximation algorithm for similarity transformations. The runtime for translations is O(TEMD(n,m)), the runtime of the latter two algorithms is O(nmTEMD(n,m)), where TEMD(n,m) is the time to compute the EMD between two fixed weighted point sets with n and m points, respectively. All these algorithms are based on a more general structure, namely on reference points. This leads to elegant generalizations to higher dimensions. We give a comprehensive discussion of reference points for weighted point sets with respect to the EMD.

We propose the linear axis, a new skeleton for polygonal shapes. It is related to the medial axis and the straight skeleton, being the result of a wavefront propagation process. The wavefront is linear and propagates by translating edges at constant speed. The initial wavefront is an altered version of the original polygon: zero-length edges are added at reflex vertices. The linear axis is a subset of the straight skeleton of the altered polygon. In this way, the counter-intuitive effects in the straight skeleton caused by sharp reflex vertices are alleviated. We introduce the notion of e-equivalence between two skeletons, and give an algorithm that computes the number of zero-length edges for each reflex vertex which yield a linear axis e-equivalent to the medial axis. This linear axis and thus the straight skeleton can be computed from the medial axis in linear time for polygons with a constant number of “nearly co-circular” sites. All previous algorithms for straight skeleton computation are sub-quadratic.

Due to the recent improvements in laser scanning technology, 3D visualization and modeling, there is an increasing need for tools supporting the automatic search for 3D objects in archives. In this paper we describe a new geometric approach to 3D shape comparison and retrieval for arbitrary objects described by 3D polyhedral models that may contain gaps. In contrast with the existing approaches, our approach takes the overall relative spatial location into account by representing the 3D shape as a weighted point set. To compare two objects geometrically, we enclose each object by a 3D grid and generate a weighted point set, which represents a salient point for each non-empty grid cell. We compare three methods to obtain a salient point and a weight in each grid cell: (1) choosing the vertex in the cell with the highest Gaussian curvature, and choosing a measure as weight for that curvature, (2) choosing the area-weighted mean of the vertices in the cell, and choosing a measure as weight denoting the normal variation of the facets in the cell and (3) choosing the center of mass of all vertices in the cell, and choosing one as weight. Finally, we compute the similarity between two shapes by comparing their weighted point sets using a new shape similarity measure based on weight transportation that is a variation of the Earth Mover's Distance. Unlike the Earth Mover's Distance, the new shape similarity measure satisfies the triangle inequality. This property makes it suitable for use in indexing schemes, that depend on the triangle inequality, such as the one we introduce, based on the so-called vantage objects. The strength of our approach is proven through experimental results using a database consisting of 133 models such as mugs, cars and boats, and a database consisting of 512 models, mostly air planes, classified into conventional air planes, delta-jets, multi-fuselages, biplanes, helicopters and other models. The results show that the retrieval performance is better than related shape matching methods.

We propose a novel type of decomposition for polygonal shapes. It is thought that, for the task of object recognition, the human visual system uses a part-based representation. Decompositions based on skeletons have been previously proposed in computer vision. Our method is the first one, however, based on the straight line skeleton. Compared to the medial axis, the straight line skeleton has a few advantages: it contains only straight segments and has a lower combinatorial complexity. The skeletal nodes and the way they are generated are the basis for our decomposition, which has two stages that result in a decomposition into (possibly overlapping) parts. First, a number of visually striking parts are identified, then their boundaries are successively simplified, by locally removing detail. Our method runs in time ((n+r1+r22)log2 n), after the skeleton construction, where n is the number of vertices in the polygon, r1 the number of split events, and r2 the number of reflex edge annihilations. The decomposition is invariant to rigid motions and uniform scalings. We present results indicating that it provides plausible decompositions for a variety of shapes. This makes it attractive for partial shape matching in content-based image retrieval.

Shape matching is an important ingredient in shape retrieval, recognition and classification, alignment and registration, and approximation and simplification. This paper treats various aspects that are needed to solve shape matching problems: choosing the precise problem, selecting the properties of the similarity measure that are needed for the problem, choosing the specific similarity measure, and constructing the algorithm to compute the similarity. The focus is on methods that lie close to the field of computational geometry.

We derive a pseudo-metric for weighted point sets. There are numerous situations, for example in the shape description domain, where the individual points in a feature point set have an associated attribute, a weight. A distance function that incorporates this extra information apart from the points' position can be very useful for matching and retrieval purposes. There are two main approaches to do this. One approach is to interpret the point sets as fuzzy sets. However, a distance measure for fuzzy sets that is a metric, invariant under rigid motion and respects scaling of the underlying ground distance, does not exist. In addition, a Hausdorff-like pseudo-metric fails to differentiate between fuzzy sets with arbitrarily different maximum memebership values. The other approach is the Earth Mover's Distance. However, for sets of unequal total weights, it gives zero distance for arbitrarily different sets, and does not obey the triangle inequality. In this paper we derive a distance measure, based on weight transportation, that is invariant under rigid motion, respects scaling, and obeys the triangle inequality, so that it can be used in efficient database searching. Moreover, our pseudo-metric identifies only weight-scaled versions of the same set. We demonstrate its potential use by testing it on two different collections, one of company logos and another one of fish contours.

Large image databases are used in an extraordinary number of multimedia applications in fields such as entertainment, business, art, engineering, and science. Retrieving images by their content, as opposed to external features, has become an important operation. A fundamental ingredient for content-based image retrieval is the technique used for comparing images. There are two general methods for image comparison: intensity based (color and texture) and geometry based (shape). A recent user survey about cognition aspects of image retrieval shows that users are more interested in retrieval by shape than by color and texture [62]. However, retrieval by shape is still considered one of the most difficult aspects of content-based search. Indeed, systems such as IBM’s Query By Image Content, QBIC [57], perhaps one of the most advanced image retrieval systems to date, is relatively successful in retrieving by color and texture, but performs poorly when searching on shape. A similar behavior is exhibited in the new Alta Vista photo finder [10].

Visibility partitions play an important role in computer vision and pattern matching. This paper studies a new type of visibility, reflection-visibility, with applications in affine pattern matching: it is used in the definition of the reflection metric between two patterns consisting of line segments. This metric is affine invariant, and robust against noise, deformation, blurring, and cracks. We present algorithms that compute the reflection visibility partition in O((n+k) log(n)+v) randomised time, where k is the number of visibility edges (at most O(n2)), and v is the number of vertices in the partition (at most O(n2+k2)). We use this partition to compute the reflection metric in O(r(nA + nB)) randomised time, for two line segment unions, with nA and nB line segments, separately, where r is the complexity of the overlay of two reflection-visibility partitions (at most O(nA4 + nB4)).

This paper formulates properties of similarity measures. We list a number of similarity measures, some of which are not well known (such as the Monge-Kantorovich metric), or newly introduced (reflection metric), and give a set constructions that have been used in the design of some similarity measures.

On a collection of subsets of a space, fundamentally different metrics may be defined. In pattern matching, it is often required that a metric is invariant for a given transformation group. In addition, a pattern metric should be robust for defects in patterns caused by discretisation and unreliable feature detection. Furthermore, a pattern metric should have sufficient discriminative power. We formalise these properties by presenting five axioms. Finding invariant metrics without requiring such axioms is a trivial problem. Using our axioms, we analyse various pattern metrics, including the Hausdorff distance and the symmetric difference. Finally, we present the reflection metric. This metric is defined on finite unions of n - 1-dimensional hyper-surfaces in IRn. The reflection metric is affine invariant and satisfies our axioms.

Graphs are important structures to model complex relationships such as chemical compounds, proteins, geometric or hierarchical parts, and XML documents. Given a query graph, indexing has become a necessity to retrieve similar graphs quickly from large databases. We propose a novel technique for indexing databases, whose entries can be represented as graph structures. Our method starts by representing the topological structure of a graph as well as that of its subgraphs as vectors in which the components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

This paper presents an incremental approach to geometric constraint satisfaction that categorizes solutions into so-called quanta. A quantum is a range of solutions with uniform geometric characteristics. This approach is suitable for interactive design because it can handle (perhaps temporarily) incomplete specifications and alternative solutions, and performs satisfaction locally and incrementally. The intermediate solutions are kept in the geometric domain, so that new geometric constraints can be interpreted on the same high level of abstraction, allowing powerful reasoning. Both alternative discrete solutions and continuous ranges of solutions are determined. Propagation of information is performed by ‘propagation of known state’, and the information itself results from ‘solution set inference’, where a solution set is represented in geometrical form by unions and intersections of quantum labels. This representation allows the use of simple logical expressions of constraints, it uniformly handles delayed satisfaction, and it supports ‘constraint inference’, the derivation of implied constraints by geometric reasoning.