CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation 
196 
Figure 5: First images retrieved using Brute vote. The 
query has a dark red border, while relevant images have 
a bright green border. 
the relevant image. The same query but with the Ransac 
method is shown on Fig. 7. Images retrieved have less 
than 10 matching keypoints. The removal of non-coherent 
points increases the ranks of relevant images. The im 
provement is thus better than the one of the Angle differ 
ences refinement. 
Figure 6: First images retrieved using the Angle differences 
refinement. 
Figure 7: First images retrieved using the Ransac refine 
ment. 
We have computed the mean best rank among relevant im 
ages for a set of ten queries. We also compared the multi 
curves approach to a linear processing of the database for 
the k-NN search, in order to see the influence of the ap 
proximate search. The ranks and times are shown in Table 
1. 
Method 
mean best rank 
time 
Image matching 
27.09 
11514s 
Linear search 
5.45 
22967s 
Brute vote 
14 
447s 
Ransac 
1.09 
- 
Angle Differences 
7.91 
- 
Table 1: Mean best rank for the first dataset. denotes a 
time not computed. 
As we can see, the time used for the pair-wise compari 
son or for the linear k-NN search are prohibitive. Since 
Brute vote uses Multicurves, which is an approximate k- 
NN method, we should expect some degradation when com 
pared to Linear search, which uses the costly exact k-NN 
search. We note, however, that by using Ransac, the pre 
cision lost is more than compensated. The Ransac refine 
ment has the best results, and is totally satisfactory from 
the users point of view. 
Figure 8: Evolution of the number of relevant images 
against the number of images retrieved. 
We measure the evolution of the number of relevant im 
ages as the percentage of the database retrieved increases 
on Fig. 8. The Ransac method outperforms the other in the 
beginning of the retrieval, but then stops to retrieve images 
(if no coherent affine transform is found, then the image 
has a null vote). The Angle Differences and the brute vot 
ing are less efficient, but still manage to retrieve relevant 
images within the top 10 images. The pair-wise compari 
son fails to showing relevant images within the top 10. 
The precision (ratio between number of relevant images re 
trieved and total images retrieved) is shown on Fig. 9. The 
precision within the first five images retrieved (which is the 
most relevant metric to the user) is better for the Ransac re 
finement. Past this point, all three k-NN based methods are 
almost equivalent. The pair-wise comparison is surpris 
ingly worse than the other methods.