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 all 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.