Distance Transformation: algorithms and applications

Francisco de Assis Zampirolli
Federal University of ABC, Brazil

The Distance Transform is one of the classical operators in image processing, and can be used in Pattern Recognition and Data Mining, and there is currently a great demand for efficient parallel implementations on graphics cards, known as GPU. Distance transform is a classical transformations in Mathematical Morphology and its algorithms that can be written using a fundamental morphological operator. The performance of the algorithms is an important research problem. To improve them, some algebraic properties like indempontence and decomposition of structuring functions needs to be used. Morphological operators can be coded in parallel, sequential, or propagation sweeping patterns. There are also sweeping patterns Directional and Multidimensional. In this second algorithm the distance transform can be composed by several one dimensional erosions. The structuring functions used in the erosion belongs to a family of four directional one-dimensional two-point structuring functions. The erosion algorithm is based on a propagation scheme very simple to code and understand, yet being one of the fastest euclidean distance transform algorithms in the literature. Some of these sweeping patterns, known as brute-force, can be implemented in GPU, and even then present excellent results, comparable to the best CPU algorithms, which might contribute to future applications in image processing.

Francisco de Assis Zampirolli

Francisco de Assis Zampirolli is a Professor in the Center of Mathematical, Computer and Cognition at the Federal University of ABC, Brazil. He received his BSs degrees in Mathematics from the Federal University of Espírito Santo, Brazil in 1992, and MSc in Applied Mathematics from the University of São Paulo, Brazil in 1997, and Ph.D. in Electrical Engineering from the University of Campinas, Brazil in 2003. Has experience in the area of Computer Science, with emphasis on Image Processing, acting on the following subjects:mathematical morphology, computer vision,  automatic code generation and documents, GPU, and mobile devices.