ght).
use complex types of
only a small subset of
e is actually visible and
ond, the set of detec-
Xf landmarks which do
ark (false detections as
ated on private ground
inicipal register). As a
ow chance that a com-
landmarks can also be
order to deal with this
ness we decided to use
to be discussed below),
ced with a lot of ambi-
lypothesize-and-Test
biguity by applying a
it, we randomly select a
ip a valid constellation.
jetermine all possibly
his is done by indexing
ons of efficiency. Given
andidate database con-
itch between the image
es. As indicated above,
esis by estimating the
dmark correspondences
| scoring the number of
ned by transforming the
into world coordinates
tion model is available)
h among the database
radius (e.g. 1.5 m in
umber of hits obtained
a small fraction of the
s way), we consider the
-abase constellations. If
tes, we randomly select
a behind this method is
mber of hits for perfect
ulty image constellation
r of hits. By the word
stellations which do not
ole covers not registered
f the constellations used
nna 1996
Figure 3: Results of the landmark extraction scheme applied to a small sub-image which shows five manhole covers. On the
left side, small circles indicate the potential landmarks detected by normalized cross-correlation. In the final result (right) the
cross centers correspond to the estimated landmark centers while the radii of the circles correspond to the values of rin.
Note, that one of the visible landmarks has been rejected by the verification procedure due to its high approximation error.
as well as the average ratio between correct detections and
erroneous ones (from our extraction experiments), we can
specify the mean number of random trials required to select
a perfect image constellation, which should give a successful
total match. In summary, the algorithm proceeds as follows:
1. Prepare the database by constructing all database con-
stellations according to the rules to be specified below.
2. Randomly select a set of image landmarks which makes
up a valid image constellation.
3. Determine all possibly matching database constella-
tions through geometric indexing.
4. Select an unused candidate from the indexed database
constellations.
5. Estimate the orientation parameters based on the given
landmark correspondences and score the number of
hits.
6. When the number of hits is higher than a given thresh-
old, stop with success; otherwise, when there is still an
unused candidate, continue with step 4; otherwise con-
tinue with step 2.
Note that in case of a successful total match, the desired
result—i.e., the exterior orientation—is already available from
the verification step which determines the orientation param-
eters based on a maximum number of landmark matches.
Since we can expect to yield a high number of correspon-
dences per image (50-100), the estimate is highly reliable.
Thus, based on a reliable estimate it is possible to recognize
landmarks with significantly distorted coordinates by looking
for outliers in the residuals. Such an analysis enables us to
finally enhance the result by excluding detected outliers as
well as to examine the accuracy of the coordinates included
in the landmark database.
3.3. The Type of Constellations Used
We now have to define the type of constellations to be used
in our approach. The matching algorithm sketched above
implies a number of criteria to be considered in this context:
e |t should be possible—with respect to time and stor-
age capacities—to precompute all valid constellations
among the database landmarks.
e There should be a high probability that constellations
of the desired type can be found among the landmarks
detected in the image. This excludes complex constel-
lations which are specific but also sensitive to missing
or additional features.
e There must be an efficient method to access all possi-
bly matching database constellations for a given image
constellation.
e To limit the computational effort required to estimate
the orientation parameters and to transform the coordi-
nates, the number of candidate database constellations
associated with a given image constellation should be
small.
e The probability for randomly selecting a perfect image
constellation should be high.
Trying to find a trade-off between specifity and robustness, we
considered two types of constellations: triples and five-tuples.
The most serious argument for using small-sized n-tuples is
given by the last criterion from the list above: The probability
for randomly selecting a perfect n-tuple decreases exponen-
tially with increasing n; Table 1 reveals the consequences of
this relationship. The experiments reported in Section 2.4
have shown that the set of detections typically includes a
fraction of false detections in the range of 10% to 20% (see
149
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
JA“
