Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

The efficient algorithms for achieving Euclidean distance transformation.

Frank Y Shih1, Yi-Ta Wu

  • 1Computer Vision Laboratory, College of Computing Sciences, New Jersey Institute of Technology, Newark, NJ 07102, USA. shih@njit.edu

IEEE Transactions on Image Processing : a Publication of the IEEE Signal Processing Society
|August 26, 2004
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Development and validation of a real-time computer-aided measuring system for colorectal polyp size (with video).

Gastroenterology report·2026
Same author

Colorectal Polyp Size Measurement Faces Infinite Possibilities: Artificial Intelligence Is the Key.

Digestion·2025
Same author

No Evidence That the Phoretic Mite <i>Poecilochirus carabi</i> Influences Mate Choice or Fitness in the Host Burying Beetle <i>Nicrophorus nepalensis</i>.

Ecology and evolution·2025
Same author

Automatic liver segmentation from abdominal CT volumes using graph cuts and border marching.

Computer methods and programs in biomedicine·2017
Same author

Efficient liver segmentation in CT images based on graph cuts and bottleneck detection.

Physica medica : PM : an international journal devoted to the applications of physics to medicine and biology : official journal of the Italian Association of Biomedical Physics (AIFB)·2016
Same author

Computer-aided detection of breast masses: four-view strategy for screening mammography.

Medical physics·2011
Same journal

Style-Aware Contrastive Test-Time Adaptation: A Dual-Cache Model for Robust Vision-Language Alignment.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2026
Same journal

Semantic Frame Interpolation.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2026
Same journal

Physics-Guided Cross-Modal Decoupling with Test-Time Adaptation for Hyperspectral Image Restoration.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2026
Same journal

Change-Prior-Guided Unsupervised Change Detection of Heterogeneous Remote Sensing Images.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2026
Same journal

AgonicDreamer: Enhancing Multi-View Consistency in Text-to-3D Generation via Rectified Score Distillation.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2026
Same journal

BiCM-Prompt: Bidirectional Cross-Modal Prompt Tuning for Class-Incremental Learning on Multisource Remote Sensing Images.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2026
See all related articles

This study introduces a novel two-scan algorithm for Euclidean distance transformation (EDT), significantly improving efficiency and accuracy. The new method correctly handles images with obstacles, unlike many existing algorithms.

Area of Science:

  • Computer Vision
  • Image Processing
  • Computational Geometry

Background:

  • Euclidean distance transformation (EDT) is a fundamental image processing technique.
  • Existing iterative erosion algorithms for EDT can be computationally redundant.
  • Accurate EDT is crucial for various applications, including object recognition and pathfinding.

Purpose of the Study:

  • To develop a more efficient and accurate algorithm for Euclidean distance transformation.
  • To address limitations of existing EDT algorithms, particularly in handling images with obstacles.
  • To propose a constant-time algorithm for EDT without preprocessing.

Main Methods:

  • An improved iterative erosion algorithm was developed to reduce redundant calculations.
  • A novel two-scan-based algorithm was derived to achieve EDT in constant time.

Related Experiment Videos

  • The proposed algorithm's performance was evaluated, especially in scenarios with image obstacles.

    • Main Results:

    • The two-scan-based algorithm achieves correct Euclidean distance transformation efficiently.
    • The algorithm operates in constant time, avoiding iterative processes.
    • It demonstrates superior accuracy in images containing obstacles compared to other methods.
    • No additional preprocessing or relative-coordinate recording is required.

    Conclusions:

    • The developed two-scan algorithm offers a significant advancement in Euclidean distance transformation.
    • It provides a correct, efficient, and robust solution for EDT, even with complex image features.
    • This method eliminates the need for costly preprocessing steps, making it highly practical.