0.2 
  
0.15} 
0.17 
h(n) 
0.05} 
  
  
  
  
0.8} 4 
0.6 
IH(w)l 
04r 4 
02r 4 
  
  
  
0 A 1 L eme tee A a 
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 
w/pi 
Figure 2: Low-pass filter for the % — s curve: ımpulse re- 
sponse and magnitude of the frequency response 
  
s(n) 
  
  
  
  
  
s‘(n) 
  
  
  
  
Figure 3: An example of filtering a 1-D sequence by the 
equiripple low-pass filter 
2.2 Segmentation in % — s domain 
In order to easily detect circular arcs in addition to straight 
lines, the y —5 domain can be used. In this domain, straight 
lines appear as horizontal lines, and circular arcs as arbi- 
trary straight lines. Since both straight lines and circular 
arcs appear in the y) — s domain as straight lines, we can 
use the split-and-merge algorithm described in section 2.1 
to segment the y) — s curve and get as a result both the 
straight lines and the circular arcs. 
As described earlier, the input is a list of points in a 
3-D continuous coordinate system. Since this input is de- 
rived from a discrete 2-D representation, noise effects that 
were produced during the scanning of the original aerial 
photographs cannot be avoided. The y — s method is very 
sensitive to noise. À point in the spatial domain that 1s dis- 
placed by approximately the distance between two neigh- 
boring points will cause ~ 45° “offset” in the y — s curve. 
Therefore, the original data should be filtered by a low-pass 
filter. Since the breakpoints we try to detect are also high 
frequency phenomena, they will be affected too. In order to 
compromise between noise removal and information preser- 
vation, a filter with few coefficients should be used. We used 
the Parks-McClellan equiripple algorithm (Rabiner et. al, 
1975) to design such a filter. The equiripple method mini- 
mizes the maximum error between an ideal (infinite length) 
low pass filter and a filter with a truncated number of co- 
efficients. By this, an optimal filter can be achieved for a 
524 
given set of specifications. This set includes the cutoff fre- 
quency, the transition band, a weighting function for the 
errors in the pass and the stop bands, and the number of 
coefficients. Recursive or nonlinear filters (Wuescher and 
Boyer, 1991) are alternate solutions to the filtering prob- 
lem. The impulse and frequency responses of the filter are 
shown in figure 2. Figure 3 shows a noisy 1-D sequence 
before and after filtering. In the case of 3-D edges, all three 
coordinates are convolved separately with this filter. 
The % — s domain in 2-D space consists basically of a 
plot of the orientation (V) versus length (s) of the original 
spatial curve. In this representation, the slope of the line 
corresponds to the curvature of the original curve. There- 
fore, it can be easily shown that a straight line in the spatial 
domain appears as a horizontal line (parallel to the s axis) 
in the  — s domain, and a circular arc (which has a constant 
curvature) appears as an arbitrary straight line. The y — s 
curve for a nonanalytical spatial curve is constructed by 
computing the directions between points. In order to over- 
come some residual noise effects, we calculate the direction 
at a certain point not between the point and its neighbor, 
but between its predecessor and successor. In cases of more 
extreme noise residuals, a larger interval can be used for 
calculations. 
In order to segment the % — s curve, discontinuities 
should appear only at breakpoints. An artificial discon- 
tinuity is present when the original curve orientation goes 
from 360° to 0° or vice versa. Hence, after representing 
the curve in the y — s domain, this artificial discontinuity 
is eliminated. The procedure is described by the following 
pseudo code, where c is a parameter which compensates for 
the discontinuity: 
Discontinuity elimination1() 
l. let p1 ... p, be the list of points of the  — s curve 
2.0 
3. Vi, 2<i<n 
3.1 Vi = Vi + € 
3.2 if lv; m Vii 2 180? then 
e ifyi 2 yia 
then y; :— y; — 360°; c:= c — 360° 
else v; :— 9; + 360°; c :— c 4- 360? 
With this procedure no changes in orientation of more 
than 180? will occur. 
We have extended the y — s approach to 3-D. A hor- 
izontal angle a and a vertical angle ¢ are used to express 
the spatial direction. Again, a straight line in the spatial 
domain appears as a line which is parallel to the distance 
axis of the 9» — s domain. A circular arc, contained in an 
arbitrary plane in the 3-D space, appears as an arbitrary 
straight line in the 3-D y — s space. 
Special attention must be paid when the tangent of a 
circular arc at a certain point becomes vertical. This situ- 
ation is described by the following: 
|; — a;_1| = 180° 
|] = 1$; = 90° 
Di 7 di 
Careful examination reveals the gradient of ¢ changes its 
sign leading to a discontinuity of the vertical angle. In 
Fi 
orde 
proc 
into 
Disc 
Figui 
o! an 
T 
of the 
possi 
done 
the c 
break 
segmi 
O 
repre: 
segme 
rithm 
is a li 
straig 
spatiz