基于立体视觉的三维重建算法

于 明，齐菲菲，于 洋，阎 刚，薛翠红

(河北工业大学计算机科学与软件学院，天津300401)

0 引言

随着科技的发展，三维重建技术已引起越来越多的计算机图形学研究人员的关注［1］。目前基于立体视觉的三维重建算法主要有下面几类:基于轮廓线的算法［2-3］。这类算法通过利用物体投影在图像平面上的轮廓线来重构物体的三维模型;基于深度图的算法［4-5］。该类算法通过配准和合并多幅包含图像深度值的深度图像来得到物体表面的完整信息;基于体素的算法［6］。这类算法通过将待重建物体划分为一个个小立方体栅格，然后基于这些体素来进行物体的三维重建;基于匹配点的算法［7-8］。该类算法首先通过图像序列得到物体的稀疏点云结构，再通过扩散操作得到物体表面的稠密点云［9-10］。PMVS(patch multi-view stereo)算法［11］便是一种基于面片 (将匹配点用片面形式表示)的点云重建算法，它是通过扩展种子面片的原理完成物体表面重建的，是目前公认重建效果最好的算法之一。但是PMVS算法在片面扩展过程中，容易出现重建表面不够连续，与真实物体的形状有一些偏差等情况。同时由于PMVS算法空间和时间复杂度比较高，在处理高分辨率图像时需要付出巨大的时间和空间代价。针对上述问题，本文提出了一种加入法向调整的PMVS改进算法，并且通过采用多分辨率分级重建策略［12］在一定程度上提高了重建效率。

1 PMVS算法

PMVS算法是由Y.Furukawa等人提出的，它的基本原理是利用Harris算子和DoG(Difference-of-Gaussian)算子检测出每幅图像中的特征点，然后利用匹配算法得到稀疏的三维点云结构，再将这些匹配点定义成种子片面，通过扩展种子片面得到稠密的片面结构。PMVS算法通常要进行多次的扩展和过滤操作以达到高精度的重建效果。算法流程如图1所示。

图1 PMVS算法流程

为了方便介绍PMVS算法的原理，给出以下几个定义:

(1)片面模型 PMVS算法将重建出的每个匹配特征点f对应成一个种子片面p，它包含几个属性c(p)，n(p)，R(p)，分别表示片面p的中心，p的单位法向，p的参考图片(p在图片上是可见的)。它们的初始值定义如下

(O(Ii)表示图片Ii对应的摄像机光心)

(2)光学误差函数 定义V(p)是p的可见图像的集合，光学误差函数定义如下

其中h(p，I1，I2)是图片I1和I2间的灰度差异函数，PMVS算法通过用共轭梯度法最小化光学误差函数的方法，在p的匹配特征点集合中选择最优的一个作为最终的面片。

(3)图像块模型 PMVS算法将每幅图像Ii划分为一个个大小为β×β个像素的图像块C(x，y)，以每个图像块里至少重建出一个种子片面，来确保重建出的面片集合能完全覆盖物体表面。

PMVS算法重建过程分三步:特征点检测与匹配，面片扩展，错误片面过滤。首先通过DoG算子和Harris算子提取特征点，根据极线约束原理获取匹配特征点集合，设某个特征点f对应一个种子片面p，利用式 (1)，(2)，(3)初始化p，将得到的c(p)和n(p)作为变量，用共轭梯度法最小化灰度差异值，在p的匹配特征点集合中选择最优的一个作为最终对应面片。接下来进行片面的扩展，在p的邻居图像块Ci(x，y)中扩展p的近邻片面p'，首先利用片面p的信息初始化片面p'，c(p')的初始值为Ci(x，y)的中心投影线与p所在平面的交点，n(p')的初始值等于n(p)，再利用优化过程对c(p')和n(p')进行优化，从而得到一个新的片面，直到扩展出的片面集合能够完全覆盖物体表面。扩展结束后，要进行过滤操作，将灰度一致性、几何一致性比较弱的片面剔除。

2 加入法向调整的PMVS算法改进

PMVS算法在进行片面扩展过程中，对于每个重建出的新片面都要进行一次共轭梯度法迭代操作来对片面进行优化，这样就使得算法的时间复杂度非常大，特别当图像较多，图像分辨较大时，PMVS算法的空间复杂度和时间复杂度将是非常大的。同时PMVS在生成新的片面时，仅仅利用当前片面的信息来初始化新片面的参数，并没有考虑周围片面的信息，这样重建出的片面集合往往连接性不好，重构出的物体表面不够光滑。所以既要保证重建精度又能提高重建效率正是本文采用多分辨率分级重建的初衷。实际上在重建物体时，仅需要在物体结构比较复杂的区域重建出较稠密的点云，而在物体结构较平坦的区域少量的点云便可以描述物体形状。PMVS算法为用户提供了选择分辨率等级的接口，Level 0级指原始图像，Level L指下采样图像，其长、宽是原始图像长、宽的1/2L。我们可以先选择在适当的等级上进行PMVS重建，利用重建出的稀疏片面，计算每个片面中心点的主曲率，如果其主曲率大于设定的阈值，则说明物体在该点周围区域内形状有较大变化，则需要在该点周围区域进行高分辨等级的PMVS重建［12］。算法的基本框架如下:

步骤1 根据重建场景的不同选择恰当的分辨率等级Level L进行PMVS点云重建，在得到的稀疏片面集合中选择某个种子片面p，采用KD(K-dimension)树算法寻找p的k近邻片面。

步骤2 利用p及k近邻片面集合拟合二次曲面，计算出每个点的主曲率，如果存在主曲率绝对值大于阈值T的点，则把这些点放在集合Q里，把p所在的图像块以及其周边的八个图像块一起做下标记。

步骤3 把集合Q里的点作为新的种子片面，在做了标记的图像块上进行分辨率等级为Level L－1的PMVS片面扩展重建，在扩展当前片面p的一个临近片面p'时，为考虑周围片面对新的片面p'的影响，找到与p距离最近的另一个片面p″，设p″与p在水平方向上的距离为a，在垂直方向上的距离为b。如果a和b满足a≤la，b≤lb且0.3＜a/b＜2(其中la和lb为提前设置的阈值，0.3＜a/b＜2表示a与b不能相差太多，否则意味着断层现象，不宜再考虑p″对p'的影响)则执行步骤4，否则仅用p的信息初始化p'。

步骤4 设当前片面p所在的图像块的中心投影线与片面p的交点为p0，则可用pp0表示p到p'的水平距离，记作l，那么p″到p'的水平距离为a－l。在初始化片面p'的法向n(p')时，综合考虑n(p)和n(p″)的影响，设它们的影响系数分别为a－l/a和l/a，则有

步骤5 将上面步骤得到的n(p')做参数，利用共轭梯度法迭代优化新片面p'的位置和法向，最终得到最优的新的片面p'，依次在做过标记的图像块中对剩下的片面进行以上步骤的扩展操作，直到图像分辨率等级提高为Level 0，则算法停止。

3 实验与分析

本文利用从多个角度拍摄的真实图像序列，来进行PMVS算法及本文改进算法的对比实验。实验分为两部分，实验1分别用原始的PMVS算法和加入法向调整后的改进算法对真实图像序列进行三维重建，并比较重建结果。实验2分别用单分辨率PMVS算法和加入多分辨率分级重建后的算法，对真实图像序列进行三维重建，并比较重建结果。

实验1 本文的实验数据是通过摄像机每隔10度拍摄得到的两组图像序列。图像分辨率为1600×1200，图2、图4为图像序列，图3、图5为原始PMVS算法和加入法向调整后的算法的重建效果对比。表1列出了重建片面总数的结果对比。

图5 重建结果

表1 原始PMVS算法与加入法向调整的算法的重建结果对比

实验结果表明，改进后的算法比原始算法得到的片面总数增加了将近4%，并且改进后的算法在物体表面结构复杂的区域得到了较好的细节刻画效果，重建出的物体表面也更加光滑，更加连续。

实验2 利用上图2及图4中的图像序列，分别进行单一分辨率与多分辨率分级的PMVS重建。图6、图7是实验结果对比。其中进行多分辨率分级重建时选择初始分辨率为Level 2。

图6(a)为原始PMVS算法在Level 0等级上的重建结果，图6(b)为从Level 2到Level 0上的重建结果，首先从Level 2上重建得到47895个稀疏点，根据计算曲率，设置曲率阈值T=5，得到18206个种子点，然后利用这些点在Level 1上进行重建，得到69162个点，将阈值调整为6，得到下一步的种子点25589个，再利用这些点在Level 0上进行重建，得到97239个点，将三次的重建结果合并得到图6(b)的重建结果。

图7(a)为原始PMVS算法在Level 0等级上的重建结果，图7(b)为从Level 2到Level 0上的重建结果，首先从Level 2上重建得到38581个稀疏点，根据计算曲率，设置曲率阈值T=5，得到14725个种子点，然后利用这些点在Level 1上进行重建，得到56959个点，将阈值调整为6，得到下一步的种子点20574个，再利用这些点在Level 0上进行重建，得到78182个点，将三次的重建结果合并得到图7(b)的重建结果。

表2列出了两组实验的运行时间，通过对比可知采用多分辨率分级重建的PMVS算法比原始的算法在运行时间上缩短了很多。

表2 单一分辨率与多分辨率分级重建的运行时间对比

本文实验环境:Intel双核 (CPU 2.80GHz)，2G内存，Windows XP操作系统。算法利用Visual C++实现。本文实验中阈值la=6l，lb=3l(l为每次计算得到的常数)，β=2，k=100，T=5～10。

4 结束语

虽然PMVS算法是目前公认的重建效果最好的算法之一，但是在对一些具有复杂结构的场景进行重建时，场景的一些细节重建效果并不理想，重建出的物体表面不够连续，与真实物体的形状有一些偏差，因此本文通过考虑近邻片面对新片面的影响，对新的片面加入了法向的调整，使重建出的物体表面更连续更接近真实物体的形状，进而提高了重建的准确性。另外PMVS算法的时间复杂度与空间复杂度非常大，特别是对于高分辨率的场景进行重建时，算法运行时间非常长，因此本文采用多分辨率分级重建的策略，根据物体表面结构复杂程度进行不同级别的PMVS重建，这样既保证了重建的精度，又提高了重建的效率。

［1］SHU Bo，QIU Xianjie，WANG Zhaoqi.Survey of shape from image［J］.Journal of Computer Research and Development，2010，47(3):549-560(in Chinese).［束搏，邱显杰，王兆其.基于图像的几何建模技术综述［J］.计算机研究与发展，2010，47(3):549-560.］

［2］QIAN Subin，LIN Yi.3D reconstruction of rotated surface based on contour lines［J］.Computer Engineering and Design，2009，30(16):3875-3878(in Chinese).［钱苏斌，林意.基于轮廓线的旋转曲面三维重建 ［J］.计算机工程与设计，2009，30(16):3875-3878.］

［3］WANG Yanxia.Research on profile extraction and key technologies for 3D reconstruction［D］.Chongqing:University of Chongqing，2010:63-74(in Chinese).［王艳霞.图像轮廓提取与三维重建关键技术研究［D］.重庆:重庆大学，2010:63-74.］

［4］Bradley D，Boubekeur T，Heidrich W.Accurate multi-view reconstruction using robust binocular stereo and surface meshing［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Anchorage，USA:IEEE，2008:1-8.

［5］LI Tao.Depth map recovery for monocular and multi-view images［D］.Beijing:Tsinghua University，2009:14-26(in Chinese).［李涛.单目视图与多目视图的深度图恢复方法研究［D］.北京:清华大学，2009:14-26.］

［6］Pons J P，Keriven R，Faugeras O D.Multi-view stereo reconstruction and scene flow estimation with a global image based matching score［J］.International Journal of Computer Vision，2007，72(2):179-193.

［7］ZHU Qingsheng，LUO Dajiang，GE Liang，et al.Multiple-imagebased 3D reconstruction ［J］.Computer Engineering and Design，2010，31(10):2351-2357(in Chinese).［朱庆生，罗大江，葛亮，等.基于多幅图像的三维重建［J］.计算机工程与设计，2010，31(10):2351-2357.］

［8］LIU Wei，MA Jun.Accurate linear triangulation method based on multiple view ［J］.Computer Engineering and Design，2009，30(12):3035-3037(in Chinese).［刘伟，马俊.基于多视图的三维空间点精确重建算法［J］.计算机工程与设计，2009，30(12):3035-3037.］

［9］Furukawa Y，Curless B，Seitz S M，et al.Towards internet-scale multi-view stereo［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Miami，USA:IEEE，2010:1434-1441.

［10］Hiep V H，Keriven R，Labatut P，et al.Towards high-resolution large-scale multi-view stereo［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Miami，USA:IEEE，2009:1430-1437.

［11］Furukawa Y，Ponce J.Accurate，dense，and robust multi-view stereopsis［C］//Proceedings of the IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(8):1362-1376.

［12］SHI Limin，GUO Fusheng，HU Zhanyi.An improved PMVS through scene geometric information ［J］.Acta Automatica Sinica，2011，37(5):561-563(in Chinese).［史利民，郭复胜，胡占义.利用空间几何信息的改进PMVS算法 ［J］.自动化学报，2011，37(5):561-563.］