MRF labeling with a graph-shifts algorithm

We present an adaptation of the recently proposed graph-shifts algorithm for labeling MRF problems from low-level vision. Graph-shifts is an energy minimization algorithm that does labeling by dynamically manipulating, or shifting, the parent-child relationships in a hierarchical decomposition of the image. Graph-shifts was originally proposed for labeling using relatively small label sets (e.g., 9) for problems in high-level vision. In the low-level vision problems we consider, there are much larger label sets (e.g., 256). However, the original graph-shifts algorithm does not scale well with the number of labels; for example, the memory requirement is quadratic in the number of labels. We propose four improvements to the graph-shifts representation and algorithm that make it suitable for doing labeling on these large label sets. We implement and test the algorithm on two low-level vision problems: image restoration and stereo. Our results demonstrate the potential for such a hierarchical energy minimization algorithm on low-level vision problems with large label sets.