next up previous index
Next: Markov Random Fields Up: Markov Random Fields Previous: Markov Random Fields


Neighborhood System and Cliques

The sites in are related to one another via a neighborhood system.   A neighborhood system for is defined as

where is the set of sites neighboring i. The neighboring relationship has the following properties:

(1) a site is not neighboring to itself: ;
(2) the neighboring relationship is mutual: .

For a regular lattice , the neighboring set of i is defined as the set of nearby sites within a radius of r  


where denotes the Euclidean distance between A and B and r takes an integer value. Note that sites at or near the boundaries have fewer neighbors.

Figure 1.2: Neighborhood and cliques on a lattice of regular sites.

In the first order neighborhood system, also called the 4-neighborhood system,     every (interior) site has four neighbors, as shown in Fig.1.2(a) where x denotes the considered site and 0's its neighbors. In the second order neighborhood system, also called the 8-neighborhood system,   there are eight neighbors for every (interior) site, as shown in Fig.1.2(b). The numbers shown in Fig.1.2(c) indicate the outermost neighboring sites in the n-th order neighborhood system.   The shape of a neighbor set   may be described as the hull enclosing all the sites in the set.

When the ordering of the elements in is specified, the neighbor set can be determined more explicitly. For example, when is an ordered set of sites and its elements index the pixels of a 1D image, an interior site has two nearest neighbors, , and a site at the boundaries (the two ends) has one neighbor each,   and . When the sites in a regular rectangular lattice correspond to the pixels of an image in the 2D plane, an internal site has four nearest neighbors as , a site at a boundary has three and a site at the corners has two.

Figure 1.3: Neighborhood and cliques on a set of irregular sites.

For an irregular , the neighbor set of i is defined in the same way as (1.13) to comprise nearby sites within a radius of r


The dist function needs to be defined appropriately for non-point features. Alternatively, the neighborhood may be defined by the Delaunay triangulation,(Algorithms for constructing a Delaunary triangulation in higher dimensional space can be found in [Bowyer 1981 ; Watson 1981]) or its dual, the Voronoi polygons, of the sites [Besag 1975]. In general, the neighbor sets for an irregular have varying shapes and sizes. Irregular sites and their neighborhoods are illustrated in Fig.1.3(a). The neighborhood areas for sites i and j are marked by the dotted circles. The sizes of the two neighbor sets are and .

The pair constitutes a graph in the usual sense where contains the nodes and determines the links between the notes according to the neighboring relationship. A clique   c for is defined as a subset of sites in . It consists either of a single site , or of a pair of neighboring sites , or of a triple of neighboring sites , and so on. The collections of single-site, pair-site and triple-site cliques will be denoted by , and , respectively, where





Note that the sites in a clique are ordered, and is not the same clique as , and so on. The collection of all cliques for is

where "..." denotes possible sets of larger cliques.

The type of a clique   for of a regular lattice is determined by its size, shape and orientation. Fig.1.2(d)-(h) show clique types for the first and second order neighborhood systems for a lattice.  The single-site and horizontal and vertical pair-site cliques in (d) and (e) are all those for the first order neighborhood system (a). The clique types for the second order neighborhood system (b) include not only those in (d) and (e) but also diagonal pair-site cliques (f) and triple-site (g) and quadruple-site (h) cliques. As the order of the neighborhood system increases, the number of cliques grow rapidly and so the involved computational expenses.

Cliques for irregular sites   do not have fixed shapes as those for a regular lattice. Therefore, their types are essentially depicted by the number of involved sites. Consider the four sites f, i, m and n within the circle in Fig.1.3(a) in which m and n are supposed to be neighbors to each other and so are n and f. Then the single-site, pair-site and triple-site cliques associated with this set of sites are shown in Fig.1.3(b).     The set does not form a clique because f and m are not neighbors.

next up previous index
Next: Markov Random Fields Up: Markov Random Fields Previous: Markov Random Fields