Tree-based iterated local search for Markov random fields with applications in image analysis

Truyen Tran, Dinh Phung, Svetha Venkatesh

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)


The maximum a posteriori assignment for general structure Markov random fields is computationally intractable. In this paper, we exploit tree-based methods to efficiently address this problem. Our novel method, named Tree-based Iterated Local Search (T-ILS), takes advantage of the tractability of tree-structures embedded within MRFs to derive strong local search in an ILS framework. The method efficiently explores exponentially large neighborhoods using a limited memory without any requirement on the cost functions. We evaluate the T-ILS on a simulated Ising model and two real-world vision problems: stereo matching and image denoising. Experimental results demonstrate that our methods are competitive against state-of-the-art rivals with significant computational gain.

Original languageEnglish
Pages (from-to)25-45
Number of pages21
JournalJournal of Heuristics
Issue number1
Publication statusPublished - Feb 2015
Externally publishedYes


  • Belief propagation
  • Iterated local search
  • MAP assignment
  • Markov random fields
  • Strong local search

Cite this