Minimal nonsimple sets of voxels in binary images on a face-centered cubicgrid

One can prove that a specified parallel thinning algorithm always preserves the topology of the input binary image by verifying that no iteration of t hat algorithm can ever delete a minimal non-simple ("LMNS") set of 1's of a n image. For binary images on a 3D face-centered cubic ("FCC") grid, we det ermine which sets of voxels can be MNS, and also determine which of those s ets can be MNS without being a component of the 1's. These two problems are complicated by the fact that there are (at least) three reasonable ways of defining connectedness for sets of 1's and 0's in a binary image on an FCC grid, since one can: (a) use 18-connectedness for sets of 1's and 12-conne ctedness for sets of 0's; (b) use 12-connectedness both for sets of 1's and for sets of 0's; (c) use 12-connectedness for sets of 1's and 18-connected ness for sets of 0's. We solve the two problems in all three cases. The analogous problems for binary images on Cartesian grids were first solv ed by Ronse (in the 2D case) and Ma (in the 3D case). However, our treatmen t of simple 1's and MNS sets is rather different from theirs, in that it is based on the attachment sets of 1's in binary images. This concept was int roduced in an earlier paper [T. Y. Kong, "On topology preservation in 2-D a nd 3-D thinning," Int. J. Pattern Recognition and Artificial Intelligence 9 (1995) 813-844] and we use the same general approach to MNS sets as was us ed there. The voxels of an FCC grid are rhombic dodecahedra, which are rather more di fficult to visualize and draw than the cubical voxels of a 3D Cartesian gri d. An advantage of working with attachment sets is that such sets can be sh own in a planar Schlegel diagram of a voxel, which is easy to draw.