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

Étude du trace automatique des canaux d'interconnexion de circuits intégrés. Une première partie est consacrée au trace de canaux rectangulaires dont les points à interconnecter sont tous repartis sur deux faces parallèles : les canaux bifaces. Une modélisation du problème est proposée. La faisabilité du problème est étudié et un minorant de la largeur minimale du canal est calcule. Différentes circonstances dans lesquelles ce minorant ne peut être atteint sont identifiées. Une heuristique de trace est décrite et formalisée. Une deuxième partie est consacrée au problème de l'interconnexion d'un ensemble de blocs polygonaux repartis dans un plan et séparés par des canaux d'interconnexion : le problème multi-canal. Les différentes approches du problème sont analysées. Une stratégie originale pour la résolution du problème pose par les configurations en "matrice de blocs" est ensuite proposée. Une heuristique originale de trace est décrite, ainsi qu'un programme implémentant cette heuristique. Des résultats expérimentaux sont présentés.

Étude des méthodes de placements : évaluation des critères d'optimisation, et fonction du cout de placement. Présentation des heuristiques de placement suivant une classification synthétique afin de mettre en évidence leurs avantages, leurs inconvénients et leurs domaines d'application. Principes d'adaptation des méthodes de placement au traitement des réseaux structurés. Implantation des connexions dans les structures à canaux d'interconnexion. Détail des stratégies basées sur une décomposition du traitement en deux phases successives. Étude en particulier des méthodes de tracé global sur les réseaux prédiffusés. Présentation d'un système d'implantation automatise sur les réseaux de cellules prédiffusés structurés en matrice de macro-site.

L'objet de cette thèse est la réalisation d'algorithmes et d'outils d'aide à l'étude des propriétés de structures combinatoires particulières, les structures décomposables. Nous nous intéressons pour cela à la génération aléatoire et systématique de structures décomposables, puis à leur représentation graphique automatique. Ce travail se situe à la frontière entre calcul mathématique et visualisation. Les structures décomposables sont les structures combinatoires qu'il est possible de former récursivement en utilisant des constructeurs aux propriétés particulières. Le point de vue est similaire à celui adopté dans la théorie des espèces de structures, où l'on privilégie la description d'ensembles de structures à partir de transformations d'ensembles existants. Il est alors possible, grâce à des spécifications, de décrire une infinité d'ensembles de structures combinatoires parmi lesquels les permutations, les graphes fonctionnels, les arbres enracinés ou encore les hiérarchies. L'intérêt de cette démarche tient au fait que l'on sait résoudre des problèmes de dénombrement et de comportement asymptotique sur ces ensembles et générer aléatoirement de façon uniforme des structures de ces ensembles. Les applications concernent le calcul de complexité en moyenne d'algorithmes, et la génération de jeux de tests pour la validation expérimentale ou l'étalonnage d'algorithmes. Nous présentons dans cette thèse deux types de résultats. Les premiers concernent la génération de structures décomposables, les seconds leur représentation graphique. Nous présentons une implantation d'un algorithme classique de génération aléatoire de structures décomposables, et nous proposons des techniques permettant de générer tous les éléments d'un ensemble à partir de sa spécification. Nous proposons également un algorithme de tracé de graphes particuliers, pour lesquels il existe à la fois des relations d'adjacence et d'inclusion entre les nœœœœœoeuds. Ces graphes, que nous appelons les graphes composés, sont en effet bien adaptés à la représentation de la nature générique des structures décomposables. Ce travail est concrétisé par la réalisation de deux logiciels de tracé de structures combinatoires. Leur utilisation n'est cependant pas limitée à ce seule domaine et les apsects liés à leur application à la visualisation de graphes en général sont abordés.

Les principaux algorithmes de placement et d'interconnexion sont passes en revues. On propose ensuite une classification des représentations symboliques de circuits intégrés, et on s'intéresse aux circuits représentés à l'aide du symbolisme défini pour le MD-MOS. Une methode de placement des portes et de traces des connexions automatises est présentée pour les circuits MD-MOS organisés en cellules à une et deux lignes d'alimentation.

La partie centrale des lampes à basse consommation est constituée d'un tube en verre rempli de plasma de mercure et recouvert d'une couche de grains de luminophores. Ces grains de quelques microns absorbent la radiation UV et émettent de la lumière visible. Dans cette thèse, deux problèmes liés à ces couches sont étudiés. Dans une première partie, un modèle de champ de phase est développé pour décrire le changement de la morphologie des grains lors du recuit de synthèse en présence d'un fondant. A l'aide de ce modèle, nous avons mis en évidence le rôle des tensions de surface et des mécanismes de transport de matière dans le liquide. Dans une seconde partie, nous utilisons la méthode du tracé de rayons pour modéliser les propriétés optiques d'une couche de grains de luminophores. Cette dernière a deux buts qui peuvent sembler contradictoire : absorber le maximum de rayons UV et maximiser l'extraction de lumière visible. Nous avons mis en évidence l'existence d'un optimum d'efficacité d'extraction, ce qui suggère que les pertes de lumière visible dans la lampe peuvent être atténuées en utilisant des couches peu compactes.

Le tracé de rayons est désormais un algorithme classique pour la visualisation en synthèse d'images. Nous nous sommes cependant efforcés de ne pas le considérer comme un simple algorithme de visualisation mais comme un algorithme plus général de simulation de transfert d'énergie au sein d'un environnement géométrique. Ce choix a conduit à la définition d'un modèle géométrique indépendant du modèle de rendu qui lui est associé. Ce modèle utilise une méthode par arbre de construction (CSG) avec deux améliorations essentielles: l'utilisation d'un graphe au lieu d'un arbre ainsi que la possibilité d'associer des propriétés à n'importe quel objet du modèle. L'algorithme de calcul d'intersection entre un rayon et un objet est spécialement adapte à ce modèle, et il utilise une technique d'accélération nouvelle, basée sur l'utilisation d'englobant appelés boites englobantes généralisées, palliant certains inconvénients des techniques classiques. L'algorithme de rendu a été rendu générique, ce qui permet de changer facilement d'implémentation de l'algorithme de rendu. Les modèles classiques (Lambert et Phong) sont présentés en détail. Enfin, nous présentons trois applications de notre environnement: l'utilisation de nouveaux systèmes de perspectives, la visualisation de densités volumiques et de primitives de lumière, ainsi qu'une version parallèle de notre algorithme.

En synthèse d'images réaliste, nous simulons fidèlement les lois physiques pour créer une image. Les sources lumineuses sont alors un élément essentiel car ce sont elles qui produisent l'énergie répartie dans la scène. Ce document caractérise les modèles de sources actuels et propose des méthodes pour accélérer leur traitement. Après une étude détaillée du domaine au chapitre 2, nous recensons au chapitre 3 les solutions les plus efficaces pour modéliser une source lumineuse. Dans le chapitre 4, nous proposons une solution innovante pour traiter les sources en champ lointain. Le chapitre 5 est consacré au cas du champ proche. Nous introduisons une nouvelle structure de données, dite lumigraphe sphérique, réduisant par 100 les temps de calcul de traitement des rayons d'ombre. Une source de lumière moderne peut être composée d'objets complémentaires tels que des miroirs. L'ensemble des rayons en sortie de cet objet peut être vu comme une source à part entière. Le chapitre 6 traite de telles sources, dites virtuelles.

La synthèse d'images de paysages est l'axe directeur de cette thèse. Ce thème permet d'aborder différents problèmes ouverts en synthèse d'image tri-dimensionnelle. Plusieurs techniques d'optimisation de la méthode du tracé de rayon sont exposés à travers deux applications: la visualisation de surfaces topographiques définies sur une grille rectangulaire et la représentation de scènes composées d'objets variés. Pour accroitre le réalisme des images générées, un algorithme de synthèse de textures adapté à la représentation de textures naturelles et particulièrement de ciels nuageux est représenté. Enfin une discussion des problèmes liés à l'utilisation d'une table de couleur est fournie accompagnée d'un exposé de la solution adoptée pour produire les images présentées dans ce rapport.

Cette thèse traite de la problématique de l'analyse automatique de tracés manuscrits réalisés à mains levée, à caractère géométrique et acquis en ligne. Lorsque l'on analyse un tracé en ligne, on peut le faire selon plusieurs angles. Comme pour les tracés hors ligne, on peu s'atteler à reconnaitre la forme produite. Mais le caractère en ligne de l'acquisition permet également d'autres niveaux d'analyse, comme l'analyse de la procédure utilisée par le dessinateur lors de la production de son dessin. Nous avons dans le cadre de ce travail élaboré des outils permettant de telles analyses de la production de tracé. Dans une première partie nous traitons des pré traitements à effectuer sur le tracé afin de pouvoir procéder aux analyses spatio-graphique et procédurale. Ces pré traitements sont le filtrage, la segmentation mixte à base d'arcs de cercles et de segments de droite, la sélection des points d'intérêt ainsi que l'identification de la nature de ces points. La seconde partie concerne l'analyse visuo-spatiale. Nous abordons alors deux aspects: la question de la reconnaissance des formes et celle de l'évaluation automatique de leur qualité. Notre contribution consiste en une méthode de reconnaissance basée sur l'apparence utilisant des descripteurs locaux. La dernière partie traite de l'analyse procédurale. Nous proposons une méthode d'extraction et de modélisation de la procédure mise en œuvre lors du dessin d'une forme. Nous montrons comment en utilisant cette modélisation, nous pouvons non seulement déterminer la procédure favorite d'un utilisateur mais également reconnaitre un dessinateur par l'analyse de sa procédure. / This thesis handles the problem of the automatic analysis of online hand drawn geometric sketches. An online sketch can be analysed according to several points of view. As for offline sketching, we can try to recognize the produced shape. However, online sketching allows other levels of analysis. For example the analysis of the behavior of the drawer during the production of the sketch. In this thesis, we have tried to develop tools allowing a multi level analysis, including both shape and behavior analysis. The first part of our work deals with the pre treatments that must be performed on the sketch in order to allow upper level analysis. Those pre treatments are filtering, mixed segmentation and feature points detection and labelisation. In the second part, we approach shape analysis in two aspects: shape recognition and evaluation. We have developed a appearance based method which use local descriptors to allows both recognition and evaluation of the quality of a produced shape compared to the model . in the last part we propose a method for drawer's behavior extraction and modeling. Then we show how we can not only determine the favorite procedure of a drawer but also recognize the drawer by analyzing his behavior.