Efficient segmentation of globally optimal surfaces in volumetric images is a central problem in many medical image
analysis applications. Intra-class variance has been successfully utilized, for instance, in the Chan-Vese model especially
for images without prominent edges. In this paper, we study the optimization problem of detecting a region (volume)
bounded by a smooth terrain-like surface, whose intra-class variance is minimized. A novel polynomial time algorithm is
developed. Our algorithm is based on the shape probing technique in computational geometry and computes a sequence
of <i>O(n)</i> maximum flows in the derived graphs, where <i>n</i> is the size of the input image. Our further investigation shows
that those <i>O(n)</i> graphs form a monotone parametric flow network, which enables to solving the optimal region detection
problem in the complexity of computing a single maximum flow. The method has been validated on computer-synthetic
volumetric images. Its applicability to clinical data sets was demonstrated on 20 3-D airway wall CT images from 6
subjects. The achieved results were highly accurate. The mean unsigned surface positioning error of outer walls of the
tubes is 0.258 ± 0.297mm, given a voxel size of 0.39 x 0.39 x 0.6mm<sup>3</sup>.
Proc. SPIE. 7259, Medical Imaging 2009: Image Processing
KEYWORDS: Image processing algorithms and systems, Detection and tracking algorithms, Data modeling, Magnetic resonance imaging, Image segmentation, 3D modeling, Feature extraction, Medical imaging, 3D vision, 3D image processing
We present a novel method for incorporating both edge and regional image information in a 3-D graph-theoretic
approach for globally optimal surface segmentation. The energy functional takes a ratio form of the "onsurface"
cost and the "in-region" cost. We thus introduce an optimal surface segmentation model allowing
regional information such as volume, homogeneity and texture to be included with boundary information such
as intensity gradients. Compared to the linear combination as in the standard active contour energies, this ratioform
energy is parameter free with no bias toward either a large or small region. Our method is the first attempt
to use a ratio-form energy functional in graph search framework for high dimensional image segmentation, which
delivers a globally optimal solution in polynomial time. The globally optimal surface can be achieved by solving
a parametric maximum flow problem in the time complexity of computing a single maximum flow. Our new
approach is applied to the aorta segmentation of 15 3-D MR aortic images from 15 subjects.
Compared to an expert-defined independent standard, the overall mean unsigned surface positioning error
was 0.76± 0.88 voxels. Our experiments showed that the incorporation of the regional information was effective
to alleviate the interference of adjacent objects.