Ze is
from
hine
3-D
atia.
hine
and
lysis
7-8
ima-
RECOGNITION OF ROAD AND RIVER PATTERNS BY
RELATIONAL MATCHING
Norbert Haala and George Vosselman
Institute of Photogrammetry, Stuttgart University
Keplerstrafie 11, D-7000 Stuttgart 1, Germany
ISPRS Commission III
ABSTRACT:
This paper discusses a procedure aiming at the automatic exte-
rior orientation of images. To this purpose the relational match-
ing method is used to match relational descriptions of images
and maps. Because roads, rivers and land parcels often con-
stitute unique structures, these topographic features are taken
as the basic elements of the descriptions and are used to iden-
tify and locate landmarks like road crossings, waterway junctions
and specific parcel structures. The structural descriptions of the
images are obtained by thresholding selected channels of colour
images and subsequent thinning of the linear structures. Tree
search methods are used to match the derived relational image
descriptions with hand made descriptions of the landmarks.
KEYWORDS: Artificial Intelligence, Image Interpretation,
Feature Extraction, Pattern Recognition
1 INTRODUCTION
In recent years it has been shown that several important pho-
togrammetric tasks, like the relative orientation of images, the
aerial triangulation and the derivation of digital terrain mod-
els, can be automated with digital image processing techniques
[Schenk et al. 1991, Tsingas 1991, Ackermann and Krzystek
1991]. The main concern in solving these tasks is to establish
correspondences between (patches of) the overlapping images.
Using the area based or feature based correspondence algorithms
that have been developed over the last decade, homologous points
indeed can be found.
Another group of tasks, including the exterior orientation of im-
ages and mapping of images, also is a research topic, but the
progress in the automation of them is much slower. Like the
ones mentioned above, these tasks also have to be solved by deter-
mining a correspondence. However, this is not a correspondence
between two images, but a correspondence between an image and
a model of the contents of this image. E.g., for the exterior orien-
tation of an image one has to determine a match between image
patches and models describing the control points. The automa-
tion of the mapping process involves a comparison of the image
with generic models that define the expected appearances of the
roads and houses in the image. The need to model the image
contents makes these tasks relatively hard to automate.
This paper deals with the automatic exterior orientation of im-
ages by matching images to descriptions of natural control points
(landmarks). Compared to the mapping task, this problem has
the advantage that one can select the landmarks one wants to
measure. Le., those landmarks can be utilized that are relatively
easy to model and easy to recognize.
The landmarks we use for the orientation are described by rela-
tional descriptions. The reason for this choice is twofold. First,
the description has to be feature based, because area based de-
scriptions (i.e. grey values) would depend on the season and the
weather conditions which are difficult to model. Second, a de-
scription by features only usually does not contain enough infor-
mation to recognize a landmark, because the approximate values
969
of position and rotation that can be obtained from the flight plan
are very inaccurate. Le., the image patch in which a landmark
has to be found will contain many features that do not belong to
that landmark. The risk of matching the wrong features is there-
fore relatively high. This risk can be reduced by using the struc-
tural information that is contained in the relationships between
the features. This structural information can well be represented
in relational descriptions.
In aerial photographs such structural information is present in
landmarks like road crossings, river junctions and land parcels.
The relational descriptions we use in the matching step therefore
consist of roads, rivers and parcel boundaries and their topolog-
ical and geometrical relations. So, the problem of recognizing
a landmark is defined as the problem of matching a relational
description of an image patch to the relational description of the
model of the landmark. This problem can be solved with the
relational matching method [Shapiro and Haralick 1981]. In con-
trast to the usual least squares methods, this method does not
require approximate values for the position or the orientation.
The next section describes the extraction of the relational de-
scriptions from the colour images. The relational descriptions of
the landmark models were obtained by digitizing maps. Section
3 deals with the evaluation of the correspondences. The task of
the matching algorithm is to find the best mapping between the
features of the image and the features of the model. To this pur-
pose one needs a quantitative evaluation measure that describes
the quality of the mappings. With the tree search methods, that
will be described in section 4, one then can select the best map-
ping. Throughout the paper the different processing steps are
illustrated by an example of the location of a road junction. Sec-
tion 5 shows and discusses the results on the location of this and
five other landmarks.
2 STRUCTURAL DESCRIPTION
In order to get a comparable representation of the image object
and the landmark, structural descriptions were extracted from
the image and the landmark. They describe the selected image
objects and the landmark model in terms of geometric primitives
(points, lines, and regions) and their relations. To obtain an ex-
pressive description, objects containing sufficient structure like
roads, rivers and cornfields were used. The relational image de-
scription was derived automatically from a colour image in two
steps. First, an appropriate band of a colour image was selected
to compute a binary image by classifying pixels that belong to
the objects of interest. Secondly, the binary image was vectorized
by a contour tracing, respectively a line tracing algorithm, and
the relational description was extracted.
The structural descriptions of the landmarks were obtained by
digitizing maps, but, in principle they could also have been de-
rived from a geographic information system (GIS).
