difference between DIRECT7 、DIRECT1、and KDTREE

[chennuo0125-HIT]

thank you for your contribution, i don't know what is difference between DIRECT7 、DIRECT1 and KDTREE ？

[koide3]

For each point in the input cloud, NDT searches the neighbor voxels to calculate the gradient of the matching score. The original NDT implementation in PCL used kdtree-based radius search to find the neighbor voxels. But, the radius search is expensive processing, and it affects the matching speed. DIRECT1 and DIRECT7 directly finds the neighbor voxels by indexing. As illustrated in the figure, DIRECT1 just returns the voxel which contains the point (voxel[x, y]), while DIRECT7 extracts the seven voxels next to the center voxel (voxel[x, y], voxel[x-1, y], voxel[x, y-1], ...).

The matching result with KDTREE is identical to the original version in PCL, and it is slightly faster thanks to the SSE optimization. DIRECT1 is much faster, but a bit unstable since it refers narrow area compared to KDTREE. DIRECT7 is faster than KDTREE, and it extracts the same voxels as KDREE in most of cases.

[chennuo0125-HIT]

@koide3 thank you for your answer , i get it !

[bob-ROS]

Hey @koide3. I have used your package with great success for my thesis, very impressive implementation. Do you have any paper explaining these settings more in detail?

[koide3]

Hi @bob-ROS ,
We've not published some papers about the detail of this implementation. If you need general explanation of the NDT algorithm, this thesis would be helpful.

This implementation was developed as a part of the following work, and I would be glad if you refer to it in case it is appropriate for your paper.

• Kenji Koide, Jun Miura, and Emanuele Menegatti, A Portable 3D LIDAR-based System for Long-term and Wide-area People Behavior Measurement, International Journal of Advanced Robotic Systems, 2019