Méthodes rapides pour la recherche des plus proches voisins SIFT : application à la recherche d'images et contributions à la reconstruction 3D multi-vues
Institution:
Paris 5Disciplines:
Directors:
Abstract EN:
In the first part of this thesis, we are concerned by the nearest neighbour problem, applied on local image descriptors. We restricted ourselves to the SIFT descriptors because of its efficiency. The application of this work is the retrieval of similar images in large databases. First, we compare performances of linear search, on CPU and on GPU (graphic processors), and also when using partial distances. Then, we propose new hash functions t solve the approximate nearest neighbours problem. The hash functions we propose are based on a selection of a few distinctive dimensions per point. For the application of near duplicate retrieval, our algorithm is more efficient than state-of-the-art algorithms. Tested on a database containing 500. 000 images, it finds similar images in less than 300ms. Eventually, we show that it fits very simply within a Bag-Of-Features approach, and it retrieves mor images than kmeans based vocabularies. In a second part, we propose several results on the problem of multi-view 3D reconstruction. We first propose a robust method to obtain the 3D reconstruction of a car from a video sequence. Our system uses the hypothesis that the car is in linear translation in order to fit a point cloud with polynomial surfaces. Then, we propose an algorithm, not dedicated to cars, that uses SIFT descriptors to obtain the 3D surface from images of an object. The descriptors correspondences are searched between input images and virtual images of the temporary object. With this method, the reconstructed surface converges to the true surface object.
Abstract FR:
Dans la premiere partie de cette thèse, nous nous intéressons à la recherche rapide de plus proches voisins de descripteurs locaux d'images. Nous nous sommes concentrés sur la recherche de descripteurs SIFT en raison de leur efficacité. Nous appliquons nos résultats à la recherche d'images similaires, notamment dans des grandes bases. Nous comparons d'abord les performances de la recherche linéaire sur CPU et sur GPU (processeurs des cartes graphiques), ainsi que les résultats obtenus en utilisant une distance partielle. Ensuite, nous proposons un algorithme de recherche approximative des voisins. L'algorithme proposé est basé sur des fonctions de hachage qui construisent des clés de hachage à partir d'un sous ensemble de dimensions de l'espace, sélectionné pour chaque point. Pour la recherche d'images similaires, cet algorithme s'avère être plus performant que les algorithmes de l'etal de l'art. Nous montrons l'efficacite de cet algorithme en l'utilisant pour chercher des images similaires dans une base de 500. 000 images, avec des requêtes effectuées en moins de 300 ms. Enfin, nous montrons que cet algorithme s'adapte tout à fait à un cadre « Bag-Of-Features » et qu'il est plus performant, sur des bases d'images similaires, que des vocabulaires k-means. Dans une seconde partie, nous concentrons nos travaux sur la reconstruction 3D à partir de plusieurs images. Nous proposons une méthode pour reconstruire de manière robuste une voiture en 3D a partir d'une acquisition vidéo. Le système proposé fait l'hypothèse que les voitures sont en translation rectiligne pour ensuite reconstruire le vehicule filmé par extrusion de polynômes. Enfin, nous introduisons un algorithme de reconstruction 3D multi-vues qui utilise les descripteurs SIFT pour trouver des correspondances entre des images de l'objet et des rendus virtuels de l'objet temporaire en cours de reconstruction. Cette méthode permet de faire converger une surface 3D vers la surface réelle de l'objet.