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