Next: The Labeling Problem Up: Visual Labeling Previous: Visual Labeling

1.1.1

## Sites and Labels

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.

Next: The Labeling Problem Up: Visual Labeling Previous: Visual Labeling