羅慶 唐清善

摘? 要：鑒于多視圖三維重建算法的特征檢測和匹配能力較差，文章提出一種基于改進ORB特征提取的快速三維重建算法。該算法針對傳統(tǒng)算法在建筑數(shù)據(jù)采集中的重建效果差和運行效率低的問題進行了優(yōu)化，首先運用改進的ORB算法進行特征點提取，采用GMS算法進行特征匹配，得到匹配結果后利用全局式SFM對場景相機位姿進行估計，之后再進行光束法平差，最后利用PMVS算法得到稠密重建的結果。實驗結果表明，該算法在三維重建運行效率上有所提升，能夠滿足快速的三維重建要求。

關鍵詞：全局式SFM；ORB算法；GMS算法；光束法平差

中圖分類號：TP391.4；TP312 文獻標識碼：A 文章編號：2096-4706（2023）15-0083-05

A Fast 3D Reconstruction Algorithm Based on Improved ORB Feature Extraction

LUO Qing， TANG Qingshan

（School of Physics & Electronic Science， Changsha University of Science & Technology， Changsha? 410114， China）

Abstract： In view of the poor feature detection and matching ability of multi view iterative reconstruction algorithm， this paper proposes a fast iterative reconstruction algorithm based on improved ORB feature extraction. This algorithm has been optimized to address the issues of poor reconstruction performance and low operational efficiency of traditional algorithms in building data collection. Firstly， the improved ORB algorithm is used for feature point extraction， and the GMS algorithm is used for feature matching. After obtaining the matching results， the global SFM is used to estimate the camera pose of the scene， followed by bundle adjustment. Finally， the PMVS algorithm is used to obtain the dense reconstruction results. The experimental results show that the algorithm improves the running efficiency of iterative reconstruction and can meet the requirements of fast iterative reconstruction.

Keywords： global SFM; ORB algorithm; GMS algorithm; bundle adjustment

0? 引? 言

多視圖三維重建技術是指通過三維物體的二維投影來恢復三維形狀的技術[1]，目前基于運動恢復結構（Structure From Motion， SFM）的算法是多視圖三維重建研究的熱點方向[2]。

圖像特征提取和匹配是三維重建流程研究中較為重要的內(nèi)容，目前多視圖三維重建大多是基于特征提取算法SIFT（尺度不變特征變換）[3]來實現(xiàn)。該算法能夠在不同尺度和旋轉的情況下得到較好的匹配結果，但由于使用了128維描述符，計算過于復雜導致匹配效率低下。針對這一問題，以下研究者給出了不同的解決辦法。文獻[4]提出基于Bicular算法的自適應尺度結合Harris算法改進SIFT算法，具有更強的特征點檢測與匹配能力；文獻[5，6]提出基于AKAZA算法的多視圖三維重建改進方法，以AKAZA算法為基礎一定程度上提高了重建的效率，但使用單應性矩陣迭代隨機采樣一致算法模型耗時較長。傳統(tǒng)ORB特征提取算法提取特征點數(shù)較多且提取速率快，但所提取的特征點分布不均勻且存在誤匹配較多的情況，為此，通過四叉樹原理[7]對圖像進行分區(qū)域特征提取得到均勻分布的特征點后，使用GMS（Grid-based Motion Statistics）[8]算法對特征點進行匹配。結合GMS特征匹配和ORB特征點提取算法的效果較傳統(tǒng)ORB算法和其他同類特征匹配算法更好[9]。Tamilarasi[10]提出的增量式SFM重建算法，通過挑選基準圖像再疊加新的圖像并進行光束法平差優(yōu)化后得到點云，文獻[11-13]在增量式方法的基礎上提高了重建效率，但該方法只有在序列圖像較少的情況下才能獲得較好的重建效果和運行效率，當圖像增多時耗時和誤差也會驟然變大。

針對上述問題，提出基于四叉樹和改進ORB特征提取的快速三維重建算法，運用ORB算法進行特征提取和暴力匹配后引入GMS算法對粗匹配點進行篩選，采用全局式SFM[14]算法得到稀疏點云后再使用PMVS算法得到稠密點云，從而完成多視圖幾何三維重建。

1? 基于ORB特征提取的全局式SFM算法

1.1? 特征檢測與匹配

1.1.1? ORB特征提取

1.1.1.1? 特征點提取與篩選

首先對圖像特征點進行粗提取，通過機器學習的方法篩選粗提取的匹配點，運用基于四叉樹的劃分[15]算法來篩選最優(yōu)的FAST角點。設置自適應閾值，在提取的特征點達到期望值后結束提取以減少算法運行時間，從而避免了傳統(tǒng)ORB算法的冗余扎堆現(xiàn)象，得到均勻的特征點，有利于匹配精度的提升。

1.1.1.2? 計算特征點的灰度質心

ORB算法借助矩法來確定FAST特征點的方向，通過矩來計算以特征點為中心r半徑范圍內(nèi)的質心，特征點和質心之間的向量作為該特征點的方向。矩的定義為：

其中，I （x， y）表示圖像灰度，該矩質心為：

根據(jù)質心坐標得到特征點方向：

1.1.1.3? BRIEF算法描述

經(jīng)過上一步我們可以確定圖像的關鍵點，現(xiàn)在需要通過BRIEF算法將這些關鍵點轉化為特征向量。該算法的主要思想是比對特征點與周圍鄰域多個點對之間的灰度大小，得到0或1兩種結果，算式為：

其中，I （x）與I （ y）分別表示該點的像素值，得到結果形成二進制編碼串，該編碼串的長度通常為128～512，代表著該描述子的屬性和周圍鄰域信息，這一特性使得BRIEF的運算速度非?？?。通過下式將每點得到的τ （ p; x， y）構成此目標點的BRIEF特征描述子：

1.1.2? GMS算法圖像匹配

假設IA和IB為輸入圖像，IA到IB圖像的最近鄰匹配集合為T ={t1，t2，…，ti，…，tN}，ti表示其中的一個圖像匹配對，假定正確的匹配點鄰域內(nèi)還有Si個匹配點支持它，其中Si = | λ | - 1，由于每個特征點之間相互獨立，其鄰域內(nèi)支持量Si服從二項式分布，如式（7）所示：

其中，Pt和Pf分別表示正確匹配和錯誤匹配時鄰域窗口支持的概率，R表示鄰域內(nèi)匹配對的數(shù)量。Si的數(shù)學期望及標準差為：

根據(jù)期望Ef和標準差Sf可以確定正確匹配和錯誤匹配的可區(qū)分度：

ε=Ef+aSf（10）

Ef的大小可以忽略不計，統(tǒng)計網(wǎng)格中對所有特征匹配對的鄰域支持量為Si，保留Si＞ε作為正確的匹配點對。

1.2? SFM算法

1.2.1? 求解基礎矩陣

設第一幀下P點空間位置為[X， Y， Z]，根據(jù)針孔相機模型得到像素點位置分別為KP、K （RP + t），其對極幾何關系為：

PT2K（-T）T^PK-1P1=0（11）

其中，P1和P2表示不同圖像的對應特征點對，該式簡潔描述了匹配點之間的空間位置關系。

1.2.2? 相機旋轉和平移向量求解

三維旋轉變換可以用3×3的正交矩陣T表示，相機i和j之間的旋轉關系可以表示為：

Tij=TjT-1i（12）

相機平移求解以相機旋轉結果作為輸入，相機相對于全局坐標系的平移向量可通過式（13）求得：

Eij=TTi（[ti]x-[tj]x）Tj（13）

2? 仿真實驗與分析

2.1? 全局式SFM三維重建流程和實驗環(huán)境

改進的基于ORB特征提取的全局式SFM三維重建算法主要流程如下：

1）輸入圖像序列，提取圖像信息，生成EXIF文件。

2）使用改進的ORB算法提取特征點和暴力匹配算法后得到特征粗匹配對，使用GMS算法進行特征匹配篩選得到均勻的匹配點對。

3）根據(jù)匹配的特征點計算序列圖片之間的空間位置關系，并計算出相機的全局旋轉矩陣和全局平移矩陣。

4）利用光束法平差優(yōu)化重投影誤差，得到稀疏點云。

5）使用基于面片的多視圖立體算法得到稠密點云。首先利用稀疏點云特征點與其相鄰點結合圖像信息得到面片并進行擴展，過濾掉錯誤面片后得到稠密點云。

本系統(tǒng)是在Ubuntu 16.04平臺上開發(fā)的，仿真依賴庫為OpenMVG、OpenMVS和OpenCV，硬件環(huán)境為Intel Core i5-8250U（1.6 GHz），開發(fā)語言為C++。

2.2? 圖像配準實驗

在多視圖三維重建中，圖像特征點的提取和匹配作為最基礎的部分，其匹配效率和匹配精度也影響著整個三維重建流程的效果。本次實驗將使用序列建筑圖像作為輸入，檢驗圖像特征匹配的數(shù)量、精度和時間復雜度。其中相機焦距為35 mm，圖像分辨率為2 592×3 872。實驗中使用的部分序列圖像和不同算法匹配結果如圖1和圖2所示。

在圖像配準實驗中分別利用SIFT、ORB和本文算法進行圖像特征提取和匹配，對如表1所示的匹配結果進行分析可知，本文算法在粗匹配點數(shù)和精匹配點數(shù)上都取得了很好的結果。其中精匹配是由粗匹配經(jīng)過隨機抽樣一致算法得到的，精匹配點數(shù)達到2 727，匹配準確率也高于SIFT算法和傳統(tǒng)ORB算法，達到了98.7%，匹配效率即單位時間精匹配點，本文算法為1 934點/秒，SIFT和傳統(tǒng)ORB算法分別為295點/秒和1 293點/秒。在特征檢測與匹配耗時上本文算法分別為SIFT和傳統(tǒng)ORB算法的15.25%和66.85%，而在特征點匹配能力上較之兩種算法均有所提高。

將本文特征匹配算法應用到多視圖三維重建的流程中，其中使用數(shù)據(jù)集序列圖像數(shù)量為543張，以下實驗將三組不同圖像特征匹配算法在三維重建中的時間復雜度進行對比。如表2所示。

表2描述了不同特征提取算法在三維重建流程中的時間復雜度，在特征提取和匹配過程中，SIFT平均每張圖片耗時7.9秒，傳統(tǒng)ORB單張耗時2.47秒，改進ORB算法單張耗時為1.96秒，改進ORB算法耗時為SIFT的24.8%，是傳統(tǒng)ORB算法的79.35%。從該組實驗可以看出，基于改進ORB算法的特征提取和匹配的耗時更少，提高了三維重建流程的運行效率，進一步實現(xiàn)了快速的三維重建。ORB特征提取算法的主要特點是提取速度快，但特征點的魯棒性較差，容易產(chǎn)生錯誤的匹配點。基于GMS算法的運動統(tǒng)計特性（即一個正確的匹配點周圍也一定存在足夠多的匹配點來支撐匹配），結合改進ORB和GMS兩種算法可以得到一種速度快且質量好的特征匹配方法。得到特征匹配的結果后，繼續(xù)往下進行完成實驗。

2.3? SFM三維重建試驗

圖3和表3分別給出不同算法的三維重建可視化結果和重建數(shù)據(jù)，從可視化的角度來看，在稠密點云上全局式ORB算法得到的結果擁有更加清晰的邊緣，孔洞也更少，可視化效果最佳。

僅從增量式三維重建數(shù)據(jù)上分析，基于改進ORB算法的三維重建所能得到的稀疏點云比基于SIFT算法增加了24.27%，比基于傳統(tǒng)ORB算法增加了39.62%，稠密點云數(shù)分別增加17.49和27.27%。采用全局式ORB算法得到的稀疏點云相較于前三種算法分別增加35.23%、51.94%、8.82%，而稠密點云分別增加28.28%、38.96%、9.18%，重建效率相較于增量式ORB算法提升28.56%，可以看到全局式ORB算法得到的稠密點云具有更加豐富的紋理信息。綜上，基于本文算法的三維重建系統(tǒng)在該數(shù)據(jù)集中表現(xiàn)出更加優(yōu)異的性能，不僅得到了更加豐富的點云信息，在三維重建效率上也比增量式重建有所提升。

通過二維圖像生成三維模型后，由于受噪聲等因素的干擾，所生成的三維模型再反投影至二維圖像，初始位置與該投影點并不會完全重合，假設將所有投影點與該點原始位置之間距離平方和均值的平方根作為重建的均方根誤差，可表示為：

基于ORB算法的全局式三維重建最終得到的均方根誤差為0.28，在增量式重建中本文算法得到的重建誤差低于其他重建算法，表示基于改進ORB算法的三維重建模型在一定程度上減小了重投影誤差，這是因為該算法得到的匹配點對更加準確，誤匹配率更低，在通過特征點生成三維空間點時因誤匹配帶來的干擾也更小，而增量式和全局式三維重建算法所產(chǎn)生的重建誤差的差異主要是因為增量式三維重建會隨著圖像的加入不斷進行光束法平差而產(chǎn)生誤差的累積，而全局式三維重建考慮了相鄰相機之間的空間關系，不會導致重建結果的漂移，并且這種差距會隨著序列圖像數(shù)量的增加而變大。

3? 結? 論

針對傳統(tǒng)增量式三維重建算法存在重建效率和重建精度低的問題，提出一種基于改進ORB算法的三維重建，實驗結論如下：

1）基于改進ORB算法得到的特征點更精確，在匹配能力上要高于其他同類算法，并且提高了匹配效率。

2）將改進的ORB算法運用到三維重建系統(tǒng)中能夠獲得更加稠密的點云，降低了重建誤差，驗證了改進ORB算法應用于三維重建系統(tǒng)的可行性。

3）使用全局式三維重建算法能夠改進增量式重建產(chǎn)生的誤差累積問題，有效減小了均方根誤差，提升了重建效率，在可視化角度上得到的稠密點云邊緣更加清晰，孔洞更少。

參考文獻：

[1] 鄭太雄，黃帥，李永福，等.基于視覺的三維重建關鍵技術研究綜述 [J].自動化學報，2020，46（4）：631-652.

[2] 王巧麗，徐增波，張玲.基于運動恢復結構三維重建的應用與研究進展 [J].毛紡科技，2021，49（7）：95-98.

[3] LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints [J].International Journal of Computer Vision，2004，60（2）：91-110.

[4] 普陽光.改進ASIFT算法的PMVS三維重建 [J].計算機時代，2018，312（6）：69-71.

[5] 周泩樸，耿國華，李康，等.一種基于傳統(tǒng)AKAZE算法的多視圖幾何三維重建方法 [J].計算機科學，2018，45（S2）：180-184+207.

[6] 郝豪杰，李朝奎，方軍，等.改進的傳統(tǒng)AKAZE特征提取的全局式SFM三維重建算法 [J].測繪科學技術學報，2021，38（5）：492-498.

[7] 倪翠，王朋，孫浩，等.一種基于四叉樹劃分的改進ORB算法 [J].應用科學學報，2022，40（2）：266-278.

[8] BIAN JW，LIN WY，MATSUSHITA Y，et al. GMS： Grid-based motion statistics for fast， ultra-robust feature correspondence [C]//2017 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. Honolulu：IEEE，2017：2828-2837.

[9] 潘峰，沈建新，秦順，等.融合GMS的ORB特征點提取與匹配算法 [J].計算機工程與設計，2022，43（8）：2244-2251.

[10] TAMILARASI M，DURAISWAMY K. Genetic based Fuzzy Seeded Region Growing Segmentation for Diabetic Retinopathy Images [EB/OL].[2023-02-02].https：//www.zhangqiaokeyan.com/academic-conference-foreign_meeting-294498_thesis/0705018999867.html.

[11] SNAVELY N，SEITZ S M，SZELISKI R. Modeling the world from Internet photo collecting [J].International Journal of Computer Vision，2008，80（2）：189-210.

[12] WU C C. VisualSFM： A visual structure from motion system [EB/OL].[2023-02-04].http：//ccwu.me/vsfm/index.html.

[13] RAMMALINGAM S，ANTUNES M，SNOW D，et al. Line-sweep： Cross-ratio for wide-baseline matching and 3D reconstruction [C]//2015 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. Boston：IEEE，2015：1238-1246.

[14] MICHELETTI N，CHANDER J H，LANE S. Structure from motion （SFM） photogrammetry [EB/OL].[2023-01-25].https：//www.researchgate.net/publication/293108194_Structure_from_motion_SFM_photogrammetry.

[15] 彭智東，宣士斌.融合最小生成樹和四叉樹的圖割圖像分割方法 [J].計算機技術與發(fā)展，2018，28（12）：102-105+126.