Voronoi-Based Extraction of a Feature Skeleton from Noisy Triangulated Surfaces

Recent advances in 3D reconstruction allow to quickly acquire highly detailed and complex geometry. However, the outcome of such systems is usually unstructured, noisy and redundant. In order to enable further processing such as CAD modeling, physical measurement or rendering, semantic information about shape and topology needs to be derived from the data. In this paper, a robust approach to the extraction of a feature skeleton is presented. The skeleton reflects the overall structure of an object. It is given by a set of lines that run along ridges or valleys and meet at umbilical points. The computed data is not just useful for building semantic-driven CAD models in reverse engineering disciplines but also to identify geometrical features for tasks like object recognition, registration, rendering or re-meshing. Based on the mean curvature, a Markov random field is used to robustly classify each vertex either belonging to convex, concave or flat regions. The boundaries of the regions are described by a set of points that are robustly estimated using linear interpolation. A novel algorithm is used to extract the feature skeleton based on the Voronoi decomposition of the boundary points. The method has been successfully tested on real world examples and the paper concludes with a detailed evaluation.