Recherche d'images rapide pour des similarités …cedric.cnam.fr/~crucianm/src/echelle/DGorisse.pdfRecherche d'images rapide pour des similarités basées noyaux David Gorisse (Doctorant

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


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)


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 )


Locality Sensitive Hashingapproximation R-NN

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


Locality Sensitive HashingPrincipe

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


Locality Sensitive HashingThéorie : fonction Localement Sensible


Locality Sensitive HashingThéorie : fonctions de Hachage

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


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


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


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 :


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


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 ?


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


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


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)


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]


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


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


AlgorithmeBase

Hachage de la Base

S

S

Table de hachage 1

Table de hachage N


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)


AlgorithmeBase

Hachage de la Base

S

S

Table de hachage 1

Table de hachage N


Requête

S

SS

S

TOP N

(3) Tri

(2) Sélection par Vote

(1) recherche Kppv


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


Sélection Rapide + Classement par Vote

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


Classement par Similarité K de la sélection

Sélection Rapide

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


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


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


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





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:

Documents

Recherche d'images rapide pour des similarités …cedric.cnam.fr/~crucianm/src/echelle/DGorisse.pdfRecherche d'images rapide pour des similarités basées noyaux David Gorisse (Doctorant