Efficient computation of the Euclidean distance transform

被引：8

作者：

Boxer, L ^{[1
]}

Miller, R

机构：

[1] Niagara Univ, Dept Comp & Informat Sci, New York, NY 14109 USA

[2] SUNY Buffalo, Ctr Comp Res & Dev Comp Sci & Engn, Buffalo, NY 14260 USA

[3] SUNY Buffalo, Ctr Computat Res, Buffalo, NY 14260 USA

[4] SUNY Buffalo, Dept Comp Sci & Engn, Buffalo, NY 14260 USA

来源：

COMPUTER VISION AND IMAGE UNDERSTANDING | 2000年 / 80卷 / 03期

基金：

美国国家科学基金会;

关键词：

Euclidean distance transform; binary image; parallel algorithm; RAM; EREW PRAM; mesh; hypercube; mesh-of-trees;

D O I：

10.1006/cviu.2000.0880

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many architectures and has optimal cost for the RAM and EREW PRAM. (C) 2000 Academic Press.

引用

页码：379 / 383

页数：5

共 7 条

[1] Fast Euclidean distance transformation by propagation using multiple neighborhoods [J].

Cuisenaire, O ;

Macq, B .

COMPUTER VISION AND IMAGE UNDERSTANDING, 1999, 76 (02) :163-172

[2] Parallel computation of the Euclidean distance transform on the mesh of trees and the hypercube computer [J].

Lee, YH ;

Horng, SJ ;

Kao, TW ;

Chen, YJ .

COMPUTER VISION AND IMAGE UNDERSTANDING, 1997, 68 (01) :109-119

[3]

Miller R., 1996, PARALLEL ALGORITHMS

[4]

MILLER R, 2000, ALGORITHMS SEQUENTIA

[5]

Nadler S B Jr., 1978, Hyperspaces of Sets

[6] DISTANCE FUNCTIONS ON DIGITAL PICTURES [J].

ROSENFELD, A ;

PFALTZ, JL .

PATTERN RECOGNITION, 1968, 1 (01) :33-+

[7] AN IMAGE ALGORITHM FOR COMPUTING THE HAUSDORFF DISTANCE EFFICIENTLY IN LINEAR TIME [J].

SHONKWILER, R .

INFORMATION PROCESSING LETTERS, 1989, 30 (02) :87-89

← 1 →