LIO-HKDT: Fast and Accurate LiDAR-Inertial Odometry with Hash K-D Tree
Yuexin Mu, Ao Ren, Duo Liu, Murong Wang, Zihao Zhang, Haojie Lu, Yujuan Tan, Kan Zhong
AI summary
Problem
Continuous LiDAR point cloud generation creates a severe computational bottleneck for K-nearest neighbor searches and incremental map updates, hindering real-time performance in autonomous navigation systems.
Approach
The authors design a sparse hash table that maps voxel indices to local k-d trees, augmented by a voxel distribution mechanism and a buffered parallel update strategy to enable fast localized searches and efficient batch insertions.
Key results
- Achieves the lowest total computational cost for insertion and search across all tested densities
- Maintains stable search and insertion efficiency as point cloud density increases
- Delivers pose estimation accuracy comparable to state-of-the-art LIO systems
- Reduces memory overhead while enabling multi-threaded batch point cloud updates
Why it matters
Provides a scalable, real-time mapping solution for autonomous robots and vehicles operating in dense, dynamic environments.
Abstract
LiDAR-inertial odometry(LIO) has been widely ap- plied in intelligent robotics and autonomous driving, providing high-precision and low-latency ego-motion estimation. However, the massive point clouds generated by LiDAR introduce inten- sive data processing demands, making k-nearest neighbor(KNN) search and map update a critical bottleneck that limits the real- time performance of the LIO system. This letter proposes a novel data structure, the Hash K-D Tree(hkd-Tree), which uses hashed voxel indices as keys and local k-d tree as values. It combines the localized search advantages of voxel-based methods with the efficient search capability of k-d tree, enabling fast KNN search and point cloud insertion. To further improve the performance of the hkd-Tree, we propose a voxel distribution mechanism and buffered update strategy, where each new point is assigned to neighboring voxels within the search radius and inserted into local k-d tree via parallel batch updates. We develop a LiDAR- inertial odometry system, LIO-HKDT, based on the proposed hkd-Tree. Extensive experiments demonstrate that the hkd-Tree enables highly efficient point cloud search and insertion. LIO- HKDT achieves comparable accuracy to state-of-the-art LIO systems while significantly improving runtime efficiency.