SL
SION
zz
Figure 2: Manhole cover: intensities (left), intensity plot (center); adapted model (right).
Thus, in our experiments we are able to automatically
extract 25% to 30% of all the landmarks visible in the im-
ages, while the number of false detections is reasonably low.
Figure 3 illustrates a result obtained on a small image subpart.
3. MATCHING LANDMARK CONSTELLATIONS
WITH A LANDMARK DATABASE
Given both, the positions of the landmarks detected in an
image and a database containing the geodetic coordinates of
all landmarks that are known to exist in the observed area,
we now have to solve the problem of identification, i.e., to
find the correct correspondences between the two sets. Find-
ing these correspondences automatically provides us with the
ground control information required to perform an estimation
of the exterior orientation parameters automatically.
3.1. The Nature of the Matching Task
An important characteristic of the given matching task is
that, in general, we cannot identify or distinguish individ-
ual manhole covers on the basis of their visual appearance.
Therefore, a matching algorithm can only exploit geometric
relations of sets of manhole covers. This implies that we can-
not decide about the correctness of a single correspondence;
rather, correctness is defined on a set of correspondences: To
represent a correct total match, the set has to be geometri-
cally consistent, i.e. there must be a perspective transforma-
tion which relates a sufficiently large fraction of the image
landmarks with database landmarks resulting in sufficiently
small residuals.
It is also important to note that we have to match large sets
of landmarks. This demands an effective control of the search
mechanism in order to prevent a combinatorical explosion. It
is obvious that, for combinatorical reasons, we are not able to
systematically try all possible sets of point-to-point matches.
Instead, the matching process is based on characteristic con-
stellations among the landmark sets whose specifity reduces
the ambiguities in the candidate selection process. In the fol-
lowing, constellations of image landmarks will be termed im-
age constellation while we denote constellations of database
landmarks by the term database constellation.
One possibility would be the use of very specific constellations
like subparts of the road network, knowing that this network
is clearly reflected in the spatial arrangement of the manhole
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
covers. However, we decided not to use complex types of
constellations for two reasons: First, only a small subset of
the landmarks included in the database is actually visible and
detectable within the image, and second, the set of detec-
tions includes a significant fraction of landmarks which do
not correspond with a database landmark (false detections as
well as manhole covers which are located on private ground
and, thus, are not included in the municipal register). As a
consequence, there might be a very low chance that a com-
plex pattern defined on the database landmarks can also be
found within the set of detections. In order to deal with this
kind of incompleteness and erroneousness we decided to use
rather simple types of constellations (to be discussed below),
thereby accepting that we are still faced with a lot of ambi-
guities in this case.
3.2. Matching Constellations by Hypothesize-and- Test
We overcome the problem of ambiguity by applying a
hypothesize-and-test mechanism: First, we randomly select a
set of image landmarks which make up a valid constellation.
For this image constellation we determine all possibly
matching database constellations. This is done by indexing
through geometric invariants for reasons of efficiency. Given
an image constellation and several candidate database con-
stellations, we then hypothesize a match between the image
constellation and one of the candidates. As indicated above,
we can verify (test) such a hypothesis by estimating the
orientation parameters from the landmark correspondences
given by the constellation match and scoring the number of
"hits". The number of hits is determined by transforming the
coordinates of the image landmarks into world coordinates
(which presumes that a digital elevation model is available)
and doing a nearest-neighbor search among the database
landmarks within a small search radius (e.g. 1.5 m in
physical dimensions). When the number of hits obtained
in this way is too small (i.e. only a small fraction of the
detections can be "explained" in this way), we consider the
next candidate from the indexed database constellations. If
the verification fails for all candidates, we randomly select
a new image constellation. The idea behind this method is
that it will succeed with a large number of hits for perfect
image constellations, while for a faulty image constellation
it fails yielding only a small number of hits. By the word
perfect we denote those image constellations which do not
include any false detections or manhole covers not registered
in the database. Knowing the size of the constellations used
148
Figure 3: F
left side, sr
cross cente
Note, that
as well as
erroneous
specify the
a perfect ii
total matc
1. Prey
stell
2. Ran
up e
3. Det
tion
4. Sele
con:
5. Esti
lanc
hits
6. Wh
old,
unu
tinu
Note that
result—i.e
the verific
eters base
Since we
dences pe
Thus, bas
landmarks
for outlier
finally enl
well as to
in the lan
