Thèse (M.Sc.)--Université Laval, 2007. / Titre de l'écran-titre (visionné le 5 mai 2008). Bibliogr.

Un document multimédia marie les technologies de l'écrit, de l'image et du son. Actuellement, les documents multimédia doivent pouvoir être exécutés sur de nombreuses plates-formes (téléphones portables, PDA, ordinateurs de bureau, lecteurs de salon...). Cette diversification des utilisations et des supports nécessite l'adaptation des documents à leur contexte d'exécution, parfois imprévisible au moment de la conception du document.<br /><br />Pour s'affranchir des langages ou formats de description multimédia, nous abstrayons les documents en une structure exprimant l'ensemble des relations entre objets du document. Les relations entre objets sont d'ordre temporel, spatial, hypermédia voire inter-dimensionnel, et peuvent être de nature qualitative. Cette structure capture la sémantique des documents car elle est capable de couvrir chacune de ses exécutions potentielles. Dans ce contexte, adapter va consister à calculer un ensemble d'exécutions le plus proche possible de ces exécutions potentielles qui satisfont les contraintes d'adaptation imposées par une plate-forme cible. À cet effet, les relations de la structure abstraite sont modifiées de sorte de satisfaire ces contraintes d'adaptation. Nous montrons, pour chaque dimension du document, comment réaliser ceci de manière réaliste.<br /><br />Afin de montrer l'applicabilité d'une telle approche, nous la développons dans un cadre adapté au standard SMIL pour lequel nous déclinons les adaptations spatiales, temporelles, spatio-temporelles et hypermédia. Nous sommes amenés à développer des techniques spécifiques pour les représentations spatiales et temporelles efficaces. Nous explorons aussi des approches impliquant la suppression d'objets.

L'objectif des travaux présentés dans cette thèse est de poser les fondements d'une formalisation qui permettrait, d'une part la description d'une représentation numérique de terrain dans un langage intelligible à destination d'observateurs localisés au sol et, d'autre part, de faciliter les échanges entre des communautés scientifiques disposant de corpus sémantiques différents.<br />Nous cherchons à décrire une silhouette - i.e., une coupe de terrain ou la séparation terre/ciel à l'horizon - selon la perception que peut en avoir un observateur. Nous introduisons un modèle, fondé sur une approche qualitative, qui consiste à décrire une silhouette par une séquence de symboles signifiants. L'utilisateur ayant la possibilité de définir ses propres catégories, le modèle possède la capacité de s'adapter à différents contextes.<br />L'originalité de notre modèle repose dans la méthode de détection des formes significatives. Nous nous ecartons volontairement des méthodes numériques généralement utilisées dans les systèmes de détection ou de reconnaissance de forme. Nous considérons que la perception d'une forme particulière de relief est contingente de la perception de saillances, définies ici comme des points qualitativement remarquables. La description d'une silhouette inclut les relations topologiques qui relient les formes de relief détectées. Afin de tenir compte de l'imprécision des frontières des formes de relief, nous proposons une extension de la méthode 9-intersection. Les relations méréologiques, quant à elles, nous sont utiles pour dériver des représentations à différents niveaux d'abstraction.<br />Nous avons implanté le modèle en Java. Le prototype réealisé permet de définir des catégories, d'analyser des silhouettes, de déterminer les relations topologiques qui lient les formes détectées et d'obtenir une description à différents niveaux d'abstraction.<br />Cette thèse a bénéficié du soutien financier de la Région Bretagne.

La recherche développée dans cette thèse introduit une approche qualitative pour représenter et raisonner à partir d'entités spatiales dans un espace géographique à deux dimensions. Les patrons de mouvements entre entités dynamiques sont catégorisés à partir d'un modèle qualitatif de relations topologiques entre une ligne orientée et une région, et de relations d'orientation entre deux lignes orientées, respectivement. Les mouvements qualitatifs sont dérivés à partir de relations spatio-temporelles qui caractérisent des entités dynamiques conceptualisées comme des points ou des régions dans un espace à deux dimensions. Cette architecture de raisonnement permet de dériver des configurations de mouvements basiques dérivées à partir d'entités statiques et dynamiques. L'approche est complétée par une qualification de ces configurations à partir d'expressions du langage naturel. Les compositions de mouvements sont étudiées tout comme les transitions possibles dans des cas de données incomplètes. Les tables de compositions sont également explorées et permettent d'étendre les possibilités de raisonnement. Le modèle est expérimenté dans le contexte de l'analyse de trajectoires aériennes et maritimes. / The research developed in this thesis introduces a qualitative approach for representing and reasoning on moving entities in a two-dimensional geographical space. Movement patterns of moving entities are categorized based on a series of qualitative spatial models of topological relations between a directed line and a region, and orientation relations between two directed lines, respectively. Qualitative movements are derived from the spatio-temporal relations that characterize moving entities conceptualized as either points or regions in a two-dimensional space. Such a spatio-temporal framework supports the derivation of the basic movement configurations inferred from moving and static entities. The approach is complemented by a tentative qualification of the possible natural language expressions of the primitive movements identified. Complex movements can be represented by a composition of these primitive movements. The notion of conceptual transition that favors the exploration of possible trajectories in the case of incomplete knowledge configurations is introduced and explored.Composition tables are also studied and provide additional reasoning capabilities. The whole approach is applied to the analysis of flight patterns and maritime trajectories.

La modélisation et la résolution de problèmes sous contraintes constituent un domaine majeur enIA. Par la nature diverse des contraintes, différents formalismes de représentation ont été proposés pour les exprimer de manière simple et compacte tout en garantissant une efficacité des outils de résolutions associés. Les formules propositionnelles, les réseaux de contraintes discrets (RCD) et qualitatives (RCQ) sont des cadres de modélisation répondant à ces critères. Pour les informations temporelles ou spatiales, les RCQ constituent un modèle de choix avec de nombreuses applications comme l’ordonnancement de tâches, la planification temporelle ou spatiale, les systèmes d’informations géographiques. Nos contributions visent à étudier les liens des RCQ vers les RCD et les formules propositionnelles, afin d’adapter les outils issus des divers domaines et de proposer de nouvelles approches. Tout d’abord, nous nous concentrons sur l’aspect structurel des RCQ, en adaptant la méthode de la composition faible dans les différents cadres. Nous exploitons ensuite les propriétés des classes traitables de certains formalismes qualitatifs, afin de définir une transformation vers la logique propositionnelle. En exploitant la transformation vers les RCD, nous proposons une méthode incomplète facilitant la preuve de l’incohérence des RCQ par la relaxation de la propriété de composition faible, puis nous complétons l’approche en exploitant les classes traitables. Enfin, ces études nous conduisent à proposer une nouvelle forme de substituabilité locale, dont les détections statique et dynamique permettent d’obtenir une amélioration algorithmique dans le cadre des RCD. / Modelling and solving constraints problems is a major domain in Artificial Intelligence. By the various natures of the constraints, different formalisms were proposed to express them in a simple andcompact way while guaranteeing the effectiveness of the associated solution tools. Propositional formulae, discrete constraint networks (DCNs), and qualitative constraint networks (QCNs) are the well known frameworks that guaranty these requirements. For temporal or space information, QCNs constitute a model of choice with many real world applications such as scheduling, temporal or spatial planning and geographic information systems. Our contributions aim at studying the links between QCNs, DCNs and propositional formulas, in order to adapt the tools developed in these fields and to propose new approaches. First of all, we focus on the structural aspects of QCNs, by transforming weak composition within the various frameworks. In order to define a transformation towards propositional logic we then exploit the properties of tractable classes of some qualitative formalism. Exploiting the transformation towards DCNs, we propose an incomplete method simplifying the proof of the inconsistency for QCNs by relaxing the weak composition property. Then, we propose a complete approach thanks to tractable classes. Finally, these studies lead us to propose a new form of local substitutability, whose static and dynamic detections significantly improve search algorithms for DCNs.

Le but de ce mémoire était d’effectuer, dans un contexte géospatial, une comparai- son d’une approche de raisonnement qualitatif basée sur le PROLOG avec une autre approche reposant sur l’ASP. La principale question que nous posons est la suivante : Le moteur de raisonnement Smodels rendant possible la mise en oeuvre du raisonnement non monotone poussé et faisant intervenir le concept de modèle stable peut-il nous permettre de résoudre des problèmes de vérification de cohérence ontologique et des problèmes de révision dans le contexte de la géomatique ? Pour y répondre, nous avons procédé à une série de tests sur un échantillon de la Base nationale de données topographiques (BNDT). À la lumière des résultats obtenus, cette approche se montre très efficace et contribue à l’amélioration de la cohérence de l’information géospatiale et du raisonnement spatial réalisé à partir de cette dernière. / The objective of this thesis is to make a comparison between a qualitative reasoning approach based on PROLOG with another approach based on ASP. Our principal research question was the following : Can the Smodels reasoning engine, allowing for advanced non monotonic reasoning and introducing the stable model concept, allow us to solve ontological consistency checking problems as well as revision problems in a geomatic context ? To answer this question, we carried out a series of tests on a cross-section from the National Topographical Database (NTDB). In the light of the results obtained, this approach has proven very effective and contributes to the amelioration of geospatial information consistency and to the resultant improvement in spatial reasoning.

La plupart des systèmes experts actuels reposent sur les connaissances de surface (le savoir-faire) d'un expert du domaine d'application. Plus récemment, une autre approche s'est développée. Elle vise a exploiter les connaissances profondes (théoriques) acquises dans le domaine d'application. La thèse étudie cette dernière approche dans le cadre du projet pic (poste de travail intelligent pour le comptable). Les aspects méthodologiques sont développés dans la première partie. Une nouvelle classe d'applications des systèmes experts est proposée: l'interprétation comparative. Elle a pour but de mettre en évidence et expliquer la cause des différences entre deux états d'un système. Une methode générale permettant d'aborder ce probleme est présentée, ainsi que des techniques la mettant en œuvre sur des modèles qualitatifs et numériques. Les contributions au projet pic sont développées dans la seconde partie. Un générateur de systèmes experts d'interprétation comparative est d'abord présenté. Il a servi a la réalisation de deux systèmes: le premier pour l'analyse de la performance d'une entreprise par la methode des surplus, le second pour le diagnostic financier d'entreprise. Un système expert pour la déduction des écritures comptables utilisant également l'approche profonde est ensuite présenté. A la lumière de ces deux dernières applications déjà abordées par les systèmes experts utilisant des connaissances de surface, les deux approches de conception de systèmes experts sont comparées

Une caractéristique des systèmes dynamiques complexes, qu'ils soient physiques ou naturels, est la présence de processus évoluant à différentes échelles de temps (dynamiques multiples) et de façon fortement non-linéaire. Nous nous plaçons dans le cas où l'évolution de chaque processus étudié est une série de mesures, ou bien est issue de la simulation de modèles numériques. Pour concevoir ou améliorer ces modèles en se basant sur l'échelle qui l'intéresse, l'utilisateur doit d'abord être capable de représenter l'évolution de chaque processus à plusieurs échelles, déterminées objectivement selon l'évolution elle-même. Ensuite, le choix d'une ou de plusieurs représentations doit être guidé par l'interprétation des caractéristiques dynamiques à chaque échelle de temps. Nous définissons une notion de granularité temporelle, exprimant le niveau de détail de la représentation. Ayant affaire à des processus biologiques dont la forme de l'évolution est plus informative pour l'utilisateur que les valeurs numériques précises, une représentation qualitative/quantitative est élaborée : une segmentation de l'évolution initiale en épisodes triangulaires (exprimant différentes formes de comportements locaux), puis l'abstraction successive de ces épisodes triangulaires en épisodes trapézoïdaux, conduisent à l'obtention de toutes les représentations possibles de l'évolution, et de toutes les échelles de temps associées. Le développement d'outils graphiques, symboliques et statistiques permet d'identifier et d'interpréter automatiquement les principales caractéristiques dynamiques du processus à n'importe quelle échelle de temps : équilibre, stabilité, périodicité, récurrence, comportements majoritaires, etc. Ces caractéristiques permettent de conseiller un choix d'échelles de temps et, par suite, de fréquences d'échantillonnage pertinentes. Une fonctionnalité suppl émentaire vise à identifier et à dissocier localement les composantes fréquentielles de l'évolution initiale. Des exemples d'interprétation sont donnés pour deux modèles biologiques. Les analyses sont confrontées à la connaissance experte d'un agronome pour la validation de la méthode. Ce travail a conduit à la conception du logiciel PARADISE (Process AbstRaction AnD Interpretation SystEm)

Cette thèse aborde l'aide du pronostic basée sur l'image et les ontologies médicales, en utilisant la représentation des connaissances et le raisonnement pour les très grandes images microscopiques. Une application médicale particulière dans laquelle une assistance de type pronostic est nécessaire est la graduation du cancer du sein. Même si cela est considéré comme un outil d'évaluation essentiel dans la pratique de pathologie moderne, les principaux problèmes posés par la procédure manuelle de pronostic sont : la nécessité des connaissances, attention et temps. D'autre part, le manque de représentation sémantique formelle standardisée pour aider l'indexation et la classification de la terminologie, ainsi que l'utilisation d'un mécanisme d'inférence pour assister la graduation représentent des problématiques clé du domaine. Dans ce sens, cette étude propose une représentation formelle qualitative pour la graduation du cancer du sein ainsi qu'une ontologie d'application Breast Cancer Grading Ontology (BCGO) pour décrire les connaissances d'une manière cohérente. Une autre question que nous adressons en proposant l'ontologie est le fossé sémantique entre les concepts sémantiques de haut niveau et les caractéristiques de l'image de bas niveau. En plus, nous proposons un soutien de théorie spatiale pour la représentation des relations spatiales entre les concepts spécifiques à la graduation du cancer du sein. L'ontologie BCGO est intégré dans une plateforme microscopique cognitif virtuelle MICO pour l'exploration visuelle, l'indexation et l'extraction sémantique de l'image microscopique.

Parmi les différentes formes de raisonnement étudiées dans le contexte de l'intelligence artificielle, le raisonnement qualitatif permet d'inférer de nouvelles connaissances dans le contexte d'informations imprécises, incomplètes et dépourvues de valeurs numériques. Il permet par exemple de déduire de nouvelles informations à partir d'un ensemble d'informations spatiales telles que « la France est frontalière de l'Allemagne », « la Suisse est à l'est de la France », « l'Italie est en Europe » et « le Luxembourg est proche de la France ». Il peut également être utilisé pour résoudre des abstractions de problèmes quantitatifs difficiles à résoudre, afin par exemple d'accélérer la résolution de ces problèmes.De nombreux formalismes de raisonnement qualitatif ont été proposés dans la littérature. Ils ne se focalisent cependant que sur un seul aspect du monde, alors que la majorité des applications requièrent la prise en compte d'informations hétérogènes. Afin de répondre à ces besoins, plusieurs combinaisons et extensions de formalismes qualitatifs, comme le raisonnement spatio-temporel et le raisonnement multi-échelle, ont récemment été proposées dans la littérature. Le raisonnement spatio-temporel permet de raisonner dans le contexte d'informations spatiales et temporelles interdépendantes. Le raisonnement multi-échelle permet de raisonner avec des informations de précisions différentes, et en particulier de lever des incohérences apparentes.Dans cette thèse, nous nous intéressons au raisonnement multi-échelle, au raisonnement spatio-temporel et aux combinaisons de formalismes qualitatifs.Nous proposons d'étendre le raisonnement qualitatif temporel multi-échelle pour prendre en compte le fait que les intervalles de temps peuvent être perçus comme des instants à certaines échelles de précision, de formaliser intégralement ce raisonnement et d'étudier la décision de la cohérence dans ce contexte ainsi que sa complexité. Nous montrons en particulier que ce formalisme permet de décider la cohérence et que le problème de décision de la cohérence est NP-complet, même dans le cas le plus simple.En outre, nous proposons un cadre général permettant de raisonner sur les séquences temporelles d'informations qualitatives, une forme de description spatio-temporelle. Ce cadre permet notamment de raisonner dans le contexte d'évolutions complexes. Par exemple, les entités considérées peuvent avoir des caractéristiques préservées au cours du temps, évoluer de manière dépendante les unes par rapport aux autres, tout en ayant un comportement potentiellement irréversible et différent selon leur nature. De plus, dans ce cadre, le raisonnement est plus performant computationnellement que les approches de l'état de l'art. Nous étudions en particulier la décision de la cohérence dans le contexte spécifique de régions mobiles de taille constante, et montrons que ce cadre permet effectivement de décider la cohérence.De surcroît, nous proposons un cadre formel unifiant plusieurs formes d'extensions et de combinaisons de formalismes qualitatifs, incluant le raisonnement multi-échelle et les séquences temporelles. Ce cadre permet de raisonner dans le contexte de chacune de ces combinaisons et extensions, mais également d'étudier de manière unifiée la décision de la cohérence et sa complexité. Nous établissons en particulier deux théorèmes complémentaires garantissant que la décision de la cohérence est polynomiale, et nous les utilisons pour prouver que plusieurs fragments de séquences temporelles sont traitables.Nous généralisons également la définition principale de formalisme qualitatif afin d'inclure des formalismes qualitatifs exclus des définitions de la littérature, importants dans le cadre des combinaisons. / In this thesis, we are interested in qualitative multi-scale reasoning, qualitative spatio-temporal reasoning and combinations of qualitative formalisms.We propose to extend the multiscale temporal reasoning to take into account the fact that time intervals can be perceived as instants at certain scales of precision, to fully formalize this reasoning and to study its consistency problem. We show in particular that this formalism decides consistency and that the consistency problem is NP-complete, even in the simplest case.In addition, we propose a general framework for reasoning on temporal sequences of qualitative information, a form of spatio-temporal description. This framework allows for reasoning in the context of complex evolutions. For example, the considered entities may have characteristics preserved over time, evolve in a dependent manner with respect to each other, while having a potentially irreversible and different behavior depending on their nature. Moreover, in this context, reasoning is computationally more efficient than state-of-the-art approaches. In particular, we study the consistency problem in the specific context of constant-size moving regions, and show that this framework actually decides consistency.Furthermore, we propose a formal framework unifying several forms of extensions and combinations of qualitative formalisms, including multi-scale reasoning and temporal sequences. This framework allows one to reason in the context of each of these combinations and extensions, but also to study in a unified way the consistency problem. In particular, we establish two complementary theorems guaranteeing that the consistency problem is polynomial, and we use them to prove that several fragments of temporal sequences are tractable.