用于三维重建的改进特征匹配策略

吴越　李胜旺　白宇

摘 要：为了能够更加快速地获取特征点以及提高特征匹配结果的稳定性，提出了一种改进的匹配策略。首先，对图像进行下采样，通过低分辨率的图像进行匹配，快速筛选掉匹配失败的匹配对，然后对匹配成功的匹配对对应的原始图像进行匹配，以达到加速的目的。其次，为有效提高三维点云的精度，对SIFT的匹配结果和SURF的匹配结果进行融合，将融合后的结果应用到三维重建技术中。最后，通过使用自采数据集和公开数据集对算法进行测试，并对实验数据进行分析。结果显示，改进的特征匹配策略使三维重建的运行速度提高了40%，并大幅增加了三维点的个数。所提出的方法不仅可以减少特征匹配过程的运算量，还可以提高三维重建的稳定性，在三维重建研究工作中具有一定的参考价值。

关键词：计算机视觉;三维重建;下采样;特征匹配;SIFT;SURF

中图分类号：TP319 文献标志码：A

doi：10.7535/hbkd.2019yx05007

Improved feature matching strategy for 3D reconstruction

WU Yue， LI Shengwang， BAI Yu

（School of Information Science and Engineering， Hebei University of Science and Technology， Shijiazhuang， Hebei 050018， China）

[WT5HZ][HJ1.7mm]Abstract：

In order to get the feature points in the image more quickly and improve the stability of feature matching results， an improved matching strategy is proposed. First， the image is subsampled， matched by a low-resolution image， and the matching pair that matches the failure is quickly filtered out， and then the matched ones that succeed are matched with the corresponding original images， so as to achieve the purpose of acceleration. In addition， the matching result of SIFT and the matching result of SURF are merged， and the fusion result is applied to the 3D reconstruction technology， which effectively improves the accuracy of the 3D point cloud. The algorithm is tested by using self-acquired data set and public data set， and the experimental data is analyzed. The results show that the improved feature matching strategy improves the running speed of 3D reconstruction by 40% and greatly increases the number of 3D points. Therefore， the proposed method can not only reduce the computational burden of feature matching process， but also improve the stability of 3D reconstruction， so it has certain reference value in the research of 3D reconstruction.

Keywords：computer vision; 3D reconstruction; subsampling; feature matching; SIFT; SURF

三维模型重建是计算机视觉领域中一个非常重要的研究方向，相比二维图像信息，三维模型具有更加强烈的真实感，能够呈现出更多的信息。随着虚拟现实和增强现实技术的发展，可以预见三维数据将是未来数据呈现的主要形式。要进行三维重建，首先要获取三维点云。获取三维点云的方式多种多样，其中对无序图像的三维重建是众多方法中最为廉价的一种方法，其特点是只需要计算资源即可，但是重建的速度较慢。立体匹配是三维重建过程中最重要的一个环节，旨在以不同的图像中找到相同的特征点，其效果直接影响整个三维重建的质量。一方面，针对无序图像三维重建的输入是围绕目标物体拍摄的一组照片，输出是一个三维模型，由于图像之间没有时间和空间上的关系，所以在匹配过程中需要进行两两匹配，从而需要花费大量的时间进行计算。另一方面，在三维重建算法的研究中，通常只保留一种图像特征匹配的结果，因此可能会出现由于匹配不足而导致重建失败的情况。

近年来，三维重建的学术研究涉及到众多领域[1]，如考古、医学[2]、农业、航天、工业等。但是在实际应用中还是存在一些不稳定性，因此，仍需要在该学术领域中做出更加深入的研究。随着深度学习的发展[3-5]，三维重建技术也得到了迅猛发展。三维重建的方式有很多，如基于图像的三维重建[6-7]、基于视频的三维重建[8]。特征匹配是三维重建流程中非常重要的一部分[6，9]，主要由特征检测和特征匹配两部分组成。最常见的特征检测有Harris，SIFT，SURF，ORB等。Harris角点检测[10]要求特征点具有局部差异性，所以其检测结果主要分布在与周围环境不一样的点，对于纹理比较均匀的地方效果不佳。另外，Harris角點检测不具有尺度不变性。为了解决尺度变化的问题，LINDEBERG[11]提出了LoG边缘检测算子，其检测效果好，但是要先对图像进行高斯滤波，再进行拉普拉斯运算，导致计算量太大。为了能够更好地运用LoG边缘检测算子的性质，LOWE[12]提出了SIFT算法，此算法具有尺度不变性、旋转不变性和亮度变化不变性，另外在视角变化、仿射变换方面也具有一定的鲁棒性，但是SIFT算法也需要进行大量计算，运行速度也不太理想。为了提高特征点检测的速度，BAY等[13-14]提出了问题算法，该算法不但延续了SIFT 算法的优良性能，还解决了其计算量大、运行速度慢的问题，在提取特征点和描述特征向量等方面做了改进，大幅提高了运算速度。RUBLEE等[15]提出了ORB算法，它结合了FAST特征点的检测方法与BREIF特征描述子，并进行了改进，效率有很大提升。齐冰洁等[16]针对SURF算法对特征检测误差敏感的特点，提出了oSURF算法，与SURF算法相比，在相同计算速度下，oSURF算法的精度提高了5%～10%。基于SIFT的可扩展性，冯玉朋等[17]提出了Harris-SIFT算法用于无人驾驶领域，先用Harris算法将图像中的角点提取出来作为特征候选点，再用SIFT算法在候选点中进行特征点提取，起到了加速的作用，解决了实时性较差的问题。为了解决旋转和尺度不变性，KARTHIK等[18]提出了Harris-FAST算法，其原理是将Harris和FAST兴趣点检测器进行融合，使得算法具有旋转和尺度不变性，然后将兴趣点检测器定位到优选区域来优化检测器，降低了算法的运行时间。

本文提出了一种特征匹配的加速方法，通过下采样降低图像的分辨率，利用低分辨率的图像进行筛选，滤除掉匹配失败的匹配对，再将匹配成功的匹配对对应的原图进行匹配，减少原图的匹配次数，达到加速的效果。给出了一种提高三维点云稳定性的方法，融合SIFT特征匹配的结果和SURF特征匹配的结果，使2种特征匹配结果互补，增加三维点云中点的数量，提高了三维点云的精度。

1 三维重建

针对无序图像的三维重建[19]，通过计算机视觉技术来恢复二维图像中的三维信息，以此来建立目标场景的三维模型。其主要流程如下。

第1步：获取图像集;

第2步：特征点检测及匹配;

第3步：使用运动恢复结构（SFM）进行相机标定，获取稀疏点云;

第4步：使用多视角立体技术（MVS）进行稠密匹配[20]，获取稠密点云;

第5步：对稠密点云进行表面重建。

以获取的无序图像作为输入，对图像进行特征点检测及匹配。在SFM技术中，通过捆绑调整（Bundle Adjustment）对相机进行标定，恢复相机的姿态，进而获取稀疏的三维点云。在此基础之上进行多视角的稠密匹配，得到稠密的三维点云。最后，为了创建更加完整、平滑的表面，需要对稠密点云进行表面重建。为了提高三维重建的运行速度及稳定性，本文在第2步做了改进。

2 改进的匹配策略

2.1 下采样筛选

在对图像进行下采样的过程中，会不断缩小图像的尺寸，得到一组不同尺寸的图像。若对一幅分辨率为M×N的图像I进行n倍下采样，就会得到分辨率为（M/n） ×（N/n）的图像，其原理就是将原始图像中n×n的区域合成1个像素点，此像素点的值就是区域内所有像素的均值，如式（1）所示：

pk=∑[DD（X]i∈win（k）[DD）][SX（]Ii[]n2[SX）]，（1）

式中：pk为将原始图像的第k个区域合成的第k个像素点;Ii为原图中的第i个像素，其中i属于第k个区域，这里要求n是M和N的公约数。

表1列出了不同倍数的下采样对应的图像尺寸。

在进行无序图像的三维重建过程中，要对图像进行两两匹配，例如在4张图像之间进行匹配，则会产生3+2+1=6次匹配。因此在图像集数量很大的情况下，会产生庞大的计算量。在同等条件下，由于低分辨率图像的像素点少，所以低分辨率图像之间匹配的速度比高分辨率图像之间匹配的速度快。因此，本文的算法原理是在得到低分辨率的图像之后，先利用低分辨率的图像进行匹配，若匹配成功，则对相应的原图进行匹配，若匹配失败，则过滤掉这对匹配关系，达到快速筛选的目的。此方法可有效减少匹配的计算量，筛选算法描述如表2所示。

2.2 融合SIFT和SURF的匹配结果

SIFT算法具有旋转不变性、尺度不变性、亮度变化不变性，并且对视角变化、仿射变换具有一定程度的稳定性。SURF算法由SIFT算法改进而来，SIFT算法构建尺度空间是用DoG对LoG近似，SURF算法是用盒子滤波器对LoG近似，并且利用积分图像进行卷积计算，此计算过程可以在不同尺度空间下同时运行。SURF算法计算特征点的位置和尺度也依赖于Hessian矩阵，因此SURF算法的速度约为SIFT算法的3倍，并且更加具有鲁棒性。SURF算法在处理模糊和旋转的图像时具有一定的优势，但是在处理具有视角变化和光照变化的图像时效果并不理想。

生成SIFT特征后，一般采用欧氏距离作为判断的标准。输入图像A和图像B的特征点a与b，则两者的欧氏距离如式（2）所示，因SIFT特征的维度为128，所以式（2）中n=128。计算出欧氏距离，使用式（3）进行最近邻搜索。

设b*为a的最近邻，b**为a的次近邻。为了筛选掉一些孤立的点，有2种常见方法。一种方法是设定一个阈值β，满足D（a，b*）<β，即要求距离小于β。一般情况下，β的取值为1，以此来排除一些距离较远的点。另一种是本文采用的方法，找到最近距离D（a，b*）与次近距离D（a，b**）后，满足D（a，b*）/D（a，b**）<α，则认为此匹配是可靠的。LOWE[12]认为0.4<α<0.6，取值越小，精度就越高，因此匹配到的点就越少。

与SIFT特征匹配类似，SURF特征匹配也是通过欧氏距离来确定匹配度，区别在于SURF特征匹配通过加入Hessian矩阵迹的判断来提高匹配效率。若2个特征点的Hessian矩阵迹正负号相同，则表示2个特征点的对比度相同，若正负号不同，则表示2个特征点的对比度相反，直接排除。

因为基于图像的三维重建所用到的图像集是通过网络收集或者个人拍摄的，因此图像集可能存在尺寸大小不一致、光照明暗不一致、图像之间发生旋转等问题。针对这种情况，结合SIFT算法和SURF算法各自的特性，將SIFT的匹配结果和SURF的匹配结果进行融合，以增强匹配结果的稳定性。

定义图像A到图像B的匹配结果为RAB，则RAB（SIFT）为使用SIFT匹配的结果，

RAB（SURF）为使用SURF匹配的结果。设容器的尺寸为L，通过式（4）求取容器R的大小，即SIFT匹配结果的数量加上SURF匹配结果的数量。依次将SIFT的匹配结果RAB（SIFT）和SURF的匹配结果RAB（SURF）放入容器RAB（ALL）中，融合后的匹配结果为RAB（SIFT）与RAB（SURF）的合集，由式（5）表示。

用同样的方法求出图像B到图像A的匹配结果RBA（ALL）。此方法可以弥补只用一种特征匹配的结果产生的匹配不足问题，3种匹配结果的关系如图1所示。

通过融合2种特征匹配结果的匹配数量必然会增加，从而可以增加SFM算法得到的稀疏点云中点的数量，提高稀疏点云到稠密点云过程中的稳定性，最终可以提高三维模型的质量。图2分别展示了SIFT特征匹配的结果、SURF特征匹配的结果和融合了2种特征匹配的结果，图2 a）中有21条匹配对，图2 b）中有4条匹配对，图2 c）中有21+4=25条匹配对。

3 实验及结果分析

3.1 实验数据

为了验证匹配策略的有效性以及对三维重建效果的影响，通过大量实验进行测试。本实验是在配置了Intel Xeon X5450 3.00 GHz的CPU，NVIDIA Quadro FX 370（256 MB）的GPU和4 GB内存的个人工作站上进行的，操作系统为Ubuntu 18.04。

考虑到测试数据的完整性，实验选用了1组自采数据集和2组公开数据集。自采数据集是个人拍摄的河北科技大学风勇广场石刻（FY），公开数据集包括慕尼黑工业大学计算机视觉组提供的贝多芬石膏像（Beethoven）和维罗纳大学计算机科学系提供的布拉广场照片（PiazzaBraNew），详细信息如表3所示。

FY是在室外自然环境中拍摄的，Beethoven是在室内光照下拍摄的，PiazzaBraNew是在广场中任意采集的。其中FY和Beethoven是小规模的图像集，即每张照片都包含了整个目标物体，而PiazzaBraNew是大规模的图像集，每张照片只包含场景的一小部分。图3为拍摄示意图，目标物体周围的锥形标识代表每张照片的拍摄位置及方向。

3.2 验证匹配策略

首先，对图像集进行8倍下采样，通过FY得到分辨率为408×306的图像，通过Beethoven得到分辨率为128×96的图像，通过PiazzaBraNew得到分辨率为376×250的图像。然后，使用筛选策略（2.1中描述的方法）和融合策略（2.2中描述的方法）对3组图像集进行测试。最后，对实验数据进行对比和分析。

图4展示了FY的三维点云对比图，图5展示了Beethoven的三维点云对比图，图6展示了PiazzaBraNew的三维点云对比图。

具体对比项包括：

a）未使用筛选策略，只使用SIFT特征匹配结果生成的三维点云;

b）未使用筛选策略，只使用SURF特征匹配结果生成的三维点云;

c）未使用筛选策略，使用融合策略生成的三维点云;

d）使用筛选策略，只使用SIFT特征匹配结果生成的三维点云;

e）使用筛选策略，只使用SURF特征匹配结果生成的三维点云;

f）使用筛选策略，使用融合策略生成的三维点云。

表4记录了各组实验的数据，包括使用各种匹配策略完成整个三维重建流程的时间和生成的三维点云的点数，以及使用本文算法提高的效率和三维点的增长量。通过观察图表可以看出，使用筛选策略的三维重建时间比未使用筛选策略的三维重建时间短，使用融合策略生成的三维点云比只使用一种特征匹配结果生成的三维点云的完整度更高。

由于数据太多，本文仅以通过FY生成的实验数据为例说明表4中数据的含义。与未使用筛选策略的三维重建时间相比，使用筛选策略并且只用SIFT特征匹配结果的三维重建时间速度提高了56%。在未使用筛选策略的情况下，使用融合策略生成的三维点云的点数比只使用SIFT特征匹配结果生成的三维点云的点数增长了26%，比只使用SURF特征匹配结果生成的三维点云的点数增长了48%。Beethoven和PiazzaBraNew同理，故不再赘述。

通过3组图像集可知，使用筛选策略的三维重建在速度上平均提高了约40%，其中在FY中提速52%，在Beethoven中提速41%，在PiazzaBraNew中提速26%。相对只使用SIFT特征匹配的结果而言，使用融合策略平均增加了约25%的三维点个数，其中在FY中增加了16%的三维点，在Beethoven中增加了37%的三维点，在PiazzaBraNew中增加了23%的三维点。相对只使用SURF特征匹配的结果而言，使用融合策略平均增加了约114%的三维点个数，其中在FY中增加了40%的三维点，在Beethoven中增加了80%的三维点，在PiazzaBraNew中增加了223%的三维点。

使用筛选策略的三维重建速度比未使用筛选策略的三维重建速度快，在对比图中可以看出，使用筛选策略产生的三维点云没有产生空洞，也就意味着对三维重建结果并未产生影响。在FY中，融合策略的优势不是很明显。与图4 c）相比，图4 a）和图4 b）只是损失了石刻周围的一些场景，保留了目标物体的绝大部分内容，在细节上有些损失。但是在Beethoven和PiazzaBraNew中，融合策略发挥了很大的作用。由于只使用一种特征匹配的结果，导致匹配数量不足，使三维点云产生空洞，例如图5 b）的石膏像后侧产生了很大的空洞，图6 a）的广场右側丢失了一部分场景，图6 b）只保留了广场的一角。综上所述，所提出的匹配策略不仅提高了三维重建的运行速度，还改善了三维重建的效果。

4 结 语

针对无序图像之间匹配的复杂性，提出了一种筛选策略，有效减少了算法的计算量，大幅提高了三维重建的运行速度。另外，根据SIFT算法和SURF算法的特性，提出了融合SIFT匹配结果和SURF匹配结果的方法，增加了三维点的数量，增强了三维点云的稳定性，提高了三维重建的质量。

虽然所提出的匹配策略达到了预期效果，但是仍然需要继续改进。首先，本文提出的筛选策略是在低分辨率下进行的，可能会出现本应成功匹配的匹配对被过滤，从而导致三维模型失真的情况。未来可考虑对降采样算法进行改进，改善低分辨率图像的精度，提高匹配的成功率。其次，本文提出的融合策略需要同时运行SIFT算法和SURF算法，可能会导致一部分匹配对被重复计算，增加算法的运行时间。未来可考虑加入去重算法，提高算法的运行速度。

参考文献/References：

[1]孙玉娟. 基于光学图像的三维重建理论与技术[M]. 北京：清华大学出版社， 2017.

[2]YANG Hongkai， LIANG Kaichao， KANG Kejun， et al. Slice-wise reconstruction for low-dose cone-beam CT using a deep residual convolutional neural network[J]. Nuclear Science and Techniques， 2019， 30（4）： 53-61.

[3]陈加， 张玉麒， 宋鹏， 等. 深度学习在基于单幅图像的物体三维重建中的应用[J]. 自动化学报， 2019， 45（4）： 657-668.

CHEN Jia， ZHANG Yuqi， SONG Peng， et al. Application of deep learning to 3D object reconstruction from a single image[J]. Acta Automatica Sinica， 2019， 45（4）： 657-668.

[4]LI Jianwei， GAO Wei， WU Yihong. High-quality 3D reconstruction with depth super-resolution and completion[J]. IEEE Access， 2019：2895653.

[5]MESCHEDER L， OECHSLE M， NIEMEYER M， et al. Occupancy networks： Learning 3D reconstruction in function space[C]// Proceedings of IEEE Conference. on Computer Vision and Pattern Recognition.[S.l.]：[s.n]， 2019：arXiv：1812.03828.

[6]郭悅. 无序图像的多视立体匹配算法研究[D]. 成都：电子科技大学， 2017.

GUO Yue. Research on Multi-View Stereo Matching Algorithm Based on Unordered View[D]. Chengdu： University of Electronic Science and Technology of China， 2017.

[7]BOORA S， SAHU B C， PATRA D. 3D image reconstruction from multiview images[C]//2017

8th International Conference on Computing， Communication and Networking Technologies. [S.l.]：[s.n.]， 2017：8204120.

[8]KURNIAWAN R A， RAMDANI F， FURQON M T. Videogrammetry： A new approach of 3-dimensional reconstruction from video using SfM algorithm： Case studi： Coal mining area[C]// 2017 International Symposium on Geoinformatics. [S.l.]：[s.n.]， 2017：8280665.

[9]HAMZAH R A， KADMIN A F， HAMID M S， et al. Improvement of stereo matching algorithm for 3D surface reconstruction[J]. Signal Processing： Image Communication， 2018， 65： 165-172.

[10]HARRIS C G， STEPHENS M J. A combined corner and edge detector[C]// Proceedings of Fourth Alvey Vision Conference.[S.l.]：[s.n.]， 1988： 147-151.

[11]LINDEBERG T. Detecting salient blob-like image structures and their scales with a scale-space primal sketch： A method for focus-of-attention[J]. International Journal of Computer Vision， 1993， 11（3）： 283-318.

[12]LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision， 2004， 60（2）： 91-110.

[13]BAY H， TUYTELAARS T， GOOL L V. SURF： Speeded-up robust features（SURF） [C]// Proceedings of European Conference on Computer Vision.[S.l.]：[s.n.]， 2006： 404-417.

[14]BAY H， ESS A， TUYTELAARS T， et al. Speeded-up robust features（SURF）[J]. Computer Vision and Image Understand-ing， 2008， 110（3）： 346-359.

[15]RUBLEE E， RABAUD V， KONOLIGE K， et al. ORB： An efficient alternative to SIFT or SURF[C]// Proceedings of the 2011 International Conference on Computer Vision. Washington， DC ：IEEE， 2011： 2564-2571.

[16]齊冰洁，刘金国，张博研，等.高分辨率遥感图像SIFT和SURF算法匹配性能研究[J].中国光学，2017， 10（3）：331-339.

QI Bingjie， LIU Jinguo， ZHANG Boyan， et al. Research on matching performance of SIFT and SURF algorithms for high resolution remote sensing image[J]. Chinese Optics， 2017， 10（3）：331-339.

[17]冯玉朋， 曾庆喜， 马杉， 等. 无人驾驶车辆基于角点和斑点的特征提取算法[J]. 河北科技大学学报， 2017，38（3）：237-243.

FENG Yupeng， ZENG Qingxi， MA Shan， et al. A feature extraction algorithm based on corner and spots in self-driving vehicles[J]. Journal of Hebei University of Science and Technology， 2017， 38（3）： 237-243.

[18]KARTHIK O S， VARUN D， RAMASANGU H. Localized Harris-FAST interest point detector[C]// 2016 IEEE Annual India Conference （INDICON）.[S.l.]：[s.n.]， 2016：7839107.

[19]FUHRMANN S， LANGGUTH F， GOESELE M. MVE-A multiview reconstruction environment[C]// Proceedings of the Eurographics Workshop on Graphics and Cultural Heritage.[S.l.]：[s.n.]， 2014： 11-18.

[20]FERREIRA E， CHANDLER J， WACKROW R， et al. Automated extraction of free surface topography using SfM-MVS photogrammetry[J]. Flow Measurement and Instrumentation， 2017， 54： 243-249.