The Wrapper Algorithm for Surface Extraction in Volumetric Data

Andre Gueziec and Robert Hummel

Beginning with digitized volumetric data, we wish to rapidly and efficiently extract and represent surfaces defined as isosurfaces in the interpolated data. The Marching Cubes algorithm is a standard approach to this problem. We instead perform a decomposition of each 8-cell associated with a voxel into five tetrahedra, as in the Payne- Toga algorithm. Following the ideas of Kalvin, and using essentially the same algorithm as Doi and Koide, we guarantee the resulting surface representation to be closed and oriented, and we evaluate surface curvatures and principal directions at each vertex, whenever these quantities are defined. We define a valid triangulation by representing the body as a collection of tetrahedra, some of which are only partly filled, and extracting the surface as a collection of closed triangles, where each triangle is an oriented closed curve contained within a single tetrahedron. The entire surface is "wrapped" by the collection of triangles. The representation is similar to the homology theory that uses simplices embedded in a manifold to define a surface.

From the triangles that comprise the wrapping of the surface, we can easily perform an analysis of the entire structure. We use a data structure that permits efficient access to neighboring triangles and vertices, by labeling each triangle with a unique identifier. We thus create a graph structure, which is very efficiently encoded, whose nodes are the surface elements (the triangles), and the edges are the common edges joining adjacent triangles. We can thus identify each surface using a connected component labelling algorithm applied to the graph.

This provides a highly parallelizable approach to boundary surface representation, providing an efficient and compact surface representation. The Wrapper algorithm has been used to extract surfaces of the cranium from CT-scans and cortical surfaces from MR-scans at full resolution.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.