Document Description

In this paper we address the problem of matching objects which are subject to deformation. The issue of determining the best elastic match is discussed, and a scoring strategy evolved. The matching process results in finding a label for each feature

Document Share

Document Tags

Document Transcript

Pattern Recognition
Vol. 24, No. 8, pp. 747-753, 1991
rinted
in Great Britain 0031-3203/91 3.00 + .00
ergamon ress pie
~) 1991 Pattern Recognition Society
ELASTIC MAXIMAL MATCHING
R. S. MITRA and N. N. MURTHY CMC Limited, 115, S.D. Road, Secunderabad-500 003, India
Received
28
August
1990;
received for publication 3 January
1991)
Abstract In
this paper we address the problem of matching objects which are subject to deformation. The issue of determining the best elastic match is discussed, and a scoring strategy evolved. The matching process results in finding a label for each feature of the search object, from the features of the database object. A special label (NULL) is used to indicate the absence of a matching feature. Matching proceeds by backtracking. Preprocessing is done to reduce search space. Point patterns Inexact matching Elastic matching Consistent labelling Backtracking
l. INTRODUCTION
Object recognition plays a central role in most com- puter vision applications. For instance, automatic sorting of objects on a conveyor belt involves the recognition of the part from several objects stored in a database. Other applications of object recognition and image matching include quality control of indus- trial parts, registration of aerial images, navigation, change detection and stereo mapping. Recognition of an object involves the matching of the view of the object (search object) with a set of models (views of different objects), stored in a database. The model that best fits the search object is recognized as the corresponding object for the view. The results of the recognition process are used to influence subsequent decision making. Rec- ognition of objects by matching their grey images (or even binary images) is an expensive procedure. The task is often simplified by extracting feature points from the images (such as road intersections in aerial photographs, or corner points in industrial parts) and matching these patterns. Thus, matching of two objects is often reduced to the task of finding a correspondence of the feature points of one object to those of the other. There are several difficulties associated with this task: (a) Most often, there does not exist an exact one- to-one correspondence between the feature points of the two objects. This is partly due to the errors inherent in the picture formation and feature extrac- tion stages, which give rise to the presence of spu- rious points, or the absence of actual points. (b) The object that is being matched (against a database of known objects) may only be a partial view of its database counterpart. (c) The objects themselves may be deformable (within limits), thus distorting the feature graph. Point pattern matching has received considerable attention from researchers, and has involved dif- ferent methodologies. Lavine 0) uses minimal span- ning trees and nearest neighbour distances to form a measure of similarity between point patterns. Ogawa ~2) uses Delaunay triangulation to partition a point pattern into a set of triangles, based on the knowledge of some reliable points, and the largest maximal clique of the consistency graph for each triangle is used to obtain the largest set of mutually consistent pairs. Although these methods are invariant under translation, they are not very tolerant of patterns where points are randomly missed and no point is more reliable than the other, and where the patterns are deformable. Baird ~3) gives an algorithm which matches patterns in O(n 2) time, where n is the number of points in the two images, i.e. the number of points is the same in both patterns. If this criterion is not satisfied, as in our case, this algorithm becomes exponential. Point pattern matching can be viewed as a con- sistent labelling problem (CLP): (4) label each feature of the search object with a feature from the database object, such that it is consistent with the labellings given to the other features. The definition of a con- sistent labelling is dependent on the tolerance cri- teria for elastic matching. CLP can be solved by several methods: backtracking, ~5) relaxation,t 6) etc. Relaxation is a brute force method of finding a consistent labelling: for each pairing
i,j),
(i= 1 ... , m, j = 1 .... n, where m and n are the sizes of the two objects), determine the support that each other pairing
h,k), h = 1 ..... m, k = 1 ..... n,
lends to it, and update the probability of the pairing
i,j)
accordingly. The support given by (h,k) depends on the match-probability of the pairing (h,k) and the consistency of
i,j)
with
h,k).
Thus, initially i may be considered a good pairing for all j = 1 .... n. But as the support from other pairings builds up, only a few of these will have a high enough probability of match and so the possible values for j decrease. But 747
748 R.S. MITRA and N. N. MURTHY to continue this iterative process until the labelling of i is pinpointed to just one j may take a lot of time. Ton (7) reports that finding the registration points of Landsat images, having 70 points each, takes over an hour on an IBM/PC 386, even after optimizing the ordinary relaxation algorithm from O(n 4) to
O n3).
The advantage of this method is that it easily lends itself to parallelization. Backtracking is an elegant method of determining consistent labellings, by growing a constellation of labelled points recursively: given a consistent set of n labellings, add another labelling to it, if it is consistent with the previous n labellings. Although this method is inherently sequential, there exists a lot of scope for optimizations by introducing pruning techniques such as forward-checking and look- ahead. Pruning may also be done as a preprocessing step, with techniques such as relaxation. In this paper, we have advocated a preprocessing procedure to reduce search space. In Section 2, the problem definition is made. Con- sistency, cost functions and scoring strategy are also defined. Section 3 describes the preprocessing before the actual backtracking algorithm starts. Section 4 presents the backtracking algorithm, and a discussion on it. In Section 5, experiments are discussed in brief.
2 DEFINITIONS
An object is defined by a set of feature points, X = {xi}. Each feature point is defined by an attribute vector, whose values define the feature point uniquely. Thus,
xi = {al ..... aa}.
Search object X, with feature set
{xi}
(i= 1,... , m), is being matched with a database object Y, with feature set {y/} (j = 1 .... n). Finding a match is to label each
xi
with a certain
yj
(or a NULL label, indicating that no match is possible), such that these labellings are consistent. The NULL label can be considered as a special point Yn+l which, when used as a label, is consistent with all other labellings. Consistency may be of two types: (a)
Local consistency
(x~, yj) is locally consistent if the attributes of xi are similar to the attributes of yj, i.e.
Ixi.~ - Yj.kl <- tk, k = 1,... , A,
where
X~.k
is the kth attribute of xi, and tk is the allowable threshold for the kth attribute. (b)
Global consistency
Each labelling has to be globally consistent with the other labellings done so far. (xi, y/) is globally consistent with
Xc, y/, ) if ld xi, Xc ) - d yj, yf )l <- T~,
where d is a distance function defined on the point attributes, and
Te
is the allowable threshold on an edge. As an example, the attributes of the feature points are the Cartesian coordinates and brightness (grey value), and the distance function, d, is the Euclidean distance between feature points. Determining a consistent labelling is not enough; we require the best of all consistent labellings avail- able. So, a cost is computed for each labelling, and the cumulative cost is propagated as the cost of the current set of labellings. In elastic matching, determining the best of all consistent matchings is a tricky issue, perhaps best solved experimentally. For example, consider the following consistent label- lings: (a) labellings = 5, total cost = 100, (b) labeilings = 7, total cost = 200. Labelling (a) may be a subset of labelling (b). The task we are faced with here is the assigning of a score to a consistent labelling, indicating our confidence in the matching, and selecting the label- ling which has the highest score. Shapiro (5) proposes a probability model for the random alteration of an object (a structural description), and a confidence of match which is measured not on the basis of the inexactness of the match, but by the likelihood ratio whose numerator is the probability that the alteration determined by the inexact match would occur for the structural description of an entity in the class, and whose denominator is the probability that the com- puted inexact match would arise from just a chance inexact match to a completely random structural description . Such a scheme may not be feasible for several reasons: (a) it may not be possible to develop such a model of random alteration for every elastic body deformation, (b) if the number of objects (or classes) is large, then storage of their models of alteration creates extra overheads and (c) selection of a com- pletely random object (or class) in the denominator may randomly alter the scoring pattern too. Instead, we define a tolerable (good enough) elas- tic matching by introducing an upper bound on the average cost incurred while introducing a new label- ling. Any new labelling which overshoots this limit is discarded. All labellings that satisfy this criterion can now be accepted as a tolerable matching, and the question of selecting the best one addressed to these. Two criteria are used to form the score of a match: the number of matched points, and the cost of the match. Intuitively, the score should increase as the number of matched points increases, and should decrease as the cost of the matching increases. But these criteria are at odds with each other, for the higher the number of matched points, the higher the cost will be. A trade-off is sought between these two criteria--how far may the cost be allowed to increase if another labelling is attached to the current match- ing. Trade-off is given by the definition of an accept- able matching, which limits the average cost per
Elastic, maximal matching 749 labelling to a certain threshold. Thus, while com- puting the score for an acceptable matching, the number of matched points gets the first preference; second preference is given to the cost of the match- ing. It is possible for an object to get so distorted that it matches with a different object from the database, forming a high score value. But our assumption is that the discrimination between the distortions of separate objects is greater than the thresholds allowed in the matching, so that high scores for such interobject matchings would be rare, if not impossible. The definitions of the cost functions are given below:
Ce xi,xi,)
= 0, if
L xi)
= NULL or
L xr
) = NULL = I d x,, x,, ) -
d L x,), L x,,
))1, otherwise, where
L xi)
is the label assigned to
xi.
Cl Xi,
L xi))
= 0,
ifL xi)
= NULL = 1//) ~
Ce xi, xj),
otherwise, J where j takes on those values for which xj has already been labelled, and l is the number of non-NULL labellings done so far.
C, xi, L xi)) = ~, Ct xj,
L x~)),
]
where j takes on those values for which xj has already been labelled. C, is the cost of an edge comparison;
CI
is the average cost of introducing a new labelling; Ct is the total cost that is propagated during back- tracking. For consistency:
C, <- Te, Ct
<-- TI
where T, is the upper bound on edge cost, and
Tt
is the upper bound on the cost of a labelling.
3 PREPROCESSING
Matching by backtracking is equivalent to search- ing in a search tree where each node corresponds to a matched feature pair
xi, y j))
for a path from the root to a leaf node. Execution time is reduced considerably if large subtrees of the search tree can be bypassed. Each feature
xi
can potentially be matched with any y j, j = 1 ... , n. This results in a huge search space, and backtracking is bound to be expensive. Local consistencies are used to limit the possible matches for
xi
to a set of candidates {Zk}, which is a subset of {yj}. Backtracking is then applied on these candidate lists. The order of variable feature point) selection during backtracking is crucial to decreasing the search complexity of backtracking. The candidate lists are sorted on the increasing order of their lengths, so that less backtracking is done on the larger lists. This is an implementation of the first-fail principle Haralick 8)) which recommends the choice of the most constrained variable first. The order of variables is not changed dynamically during back- tracking. The order of value selection for a variable is not given importance here, since ultimately all labellings values) will have to be considered. This is because we are interested in the best matching, and not just any one matching. If the relative orientations of the objects are known, along with an alignment point in each object points that are a priori known to be matched), then the local consistency check may include some candidate boundary checking. That is to say, once the above information is known,
xi
needs to be checked only with those yj whose features say, coor- dinates) are near within thresholds) to those of xi. Figure 1 shows threshold boxes for some points in X, containing a few points of Y. Since we are considering elastic matching, the value of these thresholds would increase as the dis- tance from the alignment point increases. Depending on the property of the elastic material, elasticity may be displayed only in particular directions; accord- ingly, thresholds need to be increased in these direc- tions only. If the relative orientation or the alignment point information is not available, a few iterations of a relaxation process may be made to narrow down the possible labellings of a feature point, before starting the backtracking procedure. 4. MATCHING
4.1. Algorithm
Backtracking is essentially a recursive algorithm Nilsson 9)): given a set of consistent labellings, it tries to add another consistent labelling to it. If successful, it calls the backtrack procedure recur- sively to add the next labelling. If no consistent labelling is found at the current level of recursion, the procedure returns i.e. goes to the previous level of recursion) and tries the next labelling there. Thus, all possible combinations of labellings are tried out, and the best one is chosen. Here we consider a sequential version of back- tracking, where the stacks of
Sk
possible labellings at level
k), lk
chosen labelling at level k) and Ct the cumulative cost of matching) are maintained explicitly by the algorithm. For a detailed study of the algorithm and evaluation of its efficiency, see references 10-12).
Pseudo-code
1. [Initialize] Set k level)= 1, Best-Score =0, Matching = ).
750 R.S. MrrRA and N. N. MuaxIaV
4 • 4 0
r
• • 4 • • 4. • • • • • 4- Y • • •
Fig. 1. Threshold boxes (tolerances on x and y) for some points of X. The alignment points are marked by big crosses. Box sizes increase with distance from the alignment point. Boxes for different points may overlap. 2. [Generate] Generate the labellings at level k:
Sk
= {(xk,
Yi)[Yi
is a candidate label for
Xk} Yi
also includes a NULL label). This set may have been prepared already during preprocessing, or prepared dynamically by for- ward checking (as mentioned in Sections 3 and 4.2). 3. [Have all labellings been tried?] If
Sk
is empty, goto step 7. 4. [Advance] Choose any element of Sk, and call it
lk.
Delete it from Sk. 5. [Is new label consistent and acceptable?] Check if
lk
is consistent with the previous labellings li (i = 1 ... , k - 1), and acceptable, by computing the cost
Ct
for the labelling l k and comparing it with
Tt.
If
lk
is not consistent, goto step 3. 6. [All points labelled?] If k = m (i.e. all xi, i = 1 .... m, have been labelled), goto step 8. Else, k = k + 1 and goto step 2. 7. [Backtrack] k = k - 1. If k = 0, exit with the best matching found in step 8. Else, goto step 3. 8. [Matching found] Note the labeilings
li, i = 1 ....
m, and the associated cost,
Ct,
and compute the score, Sc, for this matching. If Sc > Best-Score, Best-Score = Sc and Match- ing = current matching. Goto step 3. 4.2.
Discussion
In backtracking, a new node (pairing) is intro- duced if it is found to be consistent with the previous nodes in the path from the root to the current node. A theorem of Montanari s (~3) states that, in a net- work with a complete graph, if every path of length 2 is path consistent then the network is path consistent. The search graph under consideration here is com- plete, since there exists an edge (i.e. a consistency relation) between every possible pair of nodes in the graph (i.e. between every pair of labellings). Therefore, consistency needs to be checked with only two of the previous labellings, in order to intro- duce the new consistent labelling. The above observation holds only for exact mat- chings. In elastic matching, the errors formed by only two checks are likely to propagate, and so more checks are necessary. How many more is a problem- specific criterion, dependent on the error tolerances allowed, and determined experimentally with the aid of training samples. The edge threshold, Te, is a constant value, but Ce is dependent on the length of the edge being considered. Hence, if the distance to the feature points with which consistency is checked for is large, it would be a good idea to revise the definition of Ce (given in Section 2) by normalizing it with the value of the distance function. Alternatively, only those features could be chosen for a consistency check, which are the nearest to the feature under scrutiny. In Section 3, we have discussed the preparation of a candidate list of labellings, for each feature of the search object. If this is not possible (in the absence of orientation or alignment point information), then these candidates can be formed dynamically during backtracking. Given that two features are labelled, and a third is about to be labelled, we need to consider only those labels which lie in a particular area. This is similar in principle to backtracking with forward checking. Figure 2 shows such a search area for the candidate labels for c, where
a,A)
and
b,B)
are the existing labellings. Pruning, an essential part of the backtracking pro- cedure, is done in Steps 2 and 5 of the algorithm,
Elastic maximal matching 751
X b
C
Y A C Fig. 2. Forward checking to form set of candidate labels. (a,A) and (b,B) are the existing labellings. Candidate labels for c are in the box marked C. by eliminating undesirable labellings at the earliest. Further pruning may be done if we want the number of non-NULL labellings to exceed a certain lower bound (MIN-MATCH). In this case, the following additions are to be made to the above algorithm: 1.1. Expected-labels = m. 4.1. If
lk
is a NULL label: If Expected-labels = MIN-MATCH goto step 4 Else Expected-labels = Expected-labels - 1. 7. (Modified) [Backtrack] If
lk
is a NULL label, Expected-labels = Ex- pected-labels + 1 k = k - 1. If k = 0, exit with the best matching found in step 8. Else, goto step 3. 8. (Modified) [Matching found] Note the labellings
li
i = 1,..., m, and the associated cost, Ct, and compute the score, Sc, for this matching. If Sc > Best-Score, Best-Score = Sc and Match- ing = current matching If
l n
is a NULL label, Expected-labels= Expected-labels + 1 Goto step 3.
5. EXPERIMENTS
The above mentioned scheme for elastic matching has been tried out with a database of 950 objects, each having about 80 feature points. The number of feature points in the search objects varied from 8 to 20. The tests were done for 40 cases. Two sample case patterns and their corresponding database objects' patterns are shown in Fig. 3. The alignment point is marked by a big cross, and the ordinary points are marked by small crosses. The (manually) paired points are marked as squares. The values of the thresholds used in the algorithm were determined with the aid of training samples. Initially, the algorithm was run with consistency checks done against all previous labellings. In sub- sequent runs, the number of consistency checks was slowly brought down, keeping the performance con- stant. It was found that eight consistency checks were enough to give good results in our application. In most cases (about 90 ), the correct object formed a high score of matching. In those cases where a wrong recognition was made, the error was partly due to lack of enough feature points, and partly due to higher than usual distortion of the search object. Search complexity was reduced considerably by the use of the pruning criteria mentioned above. The time taken to match a search object having 11 points, against its corresponding database object, was 76 ms in an IBM/PC 486. However, it should be noted that speeds vary widely in a backtracking procedure, depending on the patterns considered for matching.
6. CONCLUSIONS
A scheme for the consistent labelling of feature points of elastic bodies has been presented, using the backtracking algorithm. A matching is represented by two parameters--the number of features matched and the goodness of fit. A scheme is presented to combine these two parameters into a score value, which indi- cates the confidence in the matching. Search space is reduced during preprocessing, by considering extra information, such as orientation and alignment point. In the absence of extra information, search space is reduced by backtrack with forward checking.
7. SUMMARY
The problem of object recognition in a computer

Similar documents

Search Related

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks