Computing the centerline of a colon: A robust and efficient method based on 3D skeletons

We present a robust and efficient algorithm for calculating the centerline of a computer-generated colon model created from helical CT image data. The centerline is an essential aid for navigating through complex anatomy such as the colon. Our algorithm involves three steps. In the first step, we ge nerate a 3D skeleton of the binary colon volume using a fast topological th inning algorithm. In the second step, we employ a graph search algorithm to remove extra loops and branches. These loops and branches are caused by ho les in the object that are artifacts produced during image segmentation. In the final step, we compute a smooth representation of the centerline by ap proximating the skeleton with cubic B-splines. This final step is necessary because the skeleton contains many abrupt changes in direction due to the discrete nature of image data. The user supplies two endpoints for the cent erline; otherwise, the algorithm is fully automated. Experimental results d emonstrate that the algorithm is not only robust but also efficient.