‚ and the
chi [Yam-
vertices of
1 1s based
ns satisfy
uss-Seidel
relation-
cient ma-
LE
road seg-
ages and
B-splines
in image
an image
bund, has
+ length.
ed to ex-
y to road
followed
oup con-
ally, seg-
ped, and
ningfully.
used to
assigned
ce in the
our prin-
right di-
e details
io [Duda
the four
r evalua-
1aximum
the final
the best,
"ing pos-
lowed by
id track-
ing aims at connecting pixels to road seg-
ments. Finally, each road segment is stored
as a list of pixel coordinates; a size threshold
is used to eliminate short segments.
3.2 Segment Grouping
The roads extracted by the previous opera-
tions are highly fragmented due to the effect
of noise, poor contrast, and occlusions. Thus,
there is a need for a procedure to group seg-
ments that belong together and fill the gaps
between them in a meaningful way. The seg-
ment integration process is based upon two
main features: proximity and alignment of
pairs of segments. As a first requirement, seg-
ment [ is considered to be a neighbor of seg-
ment q, if | and q are reasonably close to each
other, as gauged by the distance between their
nearest end points. The second requirement
is that the trend or alignment of segment I
(relative to the end that is nearest q) does
not deviate too much from the alignment of
segment q (at q's end nearest to I) [Vasude-
van 1988]. After the valid neighbors of every
segment are determined, they are grouped to-
gether as continuous road segments. Finally,
the gaps between the grouped segments are
filled by the process of fitting cubic B-splines.
4. THE MATCHING MODULE
This module aims at finding the best matches
between the roads extracted from digital im-
ages and their corresponding 3-D models in
object space. The roads in both image and
object spaces are represented by paramet-
ric cubic B-splines. These splines have the
property of shape invariance under projec-
üve transformation. Thus, the coefficients
of these splines form the primitives for the
matching process. The search for the best
match is conducted using tree search meth-
ods.
4.1 Primitives and Relations
The coefficients (vertices) of the splines form
the primitives, while the distances between
the vertices describe the interrelationships be-
tween these primitives. The segmented roads
in object space are represented by a sequence
of vertices of the guiding polygon as follows:
a vertex O; is represented as (.X;, Y;, Zi, 6;),
where X;, Y;, Z; are the coordinates of the ver-
tex and 6; is the angle it encloses. The seg-
mented roads in image space are also repre-
sented by a sequence of the vertices of the
guiding polygon: a vertex L; is represented
as (z;, 9, ;), where z;,y; are the image co-
ordinates of the vertex and o; is the angle it
encloses. 'The distance 7; between two suc-
cessive vertices in object space describes the
relationship between these vertices. In addi-
tion, the distance R; between two successive
vertices in image space describes the relation-
ship between these vertices. The distances in
image and object space are related through
the image scale.
4.2 The Matching Problem
The matching problem between the object
model M;(O, T), where O and T are the vec-
tors of primitives and relationships of the ob-
ject model, and the image model M;(L, R),
where L and R are the vectors of primitives
and relationships of the image model, is sim-
ply to find a mapping f between primitives
O and L. Since there may be many possi-
ble mappings f : L — O, a measure has to
be introduced, which evaluates the quality of
the mapping between two primitives. Intu-
itively, the evaluation of a mapping should
depend on the similarity of the attribute val-
ues of the corresponding primitives and rela-
tions. The approach to find the best mapping
is called the inexact cosistent-labeling prob-
lem [Shapiro and Haralick, 1985].
Inexact consistent-labeling utilizes the con-
cept of a cost function. For every possible
mapping between the object model and the
image model, a cost is considered based on
the similarity of the corresponding primitives
and relations. The best mapping is the one
177
