基于文化粒子群的圖像配準優化算法

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

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

0 引言

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

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

1 基于互信息的圖像配準

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

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

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

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

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

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

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

2 文化粒子群優化算法

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

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

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

2.1 群體空間的設計

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

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

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

本文針對權重問題提出一種改進的動態慣性權重調整策略，慣性權重調整公式如下:

2.2 信念空間的設計

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

2.3 接受函數

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

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

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

2.4 更新信念空間

標準知識N 的更新規則如下:

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

2.5 影響函數

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

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

3 CPSO 在配準中的算法設計

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

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

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

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

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

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

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

步驟7 計算群體空間中各粒子的實際輸入和適應值函數。

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

步驟9 計算信念空間中粒子的實際輸入和適應值函數。

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

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

4 仿真與實驗分析

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

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

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

表1中給出3 種算法對圖2仿真得到指標比較。從表1可以看出，本文提出的方法在標準差、熵和互信息這些指標上優于其他方法，只是灰度均值比其他方法略差一點。圖3、圖4和圖5給出了實例中3 種算法執行后得到的誤差收斂曲線。很容易看出，使用PSO 算法搜索時，經過2.5 s 之后就能使搜索到的位置達到最優;使用IPSO 算法，經過1.5 s之后到達最優;使用本文方法，經過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

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

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

圖7 兩幅圖像的歸一化相關Fig.7 Normalized correlation of two images

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

5 結論

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

圖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 和綜合信息的醫學圖像配準新方法［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］柏連發，韓靜，張毅，等.采用改進梯度互信息和粒子群優化算法的紅外與可見光圖像配準算法［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 法結合的多分辨率三維圖像配準［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］尹丹艷，吳一全.灰色預測和混沌PSO 的紅外小目標檢測［J］.智能系統學報，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］朱霞. 一種求解作業車間調度的文化粒子群算法［J］.計算機應用研究，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，Fu 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，Falc?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.