基于PSO算法圖像匹配技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、行和列的設(shè)定p_speed=zeros(p_num，p_dim); % 先設(shè)定一個(gè)空的矩陣，來(lái)放置粒子當(dāng)前速度信息，注意行和列的設(shè)定for k_ini=1:p_num % 范圍最大值為粒子的個(gè)數(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之間的隨機(jī)均勻分布的數(shù)據(jù) p_speed(k_ini，:)=round(-10+20*rand(1，p_dim); % 初始化速度，位于-10到1

19、0之間的隨機(jī)均勻分布的數(shù)據(jù)end%-計(jì)算初始化粒子的最優(yōu)值數(shù)據(jù)-p_local_position=p_position; % 初始化后，各個(gè)粒子當(dāng)前初始化的位置為各自記憶最優(yōu)位置% p_local_position中為各個(gè)粒子的歷史記憶最優(yōu)位置p_local_value=zeros(1，p_num); % 各個(gè)粒子的記憶最優(yōu)位置的最優(yōu)值for k1=1:p_num % 尋找初始化后，當(dāng)前全局最優(yōu)粒子（本例是求最大值） % p_local_value(k1)=compute_fit(p_position(k1，:)，p_dim); % 計(jì)算各個(gè)粒子當(dāng)前的適應(yīng)度函數(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)計(jì)算各個(gè)粒子當(dāng)前的適應(yīng)度函數(shù)值 % p_local_value為保存各個(gè)粒子適應(yīng)度函數(shù)數(shù)據(jù)endp_global_value=p_local_value(1); % 先假定第一個(gè)粒子擁有當(dāng)前初始化全局最優(yōu)值p_global_position=p_position(1，:); % 即

21、假定第一個(gè)粒子為當(dāng)前初始化全局最優(yōu)粒子位置for k2=1:p_num % 尋找初始化后，當(dāng)前全局最優(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%-中心主程序-%-更新粒子位置和速度，通過(guò)判斷條件，找出全局最優(yōu)值-% while expression% statements% endflag_stop=0; % 迭代結(jié)束的標(biāo)志k_iter=

22、0; % 迭代的次數(shù)初始化while flag_stop=0 % 判斷迭代標(biāo)志，是否循環(huán) %-更新速度和位置信息- w=w_max-0.6*k_iter/p_iter; % 更新慣性權(quán)重值 % 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)+. % 粒子的自身學(xué)習(xí) (c2*rand(1).*(p_global_position(kd)-p_position(kn，kd); % 粒子的社會(huì)全局學(xué)習(xí) 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