An algorithm for a 3D simplicity test

Every thinning (or shrinking) algorithm can be stated as a list of deletion configurations. If a neighborhood of a given image point matches one of these configurations, the point will be deleted. In order to make design of a (3D) thinning (or shrinking) algorithm easy to handle, and therefore the list of configurations as short as possible, every configuration is described in three colors, black, white, and ''don't-care,'' where the don't-care ''color'' matches either a black or white point in a given image. A thinning algorithm is connectivity preserving if and only if every set deleted by this algorithm can be ordered in such a sequence that every point is simple after ail previous points in the sequence are deleted. Therefore, it is very important to determine whether a deleted point is simple or not. We present the first 3D algorithm for determining the simplicity of any three-color deletion configuration, This algorithm is memory efficient and fast. Hence it can be a very useful tool for designing 3D connectivity preserving thinning (or shrinking) algorithms. (C) 1996 Academic Press, Inc.