Last update: August 11, 2004.

BACK

Publications by

on Shape Symmetry elicitation :

• 3D Shape Registration using Regularized Medial Scaffolds, 2004.
• Towards Surface Regularization via Medial Axis Transitions, 2004.
• Computation of the Shock Scaffold for Unorganized Point Clouds in 3D, 2003.
• Three-Dimensional Shape Representation via Shock Flows, 2003.
• The Shock Scaffold for Representing 3D Shape, 2001.
• Discrete 3D Wave Propagation for Computing Morphological Operations from Surface Patches and Unorganized Points, 2000.
• Interpenetrating Waves and Multiple Generation Shocks via the CEDT, 1997.
• Simulating the Grassfire Transform Using an Active Contour Model, 1992.

BibTeX references.

This paper proposes a novel method for global registration based on matching 3D medial structures of unorganized point clouds or triangulated meshes. Most practical known methods are based on the Iterative Closest Point (ICP) algorithm, which requires an initial alignment close to the globally optimal solution to ensure convergence to a valid solution. Furthermore, it can also fail when there are points in one dataset with no corresponding matches in the other dataset. The proposed method automatically finds an initial alignment close to the global optimal by using the medial structure of the datasets. For this purpose, we first compute the medial scaffold of a 3D dataset: a 3D graph made of special shock curves linking special shock nodes. This medial scaffold is then regularized exploiting the known transitions of the 3D medial axis under deformation or perturbation of the input data. The resulting simplified medial scaffolds are then registered using a modified graduated assignment graph matching algorithm. The proposed method shows robustness to noise, shape deformations, and varying surface sampling densities.

Downloads:

• Paper in PDF

The reconstruction of objects from data in practical applications often leads to surfaces with small perturbations and other artifacts which make the detection of their ridges and generalized axes difficult. We propose an approach to smoothing small structures while preserving ridges which is based on the medial axis structure of the surface. The medial axis of the surface is organized as a graph structure and the closeness of the medial axis graph to points of instability (transitions) is used to identify those structures which are most likely due to perturbations. The removal of these structures is our approach to regularizing both the medial axis and the surface. This paper focuses on a subset of medial transitions arising from protrusions and the method is illustrated for a few synthetic and real images.

Downloads :

• Paper in PDF
• Presentation in PowerPoint
• Presentation in PDF
• Presentation in OpenOffice

The shock scaffold is a hierarchical organization of the medial axis in 3D consisting of special medial points and curves connecting these points, thereby forming a geometric directed graph, which is key in applications such as object recognition. In this paper we describe a method for computing the shock scaffold of realistic datasets, which involve tens or hundreds of thousands of points, in a practical time-frame. Our approach is based on propagation along the scaffold from initial sources of flow by considering pairs of input points. We present seven principles which avoid the consideration of those pairs of points which cannot possibly lead to a shock flow; they involve: (i) the "visibility" of a point from another, (ii) the clustering of points, (iii) the visibility of a cluster from another, (iv) the convex hull of a cluster, (v) the vertices of such convex hulls as "virtual" points, (vi) a multi-resolution framework, and, finally, (vii) a search strategy organized in layers.

Web link.

URL @ CiteSeer : http://citeseer.nj.nec.com/leymarie03threedimensional.html

We address the problem of representing 3D shapes when partial and unorganized data is obtained as an input, such as clouds of point samples on the surface of a face, statue, solid, etc., of regular or arbitrary complexity (free-form), as is commonly produced by photogrammetry, laser scanners, computerized tomography, and so on. Our starting point is the medial axis (MA) representation which has been explored mainly for 2D problems since the 1960's in pattern recognition and image analysis. The MA makes explicit certain symmetries of an object, corresponding to the shocks of waves initiated at the input samples, but is itself difficult to directly use for recognition tasks and applications. Based on previous work on the 2D problem, we propose a new representation in 3D which is derived from the MA, producing a graph we call the shock scaffold. The nodes of this graph are defined to be certain singularities of the shock flow along the MA. This graph can represent exactly the MA --- and the original inputs --- or approximate it, leading to a hierarchical description of shapes.

We develop accurate and efficient algorithms to compute for 3D unorganized clouds of points the shock scaffold, and thus the MA, as well as its close cousin the Voronoi diagram. One computational method relies on clustering and visibility constraints, while the other simulates wavefront propagation on a 3D grid. We then propose a method of splitting the shock scaffold in two sub-graphs, one of which is related to the (a priori unknown) surface of the object under scrutiny. This allows us to simplify the shock scaffold making more explicit coarse scale object symmetries, while at the same time providing an original method for the surface interpolation of complex datasets. In the last part of this thesis, we address extensions of the shock scaffold by studying the case where the inputs are given as collections of unorganized polygons.

Web link

The usefulness of the 3D Medial Axis (MA) is dependent on both the availability of accurate and stable methods for computing individual MA points and on schemes for deriving the local structure and connectivity among these points. We propose a framework which achieves both by combining the advantages of exact bisector computations used in computational geometry, on the one hand, and the local nature of propagation-based algorithms, on the other, but without the computational complexity, connectivity, added dimensionality, and post processing issues commonly found in these approaches. Specifically, the notion of flow of shocks along the MA manifold is used to identify flow along special points and curves which define a shock scaffold. This 1D scaffold is of lower dimensional complexity than the typical geometric locus of medial points which are represented as 2D sheets. The scaffold not only organizes shape information in a hierarchical manner, but is a tool for the efficient recovery of the scaffold itself and can lead to exact reconstruction. We present examples of this approach for synthetic data, as well as for sherd data from the domain of digital archaeology.

Keywords: 3D Medial Axis, 3D Skeletons, 3D Symmetry Sets, shock hypergraph, shape representation.

Web link.

We present a discrete framework for 3D wave propagation to support morphological computations with an emphasis on the recovery of the medial axis of a 3D solid, a collection of surface patches, or a data set of unorganized points. The wave propagation is implemented on a discrete lattice, where initial surfaces are considered as sources of propagation. Three classes of discrete rays are designed to cover the propagation space with a minimal number of computations. These pencils of rays represent a ``compromise'' view between Huygens and Fermat principles. The 3D medial axis points are then found at the collision of wavefronts. This method has linear time complexity in the number of nodes of the lattice used to discretize the propagation medium, i.e., it is independent of the topological complexity of the initial data. As such, it is highly efficient for the extraction of symmetries, as well as for implementing 3D morphological filters based on erosions and dilations, from large 3D data sets. The wave propagation scheme permits to implement the effect of various metrics including the Euclidean one.

Keywords: 3D morphology, skeletons, Euclidean Distance Transform, wave propagation, Eikonal, unorganized datasets, cellular automata.

Download PS version of paper here.

The extraction of symmetries as quench points of propagating orientation from edge maps of grey scale images is faced with fundamental theoretical and computational problems. Theoretical difficulties arise because low-level processes do not yield perfect information and symmetries are drastically altered with small changes such as:

1. missing edges (gaps)
2. occlusion and parts,
3. spurious edges. alter the underlying symmetry set.

While the full symmetry set retains much of the original figure's symmetries it does so at the expense of bringing to bear many unintuitive branches, thus requiring further selection for object recognition.

In this paper, we view the full symmetry set as the superposition of shocks arising from multiple generations of waves: the quenching points of the waves from the initial edge map constitute the first generation of shocks. A second generation of waves initiated at these points, simulate interpenetrating wave and generate a second generation of shocks, and so on until no further shocks can be formed. This view of the full symmetry set supports a selective continuation of waves, e.g., at shock loops to remove spurious edges, and at shock-hypothesized limbs to partition shape and close boundary gaps. This selective continuation of waves brings out relevant symmetries, but avoids the ambiguity of the full symmetry set.

The second point of the paper is to propose the use of a computational framework based on the Contour-based Euclidean Distance Transform (CEDT) for shock detection, classification, labeling, as well as for simulating interpenetrating waves and multiple generation shocks described above. The key feature of CEDT that makes this possible is the explicit simultaneous propagation of orientation and distance, as well as additional features, e.g. shock labels,which are necessary to deal with the theoretical issues raised above. In addition, CEDT is exact and of very low numerical complexity. The results for a number of illustrative examples indicate the suitability of this framework for the recovery of object symmetries from real imagery.

In this paper we present a new method for shape description of planar objects which integrates both region and boundary features. Our method is an implementation of a 2-D dynamic grassfire that relies on a distance surface on which elastic contours minimize an energy function. A Euclidean distance transform combined with an active contour model, such as the snake, is used for this minimization process. Boundary information is integrated into the model by the extraction of curvature extrema and arcs of constant curvature. The use of an active contour on a field of grass, represented as a distance surface, combined with curvature features of the boundary permits us to extract a Euclidean skeleton representation of the shape while bypassing many of the discretization problems found in other skeletonization algorithms. We propose a new concept for skeletal branch significance based on the notion of the local deformation introduced by symmetry points on the distance surface. We call this the ridge support. Furthermore, we show how the ridge support can be evaluated in terms of the velocity of formation of a symmetric axis or in terms of the slope amplitude of a tangent to the symmetric axis. We propose a new concept, the deformable skeleton, which is useful for tracking deformable shapes. We refer to this as the dynamic skeleton.

Index terms:

• 2-D grassfire simulation, active contour model, distance surface, Euclidean skeleton, contour and region shape features, multiscale representation, ridge support, deformable skeleton.

BACK

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