den 
inch 
'om- 
ated 
abel 
ents 
nate 
very 
e an 
vays 
arch 
| ex- 
ted, 
)des 
it is 
arch 
"Wer 
des 
ion, 
best 
otal 
tant 
DOs- 
ned 
wn, 
vith 
s of 
ed 
Y. 
1X 
  
65e 
ae 
  
  
  
  
Figure 3: Example streetl: extracted image lines (left), search tree (middle), result (right) 
  
  
  
  
  
  
  
  
  
Figure 4: Example river 
transformations with different point combinations were tried un- 
til an acceptable solution was found. In our application, written 
in the programming language POP-11, the algorithm needed 227 
seconds CPU time on a VAX Station 3200 in order to find a 
match for example streetl. 
Figures 4-5 give some results of the matching algorithm for other 
examples. The figures show the extracted line images, the land- 
mark models, and the models projected into the images. 
In the following table the most important parameters of the cal- 
culated matchings are summarized. The table contains the num- 
ber of model primitives (units), the number of extracted image 
primitives (labels), the number of examined nodes in the search 
trees (nodes), the number of tried transformations (trans.), and 
the search time in CPU seconds. 
  
  
  
  
  
  
  
Example units | labels | nodes | trans. | CPU [sec] 
streetl 25 67 52 6 227 
street2 27 59 47 1 100 
street3 23 71 52 6 228 
parcell 21 91 58 2 149 
parcel2 | 14 116 3307 | 1263 3557 
river 18 62 136 32 179 
  
  
  
  
  
  
  
  
The number of units and labels influence the number of nodes 
that have to be expanded and therefore the CPU time that is 
needed to find the match. Still there are some other factors 
influencing the complexity of the search space. These factors 
make it hard to predict the time the algorithm needs to find the 
match. The example parcel2 demonstrates, that the search time 
strongly increases, if the image contains many objects or object 
parts with similar primitives and relations. This is caused by the 
exponential enlargement of the search space if there are many 
973 
possible correspondences between model and image primitives. 
Differences between the description of the landmark model and 
the image, which make it necessary to use wildcard assignments 
also have a great influence on the size of the search tree. To 
demonstrate this, we produced an incorrect image description of 
example streetl by misclassifying several pixels by hand (figure 
6). The right solution still can be found, but the size of the 
expanded search tree (figure 7) increased to 293 nodes and the 
CPU time increased to 351 seconds. 
  
  
  
  
Figure 6: Image lines with segmentation error 
6 CONCLUSIONS 
Landmarks can be located by matching relational descriptions