Depuis plusieurs décennies, le développement des technologies de numérisation et de stockage ont permis la mise en œuvre de nombreux projets de numérisation du patrimoine culturel.L'approvisionnement massif et continu de ces bases de données numériques du patrimoine culturel entraîne de nombreux problèmes d'indexation.En effet, il n'est plus possible d'effectuer une indexation manuelle de toutes les données.Pour indexer et rendre accessible facilement les données, des méthodes d'indexation automatique et d'aide à l'indexation se sont développées depuis plusieurs années.Cependant, les méthodes d'indexation automatique pour les documents non-textuels (image, vidéo, son, modèle 3D, …) sont encore complexes à mettre en œuvre pour de grands volumes de données.Dans cette thèse, nous nous intéressons en particulier à l'indexation automatique d'images.Pour effectuer des tâches d'indexation automatique ou d'aide à l'indexation, il est nécessaire de construire une méthode permettant d'évaluer la similarité entre deux images.Nos travaux sont basés sur les méthodes à signatures d'image ; ces méthodes consistent à résumer le contenu visuel de chaque image dans une signature (vecteur unique), puis d'utiliser ces signatures pour calculer la similarité entre deux images.Pour extraire les signatures, nous utilisons la chaîne d'extraction suivante : en premier, nous extrayons de l'image un grande nombre de descripteurs locaux ; puis nous résumons l'ensemble de ces descripteurs dans une signature de grande dimension ; enfin nous réduisons fortement la dimension de la signature.Les signatures de l'état de l'art basées sur cette chaîne d'extraction permettent d'obtenir de très bonnes performance en indexation automatique et en aide à l'indexation.Cependant, les méthodes de l'état de l'art ont généralement de forts coûts mémoires et calculatoires qui rendent impossible leurs mise en œuvre sur des grands volumes de données.Dans cette thèse, notre objectif est double : d'une part nous voulons améliorer les signatures d'images pour obtenir de très bonnes performances dans les problèmes d'indexation automatique ; d'autre part, nous voulons réduire les coûts de la chaîne de traitement, pour permettre le passage à l'échelle.Nous proposons des améliorations d'une signature d'image de l'état de l'art nommée VLAT (Vectors of Locally Aggregated Tensors).Ces améliorations permettent de rendre la signature plus discriminante tout en réduisant sa dimension.Pour réduire la dimension des signatures, nous effectuons une projection linéaire de la signature dans un espace de petite dimension.Nous proposons deux méthodes pour obtenir des projecteurs de réduction de dimension tout en conservant les performances des signatures d'origine.Notre première méthode consiste à calculer les projecteurs qui permettent d'approximer le mieux possible les scores de similarités entre les signatures d'origine.La deuxième méthode est basée sur le problème de recherche de quasi-copies ; nous calculons les projecteurs qui permettent de respecter un ensemble de contraintes sur le rang des images dans la recherche par rapport à l'image requête.L'étape la plus coûteuse de la chaîne d'extraction est la réduction de dimension de la signature à cause de la grande dimension des projecteurs.Pour les réduire, nous proposons d'utiliser des projecteurs creux en introduisant une contrainte de parcimonie dans nos méthodes de calcul des projecteurs.Comme il est généralement complexe de résoudre un problème d'optimisation avec une contrainte de parcimonie stricte, nous proposons pour chacun des problèmes une méthode pour obtenir une approximation des projecteurs creux recherchés.L'ensemble de ces travaux font l'objet d'expériences montrant l'intérêt pratique des méthodes proposées par comparaison avec les méthodes de l'état de l'art. / In the last decades, the development of scanning and storing technologies resulted in the development of many projects of cultural heritage digitization.The massive and continuous flow of numerical data in cultural heritage databases causes many problems for indexing.Indeed, it is no longer possible to perform a manual indexing of all data.To index and ease the access to data, many methods of automatic and semi-automatic indexing have been proposed in the last years.The current available methods for automatic indexing of non-textual documents (images, video, sound, 3D model, ...) are still too complex to implement for large volumes of data.In this thesis, we focus on the automatic indexing of images.To perform automatic or semi-automatic indexing, it is necessary to build an automatic method for evaluating the similarity between two images.Our work is based on image signature methods ; these methods involve summarising the visual content of each image in a signature (single vector), and then using these signatures to compute the similarity between two images.To extract the signatures, we use the following pipeline: First, we extract a large number of local descriptors of the image; Then we summarize all these descriptors in a large signature; Finally, we strongly reduce the dimensionality of the resulting signature.The state of the art signatures based on this pipeline provide very good performance in automatic indexing.However, these methods generally incur high storage and computational costs that make their implementation impossible on large volumes of data.In this thesis, our goal is twofold : First, we wish to improve the image signatures to achieve very good performance in automatic indexing problems ; Second, we want to reduce the cost of the processing chain to enable scalability.We propose to improve an image signature of the state of the art named VLAT (Vectors of Locally Aggregated Tensors).Our improvements increase the discriminative power of the signature.To reduce the size of the signatures, we perform linear projections of the signatures in a lower dimensional space.We propose two methods to compute the projectors while maintaining the performance of the original signatures.Our first approach is to compute the projectors that best approximate the similarities between the original signatures.The second method is based on the retrieval of quasi-copies; We compute the projectors that meet the constraints on the rank of retrieved images with respect to the query image.The most expensive step of the extraction pipeline is the dimentionality reduction step; these costs are due to the large dimentionality of the projectors.To reduce these costs, we propose to use sparse projectors by introducing a sparsity constraint in our methods.Since it is generally complex to solve an optimization problem with a strict sparsity constraint, we propose for each problem a method for approximating sparse projectors.This thesis work is the subject of experiments showing the practical value of the proposed methods in comparison with existing methods

La sélection d'un modèle approprié est l'une des tâches essentielles de l'apprentissage statistique. En général, pour une tâche d'apprentissage donnée, on considère plusieurs classes de modèles ordonnées selon un certain ordre de "complexité". Dans ce cadre, le processus de sélection de modèle revient à trouver la "complexité" optimale, permettant d'estimer un modèle assurant une bonne généralisation. Ce problème de sélection de modèle se résume à l'estimation d'un ou plusieurs hyperparamètres définissant la complexité du modèle, par opposition aux paramètres qui permettent de spécifier le modèle dans la classe de complexité choisie.<br>L'approche habituelle pour déterminer ces hyperparamètres consiste à utiliser une "grille". On se donne un ensemble de valeurs possibles et on estime, pour chacune de ces valeurs, l'erreur de généralisation du meilleur modèle. On s'intéresse, dans cette thèse, à une approche alternative consistant à calculer l'ensemble des solutions possibles pour toutes les valeurs des hyperparamètres. C'est ce qu'on appelle le chemin de régularisation. Il se trouve que pour les problèmes d'apprentissage qui nous intéressent, des programmes quadratiques paramétriques, on montre que le chemin de régularisation associé à certains hyperparamètres est linéaire par morceaux et que son calcul a une complexité numérique de l'ordre d'un multiple entier de la complexité de calcul d'un modèle avec un seul jeu hyper-paramètres.<br>La thèse est organisée en trois parties. La première donne le cadre général des problèmes d'apprentissage de type SVM (Séparateurs à Vaste Marge ou Support Vector Machines) ainsi que les outils théoriques et algorithmiques permettant d'appréhender ce problème. La deuxième partie traite du problème d'apprentissage supervisé pour la classification et l'ordonnancement dans le cadre des SVM. On montre que le chemin de régularisation de ces problèmes est linéaire par morceaux. Ce résultat nous permet de développer des algorithmes originaux de discrimination et d'ordonnancement. La troisième partie aborde successivement les problèmes d'apprentissage semi supervisé et non supervisé. Pour l'apprentissage semi supervisé, nous introduisons un critère de parcimonie et proposons l'algorithme de chemin de régularisation associé. En ce qui concerne l'apprentissage non supervisé nous utilisons une approche de type "réduction de dimension". Contrairement aux méthodes à base de graphes de similarité qui utilisent un nombre fixe de voisins, nous introduisons une nouvelle méthode permettant un choix adaptatif et approprié du nombre de voisins.

Cette thèse étudie l'intérêt du contexte pour améliorer l'interopérabilité entre ontologies hétérogènes, d'une manière qui permette leur évolution indépendante. Lors de collaborations, les organisations échangent leurs données, qui sont décrites par des concepts définis dans des ontologies. L'objectif est d'obtenir un service d'évaluation de tels concepts, basé sur le contexte.<br />Nous proposons une méthodologie pour déterminer, modeler et utiliser le contexte. En l'appliquant, nous découvrons trois usages du contexte qui contribuent à améliorer la réconciliation d'ontologies : Nous proposons de désambiguïser les sens pragmatiques possibles des concepts en comparant les "perspectives" avec lesquelles les concepts ont été développés ; de personnaliser en considérant le contexte des agents, constitué d'une sélection pertinente parmi les domaines et tâches de l'organisation ; d'évaluer la pertinence des données associées au concept pour la tâche qui a suscité le besoin en interopérabilité.

Les travaux de cette thèse concernent la comparaison des documents vidéo. Dans le domaine en pleine expansion de la vidéo numérique, les documents disponibles sont maintenant présents en quantité importante même dans les foyers. Opération de base de tout type d'analyse de contenus, en complément de la classification, de l'extraction et de la structuration, la comparaison dans le domaine de l'audiovisuel est d'une utilité qui n'est pas à démontrer.<br />Des approches classiques de comparaison se basent essentiellement sur l'ensemble des caractéristiques<br />bas niveaux des documents à comparer, en les considérant comme des vecteurs multidimensionnels. D'autres approches se basent sur la similarité des images composant la vidéo sans tenir compte de la composition temporelle du document ni de la bande<br />son. Le défaut que l'on peut reprocher à ces méthodes est qu'elles restreignent la comparaison à un simple opérateur binaire robuste au bruit. De tels opérateurs sont généralement utilisés afin d'identifier les différents exemplaires d'un même document. L'originalité de notre démarche réside dans le fait que nous introduisons la notion de la similarité de style<br />en s'inspirant des critères humains dans la comparaison des documents vidéo. Ces critères<br />sont plus souples, et n'imposent pas une similarité stricte de toutes les caractéristiques étudiées<br />à la fois.<br />En nous inspirant de la programmation dynamique et de la comparaison des séries chronologiques, nous définissons un algorithme d'extraction des similarités entre les séries de valeurs produites par l'analyse de caractéristiques audiovisuelles de bas-niveau. Ensuite, un second traitement générique approxime le résultat de l'algorithme de la longueur de la Plus<br />Longue Sous-Séquence Commune (PLSC) plus rapidement que ce dernier. Nous proposons une représentation des données issues de ces traitements sous la forme d'un schéma matriciel propre à la comparaison visuelle et immédiate de deux contenus. Cette matrice peut être également utilisée pour définir une mesure de similarité générique, applicable à des documents de même genre ou de genres hétérogènes.<br />Plusieurs applications ont été mises en place pour démontrer le comportement de la méthode de comparaison et de la mesure de similarité, ainsi que leur pertinence. Les expérimentations concernent essentiellement : - l'identification d'une structure organisationnelle en collection / sous-collection d'une base de documents, - la mise en évidence d'éléments<br />stylistiques dans un film de cinéma, - la mise en évidence de la grille de programmes d'un<br />flux de télévision.

Le recalage est un problème classique en vision par ordinateur qui intervient notamment dans de nombreuses tâches d'analyse des images médicales. Le principe général d'un algorithme de recalage est d'optimiser un critère mesurant la correspondance entre deux images sur un espace prédéterminé de transformations spatiales. Le choix du critère, appelé mesure de similarité, conditionne de façon déterminante la précision et la robustesse de l'algorithme. Il existe aujourd'hui un dictionnaire de mesures de similarité dans lequel le concepteur d'un programme choisit, en se fiant le plus souvent à son intuition et à son expérience, celle qui est la mieux adaptée à son problème particulier. Afin de rendre plus objectif un tel choix, cette thèse propose une méthodologie pour construire des mesures de similarité en fonction de modèles probabilistes de formation d'images. En considérant d'abord un modèle simple de liaison fonctionnelle entre les intensités des images, nous définissons une nouvelle classe de mesures de similarité liée à la notion de rapport de corrélation. Nous montrons expérimentalement que cette classe est adaptée au recalage rigide multimodal d'images acquises par résonance magnétique (IRM), scanner et scintigraphie. La méthode du rapport de corrélation est ensuite étendue au cas du recalage multimodal non-rigide au prix de quelques adaptations pratiques. Enfin, nous formulons le recalage d'images comme un problème général d'estimation par maximum de vraisemblance, ce qui nous permet de prendre en compte des modèles de dépendance inter-images plus complexes que des modèles fonctionnels. Cette approche est appliquée au recalage rigide d'images ultrasonores 3D et IRM.

Les dispersions affectant les structures fabriquées en série génèrent d'importants écarts de comportement entre des objets nominalement identiques. D'un point de vue vibro-acoustique, cette variabilité a été observée, quantifiée et ses origines ont même pu être identifiées et localisées sur certaines structures simples. Mais les effets de cette variabilité sur la perception du son émis par l'objet sont encore peu connus. Ce travail porte sur l'évaluation des effets des dispersions de structure sur l'identité sonore. Le son est aujourd'hui, à l'instar de n'importe quel composant du produit, conçu pour répondre aux attentes du client. Il se peut ainsi que l'identité sonore, résultat de cette phase de design sonore, soit elle aussi sujette à d'importantes variabilités. Dans un premier temps, la stabilité de descripteurs perceptifs utilisés classiquement pour décrire la perception de bruit intérieur d'automobiles a été évaluée sur un panel de véhicules dont les dispersions n'ont pas été contrôlées. L'évolution de l'identité sonore a ainsi été observée sur une population de produits. Puis l'étude s'est concentrée sur un système simple dont plusieurs caractéristiques physiques peuvent être finement contrôlées. Nous avons montré que la démarche par plan d'expérience fractionnaire peut être utilisée pour mesurer la contribution des facteurs et de leurs éventuelles interactions à la perception du bruit de ce système. Cette démarche a ensuite été utilisée pour un second cas, pour lequel les sons étaient synthétisés. Différentes analyses perceptives ont été menées (mesure de la similarité des objets dispersés par rapport à l'objet de référence et catégorisation libre des sons de synthèse), dont les résultats concordants ont permis de mettre en évidence les facteurs les plus influents. Cependant, une dernière expérience a montré que, malgré les dispersions pouvant affecter ces facteurs, des différences d'identité sonore peuvent être perçues sur un panel d'objets identiques mais ne conduisent pas à des confusions avec des objets nominalement différents.

La recherche d'information (RI) est un domaine prépondérant dans la vie contemporaine car elle permet de disposer d'éléments d'informations qui permettent d'agir et de prendre des décisions face à une situation donnée. En effet, l'objectif d'une RI est de s'informer, d'apprendre de nouvelles notions que nous ne maîtrisons pas. La disponibilité et la pertinence de ces nouvelles informations ont donc une très grande influence sur la prise de décision. La plupart des moteurs de recherche actuels utilisent des index regroupant les mots représentatifs des documents afin de permettre leur recherche ultérieure. Dans ces méthodes, les documents et les requêtes sont considérées comme des sacs de mots, non porteurs de sens. L'une des méthodes innovantes actuelles est l'indexation et la recherche sémantique des documents. Il s'agit de mieux prendre en compte le besoin de l'utilisateur en considérant la sémantique des éléments textuels. Nous nous intéressons à cet aspect de la RI en considérant une indexation et une recherche à base d'ontologies de domaine. Les solutions que nous proposons visent à améliorer la pertinence des réponses d'un système par rapport au thème de la recherche. Le discours contenu dans un document ou dans une requête ne sont pas les seuls éléments à prendre en compte pour espérer mieux satisfaire l'utilisateur. D'autres éléments relatifs au contexte de sa recherche doivent aussi être pris en compte. La granularité des informations à restituer à l'utilisateur est un autre aspect. Nous nous sommes intéressés à ces différents aspects et avons développé un méta-modèle de représentation multi-facette des documents en vue de leur accès sémantique. Dans notre modèle, le document est vu selon différentes dimensions dont la structure logique, la structure physique, la sémantique des contenus ainsi que leurs évolutions dans le temps. Nous avons également proposé des mesures de similarité sémantique entre concepts et une fonction de similarité entre les graphes d'annotation des requêtes et ceux des documents. Pour évaluer et valider nos solutions, nous avons instancié ce modèle dans trois domaines distincts : l'apprentissage en ligne, la maintenance automobile et les partitions musicales Braille. Nous avons également évalué les résultats en termes de rappel/précision des fonctions que nous avons proposées et montré leur supériorité par rapport à l'état de l'art.

La génomique moléculaire fait face en ce début de siècle à de nouvelles situations qu'elle doit prendre en compte. D'une part, depuis une dizaine d'années, la quantité de données disponibles croît<br />de manière exponentielle. D'autre part, la recherche dans le domaine<br />implique de nouvelles questions dont les formulations in silico<br />génèrent des problèmes algorithmiquement difficiles à résoudre.<br /><br />Parmi ces problèmes, certains concernent notamment l'étude de réarrangements génomiques dont les duplications et les éléments transposables. Ils imposent que l'on soit en mesure de détecter précisément et efficacement de longues répétitions approchées et multiples dans les génomes. Par répétition multiple, nous désignons<br />des répétitions ayant au moins deux copies dans une séquence d'ADN, ou ayant des copies dans au moins deux séquences d'ADN distinctes. De plus, ces répétitions sont approchées dans le sens où des erreurs existent entre les copies d'une même répétition.<br /><br />La recherche de répétitions approchées multiples peut être résolue par des algorithmes d'alignements multiples locaux mais ceux-ci présentent une complexité exponentielle en la taille de l'entrée, et ne sont donc pas applicables à des données aussi grandes que des génomes. C'est pourquoi, de nouvelles techniques doivent être créées pour répondre à ces nouveaux besoins. <br /><br />Dans cette thèse, une approche de filtrage des séquences d'ADN est<br />proposée. Le but d'une telle approche est de supprimer rapidement et<br />efficacement, parmi des textes représentant des séquences d'ADN, de<br />larges portions ne pouvant pas faire partie de répétitions. Les données filtrées, limitées en majorité aux portions pertinentes, peuvent alors être fournies en entrée d'un algorithme d'alignement multiple local.<br /><br /><br />Les filtres proposés appliquent une condition nécessaire aux séquences pour n'en conserver que les portions qui la respectent. Les travaux que nous présentons ont porté sur la création de conditions de filtrage, à la fois efficaces et simples à appliquer d'un point de vue algorithmique. À partir de ces conditions de filtrage, deux filtres, Nimbus et Ed'Nimbus, ont été créés. Ces filtres sont appelés exacts car il ne suppriment jamais de données contenant effectivement des occurrences de répétitions respectant les caractéristiques fixées par un utilisateur. L'efficacité du point de vue de la simplicité d'application et de celui de la précision du filtrage obtenu, conduit à de très bons résultats en pratique. Par exemple, le temps utilisé par des algorithmiques de recherche de répétitions ou d'alignements multiples peut être réduit de plusieurs ordres de grandeur en utilisant les filtres proposés.<br /><br />Il est important de noter que les travaux présentés dans cette thèse<br />sont inspirés par une problématique biologique mais ils sont également généraux et peuvent donc être appliqués au filtrage de tout type de textes afin d'y détecter de grandes portions répétées.

La sélection d'un modèle approprié est l'une des tâches essentielles de l'apprentissage statistique. En général, pour une tâche d'apprentissage donnée, on considère plusieurs classes de modèles ordonnées selon un certain ordre de " complexité". Dans ce cadre, le processus de sélection de modèle revient 'a trouver la " complexité " optimale, permettant d'estimer un modèle assurant une bonne généralisation. Ce problème de sélection de modèle se résume à l'estimation d'un ou plusieurs hyper-paramètres définissant la complexité du modèle, par opposition aux paramètres qui permettent de spécifier le modèle dans la classe de complexité choisie. L'approche habituelle pour déterminer ces hyper-paramètres consiste à utiliser une " grille ". On se donne un ensemble de valeurs possibles et on estime, pour chacune de ces valeurs, l'erreur de généralisation du meilleur modèle. On s'intéresse, dans cette thèse, à une approche alternative consistant à calculer l'ensemble des solutions possibles pour toutes les valeurs des hyper-paramètres. C'est ce qu'on appelle le chemin de régularisation. Il se trouve que pour les problèmes d'apprentissage qui nous intéressent, des programmes quadratiques paramétriques, on montre que le chemin de régularisation associé à certains hyper-paramètres est linéaire par morceaux et que son calcul a une complexité numérique de l'ordre d'un multiple entier de la complexité de calcul d'un modèle avec un seul jeu hyper-paramètres. La thèse est organisée en trois parties. La première donne le cadre général des problèmes d'apprentissage de type SVM (Séparateurs à Vaste Marge ou Support Vector Machines) ainsi que les outils théoriques et algorithmiques permettant d'appréhender ce problème. La deuxième partie traite du problème d'apprentissage supervisé pour la classification et l'ordonnancement dans le cadre des SVM. On montre que le chemin de régularisation de ces problèmes est linéaire par morceaux. Ce résultat nous permet de développer des algorithmes originaux de discrimination et d'ordonnancement. La troisième partie aborde successivement les problèmes d'apprentissage semi supervisé et non supervisé. Pour l'apprentissage semi supervisé, nous introduisons un critère de parcimonie et proposons l'algorithme de chemin de régularisation associé. En ce qui concerne l'apprentissage non supervisé nous utilisons une approche de type " réduction de dimension ". Contrairement aux méthodes à base de graphes de similarité qui utilisent un nombre fixe de voisins, nous introduisons une nouvelle méthode permettant un choix adaptatif et approprié du nombre de voisins.

L'apprentissage automatique consiste à concevoir des programmes informatiques capables d'apprendre à partir de leurs environnement, ou bien à partir de données. Il existe différents types d'apprentissage, selon que l'on cherche à faire apprendre au programme, et également selon le cadre dans lequel il doit apprendre, ce qui constitue différentes tâches. Les mesures de similarité jouent un rôle prépondérant dans la plupart de ces tâches, c'est pourquoi les travaux de cette thèse se concentrent sur leur étude. Plus particulièrement, nous nous intéressons à la classification de données, qui est une tâche d'apprentissage dit non supervisé, dans lequel le programme doit organiser un ensemble d'objets en plusieurs classes distinctes, de façon à regrouper les objets similaires ensemble. Dans de nombreuses applications, ces objets (des documents par exemple) sont décrits à l'aide de leurs liens à d'autres types d'objets (des mots par exemple), qui peuvent eux-même être classifiés. On parle alors de co-classification, et nous étudions et proposons dans cette thèse des améliorations de l'algorithme de calcul de co-similarités XSim. Nous montrons que ces améliorations permettent d'obtenir de meilleurs résultats que les méthodes de l'état de l'art. De plus, il est fréquent que ces objets soient liés à plus d'un autre type d'objets, les données qui décrivent ces multiples relations entre différents types d'objets sont dites multivues. Les méthodes classiques ne sont généralement pas capables de prendre en compte toutes les informations contenues dans ces données. C'est pourquoi nous présentons dans cette thèse l'algorithme de calcul multivue de similarités MVSim, qui peut être vu comme une extension aux données multivues de l'algorithme XSim. Nous montrons que cette méthode obtient de meilleures performances que les méthodes multivues de l'état de l'art, ainsi que les méthodes monovues, validant ainsi l'apport de l'aspect multivue. Finalement, nous proposons également d'utiliser l'algorithme MVSim pour classifier des données classiques monovues de grandes tailles, en les découpant en différents ensembles. Nous montrons que cette approche permet de gagner en temps de calcul ainsi qu'en taille mémoire nécessaire, tout en dégradant relativement peu la classification par rapport à une approche directe sans découpage.