Abstract
This article presents a mathematical paradigm called Data Driven Markov Chain Monte Carlo (DDMCMC) for effective stochastic inference in the Bayesian framework. We apply the DDMCMC paradigm to two typical problems in image analysis: object recognition and image segmentation. In both problems, the solution spaces are not only high dimensional but heterogeneously-structured in the sense that they are composed of many subspaces of varying dimensions. Each of the subspace is product of what we called the object spaces. The latter is further decomposed into the so-called atomic spaces. The DDMCMC paradigm simulates Markov chains for exploring the solution spaces using both jump and diffusion dynamics. Unlike traditional MCMC algorithms, the DDMCMC paradigm utilizes data driven (or bottom-up) techniques, such as Hough transform, edge detection, and color clustering, to design effective transition probabilities for Markov chain dynamics. This drastically improves the effectiveness of traditional MCMC algorithms in terms of two standard metrics: 'burn-in' period and 'mixing' rate. The article proceeds in three steps. Firstly, we analyze the structures of the solution space (Omega) for the two tasks. Secondly, we study how data-driven techniques are utilized to compute importance proposal probabilities in the solution spaces, the object spaces and atomic spaces. These proposal probabilities are expressed in non-parametric form using weighted samples or particles. Thirdly, we design Markov chains to travel in such heterogeneous structured solution space as an ergodic and reversible process. The paper first review the DDMCMC theory using a simple object recognition problem -- the (psi) -- world reported in [14], then we briefly introduce the results on image segmentation.
