### 2013 vsfm Towards Linear-time Incremental Structure from Motion
#### 摘要与背景
本文讨论了结构从运动（Structure from Motion, SfM）中的增量法，并提出了一个能够实现近似线性时间复杂度的方法。传统上，增量SfM的时间复杂度被认为是O(n^4)，其中n代表摄像头的数量。然而，随着预条件共轭梯度（Preconditioned Conjugate Gradient, PCG）方法在束调整（Bundle Adjustment, BA）中的显著改进，重新评估增量SfM的速度变得尤为重要。
#### 方法论与贡献
文章主要介绍了以下几点创新之处：
1. **预选特征匹配**：这是一种能够减少图像对之间匹配比例高达95%的技术，同时仍然能保证足够好的匹配结果用于重建过程。
2. **共轭梯度束调整的时间复杂度分析**：通过理论分析和实验验证，作者证明了在实践中束调整的时间复杂度为O(n)。
3. **增量SfM中的子步骤优化**：文章展示了使用一种新颖的束调整策略时，包括束调整和点过滤在内的许多子步骤实际上只需要O(n)的时间。
4. **定期重新三角化**：为了保持高精度，文章提出了一种定期重新三角化那些最初未能成功三角化的特征匹配点的方法。
#### 实验验证与结果
为了验证所提出方法的有效性，作者在大量的照片集合和长视频序列上进行了测试，这些数据集具有不同的设置。结果显示，在大规模重建任务中，该方法的表现达到了当前的最佳水平。
#### 结论与展望
通过上述贡献，作者不仅提高了SfM的效率，还实现了低复杂度和高可扩展性，这对于处理大规模场景组件至关重要。该算法作为VisualSFM的一部分，可在<http://homes.cs.washington.edu/~ccwu/vsfm/>获得。
#### 重要概念详解
1. **增量结构从运动（Incremental Structure from Motion）**：
- 增量SfM是一种逐步构建三维模型的技术，它通过不断地将新的图像添加到现有的模型中来逐步扩大模型规模。这种方法通常比一次性处理所有图像更有效率。
2. **束调整（Bundle Adjustment）**：
- 束调整是一种非线性最小二乘优化技术，用于改善3D重建的精度。它通过最小化所有观测值与预测值之间的差异来优化相机参数和3D点的位置。
3. **预条件共轭梯度（Preconditioned Conjugate Gradient, PCG）**：
- PCG是一种加速求解大型稀疏线性系统的迭代方法，它通过预处理矩阵来改善收敛速度。在束调整中，PCG方法的引入极大地提高了优化过程的效率。
4. **预选特征匹配（Preemptive Feature Matching）**：
- 预选特征匹配是一种高效的方法，用于减少图像间匹配的计算负担。通过预先筛选出最有可能匹配的特征点，可以显著降低匹配对的数量，从而提高整个流程的效率。
5. **定期重新三角化（Regular Retriangulation）**：
- 定期重新三角化是指在SfM过程中，定期重新计算那些未能成功进行三角化的特征点的位置。这有助于提高模型的准确性和完整性。
6. **线性时间复杂度（Linear Time Complexity）**：
- 线性时间复杂度表示算法运行时间与输入大小成正比。对于SfM来说，达到O(n)的时间复杂度意味着处理每个图像或摄像头所需的时间是恒定的，这对于处理大规模数据集非常重要。
通过一系列技术创新和优化，作者成功地提高了增量SfM的效率，并且在不牺牲精度的情况下实现了近似线性时间复杂度。这项工作对于推动结构从运动领域的研究和发展具有重要意义。
