Efficient computation of MRF for low-level vision problems

Abstract

Low-level computer vision problems, such as image restoration, stereo matching and image segmentation, have been given sufficient attention by computer vision researchers. These problems, though appear to be distinct, share a common structure: given the observed image data, estimating an hidden label at each pixel position. Due to this similarity, one effective solution is to deal with the low-level vision problems by a unified approach: Markov Random Fields (MRFs) framework, which includes MRFs modeling and inference. To be specific, the relationship between observed image data and hidden labels are modeled by MRFs network, formulating a joint distribution. Inference allows to efficiently find a local optimum of the distribution and producing the estimation of underlying labels. We study how to efficiently solve low-level vision problems by MRFs framework. To achieve this target, we mainly focus on two aspects: (1) optimizing the MRFs structure; (2) improving the efficiency of inference. MRFs structures express how we describe the relationship between observed data and hidden labels, as well as the relationship among hidden label themselves. We aim to optimize the MRFs structure for fast inference. Besides the structure, there are two important terms used in inference, one is called data-term and another is called prior-term. In this work, we also study generating a reliable and robust data-term to increase the accuracy and efficiency of inference. In this thesis, a multi-spanning-tree decomposition work is firstly proposed. The traditional 4-connected MRF is broken down to a set of spanning trees, which are loopy-free. Edges in the original grid are uniformly distributed in these spanning trees. Using the multi-spanning-tree structure, inference can be performed fast and parallel; inference results can be combined by an efficient median filter. In the second place, a deeper analysis on spanning tree MRFs is proposed. Tree structure is popularly utilized for inference, but how to select an optimal spanning tree is widely overlooked by researchers. The problems are formulated as finding an optimal spanning tree to approximate 4-connected grid and solved by minimizing the KL-divergence between tree and grid distribution. It is also demonstrated that for different low-level vision problems, the selection criterion of optimal spanning trees are distinct. Besides the MRFs structure analysis, we also optimize the data-term generation process. This work is done specialized for image denoising. We use a non-local technique to create a reliable and low dimensional label space, generating the data-term. This data-term helps to provide comparable results with state-of-art algorithims in a quite limited time. To sum up, we efficiently solve low-level vision problems by MRFs inference. Although MRFs based low-level vision problems have been analyzed fora long time, there are still some interesting work being overlooked. After a careful scrutiny on the literature, we extend existing ideas and develop new algorithms, empirically demonstrate the MRFs computation can be improved both in timing and accuracy.