PMVS：多视图匹配经典算法

导语：Multi-View Stereo(MVS)多视图立体匹配与三维重建的任务是：以已知内外参数的多幅图像(SfM的结果)为输入，重建出真实世界中物体/场景的三维模型。

本文作者提出了PMVS的经典算法，深入了解传统算法的实现效果，可以帮助我们与基于深度学习的方法进行对比，对“如何评估多个视图间相似性”这一问题有更深刻的认识，希望能对相关研究人员有一定的参考帮助。

论文题目：Accurate, Dense, and Robust Multiview Stereopsis

作者：Scentea|来源微信公众号：3D视觉工坊

论文地址：https://ieeexplore.ieee.org/document/5226635

代码地址：https://github.com/pmoulon/CMVS-PMVS该论文提出的方法可以分解为三个主要的部分：1. 重建出若干可以完整覆盖目标物体/场景的面片；2. 将面片模型转换为多边形渔网模型；3. 优化多边形渔网模型。这里重点分析文中提出的“匹配-扩张-剔除”策略，这也是PMVS算法的核心内容。

图 1 算法流程算法效果如下图所示，从左到右依次为输入图像(不同角度共48张)，特征点提取，特征匹配结果，扩张剔除迭代3次后效果，转换为网状模型效果。

图 2 算法效果总览

1、基本模型

基本模型中提及的符号含义

1.1、面片模型

先来了解什么是面片模型 (Patch Model)，所谓面片，是指三维物体表面的局部切平面，可以近似地表示某一局部范围内的三维物体表面，与数学中在某一范围内用切线研究曲线的做法一致，都是“将非线性函数线性化来近似处理”的思想。本质上看，一个面片是三维空间中的一个矩形，由其中心点、单位法向和参考图像三者共同确定，中心点c(p)是其对角线交点的坐标，单位法向n(p)是从中心点指向参考图像R(p) 对应的摄影中心的单位向量，这里之所以要引入参考图像的概念，是因为一个面片会在多幅图像中出现，选定其中的某一图像作为该面片的参考图像，将包含该面片的所有图像组成的集合V(p)称为该面片的可视集。（思考：如何确定一个面片的可视集并从中指定其参考图像？）

图 3 面片模型

1.2、成像差异函数

接着作者在面片可视集的基础上引入了成像差异函数 (Photometric Discrepancy Function) 的概念，或者叫灰度差异函数。

图 4 成像差异函数

1.3、图像模型

基于面片的表面表示方式最大的优势是其灵活性，但缺少面片与面片之间的连接信息，这使得寻找邻近面片，面片规整等操作实现起来较复杂，为此引入图像模型(Image Model)，建立起重建出的面片和其可视图像上投影间的联系。具体的讲，将每张图像分割为β×β的网格单元Ci(x,y)，在第i张图像的(x,y)处存储一个数组Qi(x,y)，其中包含投影在该网格单元上的所有面片信息。

图 5 图像模型

2、初始面片生成

该论文提出的多视图匹配三维重建方法，可以分为初始面片生成、面片加密、面片剔除三部分，经过初始特征匹配得到一组稀疏的面片集合，然后通过反复加密、剔除面片的过程得到最终的结果。每幅图像通过Harris和DoG算子提取出特征点后，进入到特征匹配阶段，这是PMVS算法的核心内容，思路如下：

图 6 特征匹配算法伪代码图 7 特征匹配后的效果

3、面片加密

经过上述的特征匹配后，重建出了一组稀疏的面片，接下来通过已有的面片在周围空处生成新的面片进行加密，期望达到的效果是每个图像网格单元上都至少包含有一个面片。首先，对于一个面片p，明确其周边可以扩张的网格单元，然后按照某种扩展策略进行扩展，具体思路如下：

确定可扩张网格单元

存在面片p的网格单元Ci(x,y)，根据下式，将其上下左右四个网格单元视作邻近网格单元，但并非每个邻近网格单元都是可扩张的网格单元，还需要满足两个基本条件。

图 8 邻近网格单元

第一个条件：该网格单元中不存在邻近面片p’，邻近面片的判定条件如下，意思是说两个面片中心点的距离不能过大，且两个面片的朝向不能偏差很大。

第二个条件是作者从深度方面考虑的，扩张出的面片p’和面片p对应的实际深度不能相差过大，但是实际的深度要在完成三维重建的过程后才能知道，这里就进入了一个“鸡生蛋”的逻辑死循环中，该论文中作者在这里仅做了一个简单的处理，判断两者间的成像差异函数。简单总结一下，结合下图，在确定可扩张的网格单元时分为三种情况，没有面片时(绿色箭头a)进行扩张；有面片且为邻近面片时(红色箭头b)没有必要扩张；有面片但非邻近面片时(橙色c)需要进一步判断成像差异系数，若小于给定阈值没必要扩张，大于给定阈值则扩张。

3.2、扩张策略

在明确了哪些网格单元可以扩张后，接下来的问题就是如何根据已有的面片构建出新的面片了，思路如下：

图 9 扩张策略的伪代码

4、面片剔除

在扩张的过程中，为应对那些变化较大、较难重建的区域，调大了成像差异的阈值，但与此同时不可避免地会出现一些冗余、灰度差异大等低质量的面片，在这一步中进行剔除，“扩张-剔除”的操作需要迭代进行若干次（该论文中统一进行3次），每次剔除分三步进行，每步的侧重不同，前两步从成像一致性/灰度一致性入手，第三步强调面片间的关联性。第一步剔除掉出现在同一个网格单元中，但并非邻近面片的粗差情况；第二步通过视差图测试，剔除掉那些较少图像上能看到的面片；第三步，剔除掉在相邻网格单元中相邻面片个数占总面片数小于1/4的面片。下图表示了整个算法过程中面片的个数变化，通过“扩张”后面片个数急剧增加，然后通过三种策略剔除较差的面片，面片数不断减少，再进行下一次的“扩张-剔除”。

图 10 不同阶段的面片数图 11 最终重建出的面片（物体）

图 12 最终重建出的面片（场景）可以看出，除了重复纹理区域（人的头发）、凹陷部分、深度突变区域外，重建的整体效果还是不错的，这得益于“匹配-扩张-剔除”策略的成功，成像差异函数的提出是立体匹配从双目走向多视图的关键，可视集V(p)在极线约束下利用几何信息，更新可视集V*(p)进一步考虑灰度信息，在深度学习出现后，已有论文实现通过学习的方式来评估多个面片间的相似性。

参考文献：Y. Furukawa and J. Ponce, "Accurate, Dense, and Robust Multiview Stereopsis," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 8, pp. 1362-1376, Aug. 2010, doi: 10.1109/TPAMI.2009.161.

备注：作者也是我们「3D视觉从入门到精通」特邀嘉宾：一个超干货的3D视觉学习社区本文仅做学术分享，如有侵权，请联系删文。

3.彻底搞透视觉三维重建：原理剖析、代码讲解、及优化改进

4.国内首个面向工业级实战的点云处理课程

5.激光-视觉-IMU-GPS融合SLAM算法梳理和代码讲解

6.彻底搞懂视觉-惯性SLAM：基于VINS-Fusion正式开课啦

7.彻底搞懂基于LOAM框架的3D激光SLAM: 源码剖析到算法优化

8.彻底剖析室内、室外激光SLAM关键算法原理、代码和实战(cartographer+LOAM +LIO-SAM)

9.从零搭建一套结构光3D重建系统[理论+源码+实践]

10.单目深度估计方法：算法梳理与代码实现