Publications

This work introduces a method to hierarchically segment articulated shapes into meaningful parts and to register these parts across populations of near-isometric shapes (e.g. head, arms and legs of humans in different body postures). The method exploits the isometry invariance of eigenfunctions of the Laplace-Beltrami operator and uses topological features (level sets at important saddles) for the segmentation. Concepts from persistent homology are employed for a hierarchical representation, for the elimination of topological noise and for the comparison of eigenfunctions. The obtained parts can be registered via their spectral projection across a population of near isometric shapes. This work also presents the highly accurate computation of eigenfunctions and eigenvalues with cubic FEM on triangle meshes and discusses the construction of persistence diagrams from the Morse-Smale complex as well as the relation to size functions.

In this paper, we first analyze different common discretizations of the Laplace-Beltrami operator (geometric Laplacians, linear and cubic FEM operators) in terms of the correctness of their eigenfunctions with respect to the continuous case. We then present the family of segmentations induced by the nodal sets of the eigenfunctions, discussing its meaningfulness for shape understanding.

This paper proposes the use of the surface based Laplace-Beltrami and the volumetric Laplace eigenvalues and -functions as shape descriptors for the comparison and analysis of shapes. These spectral measures are isometry invariant and therefore allow for shape comparisons with minimal shape pre-processing. In particular, no registration, mapping, or remeshing is necessary. The discriminatory power of the 2D surface and 3D solid methods is demonstrated at a population of female caudate nuclei (a subcortical gray matter structure of the brain, involved in memory function, emotion processing, and learning) of normal control subjects and of subjects with schizotypal personality disorder. The behavior and properties of the Laplace-Beltrami eigenvalues and -functions are discussed extensively for both the Dirichlet and Neumann boundary condition showing advantages of the Neumann vs. the Dirichlet spectra in 3D. Furthermore, topological analyses employing the Morse-Smale complex (on the surfaces) and the Reeb graph (in the solids) are performed on selected eigenfunctions, yielding shape descriptors, that are capable of localizing geometric properties and detecting shape differences by indirectly registering topological features such as critical points, level sets and integral lines of the gradient field across subjects. The use of these topological features of the Laplace-Beltrami eigenfunctions in 2D and 3D for statistical shape analysis is novel.

This paper proposes to use the volumetric Laplace spectrum as a global shape descriptor for medical shape analysis. The approach allows for shape comparisons using minimal shape preprocessing. In particular, no registration, mapping, or remeshing is necessary. All computations can be performed directly on the voxel representations of the shapes. The discriminatory power of the method is tested on a population of female caudate shapes (subcortical gray matter structure of the brain, involved in memory function, emotion processing, and learning) of normal control subjects and of subjects with schizotypal personality disorder. The behavior and properties of the volumetric Laplace spectrum are discussed extensively for both the Dirichlet and Neumann boundary condition showing advantages of the Neumann spectra. Both, the computations of spectra on 3D voxel data for the purpose of shape matching as well as the use of the Neumann spectrum for shape analysis are completely new.

This paper proposes to use the Laplace-Beltrami spectrum (LBS) as a global shape descriptor for medical shape analysis. The approach allows for shape comparisons using minimal shape preprocessing. In particular, no registration, mapping, or remeshing is necessary. The discriminatory power of the method is tested on a population of female caudate shapes of normal control subjects and of subjects with schizotypal personality disorder.

The question "Can one hear the shape of a drum" has been asked in several contexts before (e.g., by Bers and Kac). It is a pictorial way of asking if the eigenvalues of the Laplacian on a given domain completely characterize its shape, in other words, if the spectrum is a complete shape descriptor (which it is not in general).

In this talk we will give an overview on how the computation of the spectra can be accomplished using FEM for manifolds in 2D and 3D (e.g. iso-surfaces, boundary representations, solid bodies, vector fields...) with the Dirichlet and Neumann boundary condition. We demonstrate that it is computational feasible to numerically extract geometric properties (volume, area, boundary length and even the Euler characteristic) from the first eigenvalues. Since the spectrum contains geometrical information and since it is an isometry invariant and therefore independent of the object's representation, parametrization, spatial position, and optionally of its size, it is optimally suited to be used as a fingerprint (Shape-DNA) in contemporary computer graphics applications like database retrieval, quality assessment, and shape matching in fields like CAD, medicine or engineering.

We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study.

This patent describes a medial axis (MA) representation and parametrization of shapes for an accurate representation of the domain with possibly curved boundary. The MA represenation can be used to model, mesh and optimize the shape, due to its skeletal structure that follows the trend of the object and describes the local thickness. The proposed method closes the design optimization cycle and bridges the gap between the design, mesh construction and FEM analysis components for a complete and efficient automation.

In the area of image retrieval from data bases and for copyright protection of large image collections there is a growing demand for unique but easily computable fingerprints for images. These fingerprints can be used to quickly identify every image within a larger set of possibly similar images. This paper introduces a novel method to automatically obtain such fingerprints from an image. It is based on a re-interpretation of an image as a Riemannian manifold. This representation is feasible for gray value images and color images. We discuss the use of the spectrum of eigenvalues of different variants of the Laplace operator as a fingerprint and show the usability of this approach in several use cases. Contrary to existing works in this area we do not only use the discrete Laplacian, but also with a particular emphasis the underlying continuous operator. This allows better results in comparing the resulting spectra and deeper insights in the problems arising. We show how the well known discrete Laplacian is related to the continuous Laplace-Beltrami operator. Furthermore we introduce the new concept of solid height functions to overcome some potential limitations of the method.

This books gives a detailed overview on the mathematical background of the Laplace Beltrami operator (LBO) for a Riemannian manifold. A few analytical computations are presented for special domains in 2D and 3D. Furthermore the numerical computation of the spectra of the LBO are described using a special method for planar domains and the FEM method with up to cubic form functions for the general setup in 2D and 3D. Since the spectrum of the LBO is an isometry invariant, it is invariant under translation, rotation, and invariant under a change of parametrization. It is therefore possible to construct complex objects by gluing several parameter spaces to each other. Some examples are presented, also employing the medial axis as a tool to guide the parametrization of any 2D domain in a way that ensures good meshes without any error at the boundary.

Furthermore this book describes the extraction of geometric data from the spectrum. For this purpose the rapid convergence of the Heat trace is shown. Finally several applications and examples are presented to employ the spectrum in the field of shape recognition. Examples of isospectral 3D solids are shown, that can be distinguished by the spectrum of their boundary surface. The robustness is demonstrated when objects on different mesh resolutions are successfully compared. It is shown how the Neumann boundary condition can be used instead of the Dirichlet condition in cases where the boundary is not supposed to play an important role. finally several complex objects are matched successfully employing their Laplace-Beltrami spectrum.

This paper describes in detail a method to extract fingerprints of any surface or solid object by taking the eigenvalues of its respective Laplace-Beltrami operator. Since the spectrum is an isometry invariant it is independent of the objects representation including parametrization, spatial position and of its representation (e.g. NURBS or any parametrized or implicitly represented surface or even for polyhedra). Therefore checking if two objects are isometric needs no prior alignment (registration / localization) of the objects, but only a comparison of their (normalized) spectra, the Shape-DNA.
In this paper we describe the computation of the Shape-DNA and their comparison. We also give an overview on implementation issues like meshing, numerics and the used "Atlas" data structure allowing principally to compute eigenvalues of topologically complex objects by gluing surface patches. Exploiting the isometry invariance of the Laplace-Beltrami operator we succeed in computing eigenvalues for smoothly bounded objects without discretization errors caused by approximation of the boundary.
Furthermore we show the rapid convergence of the heat trace series and demonstrate that it is computationally feasible to extract geometrical data such as the volume, the boundary length and even the Euler characteristic from the numerically calculated fingerprint data. This fact not only confirms the exactness of our computed eigenvalues, but also underlines the geometrical importance of the spectrum.
With the help of the here described Shape-DNA it is possible to support copyright protection, database retrieval and quality assessment of digital data representing surfaces and solids.

This paper introduces a method to extract fingerprints of any surface or solid object by taking the eigenvalues of its respective Laplace-Beltrami operator. Using an object's spectrum (i.e. the family of its eigenvalues) as a fingerprint for its shape is motivated by the fact that the related eigenvalues are isometry invariants of the object. Employing the Laplace-Beltrami spectra (not the spectra of the mesh Laplacian) as fingerprints of surfaces and solids is a novel approach in the field of geometric modeling and computer graphics. Those spectra can be calculated for any representation of the geometric object (e.g. NURBS or any parametrized or implicitly represented surface or even for polyhedra).

Since the spectrum is an isometry invariant of the respective object this fingerprint is also independent of the spatial position. Additionally the eigenvalues can be normalized so that scaling factors for the geometric object can be obtained easily. Therefore checking if two objects are isometric needs no prior alignment (registration / localization) of the objects, but only a comparison of their spectra. With the help of such fingerprints it is possible to support copyright protection, database retrieval and quality assessment of digital data representing surfaces and solids.

This patent describes a method to identify and compare shape of solids, surfaces and images by using the spectrum of the Laplace-Beltrami operator of the given object as a fingerprint. Please see our corresponding publications for a detailed description of the properties and the numerical computation of these spectra for the different kinds of objects. Possible applications like "Copyright protection", "Database retrieval", "Shape Matching" and "Quality Assessment" are described, making use of the fact that the spectrum is an isometry invariant and therefore completely independent of the objects representation and spatial position. Furthermore it is shown how the spectra can be compared independently of the objects size, if desired.

This work gives an overview on representation and processing of geometric models. Volume based representations (e.g. voxel rep.) and boundary representations (planar polygons, parametric surfaces defined by a map from 2D-space to 3D-space, especially spline surfaces and trimmed surfaces, multiresolutionally represented surfaces, e.g. wavelet-based surfaces and surfaces obtained by subdivision schemes) as well as explicit or implicit mathematical object representations are described and compared. The rather new method of "Medial Modeling", where an object is described by its medial axis and an associated radius function, is also presented. This medial modeling concept developed at the Welfenlab yields a very intuitive user interface useful for solid modeling, and also gives as a by-product a natural meshing of the solid for FEM computations. Finally additional attributes that can be attached to an object, i.e. attributes of physical origin or logical attributes, are discussed.