Dans le cadre de la robotique mobile en environnement extérieur, les concepts de localisation et de perception sont au coeur de toute réalisation. Aussi, les travaux menés au sein de cette thèse visent à rendre plus robustes des processus de localisation existants sans pour autant augmenter de manière notable leur complexité. La problématique proposée place un robot au sein d'un environnement potentiellement dangereux avec pour objectif de suivre une trajectoire établie comme sécurisée avec une carte aussi simple que possible. De plus, des contraintes fortes sont imposées tant dans la réalisation (système peu onéreux, indétectable) que dans le résultat (une exécution temps-réel et une localisation en permanence dans une tolérance de 10 cm autour de la trajectoire de référence). Le capteur extéroceptif choisi pour mener à bien ce projet est une caméra tandis que l'estimation de la pose du véhicule à chaque instant est réalisée par un ltre de Kalman dans sa version étendue. Les principaux problèmes d'estimation résident dans la non-linéarité des modèles d'observation et les contributions apportées apportent quelques solutions : - une méthode de calcul exacte de la propagation des incertitudes de l'espace monde vers l'espace capteur (caméra) ; - une méthode de détection des principaux cas de divergence du filtre de Kalman dans le calcul de la phase de mise à jour ; - une méthode de correction du gain de Kalman. Ce projet avait deux objectifs : réaliser une fonction de localisation répondant aux contraintes fortes préalablement évoquées, et permettre à un véhicule de quitter temporairement la trajectoire de référence, suite à la prise en main de l'opérateur pour ensuite reprendre le cours normale de sa mission au plus près de la trajectoire de référence. Ce deuxième volet fait intervenir un cadre plus large dans lequel il faut, en plus de la localisation, cartographier son environnement. Cette problématique, identifiée par l'acronyme SLAM (Simultaneous Localization And Mapping), fait le lien avec les deux dernières contributions de ces travaux de thèse : - une méthode d'initialisation des points qui constitueront la carte SLAM; - une méthode pour maintenir la cohérence entre la carte de référence et la carte SLAM. Des résultats sur des données réelles, étayant chacune des contributions, sont présentés et illustrent la réalisation des deux principaux objectifs.

Dans le cadre de la robotique mobile en environnement extérieur, les concepts de localisation et de perception sont au coeur de toute réalisation. Aussi, les travaux menés au sein de cette thèse visent à rendre plus robustes des processus de localisation existants sans pour autant augmenter de manière notable leur complexité. La problématique proposée place un robot au sein d'un environnement potentiellement dangereux avec pour objectif de suivre une trajectoire établie comme sécurisée avec une carte aussi simple que possible. De plus, des contraintes fortes sont imposées tant dans la réalisation (système peu onéreux, indétectable) que dans le résultat (une exécution temps-réel et une localisation en permanence dans une tolérance de 10 cm autour de la trajectoire de référence). Le capteur extéroceptif choisi pour mener à bien ce projet est une caméra tandis que l'estimation de la pose du véhicule à chaque instant est réalisée par un filtre de Kalman dans sa version étendue. Les principaux problèmes d'estimation résident dans la non-linéarité des modèles d'observation et les contributions apportées apportent quelques solutions : - une méthode de calcul exacte de la propagation des incertitudes de l'espace monde vers l'espace capteur (caméra) ; - une méthode de détection des principaux cas de divergence du filtre de Kalman dans le calcul de la phase de mise à jour ; - une méthode de correction du gain de Kalman. Ce projet avait deux objectifs : réaliser une fonction de localisation répondant aux contraintes fortes préalablement évoquées, et permettre à un véhicule de quitter temporairement la trajectoire de référence, suite à la prise en main de l'opérateur pour ensuite reprendre le cours normal de sa mission au plus près de la trajectoire de référence. Ce deuxième volet fait intervenir un cadre plus large dans lequel il faut, en plus de la localisation, cartographier son environnement. Cette problématique, identifiée par l'acronyme SLAM (Simultaneous Localization And Mapping), fait le lien avec les deux dernières contributions de ces travaux de thèse : - une méthode d'initialisation des points qui constitueront la carte SLAM ; - une méthode pour maintenir la cohérence entre la carte de référence et la carte SLAM. Des résultats sur des données réelles, étayant chacune des contributions, sont présentés et illustrent la réalisation des deux principaux objectifs.

This thesis work deals with the most actual topic in Computer Vision field which is scene understanding and this using matching of 3D feature point images. The objective is to make use of Saab’s latest breakthrough in extraction of 3D feature points, to identify the best alignment of at least two 3D feature point images. The thesis gives a theoretical overview of the latest algorithms used for feature detection, description and matching. The work continues with a brief description of the simultaneous localization and mapping (SLAM) technique, ending with a case study on evaluation of the newly developed software solution for SLAM, called slam6d. Slam6d is a tool that registers point clouds into a common coordinate system. It does an automatic high-accurate registration of the laser scans. In the case study the use of slam6d is extended in registering 3D feature point images extracted from a stereo camera and the results of registration are analyzed. In the case study we start with registration of one single 3D feature point image captured from stationary image sensor continuing with registration of multiple images following a trail. Finally the conclusion from the case study results is that slam6d can register non-laser scan extracted feature point images with high-accuracy in case of single image but it introduces some overlapping results in the case of multiple images following a trail.

Incremental smoothing and mapping (iSAM) is presented, a novel approach to the simultaneous localization and mapping (SLAM) problem. SLAM is the problem of estimating an observer's position from local measurements only, while creating a consistent map of the environment. The problem is difficult because even very small errors in the local measurements accumulate over time and lead to large global errors. iSAM provides an exact and efficient solution to the SLAM estimation problem while also addressing data association. For the estimation problem, iSAM provides an exact solution by performing smoothing, which keeps all previous poses as part of the estimation problem, and therefore avoids linearization errors. iSAM uses methods from sparse linear algebra to provide an efficient incremental solution. In particular, iSAM deploys a direct equation solver based on QR matrix factorization of the naturally sparse smoothing information matrix. Instead of refactoring the matrix whenever new measurements arrive, only the entries of the factor matrix that actually change are calculated. iSAM is efficient even for robot trajectories with many loops as it performs periodic variable reordering to avoid unnecessary fill-in in the factor matrix. For the data association problem, I present state of the art data association techniques in the context of iSAM and present an efficient algorithm to obtain the necessary estimation uncertainties in real-time based on the factored information matrix. I systematically evaluate the components of iSAM as well as the overall algorithm using various simulated and real-world data sets.

El modelat d'escenes és clau en un gran ventall d'aplicacions que van des de la generació mapes fins a la realitat augmentada. Aquesta tesis presenta una solució completa per a la creació de models 3D amb textura. En primer lloc es presenta un mètode de Structure from Motion seqüencial, a on el model 3D de l'entorn s'actualitza a mesura que s'adquireix nova informació visual. La proposta és més precisa i robusta que l'estat de l'art. També s'ha desenvolupat un mètode online, basat en visual bag-of-words, per a la detecció eficient de llaços. Essent una tècnica completament seqüencial i automàtica, permet la reducció de deriva, millorant la navegació i construcció de mapes. Per tal de construir mapes en àrees extenses, es proposa un algorisme de simplificació de models 3D, orientat a aplicacions online. L'eficiència de les propostes s'ha comparat amb altres mètodes utilitzant diversos conjunts de dades submarines i terrestres. / Scene modeling has a key role in applications ranging from visual mapping to augmented reality. This thesis presents an end-to-end solution for creating accurate, automatic 3D textured models, with contributions at different levels. First, we discuss a method developed within the framework of sequential Structure from Motion, where a 3D model of the environment is maintained and updated as visual information becomes available. The technique is more accurate and robust than state-of-the-art 3D modeling approaches. We also develop an online effcient loop-closure detection algorithm, allowing the reduction of drift and uncertainties for mapping and navigation. Inspired from visual bag-of-words, the technique is entirely sequential and automatic. Lastly, motivated by the need to map large areas, we propose a 3D model simplification oriented towards online applications. We discuss the efficiency of the proposals and compare them with state-of-the-art approaches, using a series of challenging datasets both in underwater and outdoor scenarios.

Thesis (MScEng)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Simultaneous localization and mapping (SLAM) is vital for autonomous robot navigation. The robot must build a map of its environment while tracking its own motion through that map. Although many solutions to this intricate problem have been proposed, one of the most prominent issues that still needs to be resolved is to accurately measure and track landmarks over time. In this thesis we investigate the use of stereo vision for this purpose. In order to find landmarks in images we explore the use of two feature detectors: the scale-invariant feature transform (SIFT) and speeded-up robust features (SURF). Both these algorithms find salient points in images and calculate a descriptor for each point that is invariant to scale, rotation and illumination. By using the descriptors we match these image features between stereo images and use the geometry of the system to calculate a set of 3D landmark measurements. A Taylor approximation of this transformation is used to derive a Gaussian noise model for the measurements. The measured landmarks are matched to landmarks in a map to find correspondences. We find that this process often incorrectly matches ambiguous landmarks. To find these mismatches we develop a novel outlier detection scheme based on the random sample consensus (RANSAC) framework. We use a similarity transformation for the RANSAC model and derive a probabilistic consensus measure that takes the uncertainties of landmark locations into account. Through simulation and practical tests we find that this method is a significant improvement on the standard approach of using the fundamental matrix. With accurately identified landmarks we are able to perform SLAM. We investigate the use of three popular SLAM algorithms: EKF SLAM, FastSLAM and FastSLAM 2. EKF SLAM uses a Gaussian distribution to describe the systems states and linearizes the motion and measurement equations with Taylor approximations. The two FastSLAM algorithms are based on the Rao-Blackwellized particle filter that uses particles to describe the robot states, and EKFs to estimate the landmark states. FastSLAM 2 uses a refinement process to decrease the size of the proposal distribution and in doing so decreases the number of particles needed for accurate SLAM. We test the three SLAM algorithms extensively in a simulation environment and find that all three are capable of very accurate results under the right circumstances. EKF SLAM displays extreme sensitivity to landmark mismatches. FastSLAM, on the other hand, is considerably more robust against landmark mismatches but is unable to describe the six-dimensional state vector required for 3D SLAM. FastSLAM 2 offers a good compromise between efficiency and accuracy, and performs well overall. In order to evaluate the complete system we test it with real world data. We find that our outlier detection algorithm is very effective and greatly increases the accuracy of the SLAM systems. We compare results obtained by all three SLAM systems, with both feature detection algorithms, against DGPS ground truth data and achieve accuracies comparable to other state-of-the-art systems. From our results we conclude that stereo vision is viable as a sensor for SLAM. / AFRIKAANSE OPSOMMING: Gelyktydige lokalisering en kartering (simultaneous localization and mapping, SLAM) is ’n noodsaaklike proses in outomatiese robot-navigasie. Die robot moet ’n kaart bou van sy omgewing en tegelykertyd sy eie beweging deur die kaart bepaal. Alhoewel daar baie oplossings vir hierdie ingewikkelde probleem bestaan, moet een belangrike saak nog opgelos word, naamlik om landmerke met verloop van tyd akkuraat op te spoor en te meet. In hierdie tesis ondersoek ons die moontlikheid om stereo-visie vir hierdie doel te gebruik. Ons ondersoek die gebruik van twee beeldkenmerk-onttrekkers: scale-invariant feature transform (SIFT) en speeded-up robust features (SURF). Altwee algoritmes vind toepaslike punte in beelde en bereken ’n beskrywer vir elke punt wat onveranderlik is ten opsigte van skaal, rotasie en beligting. Deur die beskrywer te gebruik, kan ons ooreenstemmende beeldkenmerke soek en die geometrie van die stelsel gebruik om ’n stel driedimensionele landmerkmetings te bereken. Ons gebruik ’n Taylor- benadering van hierdie transformasie om ’n Gaussiese ruis-model vir die metings te herlei. Die gemete landmerke se beskrywers word dan vergelyk met dié van landmerke in ’n kaart om ooreenkomste te vind. Hierdie proses maak egter dikwels foute. Om die foutiewe ooreenkomste op te spoor het ons ’n nuwe uitskieterherkenningsalgoritme ontwikkel wat gebaseer is op die RANSAC-raamwerk. Ons gebruik ’n gelykvormigheidstransformasie vir die RANSAC-model en lei ’n konsensusmate af wat die onsekerhede van die ligging van landmerke in ag neem. Met simulasie en praktiese toetse stel ons vas dat die metode ’n beduidende verbetering op die standaardprosedure, waar die fundamentele matriks gebruik word, is. Met ons akkuraat geïdentifiseerde landmerke kan ons dan SLAM uitvoer. Ons ondersoek die gebruik van drie SLAM-algoritmes: EKF SLAM, FastSLAM en FastSLAM 2. EKF SLAM gebruik ’n Gaussiese verspreiding om die stelseltoestande te beskryf en Taylor-benaderings om die bewegings- en meetvergelykings te lineariseer. Die twee FastSLAM-algoritmes is gebaseer op die Rao-Blackwell partikelfilter wat partikels gebruik om robottoestande te beskryf en EKF’s om die landmerktoestande af te skat. FastSLAM 2 gebruik ’n verfyningsproses om die grootte van die voorstelverspreiding te verminder en dus die aantal partikels wat vir akkurate SLAM benodig word, te verminder. Ons toets die drie SLAM-algoritmes deeglik in ’n simulasie-omgewing en vind dat al drie onder die regte omstandighede akkurate resultate kan behaal. EKF SLAM is egter baie sensitief vir foutiewe landmerkooreenkomste. FastSLAM is meer bestand daarteen, maar kan nie die sesdimensionele verspreiding wat vir 3D SLAM vereis word, beskryf nie. FastSLAM 2 bied ’n goeie kompromie tussen effektiwiteit en akkuraatheid, en presteer oor die algemeen goed. Ons toets die hele stelsel met werklike data om dit te evalueer, en vind dat ons uitskieterherkenningsalgoritme baie effektief is en die akkuraatheid van die SLAM-stelsels beduidend verbeter. Ons vergelyk resultate van die drie SLAM-stelsels met onafhanklike DGPS-data, wat as korrek beskou kan word, en behaal akkuraatheid wat vergelykbaar is met ander toonaangewende stelsels. Ons resultate lei tot die gevolgtrekking dat stereo-visie ’n lewensvatbare sensor vir SLAM is.

A ventosa de trÃplice funÃÃo atua na admissÃo e/ou expulsÃo de ar contido na tubulaÃÃo, protegendo tubulaÃÃo e equipamentos contra os efeitos decorrentes do acÃmulo de ar e golpe de arÃete. AtravÃs do orifÃcio cinÃtico, ela admite grande quantidade de ar quando a pressÃo no interior da tubulaÃÃo torna-se inferior à atmosfÃrica, e expulsa ar apÃs a separaÃÃo da coluna a uma pressÃo superior à atmosfÃrica. Na regiÃo de admissÃo de ar, a ventosa com orifÃcio âNon Slamâ admite grande volume de ar atravÃs do orifÃcio cinÃtico, e inicia a expulsÃo de ar, atravÃs do mesmo orifÃcio. A partir de um determinado valor de pressÃo positiva, o orifÃcio cinÃtico à fechado e abre-se um orifÃcio de menor diÃmetro, chamado de orifÃcio de "Non Slam", amortecendo, assim, o choque das colunas lÃquidas que estavam separadas. Neste trabalho, propÃe-se uma metodologia para o cÃlculo dos coeficientes de admissÃo e expulsÃo de ar no regime transiente a partir das curvas disponibilizadas pelos fabricantes. O trabalho visa minimizar a falta de informaÃÃes experimentais sobre as ventosas com base nas curvas dos fabricantes para a determinaÃÃo dos coeficientes de admissÃo e expulsÃo de ar. Nesse estudo nÃs comparamos o efeito de se usar um Ãnico coeficiente de descarga de ar para entrada e outro Ãnico para a saÃda de ar versus considerar a variaÃÃo desses coeficientes de descarga à medida que as pressÃes variam. O programa computacional UFC7, escrito em Java, implementa o transiente hidrÃulico com suas condiÃÃes de contorno. / sucker triple function acts on admission and / or expulsion of air in the pipe, protecting piping and equipment against the effects of air and accumulation water hammer. Through kinetic hole, she admits lot of air when the pressure inside the pipe becomes lower than atmospheric, and expels air after separation column at a superatmospheric pressure. The inlet region air, the suction orifice "Non slam" admits large volume of air through the orifice Kinetic and starts expelling air through the same hole. From a certain Positive pressure value, the kinetic orifice is closed and opens a lower orifice diameter hole called "Non slam", cushioning, thus, the shock of columns they were separated liquid. In this paper, we propose a methodology for calculating the admission rates and expulsion of air in transient from the curves provided by the manufacturers. The work aims to minimize the lack of information Experimental suction cups on the basis of the curves for the determination of makers the admission rates and expulsion of air. In this study we compared the effect of using a single air discharge coefficient for input and another for output only Air versus consider the variation of these coefficients discharge pressures as range. The UFC7 computer program written in Java, implements the transient Hydraulic with its boundary conditions

Mobile laser scanning systems automate the acquisition of 3D point clouds of environments. The mapping systems are commonly mounted on cars or ships. This paper presents a flexible mapping solution mounted on an underground vehicle that is able to map underground mines in 3D in walking speeds. A clever choice of hard- and software enables the system to generate 3D maps without using GPS (global positioning system) information and without relying on highly expensive IMU (inertial measurement unit) systems.

Cette thèse traite des problèmes de modélisation, reconnaissance, localisation et utilisation du contexte pour la manipulation d'objets par un robot. Le processus de modélisation se divise en quatre composantes : le système réel, les données capteurs, les propriétés à reproduire et le modèle. En spécifiant chacune des ces composantes, il est possible de définir un processus de modélisation adapté au problème présent, la manipulation d'objets par un robot. Cette analyse mène à l'adoption des descripteurs de texture locaux pour la modélisation. La modélisation basée sur des descripteurs de texture locaux a été abordé dans de nombreux travaux traitant de structure par le mouvement (SfM) ou de cartographie et localisation simultanée (SLAM). Les méthodes existantes incluent Bundler, Roboearth et 123DCatch. Pourtant, aucune de ces méthodes n'a recueilli le consensus. En effet, l'implémentation d'une approche similaire montre que ces outils sont difficiles d'utilisation même pour des utilisateurs experts et qu'ils produisent des modèles d'une haute complexité. Cette complexité est utile pour fournir un modèle robuste aux variations de point de vue. Il existe deux façons pour un modèle d'être robuste : avec le paradigme des vues multiple ou celui des descripteurs forts. Dans le paradigme des vues multiples, le modèle est construit à partir d'un grand nombre de points de vue de l'objet. Le paradigme des descripteurs forts compte sur des descripteurs résistants aux changements de points de vue. Les expériences réalisées montrent que des descripteurs forts permettent d'utiliser un faible nombre de vues, ce qui résulte en un modèle simple. Ces modèles simples n'incluent pas tout les point de vus existants mais les angles morts peuvent être compensés par le fait que le robot est mobile et peut adopter plusieurs points de vue. En se basant sur des modèles simples, il est possible de définir des méthodes de modélisation basées sur des images seules, qui peuvent être récupérées depuis Internet. A titre d'illustration, à partir d'un nom de produit, il est possible de récupérer des manières totalement automatiques des images depuis des magasins en ligne et de modéliser puis localiser les objets désirés. Même avec une modélisation plus simple, dans des cas réel ou de nombreux objets doivent être pris en compte, il se pose des problèmes de stockage et traitement d'une telle masse de données. Cela se décompose en un problème de complexité, il faut traiter de nombreux modèles rapidement, et un problème d'ambiguïté, des modèles peuvent se ressembler. L'impact de ces deux problèmes peut être réduit en utilisant l'information contextuelle. Le contexte est toute information non issue des l'objet lui même et qui aide a la reconnaissance. Ici deux types de contexte sont abordés : le lieu et les objets environnants. Certains objets se trouvent dans certains endroits particuliers. En connaissant ces liens lieu/objet, il est possible de réduire la liste des objets candidats pouvant apparaître dans un lieu donné. Par ailleurs l'apprentissage du lien lieu/objet peut être fait automatiquement par un robot en modélisant puis explorant un environnement. L'information appris peut alors être fusionnée avec l'information visuelle courante pour améliorer la reconnaissance. Dans les cas des objets environnants, un objet peut souvent apparaître au cotés d'autres objets, par exemple une souris et un clavier. En connaissant la fréquence d'apparition d'un objet avec d'autres objets, il est possible de réduire la liste des candidats lors de la reconnaissance. L'utilisation d'un Réseau de Markov Logique est particulièrement adaptée à la fusion de ce type de données. Cette thèse montre la synergie de la robotique et du contexte pour la modélisation, reconnaissance et localisation d'objets. / This Thesis addresses the modeling, recognition, localization and use of context for objects manipulation by a robot. We start by presenting the modeling process and its components: the real system, the sensors' data, the properties to reproduce and the model. We show how, by specifying each of them, one can define a modeling process adapted to the problem at hand, namely object manipulation by a robot. This analysis leads us to the adoption of local textured descriptors for object modeling. Modeling with local textured descriptors is not a new concept, it is the subject of many Structure from Motion (SfM) or Simultaneous Localization and Mapping (SLAM) works. Existing methods include bundler, roboearth modeler and 123DCatch. Still, no method has gained widespread adoption. By implementing a similar approach, we show that they are hard to use even for expert users and produce highly complex models. Such complex techniques are necessary to guaranty the robustness of the model to view point change. There are two ways to handle the problem: the multiple views paradigm and the robust features paradigm. The multiple views paradigm advocate in favor of using a large number of views of the object. The robust feature paradigm relies on robust features able to resist large view point changes. We present a set of experiments to provide an insight into the right balance between both. By varying the number of views and using different features we show that small and fast models can provide robustness to view point changes up to bounded blind spots which can be handled by robotic means. We propose four different methods to build simple models from images only, with as little a priori information as possible. The first one applies to planar or piecewise planar objects and relies on homographies for localization. The second approach is applicable to objects with simple geometry, such as cylinders or spheres, but requires many measures on the object. The third method requires the use of a calibrated 3D sensor but no additional information. The fourth technique doesn't need a priori information at all. We apply this last method to autonomous grocery objects modeling. From images automatically retrieved from a grocery store website, we build a model which allows recognition and localization for tracking. Even using light models, real situations ask for numerous object models to be stored and processed. This poses the problems of complexity, processing multiple models quickly, and ambiguity, distinguishing similar objects. We propose to solve both problems by using contextual information. Contextual information is any information helping the recognition which is not directly provided by sensors. We focus on two contextual cues: the place and the surrounding objects. Some objects are mainly found in some particular places. By knowing the current place, one can restrict the number of possible identities for a given object. We propose a method to autonomously explore a previously labeled environment and establish a correspondence between objects and places. Then this information can be used in a cascade combining simple visual descriptors and context. This experiment shows that, for some objects, recognition can be achieved with as few as two simple features and the location as context. The objects surrounding a given object can also be used as context. Objects like a keyboard, a mouse and a monitor are often close together. We use qualitative spatial descriptors to describe the position of objects with respect to their neighbors. Using a Markov Logic Network, we learn patterns in objects disposition. This information can then be used to recognize an object when surrounding objects are already identified. This Thesis stresses the good match between robotics, context and objects recognition.

Disertační práce se zabývá zpracováním mračenen bodů z laserových skenerů pomocí vektorizace a následnému vyhledávání korespondencí mezi takto získanými aproximacemi pro potřeby současné sebelokalizace a mapování v mobilní robotice. První nová metoda je určena pro segmentaci a filtraci surových dat a realizuje obě operace najednou v jednom algoritmu. Pro vektorizaci je představen optimalizovaný algoritmus založený na úplné metodě nejmenších čtverců, který je v současnosti patrně nejrychlejší ve své třídě a blíží se tak eliminačním metodám, které ovšem produkují výrazně horší aproxi- mace. Inovativní analytické metody jsou představeny i pro účely vyjádření podobnosti mezi dvěma vektorizovanými skeny, pro jejich optimální sesazení a pro vyhledávání korespondencí mezi nimi. Všechny představené algoritmy jsou intezivně testovány a jejich vlastnosti ověřeny množstvím experimentů.