基于改進粒子群算法的圖像匹配技術研究

馮 浩，李現偉

(1.宿州學院機械與電子工程學院，安徽宿州234000；2.早稻田大學國際情報通信研究科，東京169-8050)

基于改進粒子群算法的圖像匹配技術研究

馮 浩1，李現偉2

(1.宿州學院機械與電子工程學院，安徽宿州234000；2.早稻田大學國際情報通信研究科，東京169-8050)

在分析基本粒子群優化算法的基礎上，對學習因子進行非線性異步策略調整，改變其固定常數模式，平衡算法在迭代過程中的局部和全局搜索能力；同時引入活力因子，對失活粒子執行變異操作，提高種群多樣性。改進算法可以提升對多維空間的全局尋優能力，避免粒子產生早熟收斂現象。將改進粒子群算法引入圖像匹配優化問題中，提出了一種基于改進粒子群算法的圖像匹配算法，實驗結果表明，該算法具有更快的匹配速度以及更高的匹配精度，具有強魯棒性。

粒子群優化算法；圖像匹配；學習因子；活力因子

D01∶10.19329/j.cnki.1673-2928.2016.06.008

引言

隨著計算機技術的快速發展，圖像匹配技術日漸趨于成熟。作為圖像處理的重要技術之一，圖像匹配在目標識別、立體視覺、飛行器制導等領域得到較為廣泛的應用[1]。目前針對圖像匹配方法的研究主要集中于匹配精度、匹配速度以及匹配算法的抗干擾性能等方面。

在圖像匹配過程中，特征空間、搜索策略以及相似性度量是其關鍵的三個要素。針對不同要素選擇合適的匹配方法，有利于提高圖像匹配的效率。本文以灰度值作為圖像匹配特征，同時將模板匹配與粒子群優化(Particle Swarm Optimization，PSO)算法相結合，在研究改進PSO算法的基礎上，構建基準圖像與模板圖像之間的相似性度量數學模型，實現對目標圖像的精確匹配。實驗結果表明，改進的PSO算法提高了種群多樣性，具有更高的收斂精度和收斂速度，全局尋優能力突出。在此基礎之上，改進算法可以實現灰度圖像的快速匹配，其匹配精度、速度以及抗干擾性均優于對比算法。

1 粒子群優化(PSO)算法

PSO算法是由Kenndy博士和Eberhart博士于1995年提出，它是在研究鳥類群體覓食行為的基礎上所提出的一種群智能進化算法，該算法通過模仿鳥群覓食，利用群體協作和信息共享找到食物最優位置[2]。在PSO算法中，單個粒子代表搜索空間中的一個解，并且每個粒子都具有一定的飛行速度，則在D維空間中，假設種群大小為N，每個粒子的飛行速度可表示為vi=(vi1,vi2,···,vid)T，粒子的位置表示為xi=(xi1,xi2,···,xid)T，則第i個粒子根據式(1)、式(2)更新自身速度及位置[3]：

其中：i=1,2,···,N；d=1,2,···,D。w表示慣性權值，取值范圍為[0.4,0.9]；c1和c2表示學習因子，反映粒子個體極值和全局極值對下一狀態的影響；r1和r2為[0,1]之間的隨機數；k表示第k次迭代；在第k次迭代中，表示第i個粒子的飛行速度；表示第i個粒子的位置；表示第i個粒子的個體最優位置；則表示整個粒子群的全局最優位置。

2 改進粒子群優化算法

2.1 學習因子調整策略

由于基本PSO算法在迭代初期收斂速度較快，易產生早熟收斂現象，陷入局部極小，從而使得算法的收斂精度不高，全局尋優能力較差。因此，國內外大量研究學者對標準PSO算法做了改進和優化，如Shi等學者在文獻[4]中對慣性權值進行線性調節；Clerc等學者在文獻[5]中提出帶收縮因子的PSO算法；姜長元等人在文獻[6]中提出慣性權重正弦調整的粒子群算法；董平平等人在文獻[7]中提出一種改進的自適應慣性權值粒子群優化算法等等，上述算法在收斂性能指標上均有顯著提高。

大量實驗表明，學習因子的非線性變化可以

更好地解決各種非線性優化問題。本文在此基礎上對學習因子進行非線性異步調整，主要思想是：在算法迭代過程中，學習因子c1隨迭代次數的增加進行非線性遞減，而學習因子c2進行非線性異步遞增。通過調整，使得粒子在算法初期的自身調節能力增強，種群多樣性增加；而在算法后期，粒子的協作能力逐步提升，社會經驗增強，有利于進行全局最優搜索。調整后的學習因子數學模型如下式所示：其中，α(k)表示如下：

實驗證明，學習因子上下限在如下范圍內變化，算法的收斂速度以及精度可得到較大提升。

2.2 活力因子的引入

本文在構造學習因子策略模型的同時，對標準PSO算法作進一步改進。由PSO算法更新公式可知，當粒子當前位置逐步接近全局最優位置，即二者距離趨于零時，粒子的飛行速度逐漸減小并趨于零，此時粒子運動活力降低，產生停滯現象；反之，二者距離越大，粒子飛行速度也隨之加快。因此，可以通過對粒子當前位置進行變異操作來更好地控制粒子飛行速度，從而增加種群多樣性，使粒子能夠跳出局部極值。為此，引入粒子活力因子σ（σ≥0），通過選擇合適的σ，使得當粒子的當前位置與全局最優位置小于σ時，對當前位置執行變異操作，增強全局搜索能力。

在第k次迭代過程中，粒子i的當前位置xi(k)和全局最優位置pg(k)之間的距離定義為d(k)，其數學模型如下：

式（6）中，當d(k)＜σ時，粒子的飛行速度將會以較大概率產生停滯現象，造成算法的陷入局部極值，此時，對粒子i的當前位置xi(k)執行變異操作，改變粒子的飛行方向，通過初始化當前失活粒子的位置來增加種群多樣性，使粒子能夠以較大概率跳出局部最優。

3 基于AMPSO算法的圖像匹配

3.1 圖像的模板匹配

由于模板匹配方法具有運算簡單、抗干擾性能強的優點，已被廣泛應用于圖像匹配技術。如圖1所示，模板匹配即是在待匹配的基準圖像S中，搜索與模板T最為接近的目標子圖Si,j的位置。其中，S大小為M×N，模板T大小為X×Y，i,j為目標子圖左上角像素點在基準圖S中的坐標，i,j滿足1≤i≤M-X+1，1≤j≤N-Y+1。

圖1 基準圖和模板圖

本文將改進粒子群優化算法與模板匹配方法進行融合，則圖像的模板匹配可以轉化為運用PSO算法在二維空間中搜索最優匹配位置，基本流程如圖2所示。

圖2 基于AMPSO算法的圖像匹配流程圖

圖像的模板匹配算法較多，包括平均絕對差(Mean Absolute Difference，MAD)算法[8]、歸一化積相關(Normal Cross Correlation，NCC)算法[9]以及序貫相似性檢測法(Sequential Similarity Detection Algo?rithm，SSDA算法)[10]等。考慮到匹配速度以及實現難度問題，本文選用MAD算法作為改進PSO算法的適應度評價函數。其數學公式如下：

式（7）中，d(x,y)表示當偏移量為(x,y)時，所對應的匹配度量值，當d(x,y)取最小值時，可以得到最優匹配位置(x,y)。

綜合以上分析，將基于改進PSO算法的圖像匹配算法簡稱為AMPSO算法。

3.2 實驗仿真

在MATLAB7.0環境下進行實驗仿真，同時與傳統的模板匹配算法進行對比分析，包括MAD算法以及NCC算法。實驗選用Lena灰度圖像作為原始待匹配圖像，選取原始圖像大小254×254，待匹配模板大小為89×86，如圖3(a)和(b)所示。利用AMPSO算法對Lena原始圖像進行匹配，在無噪聲環境下，其最佳匹配結果如圖3(c)所示。

圖3 原始圖像、模板圖像以及匹配結果

在AMPSO算法中，慣性權值w選擇線性遞減策略，其中wmax=0.9，wmin=0.4；設定學習因子上下限分別為，調節系數λ=10；活力因子σ根據實驗情況以及經驗進行相應設置；設置種群大小為40，最大迭代次數M分別選擇30、40、50和60。實驗次數為50次。分別與MAD算法以及NCC算法在平均運行時間、正確匹配次數、最優匹配位置、最差匹配位置以及匹配精度指標上進行對比，如表1所示。

由表1可以看出，當最大迭代次數設置較小時，AMPSO算法的匹配精度無法達到100%，而當最大迭代次數大于50時，算法的匹配精度可以得到保證；對于MAD算法和NCC算法，二者匹配精度均可以達到100%，表明這兩種算法具有較高的匹配率。同時，可以看出AMPSO算法在平均運行時間指標上明顯優于MAD算法和NCC算法，特別是在保證匹配精度的前提下，AMPSO算法的平均運行時間大約是MAD算法的1/16，是NCC算法的1/32，匹配速度明顯占優。這也表明AMPSO算法具有快速收斂速度，同時，當選擇適當的種群大小以及最大迭代次數時，算法的全局搜索能力會更加突出，在保證匹配速度的同時，可以有效提升圖像的匹配精度。

為測試AMPSO算法的抗干擾性能，在圖3(a)中加入15%的椒鹽噪聲，利用AMPSO算法對加噪后的Lena圖像進行模板匹配，其最佳匹配結果如圖3(d)所示。大量實驗證明，在選擇合適的種群規模以及迭代次數的前提下，AMPSO算法可以實現對加噪圖像的精確匹配。

同時，實驗以加噪圖像作為基準圖像，在模板圖像保持不變的前提下，將AMPSO算法和MAD算法以及NCC算法進行圖像匹配對比分析。其中，AMPSO算法的種群大小選擇40，最大迭代次數選擇M=50，其他參數不變。實驗次數50次。實驗結果見表2所示。

表1 三種匹配算法的不同性能指標比較

表2 加噪環境下三種匹配算法的性能比較

由表2可知，在加噪環境下，AMPSO算法的匹配速度優勢明顯，耗時少。同時，AMPSO算法在匹配精度上也優于對比算法，可以精確找到模板圖像的匹配位置坐標，表現出較好的抗干擾性。

4 結束語

通過對基本PSO算法進行改進優化，改變學習因子的固定模式，實現其非線性異步變化，同時引入活力因子，增加種群多樣性，使算法有效跳出局部極值，在提升收斂速度的同時，增強全局尋優能力。將改進PSO算法引入圖像匹配技術中，實驗結果表明，改進PSO算法可以在保證匹配速度的前提下，實現對目標圖像的精確匹配，且抗干擾性能突出，具有強魯棒性，滿足實際應用中對匹配速度和匹配精度的要求，在圖像匹配問題優化方面具有一定的實際指導意義。

[1]劉佳，傅衛平，王雯，等.基于改進SIFT算法的圖像匹配[J].儀器儀表學報，2013（05）∶1107-1112.

[2]VANDEN BERGH F,ENGELBRECHT A P.Training Prod?uct Unit Networks Using Cooperative Particle Swarm Optimiza?tion[C]//IEEE International Joint Conference on Neural Net?works,Washington DC,USA,2001∶126-131.

[3]KENNEDY J,EBERHART R.Particle swarm optimization [C]//Proceedings of the 4th IEEE International Conference on NeuralNetworks.Piscataway,NJ∶IEEE ServiceCenter,1995∶1942-1948.

[4]SHI Y,EBERHART R.Empirical study of particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolu?tionary Computation,Piscataway,NJ∶IEEE press,1999∶1945-1950.

[5]CLERC M.The swarm and the queen∶towards a determin?stic and adaptive particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscat?away,NJ∶IEEE Service Center,1999∶1951-1957.

[6]姜長遠，趙曙光，沈士根.慣性權值正弦調整的粒子群算法[J].計算機工程與應用，2012，48（8）∶40-42.

[7]董平平，高東慧,田羽波.一種改進的自適應慣性權值粒子群優化算法[J].計算機仿真，2012，29（12）∶283-286.

[8]劉寶生，閆莉萍，周東華.幾種經典相似性度量的比較研究[J].計算機應用研究，2006（11）∶1-3.

[9]楊通鈺，彭國華.基于NCC的圖像匹配快速算法[J].現代電子技術，2010（22）∶107-109.

[10]王杉，陳翔，司寒羽.基于遙感圖像信息特征的單調遞增SSDA算法[J].華東交通大學學報，2013（01）∶15-21.

Image Matching Technology Based on Improved Particle Swarm Optimization Algorithm

FENG Hao1,LI Xianwei2
(1.Colloge of Mechanical and Electronic Engineering,Suzhou University,Suzhou AnHui 234000,China; 2.Global Information and Telecommunication Institute,Waseda University,Tokyo,169-8050,Japan)

Based on the analysis of the basic particle swarm optimization algorithm,the thesis adjusted the learn?ing factor by the strategy of nonlinear asynchronous,changed the model of fixed constant,and balanced the global and local search ability in the process of iteration;simultaneously the thesis introduced the activity factor to im?prove the population diversity which performed mutation for the particles who lost energy.The improved algorithm can improve the global search capability in the multidimensional space,and avoided premature convergence phe?nomenon.The improved particle swarm algorithm was introduced into image matching optimization problem,and proposed an image matching algorithm based on the improved particle swarm algorithm,the experimental results showed that The algorithm has the advantages of faster matching speed and higher matching accuracy,and has strong robustness.

particle swarm optimization algorithm;image matching;learning factor;activity factor

TP391

A

1673-2928（2016）06-0022-04

（責任編輯：郝安林）

2016-03-20

宿州學院一般科研項目(2014yyb03)、宿州學院科研平臺開發課題(2014YKF44)。

馮浩(1983-)，男，河南安陽人，宿州學院講師，碩士，主要研究方向：圖像處理、智能算法。