5.1.2
Two important computational issues in object matching are how to use contextual constraints and how to deal with uncertainties. Contextual constraints in object recognition are often represented using the notion of relational graphs. An object is represented by a set of features, their properties and relations. Relative values between two image features embed context in matching [Fischler and Eschlager 1973]. Object matching is then reduced to matching between two relational graphs. On the other hand, noise is inevitably introduced in the process of feature extraction and relation measuring.
In the maximum clique method [Ambler et al. 1973,Gharaman et al. 1980] for relational graph matching, an associated graph is formed from the two relational graphs, one for the scene and the other for a model object [Ambler et al. 1973]. Each node of the associated graph represents a possible match. The optimal matching is given by the maximal cliques.
A class of constraint satisfaction problems for matching is studied by [Shapiro and Haralick 1981]. In their work, the criterion is the weighted number of mis-matched relations. Most of such work involves definition of some criteria to describe the ``goodness'', or reversely the cost, of matching with relational constraints. Errors and mistakes in symbolic relations are mapped into a number, and this number is then used as a criterion to decide whether a homomorphism is acceptable or not. The inexact matching problem is viewed as finding the best homomorphism, i.e. the one with minimum number of errors with respect to a given attribute value threshold, a missing part threshold, and a relation threshold.
Relaxation labeling (RL) [Rosenfeld et al. 1976] has been a useful method for solving the matching problem. The constraints are propagated via a compatibility function and the ambiguity of labeling is reduced using an iterative RL algorithm. In our view, the most important part in the RL-based recognition is the definition of the compatibility function. Various RL schemes should be considered as algorithms for finding solutions. This will be further examined in Section 8.2.2.
Typical early works on relational matching using RL include [Davis 1979] and [Bhanu and Faugeras 1984,Bhanu 1984]. In [Davis 1979], the objective function consists of four terms. Each term either encodes a particular constraint or penalizes unmatched features, the idea dated back to the work by Fischler and Elschlager (1973) . An association graph [Ambler et al. 1973] is used for matching relational structures. In the search for optimal matching, incompatible nodes for which some evaluation function is below a threshold are deleted from the graph. This generates a sequence of association graphs until a fixed point is reached. In [Bhanu and Faugeras 1984,Bhanu 1984], matching is posed as an optimization problem and the optimization is performed by using an RL algorithm presented in [Faugeras and Berthod 1981].
A feature common to most of the above matching works is that thresholds are used to determine whether two matches are compatible. This effectively converts the weighted-graph matching into symbolic matching. While greatly reducing search space, this may rule out the potential matches. Because of the noise, the observation of the objects, which represents feature properties and relations extracted from the scene, can be considered as a set of random variables. Furthermore, some object features may be missing and spurious features may emerge due to noise and un-modeled objects. The matching strategy has to deal with these uncertainties. It is hard to judge that in the presence of uncertainties, a difference of 1.000001 is an impossible while 0.999999 is a possible.
In the weak constraint satisfaction paradigm, ``hard'' constraints are allowed to be violated without causing the failure of constraint satisfaction. However, each such violation is penalized by adding an amount to a cost function that measures the imperfection of the matching. This is usually implemented by using line process in low level vision [Geman and Geman 1984,Marroquin 1985]. In a weak notion of graph-matching, Bienenstock (1988) proposes a scheme for an approximation of graph isomorphism in which relation-preserving characteristics of isomorphism can be violated but each violation incurs a small penalty. This is a transplant of the idea of the line process at the lower level to the higher level perception. Nevertheless, at a higher level where more abstract representations are used, the weak constraint satisfaction problem becomes more complicated.
Li makes use of contextual constraints not only on the prior configuration of labelings but also on the observed data into the labeling process [Li 1992a,Li 1992b,Li 1992c,Li et al. 1993]. He proposes an energy function, on a heuristic basis, which combines contextual constraints from both the prior knowledge and the observation. Kittler et al. [Kittler et al. 1993] later derive the same compatibility from probabilistic view point used in Li's energy function.
MRFs provide a formal basis for matching and recognition under contextual constraints . Modestino and Zhang (1989) describe an MRF model for image interpretation. They consider an interpretation of a scene as an MRF and define the optimal matching as the MAP estimate of the MRF. Unfortunately, the posterior probability therein is derived not by using the laws of probability but designed directly by using some heuristic rules. This contradicts the promises of MAP-MRF modeling. Cooper (1990) describes a coupled network for simultaneous object recognition and segmentation. MRF is used to encode prior qualitative, and possibly, quantitative knowledge in the non-homogeneous and anisotropic situations. The network is applied to recognize Tinkertoy objects. An interesting development is Markov processes of objects proposed by [Baddeley and van Lieshout 1992 ]. Other works in MRF-based recognition can be found in [Grenader and Y. Chowi 1991,Baddeley and van Lieshout 1993,Friedland and Rosenfeld 1992,Kim and Yang 1992,Cooper et al. 1993]. The MRF model described in the next section is based on [Li 1994a].