朱軍桃,龔朝飛,趙苗興,王 雷,馮立朋

(1.桂林理工大學(xué) a.測(cè)繪地理信息學(xué)院;b.廣西空間信息與測(cè)繪重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541006; 2.南方測(cè)繪科技股份有限公司,廣州 510700)

無(wú)人機(jī)遙感是一種新型的遙感技術(shù)手段,具有機(jī)動(dòng)性高、作業(yè)速度快、成本低及分辨率高等優(yōu)勢(shì)。 無(wú)人機(jī)遙感影像的拼接技術(shù)廣泛應(yīng)用于航海、軍事、農(nóng)業(yè)等領(lǐng)域,其功能是將若干張遙感影像通過(guò)提取、匹配、拼接等過(guò)程生成一幅視野寬廣的場(chǎng)景影像[1]。 常見(jiàn)的拼接算法有變換域法、灰度法、特征點(diǎn)法。 特征點(diǎn)法對(duì)光照條件、旋轉(zhuǎn)等變化呈現(xiàn)出良好的魯棒性,具有更高的可靠性,所以是目前影像拼接的主流方向[2]。 特征點(diǎn)提取算法主要有ORB算法[3-4]、SIFT算法[5]、SURF[6]算法等。

本文先用ORB算法提取特征點(diǎn)， 再運(yùn)用改進(jìn)的KNN-RANSAC算法進(jìn)行特征匹配,該方法主要通過(guò)三方面來(lái)改進(jìn): 一是以塊為單位進(jìn)行匹配點(diǎn)的選取; 二是快速刪除不合理的單應(yīng)性矩陣,減少內(nèi)點(diǎn)的檢測(cè)時(shí)間; 三是通過(guò)最小化代價(jià)函數(shù)迭代優(yōu)化單應(yīng)性矩陣， 最后用改進(jìn)的加權(quán)平均算法對(duì)圖像進(jìn)行融合從而完成影像的無(wú)縫拼接,得到全景影像。

1 ORB算法

ORB特征點(diǎn)檢測(cè)算法是Rublee等[7]于2011年在ICCV上提出的,該特征點(diǎn)檢測(cè)算法是基于FAST算法和BRIEF算法提出的一種新算法，可應(yīng)用于特征點(diǎn)的提取,其提取效率其計(jì)算速度比 SIFT 快兩個(gè)數(shù)量級(jí)，匹配性能也不比SURF遜色。

1.1 FAST算法

FAST檢測(cè)算法由Rosten等[8]提出,該算法只是一種特征點(diǎn)檢測(cè)算法,無(wú)法實(shí)現(xiàn)特征描述處理。FAST算法進(jìn)行特征點(diǎn)檢測(cè)的主要步驟如下[9-10]:假定點(diǎn)q是圖像I中的一個(gè)像素點(diǎn),該點(diǎn)的像素值記為Iq,同時(shí)設(shè)置一個(gè)像素強(qiáng)度閾值T，如果在圓中存在n個(gè)連續(xù)的像素,這些像素比候選像素Iq的強(qiáng)度加上閾值T更亮(圖1)；或者比Iq減去閾值T要暗,則認(rèn)為q是一個(gè)角點(diǎn)(特征點(diǎn))。

圖1 FAST角點(diǎn)檢測(cè)Fig.1 Corner detection of FAST algorithm

FAST檢測(cè)算法由于高效的檢測(cè)效率而被廣泛使用，但是FAST算法檢測(cè)出來(lái)的特征點(diǎn)沒(méi)有方向。這時(shí)引進(jìn)強(qiáng)度質(zhì)心算法,其基本思想是: 假設(shè)某個(gè)角點(diǎn)的強(qiáng)度偏離其質(zhì)心,把這個(gè)偏離的距離用一個(gè)向量表示為

(1)

式中：(x，y)為圖像中的像素點(diǎn)的坐標(biāo)，I(x，y)為該點(diǎn)的強(qiáng)度值，強(qiáng)度質(zhì)心可表示為

C=(m10/m00,m01/m00),

(2)

式中:m10/m00為X軸方向的質(zhì)心;m01/m00為Y軸方向的質(zhì)心。 這樣可以把從特征點(diǎn)O到強(qiáng)度質(zhì)心C兩點(diǎn)之間的距離組成一個(gè)向量OC,該向量的方向便可作為FAST特征點(diǎn)的方向:

α=arctan 2(m01/m10),

(3)

即得到FAST檢測(cè)算法oFAST。

1.2 BRIEF算法

BRIEF算法是一種基于二進(jìn)制字符串的描述符,計(jì)算起來(lái)簡(jiǎn)單快捷。它先將圖像進(jìn)行平滑處理,然后測(cè)試并創(chuàng)建位向量[11-12]。

在一塊大小為S×S的像素塊上，運(yùn)用ORB算法選定一個(gè)圖像片段p，定義一個(gè)二進(jìn)制檢測(cè)τ

(4)

式中:x、y是圖像片段p中的任意兩個(gè)像素點(diǎn)；p(x)、p(y)是經(jīng)過(guò)平滑處理的圖像片段p在點(diǎn)(x，y)處的灰度強(qiáng)度值。在圖像片段p中選擇n個(gè)點(diǎn)對(duì)(x，y)，用BRIEF特征描述符定義一個(gè)包含nd維的二進(jìn)制測(cè)試集

(5)

在BRIEF算法中,為了協(xié)調(diào)算法的運(yùn)行速度、存儲(chǔ)效率和識(shí)別率,nd值在BRIEF算法中一般取256。為了使上述算法生成的特征描述符具有旋轉(zhuǎn)不變性,通過(guò)FAST特征點(diǎn)檢測(cè)的特征點(diǎn)的方向確定BRIEF特征描述符的方向,并將其記為rBRIEF[13]:對(duì)于任何在點(diǎn)(xi,yi)處的特征集,其n維二進(jìn)制測(cè)試后得到一個(gè)2×n維的矩陣

(6)

記由1.1節(jié)角點(diǎn)方向α=arctan 2(m01/m10)得到作為旋轉(zhuǎn)矩陣Rα

(7)

Sα=Rα·S。

(8)

最終得到了改進(jìn)的BRIEF特征描述符rBRIEF

gn(p,α):=fn(p)|(xi,yi)∈Sα。

(9)

綜上,ORB算法是將有方向的FAST檢測(cè)算法oFAST和rBRIEF特征描述符結(jié)合而成的一種新的特征點(diǎn)檢測(cè)算法。

2 特征點(diǎn)的匹配

2.1 基于KNN(K-Nearest-Neighbor)算法的粗匹配

KNN算法又叫K最近鄰算法，是進(jìn)行數(shù)據(jù)分類的一種較為簡(jiǎn)單的算法,該算法的核心思想是倘若一個(gè)樣本在特征空間K個(gè)最相鄰的樣本中的大多數(shù)樣本都屬于某一個(gè)類別,那么該樣本也將同樣屬于該類別。 簡(jiǎn)單來(lái)講，該算法的分類原則為少數(shù)服從多數(shù)的原則。

從圖2可知,有兩個(gè)不同類型的樣本數(shù)據(jù)： 一類樣本是正方形,另一類樣本是三角形。 位于中心的圓形即是待分類的數(shù)據(jù)。 當(dāng)K=3時(shí),樣本空間位于實(shí)線圓內(nèi),此時(shí)離圓點(diǎn)最近的是2個(gè)三角形和1個(gè)正方形,由于三角形數(shù)量多于正方形,此時(shí)將該圓點(diǎn)歸到三角形一類; 當(dāng)K=5時(shí),樣本空間延伸到虛線圓內(nèi),離圓點(diǎn)最近的有3個(gè)正方形和2個(gè)三角形,此時(shí)正方形占多數(shù),故此時(shí)將圓形劃分到正方形一類數(shù)據(jù)中[14]。

圖2 KNN算法簡(jiǎn)化圖Fig.2 Simplified sketch of KNN algorithm

為了提升KNN算法的匹配速度,一般都會(huì)選用合適的搜索方法。 常用的搜索算法有KD樹(shù)搜索算法和LSH算法。 其中KD樹(shù)搜索算法主要應(yīng)用于高維空間關(guān)鍵數(shù)據(jù)的搜索處理[15-16],而LSH算法是為了解決局部敏感問(wèn)題。 本文選用KD樹(shù)搜索算法用于影像的粗匹配。

2.2 改進(jìn)的RANSAC算法

2.2.1 以塊為單位進(jìn)行匹配點(diǎn)的選取 隨機(jī)選擇4塊,再?gòu)拿繅K中隨機(jī)選擇1個(gè)點(diǎn)，這樣的選取方式可以消除因點(diǎn)之間的距離太近而對(duì)參數(shù)精度產(chǎn)生的影響[17]。具體地，先計(jì)算出待配準(zhǔn)圖像中匹配點(diǎn)坐標(biāo)的最大值和最小值,然后將待配準(zhǔn)圖像中包含匹配點(diǎn)的區(qū)域平均分成3×3塊,如圖3所示。為了處理好匹配點(diǎn)的選擇不公平問(wèn)題,采用隨機(jī)塊的選取,選取方法如圖4所示。

圖3 匹配點(diǎn)分塊示意圖Fig.3 Schematic diagram block diagram of matching points

圖4 隨機(jī)塊選取方法示意圖Fig.4 Schetch of random block selection method

假設(shè)目標(biāo)圖像一共被分為M塊,那么區(qū)間[0,1]被分成M個(gè)間隔,每個(gè)間隔的寬度d為

(10)

式中:ni為第i塊的匹配點(diǎn)數(shù)目。 在實(shí)際問(wèn)題中進(jìn)行塊的隨機(jī)提取時(shí),如果生成一個(gè)[0,1] 均勻分布隨機(jī)數(shù)并落在第i個(gè)區(qū)間上,那么第i塊即被選中。

2.2.2 快速刪除不合理的單應(yīng)性矩陣 在估計(jì)出初始單應(yīng)矩陣之后,隨機(jī)從剩余匹配點(diǎn)對(duì)中選取一對(duì)匹配點(diǎn),檢驗(yàn)這對(duì)匹配點(diǎn)是否適合該單應(yīng)性矩陣:如果適合,則繼續(xù)執(zhí)行下一步操作;否則,剔除該單應(yīng)矩陣,重新選取匹配點(diǎn)對(duì)進(jìn)行估計(jì)，以減少內(nèi)點(diǎn)的檢測(cè)時(shí)間。

2.2.3 利用L-M非線性優(yōu)化方法算法 針對(duì)內(nèi)點(diǎn)集中的匹配點(diǎn)對(duì)Mi(x,y)和Ni(x′,y′),點(diǎn)Ni(x′,y′)通過(guò)單應(yīng)性矩陣H投影變換后得到的點(diǎn)的坐標(biāo)記為Ni′(u,v)，那么投影變換前后的誤差指標(biāo)函數(shù)為

(11)

式中:ei表示當(dāng)前誤差,n表示內(nèi)點(diǎn)的數(shù)量。

假定Hk為第k次迭代求出的單應(yīng)性矩陣,更新后的單應(yīng)性矩陣為

Hk+1=Hk+ΔH,

(12)

ΔH=[JT(H)J(H)+λI]-1JT(H)e(H)，

(13)

式中:e(H)表示誤差指標(biāo)函數(shù)中的ei(H)；I表示單位矩陣；J(H)為雅可比矩陣； 參數(shù)λ(λ>0)是一個(gè)比例系數(shù)(當(dāng)λ較大時(shí),L-M算法近似于梯度下降算法；當(dāng)λ較小時(shí),L-M算法近似于高斯牛頓算法)。 每迭代成功一步,參數(shù)λ就會(huì)相應(yīng)地減小,當(dāng)誤差指標(biāo)函數(shù)與最小值接近時(shí),此時(shí)的算法計(jì)算速度也最快,同時(shí)該時(shí)刻的單應(yīng)性矩陣的精度也最高。

2.2.4 改進(jìn)后的 RANSAC算法 ①?gòu)某跏计ヅ潼c(diǎn)對(duì)集合U中,按照?qǐng)D3、圖4的分塊方法及公式隨機(jī)選取4個(gè)點(diǎn)對(duì)作為一個(gè)內(nèi)點(diǎn)集合，并將其記為Ui; ②用線性方程組的方法解算出初始單應(yīng)性矩陣Hi; ③從U-Ui中隨機(jī)地選取1對(duì)匹配點(diǎn),若該點(diǎn)對(duì)能夠通過(guò)單應(yīng)性矩陣Hi(投影誤差小于給定的閾值)檢驗(yàn),則將該點(diǎn)對(duì)加入集合Ui中,否則舍棄單應(yīng)性矩陣Hi,返回到步驟②重新選擇樣本進(jìn)行初始單應(yīng)矩陣的估計(jì); ④使用單應(yīng)性矩陣Hi去檢驗(yàn)集合U-Ui中所有的匹配點(diǎn)對(duì),如果某個(gè)點(diǎn)對(duì)的投影誤差小于給定的閾值,便可將其加入集合Ui中去; ⑤若集合Ui中的內(nèi)點(diǎn)數(shù)量小于閾值T,那么返回到步驟③重新選擇樣本進(jìn)行初始單應(yīng)矩陣的估計(jì),否則利用Ui對(duì)單應(yīng)性矩陣Hi進(jìn)行重新估計(jì),并且通過(guò)投影誤差來(lái)對(duì)單應(yīng)性矩陣Hi進(jìn)行評(píng)估; ⑥如此迭代反復(fù)步驟②～⑤k次,最終找出最優(yōu)單應(yīng)矩陣Hi及與之相對(duì)應(yīng)的集合Ui,并使用集合Ui估計(jì)單應(yīng)矩陣H; ⑦通過(guò)單應(yīng)性矩陣H計(jì)算出集合Ui中每個(gè)點(diǎn)對(duì)的投影誤差ei(H)以及誤差指標(biāo)函數(shù)E(H); ⑧計(jì)算單應(yīng)性矩陣H各分量相對(duì)于ei(H)的偏導(dǎo)數(shù)與J(H),從而求得H的增量ΔH; ⑨如果E(Hk)小于給定的閾值,則可終止運(yùn)算,此時(shí)得到單應(yīng)性矩陣H即為迭代優(yōu)化后的最優(yōu)單應(yīng)性矩陣H; ⑩如果E(Hk+1)小于E(Hk),但是大于給定的閾值,則減小參數(shù)λ的值,返回到步驟⑧； 否則， 使參數(shù)λ的值變大,返回到步驟⑨。

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

3.1 特征點(diǎn)檢測(cè)算法實(shí)驗(yàn)

對(duì)特征點(diǎn)提取算法進(jìn)行具體的實(shí)驗(yàn)分析,圖5、圖6是兩組遙感影像圖,通過(guò)不同區(qū)域的劃分來(lái)進(jìn)行對(duì)比實(shí)驗(yàn)。在特征點(diǎn)提取方面,主要用SIFT算法與本文算法進(jìn)行對(duì)比。以圖5為例,提取結(jié)果見(jiàn)圖7、圖8。

從實(shí)驗(yàn)結(jié)果可以看出,SIFT提取到的特征點(diǎn)遠(yuǎn)多于本文算法,但是實(shí)際匹配數(shù)很接近(表1)。這說(shuō)明本文所選取的ORB特征點(diǎn)提取算法能達(dá)到實(shí)驗(yàn)效果,由于ORB算法是選用的FAST快速角點(diǎn)檢測(cè),所需時(shí)間遠(yuǎn)低于SIFT特征點(diǎn)提取算法,其處理速度約是SIFT的38倍,在實(shí)用性方面也高于SIFT算法。

3.2 影像匹配結(jié)果

針對(duì)改進(jìn)KNN-RANSAC算法進(jìn)行影像的特征匹配實(shí)驗(yàn),并與傳統(tǒng)KNN-RANSAC算法進(jìn)行對(duì)比。 以圖6為例,分別進(jìn)行ORB-改進(jìn)的KNN-RANSAC特征匹配、SIFT-KNN-RANSAC特征匹配、ORB-KNN-RANSAC特征匹配,如圖9所示。

圖5 實(shí)驗(yàn)用圖(第一組)Fig.5 Maps of experiment group 1

圖6 實(shí)驗(yàn)用圖(第二組)Fig.6 Maps of experiment group 2

圖7 SIFT特征點(diǎn)提取結(jié)果Fig.7 Feature points extraction results of SIFT algorithm

圖8 本文特征點(diǎn)提取結(jié)果Fig.8 Feature points extraction results of algorithm in this paper

圖9 不同改進(jìn)算法的KNN-RANSAC特征匹配圖像Fig.9 KNN-RANSAC feature matching of different improved algorithms

表1 不同算法的性能對(duì)比Table 1 Performance comparison of different algorithms

由匹配對(duì)連線結(jié)果可以看出,不同匹配方法所完成的匹配對(duì)數(shù)差異不大。 本文采用改進(jìn)的KNN-RANSAC算法濾除誤匹配點(diǎn)之后,直接顯示匹配結(jié)果,極大地降低了匹配時(shí)間且能達(dá)到更高的匹配率,詳見(jiàn)表2。

表2 不同算法的特征匹配Table 2 Feature matching of different algorithms

注: 匹配率=匹配個(gè)數(shù)2/兩幅圖特征點(diǎn)數(shù)之積。

3.3 影像融合拼接結(jié)果

對(duì)特征匹配后的影像進(jìn)行融合拼接。 以圖5為例得出3種特征匹配的融合結(jié)果,其中圖10a—d分別為ORB-改進(jìn)的KNN-RANSAC、SIFT-KNN-RANSAC、ORB-KNN-RANSAC、ORB-改進(jìn)的KNN-RANSAC特征匹配改進(jìn)加權(quán)融合結(jié)果圖,可以看出配準(zhǔn)后的影像直接拼接會(huì)出現(xiàn)重影、錯(cuò)位等現(xiàn)象。

本文采用改進(jìn)加權(quán)平均算法對(duì)圖像進(jìn)行融合處理,實(shí)驗(yàn)表明該方法能有效消除重影、錯(cuò)位等現(xiàn)象,最終拼接結(jié)果如圖10d、圖11、圖12所示。

4 結(jié) 論

本文提出的影像匹配算法,先用ORB算法提取特征點(diǎn),再用改進(jìn)的KNN-RANSAC算法來(lái)快速刪除誤匹配點(diǎn)以及進(jìn)行特征點(diǎn)匹配,最后對(duì)影像進(jìn)行改進(jìn)加權(quán)融合。

實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)于SIFT算法在保證精度的前提下匹配速度有很大的提高,同時(shí)改進(jìn)的KNN-RANSAC算法在匹配速度上明顯優(yōu)于傳統(tǒng)方法,從而證明了本文算法的優(yōu)越性。

圖10 圖像融合對(duì)比Fig.10 Comparison of image fusion

圖11 三幅影像拼接結(jié)果Fig.11 Mosaic results of three images

圖12 十幅影像拼接結(jié)果Fig.12 Mosaic results of ten images