Fast Approximate Energy Minimization with Label Costs

Andrew Delong, Anton Osokin, Hossam Isack, Yuri Boykov

In International Journal of Computer Vision (IJCV), vol. 96, no. 1, pp. 1-27, Jan. 2012.


The a-expansion algorithm has had a significant impact in computer vision due to its generality, effectiveness, and speed. It is commonly used to minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main algorithmic contribution is an extension of a-expansion that also optimizes label costs with well characterized optimality bounds. Label costs penalize a solution based on the set of labels that appear in it, for example by simply penalizing the number of labels in the solution.

Our energy has a natural interpretation as minimizing description length (MDL) and sheds light on classical algorithms like K-means and expectation-maximization (EM). Label costs are useful for multi-model fitting and we demonstrate several such applications: homography detection, motion segmentation, image segmentation, and compression. Our C++ and MATLAB code are publicly available.

related paper - details on energy-based geometric multi-model fitting
Earlier Tech.Rep: no.731, Comp.Sci. dept., UWO, Dec. 2009)