Structure from Motion

Structure-from-Motion (SfM) 流程

![[Pasted image 20251006192355.png]]

座標系（Coordinate Systems）

在 Structure-from-Motion (SfM) 或任何視覺觀測問題中，通常涉及三個座標空間：

Global 3D Space (coordinate) 物體在全域三維空間中的位置，例如以世界為原點的 world coordinate system。
Local 3D Camera Space (coordinate) 物體在相機的局部三維座標系中。相機的 pose（姿態）（即位置與方向）決定了此局部座標與全域座標之間的轉換關係。
Local 2D Pixel Plane (coordinate) 這是影像平面上的像素座標，是將局部相機座標中的三維點投影（projection）到二維平面上的結果。

這三個空間之間的轉換由 線性代數（linear algebra） 所描述：

從 (1) Global 3D space → (2) Local 3D camera space 是一個可逆的剛體變換（rigid transformation），包含旋轉矩陣 $R$ 與平移向量 $t$： $X_{camera} = R (X_{world} - t)$
從 (2) Local 3D camera space → (3) Local 2D pixel plane 是一個投影轉換（projection transformation），通常用針孔相機模型表示： $x = K [R | t] X_{world}$ 其中 $K$ 是 intrinsic matrix（內部參數矩陣）。

此投影的反向（從 2D 回推 3D）是病態問題（ill-conditioned）：若不知相機姿態（camera pose）與深度（depth），則無法唯一決定 3D 位置。這正是為什麼需要 Bundle Adjustment (BA) —— 同時估計場景中物體的 3D 座標與相機的姿態，使重投影誤差最小化。

天文觀測的類比

一個非常好的例子來自天文觀測。自伽利略以來，觀測天空中的天體一直是理解 SfM 精神的最佳範例之一：

天空中的 恆星（fixed stars） 相當於一組穩定的背景點。
行星（planets）、小行星（asteroids）、彗星（comets）、衛星（moons 或人造衛星） 則是少數移動的目標物體。
若以太陽為原點的三維座標系，可視為 Global 3D space。
若以地球為原點，則為 Local 3D camera space。地球的位置與姿態（pose）會隨時間改變。
實際的觀測結果，是在地球上以望遠鏡或相機所獲得的 Local 2D pixel plane。由於我們不知道各天體的距離，這與 SfM 的投影問題完全類似。

高斯（Gauss）正是基於大量觀星數據，發展出 最小平方法（least squares method），能夠同時推論出恆星（固定點）、行星（移動點）以及地球的運動軌跡（相機姿態）。這個原理後來在電腦視覺中被延伸為 Structure-from-Motion (SfM)：藉由多張影像，推測出場景的 3D 點雲（3D point cloud） 與 camera poses（相機姿態）。

上圖展示了 SfM 的主要步驟 —— 這是一種電腦視覺技術，用於從多張不同視角的 2D 影像重建 3D 結構。以下為各步驟說明：

1. Input Images（輸入影像）

多張同一場景（如比薩斜塔）的重疊影像，從不同角度拍攝。 → 作為 3D 重建的原始資料。

2. Feature Extraction（特徵擷取）

使用 SIFT、SURF 或 ORB 等演算法，偵測與描述影像中的關鍵特徵點（keypoints）。 → 產生可識別的特徵描述子（feature descriptors）。

3. Image Matching（影像匹配）

比對影像間的特徵描述子，找到相同實體點的對應關係。 → 建立影像對之間的匹配（matched feature pairs）。

4. Estimate Camera Poses（相機姿態估計）

根據對應點計算相機的外部參數（extrinsics：旋轉與平移）。 → 常用 epipolar geometry（對極幾何） 和 RANSAC 來濾除誤配點。

5. Triangulate 3D Points（三角化 3D 點）

利用相機姿態與對應的影像點進行三角測量，重建場景中點的 3D 座標。 → 產生稀疏點雲（sparse point cloud）。

6. Bundle Adjustment（束調整）

以 nonlinear optimization（非線性最佳化） 同時優化 3D 點與相機姿態，最小化 reprojection error（重投影誤差）。 → 常用 Ceres Solver 或 Levenberg–Marquardt。

7. Final Reconstruction（最終重建）

整合所有優化後的 3D 點，生成稀疏的 3D 模型。 → 可透過 Multi-View Stereo (MVS) 進一步產生密集重建（dense reconstruction）。

SfM Pipeline 流程摘要

步驟	說明	主要輸出	常用算法（Algorithm）
1. Input Images	多張同一場景的 2D 影像	Image dataset	—
2. Feature Extraction	偵測關鍵點與特徵	Keypoints & Descriptors	SIFT, SURF, ORB, AKAZE
3. Image Matching	找出影像間的特徵對應點	Matched image pairs	Brute-Force Matcher, FLANN, KNN Matching, + RANSAC（過濾錯誤匹配）
4. Estimate Camera Poses	計算每張影像的相機位置與方向（相機外部參數）	Camera extrinsics	Epipolar Geometry, Essential / Fundamental Matrix Estimation, RANSAC, PnP (Perspective-n-Point)
5. Triangulation	利用相機姿態與匹配點重建 3D 點	Sparse 3D Structure	Linear / Nonlinear Triangulation, DLT (Direct Linear Transform)
6. Bundle Adjustment (BA)	聯合最佳化 3D 結構與相機姿態	Refined 3D Model	Levenberg–Marquardt (LM), Ceres Solver, g2o
7. Final Reconstruction	組成完整 3D 模型，可延伸為密集重建	Dense 3D Point Cloud / Mesh	MVS (Multi-View Stereo), PMVS, COLMAP Dense, OpenMVS

🔍補充說明：

Feature Extraction (特徵擷取)： 決定整個 SfM pipeline 的穩定性與準確性，SIFT 通常最穩但較慢；ORB 則較快、適合即時應用。
Image Matching (影像匹配)： 一般先用 descriptor distance（例如歐式距離）比對，再用 RANSAC 過濾掉 outliers。
Pose Estimation (相機姿態估計)： 可用 Essential Matrix（若相機已知內參）或 Fundamental Matrix（未知內參）。
Bundle Adjustment (束調整)： 是整個 SfM 的核心最佳化步驟，常用 Ceres Solver（Google 開源）或 g2o 進行非線性最小平方法。
MVS（Multi-View Stereo）： SfM 通常產生稀疏點雲，MVS 負責將其 densify（密集化），生成更細緻的 3D 模型。

Appendix

Appendix A: **Gauss’s Least Squares Method（最小平方法）

Origin

Invented by Carl Friedrich Gauss (early 19th century).
Developed to fit models to astronomical observations (e.g., orbits of planets and asteroids).
Assumes that measurement errors are small and Gaussian-distributed (normal distribution).

Mathematical principle

Minimize the sum of squared residuals between observed data and model predictions:

\[\min_{\theta} \sum_i (y_i - f(x_i; \theta))^2\]

where

$(x_i, y_i)$: observed data,
$f(x_i; \theta)$: model prediction, typically nonlinear function
$\theta$: parameters to estimate.

Characteristics

Deterministic: given all data, there’s one optimal solution.
Requires good data: assumes most data points are correct and errors are random (no large outliers).
Optimal in a statistical sense: if noise is Gaussian, least squares gives the maximum likelihood estimate (MLE).

Used in

Astronomy (orbit estimation)
Photogrammetry
Bundle Adjustment in SfM (nonlinear least squares)
Regression, curve fitting, sensor calibration

Appendix B: RANSAC（RANdom SAmple Consensus）

Origin

Introduced by Fischler & Bolles (1981).
Designed for computer vision and robotics, where data often contains many outliers (wrong matches).

Mathematical principle

Instead of fitting to all data, RANSAC repeatedly:

Randomly selects a minimal subset of data points.
Fits a model using only that subset.
Counts how many data points in the whole dataset agree (are within a tolerance) with this model — these are inliers.
Keeps the model with the highest consensus.
Optionally refines it using least squares on the inliers.

Characteristics

Robust to outliers: can tolerate >50% wrong data.
Stochastic: uses random sampling; result may vary per run.
Iterative: runs many times until the probability of finding a good model is high.

Used in

Computer vision tasks: fundamental matrix estimation, homography, camera pose estimation.
Any scenario with noisy feature correspondences (e.g., SfM’s early stage before bundle adjustment).

Appendix C: 高斯最小平方法, Levenberg–Marquardt, Ceres Solver

Let’s unpack this carefully, because: 👉 高斯最小平方法 (Gauss’s Least Squares Method) is the principle, 👉 while Ceres Solver and Levenberg–Marquardt (LM) are numerical implementations or algorithms built upon that principle.

🧠 一句話總結

高斯最小平方法（Least Squares） 是目標， Levenberg–Marquardt 是實現這個目標的「演算法」， Ceres Solver 是能執行這種演算法的「軟體框架」。

⚙️ 一步步理解

1️⃣ 高斯最小平方法 (Gauss’s Least Squares Method)

概念性理論（Principle / Objective）

起源：高斯（Gauss）在 1809 年為了處理天文觀測誤差提出。
目的： 找出一組參數，使得模型預測值與觀測值之間的「平方誤差總和」最小。

\[\min_{\theta} \sum_i | y_i - f(x_i; \theta) |^2\]

適用於：線性或非線性模型。
如果模型是線性的（例如 $f(x_i; \theta) = a x_i + b$），可以直接用矩陣運算解封閉解。
如果是非線性的，就要靠「疊代法（iterative methods）」近似求解。

💡 關鍵思想： 假設誤差是高斯分布的，最小平方解就是最大概似估計（MLE）。

2️⃣ Levenberg–Marquardt (LM) Algorithm

實際求解「非線性最小平方」的演算法（Algorithm）

由 Levenberg (1944) 和 Marquardt (1963) 提出。
是一種 介於 Gauss–Newton 與 Gradient Descent 之間的混合演算法。

🔹 基本思想：

對非線性模型 $f(x; \theta)$，做泰勒展開後求近似： $J(\theta) = \sum_i (y_i - f(x_i; \theta))^2$

LM 會在每次疊代中解以下修正方程： $(J^T J + \lambda I), \Delta\theta = J^T (y - f)$ 其中

$J$：Jacobian 矩陣（偏導數），
$\lambda$：damping 係數（控制步伐）。
當 $\lambda$ 很小 → 像 Gauss–Newton，快速但可能不穩。
當 $\lambda$ 很大 → 像 Gradient Descent，穩定但慢。
LM 會根據每次效果自動調整 $\lambda$。

✅ 優點：

在模型非線性時仍能穩定收斂。
適合於 Bundle Adjustment、相機校正、曲面擬合 等。

⚠️ 缺點：

需要雅可比矩陣 (Jacobian)，對大型問題運算量大。

3️⃣ Ceres Solver

現代化的數值最佳化框架（Software Implementation）

由 Google 開發的 C++ 開源非線性最小平方求解器。
支援多種求解策略，包括：
- Levenberg–Marquardt (LM)
- Dogleg Method
- Gauss–Newton
- Trust Region Policy
內建自動微分（Automatic Differentiation），幫你算 Jacobian。
極度適合大型問題，例如：
- Bundle Adjustment in SfM / SLAM
- Camera calibration
- Sensor fusion
- Robotics trajectory optimization

🧩 簡單說：

Ceres = 「非線性最小平方」問題的工具箱，裡面有 LM、GN、Dogleg 等演算法可選，使用者只要定義好 cost function 就能執行。

🔍 對比表

項目	高斯最小平方法 (Least Squares)	Levenberg–Marquardt (LM)	Ceres Solver
角色	理論基礎 / 數學目標	求解演算法	軟體實作框架
主要用途	定義「要最小化的誤差」	在非線性模型中找到參數解	高效執行 LM/GN/Dogleg 等演算法
核心思想	最小化誤差平方和	結合 Gauss–Newton 與 Gradient Descent	利用高效線性代數庫與自動微分優化
是否需要 Jacobian	理論上需要	必須要	自動或手動提供
適用範圍	任意誤差模型	非線性最小平方問題	大規模、多視角、SLAM、SfM
是否開源軟體	否	否（是一種數學方法）	✅ 是

🧩 在 SfM（Structure-from-Motion）中三者如何串起來：

步驟	工具/概念
定義誤差函數（reprojection error）	高斯最小平方法的概念
設計疊代更新算法以最小化誤差	Levenberg–Marquardt 演算法
用高效框架執行、微分、收斂控制	Ceres Solver

最終目標：

同時優化所有相機姿態 (camera poses) 與 3D 點座標，讓重投影誤差最小化。