Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.

Les travaux présentés dans cette thèse traitent de l'utilisation de la Réalité Virtuelle (RV) et plus particulièrement du retour d'effort pour améliorer l'interaction dans les applications de Conception Assistée par Ordinateur (CAO). Dans ce document, nous décrivons le rôle actuel du Product Lifecycle Management (PLM) dans l'industrie, et plus spécifiquement la place tenue par l'outil CAO. Celui-ci offre de nombreuses fonctionnalités pour l'édition d'une maquette en trois dimensions, mais, actuellement, ne bénéficie pas pleinement des méthodes d'interactions les plus récentes. Notre positionnement de recherche concerne l'utilisation des dispositifs de visualisation ainsi que les nouvelles méthodes d'interaction offertes par la RV, pour rendre l'édition de forme plus intuitive. Toutefois, de nombreuses applications industrielles du PLM, telles que l'assemblage ou l'ergonomie, utilisent déjà des solutions de RV pour augmenter l'interaction avec le produit. Afin de bien appréhender les solutions haptiques que nous proposons, un rappel des principaux concepts de la CAO est effectué, en particulier relatif à ses modèles de données (B-Rep, graphe d'historique, persistent naming). On décrit également les informations perceptibles autour de trois principales catégories : référents, informations géométriques et guides, puis les retours tactiles et d'efforts envisagés pour traduire les différents types d'informations que l'on peut rencontrer. Le travail du concepteur s'articulant autour de deux catégories de tâches : la sélection et la modification de la maquette CAO, nous avons structuré nos travaux de recherche en haptique autour de ces deux grandes classes. De fait, nous abordons ensuite les problématiques de sélection dans une maquette 3d, sélection assistée par des retours haptiques adaptés, et ce en particulier pour permettre une perception fine des composants topologiques. Dans un second temps, nous présentons deux tâches représentatives des activités de modification en CAO : l'édition de courbes et surfaces et l'extrusion. Ces deux fonctionnalités permettent de montrer l'apport de l'haptique pour la manipulation de paramètres sur deux types d'édition CAO très différents. Nous nous intéressons à l'impact de différents facteurs comme le contexte de réalisation de la tâche, la manipulation simultanée des paramètres, la cohabitation de multiples retours haptiques, ou la prise en main, par les tilisateurs, des solutions haptiques. L'analyse des expérimentations relatées dans cette thèse montre des résultats mitigés sur l'apport de l'haptique. Si ce canal sensorimoteur est généralement plebiscité, il convient néanmoins de faire attention au paramétrage des retours d'effort et à la mise en relation des différentes méthodes haptiques, au risque de gener le travail de l'utilisateur du système CAO. Au demeurant, une fois cet écueil évité, les perspectives de l'intégration de l'interaction haptique pour l'aide 'a l'édition CAO semblent prometteuses. Nous concluons cette recherche en esquissant la méthodologie d'intégration RV-CAO qu'il conviendrait de suivre pour mener à bien une évaluation complète de nos solutions avec des utilisateurs CAO experts.

Les réseaux spatiaux sont des réseaux dans lesquels les sommets occupent une position dans l'espace Euclidien. Les interactions dans ces réseaux sont déterminées par cette géometrie sous-jacente des sommets. Les réseaux de communications offrent un vaste champ d'application et une source de nouveaux modèles autour de ce thème. La thèse aborde trois sujets dans des domaines differents. Le premier concerne l'étude de certains arbres couvrant géométriques de processus ponctuels de Poisson. Ces travaux portent notamment sur le phenomene "petit monde", les arbres couvrants radiaux et l'arbre couvrant minimal. Un autre sujet de recherche porte sur la stabilité stochastique de réseaux de files d'attente pour lesquelles les files ont des interactions spatiales. La dernière partie de la thèse aborde des thèmes reliés à la géometrie stochastique: une étude du modèle de feuilles mortes et un travail sur la sensibilité de fonctionnelles de processus ponctuels de Poisson.

En dépit des progrès réalisés en vision par ordinateur et en photogrammétrie, la reconstruction tridimensionnelle de scènes à partir de photographies reste un problème extraordinairement complexe et loin d'être résolu. Dans cette thèse, nous nous intéressons au domaine plus restreint de la reconstruction automatique de bâtiments à partir d'images aériennes en multi-recouvrement. En décalage par rapport aux méthodes à base de modèles prédéfinis, notre approche utilise une modélisation très générique des bâtiments comme polyèdres sans surplomb. Pour pallier le manque de robustesse inhérent à la plupart des approches génériques, des contraintes a priori sont introduites dans la sélection de la meilleure représentation favorisant ainsi, sans les imposer, des choix correspondant à des situations récurrentes dans un environnement urbain: parallélisme, horizontalité, orthogonalité, symétrie verticale de certaines facettes. Par ce raisonnement, le système concilie à la fois les problématiques de généricité et de généralisation. La stratégie générale se compose de quatre étapes majeures. La première consiste à extraire des images trois types de primitives tridimensionnelles qui serviront à construire les modèles de bâtiments puis à sélectionner la meilleure représentation: segments 3D, facettes planes, discontinuités altimétriques. Dans un deuxième temps, l'algorithme extrait, à partir de l'arrangement de plans déduit des primitives planes, toutes les hypothèses de bâtiments modélisés comme surfaces polyédriques continues et sans surplomb. Il est prouvé, à cet effet, que cette procédure se ramène à la recherche exhaustive des cliques maximales d'un graphe adéquat. Dans l'ensemble de toutes ces hypothèses, la sélection du modèle final se fait, dans un troisième temps, par le biais d'une formulation bayésienne qui prend en compte différents types d'observation. La complexité du modèle de bâtiment et les contraintes a priori sur les primitives telles qu'orthogonalité, parallélisme, symétrie, horizontalité sont naturellement introduites dans cette formulation pour concilier adéquation aux données et simplicité de formes. Enfin, les contraintes détectées sur les primitives sont effectivement introduites dans la reconstruction. L'algorithme utilise alors une paramétrisation implicite du bâtiment qui assure l'application des contraintes sur le modèle final. La méthodologie de recherche de l'ensemble des formes admissibles par cliques maximales constitue, avec l'intégration de contraintes dans le processus de choix de la représentation et de recalage du modèle, les contributions majeures du système présenté. Des résultats et une évaluation sur images aériennes prouvent la validité de cette approche qui permet de traiter des bâtiments aux formes arbitrairement complexes et de pallier, le cas échéant, les défauts de focalisation. Malgré cette généricité, le système se révèle tolérant aux erreurs des détecteurs de primitives et présente des caractéristiques intéressantes pour la modélisation de scènes péri-urbaines.

La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Engendrer en temps-réel des déformations visuellement réalistes d'objets 3D, comme par exemple le corps et les vêtements de personnages, est un point crucial en animation, que ce pour des applications au jeu vidéo ou à la production cinématographique. Les méthodes de déformations géométriques actuelles rapides telles que le "skinning" ou l'animation physique à basse résolution ne capturent cependant pas certains comportements naturels essentiels. En particulier les déformations à volume constant du corps, le gonflement des muscles pour un personnage, ou la génération de plis sur ses vêtements dus au fait que leurs surfaces doivent rester développable. Cette thèse présente une série de méthodes rendant les modèles géométriques "actifs", c'est à dire capables de maintenir un certain nombre de contraintes intrinsèques de la surface portant sur le volume englobé ou sur le caractère développable de celle-ci. Nous étudions trois exemples: - l'ajout de contraintes locales de volumes lors de l'animation d'une créature virtuelle par skinning. - l'ajout de plis de vêtements modélisant une surface quasi-inextensible à partir d'une animation à basse résolution donnée en entrée. - la génération d'une surface de type papier froissé, basée sur la préservation de l'isométrie vis-à-vis d'un patron planaire. Dans tous ces modèles, notre approche est procédurale. Elle se base sur la déformation progressive et, potentiellement, le raffinement dynamique de la géométrie juste avant l'étape de rendu. / Generating visually realistic deformation of 3D objects in real-time for character body or garment is essential for the animation field, both for video games applications and movie production. Current fast deformation methods such as "skinning", or low resolution physically based simulations fail to capture some important natural behaviors. For instance constant volume deformation of a body, muscle bulging of a character, or wrinkling its garment which must be modeled by a developable surface. This thesis presents several methods making a geometrical models "active", that is to say able to maintain a certain number of intrinsic constraints of the surface linked to its bounded volume, or its developability. We develop three case studies - The addition of local volume constraints during skinning animation of a virtual creature. - The addition of wrinkles on garments to model stretch minimizing surface starting from a general low resolution animation provided as input. - The generation of folded paper looking surface based on length preservation with respect to its planar pattern. For every cases, we rely on a procedural approach based on progressive deformation, and eventually, on-the-fly refinement of the geometry just before the rendering stage.

L'étude de la maturation cérébrale a pour objectif une meilleure compréhension du développement du cerveau durant la grossesse et la mise en évidence des liens entre la modification des structures cérébrales et le développement cognitif. Cette étude est rendue particulièrement difficile par l'évolution constante que connaissent ces structures au cours de cette période, évolution due notamment à la croissance et à l'organisation des tissus cérébraux. La technique de visualisation privilégiée pour observer le cerveau est l'imagerie par résonance magnétique (IRM), méthode non invasive permettant l'acquisition d'images des structures cérébrales in vivo et en trois dimensions à une résolution relativement élevée. Cependant, les différences anatomiques et l'évolution rapide des structures cérébrales chez le fœtus nécessitent une nouvelle modélisation du cerveau. Le travail de cette thèse est composé de deux parties. Tout d'abord, nous avons modifié l'algorithme FCM (Fuzzy C-Means) de manière à permettre une meilleure prise en compte du bruit et du biais de l'image grâce à la méthode des moyennes non-locales issue du débruitage d'image. Ces travaux ont fait l'objet d'une validation à partir de bases d'images synthétiques et réelles. Enfin, nous nous sommes penchés sur la problématique de la segmentation des tissus cérébraux en IRM fœtale, et nous avons introduit un modèle comportant des contraintes topologiques de manière à permettre une segmentation séquentielle des tissus, en se fondant sur la position relative des différentes structures. Ces travaux ont fait l'objet d'une validation à partir de cas réels. / The study of cerebral maturation aims at a better understanding of the brain's development during the pregnancy and the high lightment of the links between the change in cerebral structures and the cognitive development. This study is particularly difficult because of the constant evolution of these structures during the pregnancy. This evolution is due to the growing and the organisation of the different cerebral tissues. The preferred visualisation technique used to observe the brain is the magnetic resonance imaging (MRI), which is a non invasive acquisition technique of in vivo 3D cerebral images with a relative high resolution. Nevertheless, significant anatomical differences and the fast evolution of the fetal cerebral structures require a new modelisation of the brain. This thesis is divided in two parts. First, we modified the Fuzzy C-Means (FCM) algorithm in order to allow a better consideration of images noise and intensity bias thanks to the non-local means method, originaly elaborated for denoising purposes. These work were validated with databases of simulated and real images. Finally, we focused on the segmentation of cerebral tissues in fetal MRI by introducing topological constraints in order to obtain a sequential segmentation, based on relative positions of the tissus. These work were validated with real cases.