SLAM 點雲圖鑑Point clouds for construction
M-01 · 2021

ikd-Tree

ikd-Tree 讓 k-d 樹只以新進點增量更新，支援單點與方盒範圍的插入、重新插入與刪除（刪除採延遲標記），並在樹上同步降採樣：以邊長 L 的立方格劃分空間，每格只保留最接近格心的點。樹以類似 scapegoat 樹的準則監測平衡並局部重建，大型子樹可交由第二執行緒重建，以維持即時性。

地圖表示與表面重建近十年已讀全文預印本地圖表示與表面重建

閱讀版本
arXiv 2102.10808v1 (22 Feb 2021, 8 pp., only version; no journal reference on the abs page)
全文取得途徑
arXiv 預印本
本頁內容

An incremental k-d tree supporting point- and box-wise insert/delete, on-tree voxel downsampling (keeping the point nearest each cell center), and partial rebuilding with optional parallel threads.

技術屬性

欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。

感測輸入3D LiDAR、IMU (in the FAST-LIO application test)
原文測試平台["未查證 (outdoor Livox Avia data、Fig. 7 shows the mapping result of the Main Building, University of Hong Kong、onboard computer DJI Manifold 2-C4、carrier not stated)"]
狀態估計不適用 (data structure; tested inside FAST-LIO)
資料關聯exact (not approximate) k-nearest-neighbour search that uses per-node range bounds and lazy-label pushdown (Sec. III-E)
時間表示不適用
去畸變不適用
迴圈閉合不適用
全域最佳化none
地圖表示incremental k-d tree of map points with lazy-delete labels and on-tree voxel downsampling
先驗資訊none
可輸出幾何downsampled point set stored in the tree
計算需求CPU only: randomized tests on a PC with Intel i7-10700 (2.90 GHz, only 2 threads running); FAST-LIO test on a DJI Manifold 2-C4 (quad-core Intel i7-8550U 1.8 GHz, 8 GB RAM); optional second thread rebuilds sub-trees larger than Nmax = 1500

使用設備

原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。

類別型號（原文寫法）角色資料集原文規格出處
LiDARLivox Avia方法輸入未標示70 degree FoV; frame rate 100 Hz(Cai et al., 2021, Sec. V-B)
運算硬體DJI Manifold 2-C4執行運算平台未標示1.8 GHz quad-core Intel i7-8550U CPU, 8 GB RAM(Cai et al., 2021, Sec. V-B)
運算硬體Intel i7-10700執行運算平台未標示PC, 2.90 GHz, only 2 threads running(Cai et al., 2021, Sec. V-A)

論文圖片

只收錄原文以開放授權（open license）釋出的圖片，並依授權條件標示出處、圖號、授權與修改方式。

  • 增量式 k-d 樹插入新點與局部重新平衡的立體示意

    Fig. 1增量式 k-d 樹插入新點與局部重新平衡的立體示意

    出處：Cai et al., 2021，Fig. 1。授權：CC BY 4.0。原始圖檔。修改：縮小至寬度不超過 1400 px，並轉存為 WebP 格式。

  • 樹上降採樣前後的點雲對照

    Fig. 2樹上降採樣前後的點雲對照

    出處：Cai et al., 2021，Fig. 2。授權：CC BY 4.0。原始圖檔。修改：縮小至寬度不超過 1400 px，並轉存為 WebP 格式。

  • FAST-LIO 中 ikd-Tree 與靜態 k-d 樹融合一筆新掃描的時間、時間分解與平衡指標

    Fig. 6FAST-LIO 中 ikd-Tree 與靜態 k-d 樹融合一筆新掃描的時間、時間分解與平衡指標

    出處：Cai et al., 2021，Fig. 6。授權：CC BY 4.0。原始圖檔。修改：轉存為 WebP 格式。

  • 香港大學本部大樓 100 Hz 建圖成果與 LiDAR 軌跡

    Fig. 7香港大學本部大樓 100 Hz 建圖成果與 LiDAR 軌跡

    出處：Cai et al., 2021，Fig. 7。授權：CC BY 4.0。原始圖檔。修改：縮小至寬度不超過 1400 px，並轉存為 WebP 格式。

作者報告的優勢與限制

優勢

  • ["On randomized data, incremental update time stayed around 1.6 ms while a static kd-tree rebuild grew linearly with points (Sec. V-A, Fig. 4).", "In FAST-LIO the per-scan fusion time stayed nearly constant around 1.6 ms (average of the last 100 scans), enabling mapping up to 100 Hz versus 10 Hz for the original static-tree FAST-LIO
  • the static tree exceeded 10 ms per scan from 366 s onward (Sec. V-B, Fig. 6(a)).", "Authors report about two orders of magnitude higher efficiency in their conclusion, while the abstract states ikd-Tree used only 4% of the static k-d tree running time (Sec. VI, Abstract)."]

限制

  • ["Insertion of spatially compact data is slower because rebuilds are triggered more often (Sec. V-A, Fig. 5).", "k-nearest search was slightly slower than the PCL static k-d tree in the randomized test (Sec. V-A, Fig. 4(b)).", "Space complexity is O(n) but with a constant a few times larger than a static k-d tree (Sec. IV-B).", "Box-wise operations use boxes aligned with the data coordinate axes (Sec. III-C).", "(inference) The on-tree downsampling keeps one point per cell, so the stored map is a resolution-limited subset of raw measurements rather than all points."]

營建工程相關證據

未在營建場域驗證；唯一實測為香港大學本部大樓的戶外 LiDAR 慣性建圖（Fig. 7）。樹上降採樣在每個邊長 L 的立方格只保留最接近格心的點（FAST-LIO 測試中 L 為 0.2 m，Table II），因此決定 FAST-LIO2 類系統輸出地圖的點密度上限（推論）。

原文驗證環境：模擬、受控實驗

報告的性能數據

以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。

本方法共出現在 2 個比較組，合計 4 筆紀錄。

Cai et al., 2021 · Text Sec. V-B 本方法 3 筆

資料集與序列authors' outdoor recording · Main Building, University of Hong Kong

表格設定（擷取紀錄原文）：FAST-LIO on a real outdoor scene with a Livox Avia; time to fuse one new LiDAR scan averaged over the most recent 100 scans; ikd-Tree replaces the static PCL k-d tree for build, update and query; downsampling cube 0.2 m (Cai et al., 2021, Text Sec. V-B)

average running time of fusing one new LiDAR scan，authors' outdoor recording · Main Building, University of Hong Kong

只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。

  • 未報告（沒有數值，不是 0）

這些是 Cai et al., 2021 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。

統計量：平均值（mean）；對齊方式：原文未報告；單位：ms；場景：outdoor campus

資料來源作者報告值(Cai et al., 2021, Text Sec. V-B)

數值與出處
方法（原文寫法）報告值出處
FAST-LIO with ikd-Tree本方法原文提出硬體：DJI Manifold 2-C4 (Intel i7-8550U, 8 GB RAM)1.6 ms有附註註記（擷取紀錄）：stated as nearly constant around 1.6 ms(Cai et al., 2021, Sec. V-B)
FAST-LIO with static K-D tree硬體：DJI Manifold 2-C4 (Intel i7-8550U, 8 GB RAM)無數值未報告註記（擷取紀錄）：increases roughly linearly and exceeds 10 ms from 366 s onward(Cai et al., 2021, Sec. V-B)

Cai et al., 2021 · Text Sec. V-A 本方法 1 筆

指標time for incremental updates per test operation, including re-building

資料集與序列randomized synthetic points · incremental test (5,000 to about 200,000 points)

表格設定（擷取紀錄原文）：Randomized test: 5,000 initial points in a 10 m cube, 1,000 operations of 200-point insertions and 5-NN queries, periodic box-wise deletes and 2,000-point insertions; tree grows to about 200,000 points; static tree is the PCL k-d tree rebuilt each operation; no downsampling (Cai et al., 2021, Text Sec. V-A)

time for incremental updates per test operation, including re-building，randomized synthetic points · incremental test (5,000 to about 200,000 points)

這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Cai et al., 2021 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。

統計量：原文未報告；對齊方式：原文未報告；單位：ms；場景：synthetic

數值與出處
方法（原文寫法）報告值出處
ikd-Tree本方法原文提出硬體：PC, Intel i7-10700 2.90 GHz, 2 threads1.6 ms有附註註記（擷取紀錄）：stated as remaining stably around 1.6 ms(Cai et al., 2021, Sec. V-A)

來源

  • Cai et al., 2021

    Yixi Cai, Wei Xu, Fu Zhang（2021）ikd-Tree: An Incremental K-D Tree for Robotic ApplicationsarXiv preprint

    arXiv 2102.10808程式碼

    預印本已讀全文近十年查證後修正

程式碼：https://github.com/hku-mars/ikd-Tree（授權：GPL-2.0 (repository LICENSE)）。有公開程式碼不等於已被重現，也不代表目前版本與論文版本相同。

回到方法圖鑑

SLAM 點雲圖鑑

本站為綜述論文《SLAM-Based Point Clouds for Construction: A Review》研究過程的互動說明文件。互動圖為教學模擬，不代表任何特定系統的實測表現；方法描述、數值與結論以所引原始文獻為準。

內容基準日 2026-09-25 · 研究與網站製作使用 AI 輔助工具，見 證據標記與方法

選擇開啟Esc關閉