e They are sensitive to absolute intensity, contrast,
and illumination.
e They get confused in rapidly changing depth fields
(eg vegetation).
For these reasons, the existing systems, especially the
ones used in automatic cartography, require the interven-
tion of human operators to guide them and correct them
(Medioni and Nevatia, 1985).
As feature matching necessarily leads to a sparse depth
map only and tends to be confused in densely textured
areas, feature matching should be regarded as comple-
mentary to, rather than as competing with, area-based
matching (Hannah, 1989). The rest of the surface must
be reconstructed by interpolation.
Some advantages of feature-based systems are:
e They are faster than area-based methods, because
there are fewer points (features) to consider;
e The match is more accurate as edges may be located
with sub-pixel precision;
e They are less sensitive to photometric variations,
since they represent geometric properties of a scene
(Medioni and Nevatia, 1985).
Some other advantages noticed while observing matched
lines overlaid on the image pairs was the ability of some
feature pairs to be located correctly, although the sur-
rounding features might vary greatly either due to tem-
poral change or reflectance characteristics due to the ge-
ometry of the system. Also, many elongated features ex-
tracted through the grouping mechanism would be larger
than the pixel windows used in area-based techniques.
4.1 Edge Pixel Determination
Linear features were extracted by convolving the images
with 2x2 pixel windows and grouping the image pixels
upon similar gradient orientation. The pixels are grouped
into so-called line-support regions (LSR). The LSR refers
to a single change in image intensity in a direction nor-
mal to the orientation of the edge. A pair of 8 mutually
exclusive binary images are produced according to the
Overlapping Partitions technique (Burns et al., 1986).
This technique proved to be extremely useful in extract-
ing lines of any orientation by grouping pixels under two
separate partitions of the 0?—360? gradient orientation
spectrum. The critical problem of this approach is the
merging of the two representations in such a way that
a single line in the image is principally associated with
a single LSR. The regions considered best are the ones
which provide an interpretation of the line which is the
longest (Burns et al., 1986).
4.2 Labelling Binary Images
The pixels were grouped on gradient orientation by la-
belling binary images using a modified method of Win-
ston’s technique (Winston and Horn, 1984). Each binary
image is composed of thousands of components (or re-
gions). Lines are fitted to these regions and attributes
determined (e.g. location, orientation, length, contrast,
width and straightness). The location of straight lines
within an image may be determined to sub-pixel accu-
racy.
910
4.3 Fitting Lines to Regions
If the intensity image of an edge and its surrounds is
thought of as a 3-dimensional surface with x and y as the
column and row of the image, respectively, and z as the
intensity of the image then this produces what is termed
an intensity surface. In these terms the line extracted
refers to a step, that is a single change in intensity. The
line extracted does not refer to an intensity surface which
forms a ridge for which there is no distinct location for the
boundaries on either side of the ridge. In Burns view these
narrow linear image events will have a width formed by
two locally parallel lines of opposite contrast (anti-parallel
vectors).
Burns approximates the intensity surface associated with
each LSR with a planar surface. Straight lines are then
extracted by intersecting this fitted plane with a horizon-
tal plane representing the average intensity of the region
weighted by a local gradient magnitude.
The method used here fitted the LSR with its axis of
least inertia, also weighted by local gradient magnitude,
using the Hough parameterization of the line. McIntosh
and Mutch’s method (McIntosh and Mutch, 1988), also
uses moments of inertia, however, edge pixels were not
weighted.
The axis of least inertia passes through the centroid of
the area. Least squared error line fitting with this form
of line equation (as opposed to slope-intercept) minimizes
errors perpendicular to the line (as opposed to those per-
pendicular to one of the coordinate axes) (Ballard and
Brown, 1982).
Deriving the orientation of the axis requires least-square
fitting by minimizing the sum of the squares of the dis-
tances of the pixels from the line using the Hough (p, 0)
parameterization of the line.
Figure 2 shows a frequency histogram of line lengths for a
subimage with center pixel coordinates (2750,3250) with
respect to the main image. The frequencies for lengths up
to and including 1 and 2 were omitted due to their very
large number which may be partly attributed to noise.
The thresholds placed on line length in the program pro-
vides a good filter on noise and poor quality lines. The
frequencies decline very rapidly for increasing line length.
4.4 Average Intensities
The average intensity of the whole subimage was deter-
mined before the gradient magnitude threshold and line
length threshold were set. A lower threshold was used
for the relatively dark, featureless subimages. A higher
threshold for the brighter subimages with more densely
spaced cultural (artificial) features. This serves the dual
purpose of maximizing the information retrieved from the
dark areas, while limiting the wealth of data to be ana-
lyzed from the high spatial-frequency areas.
A brief analysis of the relationship between subimage
average intensity and the number of lines produced of
various lengths was performed to ascertain whether any
trends occurred. This was to limit if possible the volume
of data produced in the city scenes, while at the same
time maximize the data from the relatively dark and fea-
tureless subimages.
The frequency of lines with various length ranges was dis-
played on a square root scale as the features are extracted
