A systolic algorithm for Euclidean distance transform

Author

Miyazawa, M. ; Peifeng Zeng ; Iso, N. ; Hirata, T.

Author_Institution

Brother Ind. Ltd., Nagoya

Volume

28

Issue

7

fYear

2006

fDate

7/1/2006 12:00:00 AM

Firstpage

1127

Lastpage

1134

Abstract

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² processing cells. The algorithm is designed so that the hardware resources are reduced; especially no multipliers are used and, thus, it facilitates VLSI implementation

Keywords

VLSI; computational complexity; geometry; image processing; parallel algorithms; systolic arrays; transforms; Euclidean distance transform; VLSI; binary image; image processing; systolic algorithm; Algorithm design and analysis; Clocks; Computer vision; Euclidean distance; Filtering; Hardware; Image processing; Pattern recognition; Robot vision systems; Very large scale integration; Euclidean distance transform; hardware algorithm; image processing.; systolic array; Algorithms; Artificial Intelligence; Computer-Aided Design; Equipment Design; Equipment Failure Analysis; Image Enhancement; Image Interpretation, Computer-Assisted; Imaging, Three-Dimensional; Information Storage and Retrieval; Pattern Recognition, Automated; Signal Processing, Computer-Assisted;

fLanguage

English

Journal_Title

Pattern Analysis and Machine Intelligence, IEEE Transactions on

Publisher

ieee

ISSN

0162-8828

Type

jour

DOI

10.1109/TPAMI.2006.133

Filename

1634343