郭 芮,許 鋼,李若楠,趙春葉,江娟娟
(安徽工程大學(xué) 檢測(cè)技術(shù)與節(jié)能裝置安徽省重點(diǎn)實(shí)驗(yàn)室,安徽 蕪湖 241000)
近年來,科學(xué)技術(shù)迅猛發(fā)展,值此方興未艾之際,計(jì)算機(jī)視覺技術(shù)應(yīng)運(yùn)而生,正不斷滲透到人們的日常生活中,其中比較重要的內(nèi)容就是圖像中特征點(diǎn)匹配算法的研究,它廣泛應(yīng)用于多個(gè)領(lǐng)域中[1-3],例如移動(dòng)機(jī)器人導(dǎo)航、圖像拼接、三維重建以及醫(yī)學(xué)圖像分析等計(jì)算機(jī)視覺領(lǐng)域的基礎(chǔ)研究。目前最為廣泛的特征點(diǎn)匹配算法有SIFT[4]、SURF[5]、ORB[6]等。
LAWE[4]等人于1999年提出了尺度不變的特征變換SIFT(Scale-invariant Feature Transform)算法,該算法基于特定興趣點(diǎn)而與圖像大小和旋轉(zhuǎn)無關(guān),對(duì)于圖像旋轉(zhuǎn)、尺度縮放具有較好的穩(wěn)定性,同時(shí)對(duì)亮度、視角等條件的微小變化魯棒性強(qiáng),但該算法的局部特征點(diǎn)檢測(cè)和描述子特征是建立在高維的基礎(chǔ)上,這使得整個(gè)過程計(jì)算量龐大、消耗時(shí)間多,難以滿足實(shí)時(shí)性的要求。為了克服上述不足,2006年BAY[5]等人基于SIFT的基礎(chǔ)上提出一種加速魯棒性特征SURF(Speeded Up Robust Feature)算法,由于SURF算法最大的特點(diǎn)在于采用了哈爾特征以及積分圖像的概念,這使得典型的SURF算子比SIFT算子快大概3倍左右,大大加快了程序執(zhí)行效率。機(jī)器視覺技術(shù)的發(fā)展使得人們更加關(guān)注特征匹配算法在執(zhí)行效率方面的性能,有大量學(xué)者研究表明,ORB算法的運(yùn)行速度比上述兩種算法快至少一個(gè)數(shù)量級(jí)。該算法于2011年由RUBLEE[6]等人在ICCV上提出,它在特征點(diǎn)質(zhì)量和性能間取得了較好的折中。從實(shí)時(shí)性角度評(píng)測(cè),它是目前運(yùn)行速度較快的算法。ORB是一種局部不變特征檢測(cè)子,即圖像發(fā)生旋轉(zhuǎn)變換時(shí)仍可以保持很好的魯棒性,但對(duì)于圖像尺度變化較大的圖像,傳統(tǒng)ORB算法的匹配效果卻不理想[7],由于該算法尺度空間的構(gòu)建環(huán)節(jié)不夠成熟,當(dāng)圖像尺度發(fā)生突變時(shí),圖像特征匹配的精度會(huì)受影響。文獻(xiàn)[8-10]分別通過結(jié)合SIFT和SURF檢測(cè)算子使得改進(jìn)后的ORB算法擁有尺度不變特性,但實(shí)時(shí)性和匹配精度難以兼得,可見對(duì)ORB的研究仍具有非常大的意義。
本論文提出一種基于非線性尺度空間的ORB特征匹配改進(jìn)算法,該算法借鑒A-KAZE[11](Accelerated-KAZE)算法思想對(duì)ORB進(jìn)行改進(jìn),通過構(gòu)建非線性尺度空間提取顯著特征點(diǎn),使其對(duì)尺度變換的圖像具備較強(qiáng)的表現(xiàn)。與此同時(shí),使用PROSAC[12](漸進(jìn)一致性采樣)對(duì)匹配點(diǎn)對(duì)提純,進(jìn)而提高ORB算法的匹配質(zhì)量,從而達(dá)到不失精度的條件下滿足實(shí)時(shí)匹配的目的。
ORB算法具有局部不變性,該算法采用以速度著稱的加速分割測(cè)試特征FAST[6](Feature From Accelerated Segment Test)檢測(cè)特征點(diǎn),利用旋轉(zhuǎn)二進(jìn)制魯棒基元獨(dú)立特征BRIEF[6](Binary robust independent elementary feature)算法生成描述符,再以Hamming距離為相似性度量準(zhǔn)則比較描述符完成粗匹配。其主要步驟如下:
(1)關(guān)鍵點(diǎn)提?。翰捎胦-FAST算法進(jìn)行關(guān)鍵點(diǎn)提取,加入Rosin灰度質(zhì)心法(Intensity Centroid)為其提供方向特性,使得后面的特征描述符具有方向信息;
(2)建立特征描述符:ORB算子采用具備旋轉(zhuǎn)角度的改進(jìn)BRIEF算法,即rBRIEF算法。其主要思想是依據(jù)像素點(diǎn)灰度值的大小,利用隨機(jī)選點(diǎn)機(jī)制在某個(gè)特征點(diǎn)的周邊選取一定數(shù)量的像素點(diǎn)對(duì)測(cè)試集,生成二進(jìn)制串描述符;
(3)特征點(diǎn)粗匹配:以Hamming距離作為相似性度量準(zhǔn)則對(duì)描述子進(jìn)行比較,若滿足一定的條件則認(rèn)為該特征點(diǎn)匹配對(duì)是正確的。該方法原理簡(jiǎn)單易于操作。
本文提出的一種基于非線性尺度空間的改進(jìn)ORB算子,其主要流程如1所示。
圖1 改進(jìn)ORB算法流程圖Fig.1 Improved ORB algorithm flow chart
首先借鑒A-KAZE[8]算法原理利用FED數(shù)值分析框架來求解可變傳導(dǎo)擴(kuò)散方程,進(jìn)而完成非線性尺度空間的構(gòu)建;其次采用FAST-9算法在非線性尺度空間的每一層進(jìn)行特征點(diǎn)的檢測(cè)并計(jì)算特征點(diǎn)的質(zhì)心方向;再次結(jié)合之前獲取的具有方向特性的特征點(diǎn),采用rBRIEF算法生成具有二進(jìn)制字符串特點(diǎn)的特征描述子;最后使用FLANN方法計(jì)算漢明距離進(jìn)行特征點(diǎn)的粗匹配,再對(duì)其匹配結(jié)果采用PROSAC算法(改進(jìn)的RANSAC算法)剔除噪聲點(diǎn),實(shí)現(xiàn)更加精準(zhǔn)的匹配。
由于傳統(tǒng)的ORB算法沒有很好的解決尺度不變性,所以在進(jìn)行角點(diǎn)檢測(cè)之前要對(duì)其構(gòu)建尺度空間。傳統(tǒng)的基于Gaussian尺度空間的構(gòu)建存在最大的缺陷就是高斯濾波無法保留邊緣、邊界、細(xì)節(jié)信息,它會(huì)把所有尺度的細(xì)節(jié)和噪聲平滑到相同的水平,這導(dǎo)致其位置精度和獨(dú)特性大打折扣。而基于A-KAZE算法的非線性尺度分解有望解決上述不足。
2.1.1非線性擴(kuò)散
鑒于傳統(tǒng)的正向歐拉法在求解非線性方程數(shù)值時(shí),迭代收斂步長非常短、消耗時(shí)間資源很大導(dǎo)致計(jì)算復(fù)雜度高。針對(duì)上述不足,本文在構(gòu)建一個(gè)類似金字塔型的非線性尺度空間來求解非線性濾波擴(kuò)散方程時(shí),采用快速顯示擴(kuò)散FED[13](Fast explicit diffusion)算法。可以通過非線性偏微分方程來描述傳導(dǎo)方程:
(1)
式(1)中,div和L分別為散度與圖像L的梯度求解操作,c(x,y,t)為傳導(dǎo)擴(kuò)散函數(shù);L為圖像的亮度矩陣;時(shí)間t為尺度因子,其值越大代表圖像越簡(jiǎn)單且尺度越大;其中傳導(dǎo)方程中引用的函數(shù)c依賴于圖像局部差分結(jié)構(gòu)形式的張量或標(biāo)量,使得擴(kuò)散能夠自適應(yīng)于圖像局部特性,公式定義如下:
c(x,y,t)=g(|Lσ(x,y,t)|)
(2)
(3)
(4)
(5)
式(3)~(5)中參數(shù)λ為閾值,是控制擴(kuò)散級(jí)別的對(duì)比度因子,決定了圖像平滑過程中保留邊緣信息量的多少,其值與保留的邊緣信息量呈負(fù)相關(guān)。本文的參數(shù)λ取值為70%比例的梯度直方圖。根據(jù)大量實(shí)驗(yàn)得知式(4)所表示的擴(kuò)散系數(shù)比較容易計(jì)算,所以也很常用。
2.1.2快速顯示擴(kuò)散算法
A-KAZE算法的尺度空間構(gòu)造與SIFT類似,該算法提出的FED集顯式和半隱式理論的優(yōu)勢(shì)于一體。此外,采用顯式理論分解盒子濾波[14]來近似高斯濾波器,該技術(shù)的實(shí)現(xiàn)借鑒了積分圖像的思想原理,使得計(jì)算的復(fù)雜度降低,更加便于應(yīng)用。其本質(zhì)思想是將圖像金字塔分為O個(gè)組和S個(gè)組內(nèi)子層,M=O×S是濾波后整個(gè)尺度空間包含的圖像總量。且在M次循環(huán)操作中每次循環(huán)皆為一個(gè)n次的迭代過程,我們定義第j次的迭代步長為:
(6)
式(6)中τmax為顯示求解穩(wěn)定條件范圍內(nèi)的最大閾值步長。利用FED算子可以將(1)式用矢量化矩陣表示為:
(7)
式(7)中,τ為常量,控制顯示擴(kuò)散的穩(wěn)定條件;A(Li)為圖像亮度在第i層上的傳導(dǎo)矩陣,且在整個(gè)循環(huán)過程中保持不變。
由于非線性偏微分方程不存在解析解,采用FED算法求得(1)式近似解為:
Li+1,j+1=(I+τjA(Li))Li+1,j,j=0,1,…,n-1
(8)
式(8)中,I為單位矩陣,n為顯示擴(kuò)散步數(shù),圖像亮度初始化設(shè)置為:Li+1,0=Li。
2.1.3非線性尺度空間的構(gòu)造
采用FED算法來完成尺度空間的創(chuàng)建,該尺度級(jí)別按對(duì)數(shù)遞增,與SIFT不同之處是對(duì)圖像不用進(jìn)行下采樣,它的各個(gè)層級(jí)均取用與原始圖像相同的分辨率。對(duì)應(yīng)的尺度參數(shù)σi為:
(9)
由于熱傳導(dǎo)擴(kuò)散模型是以時(shí)間為單元,故需將以像素為單位的參數(shù)σi轉(zhuǎn)化為時(shí)間單元。在高斯尺度空間下,使用標(biāo)準(zhǔn)差為σ的高斯核對(duì)圖像進(jìn)行卷積,相當(dāng)于對(duì)圖像進(jìn)行持續(xù)時(shí)間為t=σ2/2的濾波。根據(jù)式(9)求出兩者的轉(zhuǎn)換公式:進(jìn)化時(shí)間ti。
(10)
最后再結(jié)合式(7)求得相應(yīng)的尺度圖像。這樣就可以得到一個(gè)O組,每組S層的圖像金字塔了。
ORB算法采用改進(jìn)的FAST算法(oFAST)進(jìn)行角點(diǎn)檢測(cè),早期的Harris和SIFT特征點(diǎn)提取算法都是基于自相關(guān)矩陣響應(yīng)值的算法,一般會(huì)涉及到卷積運(yùn)算,導(dǎo)致運(yùn)算量龐大,F(xiàn)AST算法剛好克服了這方面的缺陷。ROSTEN等人于文獻(xiàn)[15]給出FAST的定義:在某個(gè)候選像素點(diǎn)的圓形范圍內(nèi),通過比較該點(diǎn)與鄰域點(diǎn)的灰度差值來判別該點(diǎn)是否為特征點(diǎn)。具體的特征提取過程如下:
(1)確定檢測(cè)范圍:如圖2所示,以像素點(diǎn)P為圓心,以3個(gè)像素單位為半徑畫圓,選取圓上16個(gè)像素點(diǎn)為待檢測(cè)的點(diǎn)。
(2)設(shè)定合適閾值:將上述(1)中待檢測(cè)的16個(gè)像素點(diǎn)的灰度值與P點(diǎn)灰度值逐一比較,兩點(diǎn)灰度值之差的絕對(duì)值大于某一閾值εd,則認(rèn)為這兩點(diǎn)是不同的點(diǎn)。特征點(diǎn)的響應(yīng)函數(shù)如下:
(11)
式(11)中I(x)為圓周上任意一個(gè)像素點(diǎn)的灰度值,I(p)為圓心像素點(diǎn)的灰度值,對(duì)于給定的閾值N0一般取9或12。當(dāng)N>N0,則認(rèn)為P為一個(gè)角點(diǎn)。重復(fù)上述步驟,對(duì)除P以外的每一個(gè)像素點(diǎn)執(zhí)行相同的操作,最終找出所有的角點(diǎn)。
(3)增加尺度信息:FAST算子沒有提供多尺度特性,這里的改進(jìn)方法是將上節(jié)構(gòu)建的非線性尺度空間,在其包含的O組,每組S層的圖像金字塔上,對(duì)每層圖像分別進(jìn)行FAST特征提取,從而形成尺度空間。
圖2 FAST角點(diǎn)檢測(cè)Fig.2 FAST feature detection
(4)確定圖像矩的主方向:ORB采用Rosin灰度質(zhì)心法使得描述算子具備旋轉(zhuǎn)不變特性。
在一個(gè)小的圖像塊中定義矩為:
(12)
式(12)中,I(x,y)為(x,y)點(diǎn)的灰度表達(dá)式。根據(jù)式(12)可以得到0階矩m00和1階矩m01、m10,通過矩可以找到圖像塊的質(zhì)心:
(13)
連接圖像塊的幾何中心O和質(zhì)心C,得到一個(gè)方向向量OC,特征點(diǎn)方向用公式定義為:
(14)
通過以上方法,F(xiàn)AST角點(diǎn)便具備了尺度和旋轉(zhuǎn)的信息。
ORB算法采用改進(jìn)的BRIEF算法(rBRIEF)建立描述符,其核心思想是采用隨機(jī)選點(diǎn)機(jī)制在圖像中選取像素點(diǎn),通過比較它們的灰度值從而得到描述符。其具體過程如下:
(1)為消除原BRIEF描述符以像素為測(cè)試點(diǎn)所帶來的噪聲影響,改進(jìn)算法在特征描述過程中,是以特征點(diǎn)為中心設(shè)定鄰域?yàn)?1×31像素的圖像塊,以此作為測(cè)試點(diǎn)集的候選區(qū)域。每次測(cè)試都是在一個(gè)5×5的子窗口內(nèi)隨機(jī)選取一個(gè)點(diǎn)對(duì)(x,y),使用如下準(zhǔn)則進(jìn)行二進(jìn)制賦值:
(15)
式(15)中,p(x)為經(jīng)過高斯平滑后的像素點(diǎn)x=(u,v)T的灰度函數(shù),p(y)同理。
(2)按照一定準(zhǔn)則在候選區(qū)域內(nèi)選取n個(gè)(xi,yi)點(diǎn)對(duì),即可輸出一個(gè)由n維二進(jìn)制字符串表示的描述向量:
(16)
(3)考慮到上述的描述向量沒有方向信息,ORB的解決方法是將式(14)的主方向作為特征向量的主方向。對(duì)于任意n個(gè)待測(cè)試點(diǎn)集,引入一個(gè)2×n的矩陣Q:
(17)
(4)對(duì)矩陣Q進(jìn)行旋轉(zhuǎn)變換。結(jié)合之前通過方向角θ求得相應(yīng)的旋轉(zhuǎn)矩陣Rθ,就能得到帶有方向信息的特征點(diǎn)描述矩陣Qθ:
(18)
(5)得到具有旋轉(zhuǎn)角度的特征描述子:
gn(p,θ)=fn(p)|(xi,yi)∈Qθ
(19)
通過greedy貪婪算法搜索出具有較高方差和較低相關(guān)性的n個(gè)(文獻(xiàn)[6]中n=256)點(diǎn)對(duì)作為最終的描述符,大的方差和不相關(guān)性有利于描述符保持較大區(qū)分性和描述能力的特性,為后續(xù)的特征匹配打好基礎(chǔ)。
上節(jié)求得的特征描述符是一個(gè)二進(jìn)制碼串,這里先對(duì)其采用Hamming距離快速近似最近鄰(FLANN)方法進(jìn)行粗匹配。由于外界噪聲因素的影響,粗匹配后的結(jié)果仍存在很多偽匹配對(duì),影響匹配效果。故采用PROSAC算法剔除外點(diǎn),從而提高匹配質(zhì)量。
其中粗匹配中采用原理簡(jiǎn)單、操作方便的FLANN算法,該算法在OpenCV庫中現(xiàn)已集成。由于RANSAC算法在剔除外點(diǎn)的過程中沒有考慮特征點(diǎn)間的差異性,其隨機(jī)抽樣模式會(huì)帶來迭代次數(shù)不穩(wěn)定、浪費(fèi)大量計(jì)算資源等弊端。本文采用PROSAC算法對(duì)特征點(diǎn)粗匹配對(duì)進(jìn)行優(yōu)化,該方法對(duì)包含較多離群點(diǎn)的數(shù)據(jù)仍然適用。其核心思想是依據(jù)一定準(zhǔn)則將樣本點(diǎn)進(jìn)行降序排列,在較高匹配率的粗匹配子集中計(jì)算模型,從而減少迭代次數(shù),最優(yōu)估計(jì)解也會(huì)盡早出現(xiàn)。算法流程如下:
(1)計(jì)算粗匹配后的點(diǎn)對(duì)集合S中每對(duì)匹配點(diǎn)間的距離,根據(jù)距離大小對(duì)S中的點(diǎn)對(duì)進(jìn)行降序排列;
(2)選取前m個(gè)高質(zhì)量的匹配點(diǎn)對(duì),構(gòu)成新的樣本集S';
(3)在樣本集S'中選取4組質(zhì)量最高的點(diǎn)對(duì),計(jì)算單應(yīng)矩陣Η;
(5)計(jì)算當(dāng)前內(nèi)點(diǎn)數(shù)量t,若t
(6)內(nèi)點(diǎn)數(shù)量更新為t后,用當(dāng)前內(nèi)點(diǎn)集再次計(jì)算單應(yīng)矩陣Η并完成剔除誤匹配的工作。
實(shí)驗(yàn)一:針對(duì)本文所提出的改進(jìn)算法,設(shè)計(jì)了兩類實(shí)驗(yàn):(1)尺度不變性對(duì)比實(shí)驗(yàn);(2)綜合不變性對(duì)比實(shí)驗(yàn),即尺度和旋轉(zhuǎn)角度同時(shí)改變的情況下進(jìn)行的實(shí)驗(yàn)。使用上述兩類實(shí)驗(yàn),分別對(duì)兩組圖像進(jìn)行測(cè)試,其中輸入的原始圖像格式為.png,像素大?。?50×750,兩張圖像分別取自室內(nèi)和室外環(huán)境。
圖3 第一組尺度變化下的測(cè)試結(jié)果圖Fig.3 The first set of test results under the scale changes
圖4 第二組尺度變化下的測(cè)試結(jié)果圖Fig.4 The second set of test results under the scale changes
通過圖3、圖4中的(a)、(b)對(duì)比實(shí)驗(yàn)以及表1不難發(fā)現(xiàn),采用ORB算法的測(cè)試效果圖中,未提純前成功匹配的特征點(diǎn)對(duì)數(shù)目偏少,分別為361、329,提純后正確匹配的點(diǎn)對(duì)數(shù)量分別為288、257,其正確匹配率分別為80%和78%。而采用改進(jìn)算法的測(cè)試效果圖中,未提純前成功匹配的特征點(diǎn)對(duì)數(shù)目較多,分別為428、413,提純后正確匹配的點(diǎn)對(duì)數(shù)量分別為398、376,其正確匹配率分別為93%和91%。相較于原算法,改進(jìn)算法采用快速的FED算子來提高尺度空間的構(gòu)建速度,并且沿用了ORB特征檢測(cè)算法。在有效特征點(diǎn)數(shù)目增多的情況下,平均匹配精度提升了13%。但由于添加了PROSAC算法二次剔除誤匹配點(diǎn),相較于原ORB算法,運(yùn)行時(shí)間平均增加了21.2 ms。
表1 ORB算法與改進(jìn)算法的匹配質(zhì)量比較Tab.1 Comparison of matching quality between ORB algorithm and improved algorithm
圖5 第一組尺度旋轉(zhuǎn)變化下的測(cè)試結(jié)果圖Fig.5 The first set of test results under the change of scale rotation
圖6 第二組尺度旋轉(zhuǎn)變化下的測(cè)試結(jié)果圖Fig.6 The second set of test results under the change of scale rotation
圖5、圖6是針對(duì)圖像旋轉(zhuǎn)、多尺度的綜合測(cè)試效果圖。表2是針對(duì)匹配精度和算法執(zhí)行時(shí)間方面進(jìn)行的定量分析。結(jié)合表2和兩組(a)、(b)對(duì)比圖可以看出,采用原算法的測(cè)試效果圖中,未提純前成功匹配的特征點(diǎn)對(duì)數(shù)量分別為341、314,提純后正確匹配的點(diǎn)對(duì)數(shù)目分別為276、236,其準(zhǔn)確率分別為81%和75%。而采用改進(jìn)算法的測(cè)試效果圖中,未提純前成功匹配的特征點(diǎn)對(duì)數(shù)量分別為423、408,提純后正確匹配的點(diǎn)對(duì)數(shù)目分別為389、359,其準(zhǔn)確率分別為92%和88%。由此可得,改進(jìn)算法提取到的特征點(diǎn)更加豐富,且增加了二次提純特征點(diǎn)匹配對(duì)的環(huán)節(jié),因此在匹配精度上平均提升了12%,在運(yùn)行時(shí)間上平均增加了23.47 ms,但不影響實(shí)際應(yīng)用中算法的實(shí)時(shí)性。
表2 ORB算法與改進(jìn)算法的匹配質(zhì)量比較Tab.2 Comparison of matching quality between ORB algorithm and improved algorithm
實(shí)驗(yàn)二:為了進(jìn)一步驗(yàn)證改進(jìn)算法的性能,通過復(fù)現(xiàn)率[16]來檢測(cè)在不同尺度下提取特征點(diǎn)的魯棒性。復(fù)現(xiàn)率是指兩幀圖像上提取到的相同點(diǎn)對(duì)數(shù)量占總提取點(diǎn)對(duì)數(shù)的百分比,評(píng)測(cè)公式如下:
(20)
式(20)中,min(di,dj)為基準(zhǔn)圖、待匹配圖中提取的特征點(diǎn)數(shù)目的最小值;Dij為兩幅圖的重復(fù)點(diǎn)數(shù)。復(fù)現(xiàn)率越高表示特征匹配算法的魯棒性越強(qiáng),即該算法越穩(wěn)定。實(shí)驗(yàn)二是對(duì)取自室外的圖像(柯基圖)進(jìn)行實(shí)驗(yàn),檢測(cè)不同尺度σ(σ∈[1,3])下的角點(diǎn),實(shí)驗(yàn)結(jié)果如下:
圖7 不同尺度下復(fù)現(xiàn)率比較Fig.7 Comparison of recurrence rates at different scales
由圖7不難發(fā)現(xiàn),改進(jìn)算法相較于原ORB算法,在尺度不變性方面魯棒性更強(qiáng),且角點(diǎn)檢測(cè)更加穩(wěn)定。
本文針對(duì)ORB算法沒有解決尺度不變性、誤匹配率高等問題,提出優(yōu)化算法。首先通過借鑒A-KAZE算法原理構(gòu)建非線性尺度空間,其次沿用ORB算子在每層尺度空間的圖像上進(jìn)行特征提取并計(jì)算描述子,再次使用FLANN算子和PROSAC算法雙重篩選原則剔除誤匹配,最終得到匹配質(zhì)量較高的結(jié)果。實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法有效地解決了尺度不變性的問題,提取到的特征點(diǎn)在細(xì)節(jié)和邊緣方面處理得更好,并且匹配精確度和算法效率得到了一定改善,適用于匹配精度高、尺度變化較大的應(yīng)用場(chǎng)景。