Mémoire (M.Ed.)--Université du Québec à Chicoutimi, 1989. / Document électronique également accessible en format PDF. CaQCU

Cette thèse s'inscrit dans le domaine de la recherche d'images par le contenu et plus spécifiquement dans celui de l'analyse de documents. Nous abordons le problème complexe de la localisation de symboles dans les documents où les symboles ne sont pas isolés de leur contexte. Bien qu'il existe beaucoup de travaux visant à la définition de bons descripteurs pour la représentation d'un symbole, ces derniers ne peuvent généralement pas être utilisés directement pour localiser des symboles dans les documents car on se heurte au paradoxe suivant : pour reconnaître les symboles il faudrait au préalable segmenter le document et réciproquement pour bien segmenter il faudrait au préalable reconnaître le contenu du document. Dans ce contexte, nous présentons nos contributions pour la localisation de symboles dans les documents graphiques où le problème de la localisation est abordé d'un point de vue différent de la plupart des méthodes existantes dans la littérature. Dans le contexte de l'analyse de documents graphiques, pour le problème de la localisation de symboles, presque toutes les études se focalisent sur l'aspect structurel du document, ce qui nécessite de résoudre plusieurs autres problèmes difficiles qui se situent soit en amont de la chaîne de traitements telle la vectorisation soit en aval telle la détection d'isomorphisme de (sous-) graphes. Cette thèse tente de voir ce problème de localisation sous l'aspect pixelaires qui est très rarement abordé dans les travaux précédents. Ainsi, dans nos travaux, nous avons abordé deux points essentiels pour résoudre ce problème. Le premier concerne le choix d'une représentation des informations des images de documents et le second est lié au processus de localisation de ces symboles. Afin de d´ecrire les symboles, nous proposons un descripteur de formes qui s'adapte bien aux symboles graphiques et qui peut être étendu pour d´ecrire le contenu des documents entiers ayant des symboles non-segmentés. Ce descripteur est basé sur le contexte de formes et prend en compte des informations associées aux seuls points d'intérêt associés à une forme. Le descripteur proposé assure l'invariance à la rotation et au changement d'échelle. Il est également tolérant à la déformation et à l'occultation partielle de l'objet. La localisation de symboles dans les documents graphiques s'appuie sur les techniques de traitement des documents textuels grâce à la notion de mots visuels. Un vocabulaire visuel est construit à partir d'un classifieur non-supervisé sur la base d'informations issues du descripteur de formes proposé et étendu aux documents entiers. Les documents graphiques sont ainsi “textualisés” grâce au vocabulaire visuel avec une technique d'appariements multiples. Lors de la localisation, les régions candidates sont identifiées dans les documents en fonction de l'appariement local entre la requête et les documents. La détermination des régions, parmi les régions candidates, contenant les occurrences du symbole requête est opérée à l'aide d'un système de vote adaptant le modèle vectoriel usuellement utilisé en recherche d'informations. Bien que la méthode ne soit pas encore validée sur les documents réels, les expérimentations sur des documents synthétiques et la comparaison avec une autre méthode montrent la performance de la méthode proposée en termes de précision, rappel.

Malgré la longue et riche histoire des bandes dessinées, leur définition continue de stimuler le débat parmi les experts. Ces derniers ne parviennent toujours pas à s’entendre sur la composition d’une bande dessinée, certains choisissant de mettre l’emphase sur l’usage de phylactères ou de lignes de mouvement, tandis que d’autres insistent plutôt sur la présence d’éléments à la fois graphiques et narratifs. Une définition impeccable est peut-être improbable, mais un problème mérite toutefois d’être adressé: il s’agit bien sûr de la constante exclusion des romans graphiques sans texte. Cette catégorie d’œuvres est parfois mentionnée, mais se révèle plus souvent ignorée par les experts. En effet les définitions courantes persistent à représenter les bandes dessinées comme un indéniable mélange de texte et d’images. Ce mémoire cherche donc à démontrer la nécessité de définitions plus inclusives, afin d’incorporer les romans graphiques sans texte. D’abord, en explorant l’histoire du médium et le rôle du texte dans la création et la lecture des romans graphiques, nous réfuterons les idées préconçues qui ont apporté à l’élément textuel de la bande dessinée une allure de nécessité. Puis, à travers l’analyse des romans graphiques sans texte The Arrival de Shaun Tan et The System de Peter Kuper, nous rendrons évidente la nature facultative du texte dans le processus de création d’une histoire de bande dessinée. Finalement, avec le support d’exemples provenant des romans graphiques The System de Peter Kuper et Asterios Polyp de David Mazzucchelli, nous analyserons le rôle de l’image dans le développement de la complexité narrative d’une histoire de bande dessinée, afin de prouver qu’une image n’est pas intrinsèquement plus simpliste qu’un extrait de texte. Les romans graphiques sans texte méritent tout autant l’attention académique reçue par les bandes dessinées avec texte, et devraient ainsi être reconnus dans les définitions courantes du médium. / In spite of comics’ long and rich history, their definition remains today a significant source of contention in the field. Scholars cannot seem to agree on what constitutes comics, with some of them stressing the importance of conventions such as speech balloons or motion lines, and others focusingon the pictorial and narrative elements of the form. A perfect definition may be impossible, but one issue that needs tobe addressed is the current exclusion of wordless graphic novels. While occasionally acknowledged, these works remain mainly ignored, as most working definitions present comics as a combination of text and image. This thesis intends to show that there is a need for more inclusive definitions of the medium, in order to incorporate wordless graphic novels. By first exploring the wordless ancestry of the medium and the role of text in creating and reading graphic novels, this thesis refutes the foundationally baseless assumptions about the form that have made text so widely accepted as a defining element. Then, through an analysis of Shaun Tan’s The Arrival and Peter Kuper’s The System, both of which are wordless graphic novels, this thesis demonstrates the superfluous nature of text when it comes to narrative in this medium. Finally, through readings of Peter Kuper’s The System and David Mazzucchelli’s Asterios Polyp, the thesis considers the contribution of the image to the complexity of graphic novels with and without text, in order to prove that images are not more simplistic in nature than text. The case is thereby made that wordless novels are as worthy of academic attention as graphic novels with text, and deserve acknowledgement in definitions of the medium.

De nos jours, le développement des personnages de jeux est devenu une tâche dif- ficile en raison de la complexité toujours grandissante des jeux vidéos actuels. Pour diminuer la complexité liée au développement de ces personnages, certaines approches sont applicables et consistent à utiliser des techniques d'intelligence artificielle. Dans ce travail, nous proposons d'utiliser des diagrammes états-transitions pour activer un personnage de jeu vidéo. Nous étudions les moyens de construire des diagrammes états-transitions et plus spécifiquement comment les structurer à partir des séquences de jeux. Les performances des diagrammes construits sont évaluées et nous analysons les possibilités d'améliorer les rendements obtenus. Dans nos expérimentations, nous utilisons le jeu de poursuite dénommé Pacman. Pacman constitue un banc d'essai idéal car il présente un environnement dynamique et séquentiel et nécessite une prise de décision en temps réel. Dans ce travail nous tentons d'accomplir les tâches suivantes : Acquérir des séquences de jeux à travers l'utilisation de l'apprentissage par la démonstration. Structurer des diagrammes états-transitions à partir des séquences de jeux. Analyser la possibilité d'améliorer les performances des diagrammes états-transitions par l'utilisation des techniques de raisonnement à base de cas et des éléments de la théorie de l'information. / Nowadays, developing game characters has become a difficult task because of the increasing complexity of actual video games. To reduce the complexity of developing those characters, some approaches exist and consist of using artificial intelligence techniques. In this project, we propose using state machines to activate a video game character. We learn the means to build state machines and more specifically how to structure them from game sequences. The performance of those state machines is evaluated and we analyze the possibility of improving the results. In our experimentations, we use the pursuit game called Pacman. Pacman constitute an ideal testbed because it others a dynamic and sequential environment and it calls for real time decision making. In this work we are trying to accomplish the following tasks : Acquire game sequences through usage of learning from demonstration. Structure the state machines from game sequences. Analyze the possibility of improving the performances of the state machines by using case-based reasoning techniques and elements of information theory.

Les graphiques ont pris de plus en plus d'importance dans le matériel pédagogique, les manuels scolaires ou encore les programmes informatiques. Malgré la coexistence de différents types de graphiques ou de genres graphiques, jusqu'à maintenant, les recherches sur l'apprentissage ont seulement pris en compte la distinction entre le texte et l'image. Cette thèse vise à éclaircir ce qui, dans la recherche sur l'apprentissage, semble être une catégorie globale et indivisible : les représentations visuelles. Nous nous sommes concentrées sur ce que pensent des enseignants et des étudiants de Master concernant différents types de représentations visuelles et leurs fonctions présumées dans l'enseignement et l'apprentissage. A l'heure actuelle, la recherche sur les graphiques est principalement axée sur la compréhension des élèves. Il existe très peu de recherches sur la compréhension des graphiques par les enseignants. En outre, la dimension de la formation des enseignants aux graphiques est, elle aussi, relativement ignorée. La thèse se présente en deux parties : une recherche théorique suivie d'une recherche empirique. La première partie du travail examine la littérature relative aux représentations graphiques dans l'histoire, dans les programmes scolaires à travers le monde ainsi que leur utilisation dans l'enseignement et l'apprentissage. Elle expose également les classifications des différents types de graphiques. La seconde partie de la thèse prend appui sur trois enquêtes menées auprès d'enseignants en activité et d'étudiants de Master en formation. La première investigue la compréhension des graphiques d'enseignants en activité en France et au Pakistan. Les deux autres ont été conduites auprès de futurs enseignants, en utilisant la méthode du tri de carte, afin d'identifier leurs compétences relatives à la catégorisation des différents types de graphiques.En conclusion, il semble que les programmes de formation des enseignants manquent d'un enseignement à la compréhension graphique. Même en géographie, pourtant considérée comme la discipline des graphiques et de leur enseignement, nous constatons que les enseignants sont peu familiers avec de nombreux genres graphiques. Dans l'ensemble, les graphiques génériques (camemberts, histogrammes, cartes et tableaux, etc.) ont été facilement identifiés par les enseignants alors que la classification des graphiques hybrides s'est révélée plus difficile pour la plupart d'entre eux. / Visualizations have gained more importance in pedagogical material, in text books and in computer programs. Despite the co-existence of many different types of visualizations or graphical genres, learning research only has taken into account the distinction between text and pictures. This thesis aims at unpacking what, at least in learning research, seems to be one single holistic indivisible category of visualizations. We focused on teachers' and Masters students' thoughts on the existence of different types of visualizations and their presumed function in teaching and learning. Research on graphical representations is mainly focused on students' comprehension of graphical representations. However, there is very little research in extend of teachers' comprehension of graphical representations. In addition, the aspect of teacher training of graphical representations is also relatively ignored. There are two main parts in this thesis: theoretical and empirical. In theoretical part, we presented the literature on the existence of graphical representations in worldwide curricula. Remarkable works of cartographers who played important rule for the advancement of graphic representations in context of teaching and learning. And finally, classification of different genres of graphical representations was also exhibited. Empirical part on the other hand, based on three studies conducted with in-service teachers and Masters students' about their comprehension of graphical genres. First study was conducted with in-service teachers from France and Pakistan to investigate their basic understanding of graphical representations. Second and third study explores the Masters' students' categorization of graphical representations. In conclusion, it seems that the teacher training programs lack the training of graphic comprehension. Even in the domain of geography which is considered the major domain about graphics and graphic education, teachers were observed unfamiliar with many graphic genres. Overall, Generic graphical representations (i.e. line graph, pie charts, bar charts, maps and tables etc.) were identified more comfortably. However, classification of hybrid graphical representations (i.e. combination of map and bar graph or other hybrid graphics) was slightly difficult for the participants.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse apporte des solutions pour exploiter efficacement les nouvelles architectures hautement parallèles, dans le contexte des simulations d'objets déformables en temps réel. Les premières contributions de ce document, se concentrent sur le calcul de la déformation des objets. Pour cela nous proposerons des solutions de parallélisations de solveurs linéaires, couplées à des techniques de preconditionnement asynchrone. Le second ensemble de contributions, repose sur le processeur graphique pour produire une nouvelle méthode de détection des collisions, basée sur le volume d'intersection entre les objets déformables.Enfin les derniers travaux apportent des solutions pour produire une réponse précise aux contacts, et compatible avec le temps réel. Nous aborderons notamment les problèmes liés à la découpe des organes, et à la prise en compte du couplage mécanique entre les contacts. Pour terminer, nous illustrerons nos contributions dans un ensemble d’applications médicales, qui tirent parti des contributions de ce document. / This thesis provides solutions to effectively exploit the new highly parallel architectures, in the context of simulations of deformable objects in real time. The first contributions of this paper focus on calculating the deformation of objects. For that purpose, we will propose solutions of parallelization of linear solvers, coupled with asynchronous preconditioning techniques. The second set of contributions relies on the graphics processor to produce a new collision detection method, based on intersection volumes between deformable objects. Then the last works provide solutions to produce an accurate response to contacts and is compatible with real time. We will discuss issues related to the organs cutting, and the recognition of the mechanical coupling between the contacts. Finally, we will illustrate our contributions in a range of medical applications which make the most of the contributions of this paper.

La présente thèse s'intéresse à modéliser la causalité dans le cadre de la théorie des fonctions de croyance. Dans un premier temps, nous avons analysé et révisé les fondements théoriques des différents modèles associationnels crédibilistes existants. Nous avons proposé une structure graphique qui sert de base pour le réseau causal crédibiliste. Dans ce dernier, l'incertitude au niveau des nœuds est donnée en termes de distributions de masses conditionnelles. Comme la notion d'intervention est d'une importance capitale pour une analyse causale efficiente, nous avons introduit la contrepartie de l'opérateur \do" pour la représentation des interventions dans les réseaux causaux crédibilistes. Le modèle proposé permet ainsi de calculer l'effet simultané des observations et des interventions. Il est admis que considérer l'intervention comme une action qui réussit toujours à mettre sa cible à une valeur précise en la rendant complètement indépendante de ses causes originales est une condition rarement réalisée dans les applications réelles. De ce fait, nous avons examiné le traitement des interventions dont l'occurrence et/ou les conséquences sont imparfaites. Dans la dernière partie de la thèse, nous avons proposé un modèle d'attribution de causalité permettant d'interpréter les relations d'influence qui existent entre les différents attributs du système à savoir la causalité, la facilitation ou encore la justification en présence de données observationnelles et interventionnelles. Motivé par le fait que les preneurs de décision ne sont pas uniquement intéressés par l'attribution de la causalité, ce modèle permet de définir différentes forces d'une cause. / This thesis focuses on the modeling of causality under the belief function framework. We have first analyzed and revised the theoretical foundations of existing associational belief models. Then, we have proposed a graphical structure that serves as a basis for the causal belief network. In this latter, uncertainty at the nodes is given in terms of conditional mass distributions. Since intervention is a crucial concept for an efficient causal analysis, we have introduced a counterpart of the do operator as a tool to represent interventions on causal belief networks. The proposed model allows computing the simultaneous effect of observations and interventions. It is assumed that considering an intervention as an action that always succeeds to force its target variable to have a precise value, by making it completely independent of its original causes, is a condition rarely achieved in real-world applications. Therefore, we have examined the treatment of interventions whose occurrence is imperfect and/or have imperfect consequences. In the last part of the thesis, we have proposed a model for causality ascription to interpret influential relationships between different attributes of the system namely causality, facilitation or justification in the presence observational and interventional data. Since decision makers are not only interested in ascribing causes, this model allows to define different strengths of a cause.

Cette thèse s'inscrit dans le cadre de la bioinformatique. Les outils mathématiques les plus utilisés dans ce travail relèvent de la théorie des graphes, des statistiques, de la théorie des ensembles et des mathématiques discrètes. Ces mathématiques ont permis de développer des modèles de systèmes biologiques ainsi que des algorithmes efficaces dans l'étude concrète de ces modèles. La nécessité d'analyses de jeux de données de très grande taille a rendu critique dans notre démarche cette notion d'efficacité des algorithmes. Il faut enfin remarquer que le champ biologique qui a servi de support à cette thèse nous a conduit à explorer un domaine particulier au sein de la théorie de la complexité, à savoir le développement et l'analyse des algorithmes d'énumération [etc...] / In the results presented in the present manuscripts, graph theory and combinatorial optimizationtecniques, have been used to model and solve biological problems. The manuscript is divided in twoparts, each one containing the mathematical and biological background of a given application and ouroriginal contributions to it.Part I groups a set of results designed for phylogenetics analysis, and in particular for reconstructingthe co-evolution of two groups of organisms (the so called co-phylogeny reconstruction problem).Although the addressed problem was treated in the available there was no method that solved suchproblem in a complete and efficient way. We thus developed and implemented a new one, calledEucalypt, with this purpose in mind. This not only provides a novel and usable software for cophylogenyreconstruction but also allows to investigate how the event-based model performs inpractice in terms of thenumber and quality of the solutions obtained. We compared our method to the available software. Bylooking at the results obtained, some interesting considerations about the advantages anddisadvantages of the commonly accepted mathematical model could be drawn. Finally, we introduceda new version of the problem where the host-switches are distance bounded: the k-bounded-All-MPRproblem. Eucalypt solves both problems in polynomial delay. These results have been accepted forpublication by the jounal Algorithms for Molecular Biology. The relative software is publicyavailable.Our studies show that the 'most parsimonious scenario' approach presents some limitationsthat cannot be ignored. To deal with these problems, we developed a second algorithm, called Coala,based on an approximate Bayesian computation approach for estimating the frequency of the events.The benefits of this method are twofold: it provides more confidence in the set of costs to be used in areconciliation, and it allows to estimate the frequency of the events in the cases where a reconciliationmethod cannot be applied. These results are currently under review by the jounal Systematic Biology.The relative software is publicy available.In Part 2 another set of studies is presented. Our original model for the contig scaffolding problem,and our algorithm MeDuSa, are presented and tested. Unlike traditional software, it does not rely eitheron paired-end information of sequencing reads or on a phylogenetic distance of the microorganismsused in the analysis. This drastically increases the usability of our software and, at the same time,reduces the computational time required for genome scaffolding. We show that the algorithmimplemented in MeDuSa, in most cases, is capable of producing less and longer scaffolds incomparison to commonly used scaffolders, while maintaining high accuracy and correctness of thepredicted joins. These results are currently under revision by the journal Bioinformatics.Finally, during the development of this method we encountered some pure theoretical open problemsand we decided to dedicate part of our job to their analysis. The last chapter is then dedicated to a setof problems, all related to the Implicit Hitting set enumeration problem. After some formal definitions,an original NP-completeness result is presented and the future directions of our work are described

Thèse de doctorat : Informatique : Nancy 1 : 2008. / Titre provenant de l'écran-titre.