• Topology Matching for Full Automatic Similarity Estimation of 3D Shape, 2001.
• A Reeb graph-based representation for non-sequential construction of topologically complex shapes, 1998.
• Shape Modeling & Shape Analysis Based on Singularities, 1996.
• Algorithms for extracting correct critical points & constructing topological graphs from discrete geographical elevation data, 1995.
• Modeling Contact of Two Complex Objects: with an Application to Characterizing Dental Articulations, 1995.
• Coding of Object Surfaces Using Atoms, 1994.
• Surface coding based on Morse theory, 1991.

BibTeX references.

Link at Beckman Institute.

Link to Aizu's team other related publications.

Link @ Tokyo U.

There is a growing need to be able to accurately and efficiently search visual data sets, and in particular, 3D shape data sets. This paper proposes a novel technique, called Topology Matching, in which similarity between polyhedral models is quickly, accurately, and automatically calculated by comparing Multiresolutional Reeb Graphs (MRGs). The MRG thus operates well as a search key for 3D shape data sets. In particular, the MRG represents the skeletal and topological structure of a 3D shape at various levels of resolution. The MRG is constructed using a continuous function on the 3D shape, which may preferably be a function of geodesic distance because this function is invariant to translation and rotation and is also robust against changes in connectivities caused by a mesh simplification or subdivision. The similarity calculation between 3D shapes is processed using a coarse-to-fine strategy while preserving the consistency of the graph structures, which results in establishing a correspondence between the parts of objects. The similarity calculation is fast and efficient because it is not necessary to determine the particular pose of a 3D shape, such as a rotation, in advance. Topology Matching is particularly useful for interactively searching for a 3D object because the results of the search fit human intuition well.

Notes:

1. Introduction and Related Work

• Increasing number of 3D models
• Need for searching 3D models
• 2D previous work: recognizing from shape (e.g., curvature) or image properties (e.g., color, texture, wavelet coeffs.)
• 3D previous work:
  • CAD/CAM feature extraction: too domain specific
  • Curvature: too sensitive to noise
  • Global histogram: cannot estimate local features
• Required features (to handle Global and Local properties simultaneously):
  • Concise representation of shape
  • Catch features of shape well
  • Computed automatically and robustly for general shapes
• Propose to use a "skeletal structure"
• Previous work
  • Medial Axis:
    • Computationally expensive,
    • Sensitive to noise and small undulations,
    • May have "degenerate surfaces"
  • Reeb graphs:
    • Skeleton determined using a continuous scalar function, mu, defined on an object
    • Always one dimensional (1D) graph structure
    • Invariant to translation and rotation (--> if mu chosen carefully).
    • Robust against connectivity changes caused by simplification, subdivision, remeshing.
    • Resistant against noise and deformation
    • Possible to use multiresolutional structure
• Propose a Multiresolution Reeb Graph (MRG) based on geodesic distance

2. Reeb Graph and Its Multiresolutional Extension

2.1 Reeb Graph

• Define mu as a continuous real function on an object C (in 3D space): mu: C --> R .
• The Reeb graph of mu in the quotient space C x R is defined as an equivalent class
  • (X1, mu(X1)) ~ (X2, mu(X2)) iff
    • mu(X1) = mu(X2)
    • X1 and X2 are in the same connected component of Inverse(mu).mu((X1)
• If mu is defined on a manifold with non-degenerate critical points, mu is Morse.
  • Simple example: height function on 2D manifold (most previous work use this)
    • mu(v(x,y,z)) = z
    • Example: torus, Reeb graph corresponds to connectivity information for iso-contours.

2.2 Multiresolutional Reeb Graph

• Create Reeb graphs at different levels of detail
  • Object is partitioned into regions based on function mu
  • Node = connected component, adjacent nodes are linked by edges
  • If components touch each other in the object go to finer level: repartition each region
  • Graph properties:
    • Parent-child relationships between nodes of adjacent levels
    • Converges to original Reeb graph
    • Finer level Reeb graph contains all info of coarser levels

3. Definition of the Continuous Function mu for Topology Matching

• Use geodesic distance (on the surface S of object C ) --> to achieve rotation invariance and resistance against problems caused by noise or small undulations
• Lazarus & Verroust: Level Set Diagram (LSD), geodesic distance from source point.
  • Difficult to automatically and stably find source point.
  • Solution: define mu as the sum of geodesic distances, g, from a point v to all other points, p, on surface S :
    
  • Normalize mu to make it invariant under scaling:
    • mu_norm = (mu - minimum mu)/(maximum mu)
      (NB: minimum value of mu corresponds to most central point on object)
    • Examples:
      • mu_norm is zero everywhere for a sphere
      • more asymmetric shapes have wider range of values

4. Construction of the Multiresolutional Reeb Graph

• Method described for triangle mesh

4.1 Calculating the Integral of Geodesic Distance

• Computationally expensive to compute all geodesic distances
• Approximate by Dijkstra's algorithm based on edge length (of pre-processed mesh)
• Because mu_norm value is assigned to each vertex, distribution of vertices has to be fine enough to represent well the distribution of the function:
  • It is sometimes necessary to resample until all edge lengths < threshold.
• If edges are uniform in a certain direction, then mu values are biased:
  • Introduce short-cut edges to make direction of edges more isotropic
    
• mu for a "base vertex" b is discretely approximated by:
  • Sum of lengths of shortest paths to all other vertices, times area(b), where
    • area(b) = Sum of area of faces < distance r away from b
    • r = sqrt(0.005 * area(S)) generates about 150 base vertices

4.2 Construction of the Multiresolutional Reeb Graph

• First construct finest resolution Reeb Graph:
• Divide domain (range of the function) of mu_norm into K ranges.
• Triangles lying over range boundary are subdivided s.t. each triangle belongs to exactly one range.
• Find connected components in each range (sets of triangles). Each component corresponds to one R-node.
• If triangle sets between adjacent ranges are connected, add an edge between corresponding R-nodes.
• Then construct coarser levels by unifying adjacent R-nodes, while maintaining parent-child relationships.

4.3 Computational Cost for Constructing the Multiresolutional Reeb Graph

• O(n log n) (because of Dijkstra, in 2D, i.e., along a surface), n == vertex count of mesh
• Mesh of 10,000 vertices, using 150 base vertices: 15 seconds on Pentium II 400 MHz

5. Matching Algorithm

5.1 Overview

• Each R-node gets an attribute m, at finest level: "using area and length of triangle set"
• Coarser levels: sum of attributes of child nodes
• Similarity between nodes is defined as similarity between attributes: sim(m, n)
  • 0 <= sim(m, n) <= sim(m, m)
  • sum of sim(m, m), over all m = 1
  • sim(R, S) = sum over all m in R, n in S of sim(m, n), (R and S Reeb graphs)
• Added restriction: Maintain topological consistency
• Match coarse to fine:
  • Add coarsest nodes of R and S to NLIST
  • Find matching node pair that preserves topological consistency
  • Move pair to MPAIR, insert child nodes of pair into NLIST
  • If NLIST not empty goto second step
  • Else compute sim(R, S) using pairs in MPAIR

5.2 Topological Consistency of the Multiresolutional Reeb Graph

• Two rules: R-nodes can only be matched if:
  • They are in the same range, and their parents are matched
  • Their MLISTs are the same. MLIST = list of matching labels propagated to that R-node (avoids matching nodes in different branches).

• Matching label is propagated in direction of monotonic increase or decrease of mu_norm

5.3 Finding the Matching of R-node Pairs

• Find R-node for which sim(m, m) is maximal (node that affects final result the most)
• Find candidate matching nodes (same mu_norm range, parents must match, equal MLIST)
• If no candidates, remove R-node
• Select from candidates using matching function mat(m, n)
• mat(m, n) computed using two aspects of similarity:
  • "loss of similarity" because of:
    • Matching m and n
    • Matching adjacent nodes to m and n
    • loss(m, n) = 0.5 * [sim(m, m) + sim(n, n)] - sim(m, n)
      (i.e. decrease in final similarity value)
  • Taking adjacent R-nodes into account:
    • mat(m, n) = -loss(m, n) - [sum over all adjacent mu_norm ranges of loss(adj(m), adj(n))]
      adj(m) = adj([s, t>, m) = sum of attr. of all adjacent R-nodes in [s, t) > range

• They limit adj([s, t>, m) to R-nodes in NLIST to save computation time

5.4 R-node Attribute and Similarity

• m = (a(m), l(m))
• a(m) = (1/rnum) * area(m) / area(S)
• l(m) = (1/rnum) * len(m) / (sum of len(n) for all n)
• len(m) = max(m) - min(m) (max and min of mu_norm in range)
  len(m) is not always equal to the range size
• First compute attributes at finest levels, then sum for coarser levels
• sim(m, n) = w * min(a(m), a(n)) + (1 - w) * min(l(m), l(n))

5.5 Matching at a mu_norm Region Boundary

• Sensitivity to the placement of the region boundaries of the function mu_norm:
  • Slight differences in ranges can cause very different graphs
  • Example: height function on torus

• Fix: allow one node m to match two nodes (n1, n2) if they are adjacent to the same R-node

6. Experiments of Similarity Estimation

• 230 meshes (Viewpoint, 3Dcafe, Stanford, own data)
• Pentium II 400 MHz, running Linux
• "resolution was 7" (= finest resolution has 64 ranges)
• w = 0.5

6.1 Correspondence between Two Models

• Two frogs, parts of legs of frogs match despite deformation (bent vs. stretched legs)

6.2 Matching Experiment

6.3 Search Experiment

• Pick one model out of the 230, and search against the remaining 229 models
• Four images shown for 6 query models: apple, dolphin, ring, car, frog, plant
• Overall good results

• "We believe that the results agree well with general human intuition."
• Results are reasonable for certain classes:
  • frog, animal1, dinosaur2, dolphin, stick, car, ellipse, dragon, donut, earring, sphere
    (NB: dinosaur2, dragon, earring are very small classes)
• Results are bad (i.e. almost exclusively white) for:
  • tableware, aircraft, animal4, machine, kitchenware, many holes, anatomy, face, others
• Computations: Average of about 12 seconds to compute 229 similarities, range [1, 37] seconds;
  depends on number of R-nodes in query object
  (sphere has 7 R-nodes, 1 second query time, plant has 2,000, 37 seconds)

7. Conclusions - Future work:

• Morphing, pose estimation
• Use more attributes to calculate similarity (e.g. color, curvature).
• Experimenting with Euclidean instead of geodesic distance: Deformation detection.
• Apply to volumetric data, use density function for mu.

The shape data of many complex objects, such as anatomical structures, are available in the form of contour slices. To visualize these complex shapes, most existing methods focus on resolving the contours connectivities and generating surface models. These methods do not offer any way of abstracting characteristic features from these complex shapes. To address this problem, Morse theory has previously been proposed as a topological abstraction tool, and a Morse theory-based surface coding system has been developed to code complex shapes as a sequence of basic operators. The topological structure of the coded surface is, however, implicitly stored in the operators. Topological information is thus not readily available without evaluating the operators. This paper proposes a more versatile representation by incorporating a contour containment relation into the earlier representation. With the explicit topological information, non-sequential construction and modifications can be performed without violating topological integrity. Editing operators similar to the Euler operators are also proposed.

Author Keywords: critical points; contours; Reeb graph; topology; Euler operators

To analyze given object shapes, it is necessary first to model the shapes and then to analyze the models. This paper proposes a method of modeling and analyzing two-dimensional (2D) and three-dimensional (3D) shapes based on singularities. First, a function is defined on an object. The object is then modeled by the distribution of the singularities of the function. Finally, the extracted singular points are analyzed by a Reeb graph together with wavelets for multiresolution analysis. The applications of the method include analysis of botanical leaf shapes and human facial expressions.

Keywords :

• singularity, shape analysis, multiresolution analysis, Reeb graph, wavelet, ridge and ravine.

To understand the essential properties of given data of object shapes, it is necessary to abstract them. The data is often given in the form of mesh data and equi-height contours in the case of terrain shapes, and cross-sectional images in the case of CT or MRI of human organs. To abstract such shape data, we have proposed a method based on singularities.

The basic idea is to define a function on the object and use the singularities of the function to abstract the object shape. First, let us take an example of a function k:x -> k(x) defined on a curve parameterized by x. In this case, the singular points are the maxima, minima and the inflection points of the function k. The singular points represent the global structure of the curve. Let us take another example of a three-dimensional (3D) solid object. In this case, we define a height function $h$ on its surface with its height axis in the z-direction. h gives the height of a point P located at (x,y,z) on the object surface; i.e., h(P) = z. The singular points of the function h are the peaks, passes and the pits of the object surface. We represent the shape of the object by describing the singular points together with the relationships among them. We call the description codes in what follows.

A singular point is said to be nondegenerate if the Hessian matrix H of the function is at its full rank. The number of negative eigen values of H is called the index of the singular point.

The singular points are closely related to the topology of the object, and hence suitable for abstracting its shape In a word, the singular points work in a similar way as the vertices, edges and faces of polyhedra; i.e., they represent the topological skeleton of the object. To be more precise, in the case of a function defined on the 2D surface, a singular point with index 0 is a pit, and it corresponds to a vertex of a polyhedron. A singular point with index 1 is a pass, and it corresponds to an edge. A singular point with index 2 is a peak, and it corresponds to a face.

This paper explains how to use the abstraction method of shapes by singularities for various types of data: bounding curves, equi-height contours, cross-sectional images, surface normals and mesh data. The applications that can be covered are the analysis of botanical leaf shapes, terrain shapes, human organs, and facial expressions.

We proposed a robust and exact method that extracts the singular points from the discrete elevation data while satisfying the Euler equation, and also a method that converts a surface network to the Reeb graph.

The interference of the motion paths of objects has been an important theme of research. The previous works concentrate on detecting collisions and finding colliding points, and little has been done on characterizing the contact of two objects considering the structures of the space between the objects. This paper proposes a novel method to characterize the interference of objects. Our method is based on the analysis of the structures of the complementary space of 3D objects. The topological structures are analyzed using the coding method based on the Morse theory and the Reeb graph. The method is applied to actual dental articulations to validate the model.

This paper proposes a new method to code the surface of a three-dimensional object using mathematical primitives called atoms. This method is an expansion of the method that codes the smooth surface of a natural object such as a human organ by the singular points of the height function based on Morse theory. It allows to handle the cases where there is more than one singular point on a level cross-sectional plane. Using the atoms, non-orientable surfaces such as the two-dimensional projective space and the Klein bottle can be coded. The method is further expanded to allow direct description with multiple height functions.

Keywords :

• Computer Graphics; Differentiable Manifolds; Hessian Matrix; Homotopy Types; Image Coding; Image Processing; Image reconstruction; Morse Theory; Surface Coding.

Coding the shape of a solid or a surface in space amounts to representing it as a sequence of symbols. For manufactured solids, the shape is the result of a finite number of elementary operations, such that codings are available, either directly in the form of sequences of manufacturing commands or by using a few elementary shape primitives associated with these operations. In the case of natural objects such as those found in biology or medicine, a shape can have so many more degrees of freedom such that coding them demands some simplification, together with a loss of information and a gain in conceptualization. Topology is a mathematical means of performing such simplifications which, for instance, considers two objects as being equivalent if their points are given a one to one correspondence by a bicontinuous transformation. There are, however, many different topological classifications so that to choose one it is necessary to take into account such factors as the way data is obtained, or the purpose of the coding. This paper addresses objects determined from sections, with the experience of anatomical reconstructions from microscopic sections. The basic mathematical tool for interpreting the sections of 3-D objects is Morse theory, but we shall show that it is not sufficiently precise for our problem and we shall sketch some extensions to it.