Generic Cuts: An Efficient Optimal Algorithm for Submodular MRF-MAP Problems with Higher Order Cliques
Chetan Arora, Subhashis Banerjee, Prem Kalra, and S.N. Maheshwari
European Conference on Computer Vision (ECCV), October 2012.
Abstract
We propose a new algorithm called Generic Cuts for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials satisfying submodularity. The algorithm runs in time O(2^k n^3) in the worst case (k is clique order and n is the number of pixels). A special gadget is introduced to model flows in a high order clique and a technique for building a flow graph is specified. Based on the primal dual structure of the optimization problem the notions of capacity of an edge and cut are generalized to define a flow problem. We show that in this flow graph max flow is equal to min cut which also is the optimal solution to the problem when potentials are submodular. This is in contrast to all prevalent techniques of optimizing Boolean energy functions involving higher order potentials including those based on reductions to quadratic potential functions which provide only approximate solutions even for submodular functions. We show experimentally that our implementation of the Generic Cuts algorithm is more than an order of magnitude faster than all algorithms including reduction based whose outputs on submodular potentials are near optimal.
Links
Updates
  • April 30, 2013: Released BKGC. Fixed some other minor issues.
  • April 20, 2013: Some people are reportedly using GC with the negative costs. Note that the current release can handle non-negative costs only. You will need to reparametrize outside to make all costs non-negative.
  • April 19, 2013: Crash in the Debug version fixed (Thanks Petter Strandmark for reporting)