Inference in Higher Order MRF-MAP Problems With Small and Large Cliques
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Semantic SegmentationSimilar Papers 제목 키워드 기반
Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
This paper introduces an efficient approach to integrating non-local statistics into the higher-order Markov Random Fields (MRFs) framework. Motivated by the observation that many non-local statistics (e.g., shape priors…
Image SegmentationSemantic SegmentationMin Norm Point Algorithm for Higher Order MRF-MAP Inference
Many tasks in computer vision and machine learning can be modelled as the inference problems in an MRF-MAP formulation and can be reduced to minimizing a submodular function. Using higher order clique potentials to mode…
A Higher-Order Semantic Dependency Parser
Higher-order features bring significant accuracy gains in semantic dependency parsing. However, modeling higher-order features with exact inference is NP-hard. Graph neural networks (GNNs) have been demonstrated to be an…
Dependency ParsingGraph LearningSemantic Dependency ParsingBias-Variance Trade-Off in Hierarchical Probabilistic Models Using Higher-Order Feature Interactions
Hierarchical probabilistic models are able to use a large number of parameters to create a model with a high representation power. However, it is well known that increasing the number of parameters also increases the com…
Fast Approximate Inference in Higher Order MRF-MAP Labeling Problems
Use of higher order clique potentials for modeling inference problems has exploded in last few years. The algorithmic schemes proposed so far do not scale well with increasing clique size, thus limiting their use to cliq…