Towards Surface Regularization via Medial Axis Transitions

ICPR 2004, Cambridge, U.K.

Frederic F. Leymarie – London University

Benjamin B. Kimia – Brown University

Peter J. Giblin – Liverpool University

Outline

Surface and object regularization – background

Medial scaffold for 3D shape representation

Transitions of the medial axis

Algorithm

Results

Future work

Surface and object regularization

Regularize shape: smooth away less important features while preserving significant ones in the vicinity.

Classical smoothing cannot distinguish between features and noise.

Recent anisotropic curvature smoothing methods are parameter sensitive, require a careful treatment of surface boundaries, and well-defined surface meshes (and normal fields) [Tasdizen02, Hildebrandt04].

Our goal: develop a hierarchical shape representation to elicit (geometric) regularization

Study the dynamics of the Medial Axis (MA) under perturbations.

Requires a representation of the MA as a graph.

Achievements

Take input as unorganized point clouds or polygonal meshes.

Can deal with objects under real scans, process partial surfaces.

Robust under different resolutions, acquisition conditions.

Do not require a closed surface mesh or voxelization, i.e., no inside/outside, skeleton can be a graph with loops (not a tree).

Do not over-simplified the extracted skeletal graph.

Regularization: based on a comprehensive analysis of the the medial structure w.r.t. topological changes under shape perturbations.

Shape representation: From the Medial Axis
to the Medial Scaffold

Blum (1960's & 70's):

Propagation vs.

Contact with disks

2000+:

Shock singularities

Contact typology

(Kimia, Giblin, et al.)

Shape representation: From the Medial Axis
to the Medial Scaffold

3D: Five types of points from contact theory [Giblin-Kimia PAMI04]:

Sheet: A12

Links: A13 (Axial), A3 (Rib)

Nodes: A14 (Voronoi vertices) , A1A3

Akn: contact at n distinct points,

each with k+1 degree of contact

Leymarie-

Kima '01:

Keep only

singular

points of

the flow

(radius) to

build a

graph.

Computing the Medial Scaffold

Leymarie-Kimia CVPR03:

Visibility constraints

together with clustering

leads to efficiency in

computing the graph

(linear in practice in the number of input generators)

Transitions of the MA

Study the topological events of the graph structure of the MA under perturbations and shape deformations.

Singularity theory (Arnold, Bogaevsky, since the 1990's):

In 3D, 26 topologically different perestroikas of linear shock waves.

“Perestroikas of shocks and singularities of minimum functions,”

I. Bogaevsky, 2002.

Transitions of the Medial Axis (MA)

Study the topological events of the graph structure of the MA under perturbations and shape deformations.

Transitions of the MA (Giblin & Kimia, ECCV 2002):

Under a 1-parameter family of deformations, only seven transitions are relevant.

A1A3-II

A15

A14

A5

(compression-like)

(compression-like)

(pulling apart-like)

(ridge merging-like)

Transitions of the Medial Axis (MA)

Study the topological events of the graph structure of the MA under perturbations and shape deformations.

(protrusion-like)

A1A3-I

A12A3-I

(protrusion on axial curve)

A12A3-II

(protrusion moving

thru an axial curve)

Scaffold Regularization

Transition removal, i.e., remove topological instability

Smoothing

Green: A1A3 nodes, Pink: A14 nodes

Blue: A3 links, Red: A13 links

A1A3-I

A5

A15

A12A3-I

2D Scaffold Regularization

Transition removal, i.e., remove topological instability

2D Boundary Smoothing ordered by “scale” (Tek & Kimia JMIV 2001).

Iterative removal of MA branches, ordered by boundary support (i.e., how much of the contour is represented), coupled with local boundary model adjustment, results in corner enhancement and small perturbations' smoothing.

3D Scaffold Regularization

Transition removal, i.e., remove topological instability

3D Boundary Smoothing ordered by “scale.”

Only (3) transitions pertaining to “protrusions” are considered here.

(1) Detect Axial-Rib loops in the medial scaffold.

(2) Support on the boundary is approximated as the volume subtented by V-shaped hinges which define a cap-like region in between the axial and rib curves delimiting a potential transition.

3D Scaffold Regularization

(1) Compute full Scaffold from unorganized point clouds.

(2) Symmetries pertaining to the interaction of nearby samples are used to mesh the data into surface patches (S) [Leymarie & Kimia, DIMACS 2003].

(3) Remaining graph structure is the Medial Scaffold (MS).

(4) Detect Axial-Rib loops in MS.

(5) “Walk” along axial curves for each loop identifies contact curves on S: protrusions limits.

(6) Build smooth cut-off patches.

(7) Rank order loop structures.

(8) Perform transition removal.

3D Scaffold Regularization

Sherd data: 50K

from laser scans

Significant ridges

useful for pot matching and reconstruction

(a 3D puzzle) in digital archaeology applications.

SHAPE Lab. : www.lems.brown.edu/shape/

3D Scaffold Regularization

Knot data: 10K random samples

Towards generalized cylinders

Towards 3D Object Recognition

David data: 20K and 30K reduced sample sets (ground truth = 50K)

Graph matching via graduated assignement

(to be presented at 3DPVT, Greece, Sept. 2004, Chang, Leymarie & Kimia)

a solution to the Global Registration problem.

Validation against ground truth: (object dimension = 69x69x76)

average sq. dist. = 0.000005

Conclusions - Limitations

Perturbations smaller than contact sphere radius are not “visible” from the graph structure alone.

Complementary to recent anisotropic smoothing methods (explicit ridges).

Four remaining transitions not yet used for surface regularization.

Data from Cyberware Inc.

Study curvatures of the MA

[Damon, Giblin & Kimia, Siersma].

Study the topography of the MA, e.g., hills & dales [Nackman & Pizer, 1980's]

Conclusions - Features

Hierarchical representation is built-in.

Scale represented: to distinguish large features from small ones and rank accordingly.

Reconstruction of the shape from its skeleton is always possible (exact to approx.).

Robustness: Structural information from the scaffold is more reliable than surface samples.

Generalized axes of elongated objects, and ridges are explicit represented.

Shape deformations are now handled.

Data from Cyberware Inc.

WESKATMA
What Everybody Should Know About The Medial Axis

A natural graph structure for the MA exists and leads to efficiency in computation, visualization, applications: the Medial Scaffold hierarchy in 3D.

The MA is typically NOT overly sensitive to small (scale) perturbations; it does respond to sharpness.

Shape deformations and perturbations are encoded as topological events, the transitions of shock waves.

The MA needs not be traced explicitly: the focus should be on the (isolated) singularities of the radius flow.

2004-08-10T08:57:01