ML Anthology

On Solving Exact Euclidean Distance Transformation with Invariance to Object Size

Frank Y. Shih, Chyuan-Huei T. Yang
CVPR 1993 pp. 607-608
doi:10.1109/CVPR.1993.341063 /cvpr/1993/shih1993cvpr-solving/

Abstract

A distance transformation converts a digital binary image that consists of object (foreground) and non-object (background) pixels into a gray-scale image in which each object pixel has a value corresponding to the minimum distance from the background by a distance function. Due to its nonlinearity, the global operation of Euclidean distance transformation (EDT) is difficult to decompose into small neighborhood operations. Two efficient algorithms on EDT are presented, using integers of squared Euclidean distances in which the global computations can be equivalent to local 3/spl times/3 neighborhood operations. The first algorithm requires only a limited number of iterations on the chain propagation. The second algorithm can avoid iterations, and simply requires two scans of the image. The complexity of both algorithms is only linearly proportional to image size.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

CVPR Semantic Scholar

Cite

Text

Shih and Yang. "On Solving Exact Euclidean Distance Transformation with Invariance to Object Size." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1993. doi:10.1109/CVPR.1993.341063

Markdown

[Shih and Yang. "On Solving Exact Euclidean Distance Transformation with Invariance to Object Size." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1993.](https://mlanthology.org/cvpr/1993/shih1993cvpr-solving/) doi:10.1109/CVPR.1993.341063

BibTeX

@inproceedings{shih1993cvpr-solving,
  title     = {{On Solving Exact Euclidean Distance Transformation with Invariance to Object Size}},
  author    = {Shih, Frank Y. and Yang, Chyuan-Huei T.},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {1993},
  pages     = {607-608},
  doi       = {10.1109/CVPR.1993.341063},
  url       = {https://mlanthology.org/cvpr/1993/shih1993cvpr-solving/}
}