Fast Approximate Energy Minimization with Label Costs

Andrew Delong, Anton Osokin, Hossam Isack, Yuri Boykov

In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, June 2010.
Also in International Journal of Computer Vision (IJCV), accepted December 2010.


The a-expansion algorithm [4] has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main contribution is to extend a-expansion so that it can simultaneously optimize “label costs” as well. An energy with label costs can penalize a solution based on the set of labels that appear in it. The simplest special case is to penalize the number of labels in the solution. Our energy is quite general, and we prove optimality bounds for our algorithm. A natural application of label costs is multi-model fitting, and we demonstrate several such applications in vision: homography detection, motion segmentation, and unsupervised image segmentation. Our C++/MATLAB implementation is publicly available.

WHOLE PAPER (pdf file, 6MB)
IJCV VERSION - RECOMMENDED (more examples, applications, insights, and updates on recent related work)