基于變換矩陣空間優(yōu)化搜索的模板匹配方法

基于變換矩陣空間優(yōu)化搜索的模板匹配方法

1基于模板匹配的目標(biāo)檢測(cè)算法基于視覺(jué)檢測(cè)目標(biāo)，如人類檢測(cè)、行人檢測(cè)、車輛檢測(cè)等。通常需要通過(guò)算法學(xué)習(xí)獲取模型模型和分類器模型的參數(shù)，然后利用模型和分類器模型確定實(shí)時(shí)目標(biāo)的參數(shù)。傳統(tǒng)機(jī)器學(xué)習(xí)的方法做目標(biāo)檢測(cè)達(dá)到較高水平的如梯度方向直方圖特征(HistogramofOrientedGradient,HOG)結(jié)合支持向量機(jī)(SupportVectorMachine,SVM)分類器基于模板匹配的目標(biāo)檢測(cè)只需要具有目標(biāo)模板圖像,通過(guò)匹配算法找到實(shí)時(shí)圖像中與目標(biāo)模板圖像相似的區(qū)域位置,達(dá)到檢測(cè)模板目標(biāo)的目的。當(dāng)前已有較多學(xué)者研究了基于模板匹配的目標(biāo)檢測(cè)算法航空?qǐng)D像處理領(lǐng)域中,由于航空拍攝距離較遠(yuǎn),拍攝角度變化差異較大,通常圖像場(chǎng)景較復(fù)雜,目標(biāo)較小,分辨率遠(yuǎn)低于通常意義下拍攝的圖像(如照相機(jī)、手機(jī)、監(jiān)控?cái)z像頭等拍攝的圖像),因此制作的目標(biāo)模板較小,低分辨率下圖像特征較弱,復(fù)雜場(chǎng)景帶來(lái)的干擾較大,多視角拍攝造成模板圖像與實(shí)時(shí)圖像之間的空間變換關(guān)系復(fù)雜,特殊的拍攝場(chǎng)景與方式給航空?qǐng)D像的模板匹配方法帶來(lái)了許多待解決的難點(diǎn),總結(jié)主要有以下幾點(diǎn):(1)多視角問(wèn)題。多視角造成制備的目標(biāo)模板圖像與實(shí)時(shí)圖像間的視角差異大、種類多,圖像之間的空間變換關(guān)系復(fù)雜,基于灰度匹配的方法無(wú)法解決多視角問(wèn)題。(2)小目標(biāo)弱特征問(wèn)題。小目標(biāo)本身模板圖像小,能夠提取的特征較少,采用局部特征點(diǎn)的匹配方法容易失敗。(3)航空平臺(tái)由于載荷有限,計(jì)算資源有限,航空?qǐng)D像通常數(shù)據(jù)量較大,對(duì)算法的高效性有特殊的要求。本文針對(duì)上述問(wèn)題,結(jié)合航空?qǐng)D像的特點(diǎn),提出一種多視角自適應(yīng)的模板匹配方法。通過(guò)分解多視角下圖像之間的空間變換關(guān)系,構(gòu)建空間變換矩陣的搜索空間,然后在整個(gè)搜索空間中通過(guò)優(yōu)化搜索的方法尋找到全局最優(yōu)的空間變換關(guān)系。考慮到小圖像弱特征的問(wèn)題,不采用難以提取的局部點(diǎn)特征,而將優(yōu)化搜索的目標(biāo)函數(shù)定義為模板圖像與實(shí)時(shí)圖像歸一化灰度的函數(shù),從而充分利用所有的圖像信息。2模型匹配模型2.1模型匹配問(wèn)題的建模假設(shè)模板圖像為若模板圖像在實(shí)時(shí)圖像中能找到匹配區(qū)域,則模板圖像I模板圖像I定義模板圖像I如果p2.2單元網(wǎng)格線劃分解決優(yōu)化問(wèn)題(4)必須定義優(yōu)化搜索的矩陣空間。矩陣空間由所有可能的變換矩陣組成,將變換矩陣分解成如下三個(gè)部分:式中:等式右邊第一項(xiàng)是仿射變換,包含了平移、旋轉(zhuǎn)等剛體變換和縮放等相似變換;第二項(xiàng)和第三項(xiàng)是純透視變換,分別在x方向和y方向透視投影。將其中仿射變換進(jìn)行QR分解,得到旋轉(zhuǎn)、平移和縮放三種變換為其中平移變換包含x方向和y方向上的平移,共兩個(gè)自由度,旋轉(zhuǎn)變換R縮放變換S包含x方向上的縮放和y方向上的縮放,共兩個(gè)自由度加上x(chóng)和y方向上的透視變換共2個(gè)自由度,變換矩陣H具有8個(gè)自由度,因此,矩陣空間Φ有8個(gè)維度,即Φ∈R通過(guò)計(jì)算發(fā)現(xiàn),變換矩陣Δ如圖3所示,若定義模板圖像I式中:‖·‖如果將矩陣空間Φ離散化,即將每一個(gè)維度按一定的間隔進(jìn)行網(wǎng)格劃分,共8個(gè)維度的劃分組成一個(gè)離散的網(wǎng)格,若網(wǎng)格劃分的精度為δ(0<δ<1),記為N按照表1劃分矩陣空間Φ,每一個(gè)網(wǎng)格線的交點(diǎn)即為一個(gè)矩陣變換,所有的矩陣變換H如圖4所示,如果網(wǎng)格的劃分間隔為δ,根據(jù)文獻(xiàn)[13]可以證明,對(duì)于Φ中的任意一個(gè)變換H∈Φ,N式中:Ο(·)表示等式左邊的漸近上界與括號(hào)中的表達(dá)式存在常數(shù)倍關(guān)系。因此,給定一個(gè)誤差精度δ>0,在矩陣空間N于是優(yōu)化問(wèn)題(4)可以在離散空間求的近似解,即3時(shí)間復(fù)雜度在網(wǎng)格N輸入:歸一化的灰度圖像I輸出:ΔStep1在圖像IStep2計(jì)算并返回Δ顯然,算法1的時(shí)間復(fù)雜度為Ο(1/δ輸入:歸一化的灰度圖像I輸出:變換矩陣HStep1創(chuàng)建網(wǎng)格NStep2若i≤N,對(duì)HStep3若ΔStep4i=i+1,返回Step2,直至循環(huán)結(jié)束。Step5返回H4快速匹配檢測(cè)利用算法2進(jìn)行最優(yōu)變換矩陣的求解,其計(jì)算的時(shí)間復(fù)雜度為N=Θ((1/δ分支界限法的思想是先用低精度的網(wǎng)格去劃分空間,快速找到最優(yōu)解的區(qū)域界限,然后在最優(yōu)解區(qū)域內(nèi)再進(jìn)行高精度網(wǎng)格劃分,進(jìn)一步找到最優(yōu)解的更精確界限,重復(fù)上述步驟將最優(yōu)解界限不斷縮小,直至逼近至最優(yōu)解。分支界限法要避免的是陷于局部最優(yōu),如果在低精度網(wǎng)格中找到的最優(yōu)解界限中不包含全局最優(yōu)解,由于后面的處理分支均是在當(dāng)前最優(yōu)解界限中尋找更逼近的界限,所以后面找到的最優(yōu)解一定不是全局最優(yōu)。為了直觀地描述這個(gè)問(wèn)題,如圖5所示,我們?cè)谝痪S空間進(jìn)行網(wǎng)格劃分查找最優(yōu)界限,其中橫軸矩陣空間Φ,間隔相等的灰色豎線是以精度δ對(duì)空間Φ進(jìn)行劃分的網(wǎng)格N由于SAD隨著H的變化是平滑的,根據(jù)式(13)有Δ多目標(biāo)匹配檢測(cè)問(wèn)題中,一個(gè)模板可能與實(shí)時(shí)圖像中多個(gè)區(qū)域匹配,故應(yīng)該返回多個(gè)變換矩陣H傳統(tǒng)模板匹配方法分為兩種,基于灰度的模板匹配方法只能解決平移變換,快速傅里葉方法能解決一定程度的旋轉(zhuǎn)變換;基于特征的模板匹配方法是通過(guò)特征匹配后尋找兩幅圖像之間的同名控制點(diǎn),然后直接求得變換矩陣的閉式解。但是,當(dāng)模板圖像中有效特征較少,如弱紋理圖像、實(shí)時(shí)圖像中干擾特征較多、圖像之間視角差異較大等情況,特征描述子的旋轉(zhuǎn)、縮放、仿射不變性能力有限,特征匹配的成功率通常非常低,可能無(wú)法得到閉式解或者閉式解的誤差較大。本文從優(yōu)化搜索的思路出發(fā),分析3×3的圖像變換矩陣,發(fā)現(xiàn)原始變換空間擁有8個(gè)自由度,每個(gè)自由度的取值都是連續(xù)的,即其取值集合有無(wú)窮維,無(wú)法通過(guò)優(yōu)化搜索的方法得到最優(yōu)的變換矩陣,那么考慮在一定的精度下降連續(xù)的變換空間進(jìn)行離散化數(shù)學(xué)建模,進(jìn)而在離散化的變換空間完成最優(yōu)矩陣的搜索。5實(shí)驗(yàn)和結(jié)論5.1匹配的投影誤差測(cè)試為了測(cè)試本文方法的效果,利用VOC2010dataset為了測(cè)試算法對(duì)投影變換的魯棒性,將模板圖像進(jìn)行90%、70%、50%、30%、10%的5種比例的縮放,然后進(jìn)行測(cè)試。測(cè)試中定義匹配的投影誤差為式中:C為了測(cè)試算法的抗噪聲性能,對(duì)250個(gè)樣本中的每一個(gè)樣本按表3所示三種方式進(jìn)行退化處理,生成更多的測(cè)試樣本。在上述測(cè)試集上將本文模板匹配算法與當(dāng)前最穩(wěn)定的SIFT特征匹配算法如圖7所示,橫坐標(biāo)表示圖像經(jīng)過(guò)6種不同級(jí)別的退化處理,縱坐標(biāo)表示匹配成功的概率(總共220個(gè)測(cè)試樣本)。5.2匹配檢測(cè)結(jié)果經(jīng)典的模板匹配算法如SAD、MAD、均方誤差、SSD、NCC、信息熵等基于灰度的匹配算法只能解決模板與實(shí)時(shí)圖像之間的平移關(guān)系,在頻域中處理可以解決一定程度的旋轉(zhuǎn)變換,但無(wú)法解決仿射變換、投影變換、由于測(cè)試圖像對(duì)之間存在仿射投影變換,因此這里無(wú)法參與測(cè)試比較。基于特征的匹配算法有SIFT如圖8所示,分別使用了實(shí)際采集的航空?qǐng)D像和標(biāo)準(zhǔn)庫(kù)中的圖像進(jìn)行測(cè)試,每一行是一個(gè)測(cè)試樣例,每行的第一列是模板圖像,第二列和第三列分別是本文的匹配檢測(cè)結(jié)果和SIFT匹配檢測(cè)結(jié)果。其中第一行為機(jī)場(chǎng)中飛機(jī)目標(biāo)檢測(cè)樣例,模板圖像的分辨率較低;第二行為訓(xùn)練場(chǎng)中車輛目標(biāo)檢測(cè)樣例,目標(biāo)模板相對(duì)場(chǎng)景圖像的旋轉(zhuǎn)角度較大;第三行是標(biāo)準(zhǔn)庫(kù)中的圖像匹配樣例,模板圖像相對(duì)場(chǎng)景圖像的仿射變換較大;第四行和第五行是港口艦船檢測(cè)樣例,模板圖像有一定的旋轉(zhuǎn)且分辨率較低。其中第一行和第二行均是單模板多目標(biāo)匹配檢測(cè)問(wèn)題。分別使用本文方法和SIFT匹配方法測(cè)試上述樣例,其中本文算法參數(shù)設(shè)置為縮放尺度范圍s=10,平移范圍c為實(shí)時(shí)圖像的尺寸,網(wǎng)絡(luò)精度為0.01,閾值為0.1。SIFT算法采用公開(kāi)庫(kù)VLFEAT本文算法與SIFT、ORB算法的運(yùn)行時(shí)間比較如表4所示,其中“NaN”表示匹配失敗。由實(shí)驗(yàn)結(jié)果可見(jiàn),SIFT算法匹配時(shí)間較長(zhǎng),ORB算法穩(wěn)定性能較差,本文算法采用暴力搜索算法遍歷整個(gè)變換空間,其時(shí)間消耗比傳統(tǒng)的SIFT算法還大長(zhǎng),經(jīng)過(guò)分支界限法加速后,速度可以顯著提高。這是因?yàn)榉种Ы缦薹ㄊ紫仍诖至６鹊木W(wǎng)格劃分下找到最優(yōu)解的可行區(qū)域(分支),迅速排除掉其他分支,從而大大減少無(wú)效計(jì)算,然后在找到的可行分支再進(jìn)行細(xì)粒度網(wǎng)格劃分,進(jìn)而找到精度更高的最優(yōu)解的可行分支,這樣通過(guò)不斷縮小最優(yōu)解的可行范圍避免無(wú)效運(yùn)算,在滿足精度要求下可以接受當(dāng)前的最優(yōu)可行解。6大差異視角、低分辨率模板匹配中的應(yīng)用前景分析本文研究了一種基于多視角變換空間優(yōu)化搜索的模板匹配方法,解決了航空?qǐng)D像拍攝視角多變、分辨率差異大等情況下模板目標(biāo)檢測(cè)的問(wèn)題。實(shí)驗(yàn)證明,所提方法對(duì)圖像模糊、高斯噪聲和有損壓縮等圖像退化具有較好的適應(yīng)能力,在大差異視角和低分辨率模板匹配中具有更好的穩(wěn)定性,并且具有單模板多目標(biāo)檢測(cè)的能力,無(wú)需大量目標(biāo)圖像訓(xùn)練學(xué)習(xí)。由于所提方法對(duì)模板與實(shí)際圖像的姿態(tài)差異適應(yīng)性強(qiáng)