A Systolic Algorithm for Euclidean Distance Transform
|
The Euclidean distance transform is one of the fundamental operations in image processing. It has been widely used in computer vision, pattern recognition, morphological filtering, and robotics. This paper proposes a systolic algorithm that computes the Euclidean distance map of an N\times N binary image in 3N clocks on 2N^2 processing cells. The algorithm is designed so that the hardware resources are reduced; especially no mulitipliers are used and, thus, it facilitates VLSI implementation.
[1] 1127 G. Borgefors, “Distance Transformations in Digital Images,” Computer Graphics and Image Processing, vol. 34, pp. 344-371, 1986.
[2] H. Brue, J. Gil, D. Kirkpatrick, and M. Werman, “Linear Time Euclidean Distance Transform Algorithms,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 529-533, May 1995.
[3] L. Chen and H. Chuang, “A Fast Algorithm for Euclidean Distance Maps of a 2-D Binary Image,” Information Processing letters, vol. 51, pp. 25-29, 1994.
[4] L. Chen and H. Chuang, “Designing Systolic Architechtures for Complete Euclidean Distance Transform,” J. VLSI Signal Processing, vol. 10, pp. 169-179, 1995.
[5] L. Chen and H. Chuang, “An Efficient Algorithm for Complete Euclidean Distance Transform on Mesh-Connected SIMD,” Parallel Computing, vol. 21, no. 5, pp. 841-852, 1995.
[6] O. Cuisenaire, “Distance Transformations: Fast Algorithms and Applications to Medical Image Processing,” PhD thesis, Universitá Catholique de Louvain, Belgium, Oct. 1999.
[7] P. Danielsson, “Euclidean Distance Mapping,” Computer Graphics and Image Processing, vol. 14, pp. 227-248, 1980.
[8] A. Fujiwara, T. Masuzawa, and H. Fujiwara, “An Optimal Parallel Algorithm for the Euclidean Distance Maps of 2-D Binary Images,” Information Processing Letters, vol. 54, no. 5, pp. 295-300, June 1995.
[9] T. Hirata, “A Unified Linear-Time Algorithm for Computing Distance Maps,” Information Processing Letters, vol. 58, pp. 129-133, 1996.
[10] M. Kolountzakis and K. Kutulakos, “Fast Computation of Euclidean Distance Maps for Binary Images,” Information Processing Letters, vol. 43, pp. 181-184, 1992.
[11] Y. Lee, S. Horng, T. Kao, and Y. Chen, “Parallel Computation of the Euclidean Distance Transform on the Mesh of Trees and the Hypercube Computer,” Computer Vision Image Understanding, vol. 68, no. 1, pp. 109-119, 1997.
[12] F. Leymarie and M. Levine, “Fast Raster-Scan Distance Propagation on the Discrete Rectangular Lattice,” CVGIP: Image Understanding, vol. 55, pp. 85-94, 1992.
[13] C. Maurer, R. Qi, and V. Raghavan, “A Linear Time Algorithm for Computing Exact Euclidean Distance Transforms of Binary Images in Arbitrary Dimensions,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, pp. 265-270, 2003.
[14] A. Meijster, J. Roerdink, and W. Hesselink, “A General Algorithm for Computing Distance Transforms in Linear Time,” Proc. Int'l Symp. Memory Management, pp. 331-340, 2000.
[15] D. Paglieroni, “A Unified Distance Transformation Algorithm and Architecture,” Machine Vision Applications, vol. 5, pp. 47-55, 1992.
[16] I. Ragnemarm, “Neighborhoods for Distance Transformations Using Ordered Propagation,” CVGIP: Image Understanding, vol. 56, pp. 399-409, 1992.
[17] A. Rosenfelt and J. Pfalts, “Sequential Operations in Digital Picture Processing,” J. ACM, vol. 13, pp. 471-494, 1966.
[18] H. Yamada, “Complete Euclidean Distance Transformation by Parallel Operation,” Proc. Seventh Int'l Conf. Pattern Recognition, vol. 1, pp. 69-71, 1984
Index Terms:
Euclidean distance transform, systolic array, hardware algorithm, image processing.
Citation:
Masafumi Miyazawa, Peifeng Zeng, Naoyuki Iso, Tomio Hirata, "A Systolic Algorithm for Euclidean Distance Transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 7, pp. 1127-1134, July 2006, doi:10.1109/TPAMI.2006.133
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb