A general algorithm for computing distance transforms in linear time

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

437 Downloads (Pure)

Abstract

A new general algorithm fur computing distance transforms of digital images is presented. The algorithm consists of two phases. Both phases consist of two scans, a forward and a backward scan. The first phase scans the image column-wise, while the second phase scans the image row-wise. Since the computation per row (column) is independent of the computation of other rows (columns), the algorithm can be easily parallelized on shared memory computers. The algorithm can be used for the computation of the exact Euclidean, manhattan (L-1 norm), and chessboard distance (L-infinity norm) transforms.

Original languageEnglish
Title of host publicationMATHEMATICAL MORPHOLOGY AND ITS APPLICATIONS TO IMAGE AND SIGNAL PROCESSING
EditorsJ Goutsias, L Vincent, DS Bloomberg
Place of PublicationNORWELL
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Pages331-340
Number of pages10
ISBN (Electronic)030647025X
ISBN (Print)0-7923-7862-8
Publication statusPublished - 2000
Event5th International Symposium on Mathematical Morphology (ISMM) - , Canada
Duration: 26-Jun-200029-Jun-2000

Publication series

NameCOMPUTATIONAL IMAGING AND VISION
PublisherKLUWER ACADEMIC PUBLISHERS
Volume18

Other

Other5th International Symposium on Mathematical Morphology (ISMM)
Country/TerritoryCanada
Period26/06/200029/06/2000

Keywords

  • distance transforms
  • row-column factorization
  • parallelization
  • IMAGES

Cite this