黨宏社， 李俊達(dá)， 張選德

(陜西科技大學(xué) 電氣與控制工程學(xué)院， 陜西 西安 710021)

0 引言

圖像特征匹配是計(jì)算機(jī)視覺領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，通常用于視覺SLAM[1,2]、三維重建[3]、圖像檢索[4]、目標(biāo)跟蹤[5]等領(lǐng)域.提高圖像特征提取的魯棒性，特征匹配的準(zhǔn)確性和快速性是該領(lǐng)域的研究重點(diǎn)[6].圖像特征匹配的方法大致可分兩個(gè)步驟，首先提取兩幅待匹配圖的特征點(diǎn)，并用描述子對(duì)特征點(diǎn)進(jìn)行描述，然后根據(jù)描述子比較特征點(diǎn)之間的相似程度，判斷是否匹配.

特征點(diǎn)提取算法，有經(jīng)典的尺度不變特征轉(zhuǎn)換(Scale-Invariant Feature Transform，SIFT)、SURF(Speeded Up Robust Features)、ORB(Oriented FAST and Rotated BRIEF)、AKAZE(Accelerated-KAZE)[7-10]等算法.ORB算法是由Rublee等在2011年提出的，該算法計(jì)算速度是SURF的10倍，是SIFT的100倍[7,11]，能滿足大部分場(chǎng)景對(duì)實(shí)時(shí)性的要求，但是其提取的特征點(diǎn)較集中，且魯棒性不如SIFT.孫浩等[12]提出了區(qū)域劃分的方法，將圖像分成多個(gè)小區(qū)域，在每個(gè)區(qū)域上提取一定數(shù)量的特征點(diǎn)，使得特征點(diǎn)能夠更加均勻地分布，但其使用人為設(shè)定的閾值提取特征點(diǎn)，并未根據(jù)圖像像素特點(diǎn)自適應(yīng)調(diào)整，光照變化時(shí)，提取特征點(diǎn)魯棒性較差.楊弘凡等[13]提出了自適應(yīng)閾值的ORB算法，根據(jù)某像素周圍的其他像素亮度，計(jì)算該像素的閾值，但依然存在特征點(diǎn)重疊的問題，且逐像素計(jì)算閾值非常耗時(shí)，影響實(shí)時(shí)性.

特征點(diǎn)描述子粗匹配通常采用暴力匹配(Brute-Force)與快速最近鄰搜索庫(Fast Library for Approximate Nearest Neighbors，F(xiàn)LANN)[14].常用的誤匹配去除方法有RANSAC、松弛迭代法、最小中值法以及基于視差的濾波算法[15].粗匹配得到的結(jié)果效果較差，存在大量誤匹配，而常用誤匹配剔除方法需要多次迭代，計(jì)算量大，耗時(shí)長.

針對(duì)以上問題，本文提出一種基于加權(quán)網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)的改進(jìn)ORB算法.采用區(qū)域劃分的方法使特征點(diǎn)分布均勻，使用自適應(yīng)閾值提取特征點(diǎn)，降低亮度變化的影響，利用加權(quán)網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)剔除誤匹配，提高算法運(yùn)行速度.

1 ORB算法原理

ORB算法主要分兩個(gè)步驟，F(xiàn)AST特征點(diǎn)檢測(cè)和Rotated Brief描述子計(jì)算.特征點(diǎn)即圖像中突出的部分，其周圍像素具有像素值急劇由淺色變?yōu)樯钌奶卣?以圖1為例，F(xiàn)AST特征點(diǎn)提取過程如下：

圖1 FAST特征點(diǎn)提取示意圖

(1)從圖中選擇像素點(diǎn)P，設(shè)其灰度值為Vp.

(2)設(shè)定閾值t.

(3)比較以像素P為圓心的圓周上16個(gè)像素的灰度值，若連續(xù)q個(gè)點(diǎn)的灰度值都大于Vp+t或都小于Vp-t，則認(rèn)為P是一個(gè)特征點(diǎn).

(4)獲得特征點(diǎn)后，使用Rotated Brief計(jì)算特征描述子.首先用高斯核對(duì)圖像進(jìn)行平滑處理，然后以特征點(diǎn)P為圓心劃定鄰域，在鄰域中隨機(jī)選擇一對(duì)像素a和b，根據(jù)式(1)計(jì)算這一位的值.

(1)

式(1)中：τ是描述子這一位的值，V(a)和V(b)分別為像素a與b的灰度值，從像素P的鄰域中總共選擇n個(gè)像素對(duì)，最終構(gòu)成n維Brief描述子：

(2)

(5)FAST提取的特征點(diǎn)本身不具備旋轉(zhuǎn)不變性，使用灰度質(zhì)心法給特征點(diǎn)賦予方向[16].

2 改進(jìn)ORB特征點(diǎn)匹配算法

改進(jìn)ORB的圖像匹配算法流程如圖2所示.

圖2 改進(jìn)ORB的特征點(diǎn)匹配算法流程圖

首先構(gòu)建待匹配圖片和模板圖片的高斯差分金字塔，其次將金字塔各層圖像劃分成等大的幾個(gè)小區(qū)域，使用改進(jìn)自適應(yīng)閾值算法計(jì)算每個(gè)區(qū)域的閾值，然后提取每個(gè)區(qū)域的特征點(diǎn)并計(jì)算特征描述子，使用雙向匹配算法進(jìn)行粗匹配，最后使用WGMS算法剔除誤匹配特征點(diǎn)對(duì).

2.1 構(gòu)建高斯差分金字塔

ORB算法提取到的特征點(diǎn)不具備尺度不變性，在匹配過程中會(huì)造成誤匹配或漏匹配的問題，因此，需構(gòu)建高斯差分金字塔(DoG)，過程如圖3所示.

圖3 高斯差分金字塔構(gòu)建過程

首先將讀取的圖像做H次下采樣，獲得H組不同大小的圖，構(gòu)成圖像金字塔.然后使用式(3)所示的高斯函數(shù)對(duì)圖像金字塔的各層圖像做高斯濾波，式(3)中x，y為像素坐標(biāo)，σ是平滑因子.

(3)

以第一組為例，選取固定的σ對(duì)第一層圖像做濾波，獲得第二層圖像，然后將σ乘以比例系數(shù)k，獲得新的平滑因子kσ，用它對(duì)第二層圖像濾波，結(jié)果作為第三層圖像，以此類推，最終得到L層圖像，每層圖像尺寸相同，平滑因子不同，平滑因子計(jì)算如式(4)所示.對(duì)圖像金字塔各組圖像執(zhí)行以上操作，最終獲得H組，每組L層的高斯金字塔.

σ(L)=kL-2σL≥2

(4)

最后構(gòu)建高斯差分金字塔，其第一組第一層是由高斯金字塔的第一組第二層減第一層得到的，以此類推，第H組L層圖像是由高斯金字塔的第H組L+1層減第H組L層得到的，最終獲得H組，每組L-1層的高斯差分金字塔.

2.2 特征提取

通常，特征點(diǎn)越多，圖像匹配準(zhǔn)確率越高，但FAST算法提取的圖像特征點(diǎn)存在分布密集、重疊的問題，對(duì)特征描述十分不利，而且會(huì)影響匹配精度[12].此外在傳統(tǒng)的FAST算法中，特征提取的閾值由人為設(shè)定，固定不變的全局閾值無法兼顧圖像的不同區(qū)域，也無法消除光照影響，會(huì)出現(xiàn)特征點(diǎn)誤提取和誤匹配的問題.針對(duì)以上問題，本文提出一種區(qū)域劃分自適應(yīng)閾值的ORB算法，將圖像劃分為多個(gè)區(qū)域，采用自適應(yīng)閾值在每個(gè)區(qū)域上提取特征點(diǎn)，提高特征點(diǎn)的魯棒性.

首先，將高斯差分金字塔中的每幅圖像均勻地劃分為M×N個(gè)相同大小的區(qū)域，M是分割的行數(shù)，N是分割的列數(shù).然后，根據(jù)式(5)計(jì)算各個(gè)區(qū)域的閾值t.式中m為區(qū)域內(nèi)像素個(gè)數(shù)， 為區(qū)域內(nèi)每個(gè)像素的灰度值，Vmid為區(qū)域內(nèi)像素灰度值的中位數(shù)，此處不采用平均值是為了防止亮斑或暗斑導(dǎo)致灰度值出現(xiàn)極值，對(duì)閾值計(jì)算結(jié)果產(chǎn)生不利影響.最后，根據(jù)閾值使用FAST算法提取每個(gè)圖像區(qū)域的特征點(diǎn)，然后計(jì)算Brief描述子，使用灰度質(zhì)心法計(jì)算特征點(diǎn)的方向，差分金字塔所有特征點(diǎn)的集合即為圖片的特征點(diǎn).

(5)

2.3 特征點(diǎn)粗匹配

使用改進(jìn)ORB算法對(duì)模板圖和目標(biāo)圖進(jìn)行特征點(diǎn)提取，獲得兩幅圖像的特征點(diǎn)描述子集合.若采用暴力匹配算法進(jìn)行特征點(diǎn)粗匹配，會(huì)引入大量的錯(cuò)誤匹配，增大剔除誤匹配的工作量，故本文采用一種雙向匹配算法進(jìn)行粗匹配，降低誤匹配率，提高匹配算法的準(zhǔn)確率.算法步驟如下：

(1)選擇模板圖中的一個(gè)特征點(diǎn)Pmi，根據(jù)式6計(jì)算其與目標(biāo)圖所有特征點(diǎn)之間的漢明距離d，c(i)和d(i)表示特征描述子每一位的值.

(6)

(2)選取目標(biāo)圖中漢明距離到特征點(diǎn)Pmi最近的前兩個(gè)特征點(diǎn)，即最近鄰點(diǎn)Pti和次近鄰點(diǎn)Ptj，記他們到Pmi的距離為d1和d2.若d1/d2≤T，則認(rèn)為Pmi和最近鄰點(diǎn)Ptj是一對(duì)匹配點(diǎn)，其中T是人為設(shè)定的閾值.

(3)遍歷模板圖中的特征點(diǎn)，執(zhí)行(1)、(2)兩步操作，得到匹配對(duì)集合Cm.反過來遍歷目標(biāo)圖中的特征點(diǎn)，獲得匹配對(duì)集合Ct.判斷集合Cm中的某一對(duì)匹配對(duì)(Pmi,Ptj)與集合Ct的一對(duì)匹配對(duì)(Pti,Pmi)是否相同，如果滿足則保留該匹配對(duì)，否則刪除，最終獲得匹配對(duì)集合C={c1,c2,…,Cn}，其中cn=(Pmn,Ptn).

2.4 加權(quán)網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)剔除誤匹配

通常采用隨機(jī)抽樣一致性(RANSAC)算法剔除粗匹配中的誤匹配點(diǎn)，但該方法需要多次迭代才能獲得較好的結(jié)果，存在運(yùn)算量大的問題.RANSAC的改進(jìn)算法漸進(jìn)一致采樣(PROgressive SAmple Consensus，PROSAC)從不斷更新的最佳對(duì)應(yīng)點(diǎn)集中進(jìn)行采樣，節(jié)省了一定的計(jì)算量，但仍需多次迭代才能得到較好結(jié)果.GMS算法將運(yùn)動(dòng)平滑約束轉(zhuǎn)換為剔除錯(cuò)誤匹配的統(tǒng)計(jì)量，采用基于網(wǎng)格的得分估計(jì)器，提高了算法的實(shí)時(shí)性.該算法基于貝葉斯法則，即兩幅圖像正確匹配對(duì)的鄰域內(nèi)應(yīng)該有多個(gè)支持它的匹配對(duì)，而錯(cuò)誤匹配對(duì)的鄰域內(nèi)支持它的匹配對(duì)很少甚至沒有[17].

2.4.1 網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)算法原理

首先將模板圖和目標(biāo)圖網(wǎng)格化如圖4所示.圖中3×3加粗網(wǎng)格代表的是網(wǎng)格a5的鄰域，點(diǎn)劃線表示一個(gè)正確的匹配對(duì)ci，實(shí)線表示該匹配對(duì)領(lǐng)域內(nèi)正確的匹配對(duì)，虛線表示錯(cuò)誤匹配對(duì).

圖4 網(wǎng)格化示意圖

然后計(jì)算該匹配對(duì)的鄰域支持度S，設(shè)ci是匹配對(duì)，網(wǎng)格a5和b5鄰域9個(gè)網(wǎng)格中匹配對(duì)數(shù)量為ni(i=1,2,…,9)，則：

(7)

式(7)中：減一表示從總數(shù)中減去匹配對(duì)自身.由于匹配對(duì)是獨(dú)立分布的，S服從二項(xiàng)分布：

(8)

式(8)中：N表示鄰域總匹配對(duì)數(shù)量，Pt和Pf分別表示正確和錯(cuò)誤匹配率.式(8)的期望和方差為：

(9)

(10)

由此可得概率評(píng)估函數(shù)P：

(11)

(12)

式(12)中：α是超參數(shù)，用于調(diào)節(jié)閾值，經(jīng)驗(yàn)值選擇4～6.當(dāng)S大于τ時(shí)，cl是正確匹配，將其保留，否則為錯(cuò)誤匹配，將其刪除.

2.4.2 加權(quán)網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)算法

GMS算法的問題在于網(wǎng)格大小選取，如果網(wǎng)格很小，則僅僅考慮了很少的領(lǐng)域信息，算法性能降低，如果網(wǎng)格很大，則將包括很多不正確的對(duì)應(yīng)關(guān)系，影響篩選結(jié)果.本文提出加權(quán)網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)算法，將距離影響引入支持度計(jì)算中，使用泊松函數(shù)對(duì)網(wǎng)格進(jìn)行加權(quán)，使得中心網(wǎng)格的權(quán)值最大，外圍網(wǎng)格的權(quán)值較小，可推導(dǎo)出其二維函數(shù)為：

(13)

以a5為中心點(diǎn)根據(jù)式(13)計(jì)算各網(wǎng)格的權(quán)值并作歸一化處理，得到3×3權(quán)系數(shù)矩陣，式(13)中λ要取非整數(shù)，以保證最大值唯一.

(14)

(15)

當(dāng)S大于τ時(shí)，cl是正確匹配，將其保留，否則為錯(cuò)誤匹配，將其刪除.

3 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文提出算法的有效性，采用Kaggle平臺(tái)的Cat Vs Dog數(shù)據(jù)集以及自然場(chǎng)景下拍攝的圖像進(jìn)行實(shí)驗(yàn)，貓狗圖像各5 000張，所有實(shí)驗(yàn)均在Intel?CoreTM i5-10400F CPU@2.9 GHz，32GB RAM硬件環(huán)境中，Windows10 PyCharm Community Edition 2020軟件環(huán)境中完成.

3.1 特征點(diǎn)提取實(shí)驗(yàn)

對(duì)貓和狗的圖片使用傳統(tǒng)ORB算法和本文算法提取特征點(diǎn)，實(shí)驗(yàn)結(jié)果如圖5所示.從圖5(a)可以看出，傳統(tǒng)ORB算法在提取特征點(diǎn)時(shí)出現(xiàn)了4處大量聚集，分別為狗耳朵、眼睛、牙齒以及狗的鏈子，而且沒有在狗腰臀部分提取到特征點(diǎn).從圖5(b)可以看出，改進(jìn)ORB消除了狗耳朵、牙齒和鏈子上的特征點(diǎn)聚集，狗眼睛部分的聚集也明顯緩解，同時(shí)在狗腰臀部分提取了一定數(shù)量的特征點(diǎn),與圖5(c)中SIFT算法提取效果相近.從圖5(d)可以看出，特征點(diǎn)聚集在貓面部的眼睛和鼻子處，而圖5(e)中消除了貓面部大量重疊的特征點(diǎn)，同時(shí)在貓尾部提取到了一定數(shù)量的特征點(diǎn)，較圖5(f)提取了更多的特征點(diǎn).綜上，本文算法使用的區(qū)域劃分方法，使得特征點(diǎn)分布更加均勻，避免了特征點(diǎn)聚集重疊，同時(shí)采用了自適應(yīng)閾值的方法，使得固定閾值無法提取特征點(diǎn)的部位也能有效提取，提取效果與SIFT相近.

(a)、(d)傳統(tǒng)ORB算法提取效果(b)、(e)改進(jìn)ORB算法提取效果(c)、(f)SIFT算法提取效果 圖5 算法特征提取效果對(duì)比

表1統(tǒng)計(jì)了三種算法的特征提取時(shí)間.可以看出本文算法特征提取時(shí)間較傳統(tǒng)ORB算法平均慢了13.86%，較SIFT算法快了399.19%.

表1 特征提取時(shí)間

為進(jìn)一步驗(yàn)證自適應(yīng)閾值的有效性，人為調(diào)整圖片，在原圖的基礎(chǔ)上增加和減少亮度，實(shí)驗(yàn)結(jié)果如圖6所示.圖片亮度變化后，傳統(tǒng)ORB算法提取的特征點(diǎn)依然存在大量重疊問題，亮度調(diào)暗的情況下在大部分區(qū)域無法提取到特征點(diǎn)，而改進(jìn)ORB算法和SIFT算法在光線變換情況下依然可以穩(wěn)定提取特征點(diǎn)，且特征點(diǎn)分布均勻，從圖6(k)、(l)中可以看出,改進(jìn)ORB算法在較暗的區(qū)域可以提取到特征點(diǎn)，效果優(yōu)于傳統(tǒng)ORB算法和SIFT算法.

(a)、(d)、(g)、(j)傳統(tǒng)ORB算法提取效果(b)、(e)、(h)、(k)改進(jìn)ORB算法提取效果(c)、(f)、(i)、(l)SIFT算法提取效果圖6 亮度變化后特征提取效果對(duì)比

3.2 特征匹配實(shí)驗(yàn)

改變數(shù)據(jù)集中圖片的亮度，對(duì)傳統(tǒng)ORB算法、ORB+RANSAC算法、ORB+GMS算法、SIFT算法、本文算法、文獻(xiàn)[12]和文獻(xiàn)[13]中算法進(jìn)行測(cè)試比較.七種算法匹配結(jié)果如圖7所示.從圖7(a)和圖7(f)可以看出，傳統(tǒng)ORB和文獻(xiàn)[12]算法在光照改變的情況下，誤匹配對(duì)較多，左圖部分特征點(diǎn)與右圖另一只貓的特征點(diǎn)匹配上了，同一只貓身上也存在較多的誤匹配對(duì)，圖7(b)、(c)、(d)、(e)中誤匹配較少，只有少量特征點(diǎn)誤匹配到了另一只貓身上，同一只貓身上的誤匹配數(shù)量也明顯較少.

(a)傳統(tǒng)ORB算法 (b)ORB+RANSAC算法

(c)ORB+GMS算法 (d)SIFT算法

(e)本文算法 (f)文獻(xiàn)[12]算法

(g)文獻(xiàn)[13]算法圖7 特征匹配結(jié)果

表2統(tǒng)計(jì)了七種算法特征點(diǎn)匹配耗時(shí)以及匹配準(zhǔn)確率.可以看出本文算法耗時(shí)較傳統(tǒng)ORB算法慢10.7%，較ORB+GMS算法慢1.1%，快于其他四種算法，算法實(shí)時(shí)性高，匹配準(zhǔn)確率高于其他六種算法，較傳統(tǒng)ORB算法提高41.7%，較ORB+GMS算法提高5.5%.

表2 特征點(diǎn)匹配結(jié)果對(duì)比

4 結(jié)論

本文針對(duì)ORB特征點(diǎn)過于集中重疊的問題，提出了區(qū)域劃分的方法，使特征點(diǎn)分布更為均勻.針對(duì)ORB算法在亮度變化情況下特征點(diǎn)提取不穩(wěn)定，匹配準(zhǔn)確率低的問題，提出了一種自適應(yīng)閾值的方法提取特征點(diǎn)，提高了特征點(diǎn)提取的魯棒性.針對(duì)粗匹配結(jié)果差的問題，提出WGMS算法剔除誤匹配，提高了匹配準(zhǔn)確率.實(shí)驗(yàn)結(jié)果表明本文算法可以有效對(duì)抗光照干擾，在保證實(shí)時(shí)性的情況下提高特征匹配的準(zhǔn)確率，對(duì)圖像識(shí)別，圖像拼接等領(lǐng)域研究具有良好的實(shí)用價(jià)值.