TEXMEX
Équipe de recherche TEXMEX
Techniques d'exploitation des documents multimédias
Exploration, indexation, navigation et recherche dans de très grandes bases

Sujet de master 2 recherche en informatique pour l'année 2013 / 2014

Titre : Apport de la bioinformatique pour la recherche de motifs multimédias

La recherche de motifs multimédias consiste à retrouver les occurrences d'une requête donnée dans un contenu multimédia. On peut ainsi vouloir rechercher l'ensemble des occurrences d'une publicité, connue et dont on possède un exemplaire, dans un flux télévisé. Ou une chanson dans un flux radio. Dans ces exemples, la variabilité entre occurrences d'un motif est faible. Le problème s'étend naturellement a des motifs exhibant une forte variabilité, comme lorsqu'on recherche dans des données de parole les occurrences d'un mot requête.

Les principaux enjeux de la recherche de motifs multimédias sont bien évidemment l'efficacité, i.e., la capacité à traiter en un temps raisonnable de grande quantité de donnée, et la robustesse aux variabilité, i.e., la capacité à gérer la variabilité entre occurrences d'un même motif.

Dans le domaine du multimédia, le problème est souvent abordé sous la forme d'un problème d'indexation [e.g., 1]. En effet, images dans la vidéo ou trames sonores dans l'audio sont représentées par des vecteurs de réels, appelés descripteurs. Ces derniers sont indexés, via un index ou une table de hashage, de manière à retrouver rapidement les plus proches voisins d'un point (une image ou une trame sonore). Des vérifications d'alignement temporel, souvent coûteuse en temps de calcul, sont ensuite appliqués pour retrouver la requête.

La recherche de motifs est également une problématique clé en bioinformatique. Dans ce dernier domaine, des algorithmes efficaces pour résoudre le problème ont été proposés, dérivés de l'algorithme fondamental d'alignement de séquence de symboles, FASTA [2]. Des algorithmes comme BLAST [3] ou SNAP [4] exploitent les spécificités des données ADN, au premier plan desquelles une représentation symbolique des données. Les distortions entre occurrences d'un motif suivent aussi des règles spécifiques à la génomique.

Ces algorithmes reposent sur le même principe, l'indexation de n-grammes de symboles. Tirant parti de la représentation symbolique des données, l'alignement de séquence repose sur un index dont les entrées sont de courtes séquences de symboles (3-4 symboles consécutifs), appelés n-grammes. Cette indexation permet de trouver de manière extrêmement efficace des points d'ancrage pour la requête dans les données, la requête étant ensuite recherchée de manière plus fine autour de ces points d'ancrage.

Le stage a pour objectif d'appliquer les algorithmes de génomiques pour la recherche efficace de motifs multimédias, dans la ligné de récents travaux [5, 6]. Les descripteurs réels sont quantifiés, ramenant ainsi la recherche de motifs multimédias à un problème d'alignement de séquence proche de la bioinformatique. Les données multimédias possèdent cependant des caractéristiques spécifiques que l'on ne retrouve pas en génomique: l'alphabet est potentiellement bien plus grand, on est capable de définir des distances entre symboles. On s'intéressera donc à mesurer l'impact de ces spécificités sur les algorithmes de génomique de manière à adapter ces derniers au contexte multimédia.

Après une étude bibliographique des algorithmes courants en bioinformatique, on choisira un modèle que l'on évaluera dans un contexte multimédia sur différentes tâches (recherche de publicité dans des flux télévision, de chanson dans des flux radios, voire de mots dans des flux de parole). On étudiera en particulier l'impact de la taille de l'alphabet utilisé pour la représentation des données multimédias sur le compromis entre performance et coût calculatoire. On s'attachera ensuite à proposer des améliorations pour mieux prendre en compte les spécificités de données multimédias. Exploiter les distances entre symboles, éventuellement dans une approche hiérarchique, constitue une première piste pour une recherche efficace et plus précise. L'indexation de n-grammes à trous offre la possibilité d'améliorer la gestion des insertions et omissions liées aux distortions temporelles.

Le stage se déroulera au sein de l'équipe Texmex de l'IRISA et tirera partie de l'expertise existante dans l'équipe en représentation des contenus multimédias, en indexation, et en alignement de séquence. Les expériences seront menées sur des corpus de référence pour lesquels des méthodes de recherche à l'état de l'art existent déjà, permettant ainsi une comparaison rapide à l'existant.

Bibliographie

  1. J. Yuan, G. Gravier, S. Campion, X. Li and H. Jégou. Efficient Mining of Repetitions in Large-Scale TV Streams with Product Quantization Hashing. Proc. ECCV Workshop on Web-scale Vision and Social Media, 2012.
  2. W. R. Pearson and D. J. Lipman, Improved tools for biological sequence comparison. Proc. of the National Academy of Sciences of the United States of America, 85(8), 1988.
  3. S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Journal of molecular biology, 215(3):403-410, 1990.
  4. M. Zaharia, W. J. Bolosky, K. Curtis, A. Fox, D. A. Patterson, S. Shenker, I. Stoica, R. M. Karp, and T. Sittler, Faster and more accurate sequence alignment with SNAP. CoRR, vol. abs/1111.5572, 2011.
  5. J. J. Burred. Genetic motif discovery applied to audio analysis. Proc. IEEE Intl. Conf. on Acoustics, Speech and Signal Processing, 2012.
  6. L. S. de Oliveira, Z. do Patrocínio Jr., S. Jamil F. Guimarães and G. Gravier. Searching for near-duplicate video sequences from a scalable sequence aligner. Proc. IEEE International Symposium on Multimedia, 2013.

Encadrants

Équipe de recherche

Équipe TexMex, IRISA (UMR 6074)