Volume 8 Issue 10 - May 22, 2009
Skeleton Extraction by Mesh Contraction
Tong-Yee Lee

Font Normal   Font Enlarge
Project Web Site: http://graphics.csie.ncku.edu.tw/Skeleton/

Curve-skeleton is a very useful 1D structure to abstract the geometry and topology of a 3D object. Extraction of curve-skeletons is a fundamental problem in computer graphics, visualization, image processing and computer vision. There many useful applications including virtual colonoscopies, collision detection, computer animation, surface reconstruction and shape matching etc. In the literature [1][2], most previous methods require a volumetric discrete representation of the input model. However, transforming them into volumetric representations may raise discretization error in both geometry and connectivity.

In this work [3], we propose a novel technique to extract skeletons directly from the mesh domain without requirement of volumetric discretization. Our approach (Figure 1) consists of three main steps: 1) mesh contraction, 2) connectivity surgery and 3) centeredness refinement. First, we contract a given mesh into a zero-volume skeletal shape by applying an iterative Laplacian smoothing procedure [4] with global positional constraints. Second, we execute a connectivity surgery procedure to progressively convert the contracted mesh into a 1D curve skeleton. Finally, to ensure its centeredness within the mesh, we refine the skeleton by moving each skeletal node to the center of its corresponding mesh region.
Figure 1. Left to right are the original raptor mesh and contraction results after 1, 2 and 3 iterations. The rightmost image shows the final skeleton after performing connectivity surgery and centeredness refinement [3].

In contrast to previous work, our approach has the following advantages: 1) our extracted skeleton is ensured to be homotopic to the original object, 2) it is inherently robust against noise disturbance (see Figure 2) and avoids volumetric discretization errors, and 3) the method is very fast and it is rotation invariant, and pose insensitive (Figure 3).
Figure 2. A good quality extracted skeleton from a highly noisy raptor model [3].

Figure 3. Our extracted skeleton is both pose-invariant and sampling-insensitive [3].

Figure 4 shows some curve skeletons extracted using our method. All these skeletons represent well the geometry and topology of the original shapes with different genus. More results can be found in our project web page: http://graphics.csie.ncku.edu.tw/Skeleton/ . In addition, we include video demonstration and execution code with example models in this web site. The processing time of our skeleton extraction approach is dominated by the geometry contraction process. To speed up it, we implement a multigrid solver to compute the new contracted vertex positions. As a result, our approach is very computationally efficient in comparison with other previous work. It takes 2 to 240 seconds to extract the skeletons of models with 4K to 250K vertices.
Figure 4. Our method extracts good quality curve-skeletons for complex models [3].

We present a novel approach for extracting curve-skeletons directly from mesh surfaces. In near future, we would also like to extend our framework to process more general meshes or other surface representations, including non-manifold meshes, surfaces with boundaries, and point set data. In addition, we will explore its use in some interesting applications, such as interactive mesh editing and volumetric signal processing.

[1] CORNEA, N. D., MIN, P., AND SILVER, D. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Transactions on Visualization and Computer Graphics 13, 3, 530–548.
[2] WANG, Y.-S., AND LEE, T.-Y. 2008. Curve skeleton extraction using iterative least squares optimization. IEEE Transactions on Visualization and Computer Graphics 14, 4 . 926-936.
[3] Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, and Tong-Yee Lee, “Skeleton Extraction by Mesh Contraction,” ACM Transactions on Graphics (SIGGRAPH 2008 issue), Vol. 27, No. 3, August 2008, pp. 44:1-44:10.
[4] SORKINE, O., AND COHEN-OR, D. 2004. Least-squares meshes. In Proceedings of Shape Modeling International, 191–199.
< Previous
Next >
Copyright National Cheng Kung University