A Comparative Discussion of Distance Transforms and Simple Deformations in Image Processing

Abstract

Algorithms for transformations of digital images into reconstructible subsets of the original image, and algorithms for deformations of digital images into topologically equivalent images are subjects of hundreds of publications. Two images are topologically equivalent if their adjacency trees are isomorphic. Skeletonization is a transformation of components of a digital image into a subset of the original component. There are different categories of skeletonization methods: one category is based on distance transforms, and a specified subset of the transformed image is called distance skeleton. The original component can be reconstructed from the distance skeleton. But the result is not a topologically equivalent image. A different category is defined by thinning approaches, and the result of skeletonization using thinning algorithms should be a topologically equivalent image. Thinning algorithms are one-way simple deformations, which mean object points are transferred into background points without destroying the topology of the image. Two-way simple deformations transfer object points into background points and vice versa without destroying the topology of the image. This report reviews contributions in this area with respect to properties of algorithms and characterizations of simple points, and informs about a few new results.