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 generate a 3D skeleton of the binary colon volume using a fast topological thinning algorithm. In the second step, we employ a graph search algorithm to remove extra loops and branches. These loops and branches are caused by holes in the object that are artifacts produced during image segmentation. In the final step, we compute a smooth representation of the centerline by approximating 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 centerline; otherwise, the algorithm is fully automated. Experimental results demonstrate that the algorithm is not only robust but also efficient.