Passage à l'échelle dans la recherche d'information multimédia

Journée inter-GDRs, organisée conjointement par le GDR ISIS, Thème B (Image et Vision) et le GDR I3 (http://www.irit.fr/GDR-I3/), Thème 4 (Masses de données et accès à l'information)

Les techniques de structuration de grandes bases d'images ou de vidéos, ainsi que les méthodes de recherche par le contenu dans de telles bases, font aujourd'hui l'objet de nombreux travaux. Parmi les applications visées on peut mentionner la structuration de collections audio-visuelles, la fouille de grandes bases d'images satellitaires, les moteurs de recherche de données multimédia ou la détection de copies par le contenu. Au-delà des exigences liées à la qualité des résultats, le potentiel applicatif de ces méthodes dépend très largement de leur capacité à passer à l'échelle. Parmi les multiples aspects que recouvre la notion de passage à l'échelle, nous nous intéressons principalement à la capacité de traiter un très grand volume de données (images, vidéo et/ou audio) avec des ressources limitées, et malgré une description riche du contenu, de plus en plus souvent adoptée pour assurer la qualité des résultats.

Le premier objectif de cette journée est de faire un panorama des travaux actuels en France sur ce thème, en abordant également des problèmes moins classiques que la recherche par similarité (par exemple, la recherche avec contrôle de pertinence, l'auto-jointure par similarité pour la structuration, etc.) et en privilégiant des approches nouvelles (description hiérarchique, embedding, etc.).

Le second objectif est d'examiner une question générale et importante mais problématique : l'évaluation du passage à l'échelle. En effet, une méthode performante correspond souvent à un compromis entre l'efficacité du traitement et la qualité des résultats. Il est donc indispensable de pouvoir évaluer ces deux composantes de la performance, grâce à une vérité terrain représentative et suffisamment large. Or, produire des vérités terrain réalistes de très grande taille exige un effort difficilement envisageable. Des vérités terrain synthétiques peuvent parfois être générées, mais il n'est pas simple de juger de leur pertinence par rapport aux applications réelles.

Envoyez avant le 15/05/2009 vos propositions d'exposés par courriel (à Michel.Crucianu (a) cnam.fr et Laurent.Amsaleg (a) irisa.fr), en incluant les informations suivantes : titre, auteurs avec affiliations, résumé (10-15 lignes) et, si possible, un lien vers des travaux accessibles en ligne.

Organisateurs :
Michel Crucianu (http://cedric.cnam.fr/~crucianm/)
Laurent Amsaleg (http://www.irisa.fr/texmex/people/amsaleg/index_fr.htm)
Christine Fernandez-Maloigne (http://www.sic.sp2mi.univ-poitiers.fr/maloigne/)

------------------------------------------------------
9h00 - 9h30 : Accueil et ouverture
----
9h30 :

"Etude des descripteurs SIFT pour le matching de scènes dans un contexte urbain de type Google StreetView"
David Picard, Eduardo Valle, Matthieu Cord, LIP6

"HiPeR: Un modèle hiérarchique pour la recherche exacte, progressive et approximative par similarité"
Nouha Bouteldja, Valérie Gouet-Brunet, Michel Scholl, Vertigo - CEDRIC & Wisdom, CNAM Paris

"A posteriori multi-probe LSH for large scale image retrieval"
Alexis Joly (INRIA-IMEDIA), Olivier Buisson (INA)

----
11h00 - 11h15 : Pause café
----
11h15:

"Recherche d'images rapide pour des similarités basées noyaux"
David Gorisse (ETIS), Frederic Precioso (ETIS), Matthieu Cord (LIP6), Sylvie Philipp-Foliguet (ETIS)

"Propriétés et limites des représentations en sac de mots visuels"
Pierre Tirilly (IRISA-CNRS), Vincent Claveau (IRISA-CNRS), Patrick Gros (INRIA Rennes-IRISA)

"Web-scale image search"
Matthijs Douze (INRIA-LEAR)

---------------------------
12h45 - 14h00 : Déjeuner
---------------------------
14h00 :

"Indexation hiérarchiques des contenus vidéo HD par objets dans le cadres du standard
scalable JPEG2000"
C. Morand, J. Benois-Pineau, J.-ph. Domenger (LABRI)

"Passage a l'échelle d'algorithmes de classification"
Francois Poulet, Universite de Rennes I - IRISA

"Accès à l'information multimédia classifiée"
José Martinez (INRIA-ATLAS)

----
15h30 - 15h45 : Pause café
----
15h45 :

"Extraction d'information dans les images satellitaires"
Marine Campedel, Telecom ParisTech, CoC

"De 2 à 22 millions d’images, création indexation et recherche par le contenu avec PiRiA"
Patrick Hède, Commissariat à l'Énergie Atomique (CEA) LIST

"Vers une base d'apprentissage pour l'annotation automatique d'images à grande échelle sémantisée"
Nicolas James, Laboratoire MAS, École Centrale Paris

----
16h45 - 17h30 : Discussion sur l'évaluation du passage à l'échelle.
(problématique, initiatives existantes, retour sur TRECVID 2008, nouvelles initiatives)

********************************************************

RESUMES (dans l'ordre de passage)

********************************************************

"Etude des descripteurs SIFT pour le matching de scènes dans un contexte urbain de type Google StreetView"
David Picard, Eduardo Valle, Matthieu Cord, LIP6

Dans cette présentation, nous évaluons la qualité des méthodes basées sur les statistiques d'appariement de points SIFT dans un contextede photographie urbaine (tel que Google StreetView). Ces travaux font partie du projet iTowns, pour lequel les rues de Paris sont numérisées en très haute résolution, constituant de très gros volumes de données. Dans ce contexte, la proportion de faux appariements tend à être très élevée. Nous avons testé un algorithme de recherche approximée des k plus proches voisins, afin d'accélérer la recherche. Nous l'avons comparé à une recherche linéaire, ce qui nous a permis de valider l'approche rapide. Nous avons ensuite testé plusieurs stratégies de vérification de cohérence géométrique issues de l'état del'art afin de supprimer les faux appariements. Nous avons montré que l'efficacité des SIFT dans ce contexte dépend grandement du contenu dela base et que l'étape de correction géométrique est essentielle àl'obtention de bons résultats.

----

"HiPeR: Un modèle hiérarchique pour la recherche exacte, progressive et approximative par similarité"
Nouha Bouteldja, Valérie Gouet-Brunet, Michel Scholl, Vertigo - CEDRIC & Wisdom, CNAM Paris

Ce travail s’intéresse à l’accélération de la recherche par similarité dans les espaces hautement dimensionnels. La méthode présentée, appelée HiPeR, est basée sur une hiérarchie d’espaces et d’index : la recherche commence par les espaces à faibles dimensions afin de réduire les effets de la malédiction de ladimension, fournissant ainsi un premier résultat qui sera amélioré progressivement en utilisant les plus grandes dimensions. Dans cette présentation, la hiérarchie HiPeR est implémentée avec l’index classique “VA-File”, générant une VA-Hiérarchie. Différentes stratégies sont proposées pour le parcours d’une telle hiérarchie, en assurant la recherche exacte mais aussi approximative des plus proches voisins, selon un contrôle probabiliste de perte de la précision paramétrable en ligne. Les expériences, menées sur trois différentes bases de descripteurs d'images contenant 4 millions de points, montrent qu’HiPeR améliore notablement les index classiques en termes de temps CPU et d’accès I/O.

----

"A posteriori multi-probe LSH for large scale image retrieval"
Alexis Joly (INRIA-IMEDIA), Olivier Buisson (INA)

In this talk, we will present our recent new high dimensional similarity search structure, which improves upon recent theoretical work on multi-probe and query adaptive LSH. Whereas these methods are based on likelihood criteria that a given bucket contains query results, we define a more reliable a posteriori model taking account some prior about the queries and the searched objects. This prior knowledge allows a better quality control of the search and a more accurate selection of the most probable buckets. We show that our a posteriori scheme outperforms other multi-probe LSH while offering a better quality control. Comparisons to the basic LSH technique show that our method allows consistent improvements both in space and time efficiency. We will finish by briefly presenting two recent works based on this new index structure, one related to efficient boosting of local visual features, and one related to logo retrieval in large datasets.

*******************************************************************

"Recherche d'images rapide pour des similarités basées noyaux"
David Gorisse (ETIS), Frederic Precioso (ETIS), Matthieu Cord (LIP6), Sylvie Philipp-Foliguet (ETIS)

Pour la recherche d'images proches (copy detection ou near duplicate) ou plus généralement le tri par similarité à une requête exemple d'une base d'images, les approches utilisant des descripteurs locaux, avecune recherche des kppv suivi d'un vote, se sont beaucoup développées ces dernières années [Lowe IJCV03]. Une alternative possible à ce schéma de recherche utilise des fonctions noyaux pour définir des similarités entre sacs d'indices visuels. Par exemple, Lyu [Lyu CVPR05] a proposé une fonction de similarité noyau pour comparer des images décrites par des attributs locaux (descripteurs SIFT). La similarité résultante fournit des résultats très bien évalués. Cependant, du fait de sa complexité de calcul, cette fonction est inadaptée aux recherches dans les grandes bases d'images. Nous présentons ici un schémade recherche optimisé pour calculer une similarité basée sur une fonction noyau sur sacs de vecteurs [Gorisse ICPR 08]. La méthode limite le nombre de scores de similarité à calculer permettant ainsi d'étendre l'utilisation de ce type de fonctions à de plus grandes bases. Le principe est de se "concentrer" lors d'une recherche sur le top du classement de la base. Pour cela, l'algorithme pré-sélectionne rapidement (par une approche sous-linéaire en la taille de la base) des images dont les sacs contiennent des points pas trop éloignés de la requête. Dans notre implémentation, cette sélection rapide est faite via la méthode LSH. Finalement, seules ces images pré-sélectionnées seront triées en utilisant la coûteuse fonction de similarité noyau. On montrera également comment ce type de schéma permet de faire del'apprentissage interactif.
http://perso-etis.ensea.fr/~davigori/publi/fastKernel.pdf

----

"Propriétés et limites des représentations en sac de mots visuels"
Pierre Tirilly (IRISA-CNRS), Vincent Claveau (IRISA-CNRS), Patrick Gros (INRIA Rennes-IRISA)

Les techniques récentes de recherche d'images par le contenu et de classification d'images reposent sur la description des images en sacs de mots visuels proposée par Sivic et Csurka. Basé sur des descripteurs locaux, ce modèle permet de mieux représenter le contenu des images que les descripteurs globaux classiques de couleur et de texture. En outre, il partage de nombreuses similarités avec le modèle en sac de mots utilisé pour l'indexation textuelle : les documents sont décrits comme des vecteurs de fréquences de mots, que l'on compare à l'aide d'une distance. Ces vecteurs étant creux, les distances peuvent être calculées de manière très efficace. Nous avons initialement étudié quel pouvait être l'apport de deux éléments classiques de la recherche d'information textuelle à la recherche d'images par le contenu : le choix de la distance (cosinus et distances de Minkowski) et les pondérations de termes (dans l'esprit du TF*IDF, déjà utilisé pour l'image). Les résultats de ces expériences, pratiquées sur 4 corpus d'images aux propriétés variées, apportent un éclairage quantitatif sur les propriétés et les limites des sacs de mots visuels. On observe d'une part que la marge de gain de performance devient nulle lorsque la variabilité des images augmente, ce qui est le cas dans les très grandes bases d'images. D'autre part, on remarque que la nature des requêtes peut fortement influencer les paramètres à employer, rendant difficile la mise au point d'un système de recherche d'images générique utilisant cette représentation, de même que l'évaluation d'un tel système.

----

"Web-scale image search"
Matthijs Douze (INRIA-LEAR)

Indexing large image collections based on visual similarity allows to find the images from a collection that are best related to a query image. The most effective tool for same-scene or -object recognition is the geometrical matching of interest points. This process is costly and can handle only a few hundred images in interactive time. A more efficient approach consists of quantizing the interest point descriptors, which produces a bag-of-features representation for each image. This method scales up to a few million images and has received increasing attention in the past years.
In this talk, we consider the problem of scaling up to hundreds of millions of images, which require order-of-magnitude improvements in terms of memory usage and of search speed. Two methods are proposed to achieve this goal.
The first method uses global GIST descriptors. The descriptors are quantized by k-means and augmented with binary signatures. The collection is stored in an inverted file for optimal search speed: searching in 110 million images takes 0.18 s. This approach is shown to be competitive for moderate image transformations, such as those encountered in a copy detection setup.
The second method builds upon a bag-of-features representation. Several complementary descriptors of this representation are generated using sparse linear transformations. A distance expectation criterion is then used to rank the images, and shown to provide an accuracy similar to that of the original representation, while improving the speed and decreasing the memory usage by two orders of magnitude.

******************************************************

"Indexation hiérarchiques des contenus vidéo HD par objets dans le cadres du standard
scalable JPEG2000"
C. Morand, J. Benois-Pineau, J.-Ph. Domenger (LABRI)

L'accès aux contenus vidéos, que ce soit pour des fonctions d'édition ou de diffusion, dans des bases en général très grandes, nécessite d'associer au contenu des descripteurs ou méta-données. Pour la vidéo, il s'agit de descripteurs spatio-temporels. Ces derniers doivent permettre de collecter des informations liées aux actions, événements ou activités représentés par le document vidéo considéré. Il est évident que ces contenus dynamiques peuvent intervenir à différentes échelles spatiales et temporelles. De même, la caractérisation de ces informations peut être placée à différentes échelles spatiales et temporelles selon les besoins affichés, les capacités de calcul et de stockage de méta-données, et/ou la possibilité même d'extraire de manière fiable et précise les informations visées.
L'indexation et recherche des contenu vidéos par objets reste un domaine difficile car l'extraction des objets d'intérêt des contenus vidéo variés quand ni les connaissances /a priori/ sur la nature des objets, ni données d'apprentissage ne sont pas disponibles, est un problème mal posé.
Dans le cas des contenus compressés avec des standards scalables il s'agit de proposer des outils d'extraction des objets à différentes niveaux de résolution disponibles directement dans le flux vidéo, mais aussi de concevoir des descripteurs des objets s'adaptant à ces différentes résolutions.
Dans ce travail nous proposons des méthodes d'extraction scalable spatio-temporelle des objets directement dans le domaine de la transformée utilisée dans le standard, à savoir les ondelettes de Daubechies. Ici toutes les étapes d'extraction telles que segmentation spatiale ou estimation du mouvement sont conçues dans le domaine de la transformée sans le décodage complet du flux. Afin d'assurer la possibilité des requêtes scalables nous nous intéressons aux descripteurs statistiques des objets et proposons des scénarii de requêtes guidées par l'utilisateur.

----

"Passage a l'echelle d'algorithmes de classification"
Francois Poulet, Universite de Rennes I - IRISA

Les algorithmes de classification doivent faire face a une quantite de plus en plus importante de donnees. Plusieurs solutions peuvent etre envisagees pour permettre aux algorithmes d'obtenir des resultats dans des temps d'execution et consommation memoire raisonnables. Nous presentons deux algorithmes de classification paralleles :
- un algorithme de SVM incremental et parallele sur GPU, qui permet de traiter des donnees aussi volumineuses que l'on veut (grace a l'aspect incremental de l'algorithme) dans un temps raisonnable (grace a la parallelisation sur GPU). Les gains obtenus permettent d'etre environ 130 fois plus rapide sur GPU que le meme algorithme sur CPU, soit de l'ordre de 2500 fois plus rapides que les algorithmes de reference actuels tels que libSVM, SVMPerf ou CB-SVM.
- un algorithme de Forets Aleatoires d'arbres obliques (ou de SVM) qui ne travaille a un instant donne que sur un sous-ensemble des individus et un sous-ensemble de dimensions. L'algorithme general consiste donc a construire un certain nombre d'arbres (sur un sous-ensemble d'individus et de dimensions, ce qui permet de traiter des fichiers de grandes tailles) que nous allons calculer sur un cluster de machines pour obtenir des temps de calculs raisonnables. Compare a l'algorithme de forets aleatoires de Breiman, notre algorithme est plus rapide et ameliore le taux de precision sur differents grands ensembles de donnees de l'UCI et du Kent Ridge Bio-Medical Data Set Repository.

----

"Accès à l'information multimédia classifiée"
José Martinez (INRIA-ATLAS)

Nous présentons les problématiques communes aux membres de l'équipe Atlas-GRIM. Elles concernent toutes des formes de classification de l'information, quelle soit structurée ou multimédia, dans un cadre réparti / parallèle en vue d'une indexation et d'une recherche (interactive) efficientes. En particulier, nous décrirons nos travaux sur les stratégies de placement de données pour la recherche parallèle de plus proches voisins, en vue de recherche à coût sous-linéaire. Nous discuterons le nombre optimal de noeuds pour maximiser l'utilisation des ressources. Nous évoquerons enfin des travaux de l'équipe ayant trait à l'agrégation de représentations parcimonieuses paramétrées réparties, dans un contexte d'apprentissage décentralisé.

----

"Extraction d'information dans les images satellitaires"
Marine Campedel, Telecom ParisTech, CoC

Resume :
Le Centre de Competence CNES/DLR/Telecom ParisTech (www.coc.enst.fr) a, depuis 4 ans, pour ambition l'extraction d'information et la compréhension des images satellitaires. Des satellites toujours plus performants sont lancés, à des résolutions de plus en plus hautes et avec une fréquence de mise à jour elle aussi améliorée. Les agences spatiales reçoivent des centaines de Gigaoctets quotidiennement, tout en sachant qu'une faible portion de ces images est réellement exploitée. En effet, les images satellitaires sont essentiellement exploitées par des photo-interprètes, à l'oeil, dans des applications très diverses tellesque l'étude de la déforestation, ou de l'urbanisation, la surveillance de terrains agricoles ou la cartographie rapide en cas de catastrophe naturelle. Ces professionnels s'appuient parfois sur des logiciels de traitement d'images. La présentation proposée a pour objectif de décrire les enjeux liés au traitement (semi-) automatique des images satellitaires ainsi que les problèmes techniques que cela représente : une seule image SPOT5 panchromatique a une taille typique de 12000x12000 pixels, ce qui signifie que la simple manipulation, visualisation de cette image peut être problématique. Nous détaillerons également quelques solutions développées dans le cadre du CoC, permettant d'adapter des approches classiques "multimedia" à ces images afin d'en caractériser le contenu (approches dites "sacs de mots") et les rendre plus accessibles aux interprètes (à l'aide de boucle de pertinence et d'ontologies), voire au grand public.

************************************

"De 2 à 22 millions d’images, création indexation et recherche par le contenu avec PiRiA"
Patrick Hède, Commissariat à l'Énergie Atomique (CEA) LIST

Dans le cadre du projet Fame2 (2007) une version parallèle MPI du moteur séquentiel PiRiA (CBIR) a été développée, sur une machine du partenaire BULL, afin d’indexer et de rechercher dans une collection de 22 millions d’images avec un descripteur global à signature assez courte (BIC). Dans un premier temps nous présenterons la création de labase de 22 millions d’images à partir d’un noyau issu de wikipédia ayant subi des transformations géométriques et chromatiques afin d’atteindre 22 millions. Nous présenterons ensuite les problèmes rencontrés pour créer un wrapper MPI v1 de PiRiA menant à l’indexation et la recherche. Différents types de parallélismes seront abordés. Enfin, nous présenterons une nouvelle méthode de constitution d’une base de 10 millions d’images ainsi qu'une nouvelle version MPI v2 de PiRiA.
PiRiA: http://www-list.cea.fr/fr/programmes/systemes_interactifs/labo_lic2m/piria/w3/pirianet.php

----

"Vers une base d'apprentissage pour l'annotation automatique d'images àgrande échelle sémantisée"
Nicolas James, Laboratoire MAS, École Centrale Paris

Face aux problèmes connus du fossé sémantique en recherche d'images par le contenu d'une part, et aux limitations d'autre part, du modèle de recherche d'images textuel, l'annotation automatique d'images est sujet aujourd'hui de beaucoup de travaux. Les principales approches (probabilistes, génératives, basées sur des graphes, ...) se basent sur une base de données d'apprentissage avec vérité terrain, dans laquelle chaque image possède une annotation. Dans un premier temps, nous montrerons les faiblesses des bases d'apprentissage actuelles. Notamment, la majorité de ces bases sont principalement destinées à la reconnaissance de concept visuels et utilisent donc un petit vocabulaire d'annotation pour la vérité terrain peu représentatif des applications réelles. D'autres, telles que LabelMe ou Google Image Labeler, sont disponibles pour construire de larges bases d'apprentissage possédant un vocabulaire annotation plus important, mais en l'absence de contrôle sur la rédaction des annotations, la qualité de la vérité terrain est imprévisible. Une autre limitation majeure de ces vérités terrains est le fait que aucune sémantique n'y soit attachée. Dans une seconde partie, nous exposerons un modèle de propagation de mot-clefs enrichi d'une méthode de désambiguïsation. Cette approche nous permet de construire une base d'images sémantisée.
Article en ligne: http://www.mas.ecp.fr/new/node/74