圖像配準的復制動(dòng)力學(xué)方法

第27卷第11期計算機應用研究VoL 27 No. 112010年11月Application Research of ComputersNov.2010圖像配準的復制動(dòng)力學(xué)方法鄢余武,孫亞軍,姚小強(空軍工程大學(xué)導彈學(xué)院,陜西三原713800摘要:為了實(shí)現高精度圖像配準把單個(gè)像素看做參與博弈的局中人,將圖像配準視為圖像中各個(gè)像素與其周邊像素的演化博弈過(guò)程。為了尋求博弈的均衡點(diǎn),根據配準問(wèn)題的特點(diǎn),對復制方程進(jìn)行修改,提出基于修改后的復制方程的圖像配準方法。新方法是完全基于問(wèn)題域建立起來(lái)的,能實(shí)現對任意形變的高精度配準,并且配準精度與分辨率無(wú)關(guān)。針對剛性形變的遙感圖像和非剛性形變的醫學(xué)圖像進(jìn)行了兩組實(shí)驗,結果表明了新算法的有效性關(guān)鍵詞:圖像配準;演化博弈論;復制方程;適應度;形變中圖分類(lèi)號:TP391文獻標志碼:A文章編號:1001-3695(2010)114386-03doi:10.3969/j.isn.1001-3695.2010.11.110Replicator equation based image registration approachYAN Yu-wu, SUN Ya-jun, YAO Xiao-qiangMissile institute, Air Force Engineering Uninersity, Sanyuan Shaanxi 713800, China)Abstract: If model a pixel as a player, then image registration can be viewed as an evolutionary game, in which each pixelplay with its neighbors. To find an equilibrium point of the evolutionary game, this paper adapted the well known replicatorequation according to characteristics of image registration, and proposed a registration algorithm based on the adapted replicator equation, It developed the novel algorithm on problem domain totally, it could register any complex deformation with highand furthermore the accuracy was robust to image resolution. Experimentations on rigid-deformed remote sensing iages and nonrigid-deformed medical images are designed, the results show that the proposed approach is effectiveKey words: image registration; evolutionary game theory; replicator equation; fitness; deformation其他特征;E(T)是懲罰項旨在保證得到的變形場(chǎng)滿(mǎn)足0引言某些必要的屬性,如平滑性、正反變換的一致性、拓撲保持圖像配準是通過(guò)尋求空間變換,使兩幅或多幅圖像的對應性等。點(diǎn)達到空間位置上的完全一致,如圖1所示。圖像配準算求取最優(yōu)解T的常用優(yōu)化算法有Powe法、梯度下降法、法最早是在1981年提出的lua- Kanade算法2中出現,經(jīng)過(guò)遺傳算法、模擬退火算法和粒子群算法等。這些算法將配準看多年的發(fā)展,圖像配準算法在計算機視覺(jué)領(lǐng)域得到了廣泛的應做單純的優(yōu)化問(wèn)題,與問(wèn)題域結合得不夠緊密。由于能敏函數用,應用領(lǐng)域包括目標跟蹤、運動(dòng)分析、立體視覺(jué)和圖像拼接般是逆凸和非線(xiàn)性的脫離問(wèn)題域僅僅從函數優(yōu)化的角度出等,因此研究?jì)?yōu)良的圖像配準算法具有重要意義發(fā)很難實(shí)現高精度的圖像配準本文在分析圖像配準特性的基礎上將其歸結為像素博弈問(wèn)題從演化博弈論的角度提出一種基于復制方程的圖像配準方法。新方法是基于問(wèn)題域建立起來(lái)的,能實(shí)現對任意形變的高精度配準,且配準精度與分辨率無(wú)關(guān)。1圖像配準的博弈特性圖1圖像配準示意圖設y為顏色空間,P:→為浮動(dòng)圖,P:Dp→為T(mén):般地配準能量函數由相似性測度和懲罰項構成,分別參考圖,其中n、m是圖像的支撐域待尋求的空間變換為稱(chēng)為外力內力。配準是一個(gè)外力和內力互相競爭最終達到n→+D。為了求解最優(yōu)解T,通常將配準問(wèn)題轉換為能量函平衡的過(guò)程外力驅動(dòng)浮動(dòng)圖進(jìn)行形變而內力則對形變過(guò)程數的極值求解問(wèn)題,并采用優(yōu)化法對能量函數進(jìn)行迭代最優(yōu)搜進(jìn)行必要的約束。索。配準能量的一般表達式為將圖像視為空間上有序的像素集合形變過(guò)程中每個(gè)像素E(P,P以7)=E(P,P+En(T也受到圖像中其他像素的約束,即內力。其中:E(P,P)是相似性測度表示圖像特征之間的匹配如果找中國煤化工則配準可以視為圖像程度可以直接采用圖像的灰度信息,也可以采用圖像的中各CNMHG衡時(shí)認為配準結束。收稿日期:2010-05-24;修回日期:2010-07-2作者簡(jiǎn)介:都余式(1984-),男,江西上饒人,博士研究生,主要研究方向為圖像配準與融合(yl25@163.com);孫亞軍(1982-),男,陜西風(fēng)翔人,碩士研究生,主要研究才向為館號與信息處理;姚小強(1983-),男,河南洛陽(yáng)人,磺士研究生,主要研究方向為圖像處理第11期鄢余武,等:圖像配準的復制動(dòng)力學(xué)方法4387博奔可以采取合作或非合作的方式進(jìn)行非合作博弈論是在分布式?jīng)Q策環(huán)境下分析局中人為3基于復制方程的圖像配準算法最大化個(gè)體效用的最優(yōu)策略選擇問(wèn)題。演化博弈是非合作博弈的一個(gè)分支它以有限理性的群體為研究對象進(jìn)一步分析3.1對復制方程的修改策略在群體中的長(cháng)期穩定性問(wèn)題較好地克服了經(jīng)典博弈論中與生物系統相比,圖像配準有如下特性理性假定及多重均衡的困難。演化博奔的納什均衡具有群體a)復制方程描述的系統是偽動(dòng)態(tài)的,系統的收益矩陣一穩定性,同時(shí)還可揭示采取均衡策略的個(gè)體比例般能事先確定;而圖像配準表示了一個(gè)真實(shí)的動(dòng)態(tài)系統,每輪迭代中每個(gè)個(gè)體的適應度都要重新計算。2復制方程b)在復制方程描述的進(jìn)化過(guò)程中,演化行為由固定的收益矩陣確定;而演化圖像配準過(guò)程的進(jìn)化軌跡由參考圖確定早在1930年, Fisher就提出了著(zhù)名的自然選擇基本原理c)復制方程假設種群中的個(gè)體可以被重復選擇,而圖像并被廣泛用于研究生物進(jìn)化過(guò)程的動(dòng)力學(xué)行為。該原理配準要求每個(gè)個(gè)體至多只能被選擇一次表明種群的適應度增長(cháng)率等于同一時(shí)刻適應度方差的2倍d)復制方程對所有個(gè)體同等對待,而圖像配準算法一般即E=2Σ1a1(e1-E)2。其中;a是個(gè)體i在種群中的出現要懲罰選擇同一個(gè)點(diǎn)作為潛在復制子的競爭個(gè)體。幾率;e,是i的適應度值;E是整個(gè)種群的加權平均適應度;E要對復制方程進(jìn)行相應的修改,以適應精確自動(dòng)圖像配準是E對時(shí)間t的導數。在種群進(jìn)化過(guò)程中,如果沒(méi)有發(fā)生變的需求。首先將圖像表示為像素點(diǎn)集:P=1P2i∈Dp},異,后代將完全繼承父輩的特性,所有個(gè)體都根據預定義的模P=|perl式(稱(chēng)為純策略)決定自己的行為。叫1對時(shí)間t的導數1)建立潛在的對應關(guān)系設變換T對n中的任一點(diǎn)i進(jìn)行空間變換產(chǎn)生的位移為式(1)描述了自然選擇的動(dòng)力學(xué)系統稱(chēng)為復制方程。種a,N為i的鄰域P,的配準能量為群在時(shí)刻t的狀態(tài)向量u(t)={a(t),u2(l),…,an()}位于E(p…)=p-p…42+A減-4n維歐式空間S={w∈R:∑a1=1,o1≥0}的標準單純形中。P2的演化目標是求取在種群遺傳中種群表示所有可能的個(gè)體設A,表示個(gè)體i(2)的后代數量的期望值則種群的收益矩陣可以定義為U={2)參數推導AA}l。在博弈論中種群表示策略的集合,設山表示采用策略復制方程假設相對增長(cháng)率aa1等于個(gè)體適應度與種群i對抗策略j所獲得的收益則策略i的適應度為e=E,平均適應度E=∑叫的差。為了減小圖像分辨率對最終配整個(gè)種群的加權平均適應度為E=Σ∑叫叫。復制方程具準結果的影響,本文用相對適應度差代替式(1)中的絕對適應有如下優(yōu)異特性度差:a)因為Σ,ω=0,所以狀態(tài)向量w(t)始終在單純形S中。這意味著(zhù)狀態(tài)向量始終表示個(gè)體在種群中的出現幾率的=的b)如果U={al}對稱(chēng),則E始終隨時(shí)間增長(cháng)由于∑=0仍然成立,演化配準過(guò)程的軌跡仍然處于單c)如果U={ug對稱(chēng)則向量(t)和Uk(t)的點(diǎn)積是純形S,內。Lyapunov函數。因此,復制動(dòng)力學(xué)系統始終是穩定的將式(3)重寫(xiě)為d)如果w∈S是進(jìn)化穩定的,則w是漸進(jìn)均衡的。系統不收斂。當n≤3時(shí),復制方程沒(méi)有極限環(huán);當n≥4時(shí),對于特定的收益矩陣復制方程存在極限環(huán)。如果S內部不存在不積分,得到動(dòng)點(diǎn),則每條軌跡都收斂到Sn的邊界上。如果邊界具有排斥(0.5e;-E)性則S,內部存在一個(gè)唯一的不動(dòng)點(diǎn),該不動(dòng)點(diǎn)對應于S內部所有軌跡的時(shí)間平均。)適應度估計特性a)實(shí)際上使得狀態(tài)向量通過(guò)動(dòng)力學(xué)本身實(shí)現了歸設(P,P,4)是潛在的對應點(diǎn)則個(gè)體P的適應度定義為化;特性b)確保在特定條件下,系統能隨時(shí)間的推進(jìn)逐步改善性能;特性c)保證了在特定條件下進(jìn)化系統是穩定的,不管系4)利用多對一映射建立潛在的對應關(guān)系統從哪個(gè)點(diǎn)開(kāi)始進(jìn)化;特性d)揭示了什么情況下存在最優(yōu)解復制方程假設種群中的所有策略都可以被任意數目的局以及在何處取得最優(yōu)解。這些特性對于圖像配準來(lái)說(shuō)都是成人采用而圖像配準算法一般認為圖像P中的一點(diǎn)至多只立的。特性a)對潛在對應點(diǎn)的概率進(jìn)行歸一化特性b)表示能對應于圖像P中的一個(gè)點(diǎn)反之亦然。P中某個(gè)點(diǎn)的所有整個(gè)種群的平均配準誤差隨迭代次數近似單調遞減;特性c)圖像必須進(jìn)行競爭,最終獲得圖像間可能的對應關(guān)系。此時(shí)的揭示了最終的配準結果與初始化參數無(wú)關(guān)因此極大地簡(jiǎn)化了對應關(guān)直實(shí)的對應關(guān)系需要通過(guò)以下三個(gè)步驟進(jìn)參數的初始化過(guò)程:特性d)說(shuō)明了如何有效地搜索最優(yōu)狀態(tài)行評估中國煤化工變量,如何評價(jià)最終的狀態(tài)變量。當系統穩定時(shí),=o(e1-CNMHGE)=0,則o4=0或E=e。a=0表示個(gè)體i死亡了,因此i是b)計界系積學(xué),at+4+“;+,∈D;個(gè)已消亡的點(diǎn);E=e表示讠存活著(zhù)因此i是一個(gè)位于重疊c)重新評估每個(gè)對應關(guān)系(P,P,4)的概率,a區域的點(diǎn)a'4,i∈4388計算機應用研究第27卷5)平均場(chǎng)退火RMSE值越小配準效果越好。實(shí)驗結果比較見(jiàn)圖3,其中的橫采用確定性退火優(yōu)化潛在對應關(guān)系(P,P1,d)的概率坐標表示分辨率,如橫坐標取值100表示分辨率為100×1其中:參數B(B>0)表示反轉溫度。3.2新算法綜合以上因素得到如下算法圖3不同分辨率下的配準性能比較(遙感圖像)初始化。設初始反轉溫度B=島,反轉溫度增加速率為由圖3可知,RE算法的RMSE對分辨率變化不敏感,而β,終止反轉溫度為月終止時(shí)相鄰代之間的相對變異為p,最NMl-A算法的RMSE隨分辨率降低增加較快,并且RE算法的大選代數為l,選代數k=0,a(=l∥/Dp|。RMSE小于NM-A算法的RMSE。即在同一分辨率下,RE算a)若B=By,終止。法的平均精度高于NM|-A,而且對分辨率的變化具有較好的魯b)若相鄰代之間的相對變異小于p或k≥l,終止。棒性。同時(shí),隨著(zhù)分辨率的降低,RE算法的計算量下降較快c)根據式(2)建立P、P間潛在對應關(guān)系(p,P4)的集但總體上看RE算法的計算量大于NM-A合;根據式(5)計算種群P中每個(gè)個(gè)體P的適應度e;計算整實(shí)驗2非剛性形變的醫學(xué)圖像配準個(gè)種群的加權平均適應度E=∑汕1"c/Σa1;根據式(6)基于光流場(chǎng)模型的 Demons算法0是一種應用廣泛的先更新?tīng)顟B(tài)變量a11);根據懲罰過(guò)程對多對一映射進(jìn)行懲罰。進(jìn)的圖像配準方法。實(shí)驗2將RE與 Demons算法進(jìn)行比較,d)對目標函數進(jìn)行尋優(yōu),更新位移向量d評價(jià)其性能。e)an←1(),k←k+1,轉到b)實(shí)驗數據采用經(jīng)過(guò)仿射預配準的醫學(xué)MR圖像,灰度級為DB+BB,轉到a)。0-255,原始圖像取自BrainWeb(htp://www.bicmni.megillca/ brainweb)。取圖4所示的MR圖像作為參考圖,并對參考4實(shí)驗結果與分析圖進(jìn)行人工形變得到兩種浮動(dòng)圖,如圖5(a)所示。RE和De為了驗證所提出算法的有效性,通過(guò)兩組實(shí)驗將本文提出mons算法的配準結果分別如圖5(b)(c)所示。從配準結果可的基于復制方程的配準算法(以下簡(jiǎn)稱(chēng)RE算法)與兩種典型算知, Demons算法不能正確配準第二種形變,因為圖中一些點(diǎn)的法進(jìn)行比較實(shí)驗在PC(P43.06 GHz CPU,1GB內存, Fedora10形變很大(超過(guò)了10個(gè)像素),算法陷入了局部最優(yōu);而RE算操作系統 MATLAB1)上完成。兩組實(shí)驗中E算法的參數法仍然能夠正確配準,尋優(yōu)能力優(yōu)于 Demons算法。均取A=0.0000.=1.05,B=L.0,=10,p=0.00l。實(shí)驗1剛性形變的遙感圖像配準實(shí)驗采用的真實(shí)遙感圖像取自 Vision Research Lab(hp://ion,ece.ucsb.edu),如圖2所示。對圖2中的圖像進(jìn)行多分辨率處理,得到一組大小為200×200、180×180、160160、140×140、120×120、100×100、80×80和60x60的圖像并在各個(gè)分辨率上進(jìn)行配準實(shí)驗圖4備考圖(a)參考圖(b)浮動(dòng)圖(c)標準圖圖2實(shí)驗1用到的遙感圖像基于互信息量的配準算法是目前公認較好的配準方法在圖像配準領(lǐng)域取得了極大的成功。根據圖像特點(diǎn)實(shí)驗1采用基于歸一化互信息( normalized mutual information,NM)和仿射(aine)變換模型的算法(以下簡(jiǎn)稱(chēng)NMl-A算法)與RE算法進(jìn)行比較。NMlA算法的插值方法和優(yōu)化方法分別采用雙線(xiàn)性插值和遺傳算法,遺傳算法的實(shí)現采用 MATLAB的g函數參數 StallTimeLimit設為lnf,參數 HybridEn設為@ fminsearch,即遺傳優(yōu)化結束后繼續進(jìn)行局部尋優(yōu)取運行時(shí)間t配準結果和標準圖的均方根誤差RMSE為中國煤化工指標(指標均取20次實(shí)驗的平均值),對兩種算法進(jìn)行比較。RMSE定義為CNMHG結果√m與實(shí)驗1類(lèi)似,對參考圖和形變1對應的浮動(dòng)圖進(jìn)行多分辨率處理得到一組大小為200×20、180×180、160×160、140×140、其中:P2-p表示兩幅圖像在i處的顏色差,n為像素總個(gè)數,120×120、100×10080×80和60x60的圖像,(下特第4393頁(yè)第11期李建鋒,等:一種基于PCN的醫學(xué)圖像邊緣提取方法4393·4結束語(yǔ)[8]ECKHORN R, RETTBoECK H J, ARNDT M, ef al. A neural net-ork for feature linking via synchronous activity:本文通過(guò)分析基本PCNN的特性提出了一種改進(jìn)的PCvisual cortex and from simulations[ M]. Cambridge: Cambridge Uni-NN圖像邊緣提取的方法,并將該方法應用于醫學(xué)圖像的邊versity Press, 1989: 255-272提取該方法很好地結合了PCNN仿生物視覺(jué)的特性和經(jīng)典邊[9〕 RElTBOECK H J, ECKHORN R, ARNDT M,ea. A model for緣檢測算子的優(yōu)點(diǎn)。實(shí)驗結果也表明,本文算法在醫學(xué)圖像的feature linking via correlated neural activity[ M]. New York: Spring-處理上無(wú)論是在邊緣的提取能力還是對椒鹽噪聲的抑制能力方面都優(yōu)于基本的PCNN以及Cany,sobe、 Prewitt Roberts等[ 10] ECKHORN R, RETTBOECK HJ, ARNDT M,cal. Feature linking經(jīng)典邊緣檢測箅法,從而證明了本文方法的可行性。via synchronization among distributed assemblies: simulation of results參考文獻[11]JOHNSON J L, PADGETT M L. PCNN models and applications[J][1] ELINABROUK A, AGGOUN A. Edge detection using local histogramIEEE Trans on Neural Networks, 1999, 10(3): 480-498nalysis[ J]. Electronics Letters, 1998, 34(12): 1216-1217.[ 12] LIU Qing, MA Yi-de, ZHANG Shao-gang. Image target recognitionDaviSLs.Asurveyofedgedetectiontechniques[j].computerusing pulse coupled neural networks time matrix[ CJ//Proe of theGraphics and Image Processing, 1975, 3(4): 248-270.26th Chinese Control Conference. 2007: 96[3] BASU M. Gaussian-based edge-detection methods: a survey [J). [133 Lu-ping. YT Zhang. A mixed noise image filtering method usingEEE Trans on Systems, Man, and Cybemetics-Part C: Applica-ighted-linking PCNN[ J]. Neural Computing, 2008, 71(13-15)tions and Reviews, 2002, 32(3): 252-2602986-3000.[4] TAO Hai, HUANG T S. Color image edge detection using cluster[14]MA Yi-de, LIN Dong-mei, ZHANG Bei-dou, e al. A novel algo-lysis[ C]//Proc of Intemational Conference on Image Processorrithm of image enhancement based on pulse coupled neural networktime matrix and rough set[ C]//Prmc of the 4th Intemational Confe-[5] RUSSO F. Edge detection in noisy images using fuzzy reasoningzry Systems and Knowledge Discovery. 2007: 86-90[C]//Proc of IEEE Instrumentation and Measurement Technology [15]u Min, CAl Wei, TAN Zheng. A region-based multi-sensor imageConference. 1998:369-372fusion scheme using pulse-coupled neural network[J]. Pattem[6] SIYAL M. Edge detection with BP neural networks[ C]//Proe of thRecognition Letters,2006,27(16):1948-19564th Intemational Conference on Signal Processing-. 1998: 1382-1384. [16]DI Lan, LIN Y, LU Li, An algorithm for image edge detection using[7] SIDDIQUE J 1, BURNER K E. Wavelet-based multi-resolutionimproved PCNN C//Proc of IEEE Intemational Conference onedge detection utilizing gray level edge mape[C]//Proe of IEEEGranular Computing. 2009: 136-139.(上接第43883頁(yè))并在各個(gè)分辨率上進(jìn)行配準實(shí)驗。以參考圖兩組配準實(shí)驗表明了新算法的有效性。和配準結果的均方根誤差RMSE和運行時(shí)間為標準比較兩參考文獻種算法對形變1的配準性能比較結果如圖6所示。由圖6可[1] ZIToVA B, FLUSSER J. Image registration methods:asmr[門(mén)知在相同分辨率下,RE算法的精度高于 Demon,并且對分辨Image and Vision Computing, 2003, 21(11): 977-1000率的變化具有魯棒性;兩種算法的計算量都隨分辨率提升而增[2] LUCAS B D, KANADE T. An iterative image registration technique大,但總體上RE算法的計算量比 Demons大。相比于實(shí)驗1with an application to stereo vision[ C]//Proc of Intemational Joint此處RE算法的計算量較少,這是由于所用的圖像已經(jīng)過(guò)仿射Conference on Artificial Intelligence. 1981 674-679預配準,且非剛性形變較小[3] GLOCKER B, KOMODAKIS N, TZIRITAS G, et al. Dense imageregistration through MRFs and efficient linear programming[J]. Med-ical image Analysis, 2008, 12(6): 731-741[4] ALEXANDER W, PAUL F. Fast phase-based registration of multimo-0dal image data[ J]. Signal Processing, 2009, 89(5): 724-73760182080100120140160180200[5] THOMAS L V, JOEL S B. Evolutionary game theory, natural selec.圖6不同分辨率下的配準性能比較(醫學(xué)圖像tion, and Darwinian dynamics[ M]. Cambridge: Cambridge Universi-RE算法的良好性能根源于博弈論,由于將圖像視為局中人(個(gè)體)集模型的自由度遠大于傳統的配準算法,有利于提[6]張維迎,博弈論與倌惠經(jīng)濟學(xué)[M]上海:上海人民出版社,高算法的配準能力和配準精度。從運行機制上看,RE算法是一種自下而上的方法每個(gè)個(gè)體都有自己的演化目標群體通7N0wAKM, SIRMUND K. Evolutionary dynamics of biological game過(guò)迭代的方式收斂到均衡點(diǎn),具有“涌現”特性這使得算法能004,303(5659):793實(shí)現對任意形變的高精度配準,且配準精度對分辨率變化不敏8] STADLER B MR, SRADLER P F. Molecular replicator dynamic慼魯棒性好,但相應的代價(jià)是計算量的增加1s,2003,6(1):47-77[9] YAN Yu-wu, uU Jin -mang, TONG Ming. A game-theoretic approach5結束語(yǔ)for nonrigid medical image registration[ C ]//Proc of Intemational中國煤化工 Computer Science.200研究配準能力強精度高的圖像配準算法在遙感導彈成像制導、無(wú)人機導航、手術(shù)導航等領(lǐng)域具有重要意義。本文分[10]wCNMHGal. validation of析了圖像配準具有博弈的特性并從演化博弈論的角度把迭代cele-rated'Demons'algorithm for deformable image registration in ra圖像配準看做一個(gè)演化過(guò)程提出了基于復制方程的圖像配準diation therapy[ J]. Physics in Medicine and Biology, 2005, 50算法。針對遙感圖像(剛性形變)和醫學(xué)圖像(非剛性形變)的12):2887-2905