Recherche approximative de plus proches voisins
Résumé
Content-based retrieval is inherently an expensive process. It is possible, however, to reduce the cost of this process by searching for the approximate neighbors of the query points instead of searching for the exact result. This paper describes a new approach for performing efficient approximate nearest-neighbor searches in high-dimensional databases. It allows a fine and intuitive control over the precision of the search by setting the maximum probability to miss one of the exact nearest neighbors. In addition, we show that our approach is particularly well suited for image recognition based on local descriptors. The imprecision of individual nearest-neighbor searches is totally compensated by the multiplicity of queries.
La recherche d'images par le contenu au sein de grandes bases de données est un processus notoirement coûteux. Il s'avère que l'on peut fortement réduire ce coût si l'on effectue des recherches approximatives. Cet article propose une nouvelle méthode de recherche approximative de plus proches voisins (ppv) qui permet un contrôle fin de la précision de la recherche. Ce contrôle s'exprime au travers d'un seul paramètre qui indique la probabilité maximale de ne pas retrouver un des ppv exacts. Nous montrons de plus que cette méthode est particulièrement bien adaptée au cas de la recherche d'images décrites par des descripteurs locaux. Dans ce cas, la multiplicité des descripteurs par image compense totalement l'imprécision de la recherche.