Last update: November 9, 2005

BACK

Publications on shape symmetry elicitation by Annick Montanvert, Dominique Attali, et al. :

• Delaunay Conforming Iso-surface, Skeleton Extraction and Noise Removal, 2001+
• Computing and Simplifying 2D and 3D Continuous Skeletons, 1997.
• r-Regular Shape Reconstruction from Unorganized Points, 1997 & 1998.
• Skeletal Reconstruction of Branching Shapes, 1996 & 1997.
• Modeling noise for a better simplification of skeletons, 1996.
• Squelette et Graphe de Voronoi 2D et 3D, PhD thesis of D.Attali, 1995.
• Using polyballs to approximate shapes and skeletons, 1994.

BibTeX references.

Skeletons provide a synthetic and thin representation of objects. Therefore, they are useful for shape description. Recent papers have proposed to approximate the skeleton of continuous shapes using the Voronoi graph of boundary points. An original formulation is presented here, using the notion of polyballs (we call polyball any finite union of balls). A preliminary work shows that their skeletons consist of simple components (line segments in 2D and polygons in 3D). An efficient method for simplifying 3D continuous skeletons is also presented. The originality of our approach consists in simplifying the shape without modifying its topology and in including these modifications on the skeleton. Depending on the desired result, we propose two strategies which lead to either surfacical skeletons or wireframe skeletons. Two angular criteria are proposed that allow us to build a size-invariant hierarchy of simplified skeletons.

3 classes of methods for computing skeletons:

1. Exact methods : use an analytic representation of the boundary (like polygons).
2. Discrete methods : thiniing, distance maps, ...
3. Continuous methods : Voronoi-based, no need for a continuous contour.

Definitions of neighborhood graphs :

Voronoi Graph - Vor(E) :

Let E be a finite set of points in R^n and p a point of E. The Voronoi region of p is the set of points of R^n closer to p than to any other element of E :

The Voronoi regions are convex polygons in 2D and convex polyhedra in 3D. The Voronoi graph of E, Vor(E), consists of the boundaries of the Voronoi regions of E. The Voronoi graph of n points can be computed in O( n log n + n^[N/2] ) in an N-D space.

Delaunay Tessellation - Del(E) :

It is the dual of the Voronoi grap and consists in a tessellation of the convex hull of E. It is made up of simplices whose circumscribed balls contain no other points of E. The simplices are triangles in 2D and tetrahedra in 3D for non-degenerate cases, i.e., s.t. no 4 points are co-circular in 2D or no 5 points are co-spherical in 3D. Like the Voronoi graph, it can be computed in O( n log n + n^[N/2] ) in an N-D space, and is denoted Del(E).

Gabriel graph - GG(E) :

It is a set of simplices ] s1, s2, ..., sN [ s.t. the smallest ball passing through N points ( p1, p2, ..., pN ) contains no other points of E in its interior. It can be constructed from Del(E) by removing from it each N-face not intersecting its dual Voronoi edge. It can also be computed in O( n log n + n^[N/2] ) in an N-D space, and is denoted GG(E),

Skeleton approximation through the use of the Voronoi graph

There are 4 different definitions :

1. SK1 : Use only the Voronoi vertices inside the set X.
2. SK2 : Use the Voronoi elements inside the set X.
3. SK3 : Intersection of the Voronoi graph with the sampled boundary E of set X.
4. SK0 : Dual of a polygonal approximation P of the sampled boundary E of X.

Properties:

• SK1: if the boundary of X is C³, then the set of Voronoi vertices tend to the skeleton of X and its complement; introduced by Schmitt.
• SK2 is the exact skeleton for a set made of the finite union of balls Y approximating the set X; it is a super-set of SK1; introduced by Brandt & Algazi. SK2 ensures convergence to the exact skeleton.
• SK3 is a super-set of SK2, introduced by Ogniewicz.
• SK0 requires (contour containment condition) that the boundary of P be included in the Delaunay tessellation of E (or be r-regular); introduced by Boissonnat. SK0 preserves homotopy and reversibility.

Theorem 1 : Containment property (in 2D only)

• Let P in R² be a polygonal object and let E be the vertices of P. If P is included in the Gabriel graph of E, then:
  • Boundary(P) is included in the Delaunay tessellation of P
  • SK0(P) is included in P
  • SK0(Pc) is included in Pc, where Pc is the complement of P.

Thus, when the boundary of the polygonal approximation P is included in the Gabriel graph of E, the contour containment is verified and the skeletons SK0(P) & SK0(Pc) do not intersect the boundary of P.

Theorem 2 : Equivalence between SK0 & SK2 (in 2D only)

• Let P in R² be a polygonal object and let E be the vertices of P. If P is included in the Gabriel graph of E, then:
  • SK2(P,E) = SK0(P)
  • SK2(Pc,E) = SK0(Pc)

3D Skeleton Simplification

Proposed "removing" criterion is scale-invariant and based on a generalized "bisector" angle.

A simplex T is removed from the current shape if the 2 following properties are verified:

1. The homotopy class of the shape is not modified when T is removed.
2. T is not relevant according to a certain criterion.

When the simplex T is removed, its associated Voronoi vertex v and all the Voronoi elements going through v are also removed from the skeleton.

Preserving Homotopy :

In 2D, only one type of triangle can be removed, which is associated with extremities of the skeleton and has one inner edge and 2 boundary edges: the hat triangle.

In 3D, 2 types of inner tetrahedra can be removed:

1. Hat tetrahedron : Has 3 boundary faces and 1 inner face. Removing it shortens a skeletal branch. The vertex v associated with a hat tetrahedron is called a skeleton extremity .
2. Salient tetrahedra : Has 2 boundary faces, 2 inner faces, and 1 inner edge. Its removal involves the removal of the associated Voronoi vertex v, called a skeleton border, and of the Voronoi polygon going through v.

Two different strategies are possible to simplify 3D skeletons:

1. Simplified surfacical skeleton :
   • Remove possible branches and preserve significant borders.
   • Hat tetrahedra are systematically removed (they imply 1D parts of the skeleton).
   • Salient tetrahedra are removed only if they verify a removing criterion:
     • The angle alpha(v) between the 2 faces in common with the object boundary is smaller than a given threshold (e.g. pi/3).
2. Simplified wireframe skeleton :
   • Remove possible borders and preserve siginificant branches.
   • Salient tetrahedra are systematically removed (they imply 2D parts of the skeleton).
   • Hat tetrahedra may be preserved; they are removed according to the following criterion:
     • the solid angle ß of v w/r to the boundary surface A(v) associated to v, is smaller than some threshold (e.g. pi) - approximates the amount of boundary surface v "sees", or how deep in the shape v is, the smaller the solid angle, the closer v is to the object surface, the less significant is v's contribution to the skeleton. This is a generalization of the idea of bisector angle in 2D to 3D (Fig.3).

Polyballs and their exact skeletons

In 2D, the skeleton of a polygon is made of straightline segments and portion of parabolic curves.

In 3D, the skeleton of a polyhedron is made of pieces of quadrics.

Polyball : Any finite union of balls.

Generating balls : minimum number of balls {Bi} that covers a polyball Y.

Theorem 3 : Skeleton of polyballs in 2D

• Let Y in R² be a polyball. The skeleton of Y is made of the centers of the disconnected balls and a subset of the Voronoi graph of its singular points. The latter are formed of the points m in Y s.t. the closest points to m on the boundary of Y are singular points (concavities).

Theorem 4 : Skeleton of polyballs in 3D

• The skeleton of Y is made of the centers of the disconnected balls, the straightline segments connecting the centers of the quasi-disconnected balls, and a subset ofthe Voronoi graph of its singular points. The latter are formed of the points m in Y s.t. the closest points to m on the boundary of Y are singular points.

The skeleton of a polyball, in 2D or 3D, has a very simple structure. Its computation boild down to the computation of a Voronoi graph.

In this paper, the problem of reconstructing a surface, given a set of scattered data points is addressed. First, a precise formulation of the reconstruction problem is proposed. The solution is mathematically defined as a particular mesh of the surface called the normalized mesh. This solution has the property to be included inside the Delaunay graph. A criterion to detect faces of the normalized mesh inside the Delaunay graph is proposed. This criterion is proved to provide the exact solution in 2D for points sampling a r-regular shapes with a sampling path e < sin (pi/8)r. In 3D, this result cannot be extended and the criterion cannot retrieve every face. A heuristic is proposed in order to complete the surface.

Keywords: Shape reconstruction; Interpolation; Delaunay graph; Voronoi graph; Normalized mesh; r-regular shape; Sample points.

We present a new method for the implicit reconstruction of branching shapes from a set of scattered data points. The method is based on the computation of a geometric skeleton inside the data set. This skeleton is simplified in order to filter noise and converted into skeletal elements -- a graph of interconnected curves -- that generate an implicit surface. We use Bézier triangles as extra skeletal elements to perform bulge free blends between branches while controlling the blend extent. This leads to a smooth implicit representation of the shape, directly computed in a purely geometric way.

Modeling Noise

Let the shape X be sampled as a set of points { qi }(0 < i < n+1), where each sample point can be written as the sum : qi = pi + ei , where pi is the "true" boundary coordinate of boundary point of X and the vectors ei represent additive noise.

Thickness : radius rho(s) at a skeletal point s of the maximal ball centered on s.

Bisector angle : angle ß(s) at a "simple" skeletal point s, taken between s and the 2 boundary points p0 & p1 given by the intersection with the boundary of X of the maximal ball centered at s. The bisector angle is s.t.:

• 0 < ß(s) < pi, at regular skeletal points;
• ß(s) = 0 at end points of the skeleton;
• ß(s) = pi at extremum in thickness, such as necks.

Consider the parameter graph, where skeletal vertices are plotted according to rho(s) against ß(s). In 2D, noise shows in this graph as strata of scattered points near the origin and the axes, along hyperbolas (the strata are due to quantization which forbids certain range of values for the radius of the maximal balls - discretization effect on the distance map). Thresholds on the radius and bisector angle are given by cutting off the hyperbolically distrbuted scattered data from the parameter graph. This defines a rectangular region of interest in the upper-right side of this graph.

This local characterization of noise does not translate to a practical method in 3D. See the PhD thesis of Attali (Ch.6) or the recent paper "Computing & Simplifying 2D & 3D Continuous Skeletons" (section on "3D Skeleton Simplification").

Now with the "Ecole Nationale Supérieure d'Ingénieur Electricien de Grenoble" (ENSIEG), France.

Page created & maintained by Frederic Leymarie, 1998-2005.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu