Comparaison des fonctionnalités SIFT stockées dans une firebase database mysql

J’ai donc fait quelque chose de très similaire à cela il y a quelques années. L’algorithme que vous souhaitez examiner a été proposé il y a quelques années par David Nister, le document est: “Reconnaissance évolutive avec un arbre de vocabulaire”. Ils ont à peu près une solution exacte à votre problème qui peut s’adapter à des millions d’images.

Voici un lien vers le résumé, vous pouvez trouver un lien de téléchargement en cherchant sur le titre. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

L’idée de base est de construire un arbre avec un algorithme k-means hiérarchique pour modéliser les fonctionnalités, puis exploiter la dissortingbution éparse de ses fonctionnalités pour trouver rapidement vos voisins les plus proches … ou quelque chose comme ça, cela fait déjà quelques années J’ai travaillé dessus. Vous pouvez trouver une présentation PowerPoint sur la page Web des auteurs ici: http://www.vis.uky.edu/~dnister/Publications/publications.html

Quelques autres notes:

• Je ne me soucierais pas du kernel de correspondance pyramidale, c’est vraiment plus pour améliorer la reconnaissance d’object que pour la détection d’images dupliquées / transformées.

• Je ne voudrais stocker aucune de ces fonctionnalités dans une firebase database SQL. En fonction de votre application, il est parfois plus efficace de calculer vos fonctionnalités à la volée car leur taille peut dépasser la taille de l’image d’origine lorsqu’elle est calculée de manière dense. Les histogrammes d’entités ou les pointeurs vers les nœuds d’un arbre de vocabulaire sont beaucoup plus efficaces.

• Les bases de données SQL ne sont pas conçues pour effectuer des calculs vectoriels massifs en virgule flottante. Vous pouvez stocker des éléments dans votre firebase database, mais ne l’utilisez pas comme outil de calcul. J’ai essayé cette fois avec SQLite et ça s’est très mal terminé.

• Si vous décidez de le mettre en œuvre, lisez le document en détail et conservez une copie à scope de main, car de nombreux détails mineurs sont très importants pour le bon fonctionnement de l’algorithme.

Je pense que la clé, c’est que ce n’est pas une question d’EIFT. C’est une question sur la recherche approximative du voisin le plus proche. Comme la correspondance d’images, ceci est également un problème de recherche ouvert. Vous pouvez essayer “recherche approximative du voisin le plus proche” dans Google et voir quel type de méthodes sont disponibles. Si vous avez besoin de résultats exacts, essayez: “recherche exacte du voisin le plus proche”.

Les performances de toutes ces structures de données géomésortingques (telles que les kd-trees) se dégradent à mesure que le nombre de dimensions augmente, de sorte que la clé est que vous devrez peut-être représenter vos descripteurs SIFT dans un nombre inférieur de dimensions (par exemple 10-30 à la place). 256-1024) pour avoir des recherches très efficaces sur le plus proche voisin (utilisez PCA par exemple).

Une fois que vous avez cela, je pense que cela deviendra secondaire si les données sont stockées dans MySQL ou non.

Je pense que la vitesse n’est pas le principal problème ici. Le principal problème est de savoir comment utiliser les fonctionnalités pour obtenir les résultats souhaités.

Si vous souhaitez classer les images par catégories (par exemple, une personne, une voiture, une maison, un chat), le kernel Pyramid Match est vraiment intéressant à regarder. Il s’agit en fait d’un histogramme des descripteurs de caractéristiques locales, il n’est donc pas nécessaire de comparer des caractéristiques individuelles entre elles. Il existe également une classe d’algorithmes appelée “sac de mots”, qui tente de regrouper les caractéristiques locales pour former un “vocabulaire visuel”. Encore une fois, dans ce cas, une fois que vous avez vos “mots visuels”, vous n’avez pas besoin de calculer les distances entre toutes les paires de descripteurs SIFT, mais de déterminer à quel cluster appartient chaque entité. D’autre part, si vous souhaitez obtenir des correspondances de points entre des paires d’images, par exemple pour décider si une image est contenue dans une autre ou pour calculer la transformation entre les images, vous devez alors rechercher les voisins les plus proches exacts.

En outre, il existe des fonctionnalités locales autres que SIFT. Par exemple, SURF présente des fonctionnalités similaires à SIFT, mais leur extraction est plus rapide et il a été démontré qu’elles fonctionnaient mieux pour certaines tâches.

Si vous souhaitez simplement rechercher des doublons, vous pouvez considérablement accélérer la recherche en utilisant un descripteur d’image global, tel qu’un histogramme de couleur, pour supprimer les images manifestement différentes. La comparaison de deux histogrammes de couleurs est beaucoup plus rapide que la comparaison de deux ensembles contenant chacun des centaines de caractéristiques SIFT. Vous pouvez créer une courte liste de candidats à l’aide d’histogrammes de couleurs, puis affiner votre recherche à l’aide de SIFT.

J’ai quelques outils en python avec lesquels vous pouvez jouer ici . Fondamentalement, c’est un paquet qui utilise des vecteurs transformés SIFT, puis calcule le hachage de réseau le plus proche de chaque vecteur tamisé à 128d. Le hachage est la partie importante, car il est sensible à la localité, ce qui signifie simplement que les vecteurs proches de l’espace R ^ n entraînent des probabilités de collision de hachage équivalentes. Le travail que je fournis est une extension d’ Andoni qui fournit une heuristique d’adaptation de requête pour élaguer les listes de recherche exactes de LSH, ainsi qu’une implémentation CUDA optimisée de la fonction de hachage. J’ai également une petite application qui effectue une recherche dans la firebase database d’images avec un bon retour visuel, le tout sous bsd (à l’exception de SIFT qui a quelques ressortingctions supplémentaires).