Découverte et exploitation d'objets visuels fréquents dans des collections multimédias

Automatically linking multimedia documents that contain one or several instances of the same visual object has many applications including: salient events detection, relevant patterns discovery in scientific data or simply web browsing through hyper-visual links. Whereas efficient methods now exist for searching rigid objects in large collections, discovering them from scratch is still challenging in terms of scalability, particularly when the targeted objects are small compared to the whole image. In this PhD, we first revisited formally the problem of mining or discovering such objects, and then generalized two kinds of existing methods for probing candidate object seeds: weighted adaptive sampling and hashing based methods. We then introduced a new high-dimensional data hashing strategy, that works first at the visual level, and then at the geometric level. We conducted large-scale experiments on millions of images and on a new dedicated evaluation dataset (FlickrBelgaLogos.html) that we shared with the community. We did show that our method outperforms the reference method Geometric Min Hash. Based on this contribution, we then address the problem of suggesting object-based visual queries in a multimedia search engine. State-of-the-art visual search systems are usually based on the query-by-window paradigm: a user selects any image region containing an object of interest and the system returns a ranked list of images that are likely to contain other instances of the query object. User's perception of these tools is however affected by the fact that many submitted queries actually return nothing or only junk results (complex non-rigid objects, higher-level visual concepts, etc.).L'objectif principal de cette thèse est la découverte d'objets visuels fréquents dans de grandes collections multimédia (images ou vidéos). Comme dans de nombreux domaines (finance, génétique, ...), il s'agit d'extraire une connaissance de manière automatique ou semi-­‐automatique en utilisant la fréquence d'apparition d'un objet au sein d'un corpus comme critère de pertinence. Dans le cas visuel, le problème est différent de la fouille de données classique (ADN, textuel, etc.) puisque les instances d'apparition d'un même objet ne constituent pas des entités identiques mais doivent être appariées. Cette difficulté explique également pourquoi nous nous focalisons sur la découverte des objets rigides (logos, objets manufacturés, décors, bâtiments, etc.), et non des catégories d'objets de plus haut niveau sémantique (maison, voiture, chien, ...). Bien que les techniques de recherche d'objets rigides aient atteint une certaine maturité, le problème de la découverte non supervisée d'instances d'objets dans des grandes collections d'images est à l'heure actuelle encore difficile. D'une part parce que les méthodes actuelles ne sont pas assez efficaces et passent difficilement à l'échelle. D'autre part parce que le rappel et la précision sont encore insuffisants pour de nombreux objets. Particulièrement ceux ayant une taille très restreinte par rapport à l'information visuelle contextuelle qui peut être très riche (par exemple le logo d'un parti politique apparaissant ponctuellement dans un sujet de journal télévisé). Une première contribution de la thèse est de fournir un formalisme aux problèmes de découverte et de fouille d'instances d'objets visuels fréquents. Ces deux problèmes sont en effet définis de manière très confuse dans les quelques travaux récents de la littérature les abordant. Cette modélisation nous a permis entre autres choses de mettre en évidence le lien étroit qui existe entre la taille des objets à découvrir et la complexité du problème à traiter. La deuxième contribution de la thèse est une méthode générique de résolution de ces deux types de problème reposant d'une part sur un processus itératif d'échantillonnage d'objets candidats et d'autre part sur une méthode efficace d'appariement d'objets rigides à large échelle. L'idée est de considérer l'étape de recherche d'instances proprement dite comme une simple boite noire à laquelle il s'agit de soumettre des régions d'images ayant une probabilité élevée d'appartenir à un objet fréquent de la base. Une première approche étudiée dans la thèse consiste à simplement considérer que toutes les régions d'images de la base sont équiprobables, avec comme idée conductrice que les objets les plus instanciés sont ceux qui auront la couverture spatiale la plus grande et donc la probabilité la plus élevée d'être échantillonnés. En généralisant cette notion de couverture à celle plus générique de couverture probabiliste, il est alors possible de modéliser la complexité de notre méthode pour toute fonction de vraisemblance donnée en entrée, et de montrer ainsi l'importance de cette étape. La troisième contribution de la thèse s'attache précisément à construire une fonction de vraisemblance s'approchant au mieux de la distribution parfaite, tout en restant scalable et efficace. Cette dernière repose sur une approche originale de hachage à deux niveaux, permettant de générer efficacement un ensemble d'appariements visuels dans un premier temps, et d'évaluer ensuite leur pertinence en fonction de contraintes géométriques faibles. Les expérimentations montrent que contrairement aux méthodes de l'état de l'art notre approche permet de découvrir efficacement des objets de très petite taille dans des millions d'images. Pour finir, plusieurs scénarios d'exploitation des graphes visuels produits par notre méthode sont proposées et expérimentés. Ceci inclut la détection d'évènements médiatiques transmedia et la suggestion de requêtes visuelles