Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2309.08315 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911785979740160 |
|---|---|
| author | Zhu, Jun Li, Hongyi Wang, Zhepeng Wang, Shengjie Zhang, Tao |
| author_facet | Zhu, Jun Li, Hongyi Wang, Zhepeng Wang, Shengjie Zhang, Tao |
| contents | Establishing the correspondences between newly acquired points and historically accumulated data (i.e., map) through nearest neighbors search is crucial in numerous robotic applications. However, static tree data structures are inadequate to handle large and dynamically growing maps in real-time. To address this issue, we present the i-Octree, a dynamic octree data structure that supports both fast nearest neighbor search and real-time dynamic updates, such as point insertion, deletion, and on-tree down-sampling. The i-Octree is built upon a leaf-based octree and has two key features: a local spatially continuous storing strategy that allows for fast access to points while minimizing memory usage, and local on-tree updates that significantly reduce computation time compared to existing static or dynamic tree structures. The experiments show that i-Octree outperforms contemporary state-of-the-art approaches by achieving, on average, a 19% reduction in runtime on realworld open datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_08315 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | i-Octree: A Fast, Lightweight, and Dynamic Octree for Proximity Search Zhu, Jun Li, Hongyi Wang, Zhepeng Wang, Shengjie Zhang, Tao Robotics Establishing the correspondences between newly acquired points and historically accumulated data (i.e., map) through nearest neighbors search is crucial in numerous robotic applications. However, static tree data structures are inadequate to handle large and dynamically growing maps in real-time. To address this issue, we present the i-Octree, a dynamic octree data structure that supports both fast nearest neighbor search and real-time dynamic updates, such as point insertion, deletion, and on-tree down-sampling. The i-Octree is built upon a leaf-based octree and has two key features: a local spatially continuous storing strategy that allows for fast access to points while minimizing memory usage, and local on-tree updates that significantly reduce computation time compared to existing static or dynamic tree structures. The experiments show that i-Octree outperforms contemporary state-of-the-art approaches by achieving, on average, a 19% reduction in runtime on realworld open datasets. |
| title | i-Octree: A Fast, Lightweight, and Dynamic Octree for Proximity Search |
| topic | Robotics |
| url | https://arxiv.org/abs/2309.08315 |