Share Email Print
cover

Proceedings Paper

Center line algorithm for virtual endoscopy based on chamfer distance transform and Dijkstra's single-source shortest-path algorithm
Author(s): Daniel J. Blezek; Richard A. Robb
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 20 May 1999
PDF: 9 pages
Proc. SPIE 3660, Medical Imaging 1999: Physiology and Function from Multidimensional Images, (20 May 1999); doi: 10.1117/12.349592
Show Author Affiliations
Daniel J. Blezek, Mayo Clinic and Foundation (United States)
Richard A. Robb, Mayo Clinic and Foundation (United States)


Published in SPIE Proceedings Vol. 3660:
Medical Imaging 1999: Physiology and Function from Multidimensional Images
Chin-Tu Chen; Anne V. Clough, Editor(s)

© SPIE. Terms of Use
Back to Top