Making 3D Binary Digital Images Well-Composed

A 3D binary digital image is said to be well-composed if and only if the set of points in the faces shared by the voxels of foreground and background points of the image is a surface in R3. Well-composed images enjoy important topological and geometric properties; in particular, there is only one type of connected component in any well-composed image, as 6-, 14-, 18-, and 26-connected components are equal. This implies that several algorithms used in computer vision, computer graphics, and image processing become simpler. For example, thinning algorithms do not suffer from the irreducible thickness problem if the image is well-composed. In this report, we introduce a new randomized algorithm for making 3D binary digital images that are not well-composed into well-composed ones, analyze its time complexity, and present experimental evidence of its effectiveness when faced with practical medical imaging data. We also introduce a new approach to extract simplicial surfaces from 3D binary images, which is based on our algorithm for making 3D binary digital images well-composed. We show that the extraction of simplicial surfaces from well-composed images using the Marching Cubes (MC) algorithm or some octree-based algorithms can be simplified, as only six out of the fourteen canonical configurations of cube-isosurface intersection can occur. Moreover, the continuous analog of the digital boundary of the input well-composed image and the MC surface are guaranteed to be topologically equivalent.