LP Relaxation Approach to MAP Inference in Markov Random Fields
Tomas Werner
Czech Technical University, Faculty of Electrical Engineering, Center
for Machine Perception
werner@cmp.felk.cvut.cz
In 2005, I reviewed the LP relaxation approach to MAPinference in
Markov random fields (also known as image energy minimization, weighted constraint satisfaction,
or maxsum 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
MEXfile. Compile the MEXes and run test.m.
The crucial articles cited in the review may be hardtoget:

M.I. Shlezinger.
Syntactic analysis of twodimensional visual signals in the
presence of noise. Cybernetics and Systems Analysis
12(4):612628, 1976. Springer, New York (English translation of USSR
journal "Kibernetika". Note that the name "Schlesinger" is transcripted as "Shlezinger" in the English translation.) A copy is also here.
This paper develops basic elements of MRFbased image analysis
(note, MRFs were not known in 1976) and LP relaxation approach to MRF
inference.

V.K. Koval and M.I. Schlesinger.
Dvumernoe programmirovanie v zadachakh analiza
izobrazheniy (Twodimensional programming in image analysis problems).
USSR Academy of Science, Automatics and Telemechanics,
8:149168, 1976. In Russian.
This paper develops the Augmenting DAG algorithm.

M.I. Schlesinger.
Matematicheskie sredstva obrabotki izobrazheniy
(Mathematical Tools of Image Processing).
Naukova Dumka, Kiev, 1989.
In Russian.

M.I. Schlesinger and B. Flach,
Some solvable subclasses of structural recognition problems,
Czech Pattern Recognition Workshop, 2000, invited paper.
This paper, besides other things, shows that LP relaxation (more
exactly, minimizing an upper bound by reparameterizations, called
'equivalent transformations') is tight for submodular problems (called
'monotone' there).

D. Schlesinger and B. Flach,
Transforming an arbitrary MinSum problem into a binary one,
Technical report TUDFI0601, Dresden University of Technology, April 2006.
This technical report shows (in particular) how a multilabel submodular energies can be
transformed to maximal flow problem.