Go-ICP
Go-ICP 在整個 SE(3) 空間以分支定界（BnB）搜尋點對點 ICP 之 L2 誤差的全域最佳解。旋轉以角軸向量表示於 [-π, π]³ 立方體，平移限定在 [-ξ, ξ]³，兩者都以八元樹細分；作者由旋轉與平移的不確定半徑推導每點殘差的上下界，並採外層旋轉、內層平移的巢狀 BnB。每當找到更好的解就以局部 ICP 精修並更新上界，加快收斂而不失全域最佳性；另以修剪（trimming）處理部分重疊與離群點。在 Stanford bunny 與 dragon 的 2000 次部分對完整配準中全部成功，使用距離轉換時平均約 1.5 至 1.6 秒、最長 28.9 秒（Intel i7 3.4 GHz，1000 個資料點）。作者建議用於不要求即時性的情境，或作為最佳性基準。
本頁內容
Branch-and-bound over SE(3) with derived bounds gives globally optimal L2 ICP registration independent of initialization.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | ["Kinect (bowl and loom point sets)", "structured light 3D scanner (denture point set)", "RGB-D depth images from public datasets (camera localization dataset [68], RGB-D Object Dataset [69])"] |
|---|---|
| 原文測試平台 | 未記錄 |
| 狀態估計 | nested best-first branch-and-bound: an outer BnB over rotation (angle-axis cube [-pi, pi]^3 split by octree) calls an inner BnB over translation (cube [-xi, xi]^3); per-point residual bounds come from rotation and translation uncertainty radii; whenever a better cube is found, local ICP is run from it and its result tightens the upper bound; the search stops when the best error minus the lower bound is below epsilon; outliers handled with a trimmed L2 error using Introselect (O(N)) |
| 資料關聯 | closest point under the L2 residual; for bound evaluation closest distances come either from a kd-tree or, more often in the experiments, from a precomputed 3-D Euclidean distance transform (300 x 300 x 300 grid, approximate); local ICP always uses a kd-tree |
| 時間表示 | 不適用 |
| 去畸變 | 不適用 |
| 迴圈閉合 | none |
| 全域最佳化 | globally optimal search over SE(3) (abstract) |
| 地圖表示 | 3D point sets |
| 先驗資訊 | no initial pose needed; requires a bounded translation domain [-xi, xi]^3, point sets pre-normalized to [-1, 1]^3, a convergence threshold epsilon and, for partial overlap, a hand-chosen trimming percentage rho |
| 可輸出幾何 | rigid transformation |
| 計算需求 | C++ on a standard PC with an Intel i7 3.4 GHz CPU; with the distance transform, mean and longest times 1.6 s and 22.3 s (bunny) and 1.5 s and 28.9 s (dragon) for 1000 data points against 20,000 to 40,000 model points; kd-tree runs typically 40 to 50 times longer; trimmed partial-overlap runs 0.45 to 18.4 s mean and up to 107.3 s max (Table 1); camera localization 32 s mean and 178 s max |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| RGB-D 相機 | Kinect | 資料集感測器 | bowl and loom point sets collected by the authors | 原文未報告 | (Yang et al., 2016, Sec. 6.3) |
| 運算硬體 | Intel i7 3.4GHz CPU (standard PC) | 執行運算平台 | 未標示 | C++ implementation | (Yang et al., 2016, Sec. 6) |
| 其他 | structured light 3D scanner | 資料集感測器 | denture point set | 原文未報告 | (Yang et al., 2016, Sec. 6.3, footnote 6) |
作者報告的優勢與限制
優勢
- globally optimal regardless of initialization (abstract, Sec. 7); 100% correct registration on 2,000 partial-to-full tasks on bunny and dragon, rotation errors < 2 deg and translation errors < 0.01 in normalized units (Sec. 6.2); all 2,000 trimmed partial-overlap tasks on 10 point-set pairs with 50% to 95% overlap correct, rotation < 5 deg and translation < 0.05 (Sec. 6.3, Table 1); camera localization of 100 depth images against an office model with errors below 5 deg and 10 cm (Sec. 6.4)
限制
- runs take seconds to minutes, and the authors recommend it where real-time performance is not critical or as an optimality benchmark (Sec. 6, 7)
- experiments sub-sample data sets to 1000 (or 400 to 600) data points (Sec. 6.2 to 6.4)
- runtime grows when the optimal RMS error is high, e.g. global minimum found at about 25 s with the rest spent raising the lower bound (Sec. 6.2, Fig. 17)
- trimming percentage chosen by visually guessing the non-overlap ratio (Sec. 6.3)
- L2 objective is outlier-sensitive and only trimming is implemented (Sec. 2, 5.3)
- effective data size is limited (Bueno et al., 2018 Sec. 2, secondary)
- in FGR's comparison, Go-ICP and Go-ICP-Trimming inputs were downsampled to 1,000 points as suggested by Yang et al. (Zhou et al., 2016 Sec. 5, secondary)
營建工程相關證據
原文未報告（僅有物件模型、辦公室場景深度影像定位與 RGB-D 外參校正示例，無營建場域）
原文驗證環境：模擬、公開基準
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 9 個比較組，合計 87 筆紀錄。以下列出本方法紀錄最多的 4 組，其餘 5 組列在最後，並連到性能比較頁。
Yang et al., 2016 · Table 1 本方法 40 筆
表格設定（擷取紀錄原文）：Go-ICP with distance transform and trimming on 10 partially overlapping point-set pairs; 100 random relative poses per pair and direction; N = 1000 data points; epsilon = 0.001 x K; all tasks registered correctly (Yang et al., 2016, Table 1)
mean/max time (s)，Bunny (Stanford 3D) · A to B
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Yang et al., 2016 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| Go-ICP (DT, trimming rho = 10%)本方法原文提出硬體：Intel i7 3.4 GHz PC | 0.81 s | (Yang et al., 2016, Table 1) |
Zhou et al., 2016 · Table 1 本方法 12 筆
表格設定（擷取紀錄原文）：25 synthetic range-image pairs per noise level; RMSE of ground-truth correspondence distances, unit surface diameter; GoICP variants on 1,000 points (Zhou et al., 2016, Table 1)
Average RMSE，Synthetic range images (AIM@SHAPE, Berkeley Angel, Stanford Bunny) · sigma 0
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Zhou et al., 2016 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Zhou et al., 2016, Table 1)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| GoICP [42]本方法 | 0.029 | (Zhou et al., 2016, Table 1) |
| GoICP-Trimming [42]本方法 | 0.035 | (Zhou et al., 2016, Table 1) |
| Super 4PCS [26] | 0.012 | (Zhou et al., 2016, Table 1) |
| OpenCV [8] (implementation of Drost et al.) | 0.009 | (Zhou et al., 2016, Table 1) |
| PCL [19,34] (PCL implementation of Rusu et al.) | 0.003 | (Zhou et al., 2016, Table 1) |
| CZK [7] (Choi et al. variant of Rusu's algorithm) | 0.003 | (Zhou et al., 2016, Table 1) |
| Our approach (FGR)原文提出 | 0.003 | (Zhou et al., 2016, Table 1) |
Zhou et al., 2016 · Table 2 本方法 12 筆
指標running time per pairwise registration (s)
表格設定（擷取紀錄原文）：Average running time of each global method on each synthetic model and over all models (the number of tests averaged per model is not stated; each model has five range-image pairs at three noise levels); GoICP variants on 1,000 downsampled points, others at full resolution; single thread (Zhou et al., 2016, Table 2)
running time per pairwise registration (s)，Synthetic range images · Bimba (9,416 points avg)
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Zhou et al., 2016 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Zhou et al., 2016, Table 2)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| GoICP [42]本方法硬體：Intel Core i7-5960X 3.00 GHz, single thread | 19.3 s | (Zhou et al., 2016, Table 2) |
| GoICP-Trimming [42]本方法硬體：Intel Core i7-5960X 3.00 GHz, single thread | 19.4 s | (Zhou et al., 2016, Table 2) |
| OpenCV [8] (implementation of Drost et al.)硬體：Intel Core i7-5960X 3.00 GHz, single thread | 41 s | (Zhou et al., 2016, Table 2) |
| Super 4PCS [26]硬體：Intel Core i7-5960X 3.00 GHz, single thread | 311.4 s | (Zhou et al., 2016, Table 2) |
| PCL [19,34] (PCL implementation of Rusu et al.)硬體：Intel Core i7-5960X 3.00 GHz, single thread | 18.2 s | (Zhou et al., 2016, Table 2) |
| CZK [7] (Choi et al. variant of Rusu's algorithm)硬體：Intel Core i7-5960X 3.00 GHz, single thread | 12.8 s | (Zhou et al., 2016, Table 2) |
| Our approach (FGR)原文提出硬體：Intel Core i7-5960X 3.00 GHz, single thread | 0.13 s | (Zhou et al., 2016, Table 2) |
Yang et al., 2016 · Text Sec. 6.2 本方法 7 筆
表格設定（擷取紀錄原文）：Same setting as other Text Sec. 6.2 rows; 1,000 data points vs 20,000 to 40,000 model points (Yang et al., 2016, Text Sec. 6.2)
mean/longest running time，Stanford bunny · 1,000 tests
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Yang et al., 2016 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| Go-ICP (DT)本方法原文提出硬體：Intel i7 3.4 GHz PC | 1.6 s | (Yang et al., 2016, Sec. 6.2) |
其他比較組
來源
Yang et al., 2016
（2016）Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set RegistrationIEEE Transactions on Pattern Analysis and Machine Intelligence, 38(11):2241-2254
DOI 10.1109/tpami.2015.2513405arXiv 1605.03344程式碼
同儕審查已出版已讀全文經典查證後修正
相關版本
- 會議版：Go-ICP: Solving 3D Registration Efficiently and Globally Optimally (ICCV 2013) 10.1109/ICCV.2013.184
- 預印本：arXiv:1605.03344 v1 (2016-05-11), posted after the TPAMI online date https://arxiv.org/abs/1605.03344
程式碼：https://github.com/yangjiaolong/Go-ICP（授權：GPL-3.0 (LICENSE file checked)）。有公開程式碼不等於已被重現，也不代表目前版本與論文版本相同。