## Markov Random Fields

Hassner and Sklansky introduced Markov random fields to image analysis and throughout the last decade Markov random fields have been used extensively as representations of visual phenomena. A Gibbs random filed describes the global properties of an image in terms of the joint distributions of colors for all pixels. An MRF is defined in terms of local properties. Before we show the basic properties of MRF, we will show some definitions related to Gibbs and Markov random fields [10-15].

Definition 1: A clique A is a subset of S for which every pair of sites is a neighbor. Single pixels are also considered cliques. The set of all cliques on a grid is called A.

Definition 2: A random field X is an MRF with respect to the neighborhood system n = {ns, s e S} if and only if

• p(X = x) > 0 for all x e where ^ is the set of allpossible configurations on the given grid;

• p(Xs = xs|Xs|r = xs|r) = p(Xs = xs|Xds = xds), where s|r refers to all N2 sites excluding site r, and ds refer to the neighborhood of site s;

• p(Xs = xs|Xds = xds) is the same for all sites s.

The structure of the neighborhood system determines the order of the MRF. For a first-order MRF the neighborhood of a pixel consists of its four nearest neighbors. In a second-order MRF the neighborhood consists of the eight nearest neighbors. The cliques structure are illustrated in Figs 9.1 and 9.2.

Consider a graph (t, n) as shown in Fig. 9.3 having a set of N2 sites. The energy function for a pairwise interaction model can be written in the following form:

N2 N2 w

Figure 9.1: Cliques for a first-order neighborhood, where a, 91, and 02 are the cliques coefficients for first-order neighborhood system.