Recherche d'images rapide pour des similarités...

Recherche d'images rapide pour des similarités basées noyaux

David Gorisse (Doctorant ETIS), Frédéric Precioso (ETIS), Matthieu Cord (LIP6), Sylvie Philipp-Foliguet (ETIS)

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 2

Contexte

Recherche d'Imagespar Similarité

dans des grandes bases

Near DuplicateProblème « Résolu » ?!!!

côté descripteur [Lowe04],Mais passage à l'échelle

Recherche par Similarité de classes d'objets

Machine Learning Friendly

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 3

Contexte Recherche par Similarité :

Image requête

=>

retrouve des bus « identiques » avec des prises de vues et un environnement

différents=> Proche « Near Duplicate »

retrouve également des bus très différents

=> besoin de généraliser(Machine Learning)

Représentation classique des Images :

Descripteurs Globaux : 1 image = 1 vecteur

Descripteurs Locaux : 1 image = 1 sac de vecteurs (BoF)

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 4

Problématique Comment retrouver rapidement les images les plus similaires (TOPN)

à une image requête ?

=> contrôler la complexité de la recherche quand la taille de la base devient importante

Problème d'autant plus important quand on augmente le nombre et la taille des descripteurs.

Besoin de structurer la base => indexation Schéma d'indexation classique s'écroule en haute dimension

=> recherche approximative Arbre Projection (NV Tree, VA files, Space Filing Curves, Locality

Sensitive Hashing )

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 5

Locality Sensitive Hashingapproximation R-NN

BUT : retrouver les points dans un voisinage (Rayon de Recherche R) de la requête

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 6

Locality Sensitive HashingPrincipe

=> accès à un Bucket avec une seule décision

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 7

Locality Sensitive HashingThéorie : fonction Localement Sensible

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 8

Locality Sensitive HashingThéorie : fonctions de Hachage

Pour augmenter la bonne détection => utilisation de plusieurs tables de Hachage

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 9

Mise en oeuvre LSH

Implémentation dépendante de l'espace de représentation dans Hd ou Zd (approche dico) : LSH random permutation

[Indyk98] dans Rd normalisé : similarité cosinus [Charikar02] dans Rd : distance L2 ou L1

− [Gionis99] projection de Rd dans Hd + [Indyk98]− [Datar04] découpage suivant 1 dim− [Andoni06] 24 lattice, [Jégou08] E8 lattice

Directement utilisable pour une représentation vectorielle des images et pour les distances citées ci-dessus

Extension à d'autres similarités et à des espaces non vectoriels

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 10

Similarités Noyaux

Définition : Soit

Espace des données

Espace des caractéristiques

K : X×Xℝ

K est un noyau ssi ∃ ∣ ∀ x , y , K x , y =⟨x , y ⟩

Avec Φ une injection dans un espace de Hilbert H (explicite ou non)

: ℝd Hxx

Avantages : Intégration avec les techniques de Machine Learning (réseaux de neurones, SVM, …) Permet de construire des similarités sur des espaces d'entrées non vectoriels

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 11

Noyaux sur Sacs de Vecteurs

[Lyu05, gosselin07] :

Bons Résultats

MAIS Complexité du Noyau Importante

Bi Bjr vecteurs bri s vecteurs bsj

Pour chaque couple (bri, bsj)Noyau Mineur :

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 12

Un Noyau sur Sac rapidePyramid Match Hashing [Grauman07]

Chaque image est décrite par un sac de SIFT

On utilise une Injection explicite :- Projection dans l'espace des SIFTs- Application d'une grille multi-échelle- Projection dans l'espace de Hamming

Le Noyau résultant permet d'obtenir une similarité issue de l'appariement entre les PoIs (Points of Interest) des 2 images

Injection avec une fonction Φ dans un espace de grande dimension

=> Chaque Image devient un Vecteur Unique

L'explicitation de l'espace induit permet l'utilisation du LSH

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 13

LSH sur d'autres Noyaux ?

Pyramid Match Hashing

=> bonne performance

MAIS ne s'étend pas aux noyaux ou Φ n'est pas explicite

Si la classe des noyaux est différente ex:

Peut-on accélérer le calcul ?

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 14

Notre schéma [ICPR08] Modèle: Image = sac d'attributs non ordonnés

Similarité : fonction noyau sur sac

Objectif: Calcul rapide du topN issu du classement de la base obtenu avec la fonction de similarité K.

=> Diminuer la complexité du noyau sur sac. Principe: Inspiré du schéma de David Lowe pour la « Détection de copies »

=> Le schéma résultant est une approximation du classement issu du calcul de similarité sur toute la base

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 15

La Détection de Copies [Lowe04]Base Image

Description: SIFT

Image requête

Recherche Kppv

Sélection Rapide d'images d'intérêt par VOTE

consistance géometrique

Résultat

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 16

PrincipeBase Image

Description Locale

(SIFT,...)

Image requête

Recherche Kppv

Sélection Rapide d'images d'intérêt par VOTE

Evaluation de la similarité Noyau K + classement

Résultat

(1)

(2)

(3)

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 17

Pré-Traitement : Hachage de la Base

Bj ={bsj} Table de hachage 1 Table de hachage N

Pour chaque image Bi Pour chaque attribut bsi Pour chaque Table de hachage k - sélection d'un bucket avec la fonction de hachage : fk(bsi ) - met bsi dans le bucket sélectionné

fN(b2j )fN(b1j )

f1(b2j )

f1(b1j )

Locality Sensitive Hashing

Notation : fi(): fonction de la Table de hachage i

ha,c(): fonction de hachage

[datar 2004]

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 18

AlgorithmeBase

Hachage de la Base

Table de hachage 1

Table de hachage N

Toutes les Images de la Base sont réparties entre les différents Buckets de la table i

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 19

AlgorithmeBase

Hachage de la Base

S

S

Table de hachage 1

Table de hachage N

SSToutes les Images de la Base sont réparties entre les différents Buckets de la table i

Requête

S

S

(1) recherche Kppv sélection des Buckets

contenant les PoIs proches des PoIs requêtes

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 20

AlgorithmeBase

Hachage de la Base

S

S

Table de hachage 1

Table de hachage N

SSToutes les Images de la Base sont réparties entre les différents Buckets de la table i

Requête

S

(1) recherche Kppv

SS

S

(2) Sélection par Vote Sélection des Images contenant au

moins v PoIs appartenant aux Buckets Sélectionnés en (1)

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 21

AlgorithmeBase

Hachage de la Base

S

S

Table de hachage 1

Table de hachage N

SSToutes les Images de la Base sont réparties entre les différents Buckets de la table i

Requête

S

SS

S

TOP N

(3) Tri

(2) Sélection par Vote

(1) recherche Kppv

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 22

Expérimentations• Images

• Base : VOC2006 (5,304 images)• Attributs locaux : ~100 PoI par Images

• MSER détecteur• SIFT descripteur

• Paramètre LSH• rayon de recherche entre 150 et 250 (4,0 et 6,0 après normalisation)• L=50 tables de hachage• K=20 projections

• Evaluation : Image sélection VS ensemble de la base• détérioration du TOP100• réduction des temps de calcul

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 23

Sélection Rapide + Classement par Vote

372 / 5304 images (7,1% de la Base)

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 24

Classement par Similarité K de la sélection

Sélection Rapide

372 / 5304 images (7,1% de la Base)

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 25

Classement de la SélectionVérité terrain de K :

Classement de toute la base

96% des images du TOP100 obtenu à partir de la sélection sont identiques au TOP100 obtenu sur l'ensemble de la Base

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 26

Résultats

Précision du TOP100 pour différant rayon de recherche Pourcentage des images de la base sélectionnées

Gain en temps de calcul comparé au calcul sur toute la base

Rayon 4.00 5.00 5.2 6.00Gain 122.17 14.85 10.03 3.19

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 27

Conclusion Bons Résultats en utilisant LSH Trouver le compromis entre Précision et Rapidité

Bon compromis : précision médiane de 99%

gain x10 Recherche par Similarité Rapide compatible avec des

Noyaux non Explicites et implémentable avec toutes les méthodes de recherche rapide de type Kppv

[ICPR08] : Fast approximate kernel-based similarity search for image retrieval task

[Gosselin07] : Kernel on Bags of Fuzzy Regions for fast object retrieval

[Lowe04] : Distinctive image features from scale-invariant keypoints

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 28

Pyramid Match Hashing

09/06/2009 GDR ISIS: Passage à l'échelle dans la recherche d'information multimédia 29

Pyramid Match Hashing

On se retrouve dans le cas de [Charikar02]:=> approximation similarité via LSH

Peut se réécrire comme une somme pondérée d'intersection :

Chaque histogramme peut être projeté dans l'espace de Hamming en prenant en compte la pondération

La piramide d'histogrammes s'écrit alors :

La similarité entre 2 images s'écrit alors comme un produit scalaire: