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

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

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

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

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

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

Dans le cadre de la robotique mobile, des progrès significatifs ont été obtenus au cours des trois dernières décennies pour la cartographie et la localisation. La plupart des projets de recherche traitent du problème de SLAM métrique. Les techniques alors développées sont sensibles aux erreurs liées à la dérive ce qui restreint leur utilisation à des environnements de petite échelle. Dans des environnements de grande taille, l’utilisation de cartes topologiques, qui sont indépendantes de l’information métrique, se présentent comme une alternative aux approches métriques.Cette thèse porte principalement sur le problème de la construction de cartes topologiques pour la navigation de robots mobiles dans des environnements urbains de grande taille, en utilisant des caméras omnidirectionnelles. La principale contribution de cette thèse est la résolution efficace et avec précision du problème de fermeture de boucles, problème qui est au coeur de tout algorithme de cartographie topologique. Le cadre de cartographie topologique éparse / hiérarchique proposé allie une approche de partionnement de séquence d’images (ISP) par regroupement des images visuellement similaires dans un noeud avec une approche de détection de fermeture de boucles permettant de connecter ces noeux. Le graphe topologique alors obtenu représente l’environnement du robot. L’algorithme de fermeture de boucle hiérarchique développé permet d’extraire dans un premier temps les noeuds semblables puis, dans un second temps, l’image la plus similaire. Cette détection de fermeture de boucles hiérarchique est rendue efficace par le stockage du contenu des cartes éparses sous la forme d’une structure de données d’indexation appelée fichier inversé hiérarchique (HIF). Nous proposons de combiner le score de pondération TFIDF avec des contraintes spatiales et la fréquence des amers détectés pour obtenir une meilleur robustesse de la fermeture de boucles. Les résultats en terme de densité et précision des cartes obtenues et d’efficacité sont évaluées et comparées aux résultats obtenus avec des approches de l’état de l’art sur des séquences d’images omnidirectionnelles acquises en milieu extérieur. Au niveau de la précision des détections de boucles, des résultats similaires ont été observés vis-à-vis des autres approches mais sans étape de vérification utilisant la géométrie épipolaire. Bien qu’efficace, l’approche basée sur HIF présente des inconvénients comme la faible densité des cartes et le faible taux de détection des boucles. Une seconde technique de fermeture de boucle a alors été développée pour combler ces lacunes. Le problème de la faible densité des cartes est causé par un sur-partionnement de la séquence d’images. Celui-ci est résolu en utilisant des vecteurs de descripteurs agrégés localement (VLAD) lors de l’étape de ISP. Une mesure de similarité basée sur une contrainte spatiale spécifique à la structure des images omnidirectionnelles a également été développée. Des résultats plus précis sont obtenus, même en présence de peu d’appariements. Les taux de réussite sont meilleurs qu’avec FABMAP 2.0, la méthode la plus utilisée actuellement, sans étape supplémentaire de vérification géométrique.L’environnement est souvent supposé invariant au cours du temps : la carte de l’environnement est construite lors d’une phase d’apprentissage puis n’est pas modifiée ensuite. Une gestion de la mémoire à long terme est nécessaire pour prendre en compte les modifications dans l’environnement au cours du temps. La deuxième contribution de cette thèse est la formulation d’une approche de gestion de la mémoire visuelle à long terme qui peut être utilisée dans le cadre de cartes visuelles topologiques et métriques. Les premiers résultats obtenus sont encourageants. (...) / Over the last three decades, research in mobile robotic mapping and localization has seen significant progress. However, most of the research projects these problems into the SLAM framework while trying to map and localize metrically. As metrical mapping techniques are vulnerable to errors caused by drift, their ability to produce consistent maps is limited to small scale environments. Consequently, topological mapping approaches which are independent of metrical information stand as an alternative to metrical approaches in large scale environments. This thesis mainly deals with the loop closure problem which is the crux of any topological mapping algorithm. Our main aim is to solve the loop closure problem efficiently and accurately using an omnidirectional imaging sensor. Sparse topological maps can be built by representing groups of visually similar images of a sequence as nodes of a topological graph. We propose a sparse / hierarchical topological mapping framework which uses Image Sequence Partitioning (ISP) to group visually similar images of a sequence as nodes which are then connected on occurrence of loop closures to form a topological graph. A hierarchical loop closure algorithm that can first retrieve the similar nodes and then perform an image similarity analysis on the retrieved nodes is used. An indexing data structure called Hierarchical Inverted File (HIF) is proposed to store the sparse maps to facilitate an efficient hierarchical loop closure. TFIDF weighting is combined with spatial and frequency constraints on the detected features for improved loop closure robustness. Sparsity, efficiency and accuracy of the resulting maps are evaluated and compared to that of the other two existing techniques on publicly available outdoor omni-directional image sequences. Modest loop closure recall rates have been observed without using the epi-polar geometry verification step common in other approaches. Although efficient, the HIF based approach has certain disadvantages like low sparsity of maps and low recall rate of loop closure. To address these shortcomings, another loop closure technique using spatial constraint based similarity measure on omnidirectional images has been proposed. The low sparsity of maps caused by over-partitioning of the input sequence has been overcome by using Vector of Locally Aggregated Descriptors (VLAD) for ISP. Poor resolution of the omnidirectional images causes fewer feature matches in image pairs resulting in reduced recall rates. A spatial constraint exploiting the omnidirectional image structure is used for feature matching which gives accurate results even with fewer feature matches. Recall rates better than the contemporary FABMAP 2.0 approach have been observed without the additional geometric verification. The second contribution of this thesis is the formulation of a visual memory management approach suitable for long term operability of mobile robots. The formulated approach is suitable for both topological and metrical visual maps. Initial results which demonstrate the capabilities of this approach have been provided. Finally, a detailed description of the acquisition and construction of our multi-sensor dataset is provided. The aim of this dataset is to serve the researchers working in the mobile robotics and vision communities for evaluating applications like visual SLAM, mapping and visual odometry. This is the first dataset with omnidirectional images acquired on a car-like vehicle driven along a trajectory with multiple loops. The dataset consists of 6 sequences with data from 11 sensors including 7 cameras, stretching 18 kilometers in a semi-urban environmental setting with complete and precise ground-truth.

On se consacre dans ce travail à des aspects mal pris en compte par la méthodologie classique de la carte thématique. On a tout d’abord, en première partie, revisité les connaissances sur la manière dont la carte était perçue, interprétée puis comprise, en mobilisant les domaines de la perception visuelle et de la sémiotique. La sémiotique visuelle constitue une passerelle entre l’étude de la signification des formes visuelles, importante en cartographie, et les approches esthétiques qui mobilisent ces signes visuels selon des modalités bien plus variées. La deuxième partie s’est intéressée successivement à plusieurs approches disciplinaires. L’ontologie esthétique nous a apporté une définition utile, mais surtout une analyse de la génération des propriétés esthétiques. L’iconographie a ensuite permis de décrire le fonctionnement sémiotique visuel. Enfin, on a mis à profit les travaux de certains artistes et théoriciens du design graphique qui ont exploré la relation entre formes graphiques et propriétés esthétiques. La troisième partie propose une synthèse des idées-forces des chapitres précédents en un ensemble de propositions, dont l’efficacité a été testée par enquête auprès de 850 géographes. On étudie ensuite plus longuement la mise en pratique de deux idées : la visualisation de différentes complexités visuelles internes et la visualisation des proportions et des relations colorées d’une carte. Ce travail aboutit à justifier le développement de nouvelles approches dans la méthodologie de la cartographie thématique, en allant emprunter des concepts, des idées, des méthodes d’analyse et des outils d’évaluation de l’image-carte à des disciplines proches. / We dedicated this work to issues inadequately addressed by the standard methodology of the thematic map. In the first part, we revisited the knowledge about how the map was perceived, interpreted and understood by mobilizing the domains of visual perception and semiotics. Visual semiotics provides a bridge between the study of the meaning of visual forms, important in mapping, and aesthetic approaches that mobilize these visual signs in a much more varied manner. The second part focused successively on several disciplinary approaches. The aesthetics ontology gave us a useful definition, but also an analysis of the generation of aesthetic properties. Iconography provided then the means to describe the semiotical operation. Finally, we took into account the work of some artists and graphic design theorists who have explored the relationship between graphic forms and aesthetic properties. The third section provides a summary of the key ideas of the previous chapters formalized into a set of propositions, whose effectiveness has been tested by surveying 850 geographers. We examine then more specifically the implementation of two ideas: the visualization of different internal visual complexities and the visualization of the colors proportions and relationships on a map. This work leads to justify the development of new approaches to the methodology of thematic mapping, by borrowing concepts, ideas, methods of analysis and assessment tools of the map-image from related disciplines.

Ce mémoire concerne les techniques d'indexation dans des bases d'image, ainsi que les méthodes de localisation en robotique mobile. Il fait le lien entre les travaux en Perception du pôle Robotique et Intelligence Artificielle du LAAS-CNRS, et les recherches sur la fouille de données menées à l'Université de Rabat. Depuis une dizaine d'années, la vision est devenue une source de données sensorielles essentielles sur les robots mobiles: elle fournit en particulier des représentations de l'environnement dans lequel doit se déplacer un robot sous la forme de modèles géométriques ou de modèles fondés sur l'apparence. Concernant la vision, seules les représentations fondées sur l'apparence ont été considérées; elles consistent en une base d'images acquises lors de déplacements effectués de manière supervisée durant une phase d'apprentissage. Le robot se localise en recherchant dans la base d'images, celle qui ressemble le plus à l'image courante: les techniques exploitées pour ce faire sont des méthodes d'indexation, similaires à celles exploitées en fouille de données sur Internet par exemple. Nous proposons une approche fondés sur des points d'intérêt extraits d'images en couleur texturées. Par ailleurs, nous présentons une technique de navigation par RFID (Radio Frequency IDentifier) qui utilise la méthode MonteCarlo, appliquée soit de manière intuitive, soit de manière formelle. Enfin, nous donnons des résultats très préliminaires sur la combinaison d'une perception par capteurs RFID et par capteurs visuels afin d'améliorer la précision de la localisation du robot mobile. / This document is related both to indexing methods in image data bases and to localization methods used in mobile robotics. It exploits the relationships between research works on Perception made in the Robotics department of LAAS-CNRS in Toulouse, and on Data Mining performed by the LIMAIARF lab at the Rabat University. Computer Vision has become a major source of sensory data on mobile robots for about ten years; it allows to build especially representations of the environment in which a robot has to execute motions, either by geometrical maps or by appearance-based models. Concerning computer vision, only appearance-based representations have been studied; they consist on a data base of images acquired while the robot is moved in an interactive way during a learning step. Robot self-localization is provided by searching in this data base, the image which looks like the one acquired from the current position: this function is performed from indexing or data mining methods, similar to the ones used on Internet. It is proposed an indexing method based on interest points extracted from color and textured images. Moreover, geometrical representations are also considered for an RFID-based navigation method, based on particle filtering, used either in a classical formal way or with a more intuitive approach. Finally, very preliminar results are described on a multi-sensory approach using both Vision and RFID tags in order to improve the accuracy on the robot localization

L’objectif de la thèse est de composer un catalogue des cartes françaises de l’ensemble ou d’une partie de la région étudiée, à partir des anciens recueils de cartes, et d’étudier les méthodes de publication des anciennes sources cartographiques : il s’agit de l’archéographie. Ce travail éclaire aussi la caractéristique des cartes russes, de nature historique, de la fin du XVIII° siècle et du début du XIX° siècle : l’exemple en est fourni par la « Carte du bassin du lac Sévang en Arménie, relevée par les ingénieurs russes en 1832 » et reformulée en langue française, en 1832, par le savant suisse Du Bois de Montperreux. A partir de cette carte, l’auteur de la thèse effectue des recherches sur l’altitude du lac Sévan à l’époque de l’établissement de ladite carte et sur les changements démographiques survenus dans le bassin du lac deSévan à la suite des traités russo-persans et russo-turcs. Le travail de Vardan Mkhitaryan se présente comme la première étude des cartes françaises sur le sujet et présente un catalogue de cartes inédit dans l’ensemble. [etc.] / The goal of the thesis is to set up a catalog of the French maps of the whole or part of the studied region, based on the ancient maps collections, and to study the publishing methods of the ancient cartographic sources. This is called archeography. This also enlightens the characteristics of the Russian maps, of historical nature, of the end of the 18th century and the beginning of the 19th century: a provided example is the “Map of the lake Sevang's basin in Armenia, measured by the Russia engineers in 1832” and reworded in French, in 1832, by the Swiss scholar Du Bois de Montperreux. Basing on this map, the author of the thesis performs some researches on the altitude of the lake Sevan at the time of the setting up of the aforesaid map and on the demographic changes that occurred in the lake Sevan's basin after the Russian-Persian and the Russian-Turkish treaties. VardanMikhitarian's work appears to be the the first study of the French maps on this subject and displays, in the main, an unprecedented catalogue of maps. [etc.]