LP Relaxation Approach to MAP Inference in Markov Random Fields

Tomas Werner
Czech Technical University, Faculty of Electrical Engineering, Center for Machine Perception

In 2005, I reviewed the LP relaxation approach to MAP-inference in Markov random fields (also known as image energy minimization, weighted constraint satisfaction, or max-sum labeling problem) developed by Schlesinger et al in 1970's. A long version of the review is in the research report, a reduced and improved version is in the PAMI article.

I implemented the Augmenting DAG algorithm, described in the report. Here is the code, encapsulated in MATLAB MEX-file. Compile the MEXes and run test.m.

The crucial articles cited in the review may be hard-to-get: