David Tolliver, Gary Miller, and Robert T. Collins,
"Corrected Laplacians: closer cuts and segmentation with shape priors,"
IEEE Computer Vision and Pattern Recognition (CVPR'05),
San Diego, CA, June 2005, pp.92-98.
We optimize over the set of corrected Laplacians (CL) associated with
a weighted graph to improve the average case normalized cut (NCut) of
a graph. Unlike edge-relaxation SDPs, optimizing over the set CL
naturally exploits the matrix sparsity by operating solely on the
diagonal. This structure is critical to image segmentation
applications because the number of vertices is generally proportional
to the number of pixels in the image. CL optimization provides a
guiding principle for improving the combinatorial solution over the
spectral relaxation, which is important because small improvements in
the cut cost often result in significant improvements in the
perceptual relevance of the segmentation. We develop an optimization
procedure to accommodate prior information in the form of statistical
shape models, resulting in a segmentation method that produces
foreground regions which are consistent with a parameterized family of
shapes. We validate our technique with ground truth on MRI medical
images, providing a quantitative comparison against results produced
by current spectral relaxation approaches to graph partitioning.
Click here for
full paper (473801 bytes, pdf file).