1.1.1

A * labeling problem* is specified in terms
of a set of * sites* and a set of * labels*. Let index a
discrete set of **m** sites

in which are indices. A site often represents a point
or a region in the Euclidean space such as an image pixel or an image
feature such as a corner point, a line segment or a surface patch. A set
of sites may be categorized in terms of their ``regularity''.
Sites on a lattice are considered as
spatially * regular*. A rectangular lattice for a 2D image
of size can be denoted by

Its elements correspond to the locations at which an image is sampled.
Sites which do not present spatial regularity are considered as *
irregular*. This is the usual case corresponding to features extracted
from images at a more abstract level, such as the detected corners and
lines.

We normally treat the sites in MRF models as un-ordered.
For an image, pixel can be
conveniently re-indexed by a single number **k** where **k** takes on values
in with .
This notation of single-number
site index will be used in this book even for images unless an
elaboration is necessary. The inter-relationship between sites is
maintained by a so-called * neighborhood system* (to be introduced later).

A label is an event that may happen to a site. Let be a set
of
* labels*. A label set may be categorized as being continuous or
discrete. In the continuous case, a
label set may correspond to the real line or a compact
interval of it

An example is the dynamic range for an analog pixel intensity. It is
also possible that a continuous label takes a vector or matrix value,
for example, where **a** and **b** are dimensions.

In the discrete case, a label assumes a discrete value in a set of **M**
labels

or simply

In edge detection, for example, the label set is {edge,non-edge}.

Besides the continuity, another essential property of a label set is the ordering of the labels. For example, elements in the continuous label set (the real space) can be ordered by the relation ``smaller than''. When a discrete set, say , represents the quantized values of intensities, it is an ordered set because for intensity values we have . When it denotes 256 different symbols such as texture types, it is considered to be un-ordered unless an artificial ordering is imposed.

For an ordered label set, a numerical (quantitative) measure of similarity between any two labels can usually be defined. For an unordered label set, a similarity measure is symbolic (qualitative), typically taking a value on ``equal'' or ``non-equal''. Label ordering and similarity not only categorize labeling problems but more importantly, affect our choices of labeling algorithms and hence the computational complexity.