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.
(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.
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.