Max-Sum (Labeling) Problem Page

Tomas Werner
Czech Technical University, Faculty of Electrical Engineering, Center for Machine Perception
werner@cmp.felk.cvut.cz

I have reviewed the not-widely known approach to the max-sum labeling problem (also known as the weighted constraint satisfaction problem, or MAP inference in Markov random fields) due to Schlesinger et al. The extended version of the review is in the research report, the reduced and improved version is in the PAMI article. There are also slides.

Some articles cited in the report:

M.I. Schlesinger. Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (Syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika, 4:113--130, 1976. In Russian. [DJVU]
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. [DJVU]
M.I. Schlesinger. Matematicheskie sredstva obrabotki izobrazheniy (Mathematical Tools of Image Processing). Naukova Dumka, Kiev, 1989. In Russian. [PDF, 47MB]
M.I. Schlesinger and B. Flach, Some solvable subclasses of structural recognition problems, Czech Pattern Recognition Workshop, 2000, invited paper. [PDF]
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. [PDF]

This code (encapsulated in MATLAB MEX-file) implements the Augmenting DAG algorithm for minimizing the upper bound on a max-sum problem, described in the report. Compile the MEXes and run test.m.

Here are two contributions to max-sum diffusion (described in the above survey): CVWW (the original paper contained two typos, this version has been corrected) and ICML.