An Adaptive Subdivision Scheme for Quadratic Programming in Multi-Label Image Segmentation
Marko Rak, Tim König, Klaus D. Tönnies · 2013
Convex quadratic optimization is one of the most widely used concepts in image segmentation. It facilitates a wide range of information sources, such as edge, intensity, texture and shape. The problem is especially challenging for the multi-label case, even being NP-hard in its most general setting. Therefore, fast solutions, as the α-expansion of [1], are limited to local optimality. Addressing this problem, several approaches relax the labeling integrality condition, resulting in quadratic programs (QPs) like in [2] and in [4], which can be solved in polynomial time. Although this is efficient in a theoretical sense, large-scale QPs that arise from typical multi-label tasks can rarely be used for image segmentation directly due to either time or space constraints, or both. We address this issue by an adaptive domain subdivision scheme, reducing the problem to a short sequence of spatially smoothed medium-scale QPs, which subsequently better approximate the large-scale program. Our scheme is globally optimal in terms of the approximated problem. Putting our main focus on the subdivision, we restrict ourselves to minimization of the popular but rather simple piecewise constant MumfordShah functional. Therefore, we seek for a labeling that trades off the length of the labeling border and the approximation of image intensity u by known reference intensitites ui for each label i. For discrete domains the associated energy can be written as