1.2.4

An MRF is characterized by its local property (the Markovianity)
whereas a GRF is characterized by its global property (the Gibbs
distribution). The Hammersley-Clifford theorem
[Hammersley and Clifford 1971]
establishes the equivalence of these two types of properties. The
theorem states that * F is an MRF on with respect to if
and only if F is a GRF on with respect to *. Many proofs of the theorem
exist,

A proof that a GRF is an MRF is given as follows. Let be a Gibbs distribution on with respect to the neighborhood system . Consider the conditional probability

where is any configuration
which agrees with **f** at all sites except possibly **i**. Writing
out
gives (This also provides a formula for calculating the conditional probability from potential functions.)

Divide into two set and with consisting of
cliques containing **i** and cliques not containing **i**. Then
the above can be written as

Because for any clique **c** that does not contain **i**,
cancels from both the numerator and
denominator. Therefore, this probability depends only on the potentials
of the cliques containing **i**,

that is, it depends on labels at **i**'s neighbors. This proves that a
Gibbs random field is a Markov random field. The proof that an MRF is a
GRF is much more involved; a result to be described in the next
subsection, which is about the unique GRF representation
[Griffeath 1976], provides such a proof.

The practical value of the theorem is that it provides a simple way of
specifying the joint probability. One can specify the joint probability
by specifying the clique potential functions and
chooses appropriate potential functions for desired system behavior. In
this way, he encodes the * a priori* knowledge or preference about
interactions between labels.

How to choose the forms and parameters of the potential functions for a proper encoding of constraints is a major topic in MRF modeling. The forms of the potential functions determine the form of the Gibbs distribution. When all the parameters involved in the potential functions are specified, the Gibbs distribution is completely defined. Defining the functional forms is the theme in Chapters 2 -- 5 while estimating parameters is the subject in Chapters 6 and 7.

To calculate the joint probability of an MRF, which is a Gibbs distribution, it is necessary to evaluate the partition function ( 1.25). Because it is the sum over a combinatorial number of configurations in , the computation is usually intractable. The explicit evaluation can be avoided in maximum-probability based MRF vision models when contains no unknown parameters, as we will see subsequently. However, this is not true when the parameter estimation is also a part of the problem. In the latter case, the energy function is also a function of parameters and so is the partition function . The evaluation of is required. To circumvent the formidable difficulty therein, the joint probability is often approximated in practice. Several approximate formulae will be introduced in Chapter 6 where the problem of MRF parameter estimation is the subject.