Approximate Inference: Decomposition Methods with Applications to Computer Vision Seminars/Workshops

Abstract

Markov Random Field (MRF) provides an elegant and succinct abstraction to capture inter-dependency between a large number of random variables - applications abound in signal processing, computer vision, statistical physics, combinatorics, biology, etc. In most of these applications, the key task pertains inferring the most likely assignment (aka MAP). This problem is computationally hard in general. Therefore, various approximations have been developed that utilize graph structures of the MRF for efficient computation. For example, popular approaches like Belief Propagation (and its variants) work well when the underlying graph has large girth.

In the application of MRF to computer vision, graphs do have lots of short cycles, but they naturally posses some "geometry". We develop a new class of approximation algorithms that utilize "geometry" of the underlying graph to obtain efficient approximation with provable guarantees for the MAP inference problem. In this talk, I will explain basic ideas of the MRF model, and describe our algorithm based on simple local updates, that runs in essentially linear time in the size of the MRF. I will then describe its applications to image denoising and image segmentation.