5.1
The features, properties and relations can be denoted compactly as a relational structure (RS) [Fischler and Eschlager 1973,Ambler et al. 1973,Cheng and Huang 1984,Radig 1984,Li 1992a,Li 1992b]. An RS describes a scene or a (part of) model object. The problem of object recognition is reduced to that of RS matching.
Let us start with a scene RS. Assume there are m features in the
scene. These features are indexed by a set 
of
sites. The sites constitute the nodes of the RS. Each node 
is
associated with it a vector 
composed of a number of 
unary properties or unary relations,
. A unary property
could be e.g.
the color of a region, the size of an area, or the length
of a line. Each pair of nodes (
) are related to
each other by a vector 
composed of a number of 
binary (bilateral) relations,
. A binary
relation could be e.g.
the distance between two points, or the angle
between two lines. More generally, among n features
, there may be a vector 
of
n-ary relations. This is illustrated in Fig.5.1. An
n-ary relation is also called a relation, or constraint, of order n.
The scope of relational dependencies can be determined by a neighborhood
system 
on 
. Now, the RS for the
scene is defined by a triple
where 
and H is the highest order. For
H=2, the RS is also called a relational graph (RG).
The highest
order H cannot be lower than 2 when contextual constraints must be
considered.
The RS for a model object is similarly defined as
where 
, 
, 
and so on. In this case,
the set of labels 
replaces the set of sites. Each element in 
indexes one of the M model features. In addition, the ``neighborhood
system'' for 
is defined to consist of all the other elements, that
is,
This means each model feature is related to all the other model
features. The highest considered order, H, in 
is equal to that
in 
. For particular n and k (
; 
),
represent the same type of constraint as 
; for
example, both represent the angle between two line segments.
Figure 5.2: Discrete mapping involving the NULL
label (numbered 0).
All scene nodes (sites) not modeled by the considered object should be
matched to this special label.
Relations of various orders impose unary, binary, ... , H-ary constraints on the features. Inter-contextual constraints are represented by the second or higher order relations. Due to these constraints, a scene, an object or a view of an object is seen as an integrated part rather than as individual features. The higher the order of relations is, the more powerful the constraints are, but the higher the complication and expenses are in the computation.
There can be multiple model RS's in a model base. A model RS describes a whole model object or a part of it. When an RS is used to describe a part (for example a view) of an object, the whole object may be described by several RS's and these RS's may be related by some inter-RS constraints.
Now introduce a virtual model composed of a single node 
.
It is called NULL
model. This special model represents everything not
modeled by 
, such as features due to all the other model objects
and the noise. So the actual label set in matching the scene to the
model plus NULL
contains M+1 labels. It is denoted by
After the introduction of the NULL
, the mapping from 
to 
is
illustrated in Fig.5.2.
Figure 5.3: Cup images and segmentation based on H-K surface curvatures.
Top: a cup image and its H-K map.
Bottom: a transformed version of the cup image and the HK map.
Some noise is introduced during the transformation due to quantization.
From (Li 1992a) with permission; © 1992 Academic Press.
Figures 5.3 and 5.4 demonstrate two cup
images and their segmentations based on the H-K surface curvatures
[Besl and Jain 1985]. Suppose we are matching the RG in
Fig. 5.4(b) to that in (a). Based on the constraints from
the unary properties of surface curvature and region area, and binary
relations of distance between regions, the correct matching from (b) to
(a) is 
, 
and the rest to NULL
.
Model-based matching can be considered as finding the optimal mapping from the image RS to the model RS (or vice versa). Such a mapping from one RS to another is called a morphism, written as
which maps each node in 
to a node in 
and thus maps relations 
to relations 
A morphism is called an isomorphism if it is one-to-one and onto. It is called a monomorphism if it is one-to-one but not onto. It is called a homomorphism if it is many-to-one. We do not allow one-to-many mappings because they contradict the definition of functions and, more crucially, increase the difficulties in finding the optimal solutions.
Figure 5.4: Relational graphs built from the cup HK segmentation maps.
The texture of the nodes denotes different surface types and the links
represent the adjacency relations. (a) The RG for the orginal upright cup image. Node 1
corresponds to the body of the cup and node 2 to the handle. (b) The RG
for the transformed cup. Node 5 corresponds to the body, node 1 to the
handle, and the rest to NULL
. (c) Legend for the correspondences
between texture types and H-K surface types.
From (Li 1992a) with permission; © 1992 Academic Press.
When the properties and relations in the considered RS's include numerical values, the mappings are numerical morphisms which are more difficult to resolve than symbolic morphisms. Since such morphisms do not preserve relations in the exact, symbolic sense, they may be called weak morphisms -- a term extended from the weak constraint models [Hinton 1978,Blake 1983,Blake and Zisserman 1987].
The goodness of a numerical morphism is usually judged by an objective function such as an energy. It is not very difficult to find a correct one-to-one mapping (isomorphism) between two identical RS's. The requirement that the unary properties of two nodes and the binary relations of two links must be exactly the same in order to be matched to each other provides a strong constraint for resolving the ambiguities. For the case where the two RS's have different numbers of nodes and the matched properties and relations are not exactly the same, the matching is more difficult because it cannot exploit the advantage of the strong constraint of the exact equalities. Only ``weak constraints'' are available. The subsequent sections use MRFs to establish the objective function for weak homomorphisms for inexact, partial matching.
