靳 峰,馮大政
(1.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071;2.西安電子科技大學(xué)雷達(dá)信號(hào)處理國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)
一種快速準(zhǔn)確的圖像配準(zhǔn)算法
靳 峰1,2,馮大政2
(1.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071;2.西安電子科技大學(xué)雷達(dá)信號(hào)處理國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)
通過(guò)對(duì)圖像配準(zhǔn)目標(biāo)函數(shù)的分析,提出了一種結(jié)合相似性和空間序列特征的配準(zhǔn)算法.圖像配準(zhǔn)的目標(biāo)函數(shù)包含兩個(gè)最優(yōu)解,一個(gè)是最大數(shù)量的有效特征點(diǎn),一個(gè)是最高精度的圖像變換矩陣,這兩個(gè)部分可以使用不同的特征點(diǎn)匹配矩陣來(lái)求解.其中,使用基于相似性的中心對(duì)稱局部二值模式描述子獲得變換矩陣,使用基于空間序列特征的統(tǒng)計(jì)偏轉(zhuǎn)角度序列描述子獲取有效特征點(diǎn).后者是一種融合了局部結(jié)構(gòu)特征和全局統(tǒng)計(jì)特性的描述子,具有結(jié)構(gòu)簡(jiǎn)單、描述準(zhǔn)確的優(yōu)點(diǎn).實(shí)驗(yàn)結(jié)果表明,將兩種描述方法相結(jié)合進(jìn)行圖像配準(zhǔn),具有配準(zhǔn)精度高和運(yùn)算時(shí)間短的優(yōu)點(diǎn).
圖像配準(zhǔn);特征點(diǎn)匹配;描述子;中心對(duì)稱局部二值模式;空間序列特征
圖像配準(zhǔn)是影像處理和分析的一個(gè)最重要步驟.一直以來(lái),圖像配準(zhǔn)都是計(jì)算機(jī)視覺(jué)、模式識(shí)別、醫(yī)學(xué)圖像處理和遙感領(lǐng)域的熱點(diǎn).目前應(yīng)用最廣泛的是基于特征點(diǎn)的配準(zhǔn)方法[1-4].該方法通過(guò)特征檢測(cè)提取圖像中的特征點(diǎn),利用特征點(diǎn)的匹配關(guān)系建立圖像之間的配準(zhǔn)映射變換,實(shí)現(xiàn)圖像配準(zhǔn).
一些常見(jiàn)的配準(zhǔn)算法基于特征點(diǎn)的相似性進(jìn)行點(diǎn)的比對(duì)和匹配,進(jìn)而實(shí)現(xiàn)圖像的配準(zhǔn).該類(lèi)算法為了提高特征點(diǎn)的精確性和惟一性,往往使用多維向量來(lái)描述特征點(diǎn).例如,著名的尺度不變特征變換(Scale Invariant Feature Transform,SIFT)算法采用128維向量描述特征點(diǎn).一般來(lái)講,向量維數(shù)越高,特征點(diǎn)描述越精確,運(yùn)算的復(fù)雜程度就越高.
近年來(lái),一種基于特定點(diǎn)間的約束關(guān)系的配準(zhǔn)方法越來(lái)越受到研究者的重視.該類(lèi)方法在光學(xué)圖像或遙感圖像的配準(zhǔn)、圖像分類(lèi)、模式與目標(biāo)識(shí)別以及三維重構(gòu)等領(lǐng)域獲得了許多的應(yīng)用[5-8].文獻(xiàn)[5]提出了一種基于最近鄰圖形結(jié)構(gòu)的圖配準(zhǔn)算法,使用最近鄰約束策略構(gòu)造待配準(zhǔn)特征的局部鄰近結(jié)構(gòu)作為特征描述方法.文獻(xiàn)[6]提出了名為受限空間序列約束的特征點(diǎn)配準(zhǔn)算法,同樣使用最近鄰約束策略,選取待配準(zhǔn)點(diǎn)附近若干最近鄰點(diǎn)與待配準(zhǔn)點(diǎn)間的夾角序列作為特征點(diǎn)的描述方法.該類(lèi)方法最顯著的特點(diǎn)是利用空間上的約束關(guān)系來(lái)對(duì)特征點(diǎn)進(jìn)行描述和匹配,對(duì)圖像本身的信息依賴度低,也不需要對(duì)特征點(diǎn)進(jìn)行復(fù)雜的描述.但是,其缺點(diǎn)在于該類(lèi)算法對(duì)于特征點(diǎn)的描述是基于點(diǎn)與點(diǎn)之間的距離、角度或者序列,外點(diǎn)的存在會(huì)大大影響這種描述方法的精度,匹配算法往往就變成了剔除外點(diǎn)、求解最優(yōu)匹配矩陣的優(yōu)化算法.
經(jīng)過(guò)對(duì)以上各種特征點(diǎn)描述和匹配方法的對(duì)比與分析,筆者提出了一個(gè)結(jié)合兩種不同描述子的特征點(diǎn)匹配方法.采用兩種不同的特征點(diǎn)描述子完成圖像配準(zhǔn),一種是中心對(duì)稱局部二值模式描述子(Center Symmetric Local Binary Pattern,CS-LBP),一種是下面定義的統(tǒng)計(jì)偏轉(zhuǎn)角度序列描述子(Statistical Deflection Angle Order,SDAO).筆者提出的配準(zhǔn)算法和特征點(diǎn)描述子克服了傳統(tǒng)算法的缺點(diǎn),降低了復(fù)雜的特征點(diǎn)描述對(duì)匹配過(guò)程的影響,也能對(duì)外點(diǎn)進(jìn)行有效的剔除,是一種快速準(zhǔn)確的配準(zhǔn)算法.
無(wú)論是基于相似性的圖像配準(zhǔn)算法,還是基于空間關(guān)系的方法,其特征點(diǎn)的匹配矩陣都可記為
其中,Λij是一個(gè)M×N的二維矩陣,M和N分別為待配準(zhǔn)圖像中的特征點(diǎn)數(shù)量,fij表示兩幅圖像中的一對(duì)特征點(diǎn).
定義圖像配準(zhǔn)的一般目標(biāo)函數(shù)為
其中,m為Λ中的匹配點(diǎn)對(duì)數(shù)量,Γ為圖像變換矩陣.特征點(diǎn)的匹配目標(biāo)實(shí)際上就是獲得最大數(shù)量的匹配點(diǎn)對(duì)m和最高精度的圖像變換矩陣Γs.對(duì)于目標(biāo)函數(shù)的兩個(gè)最優(yōu)解m和Γs,可以使用兩種不同的特征點(diǎn)描述方式進(jìn)行求解.
新的目標(biāo)函數(shù)定義為
其中,E為基于相似性的特征點(diǎn)匹配矩陣,D為基于空間序列的特征點(diǎn)匹配矩陣.使用矩陣E進(jìn)行圖像變換矩陣估計(jì),求得Γs;使用矩陣D得到最大的有效特征點(diǎn)對(duì).
基于相似性的特征點(diǎn)描述往往結(jié)構(gòu)非常復(fù)雜,對(duì)于大量的點(diǎn)匹配操作效率不高;基于空間序列的特征點(diǎn)描述會(huì)受到外點(diǎn)的干擾,精度不夠.可將兩種方法相結(jié)合得到更好的配準(zhǔn)效果.在基于相似性的圖像配準(zhǔn)過(guò)程中,特征點(diǎn)描述的優(yōu)點(diǎn)之一就是獨(dú)立性,外點(diǎn)的存在對(duì)于特征點(diǎn)的描述沒(méi)有影響.因此,只需要少量特征點(diǎn)就可以進(jìn)行圖像變換矩陣估計(jì).在著名的隨機(jī)采樣一致性算法中,3對(duì)不共線特征點(diǎn)就可以得到圖像變換矩陣.在得到圖像變換矩陣之后,可以利用Γ進(jìn)行外點(diǎn)的刪除,進(jìn)而使用基于空間序列的匹配方法獲得更多的匹配點(diǎn)對(duì).其具體過(guò)程為:①利用若干不共線特征點(diǎn)的相似性描述估計(jì)圖像變換矩陣Γ.②利用Γ進(jìn)行外點(diǎn)刪除;利用特征點(diǎn)的空間序列描述計(jì)算D,匹配點(diǎn)對(duì)數(shù)量記為t.若t<Tf,Tf為指定常數(shù),返回①;若t≥Tf,利用D求解Γ,同時(shí)若t>m,m=t,返回②.④迭代運(yùn)行以上步驟,直到m值穩(wěn)定不變,或者迭代次數(shù)達(dá)到上限λ;使用最大的m計(jì)算Γs.
Tf是有效匹配點(diǎn)對(duì)數(shù)量的下限.當(dāng)Tf足夠小時(shí),該算法對(duì)于外點(diǎn)容錯(cuò)的程度相當(dāng)于目前魯棒性最好的RANSC算法;但是,當(dāng)Tf減小時(shí),求解變換參數(shù)矩陣的運(yùn)算量會(huì)大大增加,運(yùn)算時(shí)間與M/t的3次方成正比.在迭代過(guò)程中,步驟③總是使用當(dāng)前最優(yōu)的內(nèi)點(diǎn)集合求解Γ,但是步驟②使用全局特征點(diǎn)計(jì)算D來(lái)防止過(guò)收斂,最終得到的是最大內(nèi)點(diǎn)集合的最優(yōu)Γs.
2.1 基于相似性的特征點(diǎn)匹配
局部二值模式(Local Binary Pattern,LBP)是目前對(duì)二維圖像最有效的紋理分析特征之一[9].文獻(xiàn)[10]首次將其應(yīng)用到圖像特征點(diǎn)描述,提出了中心對(duì)稱局部二值模式(Center Symmetric LBP,CS-LBP)描述子.已有的實(shí)驗(yàn)結(jié)果表明,CS-LBP描述子在圖像匹配方面比SIFT描述子具有更好的性能,且在存儲(chǔ)空間需求和計(jì)算開(kāi)銷(xiāo)方面具有明顯的優(yōu)勢(shì).CS-LBP描述子的定義如下:
其中,ni和ni+P/2表示等間隔地分布在以(u,v)為圓心、R為半徑的圓上的P個(gè)臨近點(diǎn)中,關(guān)于中心點(diǎn)對(duì)稱的兩個(gè)像素點(diǎn)的灰度值;Tp為閾值.由式(4)可以看出,關(guān)于中心像素點(diǎn)對(duì)稱的兩個(gè)鄰域點(diǎn)灰度值的差值被表示為一個(gè)P/2比特的二進(jìn)制數(shù),會(huì)得到2P/2種不同的模式.統(tǒng)計(jì)每一種模式出現(xiàn)的次數(shù),就可以得到CS-LBP描述子.
CS-LBP描述子的缺陷在于其忽略了中心像素對(duì)局部紋理特征的影響,從而造成了局部紋理信息的丟失,即它在某些情況下無(wú)法得到足夠的有效特征點(diǎn).筆者提出了一種基于空間序列特征的描述子與其結(jié)合使用,再通過(guò)對(duì)匹配算法的改進(jìn)彌補(bǔ)了這個(gè)不足.
2.2 基于空間序列特征的特征點(diǎn)描述子
基于空間序列特征的描述方法的基本思想是:圖像中的特征點(diǎn)都可以視為一個(gè)圖中相互連接的節(jié)點(diǎn),每一個(gè)節(jié)點(diǎn)都可以被鄰近節(jié)點(diǎn)所構(gòu)成的局部區(qū)域所描述.筆者提出的一種基于局部結(jié)構(gòu)特征的特征點(diǎn)描述子,將點(diǎn)C描述為
點(diǎn)C周?chē)奶卣鼽c(diǎn)Lj,以θj,C為權(quán)值,按照dj,C的大小排成序列,構(gòu)成對(duì)點(diǎn)C的描述.其中M為圖像中特征點(diǎn)的個(gè)數(shù);dj,C為特征點(diǎn)Lj到點(diǎn)C的距離;o(·)為序列函數(shù),它表示特征點(diǎn)Lj到點(diǎn)C距離的位置關(guān)系,其取值為{1,2,…,K},K表示取點(diǎn)C周?chē)徑卣鼽c(diǎn)的個(gè)數(shù).例如,當(dāng)K=7時(shí),特征點(diǎn)Lj到點(diǎn)C的距離按照從小到大排列的序列為[3,6,5,2,4,7,1],o(d3,C)=1,o(d6,C)=2,以此類(lèi)推.θj,C為特征點(diǎn)Lj到點(diǎn)C的連接權(quán)值,定義為特征點(diǎn)Lj經(jīng)過(guò)全局參照點(diǎn)O到達(dá)點(diǎn)C所構(gòu)成的夾角.點(diǎn)O為特定的樣本空間的均值,稱θj,C為統(tǒng)計(jì)偏轉(zhuǎn)角度(Statistical Deflection Angle,SDA).統(tǒng)計(jì)偏轉(zhuǎn)角度按照o(dj,C)構(gòu)成的序列稱為統(tǒng)計(jì)偏轉(zhuǎn)角度序列(Statistical Deflection Angle Order,SDAO).
F(C)是一個(gè)空間序列描述子,它既包含點(diǎn)C周?chē)卣鼽c(diǎn)的局部結(jié)構(gòu),又包含特征點(diǎn)樣本空間的全局信息.與傳統(tǒng)的基于局部結(jié)構(gòu)特征的特征點(diǎn)描述方法相比,筆者定義的空間序列描述子對(duì)特征點(diǎn)的局部結(jié)構(gòu)特征進(jìn)行了更加嚴(yán)格的約束.由于引入了全局參照點(diǎn),避免了局部結(jié)構(gòu)相似引起的描述混亂.
2.3 全局參照點(diǎn)
基于空間序列的特征點(diǎn)描述方式容易受到外點(diǎn)的干擾,SDAO描述子引入了全局參照點(diǎn),該點(diǎn)的選取是否受外點(diǎn)影響對(duì)于SDAO描述子的精度尤為重要.筆者給出的算法可以有效地解決這一問(wèn)題.在上述的配準(zhǔn)過(guò)程中,步驟②進(jìn)行了外點(diǎn)刪除,稱此刻剩余的點(diǎn)為“粗內(nèi)點(diǎn)”.粗內(nèi)點(diǎn)是由基于相似性的特征點(diǎn)匹配得到的,有效地避免了外點(diǎn)的干擾.將粗內(nèi)點(diǎn)視為點(diǎn)樣本空間,取其均值作為全局參照點(diǎn)O的定位.
圖1顯示了在初始外點(diǎn)比例為43%的情況下,粗內(nèi)點(diǎn)在迭代過(guò)程中不斷向最優(yōu)內(nèi)點(diǎn)集合逼近而得到的匹配精度.圖中的橫坐標(biāo)為外點(diǎn)剔除操作的迭代次數(shù),縱坐標(biāo)為像素誤差.隨著外點(diǎn)的剔除,粗內(nèi)點(diǎn)的匹配精度逐漸提高,代表了全局參照點(diǎn)的精度提高.
圖1 全局參照點(diǎn)精度
3.1 有效性檢驗(yàn)
為了檢驗(yàn)特征點(diǎn)匹配的有效性,采用復(fù)現(xiàn)率作為衡量準(zhǔn)則.此處的復(fù)現(xiàn)率是指:若在兩幅圖像中分別有r1和r2個(gè)特征點(diǎn)在變換后的圖像中存在匹配點(diǎn),而在兩幅圖像中實(shí)際檢測(cè)到的對(duì)應(yīng)匹配點(diǎn)對(duì)的數(shù)目為r3,則復(fù)現(xiàn)率R1=2r3/(r1+r2).
將圖像處理中常用的“Lena”圖像分別進(jìn)行尺度和旋轉(zhuǎn)變化下的圖像配準(zhǔn),驗(yàn)證筆者提出的算法在圖像配準(zhǔn)一般應(yīng)用上的有效性.筆者提出的算法與常用的尺度不變特征轉(zhuǎn)換(Scale Invariant Feature Transform,SIFT)算法和尺度Harris算法在復(fù)現(xiàn)率上取得的結(jié)果如圖2所示.
圖2 尺度和旋轉(zhuǎn)變化下的復(fù)現(xiàn)率
圖2顯示了在圖像發(fā)生尺度和旋轉(zhuǎn)變化時(shí)各種算法的復(fù)現(xiàn)率對(duì)比.筆者提出的算法在圖像發(fā)生尺度變化和旋轉(zhuǎn)變化的配準(zhǔn)操作時(shí),能夠獲得超過(guò)SIFT算法和尺度Harris算法的復(fù)現(xiàn)率.這是因?yàn)?筆者提出的算法中使用的特征點(diǎn)描述方法受圖像信息的影響較小,序列描述子具有高度的尺度和旋轉(zhuǎn)不變性,能夠匹配更多的有效特征點(diǎn)對(duì).較高的復(fù)現(xiàn)率表明,筆者提出的算法在圖像特征點(diǎn)檢測(cè)和匹配上是有效的和準(zhǔn)確的.
3.2 對(duì)比結(jié)果
筆者使用圖像處理中常用的檢測(cè)圖像和實(shí)際拍攝圖像進(jìn)行各種情況下的圖像配準(zhǔn),驗(yàn)證筆者提出的算法的性能.檢測(cè)圖像如圖3所示,圖3(a)為測(cè)試圖像“Boat”,圖3(b)為3幅變換圖像;圖3(c)為測(cè)試圖像“Bark”,圖3(d)為3幅變換圖像;圖3(e)、(f)和(g)為3對(duì)實(shí)際拍攝的待配準(zhǔn)圖像.
為了進(jìn)一步對(duì)筆者提出的算法進(jìn)行檢驗(yàn),采用復(fù)現(xiàn)率、有效點(diǎn)對(duì)數(shù)量和運(yùn)行時(shí)間對(duì)算法進(jìn)行分析.實(shí)驗(yàn)的硬件環(huán)境為CPU 2.1 GHz,內(nèi)存為2 GB,操作系統(tǒng)為Win7,程序開(kāi)發(fā)平臺(tái)為Matlab2012.筆者提出的算法與SIFT算法和尺度Harris算法在上述3個(gè)指標(biāo)上的運(yùn)行結(jié)果如圖4所示.圖4中橫坐標(biāo)1到9分別表示圖3中的測(cè)試圖像對(duì),其中1到3為圖3(a)與3幅變換圖像的配準(zhǔn)結(jié)果,4到6為圖3(c)與3幅變換圖像的配準(zhǔn)結(jié)果,7到9為圖3(e)、(f)和(g)的配準(zhǔn)結(jié)果.
圖3 檢測(cè)圖像
圖4 算法性能對(duì)比
為了達(dá)到實(shí)驗(yàn)結(jié)果的公平性,對(duì)比的3種方法均使用高斯差分算子進(jìn)行特征點(diǎn)檢測(cè).因此,每組檢測(cè)圖像在3種方法下的特征點(diǎn)數(shù)量和位置都是一致的,差別只在于特征點(diǎn)的描述方式和匹配算法.在多數(shù)情況下,筆者提出的算法能夠在3種算法的對(duì)比中取得最優(yōu)的復(fù)現(xiàn)率,最大的有效點(diǎn)對(duì)數(shù)量和最短的運(yùn)行時(shí)間.
圖3(a)~(b)中的檢測(cè)圖像包含了尺度和旋轉(zhuǎn)變換,而且圖像內(nèi)容豐富,紋理復(fù)雜,該組圖像中檢測(cè)到的特征點(diǎn)數(shù)量最多,筆者提出的算法在運(yùn)行時(shí)間上的優(yōu)勢(shì)非常明顯.圖3(e)的檢測(cè)圖像中包含了尺度變換和圖像剪裁,該組圖像中的特征點(diǎn)間的空間位置關(guān)系存在很大差異,筆者提出的算法在運(yùn)算時(shí)間上變長(zhǎng)是因?yàn)樵黾恿怂惴ǖ牡螖?shù).圖3(f)的檢測(cè)圖像中存在大量相似的局部結(jié)構(gòu),這種情況是圖像配準(zhǔn)的難點(diǎn),筆者提出的算法仍然保持了較高的復(fù)現(xiàn)率,因?yàn)槲闹卸x的SDAO是一種結(jié)合了局部結(jié)構(gòu)和全局信息的特征點(diǎn)描述方式.
筆者提出了一種基于特征點(diǎn)描述和匹配的圖像配準(zhǔn)算法.實(shí)驗(yàn)結(jié)果表明:與傳統(tǒng)算法相比,筆者提出的算法具有較高的復(fù)現(xiàn)率和較短的運(yùn)算時(shí)間,是一個(gè)準(zhǔn)確、快速的圖像配準(zhǔn)算法.
[1]吳偉交,王敏,黃心漢,等.基于向量夾角的SIFT特征點(diǎn)匹配算法[J].模式識(shí)別與人工智能,2013,26(1):123-127. Wu Weijiao,Wang Min,Huang Xinhan,et al.SIFT Feature Matching Algorithm Based on Vector Angle[J].PatternRecognition and Artificial Intelligence,2013,26(1):123-127.
[2] 唐朝偉,肖健,邵艷清,等.一種改進(jìn)的SIFT描述子及其性能分析[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2012,37(1):11-16. Tang Chaowei,Xiao Jian,Shao Yanqing,et al.An Improved SIFT Descriptor and Its Performance Analysis[J]. Geomatics and Information Science of Wuhan University,2012,37(1):11-16.
[3]Zhang K,Li X,Zhang J.A Robust Point-matching Algorithm for Remote Sensing Image Registration[J].IEEE Geoscience and Remote Sensing Letters,2014,11(2):469-473.
[4]Wu Y,Ma W,Gong M,et al.A Novel Point-matching Algorithm Based on Fast Sample Consensus for Image Registration[J].IEEE Geoscience and Remote Sensing Letters,2014,1(99):1-5.
[5]Aguilar W,Frauel Y,Escolano F,et al.A Robust Graph Transformation Matching for Nonrigid Registration[J].Image and Vision Computing,2009,27(7):897-910.
[6]Liu Z,An J,Jing Y.A Simple And Robust Feature Point Matching Algorithm Based on Restricted Spatial Order Constraints for Aerial Image Registration[J].IEEE Transactions on Geoscience and Remote Sensing,2011,8(4):805-841.
[7]Wang J,Zhou Y,Bai X,et al.Shape Matching and Recognition Using Group-wised Points[J].Advances in Image and Video Technology,2012(7088):393-404.
[8]Gong M,Zhao S,Jiao L,et al.A Novel Coarse-to-fine Scheme for Automatic Image Registration Based on Sift and Mutual Information[J].IEEE Transactions on Geoscience and Remote Sensing,2014,52(7):4328-4338.
[9]Ojala T,Pietikainen M,Maenpaa T.Multiresolution Grayscale and Rotation Invariant Texture Classification with Local Binary Patterns[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(7):971-987.
[10]Heikkila M,Pietikainen M,Schmid C.Description of Interest Regions with Local Binary Patterns[J].Pattern Recognition,2009,42(3):425-436.
(編輯:郭 華)
Fast and precise image registration algorithm
JIN Feng1,2,FENG Dazheng2
(1.School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China; 2.National Key Lab.of Radar Signal Processing,Xidian Univ.,Xi’an 710071,China)
An image registration algorithm is proposed through the analysis of the objective function. There are two optimal solutions to the function:the biggest number of efficient point pairs and the image transformation matrix with the highest accuracy,which can be solved by two different point matching matrices.The algorithm gets the transformation matrix by the points described in the center symmetric local binary pattern(CS-LBP),and obtains the efficient points by the statistical deflection angle order (SDAO).The SDAO is a sample and accuracy descriptor that integrates the local structure and global information of images.By combining with the advantages of the two description methods,the algorithm achieves a high alignment accuracy and a small computational volume.
image registration;point matching;descriptor;center symmetric local binary pattern;spatial order property
TP391.4
A
1001-2400(2015)06-0088-06
10.3969/j.issn.1001-2400.2015.06.016
2014-06-20
時(shí)間:2015-03-13
國(guó)家自然科學(xué)基金資助項(xiàng)目(61271293)
靳 峰(1982-),男,西安電子科技大學(xué)博士研究生,E-mail:xdjinfeng@163.com.
http://www.cnki.net/kcms/detail/61.1076.TN.20150313.1719.016.html