Efficient computation of Euclidean distance transform for applications in image processing

Author

Sudha, N. ; Nandi, S. ; Bora, P.K. ; Sridharan, K.

Author_Institution

Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Guwahati, India

Volume

1

fYear

1998

fDate

1998

Firstpage

49

Abstract

The paper presents a new parallel algorithm for computing Euclidean distance transform of a binary image. For an image of size n×n, the algorithm runs in O(n) time and takes O(n²) space. The Euclidean distance transform is computed by repeatedly performing identical local operations within a small neighbourhood of each pixel. The algorithm is therefore suitable for VLSI implementation in a cellular like structure

Keywords

VLSI; cellular arrays; combinational circuits; computational complexity; digital signal processing chips; image processing; integrated logic circuits; parallel algorithms; transforms; Euclidean distance transform; VLSI implementation; adders; binary image; cellular like structure; combinational logic; comparators; image processing; image size; local operations; parallel algorithm; pixel; registers; Application software; Computer science; Concurrent computing; Euclidean distance; Image analysis; Image converters; Image processing; Pixel; Skeleton; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

TENCON '98. 1998 IEEE Region 10 International Conference on Global Connectivity in Energy, Computer, Communication and Control

Conference_Location

New Delhi

Print_ISBN

0-7803-4886-9

Type

conf

DOI

10.1109/TENCON.1998.797067

Filename

797067