Normal distributions transform: Difference between revisions

Revision as of 18:45, 20 February 2022

Latest revision as of 14:36, 22 March 2023

(10 intermediate revisions by 5 users not shown)

Line 1:

The '''normal distributions transform''' ('''NDT''') is a [[point-set registration|point cloud registration]] [[algorithm]] introduced by Peter Biber and Wolfgang StraberStraßer in 2003, while working at [[University of Tübingen]].

The algorithm registers two point clouds by first associating a [[piecewise]] [[normal distribution|normal distribution]] to the first point cloud, that gives the probability of sampling a point belonging to the cloud at a given spatial coordinate, and then finding a transform that maps the second point cloud to the first by maximising the [[likelihood function|likelihood]] of the second point cloud on such distribution as a function of the transform parameters.

Originally introduced for 2D point cloud map matching in [[simultaneous localization and mapping]] (SLAM) and relative position tracking,<ref name="biberAndStraßer">{{harv|Biber and |Straßer (|2003)}}</ref> the algorithm canwas be appliedextended to 3D point clouds<ref>{{harv|Magnusson (|2009)}}</ref> and has wide applications in [[computer vision]] and [[robotics]]. NDT is very fast and accurate, making it suitable for application to large scale data, but it is also sensitive to initialisation, requiring a sufficiently accurate initial guess, and for this reason it is typically used in a coarse-to-fine alignment strategy.<ref>{{harv|Dong et al.|2020}}</ref><ref>{{harv|Li|Wang|Zhang|2021|pp=21-22}}</ref><ref>{{harv|Cheng et al.|2018|pp=10-11,13}}</ref>

== Formulation ==

The NDT function associated to a point cloud is constructed by partitioning the space in regular cells. For each cell, it is possible to define the mean <math>\textstyle \mathbf{q} = \frac{1}{n} \sum_i \mathbf{x_i}</math> and covariance <math>\textstyle \Sigmamathbf{S} = \frac{1}{n} \sum_i \left(\mathbf{x}_i - \mathbf{q}\right) \left(\mathbf{x}_i - \mathbf{q}\right)^\top</math> of the <math>n</math> points of the cloud <math>\mathbf{x}_1, \dots, \mathbf{x}_n</math> that fall within the cell. The probability density of sampling a point at a given spatial ___location <math>\mathbf{x}</math> within the cell is then given by the normal distribution

:<math>e^{-\frac{1}{2} \left(\mathbf{x} - \mathbf{q}\right)^\top \Sigmamathbf{S}^{-1} \left(\mathbf{x} - \mathbf{q}\right)}</math> .

Two point clouds can be mapped by ana [[Euclidean transformation]] <math>f</math> with [[rotation matrix]] <math>\mathbf{R}</math> and translation vector <math>\mathbf{t}</math>

:<math>f_{\mathbf{R}, \mathbf{t}}(\mathbf{x}) = \mathbf{R} \mathbf{x} + \mathbf{t}</math>

Line 30:

== Sources ==

*{{cite conference|title=The normal distributions transform: A new approach to laser scan matching|book-title=Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453)|year=2003|volume=3|last1=Biber|first1=Peter|last2=Straßer|first2=Wolfgang}}

*{{cite journal|title=Registration of laser scanning point clouds: A review|year=2018|journal=Sensors|volume=18|pages=1641|issue=5|publisher=Multidisciplinary Digital Publishing Institute|last1=Cheng|first1=Liang|last2=Chen|first2=Song|last3=Liu|first3=Xiaoqiang|last4=Xu|first4=Hao|last5=Wu|first5=Yang|last6=Li|first6=Manchun|last7=Chen|first7=Yanming|doi=10.3390/s18051641 |pmid=29883397 |pmc=5981425 |bibcode=2018Senso..18.1641C |doi-access=free|ref={{harvid|Cheng et al.|2018}}}}

*{{cite journal|title=Registration of large-scale terrestrial laser scanner point clouds: A review and benchmark|year=2020|journal=ISPRS Journal of Photogrammetry and Remote Sensing|volume=163|pages=327–342|publisher=Elsevier|last1=Dong|first1=Zhen|last2=Liang|first2=Fuxun|last3=Yang|first3=Bisheng|last4=Xu|first4=Yusheng|last5=Zang|first5=Yufu|last6=Li|first6=Jianping|last7=Wang|first7=Yuan|last8=Dai|first8=Wenxia|last9=Fan|first9=Hongchao|last10=Hyyppä|first10=Juha|doi=10.1016/j.isprsjprs.2020.03.013 |bibcode=2020JPRS..163..327D |s2cid=216449537|ref={{harvid|Dong et al.|2020}}}}

*{{cite journal|title=A Tutorial Review on Point Cloud Registrations: Principle, Classification, Comparison, and Technology Challenges|year=2021|journal=Mathematical Problems in Engineering|volume=2021|publisher=Hindawi|last1=Li|first1=Leihui|last2=Wang|first2=Riwei|last3=Zhang|first3=Xuping}}

*{{cite thesis|type=Ph.D.|title=The three-dimensional normal-distributions transform: an efficient representation for registration, surface analysis, and loop detection|year=2009|publisher=Örebro universitet|last1=Magnusson|first1=Martin}}