靳峰,馮大政
(1.西安電子科技大學計算機學院,710071,西安; 2.西安電子科技大學雷達信號處理國防科技重點實驗室,710071,西安)
利用空間序列描述子的快速準確的圖像配準算法
靳峰1,2,馮大政2
(1.西安電子科技大學計算機學院,710071,西安; 2.西安電子科技大學雷達信號處理國防科技重點實驗室,710071,西安)
針對基于局部結(jié)構(gòu)特征的圖像配準算法對特征描述不夠精確、外點剔除過程運算復(fù)雜度高的問題,提出了一種利用空間序列描述子的快速準確的圖像配準算法。算法定義了一種基于空間序列的特征點描述子,通過定義特征點間的連接權(quán)值和排列順序構(gòu)成點的特征來描述,融合了圖像局部結(jié)構(gòu)和全局信息;通過對隨機采樣一致性檢驗的改進,采用投票策略和隨機采樣一致性檢測的方法,解決外點剔除問題;利用空間序列描述子進行圖像配準,通過配準和外點剔除交替迭代進一步提高配準精度。定量分析與實驗結(jié)果表明:與傳統(tǒng)的特征點匹配算法相比,該算法具有結(jié)構(gòu)簡單、易于實現(xiàn)的特點,具有配準精度高和計算時間少的優(yōu)點,具有較高的復(fù)現(xiàn)率和準確率。
圖像配準;圖像特征點;空間序列描述子;隨機采樣一致性
圖像配準是指對取自不同時間、不同傳感器或不同視角的同一景物的兩幅圖像或多幅圖像進行配準、疊加的過程[1],它是影像處理和分析的一個最重要的步驟。一直以來,圖像配準都是計算機視覺、模式識別、醫(yī)學圖像處理和遙感領(lǐng)域的熱點。圖像配準技術(shù)可廣泛應(yīng)用于多源遙感數(shù)據(jù)的融合分析、復(fù)雜場景下的小目標運動跟蹤檢測、圖像拼接、地景與地圖的匹配、基于模板匹配的目標識別和高程重建等方面。
在圖像配準方面,已經(jīng)展開了大量的研究工作,圖像配準的方法主要包括基于灰度配準的方法和基于特征配準的方法[1],目前應(yīng)用較多的是后者?;谔卣髋錅实姆椒ㄊ紫葟脑紙D像中提取特征,通過特征的匹配關(guān)系建立圖像之間的配準映射變換,實現(xiàn)配準圖像。特別是在基于點特征的配準方法[2-6]中,特征點具有平移、旋轉(zhuǎn)和尺度不變性,并且彼此具有較高的區(qū)分度,能夠準確地反映圖像特征,但是,特征點的描述方法比較復(fù)雜,在如何提高配準運算的效率上,許多學者提出了改進方法[7-8]。
近年來,一種基于空間幾何關(guān)系的配準方法越來越受到研究者的重視。該類方法在光學圖像或遙感圖像的配準、圖像分類、模式與目標識別以及三維重構(gòu)等領(lǐng)域獲得了許多的應(yīng)用[9-13]。文獻[10]提出了一種基于最近鄰圖形結(jié)構(gòu)的圖像配準算法(Graph Transform Matching,GTM),該算法使用最近鄰約束策略構(gòu)造待配準特征的局部鄰近結(jié)構(gòu)作為特征描述方法。文獻[11]提出了名為受限空間序列約束(Restricted Spatial Order Constraints,RSOC)的特征點配準算法,該算法同樣使用最近鄰約束策略,選取待配準點附近若干最近鄰點與待配準點間的夾角序列作為特征點的描述方法。文獻[12]提出了基于特征點間的相對距離和角度的特征點配準算法。
基于空間幾何關(guān)系的配準算法對特征的描述過于簡單,沒有有效的外點剔除方法,因此其配準過程往往轉(zhuǎn)變?yōu)橥ㄟ^迭代求目標函數(shù)的最優(yōu)解的問題,目標函數(shù)一般為配準矩陣或者圖像變換矩陣的表達式。
為了解決這一問題,本文受排列順序編碼[14]啟發(fā),定義了一種結(jié)構(gòu)簡單的特征描述子,該描述子與傳統(tǒng)的特征點描述子相比,有效融合了圖像局部信息和全局信息;對于外點剔除問題,采用投票策略和隨機采樣一致性檢測的方法。與傳統(tǒng)算法相比,本文算法使用空間上的幾何關(guān)系特征對特征點進行描述,結(jié)構(gòu)簡單,易于實現(xiàn);對特征點的描述綜合了圖像局部結(jié)構(gòu)和全局信息,在圖像中存在相似局部區(qū)域的情況下能取得更好的配準效果;將改進的隨機采樣一致性檢測引入配準過程,在刪除外點的同時保證了最大內(nèi)點集合,具有配準精度高和計算時間少的優(yōu)點。
1.1 描述子定義
排列順序編碼(Rank Order Encoding)是一種基于序列的權(quán)值編碼方法。該編碼模型最早應(yīng)用于脈沖發(fā)放神經(jīng)網(wǎng)絡(luò)[15],其函數(shù)[14]定義為
(1)
式中:Activation(i,t)為i在某時刻t獲得的M個連接j的輸入之和;wi,j是j到i的連接權(quán)值;δ是一個取值在0到1之間的調(diào)制因子;order()表示wi,j在輸入序列中的位置,取值為{1,2,…,M}之一。i獲得的輸入由連接權(quán)值wi,j的大小和wi,j在輸入序列中的排列位置共同決定,這種表示方式稱為排列順序編碼。
如果定義了特征點間的連接權(quán)值和空間序列,排列順序編碼可以很方便地應(yīng)用于空間上的權(quán)值序列描述。圖1顯示了特征點C和其周圍的特征點Lj組成的結(jié)構(gòu)。
圖1 特征點連接
按照排列順序編碼的描述方式,Lj對特征點C的連接權(quán)值可描述為
(2)
式中:M為特征點的個數(shù);θj,c是點Lj到點C的連接權(quán)值;dj,c是點Lj到點C的距離;order()為點Lj在其到點C的空間序列中的位置。圖1中,點Lj到點C的距離按照從小到大排列的序列為[3,6,5,2,4,7,1],因此order(3)=1,order(6)=2,以此類推??梢哉J為,特征點C周圍的點Lj以θj,c為連接權(quán)值,按照dj,c的大小排成序列,構(gòu)成了對點C的描述。
根據(jù)式(2)的描述,越是處在序列靠后位置的點Lj的連接權(quán)值,對點C的作用就越小?;谶@一設(shè)定,可以使用最近鄰原則在特征點的周圍選取有限的局部最近鄰點,這些最近鄰點構(gòu)成對特征點的描述。對于特征點C而言,定義空間序列描述子為
(3)
F(C)的含義是,選取特征點C周圍的K個最近鄰點,將這些最近鄰點與點C的連接權(quán)值按照一定的排列順序所組成的向量描述。這里的排列順序使用的是空間上的距離dj,C的序列位置。
1.2 連接權(quán)值定義
圖2 連接權(quán)值的幾何意義
為了使全局參照點O能夠體現(xiàn)全局信息特征,本文使用特征點的樣本空間均值來進行點O的定義,因此將θj,C稱為統(tǒng)計偏轉(zhuǎn)角度。全局參照點O是一個統(tǒng)計信息,穩(wěn)定的特征點樣本空間是選取點O的關(guān)鍵。本文使用式(4)來進行樣本空間計算
(4)
式中:M1和M2分別為主輔圖像待匹配點的個數(shù);H和H′分別為主輔圖像中所有待匹配點間的距離構(gòu)成的矩陣。若V(u1,v1)是矩陣V在第u行和第v列的最大值,V(u2,v2)是矩陣V在第u行和第v列的次大值,并且V(u1,v1)-V(u2,v2)≥T1,T1為指定常數(shù),那么可以認為主圖像中第u個點與輔圖像中第v個點是一對匹配點。
本文將式(4)獲得的匹配點稱為內(nèi)聚點。兩幅圖像中的內(nèi)聚點具有數(shù)量相近、相對位置一致的特點。使用內(nèi)聚點作為特征點樣本空間,其均值點O的意義是主輔圖像特征點構(gòu)成的兩個圖中較大的相似子圖(最優(yōu)情況下為最大相似子圖)的中心。因此,認為點O在一定程度上包含了圖像特征點的全局信息,將其作為全局參照點引入特征點描述能夠有效區(qū)分局部結(jié)構(gòu)相近的特征點。如圖3所示,由于統(tǒng)計偏轉(zhuǎn)角度的定義中使用了全局參照點D,可以直觀地看到局部結(jié)構(gòu)近似的特征點C1和C2的描述是完全不同的。
圖3 特征點描述
待配準圖像的特征點匹配矩陣為
Γ={φgm}(g,m)∈ψ
(5)
迭代計算特征點匹配矩陣Γ和圖像變換矩陣Λ,直到獲得滿足精度條件的圖像變換矩陣,具體步驟如下。
步驟1計算特征點匹配矩陣Γ,得到特征點對集合Π1,Π1大小為s1;使用Π1更新全局參照點位置。
步驟2使用隨機采樣一致性檢驗計算內(nèi)點的點對集合Π2,Π2的大小為s2。
步驟3比較s1、s2和sm(初值為T3),若s1最大,將沒有包含在Π1中的點作為外點刪除,sm=s1,返回步驟1;若s2最大,將沒有包含在Π2中的點作為外點刪除,sm=s2,返回步驟1;若sm最大,返回步驟2。
步驟4迭代運行以上步驟,直到sm的值穩(wěn)定不變,或者迭代次數(shù)達到上限λ。認為此時的Π2是最大內(nèi)點集合Πm,使用Πm得到最終的Γ和Λ。
上述過程是對于隨機采樣一致性算法的改進,一方面刪除了外點,另一方面保留了最大內(nèi)點集合。步驟2使用了隨機采樣一致性檢驗,利用隨機點對求出圖像變換矩陣,然后根據(jù)容錯誤差進行外點刪除。本文算法在每一次的外點剔除之后,重新計算特征點匹配矩陣,采用更接近最優(yōu)解的樣本空間進行圖像變換矩陣估計,提高了隨機采樣的效率。這是因為隨機采樣一致性檢驗的時間復(fù)雜度取決于概率(sm/M)η,概率越大隨機采樣一致性檢驗的效率越高,這里η=3。本文的檢驗過程時間復(fù)雜度取決于(sm/s1)η,在迭代的過程中趨向于1。同時,為了防止過收斂,每一次計算得出的圖像變換矩陣對全體特征點進行誤差檢測,保證了獲得最大有效點對集合。最后,sm的初值T3為式(4)中定義的內(nèi)聚點的數(shù)量,若迭代結(jié)束時sm=T3,內(nèi)聚點集合就是最優(yōu)的內(nèi)點集合。即使在最差的情況下,全局參照點的位置在每一次的迭代中也趨向于內(nèi)點中心。
與傳統(tǒng)的基于空間幾何關(guān)系的特征點匹配算法相比,本文定義的描述子具有更高的匹配準確率,尤其是待配準圖像中存在大量重復(fù)的局部區(qū)域時。
圖4a為不同角度下拍攝的光學自然圖像,圖4b和圖4c為采用LOG算子進行特征點檢測之后,基于空間幾何關(guān)系的典型算法——空間序列約束算法(SOC)和本文算法得到的特征點匹配結(jié)果。前者在處理圖像中重復(fù)出現(xiàn)的規(guī)則網(wǎng)格結(jié)構(gòu)時出現(xiàn)了錯配的現(xiàn)象,該類問題必須依靠引入全局信息的描述算法來解決。
(a)輸入圖像
(b)SOC算法
(c)本文算法
本文算法在圖像外點較多的情況下,全局參照點的初值選取將受到外點的干擾。以圖5為例,圖5b變換圖像包含了對圖5a圖像尺度上的變化和剪裁,兩幅圖像的特征點數(shù)量分別為417、301,特征點匹配后剩余外點的比例為43%。在該種情形下,全局參照點的精度如圖6所示。
(a)配準圖像 (b)變換圖像
(a)初值精度 (b)迭代過程
由內(nèi)聚點得到的配準精度反映了全局參照點的精度。通過調(diào)節(jié)參數(shù)T1的值,內(nèi)聚點的配準精度可以達到4個像素以內(nèi)。以此作為全局參照點的初值,圖6b反映了隨著外點的剔除,內(nèi)聚點的匹配精度進一步提高,最終和內(nèi)點的匹配精度趨于一致。
為了進一步檢驗本文算法的有效性,采用特征點的復(fù)現(xiàn)率和準確率進行定量分析。此處的復(fù)現(xiàn)率是指如果在兩幅圖像中分別有r1和r2個特征點在變換后的圖像中存在匹配點,而在兩幅圖像中實際檢測到的對應(yīng)匹配點對的數(shù)目為r3,則復(fù)現(xiàn)率為R1=2r3/(r1+r2),準確率為R2=1-r4/r3,其中r4為配準錯誤的點對數(shù)目。匹配點對的復(fù)現(xiàn)率和準確率越高,說明特征檢測的性能越穩(wěn)定,配準的準確率越高。
本文使用實際拍攝的自然光學圖像和圖像處理中常用的測試圖像進行配準算法的驗證。圖4a、圖5a是實際拍攝的自然光學圖像,圖4a包含了拍攝視角的變化,圖5反映了尺度變換。圖7a~圖7f是圖像處理中常用的測試圖像,涵蓋了視角變換、尺度變換、大角度旋轉(zhuǎn)和圖像的仿射變換。
圖7 測試圖像
圖8 算法效果對比
為了保證配準的準確性,圖像特征點檢測使用經(jīng)典的DOG算子,實驗平臺和環(huán)境為CPU2.1 GHz,內(nèi)存2 GB,win7系統(tǒng),matlab2012。將本文算法與目前常見的基于空間幾何關(guān)系的GTM算法[10]和RSOC算法[11]進行對比,在復(fù)現(xiàn)率、查準率和運行時間上的效果如圖8所示。圖8a~圖8c中橫坐標表示圖4、圖5和圖7中的測試圖像對,其中1為圖4,2為圖5,3~5為圖7b中3幅變換圖像與圖7a的配準結(jié)果,6~8為圖7d中變換圖像與圖7c的配準結(jié)果,9、10為圖7f中變換圖像與圖7e的配準結(jié)果。
圖8a和圖8b描述的分別是各算法配準結(jié)果的復(fù)現(xiàn)率和準確率,圖8c描述的是各算法的運算時間。DOG算子檢測到的特征點普遍存在復(fù)現(xiàn)率不高的問題,本文算法由于融合了魯棒性較高的隨機采樣一致性檢驗,因此在3種算法中取得了最高的復(fù)現(xiàn)率。尤其是第5對檢測圖像,圖像信息復(fù)雜,檢測特征點數(shù)量多,圖像變換在角度和尺度上都比較明顯,本文算法仍然保持了40%以上的復(fù)現(xiàn)率。在準確率上,第1對檢測圖像由于含有較多重復(fù)出現(xiàn)的局部相似結(jié)構(gòu),容易出現(xiàn)誤配的情況,本文使用的描述子有效避免了這種情況,取得了最高的查準率。同時,在該種情況下,本文算法在運算時間上的優(yōu)勢比較明顯。在運行時間上,本文算法存在這樣的情況,在復(fù)現(xiàn)率較高的情況下,本文算法運行時間少于其他兩種算法;在復(fù)現(xiàn)率較低的情況下,本文算法的運行時間略有上升,例如圖5中兩幅圖像的配準。這是因為在低復(fù)現(xiàn)率情況下,內(nèi)聚點的初始精度比較低,也即圖像配準步驟1中的特征點對集合Π1中含有匹配錯誤的點和匹配精度不高的點,因此Π1的大小s1遠大于實際的匹配點對數(shù)量sm,而本文算法的時間復(fù)雜度取決于(sm/s1)η,因此運算時間上升。
參照排列順序編碼方法提出了一種基于空間上的幾何關(guān)系特征的特征點描述子,給出了改進的隨機采樣一致性檢測的外點剔除方法。本文算法提出的空間序列描述子融合了特征點的局部結(jié)構(gòu)和全局信息,以相對簡單的結(jié)構(gòu)定義實現(xiàn)了特征點描述。結(jié)合外點刪除策略,實現(xiàn)了快速、準確的圖像配準。
[1] ZITOVA B,FLUSSER J.Image registration methods: a survey [J].Image and Vision Computing,2003,21(11): 977-1000.
[2] 張艷,張志成.混合Forstner算法和SIFT灰度圖像特征點提取 [J].科學通報,2012,28(10): 94-95.
ZHANG Yan,ZHANG Zhicheng.Hybrid Forstner algorithm and SIFT gray image feature extraction [J].Bulletin of Science and Technology,2012,28(10): 94-95.
[3] 羅亞威,魏本昌,管濤,等.面向移動設(shè)備的快速特征點匹配方法研究 [J].計算機應(yīng)用研究,2013,30(2): 591-594.
LUO Yawei,WEI Benchang,GUAN Tao,et al.Research on fast feature match method for mobile devices [J].Application Research of Computers,2013,30(2): 591-594.
[4] 徐正光,陳宸.魯棒且快速的特征點匹配算法 [J].計算機科學,2013,40(2): 294-296.
XU Zhengguang,CHEN Chen.Robust and fast feature points matching [J].Computer Science,2013,40(2): 294-296.
[5] 吳偉交,王敏,黃心漢,等.基于向量夾角的SIFT特征點匹配算法 [J].模式識別與人工智能,2013,26(1): 123-127.
WU Weijiao,WANG Min,HUANG Xinhan,et al.SIFT feature matching algorithm based on vector angle [J].Pattern Recognition and Artificial Intelligence,2013,26(1): 123-127.
[6] 李俊山,朱英宏,朱藝娟,等.紅外與可見光圖像自相似性特征的描述與匹配 [J].激光與紅外,2013,43(3): 339-343.
LI Junshan,ZHU Yinghong,ZHU Yijuan,et al.Description and matching of self-similarities for IR and visual images [J].Laser and Infrared,2013,43(3): 339-343.
[7] 唐朝偉,肖健,邵艷清,等.一種改進的SIFT描述子及其性能分析 [J].武漢大學學報: 信息科學版,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.
[8] 陳偉,劉麗.結(jié)合角點特征與SIFT特征的加速圖像匹配 [J].計算機技術(shù)與發(fā)展,2012,22(1): 104-108.
CHEN Wei,LIU Li.Combining corner and SIFT features to accelerate image matching [J].Computer Technology and Development,2012,22(1): 104-108.
[9] QIAN Wei,FU Zhizhong,LIU Lingqiao,et al.Voting-strategy-based approach to image registration [J].Opto-Electronic Engineering,2008,35(10): 86-91.
[10]AGUILAR W,FRAUEL Y,ESCOLANO F,et al.A robust graph transformation matching for non-rigid registration [J].Image and Vision Computing,2009,27(7): 897-910.
[11]LIU Zhaoxia,AN Jubai,JING Yu.A simple robust feature point matching algorithm based on restricted spatial order constraints for aerial image registration [J].IEEE Transactions on Geosciences and Remote Sensing,2011,8(4): 805-841.
[12]XIONG Zhen,ZHANG Yun.A novel interest-point-matching algorithm for high-resolution satellite images [J].IEEE Transactions on Geosciences and Remote Sensing,2009,47(12): 4189-4200.
[13]ALAJLAN N,RUBE I E,KAMEL M S,et al.Shape retrieval using triangle-area representation and dynamic space warping [J].Pattern Recognition,2007,40(7): 1911-1920.
[14]DELORME A,PERRINET L,THORPE S J.Networks of integrate-and-fire neurons using rank order coding B: spike timing dependent plasticity and emergence of orientation selectivity [J].Neuroncomputing,2001,38(40): 539-545.
[15]VANRULLEN R,THORPE S J.Surfing a spike wave down the ventral stream [J].Vision Research,2002,42(23): 2593-2615.
[本刊相關(guān)文獻鏈接]
張琳彥,朱利.以多幅圖像非幾何約束線段匹配重建建筑物外立面三維線段模型.2014,48(4):15-19.[doi:10.7652/xjtuxb201404003]
楊雋楠,史忠科,舒甜.車輛行駛轉(zhuǎn)向角的圖像檢測方法.2013,47(6):73-78.[doi:10.7652/xjtuxb201306013]
華莉琴,許維,王拓,等.采用改進的尺度不變特征轉(zhuǎn)換及多視角模型對車型識別.2013,47(4):92-99.[doi:10.7652/xjtuxb201304016]
高燕華,劉玉歡,喻罡.多尺度非參數(shù)化水平集的超聲心動圖分割.2013,47(2):53-57.[doi:10.7652/xjtuxb201302009]
章為川,水鵬朗,朱磊.利用各向異性高斯方向?qū)?shù)相關(guān)矩陣的角點檢測方法.2012,46(11):91-97.[doi:10.7652/xjtuxb 201211018]
朱磊,水鵬朗,章為川,等.利用區(qū)域劃分的合成孔徑雷達圖像相干斑抑制算法.2012,46(10):83-88.[doi:10.7652/xjtuxb201210015]
馬元魁,張樹生,白曉亮.用球面混合曲率圖像比較三角網(wǎng)格模型的相似性.2012,46(5):97-101.[doi:10.7652/xjtuxb 201205017]
吳攀超,王宗義,林欣堂.采用局部差分模型描述的彩色圖像配準技術(shù).2011,45(10):30-37.[doi:10.7652/xjtuxb2011 10006]
徐勝軍,韓九強,趙亮,等.用于圖像分割的局部區(qū)域能量最小化算法.2011,45(8):7-12.[doi:10.7652/xjtuxb201108 002]
羅濤,牟軒沁.一種胸部X射線攝影圖像中結(jié)節(jié)檢測的多尺度匹配濾波器.2011,45(4):30-35.[doi:10.7652/xjtuxb 201104006]
趙海峰,姚麗莎,羅斌.改進的人工魚群算法和Powell法結(jié)合的醫(yī)學圖像配準.2011,45(4):46-52.[doi:10.7652/xjtuxb201104009]
唐正宗,梁晉,肖振中,等.大變形測量數(shù)字圖像的種子點匹配方法.2010,44(11):51-55.[doi:10.7652/xjtuxb201011011]
楊藝,韓崇昭,韓德強.一種多源遙感圖像分割的融合新策略.2010,44(6):88-92.[doi:10.7652/xjtuxb201006017]
徐海黎,花國然,莊健,等.采用小世界免疫克隆算子的頻率域圖像配準.2009,43(6):38-42.[doi:10.7652/xjtuxb2009 06009]
唐榮年,韓九強,張新曼.一種Log-Gabor濾波器結(jié)合多分辨率分析的虹膜識別方法.2009,43(4):31-33.[doi:10.7652/xjtuxb200904008]
王崴,李培林,張宇紅,等.地貌測量中圖像特征的匹配算法.2008,42(7):870-874.[doi:10.7652/xjtuxb200807019]
孫文方,宋蓓蓓,趙亦工.一種新穎的圖像多尺度幾何變換及其應(yīng)用.2007,41(8):982-985.[doi:10.7652/xjtuxb200708 023]
(編輯 武紅江)
AFastandAccurateImageRegistrationAlgorithmUsingSpaceOrderDescriptor
JIN Feng1,2,FENG Dazheng2
(1.School of Computer Science and Technology,Xidian University,Xi’an 710071,China;2.National Key Laboratory of Science and Technology on Radar Signal Processing,Xidian University,Xi’an 710071,China)
A fast and accurate image registration algorithm using the spatial order descriptor is proposed to improve existing image registration algorithms based on local structures that have the shortcomings of low registration accuracy on feature description and expensive computation on outlier removing.A simple shape descriptor for feature points is defined,and the definition is based on the space geometrical properties,uses the connective weights among the points and their rank order,and integrates the local structure and global information of the image.An efficient method to remove outlier is given to improve the registration accuracy,and the method is based on an improved random sample consistency test strategy.The registration accuracy is further improved by iteratively performing outlier removing and image registration.Experimental results show that the proposed algorithm has high registration accuracy and low computational cost.
image registration; image feature point; spatial order descriptor; random sample consensus
2013-10-28。
靳峰(1982—),男,博士生;馮大政(通信作者),男,教授,博士生導師。
國家自然科學基金資助項目(61271293/F010305)。
時間:2014-05-30
10.7652/xjtuxb201406004
TP391.4
:A
:0253-987X(2014)06-0019-06
網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140530.1615.001.html