Maximum Persistency in Energy Minimization


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:  
OpenGM Interface Fork:
Prebuilt mex files for Win32/Win64:
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.
 This software can be used under GPL license. If you seek its use in  a commercial product, please contact

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:

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:

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)


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
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
Linux: If you are getting an error "Invalid mex file", " version `GLIBCXX_3.4.11' not found ", check out this reference:
Recommended solution is to start matlab like this:
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/ 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

See examples and doc on the functions
I hope I will improve on this. At the moment, the following examples should be a reasonable starting point
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.

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

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, follow the instructions in there to obtain third party dependencies. Add path to /submodular/matlab.
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.


[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]


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