Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood

Frank Y. Shih; Yi Ta Wu

doi:10.1016/j.cviu.2003.09.004

Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood

Frank Y. Shih, Yi Ta Wu

Computer Science

Research output: Contribution to journal › Article › peer-review

90 Scopus citations

Abstract

Cuisenaire and Macq [Comp. Vis. Image Understand., 76(2) (1999) 163] proposed a fast Euclidean distance transformation (EDT) by propagation using multiple neighborhoods and bucket sorting. To save the time for bucket sorting and to reduce the complexity of multiple neighborhoods, we propose a new, simple and fast EDT in two scans using a 3 × 3 neighborhood. By recording the relative x- and y-coordinates, an optimal two-scan algorithm can be developed to achieve the EDT correctly and efficiently in a constant time without iterations.

Original language	English (US)
Pages (from-to)	195-205
Number of pages	11
Journal	Computer Vision and Image Understanding
Volume	93
Issue number	2
DOIs	https://doi.org/10.1016/j.cviu.2003.09.004
State	Published - Feb 2004

All Science Journal Classification (ASJC) codes

Software
Signal Processing
Computer Vision and Pattern Recognition

Keywords

Distance transformation
Euclidean distance
Image processing
Object representation

Access to Document

10.1016/j.cviu.2003.09.004

Cite this

@article{db508f55884e4e688c9f511f6693a7be,

title = "Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood",

abstract = "Cuisenaire and Macq [Comp. Vis. Image Understand., 76(2) (1999) 163] proposed a fast Euclidean distance transformation (EDT) by propagation using multiple neighborhoods and bucket sorting. To save the time for bucket sorting and to reduce the complexity of multiple neighborhoods, we propose a new, simple and fast EDT in two scans using a 3 × 3 neighborhood. By recording the relative x- and y-coordinates, an optimal two-scan algorithm can be developed to achieve the EDT correctly and efficiently in a constant time without iterations.",

keywords = "Distance transformation, Euclidean distance, Image processing, Object representation",

author = "Shih, {Frank Y.} and Wu, {Yi Ta}",

year = "2004",

month = feb,

doi = "10.1016/j.cviu.2003.09.004",

language = "English (US)",

volume = "93",

pages = "195--205",

journal = "Computer Vision and Image Understanding",

issn = "1077-3142",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood

AU - Shih, Frank Y.

AU - Wu, Yi Ta

PY - 2004/2

Y1 - 2004/2

N2 - Cuisenaire and Macq [Comp. Vis. Image Understand., 76(2) (1999) 163] proposed a fast Euclidean distance transformation (EDT) by propagation using multiple neighborhoods and bucket sorting. To save the time for bucket sorting and to reduce the complexity of multiple neighborhoods, we propose a new, simple and fast EDT in two scans using a 3 × 3 neighborhood. By recording the relative x- and y-coordinates, an optimal two-scan algorithm can be developed to achieve the EDT correctly and efficiently in a constant time without iterations.

AB - Cuisenaire and Macq [Comp. Vis. Image Understand., 76(2) (1999) 163] proposed a fast Euclidean distance transformation (EDT) by propagation using multiple neighborhoods and bucket sorting. To save the time for bucket sorting and to reduce the complexity of multiple neighborhoods, we propose a new, simple and fast EDT in two scans using a 3 × 3 neighborhood. By recording the relative x- and y-coordinates, an optimal two-scan algorithm can be developed to achieve the EDT correctly and efficiently in a constant time without iterations.

KW - Distance transformation

KW - Euclidean distance

KW - Image processing

KW - Object representation

UR - http://www.scopus.com/inward/record.url?scp=0742304570&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0742304570&partnerID=8YFLogxK

U2 - 10.1016/j.cviu.2003.09.004

DO - 10.1016/j.cviu.2003.09.004

M3 - Article

AN - SCOPUS:0742304570

SN - 1077-3142

VL - 93

SP - 195

EP - 205

JO - Computer Vision and Image Understanding

JF - Computer Vision and Image Understanding

IS - 2

ER -

Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this