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).
