MAP-MRF inference based on extended junction tree representation

Maximum a-posteriori (MAP) inference in Markov random fields (MRF) is an important topic in machine learning, computer vision and other fields. Message passing algorithms based on linear programming (LP) relaxation are powerful tools for the MAP-MRF problems. However, current message passing algorithms are usually based on simple subgraphs, resulting in slow convergence, local optimum and untightness of the LP relaxation for many problems. By extending the junction tree representation, we propose a general convergent message passing algorithm, which can work on arbitrary tractable bounded treewidth subgraphs. In the extended junction tree representation, the minimization and summation operators are commutable so that the proposed algorithm based on the extended junction tree is guaranteed to converge. Based on the treewidth-2 decomposition, better performance of the proposed algorithm is demonstrated on stereo matching, optical flow and panorama.