Technical Note: Solving the "Chinese postman problem" for effective contour deformation

To develop a practical approach for accurate contour deformation when deformable image registration (DIR) is used for atlas-based segmentation or contour propagation in image-guided radiotherapy.

We developed a contour deformation approach based on 3D mesh operations. The 2D contours represented by a series of points in each slice were first converted to a 3D triangular mesh, which was deformed by the deformation vectors resulting from DIR. A set of parallel 2D planes then cut through the deformed 3D mesh, generating unordered points and line segments, to be reorganized into a set of 2D contour points. The reorganization problem was equivalent to solving the "Chinese postman problem" (CPP) by traversing a graph built from the unordered points with the least cost. Alternatively, deformation could be applied to a binary image converted from the original contours. The deformed binary image was then converted back into contours at the CT slice locations. We validated the mesh-based contour deformation approach using lung and heart contours from 10 patients with thoracic cancer.

DIR could change the 3D mesh considerably, complicating 2D contour representations after deformation. CPP could effectively reorganize the points in 2D planes regardless of how complicated the 2D contours were. Among the 10 patients, the Dice similarity coefficient between the mesh-based contour and binary image-based contour was 97.6% ± 0.3% for lung and 97.5% ± 0.7% for heart, and the Hausdoroff distance between them was 19.8 ± 5.1 mm for lung and 6.1 ± 2.2 mm for heart. Subjective evaluation showed that the mesh-based approach could keep fine details, especially for the lung. The image-based approach seemed to overprocess contours and suffered from image resolution limits.

We developed a practical approach for accurate contour deformation and demonstrated its effectiveness for both clinical and research applications.