Recherche par similarité statistique dans une grande base de signatures locales pour l'identification rapide d'extraits vidéo

Content-based video indexing deals with techniques used to analyse and to exploit video databases without needs of any additional textual description. The work presented in this report is focused more precisely on content-based video copy detection, which is one of the emerging multimedia applications for which there is a need of a concerted effort from the database community and the computer vision community. To overcome the difficulties due to the use of very large databases, both in terms of robustness and speed, we propose a complete original and efficient strategy. The first part of this report presents the particular context of copy detection and the signatures used to describe the content of the videos. The originality of our method is that it is based both on local signatures and on a global similarity measure computed after the search in the signatures database. This similarity measure is not only a vote like other classical local approaches but it includes a registration step between candidate objects and objects retrieved by the search.The second part presents the main contribution of the thesis: A new indexing and retrieval technique belonging to the approximate similarity search techniques family. Recent works shows that trading quality for time can be widely profitable to speed-up descriptors similarity search. Whereas all other approximate techniques deal with K Nearest Neighbors search, the principle of our method is to extend the approximate paradigm to range queries. The main originality consists in determining relevant regions of the space according a theoritical model for the distortions undergone by the signatures. The method allows to determine the optimal region of the space with a high controlled probability to contain the good answer. This search paradigm is called statistical query. In practice, to simplify the access to signatures, the relevant regions are determined by using an Hilbert space filling curve and the space partition that induces. The experiments show that the technique is sublinear in database size with an assymptotically linear behavior (but only for huge databases) and that the quality performances are stable. Furthermore, they highlight that statistical queries provide a very high speed-up compared to classical exact range queries. The third part is focused on the global system assessment and the description of three applications. The experiments show that the simple theoretical distortion model is efficient enough to control the effective probability to retrieve a descriptor. They also point out that approximate similarity search is particularly profitable when using local signatures since the lost of some search results does not affect the global robustness of the detection. Furthermore, the detection results are almost invariant to strong database size growing (three orders of magnitude). The proposed approach was integrated in a difered real-time TV monitoring system which is able to control 40 000 hours of videos. The high quantity and variability of the results of this system open new data mining perspectives.Le domaine de l'indexation vidéo par le contenu s'intéresse à l'ensemble des techniques utiles pour analyser et exploiter des stocks de vidéos sans passer par des descriptions textuelles extérieures aux documents dont on dispose. Plus particulièrement, les travaux de cette thèse traitent du problème de la détection de copies basée sur le contenu. Pour résoudre conjointement les problèmes de qualité et de rapidité de la détection, liés à l'augmentation de la taille du catalogue de référence, nous avons proposé une méthode complète et efficace. Celle-ci tient compte à la fois des aspects traitement de l'image, des aspects base de données et de leurs interactions. La première partie du mémoire est consacrée à la présentation du contexte particulier de la détection de copies en vidéo et aux signatures utilisées pour caractériser le contenu des vidéos. L'originalité de notre approche est qu'elle est basée sur l'utilisation conjointe de signatures locales et d'une mesure de similarité globale calculée après la recherche des signatures similaires dans la base. Cette mesure globale n'est pas un simple vote comme dans les approches classiques car elle est précédée d'une étape de recalage originale entre l'objet candidat et les objets retournés par la recherche dans la base. La deuxième partie présente le coeur théorique du travail. Il s'agit d'une nouvelle méthode d'indexation et de recherche de descripteurs numériques s'intégrant dans le cadre de la recherche par similarité approximative. Il a en effet récemment été montré qu'une faible perte contrôlée dans la qualité des résultats de la recherche pouvait permettre des accélérations importantes du temps de recherche. Le principe de la technique présentée est d'étendre ce paradigme à la recherche à -près, contrairement aux autres approches qui s'intéressent uniquement à la recherche approximative des K plus proches voisins. L'originalité est de déterminer les régions pertinentes de l'espace selon un modèle théorique des distorsions que subissent les descripteurs, par des requêtes dites statistiques. Seule une portion de l'espace donnant une probabilité forte et contrôlée de trouver la réponse cherchée est visitée. Celle-ci est déterminée par une courbe de Hilbert et la partition qu'elle induit, simplifiant ainsi fortement l'accès à la base de descripteurs. L'évaluation expérimentale de la technique a montré que celle-ci est sous-linéaire avec un comportement asymptotique linéaire (mais que l'on observe que pour des tailles de base énormes) et que les performances en qualité sont stables. Il est également montré que les requêtes statistiques apportent une accélération conséquente par rapport aux requêtes à -près exactes. La troisième partie est consacrée à l'évaluation du système dans son ensemble et à la présentation de trois applications. Les expérimentations ont tout d'abord montré que le modèle théorique, bien que simple, permet un contrôle suffisant de la probabilité de retrouver un descripteur dans la pratique. Elles ont ensuite montré que la recherche approximative des descripteurs était particulièrement rentable lorsque l'on utilise des signatures locales puisque la perte de certains descripteurs n'influencent que très peu la qualité globale de la détection tout en accélérant fortement la recherche. Il a enfin été montré que la méthode globale était quasiment invariante à de très fortes augmentations de la quantité de vidéos dans la base (jusqu'à trois ordres de grandeur). L'approche proposée a été complètement intégrée et validée dans un système applicatif réel dont l'ampleur est sans précédent (le catalogue de référence contient jusqu'à 40 000 heures de vidéo, soit 500 fois plus que la moyenne des quantités utilisées dans l'état de l'art). Cela a soulevé des questionnements relatifs à l'utilisation des résultats issus de catalogues de référence aussi volumineux et d'envisager des pistes pour en extraire des informations de nature sémantique.LA ROCHELLE-BU (173002101) / SudocSudocFranceF