MINIMAL NONSIMPLE SETS OF VOXELS IN BINARY IMAGES ON A FACE-CENTERED CUBIC GRID

摘要

One can prove that a specified parallel thinning algorithm always preserves the topology of the input binary image by verifying that no iteration of that algorithm can ever delete a minimal non-simple ("MNS") set of 1's of an image. For binary images on a 3D face-centered cubic ("FCC") grid, we determine which sets of voxels can be MNS, and also determine which of those sets 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 setsof 1's and 12-connectedness 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-connectedness for sets of 0's. We solve the two problems in all three cases. The analogous problems for binary images on Cartestin grids were first solved by Ronse (in the 2D case) and Ma (in the 3D case). However, our treatment 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 introduced in an earlier paper [T.Y.Kong, "On topology preservation in 2-D and 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 used there. The voxels of an FCC grid are rhombic dodecahedra, which are rather more difficult to visualize and draw than the cubical voxels of a 3D Cartesian grid. An advantage of working