Memory Efficient Max Flow for Multi-label Submodular MRFs

2017-02-20 · CVPR 2016 6 · Thalaiyasingam Ajanthan, Richard Hartley, Mathieu Salzmann

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable $X_i$ is represented by $\ell$ nodes (where $\ell$ is the number of labels) arranged in a column. However, this method in general requires $2\,\ell^2$ edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.

📄 PDF Abstract BibTeX arXiv:1702.05888

Code (1)

tajanthan/memf 공식 구현

GRSA: Generalized Range Swap Algorithm for the Efficient Optimization of MRFs

2015-06-01 · CVPR 2015 6 · Kangwei Liu, Junge Zhang, Peipei Yang, Kaiqi Huang

Markov Random Field (MRF) is an important tool and has been widely used in many vision tasks. Thus, the optimization of MRFs is a problem of fundamental importance. Recently, Veskler and Kumar et. al propose the range mo…

On MAP Inference by MWSS on Perfect Graphs

2013-09-26 · Adrian Weller, Tony S. Jebara

Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a maximum weight stable set (MWSS) on a derived weighted…

ESSP: An Efficient Approach to Minimizing Dense and Nonsubmodular Energy Functions

2014-05-19 · Wei Feng, Jiaya Jia, Zhi-Qiang Liu

Many recent advances in computer vision have demonstrated the impressive power of dense and nonsubmodular energy functions in solving visual labeling problems. However, minimizing such energies is challenging. None of ex…

A Primal-Dual Algorithm for Higher-Order Multilabel Markov Random Fields

2014-06-01 · CVPR 2014 6 · Alexander Fix, Chen Wang, Ramin Zabih

Graph cuts method such as a-expansion [4] and fusion moves [22] have been successful at solving many optimization problems in computer vision. Higher-order Markov Random Fields (MRF's), which are important for numerous a…

Denoising

From MAP to Marginals: Variational Inference in Bayesian Submodular Models

2014-12-01 · NeurIPS 2014 12 · Josip Djolonga, Andreas Krause

Submodular optimization has found many applications in machine learning and beyond. We carry out the first systematic investigation of inference in probabilistic models defined through submodular functions, generalizing …

Point Processes Variational Inference