the expression (1) simplifies to: 
1 
2 
(3) 
The distance d;; decreases when the integral in expression (3) 
increases. If the neighbourhood functions are positive func- 
tions, the integral in expression (3) takes values between 0 
and 1. 
We have formulated our search problem using as valuations 
of the nodes in the search tree merit functions and not cost 
functions. The reason for this is pragmatic: it is more natural 
to evaluate the goodness than the badness of a match. Thus, 
we will not use the distance as given by expression (3) but 
only the integral in expression (3) to define the model fidelity 
mi; at the level of line segments: 
dij = | _ : | ni(z, y, 1, 0)n; (x, y, l, 0)dx dy dl d0 
s 
mi; = mile, u,1,09n;(e,vr1,0)02dy did (4) 
S 
This integral equals to the cosinus of the angle between the 
two versors n; and n; in the vector space £?(S) and can 
be thought of as a correlation measure between these two 
versors. 
The neighbourhood functions are chosen regarding the 
physics of the image formation process and some heuris- 
tics motivated by experience. We construct the function 
ni(z, y, l, 0) as a product of three functions defined on R?, R 
and (— 2, 5] respectively: 
ni(z, y,l,0) — fi(z, y) gi(l) h;(0). 
To define the function f;(z, y) we take advantage of the fact 
that the parameters of the camera and the position of the air- 
plane at the moment the aerial image was taken are known. 
We can determinate the transformation between the image 
coordinates and the coordinates in the specific model (map 
coordinates) and transform the image primitives into the map 
coordinate system. Assuming that the corresponding con- 
tours are depicted in the map, there are several error sources 
which are responsible for the fact that the line segments ex- 
tracted from the image will not overlap with the map con- 
tours. These are for example inaccuracies in: 
e the extraction of line segments from the image, 
e the determination of the transformation parameters, 
e the acquisition and digitization of the map data. 
Subsuming all these effects, we can safely assume that the 
position of the image primitives is normally distributed around 
their "true" position as given by the specific model. 
For this reason we use as a neighbourhood function f;(z, y) 
for the position of the line segments a Gaussian shaped func- 
tion. However, since we do not want to evaluate differently 
the situations when a short line segment lies in the middle 
of its model line or closer to the endpoints, our function is 
constant along the length of the line. We choose for the 
neighbourhood function f;(xz, y): 
x — zi)sin0; — (y — ty | 
  
202 
EY Roi (- ( 
for positions (z,y) between the endpoints of a line, i.e. 
{(z,y) | (x—=z:)cosOi+(y—y;)sinb; > 0 A (z—x;) cos b; + 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
(y — vi) sin 0; < Li}, and fi(x,y) = 0 otherwise. The neigh- 
bourhood functions f;(z, y) and f; (x, y) for the constellation 
of line segments shown in Fig. 3 are displayed in Fig. 4. The 
variance of the Gaussian is chosen equal to the residual mean 
square error of the transformation. 
For the part of the neighbourhood function, which depends 
from the length of the line, we choose a function which ” in- 
side” the line is proportional to the square root of the length 
and which is 0 "outside": 
a) - f if 1 € [0,1] 
0 otherwise. 
As we will see later, this choice penalizes image primitives in 
an amount proportional to the ratio of their length and the 
length of the model contour. 
The considerations regarding the uncertainty in the position 
of line segments applies also for small deviations of the an- 
gle. Thus, the neighbourhood function for the angle is cho- 
sen following similar reflections. But because the domain of 
definition of the angle is an interval and because we want 
a stronger penalization of large deviations of the angle, we 
use a trigonometric function instead of the Gaussian shaped 
function: 
hi(0) — Ke cos(0 — 0;). 
The constants K;,, Kı and Ks are calculated imposing nor- 
malization for each of the partial neighbourhood functions 
and we can thus assure the fulfillment of condition (2). 
With this choice of neighbourhood functions, the integral for 
the model fidelity is separable into three terms: the position 
fidelity, the length fidelity and the angle fidelity. The integral 
over the product of the neighbourhood functions for the po- 
sition, i.e. the position fidelity can generally not be expressed 
in a closed form. However, if the angle between the two lines 
is small or the parameter c is is in the same order of magni- 
tude as the mean geometric distances between the two line 
segments then a good approximation is given by: 
. ; = Yo 
y: fiz, y) f(z, y)dz dy = 1— X 
( ( ui sin A0 — À ) ( u2 sin Â0 — A )) 
erf | —— | - erf | ———— 
0 V2 +2cos A0? o V2 4- 2cos A0? (5) 
with A8 — 0; —0; and A — —(ri—7j) sin6;-- (yi — yj) cos6;. 
The coordinates u; and u» are the coordinates of the start- 
and of the endpoint of line I; in a coordinate system uOv 
with its origin in the starting point of line /; and with the u- 
axis parallel to the line /;. For a situation as shown in Fig. 3, 
when after a parallel displacement the perpendicular distance 
d between the two lines varies, the position fidelity varies in 
function of d as shown in Fig. 5. 
The integrals over the neighbourhood functions for the length 
and the angle of the line segments can be expressed in closed 
form and result to: 
1 24.32 
| gi(1)g; (Ddl — min(l;, 1j)" 
Ry Ll 
and 
7/2 
/ hi(0)h; (8)d0 = cos(0; Y 0;). 
—T/2 
672 
    
    
   
    
   
    
    
  
  
     
     
   
    
    
    
   
   
   
   
   
  
   
    
  
  
    
    
   
    
   
   
    
   
   
   
   
  
   
  
Figure 
The le 
the sh 
fidelity 
The t 
produ 
Usuall 
in the 
form 1 
step E 
compl: 
of the 
estima 
estima 
segme 
The m 
serves 
instant 
4.2 | 
A diffe 
archicz 
the sin 
image 
we eve 
the sh: 
the sh: 
The cc 
obtain 
the ca: 
object, 
corner 
duced 
into ac 
case w 
an edg 
card a: 
respon: 
the im; 
starting 
after tl 
howeve 
segmer 
To not 
we firs 
model 
the cor 
culate