Abstract

We propose an algorithm called Multi Label Generic Cuts (MLGC) for computing optimal solutions to MRFMAP problems with submodular multi label multi-clique potentials. A transformation is introduced to convert a mlabel k-clique problem to an equivalent 2-label (mk)-clique problem. We show that if the original multi-label problem is submodular then the transformed 2-label multi-clique problem is also submodular. We exploit sparseness in the feasible configurations of the transformed 2-label problem to suggest an improvement to Generic Cuts [3] to solve the 2-label problems efficiently. The algorithm runs in time O(mk n3 ) in the worst case (n is the number of pixels) generalizing O(2k n3 ) running time of Generic Cuts. We show experimentally that MLGC is an order of magnitude faster than the current state of the art [17, 20]. While the result ofMLGC is optimal for submodular clique potential it is significantly better than the compared methods even for problems with non-submodular clique potential.