threshold. In this experiment, the minimum distance, norm 
distance, and orientation and magnitude threshold are 15 pixels, 
1.5 pixels, 45°, mean gradient magnitude, respectively. 
It is important to use an orientation-invariant gradient 
operator, because the Fórstner interest operator is also 
orientation-invariant. Several gradient operators were tested and 
was found that the 2x2 Robert operator performs best with the 
Fórstner interest operator. Most corner points are detected well 
by the interest operator. However, a closer examination of the 
OSU campus model reveals that some corner points remained 
undetected where the gradient distribution around the point is 
not symmetrical. 
After the feature postprocessing, each straight line was named 
(closed, half-open, and open) based on the number of corner 
points connected to the line. The number of straight lines of the 
three different types after the feature postprocessing is listed in 
Table 1. Figure 7 depicts the results of this postprocessing. 
Table 1: Number of straight lines of three different types after 
  
  
  
  
postprocessing. 
Line Type Left Image Right Image 
Closed line 56 68 
Half-open line 141 148 
Open line 139 127 
  
  
  
  
  
4.2 2-D Tree Binary Relation Construction 
In the experiment, each bucket is designed to have four or five 
line primitives. Since the binary relations are constructed 
locally, the set of binary relational tuples for the label 
primitives must be larger than that of unit primitives. There is a 
chance that some label primitives may not have binary relations 
in their set of binary relational tuples which correspond to those 
of unit primitives. The nonexisting binary relational tuples in 
the binary relation set for label primitives results in assigning 
unit primitives to nils even though the unit and label primitives 
are conjugate features. This problem can be solved by reducing 
the depth of the 2-D binary tree of the label primitive set by 
one, which is equivalent to making each bucket for the label 
primitive set having twice the primitives that the unit primitive 
set has. Thus, each bucket for the label primitive set is allowed 
to have 9 or 10 line primitives. 
As listed in Table 2, the left image of the OSU stereopair 
have a number of line primitives less than the right images, thus 
the set of line primitives of the left image is taken as unit 
primitive set. As shown in Table 2, the left image (unit 
primitive set) has a 70% reduction and the right image (label 
primitive set) has a 30 % reduction. 
Table 2: The reduced number of binary relations using the 2-D 
tree technique. 
  
  
  
  
Closed and Half-open Line Left (unit) | Right (label) 
Line Primitive Number 197 216 
Maximum of Binary Relation No. 19,306 23,220 
2-D tree Technique 5,690 15,741 
  
  
  
  
  
4.3 Node Relation Matching 
For the OSU stereopair, the unit primitive set (left image) has 
22 node relations and the label primitive set has 26 node 
relations. To match two node relation sets, the proposed 
relational matching scheme with cost function was 
implemented. The cost function was selected because it tends 
to match as many as possible due to the controlled usage of nil 
mapping. The mismatch detection was then performed on those 
matched node points. In Figure 8, the matched node relations 
after the mismatch detection are shown. Since the node 
relations are distinct from one another, there were no wrong 
matches for the OSU stereopair. Using equation (1), the base 
vector b = (-0.25, -186.375) was computed. The processing 
time for node relation matching is 9.5 seconds for the OSU 
stereopair. 
4.4 Matching Results 
The matching result with benefit function only is shown in 
Figure 9 because of the lack of space. The matching result 
statistics are listed in Table 3. As shown in Table 3. two 
evaluation functions perform quite similarly except for the 
computation times. 
While the relational matching starts the search, it tries to find 
a path with a minimal cost and also a minimum number of nil 
mappings. Even though the search tree recognizes the cost of 
the current path is higher than that of the solution path already 
found, it must keep expanding the subtrees as long as the 
number of nils in the current path is smaller than the path that is 
already found. This property causes poor performance of the 
cost function. The search tree finds a path which has a 
minimum cost, but if the other path has a smaller number of nil 
mapping, then the search tree takes the path as the solution 
path. Since the cost function cannot cope efficiently with the nil 
mapping, the cost evaluation function suffers from the 
computation complexity by expanding unnecessary subtrees. 
Unlike the cost function, the benefit function does not have a 
nil mapping problem from the point of computation 
complexity. When the tree search with benefit function finds a 
path which has more benefit than the solution path already 
found, it takes the path as a solution path without considering 
the number of nil mappings in the current path. This property 
of the benefit function makes the search tree backtrack when 
the estimated benefit is smaller than the benefit of the solution 
path. This characteristic of the benefit function leads to better 
performance than cost function. 
Relational matching with both evaluation functions has 
several bad matches in which relations are held only locally, but 
not globally. These wrong matches are obtained when unit 
primitives have no corresponding label primitives in a set of 
label primitives but have label primitives which happen to have 
the relations compatible with other relations among the 
primitives. Using the relationally matched line primitives, the 
relative orientation between two images was computed. The 
matched end points were extracted from the matched lines and 
then those points were checked through the mismatch detection. 
Table 4 shows the matched end point numbers after the 
mismatch detection. 
The matched points after mismatch detection were used for 
computing the relative orientation between two images. Table 5 
Table 3: The matching results from the proposed relational 
matching scheme. 
  
  
  
  
  
  
  
Statistics Cost Benefit 
Function Function 
Total unit primitives number 197 197 
Matched line primitives number 103 107 
Good match 90 97 
Bad match 13 10 
Correct matching percentage 87.379 90.654 
Computation time (second) 1428 1079 
  
  
  
  
  
116 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
  
  
  
  
  
  
  
  
  
  
  
  
  
   
  
  
  
  
  
   
   
   
  
   
   
  
  
   
   
    
   
  
   
    
   
   
  
    
  
   
   
    
   
  
   
   
   
   
   
    
    
   
   
  
  
    
     
  
   
   
    
  
Figure 6: ( 
i 
c 
(