Le développement des techniques de traitement des requêtes de classement est un axe de recherche très actif dans le domaine de la recherche d'information. Plusieurs applications nécessitent le traitement des requêtes de classement multicritères, telles que les méta-moteurs de recherche sur le web, la recherche dans les réseaux sociaux, la recherche dans les bases de documents multimédia, etc. Contrairement aux requêtes booléennes traditionnelles, dans lesquelles le filtrage est basé sur des prédicats qui retournent vrai ou faux, les requêtes de classement utilisent des prédicats de similarité retournant un score de pertinence. Ces requêtes spécifient une fonction d'agrégation qui combine les scores individuels produits par les prédicats de similarité permettant de calculer un score global pour chaque objet. Les k objets avec les meilleurs scores globaux sont retournés dans le résultat final. Dans cette thèse, nous étudions dans un premier temps les techniques et algorithmes proposés dans la littérature conçus pour le traitement des requêtes top-k multicritères dans des contextes spécifiques de type et de coût d'accès aux scores, et nous proposons un cadre générique capable d'exprimer tous ces algorithmes. Ensuite, nous proposons une nouvelle stratégie en largeur «breadth-first», qui maintient l'ensemble courant des k meilleurs objets comme un tout, à la différence des stratégies en profondeur habituelles qui se focalisent sur le meilleur candidat. Nous présentons un nouvel algorithme «Breadth-Refine» (BR), basé sur cette stratégie et adaptable à n'importe quelle configuration de type et de coût d'accès aux scores. Nous montrons expérimentalement la supériorité de l'algorithme BR sur les algorithmes existants. Dans un deuxième temps, nous proposons une adaptation des algorithmes top-k à la recherche approximative, dont l'objectif est de trouver un compromis entre le temps de recherche et la qualité du résultat retourné. Nous explorons l'approximation par arrêt prématuré de l'exécution et proposons une première étude expérimentale du potentiel d'approximation des algorithmes top-k. Dans la dernière partie de la thèse, nous nous intéressons à l'application des techniques top-k multicritères à la recherche par le contenu dans les grandes bases de données multimédia. Dans ce contexte, un objet multimédia (une image par exemple) est représenté par un ou plusieurs descripteurs, en général sous forme de vecteurs numériques qui peuvent être vus comme des points dans un espace multidimensionnel. Nous explorons la recherche des k plus proches voisins (k-ppv) dans ces espaces et proposons une nouvelle technique de recherche k-ppv approximative «Multi-criteria Search Algorithm » (MSA) basée sur les principes des algorithmes top-k. Nous comparons MSA à des méthodes de l'état de l'art dans le contexte des grandes bases multimédia où les données ainsi que les structures d'index sont stockées sur disque, et montrons qu'il produit rapidement un très bon résultat approximatif. / Efficient processing of ranking queries is an important issue in today information retrieval applications such as meta-search engines on the web, information retrieval in social networks, similarity search in multimedia databases, etc. We address the problem of top-k multi-criteria query processing, where queries are composed of a set of ranking predicates, each one expressing a measure of similarity between data objects on some specific criteria. Unlike traditional Boolean predicates returning true or false, similarity predicates return a relevance score in a given interval. The query also specifies an aggregation function that combines the scores produced by the similarity predicates. Query results are ranked following the global score and only the best k ones are returned.In this thesis, we first study the state of the art techniques and algorithms designed for top-k multi-criteria query processing in specific conditions for the type of access to the scores and cost settings, and propose a generic framework able to express any top-k algorithm. Then we propose a new breadth-first strategy that maintains the current best k objects as a whole instead of focusing only on the best one such as in all the state of the art techniques. We present Breadth-Refine (BR), a new top-k algorithm based on this strategy and able to adapt to any combination of source access types and to any cost settings. Experiments clearly indicate that BR successfully adapts to various settings, with better results than state of the art algorithms.Secondly, we propose an adaptation of top-k algorithms to approximate search aiming to a compromise between execution time and result quality. We explore approximation by early stopping of the execution and propose a first experimental study of the approximation potential of top-k algorithms. Finally, we focus on the application of multi-criteria top-k techniques to Large Scale Content-Based Image Retrieval. In this context an image is represented by one or several descriptors, usually numeric vectors that can be seen as points in a multidimensional space. We explore the k-Nearest Neighbors search on such space and propose “Multi-criteria Search Algorithm” (MSA) a new technique for approximate k-NN based on multi-criteria top-k techniques. We compare MSA with state of the art methods in the context of large multimedia databases, where the database and the index structure are stored on disk, and show that MSA quickly produces very good approximate results.

Cette th`ese traite de l'estimation statistique distribu ́e, avec la motivation de, et l'application `a l'indexation multim ́edia par le contenu. Les algorithmes et les donn ́ees de divers contributeurs coop ́ereront vers un apprentissage statistique collectif. La contribution est un arrangement pour estimer une densit ́e de probabilit ́e multivariable, dans le cas ou` cette densit ́e prend la forme d'un mod`ele de m ́elange gaussien. Dans ce cadre, l'agr ́egation des mod`eles probabilistes de m ́elanges gaussiens de la mˆeme classe, mais estim ́es `a plusieurs nœuds sur diff ́erents ensembles de donn ́ees, est une n ́ecessit ́e typique `a laquelle nous nous int ́eressons dans cette th`ese. Les approches propo- s ́ees pour la fusion de m ́elanges gaussiens exigent uniquement le calcul mod ́er ́e `a chaque nœud et peu de donn ́ees de transit entre les nœuds. Ces deux propri ́et ́es sont obtenues en agr ́egeant des mod`eles via leurs (peu) param`etres plutˆot que par les donn ́ees multim ́edia. Dans la premi`ere approche, en supposant que les m ́elanges sont estim ́es ind ́ependamment, nous propageons leurs param`etres de fa ̧con d ́ecentralis ́ee (gossip), dans un r ́eseau, et agr ́egeons les mod`eles `a partir des nœuds reli ́es entre eux, pour am ́eliorer l'estimation. Les mod`eles de m ́elange sont en fait concat ́en ́es puis r ́eduits `a un nombre appropri ́e de composants gaussiens. Une modification de la divergence de Kullback conduit `a un processus it ́eratif pour estimer ce mod`ele agr ́eg ́e. Afin d'ap- porter une am ́elioration, l'agr ́egation est r ́ealis ́ee par la mod ́elisation bay ́esienne du probl`eme de groupement de composant de mod`ele de m ́elange gaussien et est r ́esolue en utilisant la m ́ethode variationnelle, appliqu ́ee au niveau de composant. Cela permet de d ́eterminer, par un processus simple, peu couˆteux et pr ́ecis, les attributions des composants qui devraient ˆetre agr ́eg ́es et le nombre de composants dans le m ́elange apr`es l'agr ́egation. Comme seulement les param`etres du mod`ele sont ́echang ́es sur le r ́eseau, le calcul et la charge du r ́eseau restent tr`es mod ́er ́es.

Depuis quelques années, nous assistons à l'augmentation croissante de gigantesques collections de musique en ligne. Ce phénomène a attiré l'attention de nombreux chercheurs. En effet, le besoin urgent de développer des outils et des méthodes qui permettent d'interagir avec ces énormes bibliothèques de musique numérique pose des défis scientifiques complexes. Le domaine de la recherche d'information musicale (Music Information Retrieval, MIR) est ainsi devenu très actif depuis une dizaine d'années. Ce domaine général inclut celui de l'indexation musicale dans lequel s'inscrit cette thèse qui a pour but d'aider au stockage, à la diffusion et la consultation des gigantesques collections de musique en ligne. Ce domaine ouvre de nombreuses perspectives pour l'industrie et la recherche liées aux activités multimédia. Dans cette thèse, nous nous intéressons au problème de l'extraction automatique d'informations de contenu d'un signal audio de musique. La plupart des travaux existants abordent ce problème en considérant les attributs musicaux de manière indépendante les uns vis-à-vis des autres. Cependant les morceaux de musique sont extrèmement structurés du point de vue de l'harmonie et du rythme et leur estimation devrait se faire en tenant compte du contexte musical, comme le fait un musicien lorsqu'il analyse un morceau de musique. Nous nous concentrons sur trois descripteurs musicaux liés aux structures harmoniques, métriques et tonales d'un morceau de musique. Plus précisément, nous cherchons à en estimer la progression des accords, les premiers temps et la tonalité. L'originalité de notre travail consiste à construire un modèle qui permet d'estimer de manière conjointe ces trois attributs musicaux. Notre objectif est de montrer que l'estimation des divers descripteurs musicaux est meilleure si on tient compte de leurs dépendances mutuelles que si on les estime de manière indépendante. Nous proposons au cours de ce travail un ensemble de protocoles de comparaison, de métriques de performances et de nouvelles bases de données de test afin de pouvoir évaluer les différentes méthodes étudiées. Afin de valider notre approche, nous présentons également les résultats de nos participations à des campagnes d'évaluation internationales. Dans un premier temps, nous examinons plusieurs représentations typiques du signal audio afin de choisir celle qui est la plus appropriée à l'analyse du contenu harmonique d'un morceau de musique. Nous explorons plusieurs méthodes qui permettent d'extraire un chromagram du signal et les comparons à travers un protocole d'évaluation original et une nouvelle base de données que nous avons annotée. Nous détaillons et expliquons les raisons qui nous ont amenés à choisir la représentation que nous utilisons dans notre modèle. Dans notre modèle, les accords sont considérés comme un attribut central autour duquel les autres descripteurs musicaux s'organisent. Nous étudions le problème de l'estimation automatique de la suite des accords d'un morceau de musique audio en utilisant les _chromas_ comme observations du signal. Nous proposons plusieurs méthodes basées sur les modèles de Markov cachés (hidden Markov models, HMM), qui permettent de prendre en compte des éléments de la théorie musicale, le résultat d'expériences cognitives sur la perception de la tonalité et l'effet des harmoniques des notes de musique. Les différentes méthodes sont évaluées et comparées pour la première fois sur une grande base de données composée de morceaux de musique populaire. Nous présentons ensuite une nouvelle approche qui permet d'estimer de manière simultanée la progression des accords et les premiers temps d'un signal audio de musique. Pour cela, nous proposons une topologie spécifique de HMM qui nous permet de modéliser la dépendance des accords par rapport à la structure métrique d'un morceau. Une importante contribution est que notre modèle peut être utilisé pour des structures métriques complexes présentant par exemple l'insertion ou l'omission d'un temps, ou des changements dans la signature rythmique. Le modèle proposé est évalué sur un grand nombre de morceaux de musique populaire qui présentent des structures métriques variées. Nous comparons les résultats d'un modèle semi-automatique, dans lequel nous utilisons les positions des temps annotées manuellement, avec ceux obtenus par un modèle entièrement automatique où la position des temps est estimée directement à partir du signal. Enfin, nous nous penchons sur la question de la tonalité. Nous commençons par nous intéresser au problème de l'estimation de la tonalité principale d'un morceau de musique. Nous étendons le modèle présenté ci-dessus à un modèle qui permet d'estimer simultanément la progression des accords, les premiers temps et la tonalité principale. Les performances du modèle sont évaluées à travers des exemples choisis dans la musique populaire. Nous nous tournons ensuite vers le problème plus complexe de l'estimation de la tonalité locale d'un morceau de musique. Nous proposons d'aborder ce problème en combinant et en étendant plusieurs approches existantes pour l'estimation de la tonalité principale. La spécificité de notre approche est que nous considérons la dépendance de la tonalité locale par rapport aux structures harmonique et métrique. Nous évaluons les résultats de notre modèle sur une base de données originale composée de morceaux de musique classique que nous avons annotés.

La question de recherche des objets vidéo basés sur le contenu lui-même, est de plus en plus difficile et devient un élément obligatoire pour les moteurs de recherche vidéo. Cette thèse présente un cadre pour la recherche des objets vidéo définis par l'utilisateur et apporte deux grandes contributions. La première contribution, intitulée DOOR (Dynamic Object Oriented Retrieval), est un cadre méthodologique pour la recherche et récupération des instances d'objets vidéo sélectionnés par un utilisateur, tandis que la seconde contribution concerne le support offert pour la recherche des vidéos, à savoir la navigation dans les vidéo, le système de récupération de vidéos et l'interface avec son architecture sous-jacente.Dans le cadre DOOR, l'objet comporte une représentation hybride obtenues par une sur-segmentation des images, consolidé avec la construction des graphs d'adjacence et avec l'agrégation des points d'intérêt. L'identification des instances d'objets à travers plusieurs vidéos est formulée comme un problème d'optimisation de l'énergie qui peut approximer un tache NP-difficile. Les objets candidats sont des sous-graphes qui rendent une énergie optimale vers la requête définie par l'utilisateur. Quatre stratégies d'optimisation sont proposées: Greedy, Greedy relâché, recuit simulé et GraphCut. La représentation de l'objet est encore améliorée par l'agrégation des points d'intérêt dans la représentation hybride, où la mesure de similarité repose sur une technique spectrale intégrant plusieurs types des descripteurs. Le cadre DOOR est capable de s'adapter à des archives vidéo a grande échelle grâce à l'utilisation de représentation sac-de-mots, enrichi avec un algorithme de définition et d'expansion de la requête basée sur une approche multimodale, texte, image et vidéo. Les techniques proposées sont évaluées sur plusieurs corpora de test TRECVID et qui prouvent leur efficacité.La deuxième contribution, OVIDIUS (On-line VIDeo Indexing Universal System) est une plate-forme en ligne pour la navigation et récupération des vidéos, intégrant le cadre DOOR. Les contributions de cette plat-forme portent sur le support assuré aux utilisateurs pour la recherche vidéo - navigation et récupération des vidéos, interface graphique. La plate-forme OVIDIUS dispose des fonctionnalités de navigation hiérarchique qui exploite la norme MPEG-7 pour la description structurelle du contenu vidéo. L'avantage majeur de l'architecture propose c'est sa structure modulaire qui permet de déployer le système sur terminaux différents (fixes et mobiles), indépendamment des systèmes d'exploitation impliqués. Le choix des technologies employées pour chacun des modules composant de la plate-forme est argumentée par rapport aux d'autres options technologiques.

La question de recherche des objets vidéo basés sur le contenu lui-même, est de plus en plus difficile et devient un élément obligatoire pour les moteurs de recherche vidéo. Cette thèse présente un cadre pour la recherche des objets vidéo définis par l'utilisateur et apporte deux grandes contributions. La première contribution, intitulée DOOR (Dynamic Object Oriented Retrieval), est un cadre méthodologique pour la recherche et récupération des instances d'objets vidéo sélectionnés par un utilisateur, tandis que la seconde contribution concerne le support offert pour la recherche des vidéos, à savoir la navigation dans les vidéo, le système de récupération de vidéos et l'interface avec son architecture sous-jacente.Dans le cadre DOOR, l’objet comporte une représentation hybride obtenues par une sur-segmentation des images, consolidé avec la construction des graphs d’adjacence et avec l’agrégation des points d'intérêt. L'identification des instances d'objets à travers plusieurs vidéos est formulée comme un problème d’optimisation de l'énergie qui peut approximer un tache NP-difficile. Les objets candidats sont des sous-graphes qui rendent une énergie optimale vers la requête définie par l'utilisateur. Quatre stratégies d'optimisation sont proposées: Greedy, Greedy relâché, recuit simulé et GraphCut. La représentation de l'objet est encore améliorée par l'agrégation des points d'intérêt dans la représentation hybride, où la mesure de similarité repose sur une technique spectrale intégrant plusieurs types des descripteurs. Le cadre DOOR est capable de s’adapter à des archives vidéo a grande échelle grâce à l'utilisation de représentation sac-de-mots, enrichi avec un algorithme de définition et d’expansion de la requête basée sur une approche multimodale, texte, image et vidéo. Les techniques proposées sont évaluées sur plusieurs corpora de test TRECVID et qui prouvent leur efficacité.La deuxième contribution, OVIDIUS (On-line VIDeo Indexing Universal System) est une plate-forme en ligne pour la navigation et récupération des vidéos, intégrant le cadre DOOR. Les contributions de cette plat-forme portent sur le support assuré aux utilisateurs pour la recherche vidéo - navigation et récupération des vidéos, interface graphique. La plate-forme OVIDIUS dispose des fonctionnalités de navigation hiérarchique qui exploite la norme MPEG-7 pour la description structurelle du contenu vidéo. L'avantage majeur de l'architecture propose c’est sa structure modulaire qui permet de déployer le système sur terminaux différents (fixes et mobiles), indépendamment des systèmes d'exploitation impliqués. Le choix des technologies employées pour chacun des modules composant de la plate-forme est argumentée par rapport aux d'autres options technologiques. / With the ever increasing amount of available video content on video repositories the issue of content-based video objects retrieval is growing in difficulty and becomes a mandatory feature for video search engines.The present thesis advances a user defined video object retrieval framework and brings two major contributions. The first contribution is a methodological framework for user selected video object instances retrieval, entitled DOOR (Dynamic Object Oriented Retrieval), while the second one concerns the support offered for video retrieval, namely the video navigation and retrieval system and interface and its underlying architecture.Under the DOOR framework, the user defined video object comports a hybrid representation obtained by over-segmenting the frames, constructing region adjacency graphs and aggregating interest points. The identification of object instances across multiple videos is formulated as an energy optimization problem approximating an NP-hard problem. Object candidates are sub-graphs that yield an optimum energy towards the user defined query. In order to obtain the optimum energy four optimization strategies are proposed: Greedy, Relaxed Greedy, Simulated Annealing and GraphCut. The region-based object representation is further improved by the aggregation of interest points into a hybrid object representation. The similarity between an object and a frame is achieved with the help of a spectral matching technique integrating both colorimetric and interest points descriptors.The DOOR framework is suitable to large scale video archives through the use of a Bag-of-Words representation enriched with a query definition and expansion mechanism based on a multi-modal, text-image-video principle.The performances of the proposed techniques are evaluated on multiple TRECVID video datasets prooving their effectiveness.The second contribution is related to the user support for video retrieval - video navigation, video retrieval, graphical interface - and consists in the OVIDIUS (On-line VIDeo Indexing Universal System) on-line video browsing and retrieval platform. The OVIDIUS platform features hierarchical video navigation functionalities that exploit the MPEG-7 approach for structural description of video content. The DOOR framework is integrated in the OVIDIUS platform, ensuring the search functionalities of the system. The major advantage of the proposed system concerns its modular architecture which makes it possible to deploy the system on various terminals (both fixed and mobile), independently of the exploitation systems involved. The choice of the technologies employed for each composing module of the platform is argumented in comparison with other technological options. Finally different scenarios and use cases for the OVIDIUS platform are presented.