Normal distributions transform: Difference between revisions
rename the covariance matrix from capital sigma to S, to not be confused with a sum sign |
applications |
||
Line 3: | Line 3: | ||
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. |
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">Biber and Straßer (2003)</ref> the algorithm |
Originally introduced for 2D point cloud map matching in [[simultaneous localization and mapping]] (SLAM) and relative position tracking,<ref name="biberAndStraßer">Biber and Straßer (2003)</ref> the algorithm was extended to 3D point clouds<ref>Magnusson (2009)</ref> and has wide applications in [[computer vision]] and [[robotics]]. NDT is very fast and accurate and it is 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>Dong et al. (2020)</ref><ref>Li et al. (2021)</ref><ref>Cheng et al. (2018)</ref> |
||
== Formulation == |
== Formulation == |
||
Line 30: | Line 30: | ||
== Sources == |
== 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 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}} |
|||
*{{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}} |
|||
*{{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}} |
*{{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}} |
||
Revision as of 21:22, 27 February 2022
The normal distributions transform (NDT) is a point cloud registration algorithm introduced by Peter Biber and Wolfgang Straßer in 2003, while working at University of Tübingen.
The algorithm registers two point clouds by first associating a piecewise 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 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,[1] the algorithm was extended to 3D point clouds[2] and has wide applications in computer vision and robotics. NDT is very fast and accurate and it is 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.[3][4][5]
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 and covariance of the points of the cloud that fall within the cell. The probability density of sampling a point at a given spatial location within the cell is then given by the normal distribution
- .
Two point clouds can be mapped by an Euclidean transformation with rotation matrix and translation vector
that maps from the second cloud to the first, parametrised by the rotation angles and translation components.
The algorithm registers the two point clouds by optimising the parameters of the transformation that maps the second cloud to the first, with respect to a loss function based on the NDT of the first point cloud, solving the following problem
where the loss function represents the negated likelihood, obtained by applying the transformation to all points in the second cloud and summing the value of the NDT at each transformed point . The loss is piecewise continuous and differentiable, and can be optimised with gradient-based methods (in the original formulation, the authors use Newton's method).
In order to reduce the effect of cell discretisation, a technique consists of partitioning the space into multiple overlapping grids, shifted by half cell size along the spatial directions, and computing the likelihood at a given location as the sum of the NDTs induced by each grid.[1]
References
Sources
- Biber, Peter; Straßer, Wolfgang (2003). "The normal distributions transform: A new approach to laser scan matching". Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453). Vol. 3.
- Cheng, Liang; Chen, Song; Liu, Xiaoqiang; Xu, Hao; Wu, Yang; Li, Manchun; Chen, Yanming (2018). "Registration of laser scanning point clouds: A review". Sensors. 18 (5). Multidisciplinary Digital Publishing Institute: 1641.
- Dong, Zhen; Liang, Fuxun; Yang, Bisheng; Xu, Yusheng; Zang, Yufu; Li, Jianping; Wang, Yuan; Dai, Wenxia; Fan, Hongchao; Hyyppä, Juha (2020). "Registration of large-scale terrestrial laser scanner point clouds: A review and benchmark". ISPRS Journal of Photogrammetry and Remote Sensing. 163. Elsevier: 327–342.
- Li, Leihui; Wang, Riwei; Zhang, Xuping (2021). "A Tutorial Review on Point Cloud Registrations: Principle, Classification, Comparison, and Technology Challenges". Mathematical Problems in Engineering. 2021. Hindawi.
- Magnusson, Martin (2009). The three-dimensional normal-distributions transform: an efficient representation for registration, surface analysis, and loop detection (Ph.D.). Örebro universitet.
External links
- "Register two point clouds using NDT algorithm". MathWorks.