SFM通过分析一系列从不同、未知视角拍摄的二维（2D）照片，来同时地重建一个场景或物体的三维（3D）结构，并估算出拍摄每张照片时的相机位置和朝向，即输入照片，输出3D点云模型和相机路径。

两大类型

目前主流的 SfM（Structure from Motion，运动结构恢复） 方法主要分为两类：

全局式 SfM（Global SfM）
增量式 SfM（Incremental SfM）

全局式 SfM

基本思路
一次性求解所有相机的位姿，然后通过三角化获得场景点。
位姿估计分两步：
1. 全局旋转估计
2. 在已知旋转的基础上，全局平移估计
关键问题
- 第二步依赖第一步，因此 全局旋转估计的精度 决定了最终结果质量。
优缺点
- 优点：只需在最后进行一次 Bundle Adjustment (BA)，效率高。
- 缺点：鲁棒性差，容易被 outlier 干扰导致重建失败。

增量式 SfM

基本思路
一边进行 三角化 (Triangulation) 与 PnP (Perspective-n-Points)，一边执行局部 BA 优化。
优缺点
- 优点：鲁棒性高，对 outlier 不敏感。
- 缺点：效率较低，每加入一张图像都要 BA；误差会累积，可能产生漂移。

阶段1：对应关系搜索（Correspondence Search）=Feature Extraction+Matching+Geometric Verification

特征提取（Feature Extraction）

目标：在每张照片里找到一批“稳定且独特的小点”，方便后续跨照片对比。
每个局部特征包含两部分：
1. 位置 (Location)：点在图像中的像素坐标。
2. 外观描述子 (Descriptor)：这个点周围小区域的“指纹”（形状、纹理、颜色特征）。
关键要求：不变性 (Invariance)
- 同一个物理点，在不同光照或不同角度下，提取出的“指纹”要保持差不多。
- 这样才能在多张照片中把它认出来。

特征匹配（Matching）

目标：用特征点的“指纹（descriptor）”来比较不同照片里的点，找出那些可能属于同一个三维物理点的配对，形成 特征对应关系（feature correspondences）。
工作流程：
1. 提取完特征后，把它们当作照片的“内容描述”。
2. 找出哪些照片之间有场景重叠。
3. 在重叠照片中，逐一对比特征指纹，相似度最高的就认为是匹配点。
朴素方法（Naïve Matching）：
1. 任意挑两张照片 A 和 B。
2. 在 A 中选一个特征点，把它的指纹和 B 中所有特征点的指纹逐一比较。
3. 找到最像的那个，认定为一对匹配。
4. 对 A 中所有特征点重复上述步骤。
5. 再换下一对照片，直到遍历整个照片集。
问题：
- 计算复杂度非常高： $O (N_{I}^{2} N_{F_{i}}^{2})$ 。
- 照片/特征点一多，几乎不可用。
实际改进：
- 核心思想：避免 穷举搜索（exhaustive search）。
- 使用更高效的算法（如索引、近似最近邻、图像检索等）来提升匹配速度。
输出结果：
- 并不是直接得到三维模型。
- 而是生成一份 “潜在重叠图像对”列表：
  - 哪些图像可能有重叠；
  - 其中包含多少潜在匹配点。
- “潜在”表示匹配只基于外观相似，里面可能有很多错误匹配（outliers）。
- 下一步必须通过 几何验证 来剔除这些错误。

几何验证（Geometric Verification）

目标：验证基于外观的匹配点，在几何上是否也合理。
- 特征匹配只看“长得像”，不能保证一定是同一个三维点。
- 几何验证利用投影几何来检验匹配对是否符合空间约束。
基本思路：
如果两张照片拍的是同一个刚性场景，那么 A 图中的点和 B 图中的对应点，必须满足一个统一的几何变换模型。
具体模型取决于相机运动方式和场景结构。
常见几何模型：
1. 单应性 (Homography, H)
  - 适用情况：
    - 相机只旋转、不平移（如拍全景）。
    - 场景是平面（如拍海报）。
2. 对极几何 (Epipolar Geometry)
  - 适用情况：相机有平移，场景是三维结构。
  - 基础矩阵 (Fundamental Matrix, F)：未标定相机。
  - 本质矩阵 (Essential Matrix, E)：已标定相机。
  - 核心约束：A 图的点在 B 图中的对应点必须落在极线上。
3. 三焦张量 (Trifocal Tensor)
  - 三个相机视图的扩展模型，约束更复杂。
鲁棒估计方法：RANSAC
1. 随机抽取最少点数（如估 F 矩阵需 8 对点）。
2. 基于这些点计算一个假设模型（如 $F_{h y p o t h e t i c a l}$ ）。
3. 用该模型测试所有匹配点，统计符合的点（内点 inliers）。
4. 重复成百上千次，选出内点最多的模型作为最优结果。
5. 其余不符合的点判定为外点（outliers），丢弃。
输出结果：场景图（Scene Graph）
- 节点：图像。
- 边：两张图有重叠，并附带可靠的匹配点数。
- 功能：为后续的增量式重建提供唯一输入和路线图。

阶段2：增量式重建（Incremental Reconstruction）=Initialization+Image Registration+Triangulation+Bundle Adjustment

初始化（Initialization）

目标：从场景图中挑选一对最合适的图像，利用它们之间的可靠匹配，创建整个三维重建的种子模型（seed model）。
- 种子模型是第一个、最小的、自洽的三维场景，包含两台相机的精确相对位姿和一个初始三维点云。
- 后续所有图像都将在这个基础上逐步“嫁接”进来。
关键性：
- 选择正确的初始配对至关重要，如果初始化很差，后续重建可能永远无法恢复。
- 重建的稳健性、精度和性能取决于种子位置。
为什么糟糕的初始化是灾难性的：
1. 坐标系和尺度定义：初始化隐式决定了世界坐标系的原点、方向和尺度。若初始框架歪了，后面一切都会跟着歪。
2. 误差传播：若两张照片离得太近，三角化结果会有大深度误差，该误差会在增量过程中不断放大，甚至 BA 也难以修正。
策略：
- 优先选择场景图中相机重叠多、冗余度高的区域作为初始化 → 更鲁棒、更准确。
- 如果从稀疏位置初始化，虽然运行时间短，但精度和稳定性会下降。

图像配准（Image Registration）

目标：为一张尚未加入模型的新图像，精确计算它在三维空间中的位置和朝向（相机位姿 Pose）。
- 方法：找到新图像中的 2D 特征点，与已有三维点云中的 3D 点建立对应关系（2D-3D correspondences），然后解 PnP（Perspective-n-Point）问题。
前提条件：必须已经有一个度量重建（metric reconstruction），即通过初始化得到的、带真实尺度（或一致尺度）的初始三维模型。
关键词解释：
1. 2D-3D 对应关系
  - 2D 点：新图像中的特征点像素坐标。
  - 3D 点：在已有点云中对应的三维坐标。
2. PnP 问题
  - 类比：你在一个陌生地方，能看到几个地标，并且手里有一张地图，上面标着地标的三维位置。
  - 通过测量这些地标在你视野中的方向和大小，你就能推算出自己当前的空间位置和朝向。
  - 输入：至少 $n$ 对 2D-3D 对应关系。
  - 输出：相机的 6 自由度位姿 (6-DoF Pose) = 位置 $(x, y, z)$ + 朝向 $(ro ll, p i t c h, y a w)$ 。
情况区分：
1. 已标定相机：内参已知，只需求解 6 个位姿参数。
2. 未标定相机：内参未知，需要同时求解位姿和内参（如焦距），问题更复杂，需更多对应点。
鲁棒估计：
- 2D-3D 对应关系里常有外点（错误匹配）。
- 解决办法：用 RANSAC + 最小姿态求解器，与几何验证的流程类似。

三角测量（Triangulation）

目标：利用至少两个已知位姿的相机，对同一个二维特征点的观测，计算该特征点在三维空间中的精确坐标。
前提条件：
- 新配准的图像必须能看到一部分已经存在的三维点（否则无法完成 PnP 定位）。
- 同时，新图像也能通过三角测量，帮助生成新的三维点，扩展场景覆盖范围。
核心机制：
1. 生成新点：当一个新图像与至少另一张不同视角的图像共同覆盖某个新区域时，就能通过三角测量生成新的 3D 点。
2. 冗余增强稳定性：
  - 一个点只被两张照片看到时，三维位置可能不太精确。
  - 如果后续更多照片（3、4、5 张）也看到这个点，就能利用更多观测来优化其坐标，使其更稳定、更准确。
3. 为未来配准提供地标：
  - 新生成的三维点会成为下一轮图像配准的“参照物”。
  - 当新图像加入时，它通过匹配这些三维点来计算位姿。
重要性：
- 三角测量是 SfM 增量式循环的核心环节。
- 没有三角测量，三维点云不会增长，新图像也无法获得足够的 2D-3D 对应点用于 PnP 定位，最终会导致重建停滞。

捆绑调整（Bundle Adjustment, BA）

目标：对当前模型中所有已知参数（相机位姿、相机内参、三维点坐标）进行全局、非线性优化，以最小化整体的重投影误差。
背景：
- 图像配准（Image Registration）和三角测量（Triangulation）虽然是分开的步骤，但它们的结果强相关。
  - 相机位姿的不确定性会传递到三角测量的三维点。
  - 三角测量的不确定性也会反向影响相机位姿。
- 如果不进行进一步优化，SfM 容易因误差累积而快速漂移，进入不可恢复的状态。
定义：
- BA = 联合非线性优化
- 同时调整：
  - 相机参数 $P_{c}$
  - 三维点参数 $X_{k}$
- 目标：最小化重投影误差（Reprojection Error）。
公式（重投影误差）：
$E = j \sum i \sum ρ (∥ x_{ij} - π (P_{i}, X_{j}) ∥^{2})$
- $E$ ：总误差。
- $x_{ij}$ ：图像 $i$ 中观测到的特征点像素坐标。
- $π (P_{i}, X_{j})$ ：根据相机参数 $P_{i}$ 和三维点 $X_{j}$ 投影得到的预测位置。
- $ρ (\cdot)$ ：鲁棒函数，降低外点的影响。
解释：
- 预测位置：根据当前估计的三维点和相机参数，通过投影函数 $π$ 计算出的像素位置。
- 现实位置：在特征提取阶段实际检测到的像素坐标，是唯一的观测“真值”。
- 误差：两者之间的差距。
特点：
- BA 把所有相机和三维点都放到一个大的优化问题中，一次性求全局最优。
- 从 3D 到 2D 的投影是非线性的（涉及除法），因此优化过程复杂，需要迭代算法。
- 常用优化器：Levenberg-Marquardt 算法（论文中提到）。

阶段3（可选）：稠密后贴图（MVS → Texturing and Model Generation）

Dense Reconstruction（MVS）

After sparse point clouds are obtained, further algorithms can interpolate and densify the reconstruction, producing a detailed 3D model.

Texturing and Model Generation

The final step may involve generating a mesh and applying textures from the original images for realistic visualization.

常见开源实现

Colmap：采用 增量式 SfM pipeline，鲁棒性强，应用广泛。
OpenMVG：同时实现了 增量式 和 全局式 两种 pipeline，供用户选择。

误差来源

特征提取与匹配错误
- 来源：纹理重复、模糊、光照变化、低对比度、水印/边框（WTF）等。
- 影响：错误对应→错误的两视几何→错误连接的 track → 假点 / 错误相机位姿。
- 缓解：用 RootSIFT / 学习型描述子、ratio test、交叉验证、检测并剔除 WTF 对（论文有专门讨论）。
几何验证与模型选择错误（单应/本质/基础矩阵判断）
- 来源：平面场景、纯旋转、视差太小导致模型混淆。
- 影响：错误标注为可用对，会导致退化三角化与位姿问题。
- 缓解：多模型验证（估计 F、H、E 并比较 inlier 比率），跳过全景/平面对作为初始化。
相机内参（自标定）误差
- 来源：初始焦距/畸变估计不准、主点不可辨识、过度自由化导致收敛到假解。
- 影响：系统性尺度/投影偏差，后续 BA 难收敛或发散。
- 缓解：对无先验的情况保持主点固定为图像中心、限制畸变范围、只在有足够观测时自标定。
三角化与几何条件差（baseline 小、三角角小）
- 来源：视角接近、两视基线短。
- 影响：深度不确定性大、点位置噪声呈大方差。
- 缓解：避免用纯旋转对三角化；设最小三角化角阈值；利用跨更大基线的传递匹配（transitive matches / track 扩展）。
外点 / track 合并错误（track 中混入多点）
- 来源：错误两视对应把不同点合并进一个 track。
- 影响：RANSAC/三角化失败或产生错点。
- 缓解：对 track 使用递归 RANSAC 分解（论文提出了 robust recursive triangulation），只接受满足 cheirality 和 reproj error 的子集合。
BA（Bundle Adjustment）问题：局部最优 / 漂移 / 计算量大
- 来源：初始解差、过多异常观测、模型参数过多。
- 影响：整体模型漂移、错误相机、长时间计算。
- 缓解：使用鲁棒损失（Cauchy），迭代 BA + re-triangulation + 过滤的循环策略；对高冗余影像做分组参数化（grouped BA）以提速且减少过拟合。
传感器/物理误差：滚动快门、曝光差、同步不一致、图像噪声
- 影响：投影模型与真实不符，增加残差分布尾部。
- 缓解：必要时校正滚动快门或剔除不良帧；提高匹配阈值；在 BA 中采用更强鲁棒项。

常用诊断指标（应首先检查）

重投影误差的中位/均值（median/mean reproj error）。
Track 长度分布与 inlier ratio（短 track 与低 inlier ratio 表示大量错配）。
三角化角度直方图（大量 <2° 的点说明条件差）。
被过滤/剔除的相机数量与内参异常（说明自标定问题）。
模型连通性（scene graph 中孤立子图/断裂），以及重建覆盖率。

立刻可用的实践步骤（按优先级）

在匹配阶段：采用 RootSIFT + ratio test + NN-cross check；剔除边框/水印对（multi-model检测）。
几何验证：同时估计 H/F/E，按 NH/NF、NE/NF 决策模型类型，跳过全景对做初始化。
初始化：选择图中重连通、覆盖均匀的种子对（paper 的 next-best-view score）。
三角化：用递归 RANSAC 分解 track（recover multiple points），设最小三角角阈值并检查 cheirality。
优化循环：做 local BA → 过滤高残差观测 → re-triangulate → 再次 BA（通常两次迭代即可显著提升）。
BA 加速：对高度冗余的视图做 group parameterization（redundant view mining），减小 BA 规模同时保持精度。

关键公式（便于记笔记）

重投影误差（BA 优化目标）：
三角化角（用于判断几何条件）：
RANSAC 迭代上界（用于计算需要的采样次数）：

My Notes

Explorer

SfM, Structure-from-Motion

两大类型

全局式 SfM

增量式 SfM

阶段1：对应关系搜索（Correspondence Search）=Feature Extraction+Matching+Geometric Verification

特征提取（Feature Extraction）

特征匹配（Matching）

几何验证（Geometric Verification）

阶段2：增量式重建（Incremental Reconstruction）=Initialization+Image Registration+Triangulation+Bundle Adjustment

初始化（Initialization）

图像配准（Image Registration）

三角测量（Triangulation）

捆绑调整（Bundle Adjustment, BA）

阶段3（可选）：稠密后贴图（MVS → Texturing and Model Generation）

Dense Reconstruction（MVS）

Texturing and Model Generation

常见开源实现

误差来源

常用诊断指标（应首先检查）

立刻可用的实践步骤（按优先级）

关键公式（便于记笔记）

Graph View

Table of Contents

Backlinks