Square Root SAM
本文把平滑（smoothing）視為 EKF 型 SLAM 的替代方案，將資訊矩陣或量測 Jacobian 分解為平方根形式求解。作者主張此類方法精確且更快，可批次或增量使用，較能處理非線性的運動與量測模型，並能以較低成本得到整條軌跡。欄位排序啟發式能間接利用 SLAM 問題在地理上的局部性。
本頁內容
Square-root information smoothing for SLAM factorizes the information matrix or Jacobian, offering an exact and often faster alternative to EKF-SLAM that recovers the full trajectory.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | 8-camera rig (visual point features)、wheel odometry |
|---|---|
| 原文測試平台 | simulation、wheeled UGV (iRobot ATRV-Mini) |
| 狀態估計 | square-root information smoothing by factorizing the information matrix (Cholesky or LDL) or the measurement Jacobian (QR), in batch or incremental mode; best performance with Davis' sparse LDL and colamd or symamd ordering applied to the block (pose and landmark) structure; non-linear problems are relinearized and refactorized at each call |
| 資料關聯 | real experiment: features matched between successive frames using RANSAC on a trifocal camera arrangement (Sec. 8); the formulation assumes data association is solved (Sec. 2) and the authors state they ignored data association (Sec. 10) |
| 時間表示 | discrete poses |
| 去畸變 | 不適用 |
| 迴圈閉合 | none occurred in the real experiment (Fig. 16 caption); fill-in when closing loops discussed for simulations (Sec. 7.2) |
| 全域最佳化 | full trajectory and map smoothing |
| 地圖表示 | landmarks (simulated landmarks observed with bearing and range; 4383 unknown 3D points in the real experiment) |
| 先驗資訊 | real experiment: zero-mean priors on height, pitch and roll (standard deviations 0.01 m and 0.02 rad) on the 6-DoF poses, because small floor bumps visibly affect the images in the planar indoor office (Sec. 8); formulation: the first pose x0 is treated as given and fixed at the origin, with a uniform prior over landmarks (Sec. 2; Sec. 3) |
| 可輸出幾何 | entire robot trajectory and map |
| 計算需求 | simulations in MATLAB on a 2 GHz Pentium 4 workstation running Linux (Sec. 7); the real sequence (260 joint images, 17780 measurements, 4383 unknown points) was processed in 11 min 10 s on a 2 GHz Pentium-M laptop with batch SAM invoked every three joint images; at the end forming the information matrix took about 0.6 s and LDL factorization 0.1 s (Sec. 8, Fig. 17) |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| 相機 | FireWire cameras (eight, custom rig; model not reported) | 方法輸入 | 未標示 | eight cameras distributed equally along a circle and connected to an on-board laptop; rig calibrated in advance; 260 joint images up to 2 m apart | (Dellaert & Kaess, 2006, Sec. 8; Fig. 15) |
| 輪式或腿式里程計 | odometry provided by the ATRV-Mini robot | 方法輸入 | 未標示 | standard deviations 0.02 m on x and y and 0.02 rad on yaw | (Dellaert & Kaess, 2006, Sec. 8) |
| 載具平台 | iRobot ATRV-Mini | 方法輸入 | 未標示 | mobile robot carrying the camera rig | (Dellaert & Kaess, 2006, Sec. 8; Fig. 15) |
| 運算硬體 | 2 GHz Pentium-M based laptop | 執行運算平台 | 未標示 | processed the entire real sequence in 11 min 10 s | (Dellaert & Kaess, 2006, Sec. 8) |
| 運算硬體 | 2 GHz Pentium 4 workstation running Linux | 執行運算平台 | 未標示 | MATLAB simulations | (Dellaert & Kaess, 2006, Sec. 7.1) |
作者報告的優勢與限制
優勢
- Faster yet exact relative to EKF, usable in batch or incremental mode (abstract)
- Column ordering heuristics exploit locality of SLAM (abstract)
- Incremental smoothing became cheaper than the EKF once about 600 landmarks had been seen in simulation (Sec. 7.2)
- Block-structured ordering gave a 15-fold LDL speed-up over colamd alone in the real experiment and reduced non-zeros in R from about 2.8 million (XL ordering) to about 130K in simulation (Sec. 7.1, Sec. 8, Figs. 12 and 13)
限制
- Batch refactoring performs unnecessary computation when applied incrementally, as noted by Kaess et al., 2008 (Sec. I)
- Computational complexity grows without bound because the entire trajectory is smoothed (Sec. 9, Fig. 17)
- Recovering the joint covariance is expensive, although marginals are cheaper (Sec. 9)
- No tight complexity bounds and no comparison with more recent approximate or exact SLAM methods (Sec. 9)
- Data association was ignored (Sec. 9, Sec. 10)
- In the real experiment the dominant cost was relinearizing the measurement Jacobian (453 evaluations), not factorization (Sec. 8)
營建工程相關證據
未在營建場域驗證；真實實驗在既有辦公建物室內（軌跡外框約 30 m × 50 m、總長約 190 m、260 組影像），僅與手動對齊的建物平面圖目視比對，無量化幾何精度[Sec. 8, Fig. 16]。
原文驗證環境：模擬、已完工建築
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 4 個比較組，合計 56 筆紀錄。
Dellaert & Kaess, 2006 · Fig. 10 table 本方法 48 筆
指標computation time averaged over 10 trials
表格設定（擷取紀錄原文）：Batch square-root SAM in synthetic environments; time averaged over 10 trials for trajectory length M and N landmarks (Dellaert & Kaess, 2006, Fig. 10 table)
computation time averaged over 10 trials，synthetic simulation · M = 200 poses, N = 180 landmarks
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Dellaert & Kaess, 2006 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Dellaert & Kaess, 2006, Fig. 10 table)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| none (no factorization; measures overhead)硬體：MATLAB on a 2 GHz Pentium 4 workstation running Linux | 0.031 s | (Dellaert & Kaess, 2006, Fig. 10 (tabulated values); Sec. 7.1) |
| batch square-root SAM, ldl (Davis sparse LDL)本方法原文提出硬體：MATLAB on a 2 GHz Pentium 4 workstation running Linux | 0.062 s | (Dellaert & Kaess, 2006, Fig. 10 (tabulated values); Sec. 7.1) |
| batch square-root SAM, chol (MATLAB built-in Cholesky)本方法原文提出硬體：MATLAB on a 2 GHz Pentium 4 workstation running Linux | 0.092 s | (Dellaert & Kaess, 2006, Fig. 10 (tabulated values); Sec. 7.1) |
| batch square-root SAM, mfqr (multifrontal QR)本方法原文提出硬體：MATLAB on a 2 GHz Pentium 4 workstation running Linux | 0.868 s | (Dellaert & Kaess, 2006, Fig. 10 (tabulated values); Sec. 7.1) |
| batch square-root SAM, qr (MATLAB built-in QR)本方法原文提出硬體：MATLAB on a 2 GHz Pentium 4 workstation running Linux | 1.685 s | (Dellaert & Kaess, 2006, Fig. 10 (tabulated values); Sec. 7.1) |
Dellaert & Kaess, 2006 · Text Sec.8 本方法 4 筆
資料集與序列authors' office sequence · entire sequence
表格設定（擷取紀錄原文）：Real indoor office sequence: ATRV-Mini with eight cameras and odometry, 260 joint images, about 190 m trajectory; batch square-root SAM every three joint images with LDL and block-structured colamd ordering (Dellaert & Kaess, 2006, Text Sec.8)
total processing time for the entire sequence (11 min 10 s)，authors' office sequence · entire sequence
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Dellaert & Kaess, 2006 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| incremental (repeated batch) square-root SAM本方法原文提出硬體：2 GHz Pentium-M based laptop | 670 s | (Dellaert & Kaess, 2006, Sec. 8) |
Dellaert & Kaess, 2006 · Text Figs.11-13 本方法 2 筆
指標number of non-zeros (approximate)
資料集與序列synthetic simulation · M = 1000, N = 500
表格設定（擷取紀錄原文）：Synthetic 1000-step random walk in a 500-landmark Manhattan world (Fig. 9): non-zeros in the Cholesky factor R for different column orderings, compared with the filtering covariance matrix (Dellaert & Kaess, 2006, Text Figs.11-13)
number of non-zeros (approximate)，synthetic simulation · M = 1000, N = 500
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Dellaert & Kaess, 2006 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Dellaert & Kaess, 2006, Text Figs.11-13)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| XL ordering (states then landmarks) | 2800000 count | (Dellaert & Kaess, 2006, Sec. 7.1; Fig. 12 caption) |
| colamd ordering本方法原文提出 | 250000 count | (Dellaert & Kaess, 2006, Sec. 7.1; Fig. 12 caption) |
| block-structured colamd ordering本方法原文提出 | 130000 count | (Dellaert & Kaess, 2006, Sec. 7.1; Fig. 13 caption) |
| EKF filtering covariance matrix (entries) | 500000 count | (Dellaert & Kaess, 2006, Fig. 13 caption) |
Dellaert & Kaess, 2006 · Text Sec.7.2 本方法 2 筆
資料集與序列synthetic simulation · 500 steps, 2000-landmark environment
表格設定（擷取紀錄原文）：Incremental square-root SAM versus a standard EKF, 500 time steps in a synthetic environment with 2000 landmarks (sparse LDL with symamd ordering) (Dellaert & Kaess, 2006, Text Sec.7.2)
number of landmarks seen when smoothing every step becomes cheaper than the EKF，synthetic simulation · 500 steps, 2000-landmark environment
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Dellaert & Kaess, 2006 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| incremental square-root SAM (LDL)本方法原文提出 | 600 landmarks | (Dellaert & Kaess, 2006, Sec. 7.2; Fig. 14) |
來源
Dellaert & Kaess, 2006
（2006）Square Root SAM: Simultaneous Localization and Mapping via Square Root Information SmoothingThe International Journal of Robotics Research, 25(12):1181-1203
同儕審查已出版已讀全文經典查證後修正