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