Maximum Persistency in Energy Minimization
Overview

The figure below illustrates the progress of partial optimality methods. Graph cut -based methods are fast but fail to provide partial optimality for finer graphical models. LP-based methods are more powerfull but take excessive time to compute, until this new approach [1a], illustrated in the video.
Graphical Comparison of Persistency Methods

Key features of our approach:
  • Output is an approximate solution by (speeded-up) TRW-S plus optimality guarantee for a part of this solution.
  • Invariant to reparametrization and order of labels.
  • Closely approximates maximum persistency LP (evaluated on small random problems).
Software (For Pairwise Models)

Current version is 1.2
The source code is available on GitLab: https://gitlab.icg.tugraz.at/shekhovt/part_opt  
OpenGM Interface Fork: https://github.com/pawelswoboda/opengm/tree/partialOptimality
Prebuilt mex files for Win32/Win64: part_opt_mex.zip
I can take now bug fixes on GitLab. Our OpenGM Fork unfortunatelly has not yet been merged to the master. The standalone interface can yet be improved, I am open to collaboration.
LICENSE
 This software can be used under GPL license. If you seek its use in  a commercial product, please contact  shekhovtsov@icg.tugraz.at
Compilation

Win32/64 (MSVC) / Mac / Linux

Configure with cmake-gui the project part_opt/CmakeLists.txt

Standalone Build
A version of Maxflow and QPBO code is included. Available executable:
    bin/test_random

OpenGM Build (WITH_OPENGM)
External dependencies: OpenGM (headers only, need not build), HDF5. If you plan to use Matlab mexes too, it is recommended to build HDF5 as a static library, since Matlab loads a different version of its dynamic library.
Available executable:
    bin/test_part_opt_opengm

Matlab Build (WITH_MATLAB)
Hopefully the scipt works and locates matlab for you (Check it's got the right 32/64 bit version). If not, specify in MATLAB_ROOT_DIR_ the path to matlab executable, remove all other variables with incorrectly found matlab components (Remove Entry button)  and re-configure.
Available mexes:

  • matlab/part_opt/opengm_read_mex
  • matlab/part_opt/opengm_write_mex
  • matlab/part_opt/part_opt_DEE_mex (Dead End Elimination)
  • matlab/part_opt/part_opt_DEE2_mex (Dead End Elimination on pairs)
  • matlab/part_opt/part_opt_IK_mex (Kovtun's method)
  • matlab/part_opt/part_opt_MQPBO_mex (Reduction to QPBO(-P) , see Kohli et al. [3])
  • matlab/part_opt/part_opt_TRWS_mex (Our new method)

Testing

bin/test_random -- just to test it executes on a random problem
bin/test_part_opt_openmgm -- ruth the method on a model in OpenGM format
Parameters:
This method takes parameters like this:
bin/test_part_opt_openmgm model_name.h5 data/pfau-small.h5 max_CPU=2 max_it=200
All parameters are printed when the method is started. 
Environment Variables:
For this implementation with OpenMP, its environment variables affect the performance, recommended setting is:
export OMP_PROC_BIND=true
Matlab:
Linux: If you are getting an error "Invalid mex file", "libstdc++.so.6: version `GLIBCXX_3.4.11' not found ", check out this reference: http://stackoverflow.com/questions/25929332/version-glibcxx-3-4-11-not-found-required-by-buildw-mexglx
Recommended solution is to start matlab like this:
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libstdc++.so.6 HDF5_DISABLE_VERSION_CHECK=1 matlab
export OMP_PROC_BIND=true
Matlab Examples
Can be found in matlab/part_opt/examples/example1-3. They are documented, should be realy easy to try it out.
Further Documentation

Matlab
See examples and doc on the functions
C++
I hope I will improve on this. At the moment, the following examples should be a reasonable starting point
code/optim/part_opt/test_random.cpp
code/optim/part_opt/test_part_opt_opengm.cpp
A better integration with OpenGM is also in progress.
Higher Order Maximum Persistency

This is more a research implementation in matlab described in [1b] for higher order pseudo-Boolean case and the associated evaluation code on random instances.
Download ho_persistency.zip
It is in MATLAB and uses CPLEX. It is meant for reproducibility of results and for further research.
Execution of methods HOCR, Fix and GRD* is provided by the submodular library v.1.0 by P. Strandmark and dependencies thereof, see https://github.com/PetterS/submodular.
Compilation
Install IBM ILOG Optimization Studio (see this page for academic usage). Add path to cplex/matlab/your_platform.
 Download (and of course compile) submodular library https://github.com/PetterS/submodular, follow the instructions in there to obtain third party dependencies. Add path to /submodular/matlab.
Testing
The script part_opt/ho_test.m reproduces experiments in the paper. Follow the comments in there.
part_opt/ho_plotsg.m creates group plots as in the paper.
Publications

[1a] A. Shekhovtsov, P. Swoboda and B. Savchynskyy: Maximum Persistency via Iterative Relaxed Inference with Graphical Models, CVPR 2015 [pdf] [bib]
A new improved version is now available on arXiv
[1b] A. Shekhovtsov: Higher order Maximum Persistency and Comparison Theorems, CVIU SI: Graphical Models Inference & Learning. Under review. [pdf], [bib], [ArXiv e-print], 
[6] A. Shekhovtsov. Maximum persistency in energy minimization. In CVPR, 2014. [pdf] [bib]
[7] P.Swoboda, A. Shekhovtsov, J.H. Kappes, C. Schnörr, and B. Savchynskyy. Partial optimality by pruning for MAP-inference with general graphical models. Oct 2014. [ArXiv e-print]

References

[1] OpenGM benchmark.
[2] Karteek Alahari, Pushmeet Kohli, and Philip H. S. Torr. Reduce, reuse & recycle: Efficiently solving multi-label MRFs. In CVPR, 2008.
[3] P. Kohli, A. Shekhovtsov, C. Rother, V. Kolmogorov, and P. Torr. On partial optimality in multi-label MRFs. In ICML, 2008.
[4] V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. PAMI, 28(10), 2006.
[5] I. Kovtun. Partial optimal labeling search for a NP-hard subclass of (max, +) problems. In DAGM-Symposium.
[8] Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall Tappen, and Carsten
Rother. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors.