Efficient image denoising by MRF approximation with uniform-sampled multi-spanning-tree

Traditionally, image processing based on Markov Random Field (MRF) is often addressed on a 4-connected grid graph defined on the image. This structure is not computationally efficient. In our work, we develop a multiple-trees structure to approximate the 4-connected grid. A set of spanning trees are generated by a new algorithm: re-weighted random walk (RWRW). This structure effectively covers the original grid and guarantees uniformly distributed occurrence of each edge. Exact maximum a posterior (MAP) inference is performed on each tree structure by dynamic programming and a median filter is chosen to merge the results together. As an important application, image denoising is used to validate our method. Experimentally, our algorithm provides better performance and higher computational efficiency than traditional methods (such as Loopy Belief Propagation) on a 4-connected MRF.