that minimizes the cost function. It can be 
found using backtracking search with forward 
checking [Haralick and Elliott, 1980]. 
4.3 Backtracking with Forward Check- 
ing 
The backtracking tree search begins with the 
first unit of L. This unit can potentially 
match many labels in O. Each of these po- 
tential assignments is a node at level 1 of the 
tree. The algorithm then starts to construct 
the children of the first node, which are nodes 
that map the second unit of L to each possible 
label of O. A cost is associated with each la- 
bel. The paths from the root node to any suc- 
cessful node are the consistent labellings. The 
best mapping is the path which minimizes the 
cost. Forward checking is used to cut down 
the search time by reducing the size of the 
tree that is searched. This checking is based 
on the idea that once a unit-label pair is se- 
lected at a node in the tree, the constraints 
imposed by the relations cause the selection of 
some future unit labels to become impossible. 
5. EXPERIMENTS & RESULTS 
Fig. 2 shows a digitized aerial image, the 
extracted linear features (DRO Image), the 
feature image model, and the road ground 
model. Fig. 3 shows a SPOT image, the 
extracted linear features (DRO Image), the 
feature image model, and the road ground 
model. Some roads were not extracted by the 
Duda road operator (DRO) due to the lack 
of contrast. In addition, other linear features 
and artifacts in the images were extracted. 
The linear features with sufficient length were 
matched to the road ground models. Hence, 
only roads that are represented in the ground 
model will have an acceptable match in the 
image. An acceptable match is the one whose 
cost function is minimum. 
The cost function depends on the similarity 
between the attributes of the primitives, the 
similarity between the relations, and the num- 
ber of missing vertices (wild cards). A larger 
weight is given to the attributes of the prim- 
itives, since they describe the general charac- 
terstices of the linear feature. Furthermore, 
the number of wild cards should not exceed 
a certain number. By adopting this method- 
ology, the matched roads for both the aerial 
and SPOT images were found and are shown 
in Fig. 2 and Fig. 3. The matched roads 
were investigated manually and it was found 
that they correspond to their conjugate roads 
in the ground model. The conjugate roads 
in the image and on the ground can be used 
as linear control to perform image resection 
(Exterior Orientation). 
6. CONCLUSION 
The implemented methodology is unique in 
its attempt to automate the exterior orienta- 
tion of digital photos. It has both practical 
and scientific significance. Very few in the 
photogrammetric community tried to solve 
the exterior orientation automatically. Most 
previous research has focused on the relative 
orientation of stereo-pairs or blocks of pho- 
tographs. Furthermore, for orienting satel- 
lite images or small scale aerial images, ex- 
isting maps (USGS quads) are often used to 
find control features on the ground. The ac- 
curacy of these maps is roughly 15m, which 
is not sufficient for most mapping applica- 
tions, while the accuracy of the roads cap- 
tured by the GPSVan is about 2m. By using 
the implemented methodology, more accurate 
ground control can be obtained, as compared 
to the existing manual methods. Another 
major problem with using digitized maps for 
ground control is that they were generalized 
and many features existing in the images do 
not appear on the map or are offset on pur- 
pose. Therefore, it makes sense to drive the 
van, to create an accurate road map dynam- 
ically, and to use it for the orientation of the 
images, as well. We believe that this approach 
178 
  
  
has a g 
applicat 
Refe: 
[1] 
[3] 
[4] 
Acl 
Dig 
per 
Soc 
tog 
Con 
WOC 
Bar 
[19° 
sigr 
Col 
Mo: 
3-D 
act 
chir 
Duc 
tern 
Wil 
Har 
Incr 
Con 
ficic 
198( 
Mik 
ture 
and 
Mck 
[198 
Frag 
imag 
Cari 
CM!