1.1.2

The labeling problem is to assign a label from the label set to each of the sites in . Edge detection in an image, for example, is to assign a label from the set {edge,non-edge} to site where elements in index the image pixels. The set

is called a * labeling* of the sites in
in terms of the labels in . When each site is assigned a
unique label, can be regarded as a function with domain
and image . Because the support of the function is the whole domain
, it is a * mapping* from
to , that is,

Mappings with continuous and discrete label sets are demonstrated in
Figure 1.1. A labeling is also called a *
coloring* in mathematical programming.

In the terminology of random fields (* cf. *
Section 1.2.2), a labeling is called a * configuration*.
In vision, a configuration or labeling can
correspond to an image, an edge map, an interpretation of image features
in terms of object features, or a pose transformation, and so on.

When all the sites have the same label set , the set of all possible labelings, that is, the configuration space, is the following Cartesian product

where **m** is the size of . In image restoration, for example,
contains admissible pixel values which are common to all pixel
sites in and defines all admissible images. When
is the real line, is the **m** dimensional
real space. When is a discrete set, the size of is
combinatorial. For a problem with
**m** sites and **M** labels, for example, there exist a total number of
possible configurations in .

In certain circumstances, admissible labels may not be common to all the
sites. Consider, for example, feature based object matching. Supposing
there are three types of features: points, lines and regions, then a
constraint is that a certain type of image features can be labeled or
interpreted in terms of the same type of model features. Therefore, the
admissible label for any site is restricted to one of the three types.
In an extreme case, every site **i** may have its own admissible set,
, of labels and this gives the following configuration space

This imposes constraints on the search for wanted configurations.

**Figure 1.1:** A labeling of sites can be considered as a mapping from the
set of sites to the set of labels . The above shows mappings
with continuous label set (left) and discrete label set (right).