Optimal surface segmentation in volumetric images--a graph-theoretic approach

Abstract

Efficient segmentation of globally optimal surfaces representing object boundaries in volumetric data sets is important and challenging in many medical image analysis applications. We have developed an optimal surface detection method capable of simultaneously detecting multiple interacting surfaces, in which the optimality is controlled by the cost functions designed for individual surfaces and by several geometric constraints defining the surface smoothness and interrelations. The method solves the surface segmentation problem by transforming it into computing a minimum s-t cut in a derived arc-weighted directed graph. The proposed algorithm has a low-order polynomial time complexity and is computationally efficient. It has been extensively validated on more than 300 computer-synthetic volumetric images, 72 CT-scanned data sets of different-sized plexiglas tubes, and tens of medical images spanning various imaging modalities. In all cases, the approach yielded highly accurate results. Our approach can be readily extended to higher-dimensional image segmentation.

Fig. 1. The single-surface detection problem

(a) The surface orientation. (b) Two adjacent columns of the constructed directed graph. Arcs shown in dashed lines are optional.

Fig. 2. Image unfolding

(a) A tubular object in a volumetric image. (b) “Unfolding” the tubular object in (a) to form a new 3D image. The boundary of the tubular object in the original image corresponds to a surface to be detected in the unfolded image.

Fig. 3. Summary of surface interrelation modeling

𝒩₁ and 𝒩₂ are two desired surfaces. Col₁(x, y) and Col₂(x, y) are two corresponding columns in the constructed graphs. Arcs shown in dashed lines are optional. (a) The noncrossing case. (b) The case with crossing allowed.

Fig. 4. Human airway tree and 3D resampling

(a) Three-dimensional surface rendering of a segmented human airway tree. (b) Two-dimensional slices were resampled perpendicular to the centerlines of airway branches, producing a new volume containing a single airway segment. Inside wall surface was detected, cross-sectional area, minor, and major-diameter were computed.

Fig. 5. Effect of intrasurface smoothness constraints

(a) Cross-section of the original image. (b) The first cost image. (c) The second cost image. (d) Results obtained with smoothness parameters Δ_x = Δ_y = 1. (e) Results obtained with smoothness parameters Δ_x = Δ_y = 5.

Fig. 6. Effect of surface separation constraints

(a) Cross-section of the original image. (b) The first cost image. (c) The second/third cost image. (d) Results obtained with separation parameters ${\delta }_{12}^l=5,{\delta }_{12}^u=15\text{and}{\delta }_{13}^l=16,{\delta }_{13}^u=25.$ (d) Results obtained with separation parameters ${\delta }_{12}^l=5,{\delta }_{12}^u=15\text{and}{\delta }_{13}^l=26,{\delta }_{13}^u=35.$

Fig. 7. Single-surface versus coupled-surfaces

(a) Cross-section of the original image. (b) Single surface detection using our method with standard edge-based cost function. (c) MetaMorphs method segmenting the inner border in 2D. (d) MetaMorphs with the texture term turned off. (e) Single surface detection using our algorithm and a cost function with a shape term. (f) Double-surface segmentation obtained with our approach.

Fig. 8. Segmentation using the minimum-variance cost function

(a), (b), and (c) Original images. (d), (e), and (f) The segmentation results.

Fig. 9. Execution time comparisons

(a) Single-surface detection case. (b) Execution times in smooth and noisy cost functions for triple-surface detection (3S = smooth, 3N = noisy).

Fig. 10. Signed percent errors of inner and outer-diameter measurements in the CT-imaged phantom

Mean errors standard deviations shown as a function of phantom tube diameter.

Fig. 11. Comparison of observer-defined and computer-segmented inner and outer airway wall borders

(a) Expert-traced borders. (b) Three-dimensional surface obtained using our double-surface segmentation method.

Fig. 12. Segmentation of inner airway wall surface in five consecutive slices of an airway segment, shown with 3D surface rendering of the obtained surface

(a) Slice-by-slice dynamic programming segmentation—notice the “leaking” in one of the slices using the 2D method. (b) Optimal coupled-surface segmentation approach using the 3D method.

Fig. 13. Three-dimensional segmentation of the diaphragm surface from volumetric in vivo CT image

(a) Coronal and sagittal views of the original image with the manually traced independent standard segmentation. (b) Three-dimensional surface segmentation approach.

Fig. 14. Segmentation of MR arterial walls and plaque

(a) Two original MR slices. (b) Manually identified lumen, IEL, and EEL borders. (c) Segmentation obtained using slice-by-slice dynamic programming. On average, 2.4 interaction points per image slice were needed. (d) Four borders identified by the reported fully automated optimal four-surface segmentation method.

Fig. 15. IVUS image segmentation result

(a) Polar and longitude cross-sections of the original image. (b) Segmentation result by optimal coupled-surface segmentation. (c) Surface reconstruction.