Last update: Jan.19, 1999

Publications by Chris Pudney * et al. on shape symmetry elicitation :

• 3D Voronoi Skeletons: Computation, Topological Simplification & Application, 1999+.
• Distance-Ordered Homotopic Thinning: A Skeletonization Algorithm for 3D Digital Images, 1998.
• Feature detection in volumetric images via local energy & ordered thinning, 1998.
• Distance-Based Skeletonization of 3D Images, 1996.

BibTeX references.

The 3D Voronoi skeleton of an object can be computed from a set of sample points from the object's boundary. The skeleton is obtained from the dual of the Delaunay tetrahedralization of the sample point, i.e., a subgraph of the Voronoi tessellation of the points. As with most skeletons, simplification is required to prune spurious branches induced by boundary noise.

We present a novel simplification method that can alter the skeleton's topology. This is in contrast to most existing simplification techniques that preserve topology. We change the topology by removing skeleton vertices that correspond to singularities - which typically result from poor sampling of the object's boundary, and can produce loops in the skeleton.

In addition, we present a homotopy criterion, to preserve topology elsewhere in the skeleton, and 2 significance criteria, to preserve perceptually relevant portions of the skeleton.

The (simplified) skeleton was used to reconstruct multi-scale representation of an object, and used to measure the topological length of a 3D object. Results are presented for a variety of synthetic and real objects from 3D confocal microscopy.

Significance criteria

1. Lost volume: small preturbations of the surface generate branches whose associated volume (of the dual Delaunay simplices) is relatively small.
   
2. Noise model: Based on thickness (radius of maximal ball) & bisector angle. Noise vertices are characterized by a small bisector angle or a small radius. The parameter graph is useful to identify noisy Voronoi vertices.

A set of simplification thresholds (pairs of bisector and radius values) generates multiple scales (reconstructed object).

A technique called Distance-Ordered Homotopic Thinning (DOHT) for skeletonizing 3D binary images is presented. DOHT produces skeletons that are homotopic, thin, and medial. This is achieved by sequentially deleting points in ascending distance order until no more can be safely deleted. A point can be safely deleted only if doing so preserves topology. Distance information is provided by the chamfer distance transform, an integer approximation to the Euclidean distance transform.

2 variations of DOHT are presented that arise from using different rules for preserving points:

1. The first uses explicit rules for preserving the ends of medial axes or edges of medial surfaces.
2. The second preserves the centers of maximal balls identified from the chamfer distance transform.

By thresholding the centers according to their distance values, the user can control the scale of features represented in the skeleton. Results are presented for real and synthetic 2D and 3D data.

The ability to detect features within volumetric images is important for the interpretation and analysis of such data. Most detectors are gradient based, and so can fail to accurately locate some important feature types and can be sensitive to noise. The local energy feature detector developed by Morrone and Owens marks locations where there is maximal congruence of phase in the Fourier components of an image. Points of maximal phase congruency occur at all common feature types. A 3D implementation of the local energy feature detector, suitable for volumetric data is presented. The detector computes local energy by convolving an image with oriented quadrature pairs of 3D masks. Peaks in local energy coincide with points of maximal phase congruency. To locate these peaks, the local energy result is homotopically thinned starting from the lowest energy value and proceeding to the highest. Results are presented for several CT image volumes.

Starts from a 3D binary (segmented) image and sequentially delete, in an ordered fashion, exterior points, that is, foreground points n-adjacent to background points. Foreground points are m-adjacent to each other. The connectivity relation is one of the pair: {(m,n) = (6,26), (26,6), (6,18), (18,6)}. The algorithm traces the "ridges" of maximal distance during thinning. The Distance Transform (DT) is a by-product.

Algorithm:

• Initial loop queues all exterior points
• Deletability is considered

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