tuple size #trials for an error rate of
n 20% | 30% | 40% 50%
3 2.0 2.9 4.6 8.0
4 2.4 4.2 17 16.0
5 3.1 5.9 12.9 320
10 9.3 | 35.4 | 165.4 | 1024.0
Table 1: Mean number of trials required to randomly select
a perfect n-tuple of detected landmarks.
above). Moreover, about 20% of the detections typically
represent manhole covers which are visible in the image but
which are not included in the cadastral database, for several
reasons. Thus, we have to expect that only about 60% of all
detections actually correspond with a cadaster landmark (i.e.
the “error” rate here is about 40%). This clearly favors the
use of small-sized constellations in order to keep the number
of random trials as small as possible.
To enable the precomputation of all database constellations
we have to restrict the resulting combinatorics. This is done
by constraining the pairwise distances of the constellation
landmarks. Thus, for a given database landmark we only
have to consider its neighbors located within a certain mini-
mum and maximum distance in order to construct all possible
constellations. Searching for the neighbors can be supported
by using a spatial index provided by a spatial database. Ad-
ditionally, for a triple we demand that the three altitudes of
the “triangle” represented by the three landmarks also exceed
the minimum distance threshold. The purpose of this rule is
to exclude nearly collinear tuples which would lead to less
reliable estimates for the orientation.
Since we deal with nearly vertical imaging conditions and
with more or less flat urban areas, in a first approximation
distances can be assumed to be “invariant” up to a common
scaling factor. Thus, the minimum and maximum distance
thresholds can be transformed to pixel distances knowing the
approximate value of the image scale and the pixel size. Using
the scaled distance thresholds we can construct image con-
stellations in the same way as described for the database con-
stellations. The distance thresholds should be small enough
to effectively restrict the total number of valid constellations
in the precomputation phase. They should be large enough
to ensure that we can find a sufficient number of detections
within the resulting search area in the image, giving a suf-
ficiently high probability for constructing perfect image con-
stellations. In general, we can assume that the deviations
from vertical geometry are sufficiently small to ensure that
for a valid database constellation there exists a valid image
constellation—provided that the involved landmarks are ac-
tually detected in the image—and vice versa. However, we
have to accept that we will miss some constellation matches
due to the uncertainties resulting from deviations from ver-
tical imaging, from neglecting elevation variations, and from
the limited accuracy of the cadastral coordinates.
3.4. Candidate Selection Through Indexing
As mentioned above, our approach includes an efficient candi-
date selection mechanism which is based on indexing through
certain geometric properties of the constellations. While, in
principle, this technique is applicable to both, triples as well
as five-tuples, there are some arguments which favor the use
150
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
of triples here. In order to justify our decision to use triples in
our final implementation, we discuss these arguments below.
It is well known that for a set of correct correspondences the
positions in the image and in the world are related by a pro-
jective transformation; moreover, we know that there exist
certain geometric properties of point constellations which are
invariant under perspective projection, e.g. the cross-ratio of
four collinear or five coplanar points. Thus, using five-tuples
(and assuming that the 3D-coordinates of the landmarks do
not deviate from a plane too much) would suggest to use
their cross-ratio as indexing key. In this case, we would pre-
compute the cross-ratio for all database constellations and
make according entries in an index table. In the matching
phase we would compute the cross-ratio for each given image
constellation and use it as an index to this table (see (Meer
et al., 1993) and (Lenz & Meer, 1994) for an instructive
discussion on the use of projective invariants for matching).
However, due to the uncertainties mentioned above and due
to geometric similarities that might occur among the individ-
ual constellations, we have to accept that there is no unique
relationship between image constellations and database con-
stellations. While, in our application, this holds for most
kinds of geometric properties, the use of the cross-ratio en-
tails some specific problems: First, requiring a number of five
landmarks per constellation increases the mean number of
random trials required in the matching process (see above).
Second, using the full degrees of freedom provided by a per-
spective projection does not reflect the strong restrictedness
of the nearly vertical imaging geometry. As a consequence,
the matching algorithm will be faced with some additional
ambiguities which could be excluded under the assumption of
almost affine conditions. And third, the uncertainties men-
tioned above will lead to non-ideal correspondences of the
cross-ratio values to be compared. While this is inevitable,
we have to note that it is hard to assess distances of ratios
due to their highly non-linear nature.
Therefore, we prefer to use triples instead of five-tuples in
our matching approach and decided to implement an index-
ing method based on their ordered set of landmark distances.
Using only three landmarks gives a low number of random
trials required; analyzing their (scaled) distances does reflect
the restricted imaging conditions quite well; and it is also
more obvious how to evaluate Euclidean distances between
points than distances of cross-ratios. The implemented in-
dexing mechanism proceeds as follows: To get a unique rep-
resentation for a given triple we first put the three coordinates
in a counter-clockwise circular order according to their spa-
tial arrangement and compute the distances between each
point and its successor (in the case of image landmarks, the
pixel distances are transformed into world distances by scal-
ing with the approximately known scaling factor). Finally,
we create a linear list of the three distances following the
counter-clockwise order of the points and starting with the
largest distance value. This gives a uniquely defined distance
vector carrying its largest element in the first place. For the
database triples we use this vector to create a three-level index
table. Thus, given a triple of image landmarks we compute
its associated distance vector and use this for indexing the
candidate table which requires three table access operations.
3.5. Veri
For a given
timate the
This techn
a hypothes
for small se
tation mig
criterion by
perfect im:
tation will
ber of addi
neighbor se
cluded in t
reliable est
of correspc
bined step
neighbor s
of landmai
when the :
the curren
anism yiel
significant
fect image
rect datab.
process stc
spondence
matching |
correspond
In order to
ative regist
constellatit
corresponc
will see be
be submitt
siderably k
3.6. Exp
Our appro
plemented
tected lanc
covering tl
we will dis
central ar«
burg) and
(see Sectic
mark data
from an ar
ers about
within the
ers are ac
are distort
a number
obtain sat
50 m (mir
Using thes
algorithm
the pairwi
criterion.
ate a thre
discretizat
which mig
