CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation
1. For each points in the query, find the k-nearest neigh
bours (k-NN) in the database.
2. For each neighbour found, add one vote to the corre
sponding image.
3. Rank image by descending number of votes.
Figure 1: Panoramic view of the Place de la Nation from the project iTowns.
image (Fig. 2). The SIFT descriptor consists in a 128-
dimensional vector containing a set of gradient orientation
histograms.
it induces a sequential, linear-time, processing, which is
unfeasible for large databases. Hence, instead of finding
best matches between keypoints of query and target im
ages, the best matches are found between the query and
the keypoints in the entire collection. The retrieval scheme
is as follows :
Figure 2: SIFT points of interest with respecting scales.
The classic method to use keypoints for image matching is
pair-wise image comparison. For all points of a query im
age A, find the best matching point in a target image B. If
the resulting match has good contrast (i.e. the distance of
the query point to the best point in B is far less than the dis
tance to the second best, meaning that the query point has
only one corresponding target point), add a vote to B. An
example of matching points is shown on Fig. 3. The best
image in the database corresponding to the query image is
the one with higher votes.
Figure 3: SIFT points matching between a query taken
with a mobile phone and an image from the iTowns
database.
One of the problems of pair-wise image comparison is that
The main difference with pair-wise comparison is that each
keypoint of the query has k associated matches. Thus,
points of the query with no corresponding points in the
database (points of objects that are not in the database for
instance) will still vote. Those votes are randomly dis
tributed among images and thus contribute to increase the
ranking of irrelevant images.
In order to remove the influence of those irrelevant points,
a geometrical constraint is applied to the matches, remov
ing points in the target that are not coherent with the spatial
distribution of points in the query.
3 APPROXIMATE K-NN SEARCH
There are several techniques for efficient kNN search on
large databases, like the KD-tree (Friedman et al., 1976),
the LSH (Indyk and Motwani, 1998) or projective methods
(Kleinberg, 1997). A comprehensive study can be found in
(Valle, 2008). Those methods are all approximate because,
in order to obtain more efficiency they sacrifice exactness
in the name of speed. That means that they find the correct
answers with good probability, but not certitude.
We have chosen Multicurves (Valle et al., 2008), a method
based on space-filling curves, which are fractal curves able
to map the dimensions of the input space into an one-dimen
sional space, while locally preserving the order (i.e., putting
near in the curve point which are near in the space). The
one-dimensional data can then be indexed using traditional
efficient techniques.
The particularity of Multicurves is using several of those
curves at once: first, it projects the input space into a few
moderate-dimensional subspaces, then it uses one space
filling curve to index each one of those subspaces. This
allows the method to better manage the problems associ
ated to high-dimensional indexing. In our experiments, we
have used Multicurves with 4 curves, each of them index
ing 32 of the 128 dimensions that compose the SIFT input
