Recognition and separation of discrete objects within complex 3D voxelized structures


3D voxelized images can be manipulated if their component parts can be identified, cataloged, and measured. To accomplish this, it is necessary to separate individual convex objects from the complex structures that result from digital observation techniques such as X-ray tomography. Toward this end, we have developed schemes that peel away sequential layers of voxels from complex structures until narrow waists that connect individual objects disappear, and each component object can be identified. These peeling schemes provide the most uniform possible cumulative thickness of removed layers regardless of the orientation of the voxel grid pattern. Consequently, they lead to the most accurate application regarding inter-object interfaces, medial axis analysis, and individual object statistics such as volumes, orientations and interconnectivity. Peeling schemes can be categorized by the number of steps involved in each peeling iteration. Each step removes voxels according to three possible criteria for defining the exterior of a voxel: exposed faces, edges, or corners. Each of these ultimately causes an initial sphere, for example, to evolve into a cube, dodecahedron, or octahedron, respectively. Combinations of steps can be used to create more complex polyhedra (tetrahexadra, trisoctahedra, trapezohedra, and hexoctahedra). The resulting polyhedron that most closely resembles a starting sphere depends on the appropriate definition of “sphericity”. Using a metric based on the standard deviation of the polyhedral surface from that of a concentric sphere of equal volume, the optimal scheme is peeling by faces 7 times, by edges 3 times, and by corners 4 times. This leads to a hexoctahedron with Miller indices (14 7 4) and a standard deviation of 0.025. Using a metric based on minimizing surface area, the optimal scheme is peeling by faces 9 times, by edges 6 times, and by corners 5 times, leading to a hexoctahedron with Miller indices (20 11 5). In the past, only 1-step peeling has been used (by faces or corners). If computational or conceptual constraints limit peeling to 1-step, the criterion of edges should be used, as the dodecahedron that results deviates from a sphere by only half the amount of either the cube or octahedron resulting from 1-step peeling of faces or corners, respectively. We also determined the best criteria for 2-step and 3-step peeling. The peeling schemes we identify can be used to separate objects from complex structures for application to a number of geological and other problems. Information that emerges from the analysis includes object volumes, which can be used for determining grain- or bubble-size distributions in volcanologic, petrologic, and sedimentary applications, among others.


Earth Systems Research Center

Publication Date


Journal Title

Computers & Geosciences



Digital Object Identifier (DOI)

Document Type



© 2001 Elsevier Science Ltd. All rights reserved.