724:
244:
796:
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.
444:
65:. 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.
607:
589:
946:
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".
135:
130:
45:
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
344:
775:
314:
729:
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
601:
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
518:
496:
336:
719:{\displaystyle \arg \min _{\mathbf {R} ,\mathbf {t} }\left\{-\sum _{i}\operatorname {NDT} \left(f_{\mathbf {R} ,\mathbf {t} }\left(\mathbf {x_{i}} \right)\right)\right\}}
525:
984:
Li, Leihui; Wang, Riwei; Zhang, Xuping (2021). "A Tutorial Review on Point Cloud
Registrations: Principle, Classification, Comparison, and Technology Challenges".
471:
264:
239:{\displaystyle \textstyle \mathbf {S} ={\frac {1}{n}}\sum _{i}\left(\mathbf {x} _{i}-\mathbf {q} \right)\left(\mathbf {x} _{i}-\mathbf {q} \right)^{\top }}
73:
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
76:
54:
1013:
999:
The three-dimensional normal-distributions transform: an efficient representation for registration, surface analysis, and loop detection
439:{\displaystyle e^{-{\frac {1}{2}}\left(\mathbf {x} -\mathbf {q} \right)^{\top }\mathbf {S} ^{-1}\left(\mathbf {x} -\mathbf {q} \right)}}
790:
732:
269:
884:
Biber, Peter; Straßer, Wolfgang (2003). "The normal distributions transform: A new approach to laser scan matching".
886:
Proceedings 2003 IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453)
57:(SLAM) and relative position tracking, the algorithm was extended to 3D point clouds and has wide applications in
1035:
598:
32:
1030:
451:
594:
that maps from the second cloud to the first, parametrised by the rotation angles and translation components.
782:
25:
956:
906:
778:
316:
that fall within the cell. The probability density of sampling a point at a given spatial location
47:
42:
501:
479:
319:
972:
584:{\displaystyle f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )=\mathbf {R} \mathbf {x} +\mathbf {t} }
893:
Cheng, Liang; Chen, Song; Liu, Xiaoqiang; Xu, Hao; Wu, Yang; Li, Manchun; Chen, Yanming (2018).
934:
964:
924:
914:
474:
58:
50:
of the second point cloud on such distribution as a function of the transform parameters.
960:
910:
929:
894:
456:
249:
1024:
976:
968:
125:{\displaystyle \textstyle \mathbf {q} ={\frac {1}{n}}\sum _{i}\mathbf {x_{i}} }
39:
28:
938:
786:
62:
31:
introduced by Peter Biber and
Wolfgang Straßer in 2003, while working at
919:
38:
The algorithm registers two point clouds by first associating a
789:-based methods (in the original formulation, the authors use
905:(5). Multidisciplinary Digital Publishing Institute: 1641.
770:{\displaystyle f_{\mathbf {R} ,\mathbf {t} }(\mathbf {x} )}
338:
within the cell is then given by the normal distribution
53:
Originally introduced for 2D point cloud map matching in
309:{\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}
895:"Registration of laser scanning point clouds: A review"
139:
80:
735:
610:
528:
504:
482:
459:
347:
322:
272:
252:
138:
79:
949:ISPRS Journal of Photogrammetry and Remote Sensing
769:
718:
583:
512:
490:
465:
438:
330:
308:
258:
238:
124:
811:
809:
618:
597:The algorithm registers the two point clouds by
1014:"Register two point clouds using NDT algorithm"
8:
868:
816:
855:
842:
928:
918:
829:
759:
749:
741:
740:
734:
695:
690:
679:
671:
670:
649:
630:
622:
621:
609:
576:
568:
563:
552:
542:
534:
533:
527:
505:
503:
483:
481:
458:
424:
416:
402:
397:
390:
380:
372:
356:
352:
346:
323:
321:
300:
295:
279:
274:
271:
251:
229:
219:
210:
205:
188:
179:
174:
162:
148:
140:
137:
114:
109:
103:
89:
81:
78:
805:
55:simultaneous localization and mapping
7:
986:Mathematical Problems in Engineering
450:Two point clouds can be mapped by a
391:
230:
14:
760:
750:
742:
696:
692:
680:
672:
631:
623:
577:
569:
564:
553:
543:
535:
506:
484:
425:
417:
398:
381:
373:
324:
296:
275:
220:
206:
189:
175:
141:
115:
111:
82:
969:10.1016/j.isprsjprs.2020.03.013
764:
756:
557:
549:
18:normal distributions transform
1:
1001:(Ph.D.). Örebro universitet.
785:, and can be optimised with
513:{\displaystyle \mathbf {t} }
491:{\displaystyle \mathbf {R} }
331:{\displaystyle \mathbf {x} }
1052:
997:Magnusson, Martin (2009).
856:Li, Wang & Zhang 2021
817:Biber & Straßer 2003
777:. The loss is piecewise
452:Euclidean transformation
26:point cloud registration
498:and translation vector
771:
720:
585:
514:
492:
467:
440:
332:
310:
260:
240:
126:
33:University of Tübingen
955:. Elsevier: 327–342.
871:, pp. 10–11, 13)
772:
721:
586:
515:
493:
468:
441:
333:
311:
261:
241:
127:
733:
608:
526:
502:
480:
457:
345:
320:
270:
266:points of the cloud
250:
136:
77:
961:2020JPRS..163..327D
911:2018Senso..18.1641C
43:normal distribution
767:
716:
654:
636:
581:
510:
488:
463:
436:
328:
306:
256:
236:
235:
167:
122:
121:
108:
920:10.3390/s18051641
869:Cheng et al. 2018
858:, pp. 21–22)
645:
617:
466:{\displaystyle f}
364:
259:{\displaystyle n}
158:
156:
99:
97:
1043:
1036:Pattern matching
1017:
1002:
993:
980:
942:
932:
922:
889:
872:
865:
859:
852:
846:
843:Dong et al. 2020
839:
833:
826:
820:
813:
776:
774:
773:
768:
763:
755:
754:
753:
745:
725:
723:
722:
717:
715:
711:
710:
706:
705:
701:
700:
699:
685:
684:
683:
675:
653:
635:
634:
626:
590:
588:
587:
582:
580:
572:
567:
556:
548:
547:
546:
538:
519:
517:
516:
511:
509:
497:
495:
494:
489:
487:
472:
470:
469:
464:
445:
443:
442:
437:
435:
434:
433:
429:
428:
420:
410:
409:
401:
395:
394:
389:
385:
384:
376:
365:
357:
337:
335:
334:
329:
327:
315:
313:
312:
307:
305:
304:
299:
284:
283:
278:
265:
263:
262:
257:
245:
243:
242:
237:
234:
233:
228:
224:
223:
215:
214:
209:
197:
193:
192:
184:
183:
178:
166:
157:
149:
144:
131:
129:
128:
123:
120:
119:
118:
107:
98:
90:
85:
1051:
1050:
1046:
1045:
1044:
1042:
1041:
1040:
1031:Computer vision
1021:
1020:
1012:
1009:
996:
983:
945:
892:
883:
880:
875:
866:
862:
853:
849:
840:
836:
827:
823:
814:
807:
803:
791:Newton's method
736:
731:
730:
691:
686:
666:
665:
661:
641:
637:
606:
605:
529:
524:
523:
500:
499:
478:
477:
475:rotation matrix
455:
454:
415:
411:
396:
371:
367:
366:
348:
343:
342:
318:
317:
294:
273:
268:
267:
248:
247:
204:
203:
199:
198:
173:
172:
168:
134:
133:
132:and covariance
110:
75:
74:
71:
59:computer vision
12:
11:
5:
1049:
1047:
1039:
1038:
1033:
1023:
1022:
1019:
1018:
1008:
1007:External links
1005:
1004:
1003:
994:
981:
943:
890:
888:. Vol. 3.
879:
876:
874:
873:
860:
847:
834:
830:Magnusson 2009
821:
804:
802:
799:
783:differentiable
766:
762:
758:
752:
748:
744:
739:
727:
726:
714:
709:
704:
698:
694:
689:
682:
678:
674:
669:
664:
660:
657:
652:
648:
644:
640:
633:
629:
625:
620:
616:
613:
592:
591:
579:
575:
571:
566:
562:
559:
555:
551:
545:
541:
537:
532:
508:
486:
462:
448:
447:
432:
427:
423:
419:
414:
408:
405:
400:
393:
388:
383:
379:
375:
370:
363:
360:
355:
351:
326:
303:
298:
293:
290:
287:
282:
277:
255:
232:
227:
222:
218:
213:
208:
202:
196:
191:
187:
182:
177:
171:
165:
161:
155:
152:
147:
143:
117:
113:
106:
102:
96:
93:
88:
84:
70:
67:
13:
10:
9:
6:
4:
3:
2:
1048:
1037:
1034:
1032:
1029:
1028:
1026:
1015:
1011:
1010:
1006:
1000:
995:
991:
987:
982:
978:
974:
970:
966:
962:
958:
954:
950:
944:
940:
936:
931:
926:
921:
916:
912:
908:
904:
900:
896:
891:
887:
882:
881:
877:
870:
864:
861:
857:
851:
848:
844:
838:
835:
831:
825:
822:
818:
812:
810:
806:
800:
798:
794:
792:
788:
784:
780:
746:
737:
712:
707:
702:
687:
676:
667:
662:
658:
655:
650:
646:
642:
638:
627:
614:
611:
604:
603:
602:
600:
595:
573:
560:
539:
530:
522:
521:
520:
476:
460:
453:
430:
421:
412:
406:
403:
386:
377:
368:
361:
358:
353:
349:
341:
340:
339:
301:
291:
288:
285:
280:
253:
225:
216:
211:
200:
194:
185:
180:
169:
163:
159:
153:
150:
145:
104:
100:
94:
91:
86:
68:
66:
64:
60:
56:
51:
49:
44:
41:
36:
34:
30:
27:
23:
19:
1016:. MathWorks.
998:
989:
985:
952:
948:
902:
898:
885:
863:
850:
837:
824:
795:
728:
596:
593:
449:
72:
52:
37:
21:
17:
15:
69:Formulation
1025:Categories
992:. Hindawi.
801:References
779:continuous
599:optimising
48:likelihood
977:216449537
659:
647:∑
643:−
615:
422:−
404:−
392:⊤
378:−
354:−
289:…
231:⊤
217:−
186:−
160:∑
101:∑
40:piecewise
29:algorithm
939:29883397
787:gradient
63:robotics
957:Bibcode
930:5981425
907:Bibcode
899:Sensors
878:Sources
246:of the
24:) is a
975:
937:
927:
973:S2CID
473:with
990:2021
935:PMID
781:and
61:and
16:The
965:doi
953:163
925:PMC
915:doi
793:).
656:NDT
619:min
612:arg
22:NDT
1027::
988:.
971:.
963:.
951:.
933:.
923:.
913:.
903:18
901:.
897:.
808:^
35:.
979:.
967::
959::
941:.
917::
909::
867:(
854:(
845:)
841:(
832:)
828:(
819:)
815:(
765:)
761:x
757:(
751:t
747:,
743:R
738:f
713:}
708:)
703:)
697:i
693:x
688:(
681:t
677:,
673:R
668:f
663:(
651:i
639:{
632:t
628:,
624:R
578:t
574:+
570:x
565:R
561:=
558:)
554:x
550:(
544:t
540:,
536:R
531:f
507:t
485:R
461:f
446:.
431:)
426:q
418:x
413:(
407:1
399:S
387:)
382:q
374:x
369:(
362:2
359:1
350:e
325:x
302:n
297:x
292:,
286:,
281:1
276:x
254:n
226:)
221:q
212:i
207:x
201:(
195:)
190:q
181:i
176:x
170:(
164:i
154:n
151:1
146:=
142:S
116:i
112:x
105:i
95:n
92:1
87:=
83:q
20:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.