Sensibilité locale au hachage dans OpenCV pour le traitement des images

Ceci est ma première application de traitement d’image, alors s’il vous plaît soyez gentil avec ce paysan sale.

L’APPLICATION:

Je souhaite implémenter une application rapide (les performances sont cruciales, même au-delà de la précision) lorsqu’une photo (prise par un téléphone mobile) contenant une affiche de film trouve la photo la plus similaire dans un dataset donné et renvoie un score de similarité. Le jeu de données est composé d’images similaires (sockets par téléphone portable, contenant une affiche de film). Les images peuvent être de taille, de résolution différentes et peuvent être sockets à partir de points de vue différents (mais il n’ya pas de rotation, car les affiches sont supposées toujours être orientées à droite).

Toute suggestion sur la manière de mettre en œuvre une telle application est bien acceptée.

DESCRIPTIONS DES FONCTIONS DANS OPENCV:

Je n’ai jamais utilisé OpenCV et j’ai lu ce tutoriel sur la détection et la description des fonctionnalités par OpenCV.

D’après ce que j’ai compris, ces algorithmes sont supposés trouver des points-clés (généralement des angles) et éventuellement définir des descripteurs (décrivant chaque point-clé et servant à apparier deux images différentes). J’ai utilisé “éventuellement” car certains d’entre eux (par exemple, FAST) ne fournissent que des points-clés.

PROBLÈME D’IMAGES PLUS SIMILAIRES ET LSH:

Les problèmes ci-dessus ne résolvent pas le problème “étant donné une image, comment trouver rapidement l’image la plus similaire dans un jeu de données”. Pour ce faire, nous pouvons utiliser les points clés et les descripteurs obtenus par l’un des algorithmes précédents. Le problème mentionné ci-dessus semble être un problème de voisin le plus proche et le hachage sensible à la localité est une solution rapide et populaire pour trouver une solution approximative à ce problème dans les espaces de grande dimension.

LA QUESTION:

Ce que je ne comprends pas, c’est comment utiliser le résultat de l’un des algorithmes précédents (c.-à-d. Points clés et descripteurs) dans LSH.

Existe-t-il une implémentation pour ce problème?

Je vais donner une réponse générale, dépassant le cadre de la bibliothèque OpenCV.


Citant cette réponse :

descripteurs : ils permettent de comparer les points clés. Ils résument, en format vectoriel (de longueur constante), certaines caractéristiques des points-clés.

Cela dit, nous pouvons imaginer / traiter ( géomésortingquement ) un descripteur en tant que point dans un espace dimensionnel. Donc au total, tous les descripteurs sont des points dans un espace dimensionnel. Par exemple, pour GIST , D = 960.

Les descripteurs décrivent donc l’image en utilisant moins d’informations que l’image entière (car lorsque vous avez 1 milliard d’images, la taille compte). Ils servent de représentants de l’image, nous les traitons donc au nom de l’image (car ils sont plus faciles / plus petits à traiter).


Le problème que vous mentionnez est le problème du voisin le plus proche . Notez qu’une version approximative de ce problème peut conduire à des accélérations significatives lorsque D est grand (car la malédiction de la dimensionnalité rendra les approches traditionnelles, telles qu’un arbre de kd très lent, presque linéaire en N (nombre de points)) .

Les algorithmes qui résolvent le problème NN, qui est un problème d’optimisation, sont généralement génériques. Ils peuvent ne pas se soucier de savoir si les données sont des images, des molécules, etc., par exemple, j’ai utilisé mon kd-GeRaF pour les deux. En conséquence, les algorithmes attendent N points dans un espace dimensionnel D , donc vous pourriez vouloir dire N descripteurs.

Vérifiez ma réponse pour LSH ici (ce qui indique une bonne implémentation).


Modifier :

LSH attend en entrée N vecteurs de dimension D et, étant donné un vecteur de requête (dans D ) et une plage R , trouvera les vecteurs compris dans cette plage à partir du vecteur de requête.

En conséquence, on peut dire que chaque image est représentée par un seul vecteur, au format SIFT par exemple.

Vous voyez, LSH ne résout pas le problème de k-NN directement, mais il recherche dans une plage (et peut vous donner les k-NN, s’ils se trouvent dans la plage). Pour en savoir plus sur R, consultez la section Expériences, Neighbo proche approximatif en haute dimension . kd-GeRaF et FLANN résolvent directement le problème de k-NN.