5
$\begingroup$

I have a multilabel MRF MAP inference problem (a labeling problem). The graph has relatively few nodes, about a thousand or so. The pairwise term is (very) not submodular (it does not satisfy the triangle inequality). GraphCut with truncation does not work as about 40% of the entries are not submodular. What is the state of the art for this type of problem? Loopy Belief Propagation (BP), Tree Reweighted Message Passing (TRW-S), Quadratic Pseudo-Boolean Optimization (QPBO), Iterated Conditional Modes (ICM)?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Although it may not be state of the art anymore (2006), the paper "Szeliski, et al.: A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors" (the results are also available at http://vision.middlebury.edu/MRF) has a comparison on ICM, graph cuts, BP, TRW-S on various computer-vision related problems. In their results, ICM is really bad while TRW-S seems to be doing very well and should also be able to handle non-submodular terms.

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to the site, @jakub. CV has several goals, 1 of which is to develop a permanent repository of actionable info, & 1 concern re that is linkrot. In that light, can you give an overview of the info at the linked site? Since you're new here, you may also want to read our FAQ, which discusses these issues among other aspects of CV. $\endgroup$ Oct 23, 2012 at 14:30
  • $\begingroup$ Edited, added more info about the link. $\endgroup$
    – jakub
    Oct 25, 2012 at 13:49
3
$\begingroup$

Dual decomposition does general MAP inference in graphical models well. It has much nicer failure modes than loopy belief propagation. When dual decomposition doesn't find the optimal answer, it still produces a certificate bounding the best result. Often, it does converge to the right answer and it produces a certificate of optimality.

This is a reasonable introduction to dual decomposition for inference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.