Last update: July 27, 2005

BACK

Publications by Benjamin Kimia et al. :

• A Similarity-Based Aspect-Graph Approach to 3D Object Recognition, 2004.
• A Formal Classification of 3D Medial Axis Points and Their Local Geometry, 2004.
• On the Local Form and Transitions of Symmetry Sets, Medial Axes, and Shocks, 2003.
• Euler Spiral for Shape Completion, 2003.
• Transitions of the 3D Medial Axis Under a One-Parameter Family of Deformations, 2002.
• Shock-based Indexing into Large Shape Databases, 2002.
• Metric-based Shape Retrieval in Large Databases, 2002.
• On Solving 2D and 3D Puzzles under Curve Matching, 2001.
• The Shock Scaffold for Representing 3D Shape, 2001.
• Alignment-based Recognition of Shape Outlines, 2001.
• Boundary Smoothing via Symmetry Transforms, 2001.
• Shape matching using edit-distance: An implementation, 2001.
• Symmetry maps of free-form curve segments via wave propagation, 1999 & 2003.
• Exact recovery of bisectors as shocks, 2000+.
• Symmetry maps and symmetry transforms, 2000+.
• Discrete 3D Wave Propagation for Computing Morphological Operations from Surface Patches and Unorganized Points, 2000.
• On the Local Form of Symmetry Sets, and Medial Axes, and Shocks in 3D, 2000.
• On the Local Form and Transitions of Symmetry Sets, and Medial Axes, and Shocks in 2D, 1999.
• On the Intrinsic Reconstruction of Shape from its Symmetries, 1999.
• Perceptual organization via symmetry map and symmetry transforms, 1999.
• Segmentation of carpal bones from 3D CT images using skeletally coupled deformable models, 1998, 2003.
• Symmetry-based indexing of image databases, 1998.
• Curve Evolution, Wave Propagation, and Mathematical Morphology, 1998.
• Volumetric Segmentation of Medical Images By Three-Dimensional Bubbles, 1997.
• Shocks From Images: Propagation of Orientation Elements, 1997.
• Image Segmentation by Reaction-Diffusion Bubbles, 1995.
• Geometry Shock-Capturing ENO Schemes for Subpixel Interpolation, Computation & Curve Evolution, 1995.
• Geometric Heat Equation & Nonlinear Diffusion of Shapes & Images, 1994.
• Three Dimensional Shape Representation from Curvature Dependent Surface Evolution, 1994.
• Analytic Inverse of Discrete Gaussian Blur, 1993.
• Mathematical Morphology: The Hamilton-Jacobi Connection, 1992.
• Parts of Visual Form: Computational Aspects, 1992.
• Parts of Visual Form: Ecological & Psychological Aspects, 1992.
• Shapes, Shocks and Deformations I: The Components of Shape & the Reaction-Diffusion Space, 1992.
• Toward a Computational Theory of Shape, 1991 (PhD).
• On the Evolution of Curves via a Function of Curvature, I: The Classical Case, 1990 & 1992.
• Toward a Computational Theory of Shape: An Overview, 1989 & 1990.
• Deblurring Gaussian Blur, Continuous and Discrete Approaches, 1986 (M.Eng.)
• Deblurring Gaussian blur, 1984.

BibTeX references

This paper describes a view-based method for recognizing 3D objects from 2D images. We employ an aspect-graph structure, where the aspects are not based on the singularities of visual mapping but are instead formed using a notion of similarity between views. Specifically, the viewing sphere is endowed with a metric of dis-similarity for each pair of views and the problem of aspect generation is viewed as a "segmentation" of the viewing sphere into homogeneous regions. The viewing sphere is sampled at regular (5 degree) intervals and an iterative procedure is used to combine views using the metric into aspects with a prototype representing each aspect, in a "region-growing" regime which stands in contrast to the usual "edge detection" styles to computing the aspect graph. The aspect growth is constrained such that two aspects of an object remain distinct under the given similarity metric. Once the database of 3D objects is organized as a set of aspects and prototypes for these aspects for each object, unknown views of database objects are compared with the prototypes and the results are ordered by similarity. We use two similarity metrics for shape, one based on curve matching and the other based on matching shock graphs, which for a database of 64 objects and unknown views of objects for the database give (90.3%, 74.2%, 59.7%) and (95.2%, 69.0%, 57.5%), respectively, for the top three matches; identification based on the top three matches is 98% and 100%, respectively. The result of indexing unknown views of objects not in the database also produce intuitive matches. We also develop a hierarchical indexing scheme the goal of which is to prune unlikely objects at an early stage to improve the efficiency of indexing, resulting in savings of 35% at the top level and of 55% at the next level, cumulatively.

Keywords: 3D object recognition, aspect-graph, view-based recognition, shape similarity, characteristic views.

In this paper we address the curve completion problem, e.g., the geometric continuation of boundaries of objects which are temporarily interrupted by occlusion. Also known as the gap completion or shape completion problem, this problem is a significant element of perceptual grouping of edge elements and has been approached by using cubic splines or biarcs which minimize total curvature squared (elastica), as motivated by a physical analogy. Our approach is motivated by railroad design methods of the early 1900's which connect two rail segments by "transition curves", and by the work of Knuth on mathematical typography. We propose that in using an energy minimizing solution completion curves should not penalize curvature as in elastica but curvature variation. The minimization of total curvature variation leads to an Euler Spiral solution, a curve whose curvature varies linearly with arclength. We reduce the construction of this curve from a pair of points and tangents at these points to solving a nonlinear system of equations involving Fresnel Integrals, whose solution relies on optimization from a suitable initial condition constrained to satisfy given boundary conditions. Since the choice of an appropriate initial curve is critical in this optimization, we analytically derive an optimal solution in the class of biarc curves, which is then used as the initial curve. The resulting interpolations yield intuitive interpolation across gaps and occlusions, and are extensible, in contrast to the scale-invariant version of elastica. In addition, Euler Spiral segments can be used in other applications of curve completions, e.g., modeling boundary segments between curvature extrema or modeling skeletal branch geometry.

This paper proposes a smoothing technique for shape based on a perturbation analysis of the underlying medial axis, and by iteratively removing skeletal branches. While medial axis regularization usually aims at dealing with its sensitivity in the context of applications such as recognition, we use it here to smooth shape. The approach overcomes a basic drawback with current smoothing techniques, namely, the rounding of perceptually salient corners. The key idea is that the instability of the skeleton under a family of deformations can be dealt with via a symmetry transform which is applied to all related symmetry branches so as to effect an appropriate change in the shape. This leads to the notion of a splice transform which removes a branch coupled with simultaneous changes in the skeleton. In contrast to point-based pruning techniques which use local salience and which cannot construct coarse-scale corners, our approach constructs and preserves coarse-scale curvature extrema, leading to a "scale-discrete scale-space" for shape. The approach is also applicable to the smoothing of incomplete shapes represented as a set of curve segments.

Keywords: Smoothing, medial axis, symmetry set, pruning medial axis, coarse-scale corners.

Web link.

This paper presents an approach for computing the symmetries (skeletons) of an edge map consisting of a collection of curve segments. This approach is a combination of analytic computations in the style of computational geometry and discrete propagations on a grid in the style of the numerical solutions of PDE's. Specifically, waves from each of the initial curve segments are initialized and propagated as a discrete wavefront along discrete directions. In addition, to avoid error built up due to the discrete nature of propagation, shockwaves are detected and explicitly propagated along a secondary dynamic grid. The propagation of shockwaves, integrated with the propagation of the wavefront along discrete directions, leads to an exact simulation of propagation by the Eikonal equation. The resulting symmetries are simply the collection of shockwaves formed in this process which can be manipulated locally, exactly, and efficiently under local changes in an edge map (gap completion, removal of spurious elements, etc). The ability to express grouping operations in the language of symmetry maps makes it an appropriate intermediate representation between low-level edge maps and high level object hypotheses.

Keywords: shape, medial axis, symmetry set, shock detection, perceptual organization.

Segmentation of Carpal Bones from 3D CT Images using Skeletally Coupled Deformable Models

Abstract

The in vivo investigation of joint kinematics in normal and injured wrist requires the segmentation of carpal bones from 3D (CT) images, and their registration over time. The non-uniformity of bone tissue, ranging from dense cortical bone to textured spongy bone, the irregular shape of closely packed carpal bones, small inter-bone spaces compared to the resolution of CT images, along with the presence of blood vessels, and the inherent blurring of CT imaging render the segmentation of carpal bones a challenging task. We review the performance of statistical classification, deformable models (active contours), region growing, region competition, and morphological operations for this application. We then propose a model which combines several of these approaches in a unified framework. Specifically, our approach is to use a curve evolution implementation of region growing from initialized seeds, where growth is modulated by a skeletally-mediated competition between neighboring regions. The inter-seed skeleton, which we interpret as the predicted boundary of collision between two regions, is used to couple the growth of seeds and to mediate long-range competition between them. The implementation requires subpixel representations of each growing region as well as the inter-region skeleton. This method combines the advantages of active contour models, region growing, and both local and global region competition methods. We demonstrate the effectiveness of this approach for our application where many of the difficulties presented above are overcome as illustrated by synthetic and real examples. Since this segmentation method does not rely on domain-specific knowledge, it should be applicable to a range of other medical imaging segmentation tasks.

BACK

Page created & maintained by Frederic F. Leymarie, 2000-5
Comments, suggestions, etc., mail to:  ffl  at  gold dot ac dot uk