基于改進(jìn)ORB特征提取的快速三維重建算法

羅慶 唐清善

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

關(guān)鍵詞：全局式SFM；ORB算法；GMS算法；光束法平差

中圖分類號(hào)：TP391.4；TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 引? 言

多視圖三維重建技術(shù)是指通過三維物體的二維投影來(lái)恢復(fù)三維形狀的技術(shù)[1]，目前基于運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（Structure From Motion， SFM）的算法是多視圖三維重建研究的熱點(diǎn)方向[2]。

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

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

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

1.1? 特征檢測(cè)與匹配

1.1.1? ORB特征提取

1.1.1.1? 特征點(diǎn)提取與篩選

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

1.1.1.2? 計(jì)算特征點(diǎn)的灰度質(zhì)心

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

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

根據(jù)質(zhì)心坐標(biāo)得到特征點(diǎn)方向：

1.1.1.3? BRIEF算法描述

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

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

1.1.2? GMS算法圖像匹配

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

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

根據(jù)期望Ef和標(biāo)準(zhǔn)差Sf可以確定正確匹配和錯(cuò)誤匹配的可區(qū)分度：

ε=Ef+aSf（10）

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

1.2? SFM算法

1.2.1? 求解基礎(chǔ)矩陣

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

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

其中，P1和P2表示不同圖像的對(duì)應(yīng)特征點(diǎn)對(duì)，該式簡(jiǎn)潔描述了匹配點(diǎn)之間的空間位置關(guān)系。

1.2.2? 相機(jī)旋轉(zhuǎn)和平移向量求解

三維旋轉(zhuǎn)變換可以用3×3的正交矩陣T表示，相機(jī)i和j之間的旋轉(zhuǎn)關(guān)系可以表示為：

Tij=TjT-1i（12）

相機(jī)平移求解以相機(jī)旋轉(zhuǎn)結(jié)果作為輸入，相機(jī)相對(duì)于全局坐標(biāo)系的平移向量可通過式（13）求得：

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

2? 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

2.2? 圖像配準(zhǔn)實(shí)驗(yàn)

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

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

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

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

2.3? SFM三維重建試驗(yàn)

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

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

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

基于ORB算法的全局式三維重建最終得到的均方根誤差為0.28，在增量式重建中本文算法得到的重建誤差低于其他重建算法，表示基于改進(jìn)ORB算法的三維重建模型在一定程度上減小了重投影誤差，這是因?yàn)樵撍惴ǖ玫降钠ヅ潼c(diǎn)對(duì)更加準(zhǔn)確，誤匹配率更低，在通過特征點(diǎn)生成三維空間點(diǎn)時(shí)因誤匹配帶來(lái)的干擾也更小，而增量式和全局式三維重建算法所產(chǎn)生的重建誤差的差異主要是因?yàn)樵隽渴饺S重建會(huì)隨著圖像的加入不斷進(jìn)行光束法平差而產(chǎn)生誤差的累積，而全局式三維重建考慮了相鄰相機(jī)之間的空間關(guān)系，不會(huì)導(dǎo)致重建結(jié)果的漂移，并且這種差距會(huì)隨著序列圖像數(shù)量的增加而變大。

3? 結(jié)? 論

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

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

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

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

參考文獻(xiàn)：

[1] 鄭太雄，黃帥，李永福，等.基于視覺的三維重建關(guān)鍵技術(shù)研究綜述 [J].自動(dòng)化學(xué)報(bào)，2020，46（4）：631-652.

[2] 王巧麗，徐增波，張玲.基于運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)三維重建的應(yīng)用與研究進(jìn)展 [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] 普陽(yáng)光.改進(jìn)ASIFT算法的PMVS三維重建 [J].計(jì)算機(jī)時(shí)代，2018，312（6）：69-71.

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

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

[7] 倪翠，王朋，孫浩，等.一種基于四叉樹劃分的改進(jìn)ORB算法 [J].應(yīng)用科學(xué)學(xué)報(bào)，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特征點(diǎn)提取與匹配算法 [J].計(jì)算機(jī)工程與設(shè)計(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].計(jì)算機(jī)技術(shù)與發(fā)展，2018，28（12）：102-105+126.