Search

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.

The combination of LiDAR data with panoramic images could be of great benefit to many geo-related applications and processes such as measuring and map making. Although it is possible to record both LiDAR points and panoramic images at the same time, there are economic and practical advantages to separating the acquisition of both types of data. However, when LiDAR and image data is recorded separately, poor GPS reception in many urban areas will make registration between the data sets necessary. In this paper, we describe a method to register a sequence of panoramic images to a LiDAR point cloud using a non-rigid version of ICP that incorporates a bundle adjustment framework. The registration is then refined by integrating image-to-reflectance data SIFT correspondences into the bundle adjustment. We demonstrate the validity of this registration method by a comparison against ground truth data.

For the convincing modeling of virtual humans, realistic breathing is an important aspect. This paper is about the simulation of breathing, based on anatomical and physiological principles. We have built a torso, including a thorax, a deformable belly, and muscles. This results in a model with two independent breathing systems, namely abdominal and chest breathing, which gives a high degree of realism in simulating breathing. The generated spirograms, diagrams of lung volume changes, are comparable to normal human ones according to a medical expert. The generated videos show convincing breathing sequences at various frequencies. The model itself is made available for public use.

In this paper we develop methods for computer aided folk song variation research. We examine notions and examples of stability for pitches and implied chords for a group of melodic variants. To do this we employ metrical accent levels, simple alignment techniques and visualization techniques. We explore how one can use insight into stability of a known set of variants to query for additional variants.

This paper presents an automatic efficient method to fit a statistical deformation model of the human face to 3D scan data. In a global to local fitting scheme, the shape parameters of this model are optimized such that the produced instance of the model accurately fits the 3D scan data of the input face. To increase the expressiveness of the model and to produce a tighter fit of the model, our method fits a set of predefined face components and blends these components afterwards. Quantitative evaluation shows an improvement of the fitting results when multiple components are used instead of one. Compared to existing methods, our fully automatic method achieves a higher accuracy of the fitting results. The accurately generated face instances are manifold meshes without noise and holes, and can be effectively used for 3D face recognition: We achieve 97.5% correct identification for 876 queries in the UND face set with 3D faces. Our results show that contour curve based face matching outperforms landmark based face matching.

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.

After text retrieval, the next waves in web searching and multimedia retrieval are the search for and delivery of images, music, video, and 3D scenes. Not only the perceptual and cognitive aspects, but also many of the algorithmic and performance aspects are still badly understood. One relevant issue is the design of dissimilarity measures (distance functions) that have desired properties. Another aspect is the development of algorithms that can compute or approximate these distances efficiently. Indexing data structures and search algorithms are necessary to make the search more efficient than sequential browsing through large collections. Apart from provable properties of individual algorithms, the experimental verification of the performance of a complete retrieval system is important to analyse merits and drawbacks of certain approaches, and to compare various techniques.

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.

Many researches in face recognition have been dealing with the challenge of the great variability in head pose, lighting intensity and direction,facial expression, and aging. The main purpose of this overview is to describe the recent 3D face recognition algorithms. The last few years more and more 2D face recognition algorithms are improved and tested on less than perfect images. However, 3D models hold more information of the face, like surface information, that can be used for face recognition or subject discrimination. Another major advantage is that 3D face recognition is pose invariant. A disadvantage of most presented 3D face recognition methods is that they still treat the human face as a rigid object. This means that the methods aren't capable of handling facial expressions. Although 2D face recognition still seems to outperform the 3D face recognition methods, it is expected that this will change in the near future.

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.

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.

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.

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.

We report on the use of the generic programming paradigm in the computational geometry algorithms library cgal. The parameterization of the geometric algorithms in cgal enhances flexibility and adaptability and opens an easy way for abolishing precision and robustness problems by exact but nevertheless efficient computation. Furthermore we discuss circulators, which are an extension of the iterator concept to circular structures. Such structures arise frequently in geometric computing.

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.

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 a database of about 48,000 hieroglyphic polylines.

This paper is about systems support for interactive computer graphics. The aim is to integrate the two major approaches to dealing with complexity in the design and implementation of such systems, namely, constraints and object-oriented programming.

This paper presents an incremental approach to geometric constraint satisfaction that is suitable for interactive design by categorizing solutions into so called quanta. A quantum is a range of solutions with uniform geometric characteristics. In this way, the constraint management system keeps the intermediate solutions in the geometric domain, so that new geometric constraints can be interpreted on the same high level of abstraction. This approach leads to a number of advantages: the system •can handle (perhaps temporarily) under-constrained specifications, •represents both alternative discrete solutions and continuous ranges of solutions, •performs satisfaction locally and incrementally, •supports constraint inference and geometric reasoning, •preserves the declarative semantics of constraints.

Object-oriented concepts are particularly applicable to Computer Graphics in its broadest sense — interaction, images synthesis, animation, and CAD. Research in Object-Oriented Graphics has lead to a critique of the object-oriented theory. The aim of the second Eurographics Workshop on Object-Oriented Graphics was to address fundamental issues arising from the use of object-oriented techniques in computer graphics, to provide a platform to state views on relevant issues, and discuss possible research programmes to address remaining unresolved problems.

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.