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.
