A l'ère d'Internet, la classification informatisée des images est d'une importance cruciale pour l’utilisation efficace de l'énorme quantité de données visuelles qui sont disponibles. Mais comment les ordinateurs peuvent-ils comprendre la signification d'une image? La Recherche d’Information Multimédia (RIM) est un domaine de recherche qui vise à construire des systèmes capables de reconnaître automatiquement le contenu d’une image. D'abord, des caractéristiques de bas niveau sont extraites et regroupées en signatures visuelles compactes. Ensuite, des techniques d'apprentissage automatique construisent des modèles qui font la distinction entre les différentes catégories d'images à partir de ces signatures. Ces modèles sont finalement utilisés pour reconnaître les propriétés d'une nouvelle image. Malgré les progrès dans le domaine, ces systèmes ont des performances en général limitées. Dans cette thèse, nous concevons un ensemble de contributions originales pour chaque étape de la chaîne RIM, en explorant des techniques provenant d'une variété de domaines qui ne sont pas traditionnellement liés avec le MMIR. Par exemple, nous empruntons la notion de saillance et l'utilisons pour construire des caractéristiques de bas niveau. Nous employons la théorie des Copulae étudiée en statistique économique, pour l'agrégation des caractéristiques. Nous réutilisons la notion de pertinence graduée, populaire dans le classement des pages Web, pour la récupération visuelle. Le manuscrit détaille nos solutions novatrices et montre leur efficacité pour la catégorisation d'image et de vidéo, et l’évaluation de l'esthétique. / In the internet era, computerized classification and discovery of image properties (objects, scene, emotions generated, aesthetic traits) is of crucial importance for the automatic retrieval of the huge amount of visual data surrounding us. But how can computers see the meaning of an image? Multimedia Information Retrieval (MMIR) is a research field that helps building intelligent systems that automatically recognize the image content and its characteristics. In general, this is achieved by following a chain process: first, low-level features are extracted and pooled into compact image signatures. Then, machine learning techniques are used to build models able to distinguish between different image categories based on such signatures. Such model will be finally used to recognize the properties of a new image. Despite the advances in the field, human vision systems still substantially outperform their computer-based counterparts. In this thesis we therefore design a set of novel contributions for each step of the MMIR chain, aiming at improving the global recognition performances. In our work, we explore techniques from a variety of fields that are not traditionally related with Multimedia Retrieval, and embed them into effective MMIR frameworks. For example, we borrow the concept of image saliency from visual perception, and use it to build low-level features. We employ the Copula theory of economic statistics for feature aggregation. We re-use the notion of graded relevance, popular in web page ranking, for visual retrieval frameworks. We explain in detail our novel solutions and prove their effectiveness for image categorization, video retrieval and aesthetics assessment.

Le cadre général de cette thèse est l'indexation sémantique et la recherche d'informations, appliquée à des documents multimédias. Plus précisément, nous nous intéressons à l'indexation sémantique des concepts dans des images et vidéos par les approches d'apprentissage actif, que nous utilisons pour construire des corpus annotés. Tout au long de cette thèse, nous avons montré que les principales difficultés de cette tâche sont souvent liées, en général, à l'fossé sémantique. En outre, elles sont liées au problème de classe-déséquilibre dans les ensembles de données à grande échelle, où les concepts sont pour la plupart rares. Pour l'annotation de corpus, l'objectif principal de l'utilisation de l'apprentissage actif est d'augmenter la performance du système en utilisant que peu d'échantillons annotés que possible, ainsi minimisant les coûts de l'annotations des données (par exemple argent et temps). Dans cette thèse, nous avons contribué à plusieurs niveaux de l'indexation multimédia et nous avons proposé trois approches qui succèdent des systèmes de l'état de l'art: i) l'approche multi-apprenant (ML) qui surmonte le problème de classe-déséquilibre dans les grandes bases de données, ii) une méthode de reclassement qui améliore l'indexation vidéo, iii) nous avons évalué la normalisation en loi de puissance et de l'APC et a montré son efficacité dans l'indexation multimédia. En outre, nous avons proposé l'approche ALML qui combine le multi-apprenant avec l'apprentissage actif, et nous avons également proposé une méthode incrémentale qui accélère l'approche proposé (ALML). En outre, nous avons proposé l'approche de nettoyage actif, qui aborde la qualité des annotations. Les méthodes proposées ont été tous validées par plusieurs expériences, qui ont été menées et évaluées sur des collections à grande échelle de l'indice de benchmark internationale bien connue, appelés TRECVID. Enfin, nous avons présenté notre système d'annotation dans le monde réel basé sur l'apprentissage actif, qui a été utilisé pour mener les annotations de l'ensemble du développement de la campagne TRECVID en 2011, et nous avons présenté notre participation à la tâche d'indexation sémantique de cette campagne, dans laquelle nous nous sommes classés à la 3ème place sur 19 participants. / The general framework of this thesis is semantic indexing and information retrieval, applied to multimedia documents. More specifically, we are interested in the semantic indexing of concepts in images and videos by the active learning approaches that we use to build annotated corpus. Throughout this thesis, we have shown that the main difficulties of this task are often related, in general, to the semantic-gap. Furthermore, they are related to the class-imbalance problem in large scale datasets, where concepts are mostly sparse. For corpus annotation, the main objective of using active learning is to increase the system performance by using as few labeled samples as possible, thereby minimizing the cost of labeling data (e.g. money and time). In this thesis, we have contributed in several levels of multimedia indexing and proposed three approaches that outperform state-of-the-art systems: i) the multi-learner approach (ML) that overcomes the class-imbalance problem in large-scale datasets, ii) a re-ranking method that improves the video indexing, iii) we have evaluated the power-law normalization and the PCA and showed its effectiveness in multimedia indexing. Furthermore, we have proposed the ALML approach that combines the multi-learner with active learning, and also proposed an incremental method that speeds up ALML approach. Moreover, we have proposed the active cleaning approach, which tackles the quality of annotations. The proposed methods were validated through several experiments, which were conducted and evaluated on large-scale collections of the well-known international benchmark, called TrecVid. Finally, we have presented our real-world annotation system based on active learning, which was used to lead the annotations of the development set of TrecVid 2011 campaign, and we have presented our participation at the semantic indexing task of the mentioned campaign, in which we were ranked at the 3rd place out of 19 participants.

Avec l’avènement de « l'ère des données », les besoins des systèmes de traitement de l'information en ressources de calcul ont explosé, dépassant largement les évolutions technologiques des processeurs modernes. Dans le domaine de l'apprentissage statistique en particulier, les paradigmes de calcul massivement distribués représentent la seule alternative praticable.L'algorithmique distribuée emprunte la plupart de ses concepts à l'algorithmique classique, centralisée et séquentielle, dans laquelle le comportement du système est décrit comme une suite d'instructions exécutées l'une après l'autre. L'importance de la communication entre unités de calcul y est généralement négligée et reléguée aux détails d'implémentation. Or, lorsque le nombre d'unités impliquées augmente, le poids des opérations locales s'efface devant les effets émergents propres aux larges réseaux d'unités. Pour conserver les propriétés désirables de stabilité, de prédictibilité et de programmabilité offertes par l'algorithmique centralisée, les paradigmes de calcul distribué doivent dès lors intégrer cette dimension qui relève de la théorie des graphes.Cette thèse propose un cadre algorithmique pour l'apprentissage statistique large échelle, qui prévient deux défaut majeurs des méthodes classiques : la centralisation et la synchronisation. Nous présentons ainsi plusieurs algorithmes basés sur des protocoles Gossip décentralisés et asynchrones, applicables aux problèmes de catégorisation, estimation de densité, réduction de dimension, classification et optimisation convexe. Ces algorithmes produisent des solutions identiques à leurs homologues centralisés, tout en offrant une accélération appréciable sur de larges réseaux pour un coût de communication très réduit. Ces qualités pratiques sont démontrées mathématiquement par une analyse de convergence détaillée. Nous illustrons finalement la pertinence des méthodes proposées sur des tâches d'indexation multimédia et de classification d'images. / With the advent of the "data era", the amount of computational resources required by information processing systems has exploded, largely exceeding the technological evolutions of modern processors. Specifically, contemporary machine learning applications necessarily resort to massively distributed computation.Distributed algorithmics borrows most of its concepts from classical centralized and sequential algorithmics, where the system's behavior is defined as a sequence of instructions, executed one after the other. The importance of communication between computation units is generally neglected and pushed back to implementation details. Yet, as the number of units grows, the impact of local operations vanishes behind the emergent effects related to the large network of units. To preserve the desirable properties of centralized algorithmics such as stability, predictability and programmability, distributed computational paradigms must encompass this graph-theoretical dimension.This thesis proposes an algorithmic framework for large scale machine learning, which prevent two major drawbacks of classical methods, namely emph{centralization} and emph{synchronization}. We therefore introduce several new algorithms based on decentralized and asynchronous Gossip protocols, for solving clustering, density estimation, dimension reduction, classification and general convex optimization problems, while offering an appreciable speed-up on large networks with a very low communication cost. These practical advantages are mathematically supported by a theoretical convergence analysis. We finally illustrate the relevance of proposed methods on multimedia indexing applications and real image classification tasks.

A extração de metadados semânticos de vídeos digitais para uso em serviços de personalização é importante, já que o conteúdo é adaptado segundo as preferências de cada usuário. Entretanto, apesar de serem encontradas várias propostas na literatura, as técnicas de indexação automática são capazes de gerar informações semânticas apenas quando o domínio do conteúdo é restrito. Alternativamente, existem técnicas para a criação manual dessas informações por profissionais, contudo, são dispendiosas e suscetíveis a erros. Uma possível solução seria explorar anotações colaborativas dos usuários, mas tal estratégia provoca a perda de individualidade dos dados, impedindo a extração de preferências do indivíduo a partir da interação. Este trabalho tem como objetivo propor uma arquitetura de personalização que permite a indexação multimídia de modo irrestrito e barato, utilizando anotações colaborativas, mas mantendo-se a individualidade dos dados para complementar o perfil de interesses do usuário com conceitos relevantes. A multimodalidade de metadados e de preferências também é explorada na presente tese, fornecendo maior robustez na extração dessas informações, e obtendo-se uma maior carga semântica que traz benefícios às aplicações. Como prova de conceito, este trabalho apresenta dois serviços de personalização que exploram a arquitetura proposta, avaliando os resultados por meio de comparações com abordagens previamente propostas na literatura / The extraction of semantic information from digital video is important to be used on personalization services because the content is adapted according to each users preferences. However, although it is possible to find several approaches in the literature, automatic indexing techniques are able to generate semantic metadata only when the contents domain is restricted. Alternatively, this information can be created manually by professionals, but this activity is time-consuming and error-prone. A possible solution would be to explore collaborative users annotations, but such approach has the disadvantage of lacking the individuality of annotations, hampering the extraction of users preferences from the interaction. This work has the objective of proposing a generic personalization architecture that allows multimedia indexing procedures to be accomplished in a cheap and unrestricted way. Such architecture uses collaborative annotations, but keeps the individuality of the data in order to augment the users profile with relevant concepts. The multimodality of metadata and users preferences is also explored in this work, which provides robustness during the extraction of semantic information, bringing benefits to applications. This work also presents two personalization services that explore the proposed architecture, along with evaluations that compare the obtained results with previously proposed approaches

L'indexation automatisée des documents image fixe et vidéo est un problème difficile en raison de la ``distance'' existant entre les tableaux de nombres codant ces documents et les concepts avec lesquels on souhaite les annoter (personnes, lieux, événements ou objets, par exemple). Des méthodes existent pour cela mais leurs résultats sont loin d'être satisfaisants en termes de généralité et de précision. Elles utilisent en général un ensemble unique de tels exemples et le considère d'une manière uniforme. Ceci n'est pas optimal car un même concept peut apparaître dans des contextes très divers et son apparence peut être très différente en fonction de ces contextes. Dans le cadre de cette thèse, nous avons considéré l'utilisation du contexte pour l'indexation des documents multimédia. Le contexte a largement été utilisé dans l'état de l'art pour traiter diverses problématiques. Dans notre travail, nous retenons les relations entre les concepts comme source de contexte sémantique. Pour le cas des vidéos, nous exploitons le contexte temporel qui modélise les relations entre les plans d'une même vidéo. Nous proposons plusieurs approches utilisant les deux types de contexte ainsi que leur combinaison, dans différents niveaux d'un système d'indexation. Nous présentons également le problème de détection simultanée de groupes de concepts que nous jugeons lié à la problématique de l'utilisation du contexte. Nous considérons que la détection d'un groupe de concepts revient à détecter un ou plusieurs concepts formant le groupe dans un contexte ou les autres sont présents. Nous avons étudié et comparé pour cela deux catégories d'approches. Toutes nos propositions sont génériques et peuvent être appliquées à n'importe quel système pour la détection de n'importe quel concept. Nous avons évalué nos contributions sur les collections de données TRECVid et VOC, qui sont des standards internationaux et reconnues par la communauté. Nous avons obtenu de bons résultats, comparables à ceux des meilleurs systèmes d'indexation évalués ces dernières années dans les compagnes d'évaluation précédemment citées. / The automated indexing of image and video is a difficult problem because of the``distance'' between the arrays of numbers encoding these documents and the concepts (e.g. people, places, events or objects) with which we wish to annotate them. Methods exist for this but their results are far from satisfactory in terms of generality and accuracy. Existing methods typically use a single set of such examples and consider it as uniform. This is not optimal because the same concept may appear in various contexts and its appearance may be very different depending upon these contexts. In this thesis, we considered the use of context for indexing multimedia documents. The context has been widely used in the state of the art to treat various problems. In our work, we use relationships between concepts as a source of semantic context. For the case of videos, we exploit the temporal context that models relationships between the shots of the same video. We propose several approaches using both types of context and their combination, in different levels of an indexing system. We also present the problem of multiple concept detection. We assume that it is related to the context use problematic. We consider that detecting simultaneously a set of concepts is equivalent to detecting one or more concepts forming the group in a context where the others are present. To do that, we studied and compared two types of approaches. All our proposals are generic and can be applied to any system for the detection of any concept. We evaluated our contributions on TRECVID and VOC collections, which are of international standards and recognized by the community. We achieved good results comparable to those of the best indexing systems evaluated in recent years in the evaluation campaigns cited previously.

L'explosion de la quantité de documents multimédias, suite à l'essor des technologies numériques, a rendu leur indexation très coûteuse et manuellement impossible. Par conséquent, le besoin de disposer de systèmes d'indexation capables d'analyser, de stocker et de retrouver les documents multimédias automatiquement, et en se basant sur leur contenu (audio, visuel), s'est fait ressentir dans de nombreux domaines applicatifs. Cependant, les techniques d'indexation actuelles rencontrent encore des problèmes de faisabilité ou de qualité. Leur performance reste très limitée et est dépendante de plusieurs facteurs comme la variabilité et la quantité de données à traiter. En effet, les systèmes d'indexation cherchent à reconnaître des concepts statiques, comme des objets (vélo, chaise,...), ou des événements (mariage, manifestation,...). Ces systèmes se heurtent donc au problème de variabilité de formes, de positions, de poses, d'illuminations, d'orientations des objets. Le passage à l'échelle pour pouvoir traiter de très grands volumes de données tout en respectant des contraintes de temps de calcul et de stockage est également une contrainte.Dans cette thèse, nous nous intéressons à l'amélioration de la performance globale de ces systèmes d'indexation de documents multimédias par le contenu. Pour cela nous abordons le problème sous différents angles et apportons quatre contributions à divers stades du processus d'indexation. Nous proposons tout d'abord une nouvelle méthode de fusion "doublement précoce " entre différentes modalités ou différentes sources d'informations afin d'exploiter au mieux la corrélation entre les modalités. Cette méthode est ensuite appliquée à la détection de scènes violentes dans les films. Nous développons ensuite une méthode faiblement supervisée pour la localisation des concepts basiques (comme les objets) dans les images qui pourra être utilisé plus tard comme un descripteur et une information supplémentaire pour la détection de concepts plus complexes (comme des événements). Nous traitons également la problématique de réduction du bruit généré par des annotations ambiguës sur les données d'apprentissage en proposant deux méthodes: une génération de nouvelles annotations au niveau des plans et une méthode de pondération des plans. Enfin, nous avons mis en place une méthode d'optimisation des représentations du contenu multimédia qui combine une réduction de dimension basée sur une ACP et des transformations non linéaires.Les quatre contributions sont testées et évaluées sur les collections de données faisant référence dans le domaine, comme TRECVid ou MediaEval. Elles ont participé au bon classement de nos soumissions dans ces campagnes. / A consequence of the rise of digital technology is that the quantity of available collections of multimedia documents is permanently and strongly increasing. The indexing of these documents became both very costly and impossible to do manually. In order to be able to analyze, classify and search multimedia documents, indexing systems have been defined. However, most of these systems suffer quality or practicability issues. Their performance is limited and depends on the data volume and data variability. Indexing systems analyze multimedia documents, looking for static concepts (bicycle, chair,...), or events (wedding, protest,...). Therefore, the variability in shapes, positions, lighting or orientation of objects hinders the process. Another aspect is that systems must be scalable. They should be able to handle big data while using reasonable amount of computing time and memory.The aim of this thesis is to improve the general performance of content-based multimedia indexing systems. Four main contributions are brought in this thesis for improving different stages of the indexing process. The first one is an "early-early fusion method" that merges different information sources in order to extract their deep correlations. This method is used for violent scenes detection in movies. The second contribution is a weakly supervised method for basic concept (objects) localization in images. This can be used afterwards as a new descriptor to help detecting complex concepts (events). The third contribution tackles the noise reduction problem on ambiguously annotated data. Two methods are proposed: a shot annotation generator, and a shot weighing method. The last contribution is a generic descriptor optimization method, based on PCA and non-linear transforms.These four contributions are tested and evaluated using reference data collections, including TRECVid and MediaEval. These contributions helped our submissions achieving very good rankings in those evaluation campaigns.

A extração de metadados semânticos de vídeos digitais para uso em serviços de personalização é importante, já que o conteúdo é adaptado segundo as preferências de cada usuário. Entretanto, apesar de serem encontradas várias propostas na literatura, as técnicas de indexação automática são capazes de gerar informações semânticas apenas quando o domínio do conteúdo é restrito. Alternativamente, existem técnicas para a criação manual dessas informações por profissionais, contudo, são dispendiosas e suscetíveis a erros. Uma possível solução seria explorar anotações colaborativas dos usuários, mas tal estratégia provoca a perda de individualidade dos dados, impedindo a extração de preferências do indivíduo a partir da interação. Este trabalho tem como objetivo propor uma arquitetura de personalização que permite a indexação multimídia de modo irrestrito e barato, utilizando anotações colaborativas, mas mantendo-se a individualidade dos dados para complementar o perfil de interesses do usuário com conceitos relevantes. A multimodalidade de metadados e de preferências também é explorada na presente tese, fornecendo maior robustez na extração dessas informações, e obtendo-se uma maior carga semântica que traz benefícios às aplicações. Como prova de conceito, este trabalho apresenta dois serviços de personalização que exploram a arquitetura proposta, avaliando os resultados por meio de comparações com abordagens previamente propostas na literatura / The extraction of semantic information from digital video is important to be used on personalization services because the content is adapted according to each users preferences. However, although it is possible to find several approaches in the literature, automatic indexing techniques are able to generate semantic metadata only when the contents domain is restricted. Alternatively, this information can be created manually by professionals, but this activity is time-consuming and error-prone. A possible solution would be to explore collaborative users annotations, but such approach has the disadvantage of lacking the individuality of annotations, hampering the extraction of users preferences from the interaction. This work has the objective of proposing a generic personalization architecture that allows multimedia indexing procedures to be accomplished in a cheap and unrestricted way. Such architecture uses collaborative annotations, but keeps the individuality of the data in order to augment the users profile with relevant concepts. The multimodality of metadata and users preferences is also explored in this work, which provides robustness during the extraction of semantic information, bringing benefits to applications. This work also presents two personalization services that explore the proposed architecture, along with evaluations that compare the obtained results with previously proposed approaches

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.