LP Relaxation Approach to MAP Inference in Markov Random Fields
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
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:
Syntactic analysis of two-dimensional visual signals in the
presence of noise. Cybernetics and Systems Analysis
12(4):612-628, 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 MRF-based image analysis
(note, MRFs were not known in 1976) and LP relaxation approach to MRF
V.K. Koval and M.I. Schlesinger.
Dvumernoe programmirovanie v zadachakh analiza
izobrazheniy (Two-dimensional programming in image analysis problems).
USSR Academy of Science, Automatics and Telemechanics,
8:149--168, 1976. In Russian.
This paper develops the Augmenting DAG algorithm.
Matematicheskie sredstva obrabotki izobrazheniy
(Mathematical Tools of Image Processing).
Naukova Dumka, Kiev, 1989.
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
D. Schlesinger and B. Flach,
Transforming an arbitrary MinSum problem into a binary one,
Technical report TUD-FI06-01, Dresden University of Technology, April 2006.
This technical report shows (in particular) how a multilabel submodular energies can be
transformed to maximal flow problem.