Graph-Based Simplex Method for Pairwise Energy Minimization With Binary Variables
We show how the simplex algorithm can be tailored to the linear programming relaxation of pairwise energy minimization with binary variables. A special structure formed by basic and nonbasic variables in each stage of the algorithm is identified and utilized to perform the whole iterative process combinatorially over the input energy minimization graph rather than algebraically over the simplex tableau. This leads to a new efficient solver. We demonstrate that for some computer vision instances it performs even better than methods reducing binary energy minimization to finding maximum flow in a network.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast Energy Minimization Using Learned State Filters
Pairwise discrete energies defined over graphs are ubiquitous in computer vision. Many algorithms have been proposed to minimize such energies, often concentrating on sparse graph topologies or specialized classes of pai…
Optimal Binary Autoencoding with Pairwise Correlations
We formulate learning of a binary autoencoder as a biconvex optimization problem which learns from the pairwise correlations between encoded and decoded bits. Among all possible algorithms that use this information, ours…
DecoderComplexity of Discrete Energy Minimization Problems
Discrete energy minimization is widely-used in computer vision and machine learning for problems such as MAP inference in graphical models. The problem, in general, is notoriously intractable, and finding the global opti…
Unbiased Shape Compactness for Segmentation
We propose to constrain segmentation functionals with a dimensionless, unbiased and position-independent shape compactness prior, which we solve efficiently with an alternating direction method of multipliers (ADMM). Inv…
SegmentationA Tiered Move-making Algorithm for General Non-submodular Pairwise Energies
A large number of problems in computer vision can be modelled as energy minimization problems in a Markov Random Field (MRF) or Conditional Random Field (CRF) framework. Graph-cuts based $\alpha$-expansion is a standard …
DenoisingImage DenoisingImage SegmentationImage Stitching+2