then performed, which is discussed in next section. Using the 
matched node points, the initial approximation between two 
relational descriptions can be estimated. The initial 
approximation is represented by the base vector (shift) 
bs vb )! between two relational descriptions. The 
base vector with matched m node relations is computed as 
> qaem Te I oss ) x (oon, t d on ) 
= k=1 nd 
b,, w > cal iT 
b (1) 
m 
m 
where r and / stand for right and left image, respectively. The 
base vector as an initial approximation serves the mapping 
function to find the corresponding line primitives in a reduced 
search space. 
  
node point 
  
  
  
Figure 4: The node relation with its attributes. 
3.4 Evaluation Function and Heuristics 
The evaluation function guides the search algorithm to a 
solution, based on the similarity measure between two 
relational descriptions. There are two ways of estimating the 
similarity measure using the cost function: distance measure 
approach and conditional probability approach. The distance 
measure approach that utilizes the absolute differences between 
geometric attributes of conjugate primitives (relational tuples) 
is implemented in this research. Details of the conditional 
probability approach can be found in [Boyer and Kak 1988]. A 
benefit function estimates the support (or benefit) that the 
attributes of corresponding primitives and relation tuples give 
to the mapping. The mutual information is implemented as a 
benefit measure [Vosselman 1992]. The unit of information is 
nat, that is the base of the logarithm is e. It is assumed that all 
attributes of all primitives and relational tuples are independent 
of one another so that total measure of cost and benefit between 
two relational descriptions can be computed simply by 
summing up each cost (benefit) measure among primitives and 
relational tuples 
Scale, different viewing directions, surface orientation, 
topography undulation and relative heights of objects cause the 
geometric attribute values and the geometric relations to be 
different. Thus, it is necessary for the matching to know these 
variations. In this study, the variation of two relational 
descriptions is estimated by an analytical function with a few 
critical parameters. The result of this analytical function 
approach is used to compute a cost measure as well as a benefit 
measure using the conditional probability function for mutual 
information. For the analytical function, the collinearity 
equation is chosen because of easy manipulation of parameters 
of interest. For the lack of space, the implementation details of 
the analytical function approach are skipped. For a more 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
detailed description of the analytical function approach and 
evaluation function the reader is referred to Cho[1995]. 
To speed up the searching process in a tree, two well known 
heuristics are implemented: unit ordering and forward checking. 
The search space in the image matching problem is rather large. 
One way of reducing it is by ordering unit primitives. Tree 
search suffers from many backtrackings and explores fruitless 
paths when unit primitives at higher levels of a tree have many 
possible candidates. Therefore one is interested in ordering the 
tree in such a fashion that unit primitives with fewer label 
primitives are ordered at higher levels of the tree. 
Forward checking examines the consistency of current unit- 
label pair with future unit-label pairs below the current level in 
a tree. The forward checking procedure is modified to be 
suitable for the image matching problem in this study. While 
examining future with current unit-label pairs, the modified 
forward checking counts and stores the number of valid future 
pairs at the current level. This number is stored in a 2-D table: 
row for unit primitives and column for label primitives. At the 
current level of a tree, the modified forward checking sums up 
the number of previous and future unit-label pairs. The total 
number obtained by the modified forward checking is utilized 
while the search tree tries to find a solution. 
3.5 Matching Scheme 
Since the descriptions of the two images of a stereopair differ 
(due to noise, different viewing angles, difficulties in feature 
extraction and occlusion, etc.), inexact relational matching must 
be employed. The extent of nil mapping must be controlled, 
especially when the evaluation function is a cost function. If the 
tree search maps all unit primitives to nils, the total cost 
measure is zero and this mapping provides a trivial solution. 
As for the benefit function, nil mapping does not contribute any 
benefit to the mapping. However, the extent of its usage is not 
actually a concern because any unit-label pairs that benefit the 
mapping are more preferable than nil mapping. 
The proposed relational matching scheme utilizes the A* 
search with heuristics such as unit ordering and the modified 
forward checking. Since the image matching problem reaches 
the solution at the bottom of the tree, A* search is selected in 
this study. Although the proposed matching scheme employs 
the heuristic search A* with the modified forward checking and 
unit ordering, the search space is too large to reach the solution 
in a reasonable amount of time. To speed up the convergence of 
the solution, two relational descriptions are locally matched 
first, and then a globally consistent solution is achieved using a 
relation consistency check. Figure 5 illustrates the entire 
procedure of the proposed relational matching scheme. 
3.6 Mismatch Detection 
The proposed matching scheme matches the line primitives in 
two relational descriptions. Even though some matched pairs 
satisfy the interrelationships with other matched pairs, there 
could be mismatches due to a large search window, 
segmentation error, and missing corresponding features. These 
mismatches can be detected by two steps: a geometric approach 
and a radiometric approach. 
The geometric approach employs the affine transformation 
between two matched line primitive pairs. It is assumed that 
rotation between two relational descriptions is small or 
estimated from the matched line primitives. The detailed 
procedure is the following. 
114 
  
     
  
1. Com 
match 
2. Estim 
origin 
the st: 
3.- Flimi 
excee 
In this app: 
only consic 
object heigl 
While th 
blunder-lik: 
mismatches 
employs tl 
correlation 
matched pc 
are elimine 
correlation 
study.. 
To assess ! 
scheme, a s 
|