3D-NDT thesis
此博士論文以常態分布轉換（NDT）作為三維掃描的通用表面表示，並用於掃描配準、迴圈偵測與表面結構分析。配準部分將 Biber 與 Straßer 的二維 NDT 擴展到三維，以 z-y-x Euler 角參數化、解析梯度與 Hessian 搭配牛頓法與 Moré-Thuente 線搜尋求解，並提出由粗到細的迭代離散化（2 m、1 m、0.5 m 格子）、連結格子與三線性內插等延伸。作者在 Kvarntorp 礦坑隧道、模擬場景與飛行時間相機資料上，以 100 組預設初始偏移進行受控測試，並以里程計為初值處理兩段礦坑掃描序列，與 ICP 比較後結論為 NDT 對初始旋轉誤差較穩健且較快；Hessian 的反矩陣可估計位姿變異，作為配準成功與否的信心指標。論文另提出以色彩核函數擴充的 Colour-NDT、不需位姿資訊而以 NDT 表面形狀直方圖進行的外觀式迴圈偵測，以及用於礦堆巨石偵測的局部表面粗糙度分類。
本頁內容
PhD thesis presenting 3D-NDT as a general surface representation: Newton registration with iterative discretisation, linked cells and trilinear interpolation, evaluated against ICP on mine-tunnel, simulated and time-of-flight data; a Hessian-based confidence measure; Colour-NDT; NDT surface-shape histograms for appearance-based loop detection; and roughness-based point classification for boulder detection.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | SICK 2D lidar on a pan/tilt unit producing pitching 3D scans on Tjorven (180 deg horizontal, about 100 deg vertical field of view; SICK model not named for Tjorven)、SICK lidar on a continuously rotating slip-ring mount (yawing omnidirectional scans) and a Hokuyo 2D lidar for 2D localisation on Alfred、tiltable SICK laser scanner on Kurt3D (pitching scans)、PMD[vision] 19k time-of-flight camera combined with a Matrix-Vision Blue Fox colour camera (Colour-NDT data)、SwissRanger time-of-flight camera (3D-Cam scan pair, collected by Jacobs University Bremen)、SICK lidar on a Schunk PowerCube via slip-ring contacts with a digital camera (Kemi mine muck-pile scans)、simulated yawing lidar (Sci-Fi and Sim-Mine scan pairs)、wheel-encoder odometry for initial pose estimates (Kvarntorp-Loop, Mission-4) |
|---|---|
| 原文測試平台 | ActivMedia Pioneer P3-AT robot 'Tjorven' (Kvarntorp mine scans, Colour-NDT data)、Permobil electric-wheelchair platform 'Alfred' (part of the loop-detection data)、Kurt3D robot of Osnabrück University (Mission-4, Mission-4-1 and collaborative ICP comparison data)、service van carrying the slip-ring lidar to muck piles in the Kemi mine (scanner on the floor or in the van)、simulation (ray-traced scans) |
| 狀態估計 | Newton's method with Moré-Thuente line search on the NDT score (Gaussian approximation of a normal-plus-uniform mixture) with analytic gradient and Hessian and z-y-x Euler parametrisation; baseline uses iterative discretisation (2, 1, 0.5 m cells) with linked cells, 20% spatially distributed subsampling of the current scan and a step-size convergence limit of 1e-6; a BFGS quasi-Newton variant was less robust |
| 資料關聯 | each current-scan point is scored against the Gaussian of the cell it falls in; linked cells use the nearest occupied cell (kD tree of occupied cells); trilinear interpolation weights the eight nearest cells; Colour-NDT weights per-cell colour-kernel Gaussians; the ICP baseline uses point-to-point closest points with a fixed 0.5 m outlier threshold (0.1 m for 3D-Cam) |
| 時間表示 | 不適用 (pairwise registration) |
| 去畸變 | none applied: the mobile-robot registration data sets were acquired stop-and-scan (robot stopped every few metres); Sec. 3.2 only reviews motion-compensation methods for scanning while moving |
| 迴圈閉合 | appearance-based loop detection with NDT surface-shape histograms (1 spherical, 9 planar and 1 linear class in 5 range intervals; orientation normalised by dominant plane directions); threshold chosen manually or from an EM-fitted Gamma mixture; detects loop candidates only |
| 全域最佳化 | not addressed: pose-graph relaxation is deferred to existing methods (Grisetti et al., Borrmann et al.); Mission-4 and Mission-4-1 reference poses were produced with the Borrmann et al. relaxation using manually created loop closures |
| 地圖表示 | NDT cell grids: iterative multi-resolution cells (2, 1, 0.5 m for lidar scans; 0.5, 0.25, 0.125 m for time-of-flight data), with octree and k-means variants evaluated; Colour-NDT stores three colour-weighted Gaussians per cell; loop detection summarises overlapping 0.5 m cells as 55-bin surface-shape histograms |
| 先驗資訊 | initial pose estimate for registration (predefined offsets in the pairwise tests; wheel odometry in the Kvarntorp-Loop and Mission-4 sequences); loop detection uses no pose information, only scan order for a 30-scan minimum loop size |
| 可輸出幾何 | 6-DoF relative pose; NDT surface representation; loop detection output |
| 計算需求 | C++; NDT vs ICP runs on an Intel Core2 Duo 2.80 GHz (one core, 2 GiB RAM); collaborative comparison and loop detection on a 1.6 GHz Intel Celeron laptop (2 GiB); boulder labelling on a laptop with a 1600 MHz CPU (2 GiB); interpolated NDT about four times slower than non-interpolated NDT; histogram creation 0.18 to 0.50 s per histogram and about 7 microseconds per histogram comparison; boulder labelling 7.3 to 25.9 s per scan |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| LiDAR | SICK lidar on pan/tilt unit (model not named for Tjorven) | 方法輸入 | Straight, Crossing, Kvarntorp-Loop | pitching 3D scans, 180 deg horizontal and about 100 deg vertical field of view; about 90 000 to 95 000 points per scan in the mine data | (Magnusson, 2009, Sec. 4.1, 6.4.1, 6.4.3) |
| LiDAR | SICK lidar on continuously rotating motor with slip-ring contacts (Alfred) | 資料集感測器 | part of the loop-detection data (data set not specified) | omnidirectional yawing 3D scans | (Magnusson, 2009, Sec. 4.2) |
| LiDAR | tiltable SICK laser scanner (Kurt3D) | 方法輸入 | Mission-4, Mission-4-1 | pitching scans with field of view similar to Tjorven; about 70 000 to 75 000 points per scan | (Magnusson, 2009, Sec. 4.3, 6.4.3, 8.2.1) |
| LiDAR | SICK lidar on a Schunk PowerCube via slip-ring contacts (with a digital camera) | 方法輸入 | Kemi mine muck piles (locations A to D) | 72 000 to 418 000 points per scan, subsampled to one point per dm3 (10 000 to 22 000 points) | (Magnusson, 2009, Sec. 9.3.2) |
| 相機 | Matrix-Vision Blue Fox colour camera | 方法輸入 | Sofa-1, Sofa-2 | combined with the time-of-flight camera to colour the point clouds | (Magnusson, 2009, Sec. 7.3.1) |
| 輪式或腿式里程計 | wheel encoders (robot odometry) | 方法輸入 | Kvarntorp-Loop, Mission-4 | initial pose errors up to about 1.5 m and 0.2 rad per step (Kvarntorp-Loop), up to 1.4 rad (Mission-4 Scan 33) | (Magnusson, 2009, Sec. 6.4.3) |
| 載具平台 | ActivMedia Pioneer P3-AT ('Tjorven') | 方法輸入 | Straight, Crossing, Kvarntorp-Loop (Kvarntorp mine); Sofa-1, Sofa-2 | onboard computer, wheel encoders for 2D odometry, pan/tilt SICK lidar, omnidirectional camera, differential GPS antenna | (Magnusson, 2009, Sec. 4.1, 6.4.1, 6.4.3, 7.3.1) |
| 載具平台 | Permobil electric wheelchair ('Alfred') | 資料集感測器 | part of the loop-detection data (data set not specified) | custom platform with hydraulic lift | (Magnusson, 2009, Sec. 4.2) |
| 載具平台 | Kurt3D (Osnabrück University) | 方法輸入 | Mission-4, Mission-4-1, collaborative ICP comparison scan pair | controlled speed up to 4 m/s; two digital colour cameras | (Magnusson, 2009, Sec. 4.3, 6.4.2, 6.4.3, 8.2.1) |
| 運算硬體 | Intel Core2 Duo 2.80 GHz, 2 GiB RAM (one core used) | 執行運算平台 | 未標示 | NDT and ICP pairwise experiments | (Magnusson, 2009, Sec. 6.4.2) |
| 運算硬體 | laptop with 1.6 GHz Intel Celeron, 2 GiB RAM | 執行運算平台 | 未標示 | collaborative ICP comparison (Sec. 6.4.2) and loop-detection timings (Sec. 8.2.5, Table 8.3: '1.6 GHz CPU'); Sec. 9.3.2 reports boulder labelling only on 'a laptop computer with a 1600 MHz CPU and 2 GiB of RAM' without naming the CPU, so it is not stated that this is the same Celeron laptop | (Magnusson, 2009, Sec. 6.4.2, 8.2.5, 9.3.2) |
| 其他 | PMD[vision] 19k time-of-flight camera | 方法輸入 | Sofa-1, Sofa-2 | maximum range 7.5 m, 40 deg viewing angle, about 288 000 points per second | (Magnusson, 2009, Sec. 3.1.6, 7.3.1) |
| 其他 | SwissRanger time-of-flight camera | 資料集感測器 | 3D-Cam (Jacobs University Bremen) | 3D-Cam pair: about 65% overlap, about 25 000 points per scan | (Magnusson, 2009, Sec. 6.4.1) |
作者報告的優勢與限制
優勢
- Kvarntorp-Loop (48 scans): NDT and ICP both 98% successful with NDT much faster; trilinear NDT registered all scans (Sec. 6.4.3, Fig. 6.27)
- Mission-4 (55 scans): NDT 96% (53 of 55) vs ICP 87%; trilinear NDT failed only on Scan 42 (Sec. 6.4.3, Fig. 6.28)
- collaborative comparison with the Osnabrück ICP: within 0.20 m for 13.4% (ICP), 24.9% (NDT) and 99.8% (trilinear NDT) of 441 start poses (Sec. 6.4.2, Fig. 6.20)
- the largest eigenvalue of the inverse Hessian (threshold 0.5) separates failed from successful registrations better than the NDT score or the mean squared point distance (Sec. 6.6)
- loop detection: 80.6% recall at 1% false positives on Hannover-2 and 47.0% recall at 100% precision in the SLAM-style test; about 25 000 scan comparisons per second (Sec. 8.2.3, 8.2.5)
限制
- real-data reference poses were chosen manually from visually best registrations, so success is judged by thresholds of 0.20 m and 0.05 rad (Sec. 6.4.1, 6.4.3)
- the collaborative ICP comparison uses one scan pair and is not claimed to be statistically significant (Sec. 6.4.2)
- Newton optimisation is local and needs an initial pose estimate (Sec. 10.2)
- trilinear interpolation takes about four times as long as non-interpolated NDT (Sec. 6.4.1, 6.4.2)
- Colour-NDT was assessed only visually on two indoor time-of-flight data sets (Sec. 7.3.2)
- loop-detection recall falls to 27.5% to 28.6% in the self-similar mine data set, and the EM threshold needs at least about 100 scans (Sec. 8.2.3, 10.2)
- boulder detection was evaluated qualitatively on four muck piles and cannot find buried boulders or faces aligned with the pile slope (Sec. 9.3.3, 9.4)
- the author notes that 3D sensors of the time were too slow, expensive or fragile for production mines (Sec. 10.2)
- discretisation issues of basic NDT motivate the multi-resolution and interpolation extensions (abstract)
營建工程相關證據
論文主要應用為地下採礦：Kvarntorp 砂岩礦坑隧道的掃描配準與迴圈偵測，以及 Kemi 鉻礦礦堆的巨石偵測。第 1 章指出三維隧道模型可用於核對新開挖隧道形狀是否符合原設計並計算開挖量；第 10 章指出表面結構分析可延伸至採礦與營建中的料堆擷取。論文未使用營建工地資料；隧道與料堆情境對隧道施工與土方量測的參考價值屬推論。
原文驗證環境：模擬、地下或隧道、已完工建築、受控實驗、跨場域
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 11 個比較組，合計 38 筆紀錄。以下列出本方法紀錄最多的 4 組，其餘 7 組列在最後，並連到性能比較頁。
Magnusson, 2009 · Table 8.2 本方法 12 筆
表格設定（擷取紀錄原文）：SLAM-scenario loop detection: each scan matched to its most similar scan more than 30 steps away; true positive if the scan is manually labelled revisited, the match is within 10 m and below td; manual td vs td from an EM-fitted Gamma mixture at p(fp) = 0.5% (Magnusson, 2009, Table 8.2)
recall，Hannover-2 (428 revisited, 494 non-revisited scans) · manual threshold, td 0.0737
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Magnusson, 2009 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| NDT surface-shape histograms (loop detection)本方法原文提出 | 47% | (Magnusson, 2009, Table 8.2) |
Magnusson, 2009 · Text Sec. 6.4.2 (Figs. 6.20-6.21 captions) 本方法 6 筆
資料集與序列Kvarntorp tunnel scan pair (collaborative comparison) · 441 start poses
表格設定（擷取紀錄原文）：collaborative comparison: one slightly curved Kvarntorp tunnel scan pair (8 000 subsampled points each), 441 start poses with horizontal-plane translation offsets and rotation offsets from -80 to +80 deg; Osnabrück ICP vs thesis NDT; success = translation within 0.20 m (strict) or 1.0 m (loose), rotation within 5 deg; reference pose agreed manually (Magnusson, 2009, Text Sec. 6.4.2 (Figs. 6.20-6.21 captions))
success rate, strict translation threshold 0.20 m (second value in the Fig. 6.20 caption)，Kvarntorp tunnel scan pair (collaborative comparison) · 441 start poses
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Magnusson, 2009 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Magnusson, 2009, Text Sec. 6.4.2 (Figs. 6.20-6.21 captions))
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| ICP (University of Osnabrück implementation, parameters selected by that group) | 13.4% | (Magnusson, 2009, Fig. 6.20 caption; Sec. 6.4.2) |
| NDT (baseline: iterative discretisation with linked cells)本方法原文提出 | 24.9% | (Magnusson, 2009, Fig. 6.20 caption; Sec. 6.4.2) |
| NDT with trilinear interpolation本方法原文提出 | 99.8% | (Magnusson, 2009, Fig. 6.20 caption; Sec. 6.4.2) |
Magnusson, 2009 · Text Sec. 6.4.3 (Figs. 6.27-6.28 captions) 本方法 4 筆
資料集與序列Kvarntorp-Loop (Tjorven, 48 scans) · all consecutive scan pairs
表格設定（擷取紀錄原文）：stop-and-scan sequences in the Kvarntorp mine registered pairwise from odometry initial poses; success = within 0.20 m and 0.05 rad of manually determined reference poses (Magnusson, 2009, Text Sec. 6.4.3 (Figs. 6.27-6.28 captions))
success rate，Kvarntorp-Loop (Tjorven, 48 scans) · all consecutive scan pairs
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Magnusson, 2009 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Magnusson, 2009, Text Sec. 6.4.3 (Figs. 6.27-6.28 captions))
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| NDT (baseline)本方法原文提出 | 98% | (Magnusson, 2009, Fig. 6.27 caption) |
| ICP (baseline) | 98% | (Magnusson, 2009, Fig. 6.27 caption) |
Magnusson, 2009 · Table 8.1 本方法 3 筆
指標recall with less than 1% false positives
表格設定（擷取紀錄原文）：loop detection over all scan pairs; maximum recall with less than 1% false positives; ground truth = scan pairs closer than tr (Mission-4-1 also within 20 deg heading) (Magnusson, 2009, Table 8.1)
recall with less than 1% false positives，Hannover-2 (922 omnidirectional scans, about 1.24 km) · all pairs; tr 3 m; 9 984 overlapping and 839 178 non-overlapping pairs; td 0.1494
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Magnusson, 2009 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| NDT surface-shape histograms (loop detection)本方法原文提出 | 80.6% | (Magnusson, 2009, Table 8.1; Sec. 8.2.3) |
其他比較組
來源
Magnusson, 2009
（2009）The three-dimensional normal-distributions transform: an efficient representation for registration, surface analysis, and loop detectionÖrebro Studies in Technology 36 (doctoral dissertation, Örebro University), Örebro Studies in Technology 36; ISBN 978-91-7668-696-6
論文或報告已讀全文經典