next up previous index
Next: Labeling Problems in Vision Up: Visual Labeling Previous: Sites and Labels


The Labeling Problem


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