Abstract
Higher Order MRF-MAP formulation has been a popular technique for solving many problems in computer vision.
Inference in a general MRF-MAP problem is NP Hard,
but can be performed in polynomial time for the special
case when potential functions are submodular. Two popular combinatorial approaches for solving such formulations
are flow based and polyhedral approaches. Flow based approaches work well with small cliques and in that mode can
handle problems with millions of variables. Polyhedral approaches can handle large cliques but in small numbers. We
show in this paper that the variables in these seemingly disparate techniques can be mapped to each other. This allows
us to combine the two styles in a joint framework exploiting the strength of both of them. Using the proposed joint
framework, we are able to perform tractable inference in
MRF-MAP problems with millions of variables and a mix
of small and large cliques, a formulation which can not be
solved by either of the two styles individually. We show applicability of this hybrid framework on object segmentation
problem as an example of a situation where quality of results is significantly better than systems which are based
only on the use of small or large cliques