Approximate Energy Minimization with Label Costs
Andrew Delong, University of Western Ontario
I+/--expansion algorithm is popular in vision due to its generality,
effectiveness, and speed. It can minimize energies involving
unary, pairwise, and specialized high-order terms. I will present an
extension of I+/--expansion that can optimize "label cost" terms as well.
The simplest use of label costs is to penalize the number of
labels in the solution; this alone has many applications in vision, but
general label costs can do much more. I will explain
how label costs affect energies and will quickly review basic applications
in multi-model fitting (detecting planes/motions, segmentation).
The remainder of the talk will focus on the optimization
problem itself: how the extension to I+/--expansion works, how
label costs worsen optimality guarantees, how they generalize a
class of well-known (and NP-hard) "facility location" problems. Our
technique is certainly not the final word on optimizing label costs,
so those interested in optimization are especially encouraged to
This is joint
work with A. Osokin, H. Isack, and Y. Boykov.