3D skeletonization algorithms

Involved people : Zouina Aktouf, Gilles Bertrand, Christophe Lohou.

A skeletonization algorithm reduces an object without changing its topology. For doing this, one removes points of the object which are simple and which satisfy certain ``geometrical'' conditions. In 3 dimensions the choice of the geometrical conditions makes it possible to reduce the object to surfaces (we obtain then a surface skeleton) or in curves (curvilinear skeleton). Contrary to the 2D case, there does not exist many good skeletonization algorithms in 3D. Some are nonvalid algorithms [ BM95 ] (they change, in certain configurations, the topology of the object), others are based on a sufficient but not necessary condition to characterize the simple points; it follows that the obtained skeleton contains useless points.

We propose several parallel 3D skeletonization algorithms which are based on the two topological numbers presented above. These two numbers make it possible to detect the simple points and to have geometrical conditions leading to a surface or curvilinear skeleton. For example, we proposed an algorithm which uses a decomposition in sub-meshs of the initial cubic mesh [ Akt97 ].

Within the framework of the orders (see the section ``Orders and digital topology''), we proposed particularly simple and effective parallel skeletonization algorithms, ensuring moreover a perfect centering of the skeleton with respect to the original object. Conditions characterizing ends of curves or surfaces boundaries make it possible to obtain curvilinear or surface skeletons (fig. 4).

Figure	Figure
(A)	(b)

Figure	Figure
(c)	(d)

Figure 4: (A): Original object, (b): surface skeleton, (c): curvilinear skeleton, (d): homotopic kernel.