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$LB@2n(1 $PLU f)$RB 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.
展开▼
