3D-NDT
作者把 Biber 與 Strasser 的二維 NDT 推廣為三維：把模型掃描切成固定格網，每格以點的平均與共變異數表示常態分布，再以牛頓法最佳化資料點落在分布上的分數，不需最近鄰搜尋。論文比較取樣方式、格子大小，以及八叉樹、加成式、迭代式細分、連結格與無限外界等變體，並以 Kvarntorp 礦坑的原型雷射與 SICK LMS 200 資料對照 ICP：迭代細分加無限外界的 3D-NDT 在 50 對機器人掃描中高精度配準 45 對；在相同取樣比例下，3D-NDT 通常比 ICP 快將近三倍，但起始誤差較大時比 ICP 更早失敗。
本頁內容
3D generalization of NDT (cell-wise normal distributions scored with Newton's method, no nearest-neighbour search) with sampling, cell-size and subdivision variants, compared with ICP on Kvarntorp mine data: iterative-subdivision NDT registered 45 of 50 robot scan pairs with high accuracy, 3D-NDT was typically almost three times faster than ICP at the same sampling ratio, but began failing at slightly smaller initial errors.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | Optab Optronikinnovation AB prototype 3D laser range finder (modulated infrared laser on a rotating mirror, phase-shift ranging; pitching scans for TUNNEL, yawing scans for JUNCTION)、SICK LMS 200 2D laser scanner on a pan-tilt unit giving pitching 3D scans of about 95,000 points (KVARNTORP-LOOP)、2D wheel odometry of the robot for initial pose estimates (KVARNTORP-LOOP)、total station measuring three marked points on the scanner (TUNNEL); not accurate enough as ground truth, used only as initial estimate |
|---|---|
| 原文測試平台 | static Optab prototype scanner (JUNCTION: two scans from the same pose at different resolutions; TUNNEL: two poses about 4 m apart); carrier not described、Tjorven mobile robot, driven manually and stationary during each scan (KVARNTORP-LOOP) |
| 狀態估計 | Newton's method with line search on the negated NDT score (maximum step 0.05, convergence when the change of p is below 0.0001); 7-parameter axis-angle transform (Eq. 13), noted as redundant; ICP baseline: point-to-point least squares with a 1 m fixed outlier threshold and approximate kd-tree search (ANN) |
| 資料關聯 | each data-scan point is scored against the normal distribution of the cell it falls in (point-to-distribution); variants: octree, additive and iterative subdivision, linked cells and infinite outer bounds |
| 時間表示 | 不適用 (pairwise scan registration) |
| 去畸變 | 不適用 (robot kept stationary during each scan) |
| 迴圈閉合 | none |
| 全域最佳化 | none |
| 地圖表示 | regular grid of cells (1 m baseline, 0.5 m to 3 m tested) storing mean and covariance of the points in each cell that holds more than a minimum number of points (Sec. 2.2 calls five points per cell a reasonable limit); octree-forest, additive and iterative subdivision variants |
| 先驗資訊 | initial pose estimate required: synthetic offsets around a reference pose (JUNCTION, TUNNEL), total-station estimate (TUNNEL), 2D odometry (KVARNTORP-LOOP) |
| 可輸出幾何 | 6-DoF rigid transformation |
| 計算需求 | C++ implementation (ANN library for ICP, newmat for NDT) on an AMD Athlon at 1950 MHz with 512 MB memory; ICP about three times slower than 3D-NDT in the sample-ratio tests and on KVARNTORP-LOOP; iterative 3D-NDT about twice a single-resolution run |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| LiDAR | Optab prototype 3D laser range finder | 方法輸入 | JUNCTION and TUNNEL | modulated infrared laser projected onto a rotating mirror, phase-shift ranging; JUNCTION data scan 139,642 and model 72,417 points; TUNNEL about 27,500 points per scan | (Magnusson et al., 2007, Sec. 5.1; Fig. 9) |
| LiDAR | SICK LMS 200 | 方法輸入 | KVARNTORP-LOOP | 2D scanner on a pan-tilt unit for pitching 3D scans; about 95,000 points per scan; scans 4 to 5 m apart | (Magnusson et al., 2007, Sec. 5.1; Fig. 10) |
| 輪式或腿式里程計 | Tjorven 2D odometry | 方法輸入 | KVARNTORP-LOOP | pose error up to about 1.5 m and 0.2 rad between scans; reset after scans 11, 16 and 66 | (Magnusson et al., 2007, Sec. 5.2.2) |
| 全測站 | total station (model not stated) | 方法輸入 | TUNNEL | tripod-mounted; measured three marked points on the scanner from a fixed position; not accurate enough for ground truth, used as initial estimate | (Magnusson et al., 2007, Sec. 5.1; Fig. 6) |
| 載具平台 | Tjorven (authors' mobile robot) | 方法輸入 | KVARNTORP-LOOP | driven manually, stationary during scans; also carries a digital camera, sonar array, omnidirectional camera and differential GPS, not used for registration | (Magnusson et al., 2007, Sec. 5.1; Fig. 10 caption) |
| 運算硬體 | AMD Athlon 1950 MHz with 512 MB memory | 執行運算平台 | 未標示 | runs all timing experiments | (Magnusson et al., 2007, Sec. 5 baseline) |
作者報告的優勢與限制
優勢
- faster and slightly more reliable than ICP on the mine data (Abstract)
- iterative subdivision with infinite outer bounds registered 45 of 50 KVARNTORP-LOOP pairs with high accuracy and failed on two (Sec. 5.2.2, Fig. 21)
- lower median error than ICP in most single-pair tests (Sec. 5.2.1)
- NDT storage needs only a small fraction of the space of point clouds (Sec. 6)
限制
- cell size must be chosen: too small cells fail from larger initial errors and too large cells blur features; about 1 to 2 m suited this mine (Sec. 4.2, 5.2.1)
- failures start at smaller initial errors than ICP on JUNCTION (3D-NDT from 2 m or 0.3 rad, ICP reliable to 2.5 m or 0.35 rad) (Sec. 5.2.1)
- some non-converging outlier runs; at low sample ratios 3D-NDT failed up to 12% sampling while ICP was acceptable down to about 8% (Sec. 5.2.1)
- reference poses for TUNNEL and KVARNTORP-LOOP were chosen by inspecting registration attempts; no independent ground truth (Sec. 5.1, 5.2)
- array storage of all cells caused large memory use and swapping with 0.5 m cells (Sec. 5.2.1)
營建工程相關證據
論文的目標應用是在隧道開挖用的鑽堡上量測隧道斷面，用來檢核新隧道形狀、估算開挖量並檢查舊隧道安全（Sec. 1）；實驗地點為瑞典 Kvarntorp 已停產的砂岩礦坑（Sec. 5.1）。屬地下工程與隧道施工相關場景，但不是建築工地。JUNCTION 兩站在同一位置掃描，參考位姿即為零位移；TUNNEL 與 KVARNTORP-LOOP 的參考位姿是多次配準後目視挑選最佳結果再取平均，並非獨立量測，全測站量測精度不足，只用作初始估計。
原文驗證環境：地下或隧道
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 14 個比較組，合計 55 筆紀錄。以下列出本方法紀錄最多的 4 組，其餘 10 組列在最後，並連到性能比較頁。
Pang et al., 2018 · Table III 本方法 18 筆
表格設定（擷取紀錄原文）：MCity 350 m route; NDT with one parameter varied per row (values of the other parameters not stated) (Pang et al., 2018, Table III)
Localization MAE Error (m)，MCity test route (350 m) · voxel size (m) = 0.5
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Pang et al., 2018 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| NDT (voxel size (m) = 0.5)本方法 | 0.0525 m | (Pang et al., 2018, Table III) |
Pang et al., 2018 · Table I 本方法 8 筆
表格設定（擷取紀錄原文）：MCity route of 350 m at 17 mph; localisation MAE and average registration time for different reference-map resolutions; ICP rows for 121 and 400 points/m2 not listed because each registration took more than 2 s (Pang et al., 2018, Table I)
Localization MAE error (m)，MCity test route (350 m) · reference map resolution 9 points/m2
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Pang et al., 2018 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Pang et al., 2018, Table I)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| NDT本方法 | 0.3391 m | (Pang et al., 2018, Table I) |
| ICP (kd-tree, point-to-point) | 0.125 m | (Pang et al., 2018, Table I and note) |
Magnusson et al., 2007 · Text Sec. 5.2.1 本方法 6 筆
資料集與序列JUNCTION · initial translation error test (rotation error 0)
表格設定（擷取紀錄原文）：JUNCTION pair (Optab prototype scanner, both scans from the same pose, ground truth = zero motion); 100 runs per setting from start poses on a sphere around the reference; baseline 10% spatially distributed sampling of the data scan (Magnusson et al., 2007, Text Sec. 5.2.1)
initial translation error at which failed registrations start，JUNCTION · initial translation error test (rotation error 0)
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Magnusson et al., 2007 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| 3D-NDT (baseline, fixed 1 m cells)本方法原文提出 | 2 m失敗註記（擷取紀錄）：failures begin | (Magnusson et al., 2007, Sec. 5.2.1; Fig. 16) |
Magnusson et al., 2007 · Text Sec. 5.2.2 本方法 6 筆
資料集與序列KVARNTORP-LOOP · scans 17-66
表格設定（擷取紀錄原文）：KVARNTORP-LOOP scans 17-66 (50 consecutive pairs), SICK LMS 200 on Tjorven; 8000 random data-scan samples (about 8%), all model points; initial poses from 2D odometry; 'good' = within 0.10 m and 0.005 rad, 'acceptable' = within 0.20 m and 0.010 rad of reference poses obtained by inspecting a number of registration attempts and averaging the best matches (Magnusson et al., 2007, Text Sec. 5.2.2)
successful registrations (octree subdivision, 2 m cells split to 1 and 0.5 m)，KVARNTORP-LOOP · scans 17-66
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Magnusson et al., 2007 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| 3D-NDT, octree subdivision本方法原文提出 | 40 | (Magnusson et al., 2007, Sec. 5.2.2) |
其他比較組
列出其餘 10 個比較組
- Pang et al., 2018 · Text Sec. IV-E
- Pang et al., 2018 · Text Sec. IV-F
- Magnusson et al., 2009 · Text Fig. 7 caption
- Magnusson et al., 2015 · Fig. 3 (execution-time table)
- Pang et al., 2018 · Table IV
- Magnusson et al., 2009 · Text Fig. 8 caption
- Magnusson et al., 2009 · Text Sec. IV-D-2
- Magnusson et al., 2009 · Text Sec. IV-D-3
- Magnusson et al., 2015 · Text Sec. V-A
- Pang et al., 2018 · Text Sec. IV-D-2
來源
Magnusson et al., 2007
（2007）Scan registration for autonomous mining vehicles using 3D-NDTJournal of Field Robotics, 24(10):803-827
同儕審查已出版已讀全文經典