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