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