Markov Random Field Models
163
in the context of image processing. In 1902, Gibbs introduced the following
probability distribution,
rrT(x) = _1 exp {-~E(X)}
ZT
T
(6.4)
on the configuration space AS, where T > 0 is the temperature, E(x) is the
energy of the configuration x, and ZT is the normalizing constant, or the
partition function. Obviously, E(x) can take values in (-00,00) since rrT(x) E
[0, 1]. Generally, the energy function E(x) describes local interactions in terms
of a potential function which is defined over cliques.
6.2.2.1
Clique
Any singleton {5} is a clique. A subset C C -8 with more than one element is
called a clique of the graph (-8, N) if and only if any two distinct sites of Care
mutual neighbors. A clique C is called maximal iffor any site 5, C U {5} is not
a clique.
For the sake of clarification, we provide examples of cliques for two neighborhood systems: 4-neighborhood (Fig. 6.1a) and 8-neighborhood (Fig. 6.1b).
The three cliques for the 4-neighborhood system as shown in Fig. 6.1a are:
the singleton, the horizontal pair and the vertical pair. Similarly, there are ten
cliques for the 8-neighborhood system: one singleton, pixel pairs with different
orientations, various combinations of three pixels and the group of four pixels
(see Fig. 6.1b). In this example, cliques C2 and C3 are the maximal cliques for
the 4-neighborhood system, and the clique CIO is the maximal clique for the
8-neighborhood system.
6.2.2.2
Gibbs Potential and Gibbs Distribution
A Gibbs potential on A -8 relative to the neighborhood system N is a collection
{Vc}CC-8 of a function Vc : A -8 ---+ lR. U {+oo} such that
i) V c == 0 if C is not a clique,
ii) for all x,x E A -8 and all C C -8,
(x(C) = x'(C)) => (Vdx) = Vdx')) ,
(6.5)
where lR. is the set of all real numbers.
Hence, the energy function E : A -8 ---+ lR. U {+oo} is said to derive from the
potential {Vclc C -8 if
E(x) = L Vdx).
c
(6.6)