用于三維重建的改進特征匹配策略

吳越　李勝旺　白宇

摘 要：為了能夠更加快速地獲取特征點以及提高特征匹配結果的穩定性，提出了一種改進的匹配策略。首先，對圖像進行下采樣，通過低分辨率的圖像進行匹配，快速篩選掉匹配失敗的匹配對，然后對匹配成功的匹配對對應的原始圖像進行匹配，以達到加速的目的。其次，為有效提高三維點云的精度，對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.