Center line algorithm for virtual endoscopy based on chamfer distance transform and Dijkstra's single-source shortest-path algorithm

Daniel J. Blezek; Richard A. Robb

doi:10.1117/12.349592

20 May 1999 Center line algorithm for virtual endoscopy based on chamfer distance transform and Dijkstra's single-source shortest-path algorithm

Daniel J. Blezek, Richard A. Robb

Author Affiliations +

Proceedings Volume 3660, Medical Imaging 1999: Physiology and Function from Multidimensional Images; (1999) https://doi.org/10.1117/12.349592
Event: Medical Imaging '99, 1999, San Diego, CA, United States

Abstract

Successful applications of virtual endoscopy often require the generation of centerlines as flight paths for fly-through examinations of anatomic structures. Criteria for design of effective centerline algorithms should include the following: (1) tracking of the most medial path possible, (2) robustness to segmentation errors, (3) computational efficiency, and (4) minimum of user interaction. To satisfy these design goals, we have developed a centerline generation algorithm based on the chamfer distance transform and Dijkstra's single-source shortest path algorithm. The distance transformation is applied to a segmented volume to determine the distance from each object voxel to the nearest background voxel -- a 'medialness' measure for each voxel. From a user specified source voxel, the distance and path from each object voxel to the source voxel is determined using Dijkstra's single-source shortest path algorithm, with the 'medialness' measure used as the weighting or distance factor between voxels. After execution of the algorithm is complete, paths from all voxels in the object to the source can be easily computed, a feature that is useful for all implementations of virtual endoscopy, but particularly for virtual bronchoscopy, which involves branching. The algorithm runs in O[2n(1 + f)] time, where n is the number of voxels in the volume, and f is the ratio of object voxels to total voxels in the volume. The algorithm is efficient, requiring approximately 90 seconds for a 60 megabyte dataset containing a segmented colon, and is robust to noise, segmentation errors, and start/end voxel selection. The only user interaction required is choosing the starting and ending voxels for the path. We report on objective and subjective evaluations of the algorithm when applied to several mathematical phantoms, the Visible Human Male Dataset and patient exams.

Citation Download Citation

Daniel J. Blezek and Richard A. Robb "Center line algorithm for virtual endoscopy based on chamfer distance transform and Dijkstra's single-source shortest-path algorithm", Proc. SPIE 3660, Medical Imaging 1999: Physiology and Function from Multidimensional Images, (20 May 1999); https://doi.org/10.1117/12.349592

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available