基于Bundler、CMVS的3D重建
本周我们调研各种重建方法，尝试各种一直算法。尝试进行3D重建。最终我们选择用Bundler+CMVS的方法。这两个方法已经被实现为两个软件，我们主要仔细研究学习了两个算法的原理，并且调试炮筒代码，将两个软件封装在一起，组成一个可以通过一行运行的软件，方便地进行3D场景重建。
这里对整个过程做一个总结。
概览
从多幅图片进行场景重建（3D Scene Reconstruction and Rendering from Multiple Iamges），就是从一系列2D图片中，创建3D模型。它是从3D场景中获取2D图像的逆过程。深度信息的缺失构成此时面临的最大问题。也就是说对于一个2D图像上的点，你只能确定他是出现在一条空间上的一条直线（视线）上的，并不能确定它在这条直线的哪个位置。这个时候用到的技术称为三角测量法（Triangulation）.也就是说，当你有两张图片，那么一个点的空间位置可以由两张图片中该点所在的投影射线的交点确定。那么做Triangulation的关键确定两张图片或者说两个视图的相对位置以及它们之中相互对应的点。
流程
3D重建的大体过程为：特征提取与匹配、相机姿态和位置的估计、稀疏\稠密3D重建。大体过程如图１。
特征提取与匹配
图２显示的是特征匹配的过程。从各张图片中找出特征点（利用SIFT等算法），进行匹配，然后找到图片之间的集合约束关系，构建出一个几何图。
相机姿态和位置的估计
图３表示的是计算本质矩阵（Essential Matrix）的过程，具体过程是求解一个线性方程组。
图４表示的是根据由前量幅图像重建的三维点（x）和第三幅图像中的对应点利用校准法计算第三个相机矩阵（Pi）的过程。
稀疏重建
稀疏重建需要结合上述相机的姿态和位置估计。具体来讲，首先需要通过求解初始图片对儿的线性方程组来估计本质矩阵，对相机矩阵做一个不太精确的估计，然后每加入一张图片估计一个新的相机矩阵，然后通过光束平差法（Bundle Adjustment）进行三维点位置的精确计算。重复这一过程知道没有新的相机矩阵呗计算出来。流程图如图５所示
【光束平差法（Bundle Adjustment）：由于计算投影重建的时候有许多对应点可用，需要采用非线性最小二乘(Levenberg-Marquardt)求解，以最小化二次投影误差。针对这个问题的非线性最小二乘法来自于摄影测量中的光束平差法。】
我们采用的同样是这个流程。该流程建立在小孔成像模型的基础上，需要估计的具体参数有焦距（focal length）,径向畸变（k1, k2），旋转矩阵(R)和平移矩阵（T）。从三维空间点到相机点的映射可以表示为：
P = R * X + t (conversion from world to camera coordinates)
p = -P / P.z (perspective division)
p' = f * r(p) * p (conversion to pixel coordinates)
其中P.z是P的第三个轴，r(p)为
r(p) = 1.0 + k1 * ||p||^2 + k2 * ||p||^4.
因此根据上式，得到相机的朝向为:
R' * [0 0 -1]' (i.e., the third row of R or third column of R')
相机的位置为：
-R' * t .
上述整个流程通常叫做运动恢复结构（Structure from motion, SfM）。
到目前为止的具体实现
截至目前，我们具体实现了以下几个步骤。然后将这些步骤通通包装在一起，最终在Ubuntu Linux 14.04上运行的命令只有一行，无论是稀疏重建还是稠密重建。
预处理
SIFT特征提取
利用Bundler进行SfM稀疏重建
利用CMVS(Clustering Views for Multi-view Stereo)进行稠密重建
（下截图取自重建两个瓶子的场景的重建）
###预处理
由于后边我们使用了David Lowe的SIFT程序，而它要求输入图片的长宽都不能超过4000，所以我们需要对超出的图片进行缩放。缩放比例可以自己设置。 然后要提取图片的EXIF信息，信息中包含相机的生产商、相机型号和实际焦距(mm为单位)等。需要注意的是，如果使用自己的只能手机进行拍照，必须事先查询相机的型号并找到其ccd传感器的宽度。然后才能计算出以像素为单位的焦距值，这是必要的。具体如何将ccd宽度加入到程序中可以看之后我们写的readme.md。
###特征提取
我们的特征提取采用最初的SIFT算法，由David Lowe提出。直接调用其可执行二进制文件即可。当然也可以采用其他改进后的SIFT算法，但是注意的是如果后面要使用Bundler进行稀疏重建，sift提取的结果数据形式必须和David Lowe的形式完全相同。
###利用Bundler进行SfM稀疏重建
Bundler实现了一整套的SfM流程，包括相机的标定校准和点云的计算。具体原理已经在上边详细介绍过。（加building rome in a day中的描述）这样重建出的结果是稀疏的点云。
feature matching and bundle adjustment
###利用CMVS进行稠密重建
CMVS(Clustering Views for Multi-view Stereo)[http://www.di.ens.fr/cmvs/] 可以将大量的输入图片分解到不同的类，并在每一个类中并行地进行重建。这样得到的每一个类的重建结果是原图的一部分，最后整合在一起。这种分成局部并行重建的方法可以大大提高输入图片较多时的重建速度。
然后就可以利用Meshlab等软件进行显示。
这里边展示我们的几组结果，密码：123456
公开数据：
狮子头稀疏重建
