Three-dimensional Euclidean distance transformation and its application to shortest path planning

Frank Y. Shih, Yi Ta Wu

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

Abstract

In this paper, we present a novel method to obtain the three-dimensional Euclidean distance transformation (EDT) in two scans of the image. The shortest path can be extracted based on the distance maps using the minimum value tracing. The EDT is obtained correctly and efficiently in a constant time for arbitrary types of images, including the existence of obstacles. By adopting the new dynamically rotational mathematical morphology, we not only guarantee the collision-free in the shortest path, but also reduce the time complexity dramatically.

Original languageEnglish (US)
Pages (from-to)79-92
Number of pages14
JournalPattern Recognition
Volume37
Issue number1
DOIs
StatePublished - Jan 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Keywords

  • Distance transformation
  • Euclidean distance
  • Image processing
  • Shortest path planning

Fingerprint

Dive into the research topics of 'Three-dimensional Euclidean distance transformation and its application to shortest path planning'. Together they form a unique fingerprint.

Cite this