itoff fre- 
for the 
mber of 
her and 
1g prob- 
ilter are 
equence 
all three 
r. 
ally of a 
original 
the line 
There- 
e spatial 
> 8 axis) 
'onstant 
he Pp — 8 
cted by 
to over- 
lirection 
eighbor, 
of more 
used for 
tinuities 
discon- 
on goes 
esenting 
ntinuity 
ollowing 
sates for 
curve 
of more 
A hor- 
express 
spatial 
distance 
d in an 
rbitrary 
ent of a 
his situ- 
nges its 
gle. In 
    
; a=45° 02225? 
$'-90? +Ab 
  
X 
Figure 4: Compensation for an artificial discontinuity 
order to eliminate this discontinuity problem, the following 
procedure is added to the transformation of a spatial curve 
into the  — s domain: 
Discontinuity. elimination2() 
1. let p1...p, be the points of the  — s curve, c bea 
compensation factor for the horizontal angle, z be a 
zero elevation base for the vertical angle, and s a sign 
factor 
2. 6c:109 2—0*..5-—1 
3. V 2siSmn 
Jl o;:—-o;ctc6 di: Ji zs 
3.2 if (Jo; — o;1| & 180?) & 
(ld; — =| = |Gi-1 — z| = 90°) & 
(¢: = ¢;_1) then 
321. if Qi 0;1 
then c := c— 180?; aj; : a; — 180° 
else c :— c 4- 180*; oj :— o; 4- 180? 
3.2.2. if (($ — z & 90?) & (s — 1)) or 
((é — = = —90*) & (s — -1) 
then z :— z + 180°; ¢; := ¢; + 180? 
else z :— z — 180°; ¢; := ¢; — 180° 
Figure 4 shows a case where the compensation is necessary. 
a’ and $' are corrected angles. 
The disadvantage of this approach is that the restoration 
of the original spatial curve from the y) — s curve is no longer 
possible. However, the conversion into the y — s domain is 
done for approximating the location of the breakpoints on 
the curve. We can certainly store the indices of the found 
breakpoints, go back to the original spatial domain, and 
segment the original curve according to these breakpoints. 
Once we have a V — s curve which does not contain 
representation related discontinuities, the simplest way to 
segment it into straight lines is by the split-and-merge algo- 
rithm described in section 2.1. The result of this operation 
is a list of straight lines in the % — s domain. Each of these 
straight lines is examined and classified into one of three 
spatial domain categories, namely, straight line, circular arc 
525 
(b) 
  
Figure 5: Synthetic data: (a) clean; (b) noisy 
or “other,” i.e., natural lines or noise effects, according to 
the following order of criteria: 
e If thelineis shorter than a predefined threshold value, 
it is classified as “other.” 
e If the slope of the line is less than a predefined thresh- 
old value, it is classified as straight line. 
e The radius, arrow and angle of a circular arc are es- 
timated from the slope and first and last points of a 
V — s segment. If these parameters are within a pre- 
defined interval, the segment is classified as a circular 
arc. 
e In other cases, the segment is classified as “other.” 
3 EXPERIMENTAL RESULTS 
Both the split-and-merge and the y) — s methods were im- 
plemented and tested with synthetic and real data. Not all 
the experiments have been completed yet, leading to more 
results with real data. 
The synthetic data were produced by combining a set 
of straight lines and circular arcs in 3-D space, which were 
then corrupted by noise that was produced by a pseudo- 
random number generator. The magnitude of the noise 
was chosen in a way that mimics the behavior of real data. 
Figure 5 shows the clean and noisy synthetic data as 3-D 
curves. The real data were taken from the results of the 
matching process, consisting of lists of 3-D points. Figure 6a 
shows the left image of the stereo pair which was used for 
the production of these edges. The 3-D edges are shown in 
figure 6b in an orthogonal projection. 
3.1 Split-and-merge results 
The split-and-merge algorithm was implemented according 
to the description in section 2.1. In general, the offset 
threshold can be derived directly from the scale and the 
scanning resolution of the aerial images, and it should be 
larger than the size of a pixel in object space. The aerial 
photographs we used have a scale of approximately 1/4000, 
and the scanning pixel size is approximately 60 um. There- 
fore, a pixel size in object space is ~ 0.25 m. We selected 
a value which is slightly higher, taking into account also 
other noise effects. The threshold was the same for both 
the split and the merge phases of the algorithm. 
Synthetic data: Testing the split-and-merge proce- 
dure on the synthetic data did not present any troubles in 
the segmentation, just as we anticipated. The straight lines