Markov Chain Monte Carlo for Computer Vision 
--- A tutorial at ICCV05 by Zhu, Delleart and Tu  
  Markov chain Monte Carlo is a general computing technique that has been widely used in physics,
chemistry, biology, statistics, and computer science. It simulates a Markov chain whose invariant
states follow a given (target) probability in a very high (say millions) dimensional state space.
Essentially, it generates fair samples from a probability which are used for many purposes.
A. System simulation. For many systems, their states are thought to follow some probability models.
       e.g. in statistical physics, the microscopic states of a system follows a Gibbs model given
       the macroscopic constraints. Sometimes, we have hard constraints and a uniform probability 
       on the set of valid states. The fair samples produced by MCMC will show us what states are
       typical of the underlying system. E.g. the typical protein folding under certain conditions.
       In computer vision, this is often called "synthesis" ---the visual apparance of the simulated 
       images, textures, and shapes is a way to verify the sufficiency of the underlying model. So 
       it also provides a tool for learning and model verification.
B. Scientific computing. In scientific computing, one often needs to compute the integral in very 
       high dimensional space. E.g. the expected (macroscopic) property of a system. This is often
       done by Monte Carlo integration, i.e. estimating the expectation by empirical (sample) mean. 
       Another interesting problem is approximate counting. E.g. how many non-self-intersecting paths
       are in a 2D n x n lattice? One may also estimate the value of pi if we can generate uniform
       samples in a unit square.
       In computer vision, Monte Carlo integration is used in learning and model estimation, and has
       also been used in motion tracking etc.

C. Optimization and Bayesian inference. The objective is to compute the global optimum of some 
       Bayesian posterior probability. In vision, a Bayesian posterior is often quite "peaky"
       or "very cold" if it is well formulated.  This is why human vision has only one or a few of
       interpretations (otherwise we are very confused). Thus simulating the posterior will yield
       the plausible visual interpretation of the image. Very often the MCMC needs to go with an
       simulated annealing procedure. 

In the following, we prepare 7 lectures that are most related to vision research. This is 
intended for a tutorial by Zhu, Tu and Delleart at ICCV05.
1. Introduction to Markov Chain Monte Carlo 
 (1) What is Markov chain Monte Carlo?
 (2) Why using MCMC?
 (3) Examples
 (4) Computing with two categories of models in vision:
 (5) Brief history of MCMC
2. MCMC Basics--Metropolis, Metropolis-Hastings, and Gibbs Sampling
 (1) Markov Chains
 (2) Inference and Estimation via Sampling
 (3) The Gibbs Sampler
 (4) Metropolis-Hastings
 (5) Metropolis and Gibbs (revisited)
3. A variety of tricks for MCMC design
 (1) Hit-and-run, random ray
 (2) Generalized Gibbs sampler
 (3) Simulated tempering
 (4) Data augmentation
 (5) Slice sampling
 (6) Cluster sampling
 (7) Metropolized Gibbs Sampler
4. Convergence and Exact sampling techniques  
 (1) Definitions and terminologies.
 (2) Exact sampling techniques
 (3) Convergence rate and bounds using eigen-based analysis.
 (4) First hitting time analysis: ways to analyze the proposals.
5. Trans-dimensional MCMC  
 (1) Model Selection
 (2) Reversible Jump MCMC
 (3) Regression Example
 (4) Rao-Blackwellized Sampling
 (5) Polygonal Random Fields
6. Cluster sampling with SW-cut
 (1) Graph partition and labeling
 (2) Clustering with bottom-up edge probabilities
 (3) Moving in the partition space
 (4) Swendsen-Wang Cuts
 (5) Examples
7. Data-driven MCMC: Integrating MCMC Search with Discriminative Computing
 (1) Generative and discriminative models
 (2) DDMCMC case study
 (3) DDMCMC approaches for vision applications 
 Some reference books:

  [1]. J.S. Liu, Monte Carlo Strategies in Scientific Computing, Springer, 2001.
  [2]. W. R. Gilks et al (eds) Markov Chain Monte Carlo in Practice, Chapman & Hall, 1996.     
  [3]. P. Bremaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, Springer, 1999