优化特征检测的三维重建算法

姜宇航，王美清，黄陈思

(福州大学数学与计算机科学学院, 福建 福州 350116)

优化特征检测的三维重建算法

姜宇航，王美清，黄陈思

(福州大学数学与计算机科学学院, 福建 福州 350116)

提出一种自适应优化特征点检测的三维重建方法. 该优化方法以Harris算子作为基础，将Harris算子的响应矩阵分块处理，分块选取响应值. 通过比较块中最大响应值与全局响应均值的大小，分情况选择特征点. 解决了Harris算子的阈值设置问题，减少了特征点的集群现象，改善了重建结果容易出现空洞的问题，也间接提高了重建速度. 实验结果验证了该方法的有效性.

三维重建； 多视角； 特征点检测； Harris算子

0 引言

基于立体视觉的三维重建技术是研究如何通过物体的二维信息得到物体在空间中的三维信息. 传统的基于立体视觉的三维重建方法主要包括如下几种： 基于体像素的算法[1]、基于可变形多边形网格的算法[2]、基于平面的算法、基于轮廓线的算法、基于多重深度映射的算法[3]以及基于种子生长的算法[4]. 基于种子生长算法由于其简单有效的重建思路得到了较多的研究. 其中，2007年由Furukawa等[5]提出的一种基于面片的多视角立体视觉算法(PMVS算法)，获得了比较好的重建效果. PMVS算法的重建过程主要分三步： 首先进行特征点检测，将检测出的特征点进行匹配后得到空间种子点，并在种子点上生成空间面片； 其次将获得的种子点进行三维空间具体定位的优化并将其进行扩展，使扩展后的面片能够完全覆盖物体表面； 最后根据一定的约束滤除错误面片，得到重建结果.

但是，PMVS算法采用Harris算子检测算法获得的特征点容易产生集群现象，从而导致最终的重建结果容易出现空洞，同时也容易增加后续扩展以及去除异常面片步骤的实验耗时. 本研究通过将响应矩阵分块处理，分段选择响应值，在特征点密集的区域保留多个特征点，而在特征点稀疏或者没有的区域设置一个特征点，从而减少特征点的集群现象，较好地解决了重建效果中的空洞问题，间接提高实验的运行速度.

1 基于种子生长的多视重建

在基于种子生长的三维重建方法中，Furukawa提出的PMVS方法[5]是目前重建效果较好的方法，该方法先通过特征点匹配生成面片(patch)作为种子，然后扩展面片和去除错误面片，并对后两个步骤重复迭代直至达到满意的重建效果.

1.1 特征点检测与匹配

PMVS算法三维重建的第一步 是通过Harris算子和DoG算子提取特征点，通过特征点匹配，重建得到稀疏的三维点云.

1.1.1 特征点检测

PMVS主要采用Harris角点检测方法来获得特征点. Harris算子通过目标像素点(u,v)所在的图像窗口的灰度变化量来判断该像素点是否为角点. 对应于像素点(u,v)的灰度变化量定义如下：

其中: Ex, y是窗口的灰度变化值； I为图像灰度函数； wu, v是窗口函数，这里为高斯窗口函数； o(x2, y2)是位移无穷小量； Ix和Iy是一阶灰度梯度. 式(1)对应的矩阵形式如下:

设λ1和λ2是M的两个特征值，根据文献[6]可知Harris算子检测出的特征点可以定义为下式的局部区域最大值点：

1.1.2 特征点匹配和种子面片

图1 面片模型Fig.1 Patch model

假设真实物体对应的图像序列为It,t=1, 2, …,N. 在利用Harris算子和DoG算子提取出每个图像的特征点后, 依据极限约束原理，可以获取匹配特征点集合.

若照片I1，I2中的相同位置被检测出的特征点为f1，f2. 令(f1,f2)为一个特征点对, 对应真实物点F. 在F上构建种子面片p, 对应于真实物体表面该点的局部矩形切平面. 如图1所示，每个种子面片包含三个属性，c(p)表示面片的中心位置；n(p)表示面片的单位法向，方向指向光心位置；R(p)表示所有可以看到该面片的图像集合.

1.2 面片扩展和错误面片滤除

面片扩展从种子面片开始，利用相邻面片具有相似的法向和位置的特性，逐步扩散重建周围的空间面片. 为了去除重建错误的面片，扩散结束后，将灰度一致性、几何一致性比较弱的面片去除，完成滤除步骤.

2 特征点检测改进及算法

为了改善PMVS算法在重建结果中产生空洞、计算效率低等缺陷，岳立廷等[7]通过在面片扩展步骤增加几何约束优化了重建结果，减少了面片间的间隙； 周骏[8]通过几何约束和自适应对PMVS算法进行改进，提高其重建性能； 史利民等[9]提出了一种基于物体空间几何结构的面片调整和多分辨率密度自适应的重建算法，提高了重建效率.

为了解决重建结果容易产生空洞的现象，本研究优化了特征点检测算子. 传统的Harris算子容易造成特征点集群现象，因而容易给后续的种子扩展步骤增加开销，甚至使重建结果出现空洞.

为了解决上述问题，首先对公式(3)计算出的R值进行分析. 假设整幅图像的R(x, y)值的均值为R(其中O, P为图像大小)：

(内容截图)

(4)

若真实图像中某个区域的特征点很多，则该区域计算出的R值中的最大值应大于R； 若真实图像中没有特征点，相应地，计算出的最大R值应小于R.

算法流程表述如下：

步骤1： 计算图像像素点的一阶灰度梯度，得到Ix、Iy、IxIy；

步骤2： 对图像进行高斯滤波，得到矩阵M；

步骤3： 计算图像上对应的每个像素点的R(x,y)值，得到响应矩阵R；

步骤5： 将响应矩阵R自适应分割成m×n块，若R为O×P矩阵，则每一小块的高度为a=O/m，宽度为b=P/n(根据实际实验图像设定m=n=10)；

步骤7： 将所有提取出来的R(x,y)按数值排序，提取步骤6中所有保留值的前NUM个数值所对应的点作为图像的角点，这样可以排除步骤6中因保留块最大值而误提取的空白区域噪声值，从而避免后续的错误生长.

3 实验结果及比较

本研究实验平台的硬件配置为3.20GHzCPU、4.00GB内存； 软件配置为Windows7SP1的PC机； 运行环境为VisualStudio2010. 本研究实验所用到的图像取自于三维重建评价网站[10]以及Bundler软件包[11]里面提供的测试图像. 实验分为2组，分别用原始的PMVS算法和优化特征点检测后的算法进行三维重建，并比较重建结果.

图2、图4、图6、图8为图像序列的部分图像，分辨率分别为480px×640px、640px×480px、480px×640px、480px×640px. 图3，图5、图7、图9为原始PMVS算法和优化特征点检测后算法的重建效果对比. 表1列出了重建面片总数以及运行时间的对比结果.

图2 图片序列 1 : Dino

图3 序列1重建结果

图4 图片序列 2 : Kermit

图5 序列2重建结果

图6 图片序列 3 : ET

图7 序列3重建结果

图8 图片序列 4 : Temple

图9 序列4重建结果

表1 原始PMVS算法与优化角点检测后的算法的重建结果对比

实验结果表明，改进后的算法比原始得到的面片数增加了4.5%左右，重建出的物体表面信息更加丰富，实验的运行时间也有一定的节约. 于明等[12]提出的加入法向调整的PMVS改进算法使得面片数增加了近4%. 本研究与其相比增加了0.5%的面片数量.

4 结论

虽然PMVS算法是目前公认的重建效果最好的三维重建算法之一，但是在一些输入照片质量不够好的情况下，如特征点匹配不足的情况下，重建效果并不理想，重建出的物体表面会出现空洞，无法还原真实物体或者场景的原貌. 因此，本研究通过优化三维重建的第一步特征点检测来改进原始的PMVS算法. 实验结果证实优化Harris特征点检测后，对原始的PMVS的三维重建结果有所改进. 增加了重建结果的面片，节约了三维重建的运行时间.

[1]TRANS,DAVISLS. 3Dsurfacereconstructionusinggraphcutswithsurfaceconstraints[C]//Proceedingsofthe9thEuropeanConferenceonComputerVision.Graz:Springer, 2006: 219-231.

[2]ESTEBANCH,SCHMITTF.Silhouetteandstereofusionfor3Dobjectmodeling[J].ComputerVisionandImageUnderstanding, 2004, 96(3): 367-392.

[3]BRADLEYD,BOUBEKEURT,HEIDRICHW.Accuratemulti-viewreconstructionusingrobustbinocularstereoandsurfacemeshing[C]//ProceedingsoftheIEEEConferenceonComputerVisionandPatternRecognition.Anchorage:IEEE, 2008: 1-8.

[4]HABBECKEM,KOBBELTL.Iterativemulti-viewplanefitting[C]//Proceedingsofthe11thInternationalFallWorkshoponVision,Modeling,andVisualization.Aache: [s.n.], 2006: 73-80.

[5]FURUKAWAY,PONCEJ.Accurate,dense,androbustmultiviewstereopsis[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2010, 32(8): 1 362-1 376.

[6]HARRISCG,STEPHENSMJ.Acombinedcornerandedgedetector[C]//ProceedingsofFourthAlveyVisionConference. [S.l.]:Springer, 1988: 147-151.

[7] 岳立廷，于明，于洋，等. 一种基于面片的三维重建算法[J]. 计算机工程，2012, 38(14)： 199-202.

[8] 周骏. 多视图图像三维重建若干关键技术研究[D]. 四川: 电子科技大学, 2013.

[9] 史利民，郭复胜，胡占义. 利用空间几何信息的改进PMVS算法[J]. 自动化学报， 2011, 37(5)： 560-568.

[10]SEITZSM,CURLESSB,DIEBELJ,etal.Multiviewstereoevaluation[EB/OL]. (2010-02-23)[2014-6-24].http: //vision.middlebury.edu/mview/, 2010.

[11]SNAVELYN,SEITZSM,SZELISKIR.Phototourism:exploringphotocollectionsin3D[J].ACMTransactionsonGraphics(TOG), 2006, 25(3): 835-846.

[12] 于明, 齐菲菲, 于洋, 等. 基于立体视觉的三维重建算法[J]. 计算机工程与设计, 2013, 34(2): 730-733.

(责任编辑： 林晓)

3D reconstruction algorithm based on an improved feature point detection method

JIANG Yuhang, WANG Meiqing, HUANG Chensi

(College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China)

This paper presents an adaptive 3D reconstruction algorithm based on an improved feature point detection method. The optimization method is based on the Harris operator as the basis. In this article, we firstly separate the Harris operator’s response matrix into blocks. Then we compare the maximum response value in each block with the mean response value of the response matrix. Finally, we select the feature points in different situations. In this way, we solve the problem of how to set the appropriate threshold. The cluster phenomenon of feature points is relieved. And there are fewer holes in the results of the 3D reconstruction. The time of the reconstruction is also saved. The experiment results indicate that our method is effective.

3D reconstruction; multiple views; feature detection; Harris operator

10.7631/issn.1000-2243.2017.01.0086

1000-2243(2017)01-0086-05

2015-04-29

王美清(1967-), 教授，主要从事图像处理研究，mqwang@fzu.edu.cn

国家青年科学基金资助项目(61401098); 福州大学育苗基金资助项目(600916)

TP391

A