An implementation of the algorithm described in
Potts model, parametric maxflow and k-submodular functions.
Igor Gridchyn and Vladimir Kolmogorov.
In International Conference on Computer Vision (ICCV), December 2013.
2. BLOSSOM V
An implementation of a minimum cost perfect matching algorithm described in
Blossom V: A new implementation of a minimum cost perfect matching algorithm.
In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
(The experiments in the paper were performed using
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.
3. GRAPH MATCHING
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.
Old version 2.21 is still
Commercial licensing of MaxFlow (vsn 2.21) is available through the UCL Business e-licensing website.
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.
Note, version 1.2 had a bug: MergeParallelEdges() followed by Probe() could crash.
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, Ramin Zabih and Steven Gortler.
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.
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).
(NEW: an option of truncated linear smoothness term instead of Potts has been added).