sfm，即structure from motion。从一堆同一场景的照片中恢复场景的三维结构和照片拍摄时相机的位置，可分为全局sfm和增量式sfm。

全局sfm主要包括以下步骤：

1.提取各张照片上的特征点及其描述；

2.对所有照片相互进行特征点匹配；

3.根据匹配的特征点计算照片i到照片j的相互位置关系（本质矩阵5点算法，或其它算法），得到view graph；

4.对相互位置关系进行准确性验证（validation check）；

5.根据照片两两之间的匹配点数或者匹配误差，从view graph 中提取maximum spanning tree 用于计算各个照片在全局坐标系下的旋转初值；

6.通过view graph 进行rotation averaging获取各照片在全局坐标系下的旋转值；

7.使用全局旋转进行translation averaging获取各照片在全局坐标系下的平移量（或者同时获取了匹配点三维坐标值）；

8.进行最终的光束平差优化。

近十年该领域的发展主要集中在rotation averaging和translation averaging这两方面的鲁棒性和精确性提升。

根据以上pipeline，编程实现了以上7个步骤。对一段视频提取拍摄相机的运动数据（未知相机内参数，图像畸变很小，下载地址http://download.csdn.net/download/j10527/10168529），结果见下图：

view graph如下，越亮表示匹配点越多

validation check通过的如下白色所示，未通过为灰色。

maximum spanning tree如下图所示：