De nombreux scanners laser permettent d'obtenir la surface 3D a partir d'un objet. Néanmoins, la surface reconstruite est souvent lisse, ce qui est du au débruitage interne du scanner et aux décalages entre les scans. Cette these utilise des scans haute precision et choisit de ne pas perdre ni alterer les echantillons initiaux au cours du traitement afin de les visualiser. C'est en effet la seule façon de decouvrir les imperfections (trous, decalages de scans). De plus, comme les donnees haute precision capturent meme le plus leger detail, tout debruitage ou sous-echantillonnage peut amener a perdre ces details.La these s'attache a prouver que l'on peut trianguler le nuage de point initial en ne perdant presque aucun echantillon. Le probleme de la visualisation exacte sur des donnees de plus de 35 millions de points et de 300 scans differents est ainsi resolu. Deux problemes majeurs sont traites: le premier est l'orientation du nuage de point brut complet et la creation d'un maillage. Le second est la correction des petits decalages entre les scans qui peuvent creer un tres fort aliasing et compromettre la visualisation de la surface. Le second developpement de la these est une decomposition des nuages de points en hautes/basses frequences. Ainsi, des methodes classiques pour l'analyse d'image, l'arbre des ensembles de niveau et la representation MSER, sont etendues aux maillages, ce qui donne une methode intrinseque de segmentation de maillages. Une analyse mathematiques d'operateurs differentiels discrets, proposes dans la litterature et operant sur des nuages de points est realisee. En considerant les developpements asymptotiques de ces operateurs sur une surface reguliere, ces operateurs peuvent etre classifies. Cette analyse amene au developpement d'un operateur discret consistant avec Ie mouvement par courbure moyenne (l'equation de la chaleur intrinseque) definissant ainsi un espace-echelle numerique simple et remarquablement robuste. Cet espace-echelle permet de resoudre de maniere unifiee tous les problemes mentionnes auparavant (orientation et triangulation du nuage de points, fusion de scans, segmentation de maillages) qui sont ordinairement traites avec des techniques distinctes. / Many laser devices acquire directly 3D objects and reconstruct their surface. Nevertheless, the final reconstructed surface is usually smoothed out as a result of the scanner internal de-noising process and the offsets between different scans. This thesis, working on results from high precision scans, adopts the somewhat extreme conservative position, not to loose or alter any raw sample throughout the whole processing pipeline, and to attempt to visualize them. Indeed, it is the only way to discover all surface imperfections (holes, offsets). Furthermore, since high precision data can capture the slightest surface variation, any smoothing and any sub-sampling can incur in the loss of textural detail.The thesis attempts to prove that one can triangulate the raw point cloud with almost no sample loss. It solves the exact visualization problem on large data sets of up to 35 million points made of 300 different scan sweeps and more. Two major problems are addressed. The first one is the orientation of the complete raw point set, an the building of a high precision mesh. The second one is the correction of the tiny scan misalignments which can cause strong high frequency aliasing and hamper completely a direct visualization.The second development of the thesis is a general low-high frequency decomposition algorithm for any point cloud. Thus classic image analysis tools, the level set tree and the MSER representations, are extended to meshes, yielding an intrinsic mesh segmentation method.The underlying mathematical development focuses on an analysis of a half dozen discrete differential operators acting on raw point clouds which have been proposed in the literature. By considering the asymptotic behavior of these operators on a smooth surface, a classification by their underlying curvature operators is obtained.This analysis leads to the development of a discrete operator consistent with the mean curvature motion (the intrinsic heat equation) defining a remarkably simple and robust numerical scale space. By this scale space all of the above mentioned problems (point set orientation, raw point set triangulation, scan merging, segmentation), usually addressed by separated techniques, are solved in a unified framework.

This document introduces a new class of adaptive filters, namely Geometric- Algebra Adaptive Filters (GAAFs). Those are generated by formulating the underlying minimization problem (a least-squares cost function) from the perspective of Geometric Algebra (GA), a comprehensive mathematical language well-suited for the description of geometric transformations. Also, differently from the usual linear algebra approach, Geometric Calculus (the extension of Geometric Algebra to differential calculus) allows to apply the same derivation techniques regardless of the type (subalgebra) of the data, i.e., real, complex-numbers, quaternions etc. Exploiting those characteristics, among others, a general leastsquares cost function is posed, from which two types of GAAFs are designed. The first one, called standard, provides a generalization of regular adaptive filters for any subalgebra of GA. From the obtained update rule, it is shown how to recover the following least-mean squares (LMS) adaptive filter variants: real-entries LMS, complex LMS, and quaternions LMS. Mean-square analysis and simulations in a system identification scenario are provided, showing almost perfect agreement for different levels of measurement noise. The second type, called pose estimation, is designed to estimate rigid transformations { rotation and translation - in n-dimensional spaces. The GA-LMS performance is assessed in a 3-dimensional registration problem, in which it is able to estimate the rigid transformation that aligns two point clouds that share common parts. / Este documento introduz uma nova classe de filtros adaptativos, entitulados Geometric-Algebra Adaptive Filters (GAAFs). Eles s~ao projetados via formulação do problema de minimização (uma função custo de mínimos quadrados) do ponto de vista de álgebra geométrica (GA), uma abrangente linguagem matemática apropriada para a descrição de transformações geométricas. Adicionalmente, diferente do que ocorre na formulação com álgebra linear, cálculo geométrico (a extensão de álgebra geométrica que possibilita o uso de cálculo diferencial) permite aplicar as mesmas técnicas de derivação independentemente do tipo de dados (subálgebra), isto é, números reais, números complexos, quaternions etc. Usando essas e outras características, uma função custo geral de mínimos quadrados é proposta, da qual dois tipos de GAAFs são gerados. O primeiro, chamado standard, generaliza filtros adaptativos da literatura concebidos sob a perspectiva de subálgebras de GA. As seguintes variantes do filtro least-mean squares (LMS) s~ao obtidas como casos particulares: LMS real, LMS complexo e LMS quaternions. Uma análise mean-square é desenvolvida e corroborada por simulações para diferentes níveis de ruído de medição em um cenário de identificação de sistemas. O segundo tipo, chamado pose estimation, é projetado para estimar transformações rígidas - rotação e translação { em espaços n-dimensionais. A performance do filtro GA-LMS é avaliada em uma aplicação de alinhamento tridimensional na qual ele estima a tranformação rígida que alinha duas nuvens de pontos com partes em comum.

Na robótica, mapear o ambiente é tarefa importante, porque ela oferece informação para o planejamento e execução de movimentos do robô. Por este motivo, aqui são apresentados estudos que visam a construção de mapas 3-D e técnicas que auxiliam na tarefa de mapeamento. Quando são construídos mapas 3-D, é habilitado para outros pesquisadores e empresas de robótica a desenvolverem trabalhos de análise e planejamento de trajetórias em todos os seis graus de liberdade do corpo rígido que serve para modelar um robô móvel, robô manipulador ou robô móvel manipulador. Com uma representação do ambiente em 3-D, é aumentada a precisão do posicionamento do robô em relação ao ambiente e também o posicionamento de objetos que estão inseridos no campo de atuação do robô. Para solucionar o problema de mapeamento são apresentadas técnicas teóricas e suas aplicações em cada caso estudado. Nos experimentos realizados neste trabalho foi adotada a criação de mapas com grids (malhas) de ocupação. Vale lembrar, no entanto, que a construção de mapas por malhas de ocupação pressupõe o conhecimento do posicionamento do robô no ambiente. Neste trabalho foram conduzidos três experimentos e seus objetivos são redução de dados provenientes de falhas e redundâncias de informação com utilização de técnicas probabilísticas, detecção de movimento através da técnica de extração de fundo e mapeamento 3-D utilizando a técnica de ponto mais próximo. No experimento cujo o objetivo é reduzir os dados, foi possível reduzir para 4,43% a quantidade de pontos necessários para gerar a representação do ambiente com a utilização do algoritmo deste trabalho. O algoritmo de mapeamento 3-D feito com uso de modelos probabilísticos bem estabelecidos e disponíveis na literatura tem como base a probabilidade de eventos independentes e a proposta do trabalho envolvendo probabilidade a posteriori. O experimento de detecção de movimento foi gerado com a utilização da openCV e a tecnologia CUDA e utilizam a técnica do modelo de mistura gaussiana (GMM), foi analisado o tempo de processamento desempenhado por cada implementação e a qualidade do resultado obtido. Para obter uma representação precisa do ambiente foi conduzido o experimento que utiliza técnica iterativa do ponto mais próximo (ICP), para realização foi utilizado o sensor de movimento Kinect e os resultados apresentados não foram satisfatórios devido ao volume de dados adquiridos e a ausência de um sistema de estimativa da localização. / In robotics, map the environment is an important task, because it provides information for planning and executing movements of the robot. For this reason, studies presented here are aimed to build 3-D maps and techniques that aid in the task of mapping. When we build 3-D maps, we enable other researchers and robotics companies to develop analyzes and path planning in all six degrees of freedom rigid body that serves to model a mobile robot, manipulator or mobile robot manipulator.With a representation of the environment in 3-D, we increase the accuracy of the robot positioning in relation to the environment and also the positioning of objects that are inserted into the field of action of the robot. To solve the problem of mapping we presented theoretical techniques and their applications in each case studied.In the experiments in this work we adopted the creation of maps with grids of occupation. However, building grids of occupation assumes knowledge of the position of the robot on the environment.In this work we conducted three experiments and their aims are the reduction of data from failures and redundant information using probabilistic techniques, motion detection by background extraction technique and 3-D mapping technique using the closest point. In the experiment whose goal is to reduce the data has been further reduced to 4.43% the number of points required to generate the representation of the environment with the use of our algorithm.The algorithm of 3-D mapping done with probabilistic models available and well established in the literature is based on the probability of independent events and the proposed work involving the posterior probability.The motion detection experiment was performed with the use of openCV and CUDA technique using the Gaussian mixture model (GMM),and we analyzed the processing time and the quality of each implementation result.For an accurate representation of the environment was conducted the experiment using the technique of iterative closest point (ICP) was used to perform the motion sensor Kinect and the results were not satisfactory due to the volume of data acquired and the absence of a system location estimate.

O emprego de veículos terrestres autônomos tem se tornado cada vez mais comum nos últimos anos em aplicações civis e militares. Eles podem ser úteis para as pessoas com necessidades especiais e para reduzir os acidentes de trânsito e o número de baixas em combate. Esta tese aborda o problema da classificação de obstáculos e da localização do veículo em relação a um mapa topológico, sem fazer uso de GPS e de mapas digitais detalhados. Um sensor laser 3D é usado para coletar dados do ambiente. O sistema de classificação de obstáculos extrai as features da nuvem de pontos e usam-nas para alimentar um classificador que separa os dados em quatro classes: veículos, pessoas, construções, troncos de árvores e postes. Durante a extração de features, um método original para transformar uma nuvem 3D em um grid 2D é proposto, o que ajuda a reduzir o tempo de processamento. As interseções de vias de áreas urbanas são detectadas e usadas como landmarks em um mapa topológico. O sistema consegue obter a localização do veículo, utilizando os pontos de referência, e identifica as mudanças de direção do veículo quando este passa pelos cruzamentos. Os experimentos demonstraram que o sistema foi capaz de classificar corretamente os obstáculos e localizar-se sem o uso de sinais de GPS. / The employment of autonomous ground vehicles, both in civilian and military applications, has become increasingly common over the past few years. Those vehicles can be helpful for disabled people and also to reduce traffic accidents. In this thesis, approaches to the problem of obstacles classification and the localization of the vehicle in relation to a topologic map are presented. GPS devices and previous digital maps are not employed. A 3D laser sensor is used to collect data from the environment. The obstacle classification system extracts features from point clouds and uses them to feed a classifier which separates data into four classes: vehicle, people, building and light poles/ trees. During the feature extraction, an original method to transform 3D to 2D data is proposed, which helps to reduce the processing time. Crossing roads are detected and used as landmarks in a topological map. The vehicle performs self-localization using the landmarks and identifying direction changes through the crossing roads. Experiments demonstrated that system was able to correctly classify obstacles and to localize itself without using GPS signals.

This document introduces a new class of adaptive filters, namely Geometric- Algebra Adaptive Filters (GAAFs). Those are generated by formulating the underlying minimization problem (a least-squares cost function) from the perspective of Geometric Algebra (GA), a comprehensive mathematical language well-suited for the description of geometric transformations. Also, differently from the usual linear algebra approach, Geometric Calculus (the extension of Geometric Algebra to differential calculus) allows to apply the same derivation techniques regardless of the type (subalgebra) of the data, i.e., real, complex-numbers, quaternions etc. Exploiting those characteristics, among others, a general leastsquares cost function is posed, from which two types of GAAFs are designed. The first one, called standard, provides a generalization of regular adaptive filters for any subalgebra of GA. From the obtained update rule, it is shown how to recover the following least-mean squares (LMS) adaptive filter variants: real-entries LMS, complex LMS, and quaternions LMS. Mean-square analysis and simulations in a system identification scenario are provided, showing almost perfect agreement for different levels of measurement noise. The second type, called pose estimation, is designed to estimate rigid transformations { rotation and translation - in n-dimensional spaces. The GA-LMS performance is assessed in a 3-dimensional registration problem, in which it is able to estimate the rigid transformation that aligns two point clouds that share common parts. / Este documento introduz uma nova classe de filtros adaptativos, entitulados Geometric-Algebra Adaptive Filters (GAAFs). Eles s~ao projetados via formulação do problema de minimização (uma função custo de mínimos quadrados) do ponto de vista de álgebra geométrica (GA), uma abrangente linguagem matemática apropriada para a descrição de transformações geométricas. Adicionalmente, diferente do que ocorre na formulação com álgebra linear, cálculo geométrico (a extensão de álgebra geométrica que possibilita o uso de cálculo diferencial) permite aplicar as mesmas técnicas de derivação independentemente do tipo de dados (subálgebra), isto é, números reais, números complexos, quaternions etc. Usando essas e outras características, uma função custo geral de mínimos quadrados é proposta, da qual dois tipos de GAAFs são gerados. O primeiro, chamado standard, generaliza filtros adaptativos da literatura concebidos sob a perspectiva de subálgebras de GA. As seguintes variantes do filtro least-mean squares (LMS) s~ao obtidas como casos particulares: LMS real, LMS complexo e LMS quaternions. Uma análise mean-square é desenvolvida e corroborada por simulações para diferentes níveis de ruído de medição em um cenário de identificação de sistemas. O segundo tipo, chamado pose estimation, é projetado para estimar transformações rígidas - rotação e translação { em espaços n-dimensionais. A performance do filtro GA-LMS é avaliada em uma aplicação de alinhamento tridimensional na qual ele estima a tranformação rígida que alinha duas nuvens de pontos com partes em comum.

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.

Na robótica, mapear o ambiente é tarefa importante, porque ela oferece informação para o planejamento e execução de movimentos do robô. Por este motivo, aqui são apresentados estudos que visam a construção de mapas 3-D e técnicas que auxiliam na tarefa de mapeamento. Quando são construídos mapas 3-D, é habilitado para outros pesquisadores e empresas de robótica a desenvolverem trabalhos de análise e planejamento de trajetórias em todos os seis graus de liberdade do corpo rígido que serve para modelar um robô móvel, robô manipulador ou robô móvel manipulador. Com uma representação do ambiente em 3-D, é aumentada a precisão do posicionamento do robô em relação ao ambiente e também o posicionamento de objetos que estão inseridos no campo de atuação do robô. Para solucionar o problema de mapeamento são apresentadas técnicas teóricas e suas aplicações em cada caso estudado. Nos experimentos realizados neste trabalho foi adotada a criação de mapas com grids (malhas) de ocupação. Vale lembrar, no entanto, que a construção de mapas por malhas de ocupação pressupõe o conhecimento do posicionamento do robô no ambiente. Neste trabalho foram conduzidos três experimentos e seus objetivos são redução de dados provenientes de falhas e redundâncias de informação com utilização de técnicas probabilísticas, detecção de movimento através da técnica de extração de fundo e mapeamento 3-D utilizando a técnica de ponto mais próximo. No experimento cujo o objetivo é reduzir os dados, foi possível reduzir para 4,43% a quantidade de pontos necessários para gerar a representação do ambiente com a utilização do algoritmo deste trabalho. O algoritmo de mapeamento 3-D feito com uso de modelos probabilísticos bem estabelecidos e disponíveis na literatura tem como base a probabilidade de eventos independentes e a proposta do trabalho envolvendo probabilidade a posteriori. O experimento de detecção de movimento foi gerado com a utilização da openCV e a tecnologia CUDA e utilizam a técnica do modelo de mistura gaussiana (GMM), foi analisado o tempo de processamento desempenhado por cada implementação e a qualidade do resultado obtido. Para obter uma representação precisa do ambiente foi conduzido o experimento que utiliza técnica iterativa do ponto mais próximo (ICP), para realização foi utilizado o sensor de movimento Kinect e os resultados apresentados não foram satisfatórios devido ao volume de dados adquiridos e a ausência de um sistema de estimativa da localização. / In robotics, map the environment is an important task, because it provides information for planning and executing movements of the robot. For this reason, studies presented here are aimed to build 3-D maps and techniques that aid in the task of mapping. When we build 3-D maps, we enable other researchers and robotics companies to develop analyzes and path planning in all six degrees of freedom rigid body that serves to model a mobile robot, manipulator or mobile robot manipulator.With a representation of the environment in 3-D, we increase the accuracy of the robot positioning in relation to the environment and also the positioning of objects that are inserted into the field of action of the robot. To solve the problem of mapping we presented theoretical techniques and their applications in each case studied.In the experiments in this work we adopted the creation of maps with grids of occupation. However, building grids of occupation assumes knowledge of the position of the robot on the environment.In this work we conducted three experiments and their aims are the reduction of data from failures and redundant information using probabilistic techniques, motion detection by background extraction technique and 3-D mapping technique using the closest point. In the experiment whose goal is to reduce the data has been further reduced to 4.43% the number of points required to generate the representation of the environment with the use of our algorithm.The algorithm of 3-D mapping done with probabilistic models available and well established in the literature is based on the probability of independent events and the proposed work involving the posterior probability.The motion detection experiment was performed with the use of openCV and CUDA technique using the Gaussian mixture model (GMM),and we analyzed the processing time and the quality of each implementation result.For an accurate representation of the environment was conducted the experiment using the technique of iterative closest point (ICP) was used to perform the motion sensor Kinect and the results were not satisfactory due to the volume of data acquired and the absence of a system location estimate.

La création d'une maquette numérique d'un bâtiment existant nécessite le relevé du bâtiment. Le scanner laser terrestre est largement utilisé pour atteindre cet objectif. Il permet d'obtenir la géométrie des objets sous forme de nuages de points. Il fournit une grande quantité de données précises de manière très rapide et avec un niveau élevé de détails. Malheureusement, le passage du nuage de points à la maquette numérique reste actuellement largement manuel en raison du volume important de données et des processus qui sont difficiles à automatiser. Cette démarche est chronophage et source d'erreurs. Un défi majeur aujourd'hui est donc d'automatiser le processus menant à la reconstruction 3D de bâtiments existants à partir de nuages de points. L'objectif de cette thèse est de développer une chaîne de traitements permettant d'extraire automatiquement le maximum d'informations du nuage de points d'un bâtiment en vue d'intégrer le résultat dans un logiciel de BIM. / The creation of an as-built BIM requires the acquisition of the as-is conditions of existing buildings. Terrestrial laser scanning (TLS) is widely used to achieve this goal. Indeed, laser scanners permit to collect information about object geometry in form of point clouds. They provide a large amount of accurate data in a very fast way and with a high level of details. Unfortunately, the scan-to-BIM process remains currently largely a manual process because of the huge amount of data and because of processes, which are difficult to automate. It is time consuming and error-prone. A key challenge today is thus to automate the process leading to 3D reconstruction of existing buildings from point clouds. The aim of this thesis is to develop a processing chain to extract the maximum amount of information from a building point cloud in order to integrate the result in a BIM software.

O emprego de veículos terrestres autônomos tem se tornado cada vez mais comum nos últimos anos em aplicações civis e militares. Eles podem ser úteis para as pessoas com necessidades especiais e para reduzir os acidentes de trânsito e o número de baixas em combate. Esta tese aborda o problema da classificação de obstáculos e da localização do veículo em relação a um mapa topológico, sem fazer uso de GPS e de mapas digitais detalhados. Um sensor laser 3D é usado para coletar dados do ambiente. O sistema de classificação de obstáculos extrai as features da nuvem de pontos e usam-nas para alimentar um classificador que separa os dados em quatro classes: veículos, pessoas, construções, troncos de árvores e postes. Durante a extração de features, um método original para transformar uma nuvem 3D em um grid 2D é proposto, o que ajuda a reduzir o tempo de processamento. As interseções de vias de áreas urbanas são detectadas e usadas como landmarks em um mapa topológico. O sistema consegue obter a localização do veículo, utilizando os pontos de referência, e identifica as mudanças de direção do veículo quando este passa pelos cruzamentos. Os experimentos demonstraram que o sistema foi capaz de classificar corretamente os obstáculos e localizar-se sem o uso de sinais de GPS. / The employment of autonomous ground vehicles, both in civilian and military applications, has become increasingly common over the past few years. Those vehicles can be helpful for disabled people and also to reduce traffic accidents. In this thesis, approaches to the problem of obstacles classification and the localization of the vehicle in relation to a topologic map are presented. GPS devices and previous digital maps are not employed. A 3D laser sensor is used to collect data from the environment. The obstacle classification system extracts features from point clouds and uses them to feed a classifier which separates data into four classes: vehicle, people, building and light poles/ trees. During the feature extraction, an original method to transform 3D to 2D data is proposed, which helps to reduce the processing time. Crossing roads are detected and used as landmarks in a topological map. The vehicle performs self-localization using the landmarks and identifying direction changes through the crossing roads. Experiments demonstrated that system was able to correctly classify obstacles and to localize itself without using GPS signals.

La numérisation 3D du patrimoine bâti est un procédé qui s’inscrit dans de multiples applications (documentation, visualisation, etc.), et peut tirer profit de la diversité des techniques de mesure disponibles. Afin d’améliorer la complétude et la qualité des livrables, de plus en plus de projets de numérisation s’appuient sur la combinaison de nuages de points provenant de différentes sources. La connaissance des performances propres aux différents capteurs, ainsi que de la qualité de leurs mesures, est alors souhaitable. Par la suite, plusieurs pistes peuvent être explorées en vue d’intégrer des nuages hétérogènes au sein d’un même projet, de leur recalage à la modélisation finale. Une approche pour le recalage simultané de plusieurs nuages de points est exposée dans ces travaux. La gestion de potentielles fautes parmi les observations, ou de bruit de mesure inhérent à certaines techniques de levé, est envisagée à travers l’ajout d’estimateurs robustes dans la méthodologie de recalage. / Three dimensional digitization of built heritage is involved in a wide range of applications (documentation, visualization, etc.), and may take advantage of the diversity of measurement techniques available. In order to improve the completeness as well as the quality of deliverables, more and more digitization projects rely on the combination of data coming from different sensors. To this end, the knowledge of sensor performances along with the quality of the measurements they produce is recommended. Then, different solutions can be investigated to integrate heterogeneous point clouds within a same project, from their registration to the modeling steps. A global approach for the simultaneous registration of multiple point clouds is proposed in this work, where the introduction of individual weights for each dataset is foreseen. Moreover, robust estimators are introduced in the registration framework, in order to deal with potential outliers or measurement noise among the data.