Idarrou, Ali (2013) Entreposage de documents multimédias : comparaison de structures. École doctorale Mathématiques, Informatique et Télécommunications (Toulouse).

Preview

Text Download (7MB) | Preview

Abstract

Le volume de documents multimédias disponible aujourd’hui, et qui ne cesse d’augmenter, constitue une source d’information importante. Cependant, toute cette information serait sans intérêt si elle n’est pas exploitée efficacement. Gérer et exploiter de telles sources nécessite d’avoir à disposition des outils automatiques permettant de faciliter l’accès à des granules (l'information fine) documentaires, indépendamment de l’hétérogénéité sous-jacentes de ces documents en termes de type, taille, format, contenu, structure, etc. La classification automatique est une solution qui permet d’organiser et de structurer une large collection de documents afin de réduire l’espace de recherche et par conséquent d’améliorer les performances du processus d’accès à l’information. Les approches qui ont abordé la classification documentaire se distinguent par le modèle utilisé pour représenter les documents et par la démarche utilisée pour classer ces documents. S’agissant des documents multimédias, la problématique de classification découle de la complexité de leur représentation. En effet, un document multimédia est composé de plusieurs objets de différentes natures : image, texte, son, etc. Il est multi-structuré par essence ; issu de la composition de plusieurs sous-documents et chaque sous-document a une ou plusieurs structures. Ces structures peuvent être de même nature ou de natures différentes (structure physique, logique, temporelle, etc). La multi-structuralité induit des relations complexes et multiples entre deux mêmes composants d’un document. Il est donc nécessaire d’utiliser un modèle de représentation riche afin de pouvoir classer les documents à structures multiples. Les travaux de recherche que nous avons menés au cours de cette thèse visent ainsi à étudier les modèles de représentation des documents multimédias à structures multiples et à développer des outils capables de traiter de grandes masses de données en prenant en compte les contraintes liées au partage de sous-structures (sous-graphes) par des structures hétérogènes. Une des problématiques principales est de savoir comparer deux documents multi-structurés, et en conséquence de pouvoir comparer des structures de documents afin d’évaluer leur similarité. Nous nous sommes intéressés à la représentation des structures documentaires à l’aide des graphes. Comparer structurellement deux documents revient donc à comparer les graphes qui les représentent. Les méthodes classiques de comparaison de documents sont basées sur les similarités dites de « surface » : un modèle de similarité basé sur les propriétés descriptives des objets sans tenir compte des relations entre ces propriétés. Ces méthodes ne tiennent pas compte de l’information implicite qui est véhiculée par la structure documentaire. Cependant, les mêmes composants structurels peuvent ne pas avoir le même rôle, ni la même importance dans deux documents différents. Nous pensons que les informations apportées parles relations structurelles présentent un intérêt incontournable dans un processus de comparaison. Nous montrons, par conséquent, que les mesures standards existantes ne peuvent pas répondre efficacement à notre problématique. Pour évaluer la similarité entre deux graphes, nous proposons une nouvelle mesure de similarité structurelle basée sur l’isomorphisme de (sous) graphes. En théorie des graphes, l’isomorphisme de sous-graphes induits permet de démontrer qu’un graphe est inclus dans un autre, alors que l’isomorphisme de sous-graphes partiels permet de déterminer l’intersection entre deux graphes. Cependant, la recherche d’isomorphisme de sous-graphes est un problème bien connu pour être combinatoire. Ce problème combinatoire rend la plupart des approches limitées à des graphes de petite taille.

The volume of multimedia documents available today, which is increasing, is an important source of information. However, all this information is useless if it is not used efficiently. Managing and exploiting such sources needs to have automated tools available to facilitate access to granules (fine information) documentary, regardless of the underlying heterogeneity of these documents in terms of type, size, format, content, structure, etc.. Automatic classification is a solution that allows organizing and structuring a large collection of documents to reduce the search space and consequently improve the performance of the access to information. Approaches that have addressed the documentary classification are distinguished by the model used to represent the documents and the approach used to classify documents. Concerning multimedia, the problem of classification arises from the complexity of their representation. Indeed, a multimedia document is composed of several objects of various kinds: image, text, sound, etc... It is multi-structured gasoline from the composition of several sub-documents and each sub-document has one or more structures. These structures can be of the same type or of different types (physical structure, logical, temporal, etc.). The multi-structuralism induces multiple and complex relationships between the same two components of a document. It is therefore necessary to use a rich representation model to organize the documents to multiple structures. The works that we conducted in this thesis aims to study model representation of multi-structured multimedia documents and to develop tools capable of processing large amounts of data taking into account the constraints of sharing substructures (sub-graphs) by heterogeneous structures. One of the main issues is how to compare two multi-structured documents, and therefore to compare the structures of materials to assess their similarity. We are interested in the representation of document structures using graphs. Comparing structurally two documents is therefore comparing the graphs that represent them.Traditional methods of document comparison are based on the similarities called "surface": a similarity model based on descriptive properties of objects without considering the relationships between these properties. These methods do not consider implicit information that is conveyed by the document structure. However, the same structural components may not have the same role or the same size in two different documents. We believe that the information provided by the structural relationships of interest inevitable in a process of comparison. We maintain, therefore, that the existing standard measures cannot efficiently address our problem.To evaluate the similarity between two graphs, we propose a new similarity measure based on structural isomorphism of (sub) graphs. In graph theory, the isomorphism of induced sub-graphs can show that a graph is included in another, while the isomorphism of partial sub-graphs is to determine the intersection of two graphs. However, the search for sub-graph isomorphism problem is well known to be combinatorial. Combinatorial problem that makes most approaches limited to small graphs. To reduce the cost combinatory, we propose to consider a graph as a set of paths. Comparing the two graphs is therefore comparing the paths that compose them, using a structural alignment model. The proposed measure reflects the structure of graphs compared in the sense that it takes into account both the position of the nodes, the order of sibling nodes and links between those nodes.