【强基固本】一文详解colmap中的多视图重建算法原理

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—JeffWang

地址：https://zhuanlan.zhihu.com/p/480829222

做Multi-View Stereo (MVS) 以及 Structure-from-Motion (SfM) 的同学对COLMAP这个词应该不陌生， COLMAP[1] is a general-purpose SfM and MVS pipeline with a graphical and command-line interface. It offers a wide range of features for the reconstruction of ordered and unordered image collections. 说白了， COLMAP是用来做SfM或者MVS的软件，该软件内的算法主要从两篇文章中提炼出来：（1）Structure-from-Motion Revisited[2](2) Pixelwise View Selection for Unstructured Multi-View Stereo[3]. 本文主要针对COLMAP在MVS中的算法原理进行paper解读，即解读第二篇文章。

Pixelwise View Selection for Unstructured Multi-View Stereo发表在2016年的ECCV，由ETH的Marc Pollefeys大佬组发表。本篇知乎blog首先给出该篇文章想要解决的问题 (Problem to be addressed)，然后分析其解决方案 (Methods)，更多的细节可以参考原文。

01

Problem to be addressed

"This work presents a Multi-View Stereo system for robust and efficient dense modeling from the unstructured image collection." 这句话是摘要的第一句话，作者想要提出一个的MVS模型，使它能够从unstructured图像输入中稠密重建出3D场景。这并不是说在这篇文章之前没有相关的方案，只不过之前的方案存在一些问题 (1) 重建的accuracy, completness, robustness, efficiency都不令人满意。（2）尤其是在uncontrolled场景（unstructured图像输入，输入图像尺寸不一样，光照不一样等），重建结果更令人堪忧。为了解决这些方案，作者提出了以下解决方案。

02

Method

作者为了使模型更加robust，一共在baseline[4]上提出了6点算法细节的改进。在详细描述算法改机之前，我们先看一下先前的MVS baseline是怎么解决问题的。

Review of Baseline

给定reference图像    以及source images    ，对于reference上的第    个像素点    ,我们想要估计他的深度    。为了估计深度，我们比较  和    （homography-warped source patch）的颜色相似度：

其中    是遮挡标签，    和   是归一化因子，    是均匀分布，    是两个patch之间的颜色相似度，通过Normalized Cross-Correlation (NCC)计算得到。    是smooth系数。

除了颜色相似度之外，还需要遮挡标签的平滑化指标函数  ，越大的    将鼓励更加平滑的遮挡标签指标。至此为止，我们可以得出joint probability：

该式可以通过variational inference求解最优的深度：

其中    是一种衡量相似度的概率函数（和    相关，但是此处不再展开）。上式可以进一步加速，只关注    比较大的情况，因此：

其中    选取的是   比较大的source images。

至此位置，说完了baselinede做法，下面开始说本篇paper的几点改进：(1) Pixelwise normal estimation. (2) Pixelwise view selection . (3) Integration of a “temporal” view selection smoothness term. (4) Adaptive window support through bilateral photometric consistency. (5) Introduction of a multi-view geometric consistency term for simultaneous depth/normal estimation and image-based fusion.

Pixelwise Normal Estimation

上面提到的baseline在做homography-warping的时候使用了fronto-parallel 假设，这会导致artifacts for oblique structure。所以我们在估计深度的同时估计surface normals。做法比较简单，只是在之前的基础上多估计了一个    ：

在PatchMatch这个框架中propagate nromal和depth，作者提出了一种first-order smoothness的方法：即给定深度    和法向量    ,我们可以确定3D空间中的一个平面，其他像素ray与该平面的交点可以算出传播到其他像素的深度。

Pixelwise View Selection

对于unstructured image输入，pixelwise view selection可以大大提升robustness，具体来说，本文利用三种指标去选择view：（1）Triangulation Prior去选择基线比较合适的source image；（2）Resolution Prior去选择分辨率和reference近似的source views；（3）Incident Prior去选择normal正常的view（因为不可能拍摄到物体的背面，所以normal应该在0-90°）

Triangulation Prior：首先刻画两张图片的拍摄夹角：   ，其中    ,    是source相对ref的旋转平移，    是一个阈值，如上图左2，夹角在15°附近是比较好的。

Resolution Prior：unstructured图像输入经常含有分辨率不同的图像，但是分辨率不同会导致在分辨率小的图像patch中oversampling的问题，为了优化该problem，作者定义了两个patch之间的尺寸比值：    ，作者希望最小化    ,这样就可以让两个图像的分辨率尽可能接近。如上图左三可以看出，两个resolution比值为1的时候是最优的。

Incident Prior：我们之前估计得到surface normal，那么自然而然就存在一个约束：我们得到的normal（相对于source image来说）应该在0~90°之间（最好是0°，因为此时source image得到的信息是最丰富的），大于90°时我们无法拍摄到物体的背面。我们首先计算incident angle：  ,然后最小化    ,在这里并没有限制一定要在90°以内，是因为刚开始计算出来的深度和normal不一定准确，会导致incident angle在90°以上。如上图最右可以看出，incident angle小于50°是比较好的。

综上，我们想要优化以下联合概率：

其中我们用    作为    的近似，这样可以用variational inference最小化该联合概率。

View Selection Smoothness

在上文baseline我们提到，我们利用让遮挡标签尽可能的平滑化，但是这还不够，本文又加入了“时序平滑约束”，即在PatchMatch传播的迭代过程中，遮挡标签也应该尽量的平滑。此时，需要优化的概率为：

Photometric Consistency

之前在baseline中，采用NCC的方案去计算颜色相似度，NCC对于Gaussian noise是optimal的，但是针对depth discontinuity区域表现很差。所以本文使用了bilaterally weighted adaption of NCC.：

其中    是以像素    为中心的patch，   是加权的协方差矩阵：    ，    ，    和    分别是patch中的灰度距离和空间距离。

Geometric Consistency

之前的smooth约束只能去除一部分的噪声，但是并不能达到robust的效果，所以本文使用了left-right consistency checks去进一步优化。与先前工作不同的是，先前工作用Geometric Consistency作为后处理，而本文将之作为view-selection的一种指标，此处，本文提出了一种新的指标，结合了photometric指标    以及geometric指标：

其中   为geometric指标，即重投影误差，    设置为3px。

以下是总结部分。把上面提到的所有概率分布联合起来优化：

其中第一项代表空间和（迭代）时间上的smooth，第二项代表使用bilateral NCC的photometric consistency。第三项代表geometric consistency。该式子可以用过variational inference去求解（该部分以后跟进）。整篇文章的概率模型还是比较复杂的，如果让我个人用一句话来总结，那就是：根据reference image和source image拍摄的夹角、图像分辨率、法向量角度去计算不同source view（用来描述reference pixel）的权重，然后根据这些权重去计算geometric和photometric的consistency，最后用PatchMatch迭代出每个像素最合适的深度。

参考

1.COLMAP https://colmap.github.io/

2.Structure-from-Motion Revisited https://openaccess.thecvf.com/content_cvpr_2016/papers/Schonberger_Structure-From-Motion_Revisited_CVPR_2016_paper.pdf

3.Pixelwise View Selection for UnstructuredMulti-View Stereo https://www.cs.unc.edu/~ezheng/resources/mvs_2016/eccv2016.pdf

4.https://openaccess.thecvf.com/content_cvpr_2014/papers/Zheng_PatchMatch_Based_Joint_2014_CVPR_paper.pdf

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！