Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 8

Image de-noising with a Markov random field

A binary image x (pixels ±1) is observed as y with every pixel flipped independently with a small probability. The Ising model links each pixel to its four neighbours and to its observed value through the energy E(x, y) = h Σ_i x_i − β Σ_i~j x_ix_j − η Σ_i x_iy_i, and p(x | y) ∝ exp(−E). ICM (iterated conditional modes) visits the pixels in raster order and gives each the sign of lower energy, so the energy can only go down, but it stops at a local minimum. Gibbs sampling draws each pixel from its conditional instead. The lower right panel is the exact most probable image, found by a minimum graph cut.

Algorithm

Sweeps

show the average of the Gibbs samples

Energy parameters

Noise: flip probability

Try these

The image (150 × 200 pixels) is our own: the words “Graphical models” in a box, the same as in Figure 8.30 of the Python code. Book: β = 1.0, η = 2.1, h = 0, 10% noise. The graph cut is the exact minimiser of the energy (Greig, Porteous and Seheult 1989): it is recomputed whenever the parameters or the noise change.

In the lecture notes

Chapter 8 notes: Section 8.3 (Markov random fields), Section 8.3.2 (factorisation, potentials as exp(−energy)), Section 8.3.3 (image de-noising: the energy (8.42), ICM and graph cuts, Figure 8.30).
Exact maximisation on trees instead of local moves: the companion demo belief propagation: sum-product and max-sum.
Python code: code/ch08_graphical_models.py (functions ising_energy, icm, gibbs_ising, graph_cut_map, make_binary_image; Figure 8.30) and the checks in code/checks_ch08.py (ICM never raises the energy; the graph cut equals the brute-force minimum on small images).