An implementation of the "MP-BCFW" algorithm described in
A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle.
Neel Shah, Vladimir Kolmogorov and Christoph H. Lampert.
In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
SRMP generalizes TRW-S to higher-order graphical models.
For pairwise graphical models the original implementation of TRW-S should be faster
(e.g. by a factor of 3 for the case of two labels, in one informal test). For a larger number
of labels the difference should be smaller: the runtime would be dominated by distance transform operations
whose implementations are similar.
Potts model, parametric maxflow and k-submodular functions.
Igor Gridchyn and Vladimir Kolmogorov. In International Conference on Computer Vision (ICCV), December 2013.
An implementation of a minimum cost perfect matching algorithm described in
Blossom V: A new implementation of a minimum cost perfect matching algorithm.
Vladimir Kolmogorov.
In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
(The experiments in the paper were performed using version 1.0.
A description of changes is here.)
The code can also be used for computing a maximum (non-perfect) matching: the latter problem can be reduced to a perfect matching problem via a reduction described in section
1.5.1 of Guido Schäfer's Master's thesis. This reduction doubles the size of the graph.
The code above is licensed for research purposes only. Commercial licensing of Blossom V is available through the UCL Business e-licensing website.
An implementation of a dual decomposition technique for the graph matching optimization problem described in
Feature Correspondence via Graph Matching: Models and Global Optimization.
Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother. In European Conference on Computer Vision (ECCV), October 2008.
An implementation of the maxflow algorithm described in
An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision.
Yuri Boykov and Vladimir Kolmogorov.
In IEEE Transactions on Pattern Analysis and Machine Intelligence, September 2004.
Note that all experimental results reported in the paper are based on
original implementation of our algorithm that we developed while
at Siemens Corp. Research (Princeton, NJ). We are not allowed to distribute
that version. Below is a comparable version that I later
independently re-implemented based on published materials.
Implements algorithms for minimizing functions of binary variables
with unary and pairwise terms based on roof duality described in the following papers:
Roof duality, complementation and persistency in quadratic 0-1 optimization.
P. L. Hammer, P. Hansen, and B. Simeone. Mathematical Programming, 28:121-155, 1984.
Network flows and minimization of quadratic pseudo-Boolean functions.
E. Boros, P. L. Hammer, and X. Sun. Technical Report RRR 17-1991, RUTCOR Research Report, May 1991.
Preprocessing of Unconstrained Quadratic Binary Optimization.
E. Boros, P. L. Hammer, and G. Tavares. Technical Report RRR 10-2006, RUTCOR Research Report, April 2006.
Optimizing binary MRFs via extended roof duality.
C. Rother, V. Kolmogorov, V. Lempitsky, and M. Szummer. CVPR 2007.
An implementation of the primal-dual method for the dual of the convex network flow problem ("Convex Markov Random Fields") described in
New Algorithms for the Dual of the Convex Cost Network Flow Problem with Application to Computer Vision.
Vladimir Kolmogorov and Akiyoshi Shioura. Technical Report, June 2007.
An implementation of the three stereo algorithms described in the papers
Multi-camera Scene Reconstruction via Graph Cuts.
VLadimir Kolmogorov and Ramin Zabih.
In European Conference on Computer Vision, May 2002 (best paper award).
Computing Visual Correspondence with Occlusions using Graph Cuts.
Vladimir Kolmogorov and Ramin Zabih.
In International Conference on Computer Vision, July 2001.
and
Markov Random Fields with Efficient Approximations.
Yuri Boykov, Olga Veksler and Ramin Zabih.
In Computer Vision and Pattern Recognition Conference, June 1998.
Tested under windows, Visual C++ 6.0 compiler
and unix (SunOS 5.8 and RedHat Linux 7.0, GNU c++ compiler).
