points. The splines considered here are the
well-known B- splines [Barnhill and Riesen-
feld 1974]. Piecewise cubic polynomials in
parametric form C;(t) = (z(t), y(2), z(t)) de-
fine a curve as a function of the parameter t
such that
Ci(t) = 3 ViBi()
1=0
where V; = (=;,¥;,2;) are the coefficients
of the polynomial and B;(t) are the basis
functions. For the curve to appear contin-
iously smooth, it must have positional, first
derivative, and second derivative continuity
at the break points, also known as knots.
The coefficients of the piecewise polynomi-
als (B-splines) physically define the vertices
of a polygon that guides the splines to trace a
smooth curve (guiding polygon). These ver-
tices are also called control points (see Fig.
1). The control points of B-splines are invari-
ant under affine, and projective transforma-
tions. In addition, the errors incurred for a
linear feature when assuming the invariance
property of the B-spline under a perspective
transformation are small, particularly in the
case of small scale images [Cohen and Wang,
1994].
Cubic polynomials are most frequently used
for splines since they are the lowest order in
which curvature can change sign. Using the
knot points P;, which can be derived using the
critical point detection algorithm mentioned
earlier, the piecewise polynomial coefficients,
which are also the polygon vertices V;, are ob-
tained by solving a set of simultaneous equa-
tions
Vir | 2W | Va
3
6 + ran isism.
Since there are two fewer equations than un-
knowns, two conditions are added for the
open curve case to ensure that the curvature
is zero at both ends of the curve. By adding
these conditions, the number of equations is
equal to the number of unknowns, and the
equations can be solved.
The iterative algorithm of Yamaguchi [Yam-
aguchi 1988] is used to compute the vertices of
the guiding polygon. This algorithm is based
on the idea that the set of equations satisfy
the convergence condition of the Gauss-Seidel
method, and that there is a special relation-
ship among the unknowns (the coefficient ma-
irix is circulant).
3. THE IMAGE MODULE
The goal of this module is to extract road seg-
ments automatically from digital images and
to represent these segments by cubic B-splines
to serve as a model of the roads in image
space. Usually a road segment in an image
contrasts sufficiently with its background, has
a uniform width, and has sufficient length.
The Duda road operator is employed to ex-
tract pixels that most likely belong to road
segments. This low level step is followed
by thinning and road tracking to group con-
nected pixels as road segments. Finally, seg-
ments that belong together are grouped, and
the gaps between them are filled meaningfully.
3.1 The Duda Road Operator
The Duda road operator (DRO) is used to
make explicit the locations which are assigned
the highest likelihood of road presence in the
image. DRO masks are applied in four prin-
cipal directions: horizontal, vertical, right di-
agonal, and left diagonal. For more details
about DRO the reader is referred to [Duda
1973].
Once the image is convolved by the four
masks, every nonborder pixel has four evalua-
tion scores associated with it. The maximum
score for every pixel is retained, and the final
scores are thresholded to keep only the best,
which are then interpreted as producing pos-
itive responses. This procedure is followed by
thinning and road tracking. The road track-
176
ing aims
ments. Fi
as a list of
is used to
3.2 Segm
The roads
tions are I
of noise, p
there 1s a
ments tha
"between t]
ment inte,
main feati
pairs of se;
ment / is €
ment gq, if
other, as g
nearest en
is that the
(relative t
not deviat
segment q
van 1988].
segment a1
gether as «
the gaps I
filled by th
4. TH
This modu
between tl
ages and t
object spa
object spa
ric cubic I
property c
tive transf
of these sj
matching ;
match is c
ods.
4.1 Primi
The coeffic