Optimization with graph cuts has become very popular in recent years. Progress in problems such as stereo correspondence, image segmentation, etc., can be attributed, in part, to the development of efficient optimization based on graph cuts. Energy functions can be binary or multi-labeled, and if they are submodular, then a graph cut can be used to find an exact minimum, in both the binary and the multi-label case. Many useful multi-label energy functions, however, are not submodular and are NP-hard to optimize. For multi-label energies, a popular algorithm is the alpha-expansion, which finds an approximate solution. The alpha-expansion algorithm finds a local minimum with respect to "expansion" moves. The basic idea is that for a wide class of useful multi-label energies, finding the optimal alpha-expansion move for a fixed label alpha can be formulated as an optimization of a binary submodular energy. Thus the expansion moves are essentially binary, each pixel has a choice of 2 labels to switch to.
In this talk, we present several different types of moves for multi-label energies. Our moves are multi-label moves, namely each pixel gets a choice of more than 2 labels to switch to. The idea is similar to the alpha-expansion algorithm: restrict the label choice of each pixel to several out of all possible labels in such a way that the resulting restricted energy is submodular. We show that such moves work better for certain class of multi-label energy functions than alpha-expansion. We apply our multi-label moves to various tasks such as image restoration, stereo correspondence, single-view reconstruction, non-photorealistic rendering.
Copyright. All Rights Reserved.