Philip H. S. Torr
Professor in Vision and Machine Learning
Head Computer Vision Group
Department of Computing,
Oxford Brookes University,
Oxford, U.K.
philiptorr@brookes.ac.uk

This tutorial will give a description of Markov Random Fields (MRFs)
and their applications to image and video editing and segmentation,
recovery of dense stereo, texture synthesis and object recognition.

The tutorial will assume no prior knowledge and will introduce the
concept of MRFs from a Bayesian perspective. For each of the above
applications the formulation of the Markov random field will be
described. The main focus of the tutorial will be on state of the art
methods for estimating MRFs; in contrast to the rather inefficient
"old style" stochastic methods characterized by simulated annealing a
new class of deterministic methods has recently provided effective
estimators, amongst these are graph cuts, and loopy belief
propagation. These deterministic algorithms will be described in
detail. A breakdown of the course is as follows:

1. Introduction, Bayesian methods in vision, pros and cons.

2. Shortest paths, dynamic programming (borrowing from the material of
the ICCV tutorial I did with Yuri Boykov and Ramin Zabih). This part
will discuss the relationship between the Bayesian method, dynamic
programming (DP), shortest path and hidden markov models,

(a) Solution for snakes Amini, Weymouth, Jain, Using DP for Solving
Variational Problems in Vision, PAMI 1990

(b) DP in vision: Scan-line stereo, Ohta & Kanade, 1985 Cox,
Hingorani, Rao, 1996.

(c) Object extraction live-wire [Falcao, Udupa, Samarasekera, Sharma
1998] intelligent scissors [Mortensen, Barrett 1998]

(d) Texture Synthesis Efros & Freeman, 2001

3. Markov Chains, and HMM, This part will discuss the relationship
between the Bayesian method, dynamic programming (DP), shortest path
and hidden markov models, covering:

(a) inference: - MAP by Dynamic Programming, Forward and
Forward-Backward (FB) algorithms;

(b) learning: by EM and Baum-Welch;

(c) representations: pixels, patches

(d) applications: stereo vision

4. Introduction to MRFs, formulation in various problems

(a) segmentation,

(b) object extraction,

(c) stereo, motion,

(d) image restoration,

(e) pattern recognition,

(f) shape reconstruction,

(g) object matching/recognition,

(h) augmented reality,

(i) texture synthesis,

5. MRFs how to optimize them

(a) Inference: within this section I will also discuss some of my own
recent contribution to this field

i. ICM,

ii. Loopy Belief Propagation (BP),

iii. Generalised BP,

iv. Graph Cuts;

(b) Parameter learning: Pseudolikelihood maximization;

(c) representations: color pixels, patches

(d) and furthermore: Gibbs sampling, Discriminative Random Field (DRF)