基于多视图的三维重建方法因其较单视图以及二视图的重建方法约束条件少而获得更广泛的应用,1部摄像机就能完成真实感场景的重建。按算法所基于的物体模型可分为如下4类: 1)基于体的方法^[1]。这类方法的典型代表是Voxel Coloring算法和它的变形算法；2)基于曲面演化的方法^{[2, 3]}。这类方法主要包括基于体素(voxels)的算法，基于水平集(level sets)的算法和基于表面网格(surface meshes)的算法；3)基于多深度图的方法^{[4, 5]}；4)基于面片的方法^{[6, 7]}。该方法首先进行特征点的提取与匹配，然后对重建出的三维点拟合一个表面。在这4类方法中，前2类都需要一些初始信息，如包围盒和可视外壳等，这一要求使得它们受限于单个物体的重建，而基于多深度图和面片的方法适用于更具挑战性场景的重建。研究PMVS算法，针对其存在的不足，提出了一种基于簇的PMVS改进算法，该算法可实现对大型图像集的重建。 1 PMVS 算法

PMVS算法的中心思想是通过特征点提取与匹配得到物体或景物的稀疏的三维点云，用带有法向量的矩形面片模型对其进行描述，并进行面片扩散和过滤得到稠密的三维点云模型。其算法流程如图 1所示。

图 1 PMVS 算法流程

图选项

1)面片模型：面片p本质上是一个近似正切于重建物表面的平面，是一个三维空间中的小矩形。

c(p) : p的中心；

n(p) : p的单位法向量；

R(p): p的参考图像；

V(p): p的准可视图像集，p应该被看见但实际中由于高光、运动模糊等因素可能不被看见的图像集合：

2)图像模型：对于每一幅图像I_i，将其划分为大小为β₁×β₁像素的图像块(实验中β₁=2)。

C_i(x,y): I_i中坐标为(x,y)的图像块；

Q_i(x,y): p投影到V(p)中的每幅图像，其图像块 C_i(x,y)中所有面片的集合；

Q_i^*(x,y): p投影到V^*(p)中的每幅图像，其图像块C_i(x,y)中所有面片的集合；

C(p): p的准可视图像集中的相邻图像块集合。

3)光度差异函数：对于面片p，其在集合 V^*(p)上的光度差异函数g^*(p)的定义为

1)匹配：首先由Harris和DoG算子提取输入图像的特征点，对于图像 I_i中的1个特征点，在其余图像中找到与其对应极线距离在2个像素内的所有特征点作为潜在匹配点，采用三角化的方法生成三维空间点，根据他们与O(I_i)的距离对其进行升序排列，依次选出1个点尝试生成面片。其中三维点所在的位置为面片中心c(p)，c(p)指向O(I_i) 的单位向量为面片的单位法向量n(p)。利用式(1)、(2)确定V(p)及V^*(p)的初值，其中,α= 0.6 。然后通过最小化光度差异函数g^*(p)重新确定c(p) 和(p) ,再次利用式(1)、(2)更新V(p)和V^*(p)，其中τ的值不变，α= 0.3。最后若V^*(p)≥ γ(取γ=3)，重建成功，p作为种子面片将其存储到V(p)和V^*(p)对应的图像块，同时更新 Q_i(x,y)和Q_i^*(x,y) 。

2)扩散：面片扩散的目的是尽量在每个图像块中至少重建出一个面片。首先利用式(3)确定p 的邻域图像块集合C(p)，从中选取满足条件的图像块C_i(x,y′)尝试对其扩散一个新的面片p′，c(p′)的初始值为穿过C_i(x,y)中心的可视光线与面片p所在平面的交点,n(p′)，V(p′)和R(p′)的初始值为面片p的对应值，利用式(2)初始化V^*(p)，最小化光度差异函数对p′进行优化后，将那些根据深度测试判断为p′ 的一系列准可视图像加入到V(p′)中，并再次用式(3)更新V^*(p′)，最后若V^*(p)≥γ 则接受新扩散出来的面片。

3)过滤：过滤过程中采用3个过滤器来实现。第1个过滤器利用可视一致性约束剔除位于重建表面外的点，第2个过滤器采用更加严格的可视一致性约束过滤掉那些位于真实表面内部的点，第3个过滤器是通过强加一个较弱的规则来实现。 1.3 存在问题

一方面原始的PMVS算法在进行面片扩散时仅仅利用种子面片的信息来初始化新面片的参数((p′) ←(p)，V(p′) ←V(p))，可能造成新面片的法向存在较大偏差，导致重建出的表面不够光滑和连续。特别是在大型场景重建时经常遇到的俯仰拍摄，使得种子面片的法向初值很可能与真实的法向偏差很大，此时问题尤为严重。另一方面PMVS算法对大型图像集进行重建时时间和空间复杂度高，无法实现重建。 2 加入空间几何约束的PMVS算法

针对PMVS算法重建出的物体表面连接处存在缝隙和不够光滑的问题，考虑相邻面片信息对种子面片扩散的影响，提出加入空间几何约束的PMVS改进算法，从而提高重建精度，使重建表面更加光滑和连续。算法的改进方案如下：

1)从稀疏面片集P中取出一个面片p，按原算法获取满足扩散条件的图像块C_i(x′,y′)，尝试对其扩散当前面片p的一个相邻面片p′。沿着pp′ 找到与p距离最近的另一面片p″，设其到p在水平方向的距离为a，垂直距离为b 。若a和b满足a≤ l_a，b≤ l_b，且0.3<a/b<2 (其中l_a，l_b为提前设定的阈值，若a与b大于l_a与l_b，则p和p″的相关性就很小。0.3<a/b<2 表示a与b不能相差太多，否则若 a比b大很多，表明p与p″相距太远，若b比a大很多，意味着断层现象，以上情况都不宜再考虑p″对p的影响) 则执行步骤2，否则直接用n(p)初始化n(p′)，V(p)初始化V(p′)。

2)用c(p)到c(p′)的距离表示p到p′ 的水平距离，记作l，那么p′ 到p″的水平距离即可记为a-l 。在初始化p′的法向量n(p′)时综合考虑p和p″对其的影响，设其权重分别为(a-l)/a，l /a ，则有：

3)初始化扩散面片p′ 的可视图像集V(p′)。其由2部分组成：一部分为当前面片p的准可视图像集V(p)；另一部分需要考虑最近临面片p″ 的准可视图像集V(p″) 。由于V(p)与V(p″)可能存在部分相同的图像，所以V(p′)为从V(p″)中去掉与V(p)相同的图像后，所剩图像集中符合角度范围约束的所有图像集合与V(p)的和，表示为

所提出的加入空间几何约束实际为加入相邻面片p″空间几何信息来调整新扩散面片p′的初始法向量n(p′)和初始准可视图像集V(p′)，使其更接近于真实值。接下来的优化、扩散和过滤过程与原算法一致，依次对P中的面片进行以上操作，直至集合为空集。 3 基于簇的图像划分算法

针对PMVS算法对大型图像集进行重建时时间和空间复杂度高的问题，提出了基于簇的图像划分算法。

算法的主要思路为利用优秀的选择机制将初始数量较大、顺序杂乱、质量差别大的图像集划分为多个大小合理(小于给定的阈值)、重叠度小、结构紧密的图像簇，采用并行运行方式对这些簇进行重建来提高算法的运行效率，减少内存的消耗。最后将所有簇的重建结果融合成一个完整的模型。 3.1 簇的划分

簇划分需要满足的3个约束条件：紧密性约束，尺寸约束和覆盖性约束，以公式形式定义为

1)最小化|C_k|→ (紧密性)

2)∀k,|C_k|≤φ→(尺寸约束)

3)∀i,≥δ→ (覆盖性约束)

簇划分的算法流程如图 2所示。

图 2 簇划分的算法流程

图选项

1)SFM过滤器：将局部邻域的点融合为1个三维点，融合后点的位置为其邻域点的位置的平均值，以此来减少点的数量，剔除外点并提高后面3个步骤的运行效率。该步骤不断循环直至输入点集为空，最后输出点集为{P_j}。

2)图像选择：对于全部图像集，按照分辨率由低到高的顺序依次测试每幅图像，如果删除这张图像后覆盖性约束条件仍满足，那么就将此图像从集合中剔除，这样可确保低分辨率的图像可以率先剔除。为提高后续步骤的运行效率，图像是永久性的剔除。

3)簇的划分：采用文献^[8]的标准化分割法将不满足尺寸约束的簇划分为更小的簇。图像对(I_l,I_m) 的边权值e_lm表示I_l和I_m对SFM点重建的共同贡献度：

4)增加图像：向每一个簇中加入图像以使得覆盖更多的SFM点从而满足覆盖性约束。对未被覆盖的SFM点P_j，使C_k=argmax_Clf(P_j,C_l)为具有最大重建精度的簇。然后，对于P_j建立一个行为{(I→C_k),g}，将图像I(∈V_j,∉C_k)加入到C_k中，g表示这一行为的有效度，其定义为f(P_j,C_k∪{I}-f(P_j,C_k)。最后按g 值的大小进行降序排列。只考虑序列中不小于0.7倍 的最大值的行为，然后从顶端重复获取行为并去除互相冲突的行为(I和 I′是相邻的两幅图像)。不断重复加入图像直至满足覆盖性约束。

此算法前2个步骤为预处理，后2个步骤在执行时没有相互考虑，因此以迭代循环方式不断重复直到所有约束条件均满足为止。 3.2 模型的融合

对于融合三维点时产生的重建误差和重建质量多样性的问题采用2个过滤器来解决。过滤算法是基于外存设计的可以并行运行，因此可以有效地处理大量的MVS点云。

1)质量过滤器：同一表面区域可能由不同的簇重建出质量不同的结果。近的簇会得到稠密的、精确的三维点，而远的簇得到的是稀疏的、含有噪声的三维点，使用质量过滤器过滤掉后者。

2)可视性过滤器：可视性过滤器是在整体MVS点集上应用可视一致性约束，是基于簇间的可视一致性。对于每一个MVS点计算其与其他重建点的冲突次数，如果冲突次数大于3，则该MVS点被过滤掉。 4 实验结果与分析

算法利用C++进行实现，实验环境为：Intel双核(CPU 2.30 GHz)、Windows64位操作系统。实验阈值l_a= 6l，l_b= 3l，φ = 50，δ= 0.7。所有的图像用Bundler获得摄像机参数^[9]，使用Graclus进行标准化分割^[10]，Poisson算法进行表面重建^[11]。

实验1 为利用Canon IXUS相机对稻田石拍摄的一组图像序列，共有32幅图像，图像分辨率为3 648×2 736，输入图像、重建出的三维点云模型如图 3、4所示。

图 3 部分输入图像

图选项

图 4 三维点云模型

图选项

由于原始的PMVS算法无法对大型数据集进行重建，为了将所提算法与其进行比较，本实验采用一个小型数据集。因稻田石拍摄角度较好，故PMVS算法中初始法向较好，优化得到的法线多数接近于真实值，尽管如此，由图 4(a)可以看出一些局部位置仍然存在错误。文中利用加入空间几何约束的PMVS算法重建出的点云的方向与几何保持了好的一致性，得到的三维模型表面更加光滑和连续，见图 4(b)。此外，正确的法向有助于提高空间点的定位精度，有利于扩散出更多的点。由表 1知，直接使用PMVS算法输出的MVS点云为620 982个，所提出算法输出的点云为651 373个。初始采用的簇划分算法将数据集划分成了1个簇，大小为23，剔除了9张冗余的图像，减少了算法的运行时间。虽然后面利用加入空间几何约束的PMVS算法对图像簇进行重建时较原PMVS算法会多耗费一些时间，但与采用簇划分算法所减少的时间相比还是很少的，从表 1可看出，所提出算法的整体运行时间较原PMVS算法减少了37.9 min。

实验2 为从互联网上获取的巴黎圣母院数据集，共有545幅图像，图像分辨率多样。输入图像、重建出的三维点云模型和Poisson表面重建结果如图 5~图 7所示。

图 5 部分输入图像

图选项

图 6 三维点云模型

图选项

图 7 Poisson表面重建结果

图选项

巴黎圣母院数据集较大，直接使用PMVS算法进行三维重建时造成内存不足，只运行了33张便停止运行。利用文中所提出的算法对其进行三维重建时，数据集被划分为5个簇，大小分别为27、10、41、42、42，各个簇的重建结果如图 6(a)~(e)所示。输入的SFM点云为141 916个，最终输出的MVS点云为2 456 863个，簇划分的时间为1.3 min，利用加入空间约束的PMVS算法对每个簇进行重建的时间为157.4 min，最后的模型融合用了8.6 min。此数据集为游客拍摄的旅行纪念照，几乎全部为正面仰角拍摄，如此导致初始法向与真实法向偏离较远，采用加入空间几何约束的PMVS算法有效地解决了此问题。融合后的点云模型和Poisson表面重建结果见图 6(f)和图 7，很显然重建出的模型比较完整，且表面足够光滑和连续。 5 结论

在研究PMVS算法的基础上提出了将基于簇的图像划分算法和加入空间几何约束的PMVS算法二者相结合的一种新的算法。

1)实验1将所提出的算法和原PMVS算法进行了比较，结果表明所提出的算法在重建精度和效率较原PMVS算法都有了一定的提高，重建出的物体表面更加光滑和连续。

2)实验2利用所提出的算法对巴黎圣母院的大型图像集成功进行了三维重建，这是原PMVS无法实现的，且重建出的模型表面足够光滑、连续。显然所提出的算法更适用于拍摄角度有限，图像集大的场景。随着图像采集设备分辨率的提高，三维重建时所需要付出的时间和空间代价也越来越大，下一步的研究方向是在保证重建精度的同时提高高分辨率图像的重建效率。