SFM算法流程
Figure1:Block diagram of structure from motion
1. 算法简介
SFM算法是一种基于各种收集到的无序图片进行三维重建的离线算法。在进行核心的算法structure-from-motion之前需要一些准备工作，挑选出合适的图片。
首先从图片中提取焦距信息(之后初始化BA需要)，然后利用SIFT等特征提取算法去提取图像特征，用kd-tree模型去计算两张图片特征点之间的欧式距离进行特征点的匹配，从而找到特征点匹配个数达到要求的图像对。对于每一个图像匹配对，计算对极几何，估计F矩阵并通过ransac算法优化改善匹配对。这样子如果有特征点可以在这样的匹配对中链式地传递下去，一直被检测到，那么就可以形成轨迹。之后进入structure-from-motion部分，关键的第一步就是选择好的图像对去初始化整个BA过程。首先对初始化选择的两幅图片进行第一次BA，然后循环添加新的图片进行新的BA，最后直到没有可以继续添加的合适的图片，BA结束。得到相机估计参数和场景几何信息，即稀疏的3D点云。其中两幅图片之间的bundle adjust用的是稀疏光束平差法sba软件包，这是一种非线性最小二乘的优化目标函数算法。
2. 算法详述
2.1计算符合特征的图片
2.1.1特征检测
对于特征检测这一步，使用的是具有尺度和旋转不变性的SIFT描述子,其鲁棒性较强，适合用来提取尺度变换和旋转角度的各种图片特征点信息，其准确性强，在这种离线算法不需要考虑时间成本的情况下也较有优势。SIFT算法通过不同尺寸的高斯滤波器(DOG)计算得到特征点的位置信息(x,y),同时还提供一个描述子descriptor信息，在一个特征点周围4*4的方格直方图中，每一个直方图包含8个bin的梯度方向，即得到一个4*4*8=128维的特征向量。除此之外，SIFT算法计算得到的尺寸scale和方向orientation两个信息并没有用上。2.1.2特征匹配
一旦每个图片的特征点被提出来以后，就需要进行图片两两之间的特征点匹配，用F (I)表示图像I周围的特征点。对于每一个图像对I和J，考虑每一个特征f ∈ F (I)找到最近邻的特征向量fnn ∈ F (J):
然而初选的匹配对可能还是不可靠，需要用几何约束去检测。这个测试是基于事实的，假设一个静止场景，不是所有的匹配特征点在实际场景中是符合物理规律的。那么就需要计算对极几何，F矩阵可以把两张图片之间的像素坐标联系起来，并包含相机的内参信息。每一个符合的匹配对像素坐标都需要满足：
当所有的两两匹配图像对被确定以后，就可以考虑把多个图像中都出现的共同特征匹配点连接起来，就能形成轨迹了。例如，特征f1 ∈ F (I1)匹配特征f2 ∈ F (I2)，f2匹配特征f3 ∈ F (I3) ,这些特征就可以形成一个轨迹{f1, f2, f3}。然后利用宽度优先搜索BFS去找到每个特征点在所有图像对中的完整轨迹。
一旦符合的轨迹都找到后，就构造图像连接图，包含每个图像的节点，和有共同轨迹的图像边缘。
2.2 Structure from motion
描述摄像机的外参数用到3*3的旋转矩阵R和1*3的平移向量(或者摄像机中心坐标向量)，摄像机的内参数用一个焦距f和两个径向畸变参数k1和k2描述。几何场景提供轨迹中的每个3D点Xj，通过投影方程，一个3D点Xj被投影到摄像机的2D图像平面上。投影误差就是投影点和图像上真实点之间的距离。如下图：
Figure2: Reprojection error
对于n个视角和m个轨迹，投影误差的目标优化方程可以写为:
首先选择合适的初始化图像对，这十分重要，一旦错误的初始化，将会陷入局部最优而使得之后的BA陷入死循环，无法正确求解得到全局最优。具体有两点要求：第一，要有足够多的匹配点；第二，要有足够远的相机中心。
特别的，在这里用到两个图像变换之间的单应性模型来找初始化图像对。如果不能很好的符合单应性模型，说明相机中心还是有一定距离的。同样采用RANSAC方法来降噪，改善匹配的可靠性，尽量选取低的内点百分比，但是至少保证100个匹配内点。
系统采用5点法来估计初始化匹配对的外参，然后轨迹三角化后可以提供初始化的3D点，初始化的两帧图片就可以开始进行第一次bundle adjustment了。在这里用的是稀疏光束平差法sparse bundle adjustment(SBA)。
最后，不断添加新的摄像机和3D点进行BA。这个过程直到剩下的摄像机观察到的点不超过20为止，说明剩下的摄像机没有足够的点可以添加，BA结束。得到相机估计参数和场景几何信息，即稀疏的3D点云。
