Optimizing the Normal Distributions Transform Update Algorithm
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2025-02-24
Department
Major/Subject
Computer Science
Mcode
Degree programme
Master's Programme in Computer, Communication and Information Sciences
Language
en
Pages
66
Series
Abstract
The Normal Distributions Transform (NDT) is a compact representation for point cloud data that models groups of points using Gaussian distributions. One of its most important applications is in autonomous robotics, where it is used to represent maps of the environment, based on point cloud data from sensors such as lidars or time-of-flight cameras. In particular, a Simultaneous Localization And Mapping (SLAM) algorithm can utilize the NDT representation to efficiently build maps and simultaneously estimate the robot’s position within them. A key component of this is the NDT update algorithm, which is used to both create new NDT maps from point clouds and to incorporate new point cloud data into existing NDT maps. This thesis was conducted for GIM Robotics, where the NDT update algorithm was previously found to consume over 70% of the total computation time of the NDT-based SLAM algorithm. This previous finding, along with the real-time requirements of SLAM and the increasingly high data rates of modern lidars, provided the motivation for this thesis. This thesis focused on optimizing the NDT update algorithm to improve performance, with the aim of at least a twofold speedup, while maintaining accuracy. The baseline implementation was analyzed to identify bottlenecks, and optimization techniques were applied, including removal of redundant operations, improving the utilization of vector instructions by using 256-bit AVX instructions, as well as parallelizing the algorithm across processor cores using OpenMP. These optimizations resulted in a 9.8-fold speedup when updating an existing NDT map and a 6.2-fold speedup when creating a new one. In addition, a 2.25-fold speedup was observed in our SLAM algorithm when it internally used the optimized NDT update algorithm. The findings of this thesis contribute to more efficient operation of autonomous robots by helping NDT-based mapping and positioning algorithms maintain real-time performance, even with the increasingly high data rates of modern point cloud sensors. Future work could explore GPU acceleration, alternative data structures, and further improvements to the thread-level parallelization scheme introduced in this thesis.Normaalijakaumien muunnos (NDT) on pistepilvien esitysmuoto, jossa pistepilvet pakataan pienempään kokoon ryhmittelemällä pisteitä ja esittämällä pisteryhmät normaalijakaumien avulla. Yksi NDT-esitysmuodon tärkeimmistä sovelluskohteista on autonomisessa robotiikassa, missä sitä käytetään ympäristöä mallintavien karttojen esittämiseen. Nämä kartat pohjautuvat pistepilviin, jotka on kerätty käyttäen esimerkiksi lidaria tai syvyyskameraa. Kerätyistä pistepilvistä voidaan muodostaa kartta käyttämällä samanaikaista paikannus- ja kartoitusalgoritmia (SLAM), jonka yksi tärkeimmistä vaiheista on NDT-esitysmuodon luominen ja päivittäminen uusien pistepilvien perusteella. Tämä diplomityö tehtiin GIM Roboticsille, jossa käytetty SLAM-algoritmi pohjautuu pistepilvien NDT-esitysmuotoon. Aiemmassa diplomityössä havaittiin, että yli 70 % SLAM-algoritmin suoritusajasta kului NDT-esitysmuodon päivittämiseen, mikä toimi tämän työn motivaationa. Tämän diplomityön tavoitteena oli saavuttaa vähintään kaksinkertainen nopeutus NDT-esitysmuodon päivittämisessä, säilyttäen algoritmin tarkkuus. NDT-päivitysalgoritmia optimoitiin poistamalla tarpeettomia laskutoimituksia, sekä parantamalla algoritmin rinnakkaisuutta käyttämällä 256-bittisiä AVX-vektorikäskyjä sekä säikeistämällä algoritmi OpenMP:n avulla, joka mahdollisti sen ajamisen rinnakkain useammalla prosessoriytimellä. Tässä työssä saavutettiin 9,8-kertainen nopeutus NDT-päivitysalgoritmin suoritusajassa olemassaolevaa karttaa päivitettäessä, sekä 6,2-kertainen nopeutus uutta karttaa luotaessa. Tämän lisäksi saavutettiin 2,25-kertainen nopeutus NDT-päivitystä käyttävän SLAM-algoritmin suoritusajassa. Tämän työn tulokset auttavat NDT-pohjaisia kartoitus- ja paikannusalgoritmeja ylläpitämään reaaliaikaista suorituskykyä, jopa nykyaikaisten pistepilviantureiden suurilla näytteenottotaajuuksilla. Jatkotutkimuksessa voitaisiin tarkastella GPU-kiihdytystä, vaihtoehtoisia tietorakenteita, sekä tässä työssä esitellyn säikeistysmenetelmän jatkokehitystä.Description
Supervisor
Suomela, JukkaThesis advisor
Karppinen, PetriKeywords
Normal Distributions Transform, NDT Update Algorithm, Performance Optimization, SLAM, Robotics, Parallel Computing