Medial Axis Reconstruction

Thiago Pereira e Renato Paes Leme

{tpereira, paesleme}@impa.br

Introduction

The Medial Axis of a shape is composed by the points whose distance to the shape is realized by more than one point in the shape (Figure on the right from [2]). There are known methods to calculate the medial axis of polygons, polynomial curves and some other special shapes [2]. One very important problem in the Field of 3D Reconstruction is to estimate the medial axis of a shape represented by a point cloud. It is known that the medial axis is a subset of the Voronoi diagram. A classic approach is to calculate the diagram and to filter the Voronoi facets [1]. This approach is not robust in face of noise and outliers. In this work, we counter this problems by calculating the medial axis through random sampling of the point cloud.

Overview

The general idea is the following: Voronoi sites are centers of empty circles. We relax this restriction and search for "almost empty" circles that "could be" Voronoi. To do this, we start by random sampling triples of points and filtering them using criteria inspired by [1]. We claim that the centers of these circles approximate the medial axis.

Pre-processing : We start by creating a data structure that allows k-nearest neighbour queries. We use a Delaunay Triangulation. After that, we estimate the normal in each point using Monge Jet Fitting on a Local Neighbourhood. This normals are going to be used to filter the sampled circles.

Filtering : A circle is defined by three points. Before considering this circles in our algorithm, we will check some criteria. A circle that fulfills that will be called a "valid circle". In order for the sampled circles to approximate Delaunay circles, we propose the following filtering criteria: (i) not too big circles ( to avoid centers outside the object ); (ii) at least two normals of the circle should be aligned with the estimated normals of the shape; (iii) the circles should be "almost empty" ( the inner point shouldn't exceed a certain threshold )

Advancing Front Version : We experimented with calculating the Medial Axis in a multiscale fashion. Our objective is to first identify larger features ( represented by circles with large radius ) and then proceed to analyse the details ( smaller circles ). We start by random sampling some valid circles. We insert these circles in a priority queue. The algorithm proceeds by extracting the circle with largest radius, inserting its center in the medial axis and searching nearby circles. We do this by random sampling points in the local neighbourhood of the circle and checking the filtering criteria. We check if this point is too close to a point already found in the Medial Axis and discard it if it is.


On the left, an illustration of the filtering criteria and on the right, some points found by
the algorithm and connected by an Euclidian Minimal Spanning Tree.
[ view larger images ]

Results

     
The colored points approximate the medial axis. On the left, we draw the circles associated with each point. [ view larger images ]

Future work

Some interesting problems for future work are:

Bibliography

[1] Dey, T. K. and Zhao, W. 2002. Approximate medial axis as a voronoi subcomplex. In Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications (Saarbr├╝cken, Germany, June 17 - 21, 2002). SMA '02. ACM, New York, NY, 356-366.

[2] Dominique Attali, Jean-Daniel Boissonnat, Herbert Edelsbrunner, Stability and Computation of Medial Axes: a State of the Art Report. Chapter of Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration 2007 Springer-Verlag

[3] Teixeira, R. C. 1998 Curvature Motions, Medial Axes and Distance Transforms. Doctoral Thesis. UMI Order Number: AAI9832510., Harvard University.

[4] N. Amenta, S. Choi and R. Kolluri. The power crust, unions of balls and the medial axis transform, Int. J. Computational Geometry and its Applications, 2000