Article added to library!
Pubchase is a service of - free, open access, crowdsourced protocols repository. Explore protocols.
Sign in
Reset password
or connect with
By signing in you are agreeing to our
Terms Of Service and Privacy Policy
Sep 10, 2015
IEEE Transactions On Pattern Analysis And Machine Intelligence
Use of higher order clique potentials in MRF-MAP problems has been limited primarily because of the inefficiencies of the existing algorithmic schemes. We propose a new combinatorial algorithm for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials. The algorithm runs in time O(2(k)n(3)) in the worst case (k is size of clique and n is the number of pixels). A special gadget is introduced to model flows in a higher 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 the capacity of an edge and a cut are generalized to define a flow problem. We show that in this flow graph, when the clique potentials are submodular, the max flow is equal to the min cut, which also is the optimal solution to the problem. We show experimentally that our algorithm provides significantly better solutions in practice and is hundreds of times faster than solution schemes like Dual Decomposition [1], TRWS [2] and Reduction [3], [4], [5]. The framework represents a significant advance in handling higher order problems making optimal inference practical for medium sized cliques.

Downloading PDF to your library...

Uploading PDF...

PDF uploading

Delete tag:

The link you entered does not seem to be valid

Please make sure the link points to contains a valid shared_access_token