Fast and robust computation of colon centerline in CT colonography

Although several methods for generating the centerline of a colon from CT colonographic scans have been proposed, in general they are time-consuming and do not take into account that the images of the colon may be of nonoptimal quality, with collapsed regions, and stool within the colon. Furthermore, the colonic lumen or wall, which is often used as a basis for computation of a centerline, is not always precisely segmented. In this study, we have developed an algorithm for computation of a colon centerline that is fast compared to the centerline algorithms presented in the reviewed literature, and that relies little on a complete colon segments identification. The proposed algorithm first extracts local maxima in a distance map of a segmented colonic lumen. The maxima are considered to be nodes in a set of graphs, and are iteratively linked together, based on a set of connection criteria, giving a minimum distance spanning tree. The connection criteria are computed from the distance from object boundary, the Euclidean distance between nodes and the voxel values on the pathway between pairs of nodes. After the last iteration, redundant branches are removed and end segments are recovered for each remaining graph. A subset of the initial maxima is used for distinguishing between the colon and noncolonic centerline segments among the set of graphs, giving the final centerline representation. A phantom study showed that, with respect to phantom variations, the algorithm achieved nearly constant computation time (2.3-2.9 s) except for the most extreme setting (20.2 s). The algorithm successfully found all, or most of, the centerline (93% - 100%). Displacement from optimum varied with colon diameter (1.2-6.6 mm). By use of 40 CT colonographic scans, the computer-generated centerlines were compared with the centerlines generated by three radiologists. The similarity was measured based on percent coverage and average displacement. The computer-generated centerlines, when compared with human-generated centerlines, had approximately the same displacement as when the human-generated centerlines were compared among each other (3.8 mm versus 4.0 mm). The coverage of the computer-generated centerlines was slightly less than that of the human-generated centerlines (92% versus 94%). The 40 centerlines were, on average, computed in 10.5 seconds, including computation time for the distance transform, with an Intel Pentium-based 800 MHz computer, as compared with 12-17 seconds or more (excluding computation time for the distance transform needed) per centerline as reported in other studies.