We will present in this talk a graph optimization problem occurred in virtual endoscopy, which concerns finding the central path of a colon model created from helical computed tomography (CT) image data. The central path is an e ssential aid for navigating through complex anatomy such as colon. We will present an efficient and robust method for finding the central path of a colon based on 3D skeleton. The method first generates colon data from a helical CT data volume by image segmentation. It then generates a 3D skeleton of the colon. In the ideal situation, namely, if the skeleton does not contain branches, the skeleton will be the desired central path. However, almost always the skeleton contains extra branches caused by holes in the colon model, which are artifacts produced during image segmentation. To remove false branches, we formulate a graph optimization problem and show that the solution of the problem represents the accurate central path of a colon. We then provide a fast algorithm for solving the problem. Clinically, this method has been successfully applied to the analysis of a number of colon cases.

(This is joint work with Y. Ge, D. Stelts, X. Zha, and D. Vining at the Bowman Gray School of Medicine, Wake Forest University.)