Iterative point matching (Zhang)
本文提出迭代虛擬點匹配（iterative pseudo point matching）演算法，用於配準邊緣式立體視覺取得的三維曲線，或相關式立體視覺重建的稠密三維地圖。方法假設兩次觀測之間的運動很小，或已由里程計與慣性系統近似得知；每次迭代先以目前估計轉換第一組點，再以 k-D tree 搜尋第二組資料中的最近點，接著依配對距離的平均值與標準差動態設定最大容許距離 Dmax，剔除離群點、遮蔽以及出現或消失的點（曲線另以切線夾角不超過 60 度限制配對），最後以四元數或對偶四元數最小平方法求剛體運動並反覆至收斂。作者以合成曲線、移動載具上三目立體相機拍攝的椅子場景、相關式立體視覺重建的岩石場景以及頭像距離影像驗證。
本頁內容
Iterative pseudo point matching: closest-point pairing with a k-D tree, an adaptive distance threshold Dmax set each iteration from the mean and standard deviation of pair distances to reject outliers, occlusion and appearance or disappearance, and closed-form (dual) quaternion least-squares rigid motion; assumes small or approximately known motion.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | trinocular edge-based stereo (3-D curves)、correlation-based stereo (dense 3-D maps)、range images (head figure, Sec. 6.2; sensor not reported) |
|---|---|
| 原文測試平台 | mobile vehicle carrying a trinocular stereo system (Sec. 5.3)、synthetic data (Sec. 5.1-5.2) |
| 狀態估計 | Closed-form least-squares rigid motion from the retained pairs (quaternion method and dual number quaternion method of Walker et al. 1991, both implemented with identical results), iterated until the relative changes of r and t are both below 1% or a maximum of 20 (curves) or 40 (surfaces) iterations is reached |
| 資料關聯 | Closest sample point in the second frame found with a 3-D tree whose search radius shrinks with Dmax; a pair is removed when its distance exceeds an adaptive Dmax computed each iteration from the mean mu and standard deviation sigma of pair distances (mu+3sigma, mu+2sigma, mu+sigma, or the histogram valley after the main peak, depending on mu relative to the user parameter D); for curves, pairs whose tangent angle exceeds 60 deg are also rejected |
| 時間表示 | 不適用 (pairwise rigid registration) |
| 去畸變 | 不適用 |
| 迴圈閉合 | none |
| 全域最佳化 | none |
| 地圖表示 | Raw 3-D point sets: chained points for curves and scattered points for dense 3-D maps, used without smoothing or primitive fitting |
| 先驗資訊 | Small inter-frame motion or an approximate initial motion (e.g., from odometric and inertial systems) is required; the algorithm converges to the closest local minimum, and large motions need a global method first or sampling of the 6-D motion space |
| 可輸出幾何 | 6-DoF rigid transformation |
| 計算需求 | C implementation (not optimized) run on a SUN 4/60 workstation (double precision LINPACK 1.05 Mflops); per-iteration complexity O(m log n) with the k-D tree; e.g., 6.5 s for the 200-point synthetic curve case (15 iterations) and 32.5 s for the real chair scene (12 iterations), reduced to 10.5 s with coarse-to-fine sampling |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| 雙目相機 | trinocular stereo system | 方法輸入 | 未標示 | mounted on the authors' mobile vehicle; 3-D curves reconstructed with the curve-based trinocular stereo algorithm of Robert and Faugeras (1991); in the chair test the chair was about 3 m away and the two positions differed by about 4 deg and 100 mm (36 curves and 588 points, 48 curves and 763 points); camera models and optics not reported | (Zhang, 1994, Sec. 5.3; Fig. 17) |
| 雙目相機 | stereo rig with a correlation-based stereovision system (image triplets) | 方法輸入 | 未標示 | about 6 m from the rock scene; 71505 and 51503 reconstructed points; positions differ by 30 deg and 3.75 m; data resolution about 5 cm | (Zhang, 1994, Sec. 6.1; Figs. 19-20; Sec. 7.2) |
| 載具平台 | mobile vehicle (unnamed) | 方法輸入 | 未標示 | carries the trinocular stereo system; context of autonomous navigation in rugged terrain | (Zhang, 1994, Sec. 1; Sec. 5.3) |
| 運算硬體 | SUN 4/60 workstation | 執行運算平台 | 未標示 | double precision LINPACK rating 1.05 Mflops; C implementation, not optimized | (Zhang, 1994, Sec. 5 opening; Note 2) |
作者報告的優勢與限制
優勢
- Handles gross outliers, appearance and disappearance, and occlusion through dynamic distance statistics (Sec. 3.3, Sec. 8, Sec. 9)
- Simple, extensible and general point-set representation for arbitrary shapes (Sec. 9)
- Efficient: closest-point search O(N log N); coarse-to-fine sampling cut runtime from 7.49 s to 3.39 s on synthetic curves and from 32.5 s to 10.5 s on the chair scene with little accuracy change (Sec. 5.2, Sec. 5.3)
- No smoothing or derivative estimation required (Sec. 9)
- Rock scene: 0.65 to 0.92 deg and 2.87 to 6.18 cm difference from the manual registration from initial offsets of 20 deg with 2.07 to 2.56 m (Test 2 needed 80 iterations) (Sec. 6.1)
限制
- Converges only to the closest local minimum; not appropriate for large motion (Sec. 7.6, Sec. 9)
- User parameter D must be set and affects the convergence rate (Sec. 4.1, Sec. 9)
- Only partially accounts for measurement uncertainty; a full treatment would need Kalman filtering at higher cost (Sec. 7.5, Sec. 9)
- Works better on rugged terrain than on flat ground, where many close local minima exist (Sec. 9)
- Monotonic convergence is not guaranteed because p_i switches between 0 and 1 (Sec. 7.2)
- Closest sample point approximation makes the result depend on sampling density (Sec. 7.4)
營建工程相關證據
原文未報告 (no construction use; application context is vision-based autonomous vehicle navigation in rugged terrain and Digital Elevation Map building, Sec. 1)
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 10 個比較組，合計 127 筆紀錄。以下列出本方法紀錄最多的 4 組，其餘 6 組列在最後，並連到性能比較頁。
Zhang, 1994 · Table 4 本方法 36 筆
表格設定（擷取紀錄原文）：Same synthetic curve; non-symmetric criterion (2) vs symmetric criterion (1); 10 iterations; mean of 10 tries; execution-time unit not restated in Table 4 (seconds in Tables 2-3) (Zhang, 1994, Table 4)
rotation error (%)，synthetic 3-D curve (Sec. 5.1) · noise std 0
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Zhang, 1994 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Zhang, 1994, Table 4)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| non-symmetric criterion (2), default本方法原文提出 | 1.81% | (Zhang, 1994, Table 4) |
| symmetric criterion (1), variant本方法原文提出 | 0.12% | (Zhang, 1994, Table 4) |
Zhang, 1994 · Table 2 本方法 33 筆
表格設定（擷取紀錄原文）：Synthetic 3-D curve, 200 points per frame, true r=[0.02,0.25,-0.15], t=[40,120,-50]; noise std varied; 15 iterations; mean of 10 tries (Zhang, 1994, Table 2)
rotation error ||r - r_est||/||r|| (%)，synthetic 3-D curve (Sec. 5.1) · noise std 0
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Zhang, 1994 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| iterative pseudo point matching (proposed)本方法原文提出 | 2.25% | (Zhang, 1994, Table 2) |
Zhang, 1994 · Table 3 本方法 30 筆
表格設定（擷取紀錄原文）：Same synthetic curve, noise std 2 added to both curves; fraction of first-frame points varied from 1 to 1/10; mean of 10 tries (iteration count not restated; the fraction-1 column equals the Table 2 std-2 column) (Zhang, 1994, Table 3)
rotation error (%)，synthetic 3-D curve (Sec. 5.1) · fraction of points 1
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Zhang, 1994 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| iterative pseudo point matching (proposed)本方法原文提出 | 2.12% | (Zhang, 1994, Table 3) |
Zhang, 1994 · Text Sec.5.2 本方法 6 筆
資料集與序列synthetic 3-D curve (Sec. 5.1) · noise std 3
表格設定（擷取紀錄原文）：Noise std 3; coarse-to-fine (5 iterations with 1 of 5 points, then 10 with all) vs 15 iterations with all points; mean of 10 experiments (Zhang, 1994, Text Sec.5.2)
rotation error (%)，synthetic 3-D curve (Sec. 5.1) · noise std 3
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Zhang, 1994 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Zhang, 1994, Text Sec.5.2)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| proposed with coarse-to-fine sampling本方法原文提出 | 4.56% | (Zhang, 1994, Sec. 5.2) |
| proposed, all points, 15 iterations本方法原文提出 | 4.68% | (Zhang, 1994, Sec. 5.2) |
其他比較組
來源
Zhang, 1994
（1994）Iterative point matching for registration of free-form curves and surfacesInternational Journal of Computer Vision, 13(2):119-152
同儕審查已出版已讀全文經典查證後修正
相關版本
- 預印本：INRIA Research Report RR-1658 (1992), 'Iterative point matching for registration of free-form curves' (report title covers curves only; content equivalence with the IJCV article not verified) https://inria.hal.science/inria-00074899