Analysis on tree structure selection for MRF inference in low-level vision

MRF inference on the 4-connected grid is popularly utilized for early vision tasks. But due to the loopy structure of the 4-connected grid, inference becomes complicated and less efficient. This paper present a theoretical analysis on what is an optimal spanning tree structure (loop-free) to approximate the 4-connected grid, to facilitate an efficient inference. We formulate our problem in statistical view: inference on an optimal tree structure should obtain a similar distribution to that of a 4-connected grid. To measure the similarity between two distributions, KL-divergence is chosen as a powerful tool. Due to the asymmetric nature of KL-divergence, the optimization can be approached from two directions. We analyze both the two directions and find they are equivalent to tree partition function lower bound and upper bound optimization respectively. Finally, we develop a tree selection algorithm based on the two bounds optimization and evaluate them on both image denoising and stereo matching tasks.