The ability of a robot to navigate itself in the environment is a crucial step towards its autonomy. Navigation as a subtask of the development of autonomous robots is the subject of this thesis, focusing on the development of a method for simultaneous localization an mapping (SLAM) of mobile robots in six degrees of freedom (DOF). As a part of this research, a platform for 3D range data acquisition based on a continuously inclined laser rangefinder was developed. This platform is presented, evaluating the measurements and also presenting the robotic equipment on which the platform can be fitted. The localization and mapping task is equal to the registration of multiple 3D images into a common frame of reference. For this purpose, a method based on the Iterative Closest Point (ICP) algorithm was developed. First, the originally implemented SLAM method is presented, focusing on the time-wise performance and the registration quality issues introduced by the implemented algorithms. In order to accelerate and improve the quality of the time-demanding 6DOF image registration, an extended method was developed. The major extension is the introduction of a factorized registration, extracting 2D representations of vertical objects called leveled maps from the 3D point sets, ensuring these representations are 3DOF invariant. The extracted representations are registered in 3DOF using ICP algorithm, allowing pre-alignment of the 3D data for the subsequent robust 6DOF ICP based registration. The extended method is presented, showing all important modifications to the original method. The developed registration method was evaluated using real 3D data acquired in different indoor environments, examining the benefits of the factorization and other extensions as well as the performance of the original ICP based method. The factorization gives promising results compared to a single phase 6DOF registration in vertically structured environments. Also, the disadvantages of the method are discussed, proposing possible solutions. Finally, the future prospects of the research are presented.

Les avancées technologiques dans le domaine informatique (logiciel et matériel) et, en particulier, de la géolocalisation ont permis la démocratisation des modèles numériques. L'arrivée depuis quelques années de véhicules de cartographie mobile a ouvert l'accès à la numérisation 3D mobile terrestre. L'un des avantages de ces nouvelles méthodes d'imagerie de l'environnement urbain est la capacité potentielle de ces systèmes à améliorer les bases de données existantes 2D comme 3D, en particulier leur niveau de détail et la diversité des objets représentés. Les bases de données géographiques sont constituées d'un ensemble de primitives géométriques (généralement des lignes en 2D et des plans ou des triangles en 3D) d'un niveau de détail grossier mais ont l'avantage d'être disponibles sur de vastes zones géographiques. Elles sont issues de la fusion d'informations diverses (anciennes campagnes réalisées manuellement, conception automatisée ou encore hybride) et peuvent donc présenter des erreurs de fabrication. Les systèmes de numérisation mobiles, eux, peuvent acquérir, entre autres, des nuages de points laser. Ces nuages laser garantissent des données d'un niveau de détail très fin pouvant aller jusqu'à plusieurs points au centimètre carré. Acquérir des nuages de points laser présente toutefois des inconvénients :- une quantité de données importante sur de faibles étendues géographiques posant des problèmes de stockage et de traitements pouvant aller jusqu'à plusieurs Téraoctet lors de campagnes d'acquisition importantes- des difficultés d'acquisition inhérentes au fait d'imager l'environnement depuis le sol. Les systèmes de numérisation mobiles présentent eux aussi des limites : en milieu urbain, le signal GPS nécessaire au bon géoréférencement des données peut être perturbé par les multi-trajets voire même stoppé lors de phénomènes de masquage GPS liés à la réduction de la portion de ciel visible pour capter assez de satellites pour en déduire une position spatiale. Améliorer les bases de données existantes grâce aux données acquises par un véhicule de numérisation mobile nécessite une mise en cohérence des deux ensembles. L'objectif principal de ce manuscrit est donc de mettre en place une chaîne de traitements automatique permettant de recaler bases de données géographiques et nuages de points laser terrestre (provenant de véhicules de cartographies mobiles) de la manière la plus fiable possible. Le recalage peut se réaliser de manière différentes. Dans ce manuscrit, nous avons développé une méthode permettant de recaler des nuages laser sur des bases de données, notamment, par la définition d'un modèle de dérive particulièrement adapté aux dérives non-linéaires de ces données mobiles. Nous avons également développé une méthode capable d'utiliser de l'information sémantique pour recaler des bases de données sur des nuages laser mobiles. Les différentes optimisations effectuées sur notre approche nous permettent de recaler des données rapidement pour une approche post-traitements, ce qui permet d'ouvrir l'approche à la gestion de grands volumes de données (milliards de points laser et milliers de primitives géométriques).Le problème du recalage conjoint a été abordé. Notre chaîne de traitements a été testée sur des données simulées et des données réelles provenant de différentes missions effectuées par l'IGN / Technological advances in computer science (software and hardware) and particularly, GPS localization made digital models accessible to all people. In recent years, mobile mapping systems has enabled large scale mobile 3D scanning. One advantage of this technology for the urban environment is the potential ability to improve existing 2D or 3D database, especially their level of detail and variety of represented objects. Geographic database consist of a set of geometric primitives (generally 2D lines and plans or triangles in 3D) with a coarse level of detail but with the advantage of being available over wide geographical areas. They come from the fusion of various information (old campaigns performed manually, automated or hybrid design) wich may lead to manufacturing errors. The mobile mapping systems can acquire laser point clouds. These point clouds guarantee a fine level of detail up to more than one points per square centimeter. But there are some disavantages :- a large amount of data on small geographic areas that may cause problems for storage and treatment of up to several Terabyte during major acquisition,- the inherent acquisition difficulties to image the environment from the ground. In urban areas, the GPS signal required for proper georeferencing data can be disturbed by multipath or even stopped when GPS masking phenomena related to the reduction of the portion of the visible sky to capture enough satellites to find a good localization. Improve existing databases through these dataset acquired by a mobile mapping system requires alignment of these two sets. The main objective of this manuscript is to establish a pipeline of automatic processes to register these datasets together in the most reliable manner. Co-registration this data can be done in different ways. In this manuscript we have focused our work on the registration of mobile laser point cloud on geographical database by using a drift model suitable for the non rigid drift of these kind of mobile data. We have also developped a method to register geographical database containing semantics on mobile point cloud. The different optimization step performed on our methods allows to register the data fast enough for post-processing pipeline, which allows the management of large volumes of data (billions of laser points and thousands geometric primitives). We have also discussed on the problem of joint deformation. Our methods have been tested on simulated data and real data from different mission performed by IGN

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-06-07T15:41:47Z No. of bitstreams: 1 lucianowalentyxaviercejnog.pdf: 14234810 bytes, checksum: 492ebb7393b5f0e7cfc6e822067fe492 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-24T13:12:44Z (GMT) No. of bitstreams: 1 lucianowalentyxaviercejnog.pdf: 14234810 bytes, checksum: 492ebb7393b5f0e7cfc6e822067fe492 (MD5) / Made available in DSpace on 2017-06-24T13:12:44Z (GMT). No. of bitstreams: 1 lucianowalentyxaviercejnog.pdf: 14234810 bytes, checksum: 492ebb7393b5f0e7cfc6e822067fe492 (MD5) Previous issue date: 2015-09-21 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho visa melhorar um método clássico para o problema de registro rígido, o ICP (iterative Closest Point), fazendo com que a busca dos pontos mais próximos, uma de suas fases principais, considere informações aproximadas da geometria local de cada ponto combinadas à distância Euclidiana originalmente usada. Para isso é necessária uma etapa de pré-processamento, na qual a geometria local é estimada em tensores de orientação de segunda ordem. É definido o CTSF, um fator de similaridade entre tensores. O ICP é alterado de modo a considerar uma combinação linear do CTSF com a distância Euclidiana para estabelecer correspondências entre duas nuvens de pontos, variando os pesos relativos entre os dois fatores. Isso proporciona uma capacidade maior de convergência para ângulos maiores em relação ao ICP original, tornando o método comparável aos que constituem o estado da arte da área. Para comprovar o ganho obtido, foram realizados testes exaustivos em malhas com características geométricas variadas, para diferentes níveis de ruído aditivo, outliers e em casos de sobreposição parcial, variando os parâmetros do método de estimativa dos tensores. Foi definida uma nova base com malhas sintéticas para os experimentos, bem como um protocolo estatístico de avaliação quantitativa. Nos resultados, a avaliação foi feita de modo a determinar bons valores de parâmetros para malhas com diferentes características, e de que modo os parâmetros afetam a qualidade do método em situações com ruído aditivo, outliers, e sobreposição parcial. / This work aims to enhance a classic method for the rigid registration problem, the ICP (Iterative Closest Point), modifying one of its main steps, the closest point search, in order to consider approximated information of local geometry combined to the Euclidean distance, originally used. For this, a preprocessing stage is applied, in which the local geometry is estimated in second-order orientation tensors. We define the CTSF, a similarity factor between tensors. Our method uses a linear combination between this factor and the Euclidean distance, in order to establish correspondences, and a strategy of weight variation between both factors. This increases the convergence probability for higher angles with respect to the original ICP, making our method comparable to some of the state-of-art techniques. In order to comprove the enhancement, exhaustive tests were made in point clouds with different geometric features, with variable levels of additive noise and outliers and in partial overlapping situations, varying also the parameters of the tensor estimative method. A dataset of synthetic point clouds was defined for the experiments, as well as a statistic protocol for quantitative evaluation. The results were analyzed in order to highlight good parameter ranges for different point clouds, and how these parameters affect the behavior of the method in situations of additive noise, outliers and partial overlapping.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-06-07T17:49:03Z No. of bitstreams: 1 fernandoakiodearaujoyamada.pdf: 21095203 bytes, checksum: 1842e801a538bdeef0368c963b9d98b7 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-24T13:47:22Z (GMT) No. of bitstreams: 1 fernandoakiodearaujoyamada.pdf: 21095203 bytes, checksum: 1842e801a538bdeef0368c963b9d98b7 (MD5) / Made available in DSpace on 2017-06-24T13:47:22Z (GMT). No. of bitstreams: 1 fernandoakiodearaujoyamada.pdf: 21095203 bytes, checksum: 1842e801a538bdeef0368c963b9d98b7 (MD5) Previous issue date: 2016-03-15 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / No problema de registro rígido por pares é preciso encontrar uma transformação rígida que alinha duas nuvens de pontos. A sulução clássica e mais comum é o algoritmo Iterative Closest Point (ICP). No entanto, o ICP e muitas de suas variantes requerem que as nuvens de pontos já estejam grosseiramente alinhadas. Este trabalho apresenta um método denominado Shape-based Weighting Covariance Iterative Closest Point (SWC-ICP), uma melhoria do ICP clássico. A abordagem proposta aumenta a possibilidade de alinhar corretamente duas nuvens de pontos, independente da pose inicial, mesmo quando existe apenas sobreposição parcial entre elas, ou na presença de ruído e outliers. Ela se beneficia da geometria local dos pontos, codificada em tensores de orientação de segunda ordem, para prover um segundo conjunto de correspondências para o ICP. A matriz de covariância cruzada computada a partir deste conjunto é combinada com a matriz de covariância cruzada usual, seguindo uma estratégia heurística. Para comparar o método proposto com algumas abordagens recentes, um protocolo de avaliação detalhado para registro rígido é apresentado. Os resultados mostram que o SWC-ICP está entre os melhores métodos comparados, com performance superior em situações de grande deslocamento angular, mesmo na presença de ruído e outliers. / In the pairwise rigid registration problem we need to find a rigid transformation that aligns two point clouds. The classical and most common solution is the Iterative Closest Point (ICP) algorithm. However, the ICP and many of its variants require that the point clouds are already coarsely aligned. We present in this work a method named Shape-based Weighting Covariance Iterative Closest Point (SWC-ICP), an improvement over the classical ICP. Our approach improves the possibility to correctly align two point clouds, regardless of the initial pose, even when there is only a partial overlapping between them, or in the presence of noise and outliers. It benefits from the local geometry of the points, encoded in second-order orientation tensors, to provide a second correspondences set to the ICP. The cross-covariance matrix computed from this set is combined with the usual cross-covariance matrix following a heuristic strategy. In order to compare our method with some recent approaches, we present a detailed evaluation protocol to rigid registration. Results show that the SWC-ICP is among the best methods compared, with superior performance in situations of wide angular displacement, even in situations of noise and outliers.

The Iterative Closest Point (ICP) algorithm has been an extremely popular method for 3D points or surface registration. Given two point sets, it simultaneously solves for correspondences and estimates the motion between these two point sets. However, by only registering two such views at a time, ICP fails to exploit the redundant information available in multiple views that have overlapping regions. In this thesis, a multiview extension of the ICP algorithm is provided that simultaneously averages the redundant information available in the views with overlapping regions. Variants of this method that carry out such simultaneous registration in a causal manner and that utilize the transitivity property of point correspondences are also provided. The improved accuracy in registration of these motion averaged approaches in comparison with the conventional ICP method is established through extensive experiments. In addition, the motion averaged approaches are compared with the existing multiview techniques of Bergevin et. al. and Benjemaa et. al. The results of the methods applied to the Happy Buddha and the Stanford Bunny datasets of 3D Stanford repository and to the Pooh and the Bunny datasets of the Ohio (MSU/WSU) Range Image database are also presented.

Point cloud registration is a technique to align two sets of points with manifold applications across a range of industries. However, due to a lack of adequate sensing technology, this technique has seldom found applications in the automotive sector up to now. With the advent of solid-state Light Detection and Ranging (LiDAR) sensors that are easily integrable in series production vehicles as means to sense the surrounding environment, this technique can be functional to automate their operations. Maneuvering a vehicle in the proximity of a reference object is one such operation, which can only be performed by accurately estimating its position and orientation relative to the vehicle itself. This project deals with the design and the implementation of an algorithm to accurately locate an aircraft parked on an airfield apron in real time. This is achieved by registering the point cloud model of the plane to the measurement point cloud of the scene produced by the LiDAR sensors on board the vehicle. To this end, the Iterative Closest Point (ICP) algorithm is a well-established approach to register two sets of points without prior knowledge of the correspondences between pairs of points, which, however, is notoriously sensitive towards outliers and computationally expensive with large point clouds. In this work, different variants are presented that improve on the standard ICP algorithm, in terms of accuracy and runtime performance, by leveraging different data structures to index the reference model and outlier rejection strategies. The results show that the implemented algorithms can produce estimates of centimeter precision in milliseconds based only on partial observations of the aircraft, outperforming another established solution tested. / Punktmolnregistrering är en teknik för att anpassa två uppsättningar punkter med mångfaldiga applikationer inom en rad branscher. På grund av bristen på adekvat sensorsteknik har denna teknik hittills sällan används inom automotivesektorn. Med tillkomsten av solid-state LiDAR -sensorer som enkelt kan integreras i serieproduktionsfordon för att kunna känna av den omgivningen, kan denna teknik automatisera verksamheten. Att manövrera ett fordon i närheten av ett referensobjekt är en sådan operation, som bara kan utföras genom att exakt uppskatta dess position och orientering i förhållande till själva fordonet. Detta projekt handlar om design och implementering av en algoritm för att exakt lokalisera ett flygplan parkerat på ett flygfält i realtid. Detta uppnås genom att registrera planetens molnmodell till mätpunktsmolnet på scenen som produceras av LiDAR -sensorerna ombord på fordonet. För detta ändamålet är Iterative Closest Point (ICP) -algoritmen ett väletablerat tillvägagångssätt för att registrera två uppsättningar punkter utan föregående kännedom om överensstämmelserna mellan parpar, vilket dock är notoriskt känsligt för avvikelser och beräknat dyrt med stora punktmoln. I detta arbete presenteras olika varianter som förbättrar standard ICP - algoritmen, när det gäller noggrannhet och runtime performance, genom att utnyttja olika datastrukturer för att indexera referensmodellen och outlier -avvisningsstrategier. Resultaten visar att de implementerade algoritmerna kan producera uppskattningar av centimeters precision i millisekunder baserat endast på partiella observationer av flygplanet, vilket överträffar en annan etablerad lösning som testats.

Now a days where technological advancements are growing at a rapid pace, it has become a common norm for all the manufacturing companies to be abreast with these advancements for being competitive in market. This thesis deals with development of one such common norm for one of the products (Roof rack component) for company Thule. The main aim of the thesis is to curtail the products lead time to market and this was achieved by using an artificial intelligence technique i.e., Case-based reasoning (CBR). Roof rack component which is mounted on car roof is mainly constituted by two parts foot pad and bracket, this thesis main interest was concerned with only brackets and its geometry. This thesis is based on contemplating the already implemented concepts in this context, designer requirements and exploring better solutions. The methods of implementation adopted here was using CBR concept which is based on indexing , retrieve, adapt, review, retain and employing these concepts in form of an algorithm. The concept for developing the algorithm was based on Iterative closest point (ICP) approach which emphasise on assigning lower weight to pairs with greater point to point distance. The results portrayed are with respect to geometry and also with respect to application interface developed, which both together provides us a better solution.

The Iterative Closest Point (ICP) algorithm is one of the most commonly used range image processing methods. However, slow operational speeds and high input band-widths limit the use of ICP in high-speed real-time applications. This thesis presents and examines a novel hardware implementation of a high-speed ICP object tracking system that uses stereo vision disparities as input. Although software ICP trackers already exist, this innovative hardware tracker utilizes the efficiencies of custom hardware processing, thus enabling faster high-speed real-time tracking. A custom hardware design has been implemented in an FPGA to handle the inherent bottlenecks that result from the large input and processing band-widths of the range data. The hardware ICP design consists of four stages: Pre-filter, Transform, Nearest Neighbor, and Transform Recovery. This custom hardware has been implemented and tested on various objects, using both software simulation and hardware tests. Results indicate that the tracker is able to successfully track free-form objects at over 200 frames-per-second along arbitrary paths. Tracking errors are low, in spite of substantial noisy stereo input. The tracker is able to track stationary paths within 0.42mm and 1.42degs, linear paths within 1.57mm and 2.80degs, and rotational paths within 0.39degs axis error. With further degraded data by occlusion, the tracker is able to handle 60% occlusion before a slow decline in performance. The high-speed hardware implementation (that uses 16 parallel nearest neighbor circuits), is more then five times faster than the software K-D tree implementation. This tracker has been designed as the hardware component of ‘FastTrack’, a high frame rate, stereo vision tracking system, that will provide a known object’s pose in real-time at 200 frames per second. This hardware ICP tracker is compact, lightweight, has low power requirements, and is integratable with the stereo sensor and stereo extraction components of the FastTrack’ system on a single FPGA platform. High-speed object tracking is useful for many innovative applications, including advanced spaced-based robotics. Because of this project’s success, the ‘FastTrack’ system will be able to aid in performing in-orbit, automated, remote satellite recovery for maintenance. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2008-07-15 22:50:30.369

During orthopaedic surgery, preoperative CT scans can be aligned to the patient to assist the guidance of surgical instruments and the placement of implants. Registration (i.e. alignment) can be accomplished in many ways: by registering implanted fiducial markers, by touching a probe to the bone surface, or by aligning intraoperative two dimensional flouro images with the the three dimensional CT data. These approaches have problems: They require exposure of the bone, subject the patient and surgeons to ionizing radiation, or do both. Ultrasound can also be used to register a preoperative CT scan to the patient. The ultrasound probe is tracked as it passes over the patient and the ultrasound images are aligned to the CT data. This method eliminates the problems of bone exposure and ionizing radiation, but is computationally more difficult because the ultrasound images contain incomplete and unclear bone surfaces. In this work, we compare three methods to register a set of ultrasound images to a CT scan: Iterated Closest Point, Mutual Information and a novel method Points-to-Image. The average Target Registration Error and speed of each method is presented along with a brief summary of their strengths and weaknesses. / Thesis (Master, Computing) -- Queen's University, 2009-01-22 04:21:22.569

Medical imaging has become the key to access inside human body for the purpose of diagnosis and treatment planning. In order to understand the effectiveness of planned treatment following the diagnosis, treated body part may have to be monitored several times during a period of time. Information gained from successive imaging of body part provides guidance to next step of treatment. Comparison of images or datasets taken at different times requires registration of these images or datasets since the same conditions may not be provided at all times. Accurate segmentation of the body part under treatment is needed while comparing medical images to achieve quantitative and qualitative measurements. This segmentation task enables two dimensional and three dimensional visualizations of the region which also aid in directing the planning strategy. In this thesis, several segmentation algorithms are investigated and a hybrid segmentation algorithm is developed in order to segment bone tissue out of head CT slices for orthodontic treatment planning. Using the developed segmentation algorithm, three dimensional visualizations of segmented bone tissue out of head CT slices of two patients are obtained. Visualizations are obtained using the MATLAB Computer software&amp / #8217 / s visualization library. Besides these, methods are developed for automatic registration of twodimensional and three-dimensional CT images taken at different time periods. These methods are applied to real and synthetic data. Algorithms and methods used in this thesis are also implemented in MATLAB computer program.