基于文化粒子群的圖像配準優(yōu)化算法

朱霞，陳仁文，夏樺康，章飄艷

(南京航空航天大學 機械結(jié)構(gòu)力學及控制國家重點實驗室，江蘇南京210016)

0 引言

圖像配準是指同一目標的兩幅圖像在空間位置的對準。圖像配準技術(shù)過程稱為圖像匹配或者圖像相關(guān)。用一幅浮動圖像尋找一種空間幾何變換，使它與另一幅參考圖像在某些特征點上達到一致。它們的差異可能來源于不同的拍攝設(shè)備、不同拍攝位置、不同采集時間、不同傳感器分辨率等，而這些將加大配準的難度［1-4］。通常情況下，圖像配準由以下4 個基本的步驟組成:1)選擇相似性測度算法;2)確定變換模型;3)確定圖像插值方法;4)優(yōu)化策略。本文將重點放在相似性測度算法和優(yōu)化策略上面。相似性測度用來衡量兩幅或多幅圖像匹配的效果，運用一種準則使兩幅或多幅圖像在該準則下匹配效果達到最佳。互信息作為一種相似性測度，已被公認為是精度和魯棒性最高的圖像配準方法之一。互信息無需進行預(yù)處理，可以應(yīng)用于單模或多模的配準，特別是當其中一幅圖像有數(shù)據(jù)缺損時，也能得到很好的配準效果。基于互信息有好多種方法，如最大化互信息法、歸一化互信息法等。由于互信息只統(tǒng)計兩圖像間的灰度相關(guān)信息，在噪聲、分辨率等因素的影響下會導(dǎo)致兩圖像間的相關(guān)信息減少，很容易陷入局部極值，最終可能導(dǎo)致誤配準。解決方法就是將互信息與其他判斷條件相結(jié)合，如:梯度、形態(tài)學梯度等，從多方面改進互信息測度，提高配準的精確度。

圖像配準中的優(yōu)化策略可以歸結(jié)為最優(yōu)化問題，即如何在精度和速度之間取得最佳。目前求解優(yōu)化問題的主要手段就是對優(yōu)化問題的可行解空間進行搜索。搜索方法主要有:共軛梯度法、爬山法、遺傳算法、模擬退火算法、粒子群優(yōu)化(PSO)算法等。PSO 算法具有原理簡單、易于實現(xiàn)、需要調(diào)整的參數(shù)較少的特點。但是傳統(tǒng)的PSO 算法后期容易陷入早熟收斂狀態(tài)，導(dǎo)致計算時間延長，計算量增大，運算效率較低，抗噪能力差，最終造成配準效果不好。魏本征等在原始PSO 算法的基礎(chǔ)上提出改進型PSO(IPSO)算法，改進后的慣性權(quán)重因子由ω轉(zhuǎn)變?yōu)?α+β×rand())ω，即對粒子群體而言，群體中慣性權(quán)重因子可以是域［αω，(α+β)ω］中的任意隨機數(shù)，群體中既可存在較大的權(quán)重因子加強PSO算法的全局搜索能力，又可有較小的權(quán)重因子加強局部搜索能力，改進操作起到提高權(quán)衡全局搜索和局部搜索能力作用，提高了算法搜索能力和收斂速度，在應(yīng)用中取得較好的效果［3］。魏本征等將其引入到醫(yī)學圖像的配準中，效果有了一定的改善，但是從速度、收斂效果、精確度來講還可以提高。本文提出了將文化粒子群優(yōu)化(CPSO)算法與最大化互信息相結(jié)合的改進方案，以解決圖像配準中計算量過大、搜索速度慢等問題。

1 基于互信息的圖像配準

互信息(MI)的概念來源于信息論，是信息理論中的一個基本概念，互信息衡量的是兩個或多個事件之間關(guān)系的緊密程度［2，5］。就一幅圖像而言，可以看成是灰度的隨機變量集，它含有信息量的多少可以用熵來表示。

式中:p(xi)為灰度值xi出現(xiàn)的概率。圖像的互信息表示兩幅圖像所包含的共同信息，可用兩幅圖像的互信息作為圖像配準的相似度函數(shù)，當互信息最大時兩幅圖像就實現(xiàn)了配準。兩幅圖的平均互信息可以由兩幅圖的熵和聯(lián)合熵組成。

聯(lián)合熵H(X，Y)的含義是圖像X 和圖像Y 中的事件同時發(fā)生的平均不確定性。定義為

對于圖像X、圖像Y 的互信息可表示為

這樣，由(4)式可以看出，對于互信息的計算就轉(zhuǎn)化為對兩幅圖像概率分布的計算。最大化互信息將信息論引入圖像配準，假設(shè)有兩幅圖像，X(浮動圖像)和Y(參考圖像)，當圖像X 在某些特征點上與圖像Y 達到一致時，互信息值最大，此時兩幅圖像的配準程度達到最佳。該方法不依賴人工干預(yù)，不需要對圖像進行預(yù)處理，也不需要任何的假設(shè)性先驗知識等，是實現(xiàn)配準自動化的一個非常好的選擇［5］。因此，基于最大化互信息配準的目的就是尋找互信息最大時的配準參數(shù):

式中:Fit(r1，r2，r3，…)為優(yōu)化約束函數(shù)，配準參數(shù)r1，r2，r3，…為圖像的縮放因子、旋轉(zhuǎn)因子、平移因子等。

由于噪聲的存在，互信息相似度函數(shù)會存在局部極大值或收斂緩慢等問題，本文針對這一問題探討利用CPSO 算法進行圖像配準的參數(shù)優(yōu)化［6-7］。

2 文化粒子群優(yōu)化算法

PSO 算法最早是美國Kennedy 博士受鳥群覓食行為的啟發(fā)，提出的一種生物進化算法。PSO 算法基于群體與適應(yīng)度，它將每個個體視為無體積的粒子，在搜索空間以變速飛行，其飛行速度根據(jù)該粒子本身的歷史經(jīng)驗以及同伴的歷史經(jīng)驗進行動態(tài)調(diào)整。Reynolds 于1994年提出了文化算法，從微觀和宏觀不同層面模擬生物層面的進化和文化層面的進化，該算法的雙層演化結(jié)構(gòu)框架有利于算法的全局收斂性［8］。因此本文將文化算法引入到PSO 算法，提出了一種CPSO 算法，并將該算法用于求解圖像配準的參數(shù)優(yōu)化問題。

本文提出的算法包含兩個進化空間:一個是由具體個體組成的群體空間，另一個是由在進化過程中獲取的經(jīng)驗和知識組成的信念空間。其演化框架如圖1所示，其中群體空間是算法進行問題求解的主空間［9-10］。通過演化操作和性能評價進行自身的迭代求解，形成個體經(jīng)驗，并通過accept()函數(shù)將個體經(jīng)驗傳遞到信念空間。信念空間將接收到的個體經(jīng)驗，不斷地進行自身的性能評價與演化，形成群體經(jīng)驗。信念空間通過influence()函數(shù)對群體空間的個體行為規(guī)則進行修改，以使群體空間中得到更高的進化效率［11］。

圖1 文化粒子群算法的基本框架Fig.1 The basic framework of cultural particle swarm optimization algorithm

2.1 群體空間的設(shè)計

由于PSO 算法是一種基于個體改進、種群協(xié)作與競爭的進化計算方法，具有理論簡單、易于編碼實現(xiàn)的特點，因此群體空間采用基本PSO 算法進行演化。粒子群可用下面5 元素形式描述:

式中:n 為群體規(guī)模;iter 為迭代次數(shù);V 和X 分別表示所有粒子的速度空間和位置空間;Ffit為適應(yīng)度，從位置空間映射到實數(shù)空間。在每一次迭代中，粒子通過跟蹤個體極值pbest 與全局極值gbest 來更新自已的位置和速度，公式如下:

式中:v(t)是粒子的當前速度;x(t)是粒子的當前位置;rand()是［0，1］之間的隨機函數(shù);c1和c2是學習因子，通常都取值為2;ω 是加權(quán)系數(shù)，用來控制歷史速度對當前速度的影響程度，一般在［0.1，0.9］之間取值。

本文針對權(quán)重問題提出一種改進的動態(tài)慣性權(quán)重調(diào)整策略，慣性權(quán)重調(diào)整公式如下:

2.2 信念空間的設(shè)計

信念空間定義為＜S，N［n］＞，其中:S 表示環(huán)境知識中存儲的一組由歷代種群所產(chǎn)生的最優(yōu)個體集合;標準知識N 保存目標函數(shù)n 個主變量參數(shù)的變化區(qū)間。每個區(qū)間描述為＜Ij，Lj，Uj＞，j =1，2，…，n. 其中:Iq=［l，u］={l≤x≤u，x∈R}，表示變量x 定義域邊界的值。上下界u 和l 由給定的值域初始化，Lj表示參數(shù)j 在區(qū)間下限lj對應(yīng)目標函數(shù)的適應(yīng)值，Uj是參數(shù)j 在區(qū)間上限uj對應(yīng)目標函數(shù)的適應(yīng)值。

2.3 接受函數(shù)

種群空間通過接受函數(shù)向信念空間提供一組最優(yōu)子集，在最優(yōu)化問題中一般是按一定的百分比取值，通常取20% ～25% ，或者根據(jù)問題環(huán)境的變化按一定的規(guī)則選取參數(shù)。

接受操作:在群體空間的粒子群演化過程中，每運行Acc 代時，用群體空間當前的全局最好值來替換信念空間中適應(yīng)值差的粒子。

式中:Bnum和Dnum為文化算法中的兩個參數(shù)，用于調(diào)節(jié)接受操作和影響操作的完成次數(shù);kmax為粒子群預(yù)先設(shè)定的粒子群最大演化代數(shù);k 為粒子群演化的當前代數(shù)。

2.4 更新信念空間

標準知識N 的更新規(guī)則如下:

這里，第i 個個體影響參數(shù)j 的區(qū)間下邊界。lkj表示參數(shù)j 第k 次迭代時的下邊界;Lkj表示lkj對應(yīng)目標函數(shù)的適應(yīng)值。同理，第i 個個體也影響參數(shù)j 的區(qū)間上邊界。ukj表示參數(shù)j 第k 次迭代時的上邊界，表示ukj對應(yīng)目標函數(shù)的適應(yīng)值。

2.5 影響函數(shù)

信念空間在形成群體經(jīng)驗后，通過影響函數(shù)對群體空間中個體的行為規(guī)則進行修改，以使個體空間得到更高的進化效率。影響函數(shù)決定哪種知識將被用于指導(dǎo)需要解決的問題。根據(jù)具體問題的不同，影響函數(shù)的設(shè)計也不同。不同的知識源對種群空間也有相應(yīng)不同的影響函數(shù)。

影響操作為在群體空間的粒子群演化過程中，每運行Inf 代時，用信念空間當前的全局最好值來替換群體空間中適應(yīng)值差的粒子。

3 CPSO 在配準中的算法設(shè)計

結(jié)合互信息的計算方法，將CPSO 算法用于二幅圖像的配準。算法流程為:

步驟1 確定算法的搜索空間，即浮動圖像在水平、垂直方向的平移量，浮動圖像繞原點旋轉(zhuǎn)的角度。

步驟2 初始化設(shè)置。設(shè)置群體空間和信念空間的種群大小，群體規(guī)模n =40，慣性權(quán)因子ω =0.9，學習因子c1=c2=2，微粒子最小位置值xmin=0，最大位置值xmax=4.0，微粒子最小速度值vmin=-2.0，最大速度值vmax=2.0. 計算粒子的互信息值以及每一個粒子的最優(yōu)值和全局最優(yōu)值。

步驟3 根據(jù)群體空間粒子位置，計算粒子的實際輸入和適應(yīng)值函數(shù)(兩幅圖像的相似性測度——最大互信息)。

步驟4 更新信念空間粒子位置，計算粒子的實際輸入和適應(yīng)值函數(shù)。

步驟5 判斷若k%Acc = =0 時，進行接受操作。

步驟6 更新群體空間粒子的位置和速度，根據(jù)最大化互信息判定檢驗粒子的速度和位置是否越界，若是，調(diào)整速度和位置。

步驟7 計算群體空間中各粒子的實際輸入和適應(yīng)值函數(shù)。

步驟8 更新信念空間粒子的位置和速度，根據(jù)最大化互信息判定檢驗粒子的速度和位置是否越界，若是，調(diào)整速度和位置。

步驟9 計算信念空間中粒子的實際輸入和適應(yīng)值函數(shù)。

步驟10 判斷若k%Inf = =0 時，進行影響操作。

步驟11 當誤差達到最初設(shè)定值或最大迭代次數(shù)時，輸出gbest 對應(yīng)的調(diào)度方案和目標值;否則，令k=k+1，返回步驟3.

4 仿真與實驗分析

本文在內(nèi)存為2 GB、處理器為Intel Core(TM)2 DUO CPU T5250 @1.50 GHz 的PC 上使用MATLAB 7.0 編譯軟件進行圖像配準實驗。以圖像配準為例，將PSO，IPSO，CPSO 算法獨立運行100 次。各性能參數(shù)比較見表1. 圖2(a)為浮動圖像，圖2(b)為參考圖像，兩幅圖在水平方向、垂直方向和旋轉(zhuǎn)角度上偏差。設(shè)計算法時將旋轉(zhuǎn)角度范圍初定為［-20°，+20°］. 圖2(c)為使用PSO 配置后得到的圖像，圖2(d)為使用IPSO 配置后得到的圖像，圖2(e)為使用CPSO 配置后得到的圖像。

表1 3 種算法中的參數(shù)比較Tab.1 The parameters of three algorithms

圖2 基于不同粒子群優(yōu)化算法的配準效果圖Fig.2 The registration results based on different PSO algorithms

表1中給出3 種算法對圖2仿真得到指標比較。從表1可以看出，本文提出的方法在標準差、熵和互信息這些指標上優(yōu)于其他方法，只是灰度均值比其他方法略差一點。圖3、圖4和圖5給出了實例中3 種算法執(zhí)行后得到的誤差收斂曲線。很容易看出，使用PSO 算法搜索時，經(jīng)過2.5 s 之后就能使搜索到的位置達到最優(yōu);使用IPSO 算法，經(jīng)過1.5 s之后到達最優(yōu);使用本文方法，經(jīng)過1 s 就能使搜索達到標準。由此可知，CPSO 算法比PSO 算法和IPSO 算法提前收斂，運行時間更短。

圖3 水平方向、垂直方向和角度誤差(PSO 算法)Fig.3 The error of parameters in PSO algorithm

圖4 水平方向、垂直方向和角度誤差(IPSO 算法)Fig.4 The error of parameters in IPSO algorithm

圖5 水平方向、垂直方向和角度誤差(CPSO 算法)Fig.5 The error of parameters in CPSO algorithm

為進一步驗證配準算法的可行性，利用歸一化互相關(guān)通過轉(zhuǎn)換一副圖像來使兩幅圖像配準［12］。圖6顯示了兩幅圖像，其中左圖為右圖的子圖。計算兩幅圖像之間的歸一化互信息，如圖7所示。歸一化峰值最大的地方意味著這兩幅圖示最相關(guān)的地點，圖像中總的變換量依賴于互相關(guān)中峰值的位置、圖像的大小等。最后為了凸顯配準效果，將全景圖先處理為灰度圖像，在全景圖中顯示彩色的子圖，如圖8所示，從中可以看出，兩幅圖像配準成功了。同樣的算法，用于實際拍攝的圖像圖9(a)，可以看出如果選取的子圖像比較小，圖9(b)的歸一化相關(guān)圖中的峰值就比較錯亂。所以本文的算法比較適合子圖在全景圖中占百分比多一點的圖像配準。

圖6 待配準的圖像(圖像來源于MATLAB 素材庫)Fig.6 Images under registration(original images from MATLAB)

圖7 兩幅圖像的歸一化相關(guān)Fig.7 Normalized correlation of two images

圖8 最后配準的圖像Fig.8 Registrated image

5 結(jié)論

圖像配準是將同一場景的兩幅或多幅圖像對齊的過程。圖像的配準本質(zhì)上是一個多維空間尋優(yōu)的過程，針對具有平移、旋轉(zhuǎn)和拍攝條件不同的圖像，提出了一種基于文化粒子群與互信息的圖像配準方法。大量實驗結(jié)果表明，本算法對存在尺度以及旋轉(zhuǎn)變化的圖像能夠?qū)崿F(xiàn)準確的配準。用最大化互信息作為相似性測度可以解決圖像間相關(guān)性的問題。CPSO 算法作為搜索方法可以解決傳統(tǒng)PSO 算法搜索速度慢的問題。本文將此算法與傳統(tǒng)PSO 算法和IPSO 算法的效果進行了比較，通過實驗結(jié)果分析可知，本文提出的圖像配準算法是一種比較穩(wěn)健的配準算法，具有速度快、魯棒性好等特點。

圖9 配準后的圖像(圖像來源于實際拍攝)Fig.9 Registrated image (the images captured in the actual test environment)

References)

［1］丁南南，劉艷瀅，張葉，等.基于SURF-DAISY 算法和隨機kd 樹的快速圖像配準［J］.光電子·激光，2012，23(7):1395 -1402.DING Nan-nan，LIU Yan-ying，ZHANG Ye，et al. Fast image registration based on SURF-DAISY algorithm and randomized kd trees ［J］. Journal of Optoelectronics ·Laser，2012，23(7):1395 -1402.(in Chinese)

［2］張澤旭，李金宗，李冬冬. 基于光流場分析的紅外圖像自動配準方法研究［J］.紅外與毫米波學報，2003，22(4):307 -312.ZHANG Ze-xu，LI Jin-zong，LI Dong-dong .Research of automated image registration technique for infrared images based on optical flow field analysis ［J］. Journal of Infrared and Milimeter Waves，2003，22(4):307 -312.(in Chinese)

［3］魏本征，趙志敏，宋一中. 基于IPSO 和綜合信息的醫(yī)學圖像配準新方法［J］.光電子·激光，2009，20(9):1271 -1274.WEI Ben-zheng，ZHAO Zhi-min，SONG Yi-zhong. A novel algorithm for multimodality medical image registration based on IPSO algorithm and hybrid information［J］. Journal of Optoelectronics·Laser，2009，20(9):1271 -1274.(in Chinese)

［4］柏連發(fā)，韓靜，張毅，等.采用改進梯度互信息和粒子群優(yōu)化算法的紅外與可見光圖像配準算法［J］.紅外與激光工程，2012，41(1):248 -254.BAI Lian-fa，HAN Jing，ZHANG Yi，et al. Registration algorithm of infrared and visible images based on improved gradient normalized mutual information and particle swarm optimization［J］.Infrared and Laser Engineering，2012，41(1):248-254.(in Chinese)

［5］楊帆，張汗靈.蟻群算法和Powell 法結(jié)合的多分辨率三維圖像配準［J］.電子與信息學報，2007，29(3):622 -625.YANG Fan ，ZHANG Han-ling. Multiresolution 3D image registration using hybrid ant colony algorithm and Powell’s method［J］.Journal of Electronics ＆ Information Technology，2007，29(3):622 -625.(in Chinese)

［6］崔偉，劉圣霞，徐騫，等. 基于互信息和梯度的紅外與可見光圖像配準新方法［J］.激光與紅外，2011，41(2):224 -228.CUI Wei，LIU Sheng-xia，XU Qian. Novel infrared-visual image registration based on combined mutual and gradient information［J］.Laser ＆ Infrared，2011，41(2):224 -228.(in Chinese)

［7］尹丹艷，吳一全.灰色預(yù)測和混沌PSO 的紅外小目標檢測［J］.智能系統(tǒng)學報，2011，6(2):126 -131.YIN Dan-yan，WU Yi-quan. The detection of a small infrared target based on gray prediction and chaotic PSO［J］.CAAI Transaction on Intelligent System，2011，6(2):126 -131.(in Chinese)

［8］Reynolds R G. An introduction to cultural algorithms［C］∥Proceedings of the Third Annual Conference on Evolutionary Programming.River Edge，NJ:World Scientific Publishing，1994:131-139.

［9］朱霞. 一種求解作業(yè)車間調(diào)度的文化粒子群算法［J］.計算機應(yīng)用研究，2012，29(4):1234 -1240.ZHU Xia. Cultural particle swarm optimization algorithm for Jobshop scheduling problem［J］.Application Research of Computers，2012，29(4):1234 -1240. (in Chinese)

［10］Reynolds R G，Peng B. Knowledge learning and social swarms in culture algorithms［J］. The Journal of Mathematic Sociology，2005，29(2):115 -132.

［11］Wang F，You H J，F(xiàn)u X Y. Adapted anisotropic Gaussian SIFT matching strategy for sar registration［J］. IEEE Geoscience and Remote Sensing Letters，2015，12(1):160 -164.

［12］de Miranda P A V，F(xiàn)alc?o A X，Udupa J K. Synergistic arc-weight estimation for interactive image segmentation using graphs［J］.Computer Vision and Image Understanding，2010，114(1):85 -99.