基于PSO算法圖像匹配技術

1、東 北 大 學研 究 生 考 試 試 卷評分考試科目： 人工神經(jīng)網(wǎng)絡的模型與算法 課程編號： 閱 卷 人： 考試日期： 姓 名： 學 號： 注 意 事 項1考 前 研 究 生 將 上 述 項 目 填 寫 清 楚2字 跡 要 清 楚，保 持 卷 面 清 潔3交 卷 時 請 將 本 試 卷 和 題 簽 一 起 上 交東北大學研究生院基于PSO算法的圖像匹配技術摘 要：圖像匹配問題是圖像處理中的一個經(jīng)典問題，在計算機視覺、模式識別和醫(yī)學圖像處理等方面有著廣泛的應用。本文主要介紹了在基于灰度圖像匹配算法基礎上，以匹配相似性度量函數(shù)為判斷標準，結合智能算法中的粒子群算法來實現(xiàn)圖像準確而快速的匹配。關鍵詞

2、：圖像匹配；相似性度量；粒子群算法；離散空間1 引言數(shù)字圖像配準是指將從同一場景拍攝的具有重疊區(qū)域的圖像通過特征匹配方法，找出圖像之間的對應關系。目前，圖像配準技術廣泛應用于醫(yī)學、生物、信息處理和其它領域，它已成為圖像處理應用中不可或缺的技術。圖像匹配問題主要有兩種對應的問題模型:一是兩幅(或者多幅)來自不同傳感器、不同視角或不同時間的圖像需找出對應關系，經(jīng)過匹配步驟可得出兩幅圖像的差別所在，為下一步處理作基礎；二是根據(jù)已知的圖像模式在另一幅圖像中搜索類似模板的目標。圖像匹配技術是數(shù)字圖像處理領域的一項重要研究，已在計算機視覺、虛擬現(xiàn)實場景、航空航天遙感測量、醫(yī)學影像分析、光學和雷達跟蹤等領域

3、有著重要的應用價值。大體圖像匹配的應用領域概括起來主要有以下幾個方面:1.計算機視覺和模式識別。包括圖像分割、物體識別、形狀重建、運動跟蹤和特征識別。2.醫(yī)學圖像分析。包括醫(yī)學成像信息診斷，生物醫(yī)學信號處理等。3.遙感信息處理。包括特定目標的定位和識別等。隨著科學技術的發(fā)展，圖像匹配技術在近代信息處理領域中的應用范圍越來越廣泛，而圖像數(shù)據(jù)量龐大這一顯著特點，嚴重制約了圖像匹配技術的實時應用。圖像匹配的準確性和實時性是現(xiàn)今在具體應用上存在的一對矛盾體，如何在保持匹配準確性的同時，提高其匹配速度是現(xiàn)階段急需解決的問題，也是目前對匹配算法的研究重點。在序列目標圖像分析、跟蹤、識別，工業(yè)實時檢測等實際

4、應用中，一般是根據(jù)已知的圖像模式，然后在另一幅圖像中搜索類似模板的目標。2 圖像匹配說明2.1圖像匹配流程圖像匹配是一個多步驟過程，總的來說，大概可分為圖像輸入、圖像預處理、匹配有用信息提取、圖像匹配、輸出結果等。由于所采用的方法各異，不同的匹配算法之間步驟也會有很大不同，但它們的大致過程是相同的。圖像匹配流程圖如圖2.1所示：圖2.1 圖像匹配流程圖2.2 基于灰度的圖像匹配算法國內外現(xiàn)階段對圖像匹配研究主要是以提高匹配的精度和速度為主，同時對匹配方法的通用性及魯棒性也有一定要求。圖像匹配方法大致可分為兩類:第一類是基于灰度的圖像匹配算法;第二類是基于特征的圖像匹配算法。本文主要講述第一類基

5、于灰度的圖像匹配算法。這類方法直接利用圖像的灰度信息進行匹配，通過象素對之間某種相似性度量(如相關函數(shù)、協(xié)方差函數(shù)、差平方和、差絕對值和等)的全局最優(yōu)化實現(xiàn)匹配，不需進行圖像分割和圖像特征提取，因而可以避免由這些預處理所造成的精度損失。這類匹配方法需要解決的問題是:匹配速度比較慢，對灰度信息變化、光照變化、噪聲非常敏感，沒有充分利用灰度統(tǒng)計特性，對每一點的灰度信息依賴較大，不適應于匹配對象存在旋轉和縮放情況下的匹配問題。本節(jié)這里主要利用了基于灰度的圖像匹配算法中較為簡單的MAD算法，并結合智能算法中的粒子群算法的尋優(yōu)優(yōu)勢，從而實現(xiàn)了較為快速而準確的圖像匹配。MAD算法即平均絕對差算法，是Lee

6、se最早提出來的一種匹配算法。原理如圖2.2所示：子圖Sxy基準圖SNM實時圖T圖2.2 平均絕對差算法原理圖基于灰度的MAD算法匹配方法函數(shù)公式可定義為：其中d(x，y)為相似性度量函數(shù)在偏移量為(x，y)時的匹配度量值。由公式可以看出，當d(x，y)取值最小時認為(x，y)是最佳匹配位置。3 算法圖像匹配3.1 算法簡介粒子群優(yōu)化算法(PSO)是一種進化計算技術，1995年由Eberhart博士和kennedy博士提出，源于對鳥群捕食的行為研究。該算法最初是受到飛鳥集群活動的規(guī)律性啟發(fā)，進而利用群體智能建立的一個簡化模型。粒子群算法在對動物集群活動行為觀察基礎上，利用群體中的個體對信息的共

7、享使整個群體的運動在問題求解空間中產(chǎn)生從無序到有序的演化過程，從而獲得最優(yōu)解。PSO算法從這種模型中得到啟示并用于解決優(yōu)化問題。PSO算法中，每個粒子表示空間中的一個解。所有的粒子都有一個由適應度函數(shù)決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。PSO算法初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解叫做個體極值pbest。另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值gbest。粒子群算法的速度和

8、位置迭代公式為：其中：，為每個粒子的速度和位置。pbesti，gbest如前所述。rand()表示（0，1）之間的均勻隨機數(shù)據(jù)。，為學習因子，w稱為慣性權值，和為正常數(shù)，稱為學習因子，它們的具體含義為：1.慣性權值w保持粒子原有飛行速度的系數(shù)，控制粒子飛行速度變化，通過w調節(jié)PSO算法的全局與局部尋優(yōu)能力。當w取值較大時，粒子飛行速度變化幅度較大，全局尋優(yōu)能力強，局部尋優(yōu)能力弱;反之當w取值較小時局部尋優(yōu)能力強，全局尋優(yōu)能力弱。選擇一個合適的w可以平衡全局和局部搜索能力，這樣可以以最少的迭代次數(shù)找到最優(yōu)解，這是因為開始較大的慣性權重可以遍歷比較大的范圍，后來小的權重有較好的局部搜索能力。2.學

9、習因子和代表了粒子向自身歷史最優(yōu)值和全局最優(yōu)值推進的隨機學習權值，的大小標志著粒子的認知能力。當=0，粒子沒有認知能力，只受“社會知識”影響，在粒子間相互影響下，有能力達到新的搜索空間，收斂速度比標準算法快，但碰到復雜問題比標準算法更容易陷入局部極值。的大小標志著粒子的社會信息交換共享能力，當=0時，沒有社會信息共享，只有“自身認知”的能力。由于粒子之間沒有信息交互，等價于眾多單個粒子的飛行，因而得到最優(yōu)解的概率很小。如果=0，說明粒子以當前速度飛行，直到邊界。為了確定和對算法性能的影響，Kennedy對以下4種模型做了大量的計算：（1）認知模型，=0;（2）社會模型，=0；（3）完全模型，=

10、；（4）無私模型，也是一種社會模型，唯一不同的是，無私模型中每一個粒子獲取自身歷史最優(yōu)值時只考慮其他粒子的信息而不包括自己。認知模型只考慮粒子自身的信息，而沒有與社會信息的交流和共享，Kennedy計算后發(fā)現(xiàn)該模型收斂速度比較慢;社會模型只考慮社會因素，傾向于向社會學習，收斂速度比較快，但容易早熟。同時，為了平衡群體因素和個體因素的影響，普遍認為和取值為2效果較好，不過在文獻中也有其它的取值，但是一般=并且范圍在0和4之間。3.2 算法圖像匹配流程本文主要是用PSO算法實現(xiàn)快速圖像匹配，主要是用基于灰度的MAD算法匹配方法函數(shù)作為適應度函數(shù)的判斷標準，在數(shù)字圖像二維離散空間快速尋優(yōu)，找到適應度

11、函數(shù)具有最優(yōu)值所對應的位置，此位置就是匹配的結果，從而實現(xiàn)圖像匹配。由于PSO算法的智能性和快速收斂性，所以參數(shù)設置合理，就可以實現(xiàn)快速而準確的圖像匹配。匹配程序的流程圖如圖3.1所示。圖3.1 PSO算法圖像匹配的程序流程圖3.3 算法的參數(shù)設置參數(shù)設置及粒子尋優(yōu)過程設計說明：若基準圖的大小為M行N列，實時圖的大小為S行J列，則粒子一維方向的位置范圍為1，M-S+1，二維方向的位置范圍為1，N-J+1。粒子位置和速度的多樣化適于粒子在全局搜索解，盡可能地發(fā)揮算法的搜索能力，否則很可能漏掉最優(yōu)解，而使算法找到次優(yōu)解。所以粒子群的初始化位置為1：M-S+1，1：N-J+1范圍內的均勻分布的隨機數(shù)

12、據(jù)。當粒子超出最大位置時，將粒子所在維度設置為最大位置。粒子最大速度的選擇通常憑經(jīng)驗給定，一般設置為粒子范圍寬度的10%-20%，根據(jù)實際情況和多次試驗的結果，所以粒子兩個維度的最大速度均設置為10。所以粒子群的初始化位置為-10：10，-10：10的均勻分布的隨機數(shù)據(jù)。學習因子和均設置為2。大的慣性因子w可以使算法不易陷入局部最優(yōu)，到算法后期，小的慣性因子可以使收斂速度加快，使收斂更加平穩(wěn)，時變權重可以在某一個范圍內變化，一般在迭代過程中按照某種規(guī)律遞減。在本文中，粒子慣性權重w最大值為1，最小值為0.4，迭代過程中粒子權重隨著迭代次數(shù)線性遞減。4 實驗結果及展望4.1實驗結果圖像匹配結果如

13、下：輸入的基準圖像和實時圖像為：圖4.1 輸入的基準圖像圖4.2 輸入的實時圖像程序運行輸出的結果為：圖4.3 輸出的PSO尋優(yōu)匹配結果本文對該算法的匹配率進行了試驗：共進行了30次試驗，成功匹配29次，匹配成功率96.67%，達到了較好的匹配準確率。本文也對本算法和全遍歷法在模板匹配次數(shù)和時間效率上進行了試驗測試。結果如表1所示。表1 本算法和全遍歷算法比較算法全遍歷法PSO算法運行時間0.62s0.51s模板匹配次數(shù)121*121=1464160*120=7200實驗中發(fā)現(xiàn)群體數(shù)目不易過大或過小。過大，PSO 算法的優(yōu)化性能得不到體現(xiàn)；過小，有可能會出現(xiàn)所求得的最優(yōu)解的精度達不到要求。迭代

14、次數(shù)亦是如此，次數(shù)過多會加大運算量，降低算法的效率，過少，可能會導致最終解的精度不夠。在上述實驗圖像和環(huán)境下，經(jīng)過多次實驗后，發(fā)現(xiàn)群體數(shù)在60左右，迭代次數(shù)在120次左右時，能得到較滿意的結果。理論上講，圖像匹配問題按上述實驗圖像的情況，其計算量為（M-S+1）（N-J+1）=14641次模板匹配計算，而PSO算法則只需要（群體數(shù)目迭代次數(shù)）次模板匹配計算，在實驗中群體數(shù)為60，迭代次數(shù)為120，所以模板匹配計算的次數(shù)為7200次。同時時間效率上也要優(yōu)于全遍歷法，而且這種優(yōu)勢在需要遍歷位置更多時，會表現(xiàn)得更加明顯。4.2 展望為更加減少計算量，提高算法的效率，本算法有如下改進方向。1.進一步優(yōu)

15、化參數(shù)，在保證匹配率的前提下，降低粒子數(shù)和迭代次數(shù)。2.優(yōu)化PSO算法，例如引入收縮因子，并將速度的限制放寬、將學習因子、采取自適應時變調整策略。3.粒子群算法與其它智能算法的融合。在基本PSO算法中加入禁忌(Tabu)算法，將基本PSO和遺傳算法相結合，進一步提出雜交PSO。5參考文獻1 紀震，廖惠連，吳青華.粒子群算法及應用M，科學出版社，2009.012 江銘炎，袁東風.人工魚群算法及其應用M，科學出版社，2012.013 劉錦峰.圖像模板匹配快速算法研究D.中南大學.碩士學位論文.2007.054 何志明.群體智能算法在圖像匹配中的應用D.陜西師范大學.碩士學位論文.2010.055

16、李小林.混合粒子群優(yōu)化算法及其在圖像匹配中的應用研究D。西安電子科技大學.碩士學位論文.2010.66 鹿艷晶，馬 苗.基于灰色粒子群優(yōu)化的快速圖像匹配算法J.計算機工程與應用.2009.45(10).7 王維真，熊義軍，魏開平，何文雅.基于粒子群算法的灰度相關圖像匹配技術.2010.46.(12).附錄在此附上pso算法的源碼，遍歷法以及截取實時圖像的源碼詳見程序文件夾。%-本程序目的是用pso算法來對圖像進行匹配-tic%-界面變量清理-close allclearclc%-讀取圖片信息-f=imread(lena_basic.jpg);row1，colu1=size(f);t=imrea

17、d(lena_time.jpg);row2，colu2=size(t);%-參數(shù)設置-w_max=1; % 慣性權重最大值w_min=0.4; % 慣性權重最小值p_num=60; % 粒子規(guī)模數(shù)量p_dim=2; % 粒子維數(shù)c1=2;c2=2; % 學習因子v_max=10; % 速度上限v_min=-10;% 速度下限p_iter=120; % 迭代最大次數(shù)次數(shù)設定p_position_min=1;p_position_max=row1-row2+1;%-初始化，位置和速度-p_position=zeros(p_num，p_dim); % 先設定一個空的矩陣，來放置粒子當前位置信息，注意

18、行和列的設定p_speed=zeros(p_num，p_dim); % 先設定一個空的矩陣，來放置粒子當前速度信息，注意行和列的設定for k_ini=1:p_num % 范圍最大值為粒子的個數(shù) p_position(k_ini，:)=round(p_position_min+. (p_position_max-p_position_min)*rand(1，p_dim); % 初始化位置，位于p_position_min到p_position_max之間的隨機均勻分布的數(shù)據(jù) p_speed(k_ini，:)=round(-10+20*rand(1，p_dim); % 初始化速度，位于-10到1

19、0之間的隨機均勻分布的數(shù)據(jù)end%-計算初始化粒子的最優(yōu)值數(shù)據(jù)-p_local_position=p_position; % 初始化后，各個粒子當前初始化的位置為各自記憶最優(yōu)位置% p_local_position中為各個粒子的歷史記憶最優(yōu)位置p_local_value=zeros(1，p_num); % 各個粒子的記憶最優(yōu)位置的最優(yōu)值for k1=1:p_num % 尋找初始化后，當前全局最優(yōu)粒子（本例是求最大值） % p_local_value(k1)=compute_fit(p_position(k1，:)，p_dim); % 計算各個粒子當前的適應度函數(shù)值 temp=p_positio

20、n(k1，:); f_temp1=f(temp(1):temp(1)+row2-1，temp(2):temp(2)+colu2-1); f_temp2=abs(f_temp1-t); p_local_value(k1)=sum(sum(f_temp2)/(row2*colu2);% p_local_value(k1)計算各個粒子當前的適應度函數(shù)值 % p_local_value為保存各個粒子適應度函數(shù)數(shù)據(jù)endp_global_value=p_local_value(1); % 先假定第一個粒子擁有當前初始化全局最優(yōu)值p_global_position=p_position(1，:); % 即

21、假定第一個粒子為當前初始化全局最優(yōu)粒子位置for k2=1:p_num % 尋找初始化后，當前全局最優(yōu)粒子 if p_global_value=p_local_value(k2) %*判斷條件* p_global_value=p_local_value(k2); % 更新全局最優(yōu)值信息 p_global_position=p_position(k2，:); % 更新全局最優(yōu)粒子位置信息 endend%-中心主程序-%-更新粒子位置和速度，通過判斷條件，找出全局最優(yōu)值-% while expression% statements% endflag_stop=0; % 迭代結束的標志k_iter=

22、0; % 迭代的次數(shù)初始化while flag_stop=0 % 判斷迭代標志，是否循環(huán) %-更新速度和位置信息- w=w_max-0.6*k_iter/p_iter; % 更新慣性權重值 % tic for kd=1:p_dim for kn=1:p_num p_speed(kn，kd)=round(w.*p_speed(kn，kd)+. % 粒子自身速度 (c1*rand(1).*(p_local_position(kn，kd)-p_position(kn，kd)+. % 粒子的自身學習 (c2*rand(1).*(p_global_position(kd)-p_position(kn，kd); % 粒子的社會全局學習 if p_speed(kn，kd)v_max % 最大速度制約 p_speed(kn，kd)=v_max; end if p_speed(kn，kd)v_min % 最大速度制約 p_speed(kn，kd)=v_min; end p_position(kn，kd)=round(p_position(kn，kd)+p_speed(kn，kd); % 更新粒子的位置 if p_position(kn，kd)p_position_max % 最大位置制約 p_position(kn，kd)=p_position_max; end end