Les cartes combinatoires sont des dessins de graphes sur des surfaces (orientable ou non), considérés à déformation près. On propose une méthode bijective de découpage d'une carte, appelée ouverture, qui à une carte associe une autre carte, dessinée sur la même surface, possédant une unique face, et munie de décorations supplémentaires appelées bourgeons. Cette construction généralise l'ouverture décrite pour le cas des cartes planaires dans [Sch97].Plusieurs travaux datant des années 90 ont permis de démontrer par des méthodes calculatoires poussées des propriétés concernant la série génératrice des cartes d'une surface donnée. En particulier, dans le cas d'une surface orientable, cette série peut s'écrire comme une fonction rationnelle d'une certaine série d'arbres. Ceci est valable que les cartes soient énumérées simplement par arêtes [BenCan91], ou également par sommets et faces [BenCanRic93]. Un résultat similaire plus faible peut également être exprimé dans le cas des cartes non orientables [AG00]. Ces propriétés de rationalité des séries génératrices de cartes expriment en fait des propriétés combinatoires structurelles fortes concernant les cartes elles-même, et la recherche d'une interprétation combinatoire de ces propriétés a été un moteur important du développement de la combinatoire bijective des cartes.L'utilisation de notre algorithme d'ouverture produit une carte qui peut à son tour être décomposée successivement en cartes plus petites munies de décorations additionnelles.Après une analyse approfondie des objets ainsi obtenus et de leur séries génératrices, ceci permet de démontrer combinatoirement les résultats de rationalité évoqués plus haut.Une k-triangulation d'un polygone fini est un ensemble maximal (pour l'inclusion) de diagonales, qui ne possède pas k+1 diagonales se croisant 2 à 2. On appelle k-étoile un ensemble de 2k+1 points et 2k+1 diagonales tel que chaque point est relié à ses deux points opposés. Les travaux de [PilSan07] ont permis de montrer qu'une k-triangulation peut être décomposée en un complexe de k-étoiles, et que les multitriangulations peuvent être obtenue l'une de l'autre par une succession d'opérations élémentaires appelées flips.Notre objectif est d'étendre ces résultats au cas des multitriangulations d'une surface quelconque. Dans cette optique, on commence par étudier une certaine classe de multitriangulations d'un polygone ayant un nombre infini de côtés, et à étendre à ce contexte les résultats principaux de [PilSan07]. En utilisant la construction classique du recouvrement universelle d'une surface quelconque, on espère ensuite pouvoir réduire l'étude d'une multitriangulations quelconque à celle d'une multitriangulation périodique d'un polygone infini, et on présente dans ce sens une ébauche de preuve, sous forme de plusieurs conjectures élémentaires. / A combinatorial map is the embedding of a graph on a surface (orientable or not), considered up to deformation. We describe a bijective method, called opening, that allows to reduce a map into a smaller map on the same surface, with only one face, along with some additional decorations called blossoms. This construction generalizes the opening described in the case of planar maps in [Sch97].Several papers from the 90's used advanced calculation methods to obtain properties on the generating series of maps on a given surface. In particular, in case the surface is orientable, this series can be written as a rational function of the generating series of some trees. This is valid both in case the maps are enumerated by their number of edges only [BenCan91], by both their number of vertices and faces [BenCanRic93]. A similar weaker result was also obtained in the case of non-orientable surfaces [AG00]. Actually, these rationality properties concerning the generating series of maps imply strong structural properties concerning the maps themselves, and providing a combinatorial interpretation of these properties has been an important motivation in the development of the bijective combinatorics of maps.The opening algorithm that we describe produces a map that can be further successively decomposed into smaller maps along with additional decorations. A deep analysis of the maps obtained this way, and their generating series, then allows to recover in a combinatorial way the rationality results described earlier.A k-triangulation of a finite polygon is a set of diagonals, maximal for the set-inclusion, such that no k+1 of its diagonals are pairwise crossing. A k-star is a set of 2k+1 points and 2k+1 diagonals such that each point is adjacent to its two opposite points. The work of [PilSan07] showed that a k-triangulation can be decomposed into a complex k-stars, and that multitriangulations can be obtained one from another by a succession of local elementary operations called flips.Our purpose is to extend these results to the case of multitriangulations on any surface. In this regard, we first study a class of multitriangulations of a polygon with an infinite number of sides, and extend to this context the main results of [PilSan07]. Using the classical construction of the universal cover of a surface, we then hope to reduce the case of a multitriangulations in any surface to that of a periodic multitriangulation of an infinite polygon. We present some element of such a proof, along with some conjectures that would allow to conclude.

Le travail de recherche concerne le traitement des données qualitatives par des méthodes neuronales. Différents modèles d'apprentissage non supervisés sont proposés.<br /><br />Ce travail de thèse a été réalisé à la direction de la recherche de RENAULT. Le travail s'est focalisé sur le développement d'un modèle de reconnaissance de trafic.<br /><br />Le premier modèle proposé dans cette thèse est dédié aux données binaires ''BTM''. C'est un modèle de quantification vectorielle de type carte topologique. Ce modèle prend les caractéristiques principales des cartes topologiques. Pour ce nouveau modèle, afin de prendre en compte les spécificités des données binaires, on a choisi de changer la métrique usuelle utilisée dans les modèles de cartes topologiques et d'utiliser la distance Hamming.<br /><br />Le second modèle est le premier modèle probabiliste de cartes topologiques dédié aux données binaires. Ce modèle s'inspire de travaux antérieurs qui modélisent une distribution par un mélange de mélange de lois de Bernoulli.<br /><br />Le troisième modèle est un nouveau modèle de carte topologique appelé CTM (Categorical topological Map) adapté à la classification non supervisée des données qualitatives multi-dimensionnelles. Ce nouveau modèle conserve cependant les principales caractéristiques des deux modèles précédents. Afin de maximiser les vraisemblance des données, CTM utilise de manière classique l'algorithme EM.<br /><br />Dans ce mémoire, on introduit le domaine d'application propre au travail mené chez RENAULT. Nous détaillerons l'apport original de notre travail: utilisation de l'information catégorielle pour traiter de la reconnaissance du trafic. Nous exposerons les différentes analyses effectuées sur l'application des algorithmes proposés.

Aide à la conception de légendes personnalisées et originales : proposition d'une méthode coopérative pour le choix des couleurs Les utilisateurs s'approprient aisément les outils cartographiques numériques pour se construire leur propre carte. Cependant, l'accès aux outils ne suffit pas pour concevoir une légende cartographique de qualité. Il est nécessaire de savoir comment faire de bons choix de représentation graphique, en particulier de bons choix de couleurs. Une expertise cartographique comportant des connaissances en sémiologie graphique et en perception des couleurs (contrastes et harmonies) est nécessaire : soit l'utilisateur possède ces connaissances, soit les outils doivent les lui apporter. Dans ce contexte, nous cherchons à aider les utilisateurs à concevoir des légendes personnalisées et originales, en nous concentrant sur l'aide au choix des couleurs. Nous proposons une méthode de conception coopérative en quatre phases reposant sur des interactions homme-machine : 1- choix d'une source d'inspiration, 2- acquisition des préférences de l'utilisateur sur les sources d'inspiration, 3- interprétation des préférences et construction de légendes adaptées, 4- retouche de légendes. Deux stratégies de conception sont envisagées en utilisant deux types de sources d'inspiration : des échantillons de carte et des toiles de maîtres. En partant du constat que des désaccords entre l'utilisateur et le système peuvent se produire, nous proposons d'utiliser des techniques de dialogue homme-machine pour améliorer l'adaptation du système à l'utilisateur. Le modèle de dialogue ainsi proposé est implémenté dans le prototype COLorLEGend (COLLEG)

Cette thèse se compose de plusieurs travaux portant sur deux branches de la théorie des probabilités: processus de particules et cartes planaires aléatoires. Un premier travail concerne les aspects algébriques des mesures invariantes des processus de particules. Nous obtenons des conditions nécessaires et suffisantes sous lesquelles un processus de particules en temps continu avec espace d’états local discret possède une mesure invariante simple. Dans un deuxième travail nous étudions un modèle "biologique" de coexistence de 2 espèces en compétition sur un espace partagé, et soumis à des épidémies modélisées par un modèle probabiliste appelé "feux de forêts". Notre résultat principal montre que pour deux espèces, il existe des régions explicites de paramètres pour lesquelles une espèce domine ou les deux espèces coexistent. Il s’agit d’un des premiers modèles pour lesquels la coexistence d’espèces sur le long terme est prouvée. Les troisièmes et quatrièmes travaux. portent sur les cartes planaires décorées par des arbres. Dans le troisième nous présentons une bijection entre l’ensemble des cartes décorées par des arbres et le produit Cartésien entre l’ensemble des arbres planaires et l’ensemble de cartes à bord simple. Nous obtenons quelques formules de comptage et quelques outils pour l’étude de cartes aléatoires décorées par un arbre. Le quatrième travail montre que les triangulations et quadrangulations aléatoires uniformes avec f faces, bord simple de taille p et décorées par un arbre avec a arêtes, convergent en loi pour la topologie locale vers différentes limites, dépendant du comportement fini ou infini de la limite de f, p et a. / This thesis consists in several works exploring some models belonging to two branches of probability theory: interacting particle systems and random planar maps. A first work concerns algebraic aspects of interacting particle systems invariant measures. We obtain some necessary and sufficient conditions for some continuous time particle systems with discrete local state space, to have a simple invariant measure. In a second work we investigate the effect on survival and coexistence of introducing forest fire epidemics to a certain two-species spatial competition model. Our main results show that, for the two-type model, there are explicit parameter regions where either one species dominates or there is coexistence; contrary to the same model without forest fires, for which the fittest species alwaysdominates. The third and fourth works are related to tree-decorated planar maps. In the third work we present a bijection between the set of tree-decorated maps and the Cartesian product between the set of trees and the set of maps with a simple boundary. We obtain some counting results and some tools to study random decorated map models. In the fourth work we prove that uniform tree-decorated triangulations and quadrangulations with f faces, boundary of length p and decorated by a tree of size a converge weakly for the local topology to different limits, depending on the finite or infinite behavior of f, p and a.

Les véhicules dits intelligents actuellement développés par la plupart des constructeurs automobiles, ainsi que les véhicules autonomes nécessitent des informations sur le contexte dans lequel ils évoluent. Certaines de ces informations (par exemple la courbure de la route, la forme des intersections, les limitations de vitesses) sont fournies en temps réel par le système de navigation qui exploite les données de cartes routières numériques. Des défauts résultant de l’évolution du réseau routier ou d’imprécisions lors de la collecte de données peuvent être contenus dans ces cartes numériques et entraîner le dysfonctionnement des systèmes d’aide à la conduite. Les recherches menées dans cette thèse visent à rendre le véhicule capable d’évaluer, de manière autonome et en temps réel, l’intégrité des informations fournies par son système de navigation. Les véhicules de série sont désormais équipés d’un grand nombre de capteurs qui transmettent leurs mesures sur le réseau central interne du véhicule. Ces données sont donc facilement accessibles mais de faible précision. Le défi de cette thèse réside donc dans l’évaluation de l’intégrité des informations cartographiques malgré un faible degré de redondance et l’absence de données fiables. On s’adresse à deux types de défauts cartographiques : les défauts structurels et les défauts géométriques. Les défauts structurels concernent les connections entre les routes (intersections). Un cas particulier de défaut structurel est traité : la détection de ronds-points qui n’apparaissent pas dans la carte numérique. Ce défaut est essentiel car il est fréquent (surtout en Europe) et perturbe le fonctionnement des aides à la conduite. Les ronds-points sont détectés à partir de la forme typique de la trajectoire du véhicule lorsqu’il les traverse, puis sont mémorisés pour avertir les aides à la conduite aux prochains passages du véhicule sur la zone. Les imprécisions de représentation du tracé des routes dans la carte numérique sont quant à elles désignées comme défauts géométriques. Un formalisme mathématique est développé pour détecter ces défauts en comparant l’estimation de la position du véhicule d’après la carte à une autre estimation indépendante de la carte. Cette seconde estimation pouvant elle aussi être affectée par un défaut, les anciens trajetsdu véhicule sur la même zone sont utilisés. Un test statistique est finalement utilisé pour améliorer la méthode de détection de défauts géométriques dans des conditions de mesures bruitées. Toutes les méthodes développées dans le cadre de cette thèse sont évaluées à l’aide de données réelles. / Several Intelligent Vehicles capabilities from Advanced Driving Assistance Systems (ADAS) to Autonomous Driving functions depend on a priori information provided by navigation maps. Whilst these were intended for driver guidance as they store road network information, today they are even used in applications that control vehicle motion. In general, the vehicle position is projected onto the map to relate with links in the stored road network. However, maps might contain faults, leading to navigation and situation understanding errors. Therefore, the integrity of the map-matched estimates must be monitored to avoid failures that can lead to hazardous situations. The main focus of this research is the real-time autonomous evaluation of faults in navigation maps used in intelligent vehicles. Current passenger vehicles are equipped with proprioceptive sensors that allow estimating accurately the vehicle state over short periods of time rather than long trajectories. They include receiver for Global Navigation Satellite System (GNSS) and are also increasingly equipped with exteroceptive sensors like radar or smart camera systems. The challenge resides on evaluating the integrity of the navigation maps using vehicle on board sensors. Two types of map faults are considered: Structural Faults, addressing connectivity (e.g., intersections). Geometric Faults, addressing geographic location and road geometry (i.e. shape). Initially, a particular structural navigation map fault is addressed: the detection of roundabouts absent in the navigation map. This structural fault is problematic for ADAS and Autonomous Driving. The roundabouts are detected by classifying the shape of the vehicle trajectory. This is stored for use in ADAS and Autonomous Driving functions on future vehicle trips on the same area. Next, the geometry of the map is addressed. The main difficulties to do the autonomous integrity monitoring are the lack of reliable information and the low level of redundancy. This thesis introduces a mathematical framework based on the use of repeated vehicle trips to assess the integrity of map information. A sequential test is then developed to make it robust to noisy sensor data. The mathematical framework is demonstrated theoretically including the derivation of definitions and associated properties. Experiments using data acquired in real traffic conditions illustrate the performance of the proposed approaches.

Les cartes planaires sont des graphes planaires dessinés sur la sphère et vus à déformation près. De nombreuses propriétés des cartes sont supposées universelles, dans le sens où elles ne dépendent pas des détails du modèle choisi. Nous commençons par établir une inégalité isopérimétrique dans la quadrangulation infinie du plan. Nous confirmons également une conjecture de Krikun portant sur la longueur des cycles les plus courts séparant la boule de rayon $r$ de l'infini. Dans un deuxième temps, nous nous intéressons à l'effet de modifications de distances sur la géométrie à grande échelle des quadrangulations uniformes, élargissant la classe d'universalité de la carte brownienne. Nous montrons également que la bijection de Tutte, entre quadrangulations et cartes planaires, est asymptotiquement une isométrie. Enfin, nous établissons une borne supérieure sur le temps de mélange de la marche aléatoire dans les cartes aléatoires. / Planar maps are planar graphs drawn on the sphere and seen up to deformation. Many properties of maps are conjectured to be universal, in the sense that they do not depend on the details of the model.We begin by establishing an isoperimetric inequality in the infinite quadrangulation of the plane. We also confirm a conjecture by Krikun concerning the length of the shortest cycles separating the ball of radius $r$ from infinity. We then consider the effect of modifications of distances on the large-scale geometry of uniform quadrangulations, extending the universality class of the Brownian map. We also show that the Tutte bijection, between quadrangulations and planar maps, is asymptotically an isometry. Finally, we establish an upper bound on the mixing time of the random walk in random maps.

A partir de températures de surface mesurées sur une base régulière et répétitive par des capteurs embarqués sur des satellites, il a été décidé de produire des cartes de températures de surface, d’indices de gel et de dégel et de limites de répartition du pergélisol sur les territoires arctiques et subarctiques. Le territoire cartographié est le territoire du Québec-Labrador. Les températures mesurées par satellite ont été comparées avec les températures de différentes stations situées en région de pergélisol continu, en Alaska et au Québec (chapitre 1). Les coefficients de corrélations sur l’ensemble des stations entre les températures de l’air et les « Land Surface Temperatures » (LST) du capteur MODIS des satellites Aqua et Terra sont tous supérieurs à 0.80. Ces mesures ont donc un extraordinaire potentiel pour déterminer les températures de surface sur le vaste territoire nordique où les stations de mesures sont très dispersées dans l’espace. Comme le territoire couvert par les satellites est de 2300 km à chaque passage (ils passent deux fois par jour), la possibilité de couvrir des étendues régionales à peu de frais est immense. Cependant, les régions arctiques connaissent un ennuagement assez important et les données satellitaires ne sont pas continues sur l’année. Leur nombre est tout de même suffisant pour établir une interpolation temporelle sur chaque pixel. Au chapitre 2, il est montré que le modèle mathématique utilisé permet de calculer les températures moyennes annuelles et les indices de gel à partir des LST très bien corrélées, et les indices de dégel corrélés de façon satisfaisante avec ceux calculés aux stations. A partir de ces comparaisons entre les pixels et les stations présentes dans un pixel, les cartes ont été produites. L’analyse de ces cartes, moyenne annuelle, indice de gel et de dégel montre des similitudes dans les régions où les données existent mais surtout établissent une représentation originale sur les parties de territoire où aucune station de mesures n’existe et apportent un élément nouveau à la compréhension du climat du Québec-Labrador. Au chapitre 3, les indices habituels qui servent à délimiter le pergélisol sur des échelles régionales sont appliqués à ce territoire. Là encore, il est démontré que la limite sud du pergélisol continu ainsi dessinée est comparable à celle des cartes existantes. Toutefois, mesurées entre 2000 et 2005, les conditions thermiques propres à cette limite ont récemment migré vers le nord. Le modèle mis au point dans cette thèse est une avancée exceptionnelle pour la cartographie du pergélisol. / From near surface temperatures measured by sensors onboard satellites, at a regular and repeated time, it has been decided to produce near surface temperature, freezing and thawing indices maps and permafrost distribution boundaries in Arctic and Subarctic regions. The mapped area is the Quebec-Labrador territory. Land Surface Temperatures (LST) retrieved from the MODIS sensor on Aqua and Terra satellites were compared as well as possible with soil and air temperatures of several stations over continuous permafrost within different tundra landscapes, in the North Slope of Alaska and Northern Quebec and Labrador (chapter 1). Correlations values (R²) established between near surface air temperatures (Tair) on all ground stations and LST from the MODIS sensor are above 0.80. This proves that LST data have a high potential to be used as regional complement of temperatures from meteorological stations. As the Terra and Aqua swath is 2300 km wide, each overpass (twice a day for both satellites), makes it possible to map vast areas at low cost. However, Arctic areas are often cloudy which results in discontinuous satellite data. The number of non-cloudy days is large enough to necessitate the calculation of a temporal interpolation between days and for each pixel. Then, in chapter 2, a mathematic model produces excellent correlations between LSTs and Tair, mean annual near surface temperatures and freezing index; correlations with thawing indices are barely satisfactory. From these correlations between pixels and ground stations, data maps are drawn. An analysis of mean annual near surface temperature, freezing and thawing indices maps shows similarities in areas where data are well known and provides some new understanding of the surface climate of Quebec-Labrador. In chapter 3, usual indices such as isotherms, which are of used to define permafrost boundaries on regional scales, are applied on this territory. Here, again, the southern limit of continuous permafrost as drawn is comparable to other existing maps. Surface thermal conditions conducive to permafrost recently migrated northward. Our model therefore offers advanced capabilities for permafrost mapping and monitoring.

Sur un territoire, des sources sonores émettent des sons qui peuvent être d’origines anthropophoniques (i.e. le bruit des véhicules), biophoniques (i.e. les sons émis par les oiseaux), ainsi que géophoniques (i.e. le bruit du vent). Ceci permet de décrire un paysage sonore des lieux tout en alimentant des besoins particuliers propres à la cartographie de l’environnement sonore tels que les propriétés acoustiques des territoires, nécessaires à la compréhension de l’environne me nt sonore. Au-delà des travaux de recherches qui étudient et analysent les propriétés acoustiques de l’environnement, l’état de l’existant se concentre sur deux types de cartes sonores : les cartes d’inventaire de sons et les cartes de bruit. Deux approches méthodologiques sont à l’origine de la production de ces cartes. La première est basée sur des enregistrements sonores mesurés et géoréférencées sur le territoire à l’aide de sonomètres, ou d’applications installées sur des tablettes/téléphones intelligents. La deuxième sert à modéliser la propagation de l’onde acoustique en lien avec les objets présents sur le territoire (i.e. bâtiments, arbres, etc.). Bien que cette deuxième approche considère les différents facteurs environnementaux qui peuvent affaiblir l’onde acoustique comme l’absorption atmosphérique (causée par le vent, la température, etc.), la divergence géométrique et la nature de la couverture des sols, on constate qu’elle est peu documentée dans la littérature scientifique, lorsqu’aucun capteur sonore n’est utilisé pour produire des cartes sonores. L’objectif principal est de définir une méthode générique de modélisation de la propagation acoustique du son pour territoire à l’aide de données géospatiales multi-sources, dont des images à très haute résolution. Ainsi à l’aide des outils géomatiques, il est possible de représenter l’interaction qui existe entre l’onde sonore et les objets environnementaux composant ce territoire. Il est alors possible à partir d’une source sonore et des points récepteurs du son de réaliser des cartes dites spatio-phoniques. Mots clés : environnement sonore, modélisation, géomatique, propagation, données géospatiales, cartographie / On a territory, sound sources emit sounds that can be of anthropophonic origins (i.e. vehicle noise), biophonic origins (i.e. sounds emitted by birds), as well as geophonic origins (i.e. wind noise). This makes it possible to describe a soundscape of the places while feeding particular needs specific to the mapping of the sound environment such as the acoustic properties of the territories, necessary to the understanding of the sound environment. Beyond the research work that studies and analyzes the acoustic properties of the environment, the state of the existing focuses on two types of sound cards: sound inventory cards and noise maps. Two methodological approaches are behind the production of these cards. The first is based on sound recordings measured and georeferenced on the territory using sound level meters, or applications installed on tablets/smartphones. The second is used to model the propagation of the acoustic wave in relation to the objects present on the territory (i.e. buildings, trees, etc.). Although this second approach considers the different environmental factors that can weaken the acoustic wave like atmospheric absorption (caused by wind, temperature, etc.), the geometric divergence and the nature of the cover of soil, it is found that it is poorly documented in the scientific literature, when no sound sensor is used to produce sound cards. The main objective is to define a generic method for modeling the acoustic propagation of a territory using multi-source geospatial data including very high resolution images. Thus, using geomatic tools, it is possible to represent the interaction that exists between the sound wave and the environmenta l objects that make up this territory. It is then possible from a sound source and sound receiving points to make so-called spatio-phonic cards

Une carte cognitive est un modèle graphique qui permet de représenter des systèmes complexes contenant un grand nombre de facteurs qui interagissent. Une carte cognitive est un graphe orienté étiqueté dont les sommets représentent des concepts et dont les arcs représentent les influences entre ces concepts. Le modèle des cartes cognitives inclut un mécanisme de raisonnement nommé propagation, qui calcule l'influence entre toute paire de concepts. Notre thèse a pour objectif d'étendre le modèle des cartes cognitives et le mécanisme de raisonnement qui y est associé. Une première contribution consiste à associer à une carte une ontologie qui organise de façon hiérarchique les concepts : l'utilisation de cette ontologie comme un dictionnaire des données hiérarchiques permet à l'utilisateur de trouver les concepts qui l'intéressent dans une carte. Notre deuxième contribution consiste à fournir des mécanismes à l'utilisateur pour lui permettre de visualiser, à la demande, des vues simplifiées de la carte initiale. Notre troisième contribution fournit une notion d'échelle qui permet de sélectionner le niveau de détail de la carte que l'on veut voir. Notre quatrième contribution consiste en des mécanismes qui donnent à l'utilisateur une carte adaptée à ses savoirs : ceci s'effectue par l'utilisation de profils des utilisateurs ou de contextes exprimés par des graphes conceptuels. Les systèmes SCCO et SCCC montrent la faisabilité de l'approche.

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