基于DCT變換和雞群優(yōu)化算法的圖像匹配*

彭 健 曹中清

（西南交通大學(xué)機(jī)械工程學(xué)院 成都 610031）

1 引言

作為計(jì)算機(jī)視覺和數(shù)字圖像處理的重要組成部分，圖像匹配在醫(yī)療診斷、圖像檢索、圖像融合、人工智能等領(lǐng)域都有非常廣泛的運(yùn)用。圖像匹配可以檢測出在待匹配的大圖像中是否有和模板圖像相同的區(qū)域，并確定相同區(qū)域在大圖像中的位置［1］。圖像匹配分為以灰度為基礎(chǔ)和以特征為基礎(chǔ)的匹配。前者直接根據(jù)圖像的灰度，利用某種相似性度量比如差平方和、差絕對(duì)值等進(jìn)行匹配。這類方法算法簡單，匹配準(zhǔn)確率高，但缺陷是容易受旋轉(zhuǎn)、光線、視角等因素的影響［2］。后者則需要先提取圖像的點(diǎn)線面等特征，將特征進(jìn)行參數(shù)化描述，再利用參數(shù)進(jìn)行圖像匹配。這類方法計(jì)算量相對(duì)較小，適應(yīng)性較好，可以用于灰度變化、形變及有遮擋等場合，但缺陷是匹配精度不高、魯棒性較差［3～4］。然而，這兩類方法采用的都是遍歷式的搜索策略，匹配效率不高。為了改善這一問題，一些學(xué)者嘗試將群智能算法用于圖像匹配。群智能算法為非遍歷式搜索，在減少圖像匹配計(jì)算量的同時(shí)，還兼具較好的魯棒性。文獻(xiàn)［5］使用粒子群算法搜索圖像中與模板像素值差異最小的區(qū)域，這種方法簡單效果好，但是使用像素灰度值作為適應(yīng)度函數(shù)易受到噪聲的干擾。文獻(xiàn)［6］將灰色關(guān)聯(lián)度與粒子群算法相結(jié)合，具有一定的抗干擾性，但是快速性和準(zhǔn)確性不可兼得，需要設(shè)置合適的參數(shù)來平衡兩者之間的關(guān)系。文獻(xiàn)［7］使用Hausdorff距離作為適應(yīng)度函數(shù)，并使用人工蜂群算法進(jìn)行搜索。這種方法收斂時(shí)間短，但是在計(jì)算Hausdorff距離時(shí)容易受噪聲影響。

雞群優(yōu)化算法是一種新型的群智能算法［8］，具有收斂速度快和收斂精度高的特點(diǎn)，在許多優(yōu)化問題的求解上有較好表現(xiàn)［9～10］。本文提出了一種基于雞群優(yōu)化算法的圖像匹配方法，通過DCT變換構(gòu)造適應(yīng)度函數(shù)。DCT變換常用于圖像壓縮領(lǐng)域［11］，具有去噪和魯棒性好的特點(diǎn)。之后，本文設(shè)置仿真實(shí)驗(yàn)，將本文方法、序貫相似性檢測算法、DCT變換與粒子群算法［12］結(jié)合的方法、DCT變換與人工蜂群算法［13］結(jié)合的方法，這四種方法的結(jié)果進(jìn)行比對(duì)，結(jié)果表明，本文方法具有匹配準(zhǔn)確率高，算法收斂速度快，可靠性好的優(yōu)點(diǎn)，為圖像匹配領(lǐng)域的研究提供了更多的參考依據(jù)。

2 DCT變換

離散余弦變換（Discrete Cosine Transform，DCT）是從離散傅里葉變換（DFT）發(fā)展過來的，它利用了傅里葉變換的對(duì)稱性，變換后的結(jié)果只包含余弦項(xiàng)。二維離散余弦變換定義為［14］

二維離散余弦變換的變換矩陣具有以下幾點(diǎn)特性［15］。

1）變換后矩陣的能量主要集中在其左上角的位置，包含了原始圖像的直流成分和低頻成分，是圖像的主要相關(guān)信息，而噪聲干擾等高頻信號(hào)則分布在矩陣的右下角。并且矩陣的各個(gè)元素是不相關(guān)的。

2）矩陣穩(wěn)定具有抗干擾性，圖像受到較小干擾時(shí)，矩陣中的元素尤其是左上角的元素變化不會(huì)大。

如果適當(dāng)?shù)厣釛壱恍└哳l信息并且保留低頻信息，那么將可以抑制圖像中的噪聲信號(hào)，并且還能使圖像去噪前后的DCT變換矩陣具有相似的系數(shù)，這也是后期匹配識(shí)別的主要依據(jù)。

3 雞群優(yōu)化算法

雞群優(yōu)化算法（Chiken Swarm Optimization，CSO）是Meng Xianbing等于2014年提出的一類基于群體智能的隨機(jī)優(yōu)化算法［8］。這種算法模擬了雞群的等級(jí)制度和群體行為，將整個(gè)雞群劃分為公雞、母雞和小雞三個(gè)群體，每個(gè)群體按照各自的行為規(guī)律進(jìn)行更新，母雞跟隨公雞、小雞跟隨母雞的關(guān)系保持?jǐn)?shù)代不變，經(jīng)過雞群若干代的進(jìn)化更新，最終得到最優(yōu)解。

3.1 適應(yīng)度函數(shù)

合適的適應(yīng)度函數(shù)對(duì)圖像匹配的結(jié)果起到至關(guān)重要的作用，前文提到，使用像素值和Hausdorff距離作為適應(yīng)度函數(shù)都容易受到噪聲的影響，于是本文將常用于圖像壓縮的DCT變換用于圖像匹配中作為適應(yīng)度函數(shù)。

設(shè)灰度圖像模板I的尺寸為m×n，待搜索的灰度圖像尺寸為M×N，要從中搜尋與模板I匹配的圖像 J。令圖像 J的左上角頂點(diǎn)坐標(biāo)為（x0，y0），x0、y0滿足 x0∈［1，M-m+1］，y0∈［1，N-n+1］，圖像J的另外3個(gè)頂點(diǎn)為（x0+m-1，y0），（x0，y0+n-1），（x0+m-1，y0+n-1）。分別對(duì)圖像I和圖像J作DCT變換得到矩陣I'和矩陣J'。出于減少計(jì)算量的考慮，而且DCT矩陣的左上角已經(jīng)包含了圖像的主要信息，于是選取I'和J'左上角h×k的矩陣，采用歸一化相關(guān)衡量兩個(gè)矩陣的相似度，得到點(diǎn)（x0，y0）的適應(yīng)度函數(shù)值f（x0，y0）的數(shù)學(xué)表達(dá)式，如下：

值得說明的是，公式中x和y是代表矩陣中第x行和第y列，和x0、y0的坐標(biāo)意義正好相反。適應(yīng)度函數(shù)的值越大，說明圖像J與模板I的匹配程度越高。在本文的雞群優(yōu)化算法中，將適應(yīng)度值按從大到小的順序排序，以適應(yīng)度函數(shù)最大的值作為雞群中最優(yōu)的個(gè)體，最后輸出最優(yōu)個(gè)體。

3.2 基于混沌系統(tǒng)的種群初始化

設(shè)雞群個(gè)體的總數(shù)量為popsize，雞群中第i個(gè)個(gè)體的位置矢量由在圖像中的橫坐標(biāo)和縱坐標(biāo)兩個(gè)參數(shù)構(gòu)成，例如，第i只雞在第t次迭代時(shí)的位置為雞群初始化的質(zhì)量對(duì)于算法的收斂速度及尋優(yōu)精度有較大影響，如何生成隨機(jī)性和遍歷性好的雞群是需要關(guān)心的重點(diǎn)。

混沌現(xiàn)象是非線性動(dòng)力映射的復(fù)雜動(dòng)力學(xué)主要表現(xiàn)形式之一，具有良好的類隨機(jī)、非周期、對(duì)初始值敏感、遍歷性、可確定性等特性。目前常用的有Logistic混沌映射和Chebyshev混沌映射，然而Logistic混沌系統(tǒng)產(chǎn)生的序列均勻與否與參數(shù)選取有關(guān)，Chebyshev混沌系統(tǒng)產(chǎn)生的序列在區(qū)間中間分布均勻而在區(qū)間兩端分布稠密。為了吸收兩者的優(yōu)點(diǎn)，克服兩者的缺點(diǎn)，本文采用文獻(xiàn)［16］提出的一種Logistic和Chebyshev混合的改進(jìn)混沌系統(tǒng)的方法，相關(guān)的實(shí)驗(yàn)表明產(chǎn)生的混沌序列在（-1，1）內(nèi)具有更均勻、更良好的散亂和擴(kuò)散效果。

首先構(gòu)造Logistic和Chebyshev初始函數(shù)，隨機(jī)給定初始值u1，v1∈（-1，1）。

3.3 雞群優(yōu)化算法

雞群優(yōu)化算法的公雞的位置更新公式如下：

式中，rand為服從［0，1］上均勻分布的隨機(jī)數(shù)，eps為一個(gè)非常小的正數(shù)，a1為第i只母雞跟隨的公雞，a2為母雞中隨機(jī)抽取的個(gè)體，且a2≠i。

小雞的位置更新公式如下：

式中，a3為第i只小雞跟隨的母雞，a4為母雞a3跟隨的公雞，C3和C4是服從［0，2］上均勻分布的隨機(jī)數(shù)，ω為慣性權(quán)重系數(shù)，它按照以下的公式計(jì)算［17］：

其中，t為當(dāng)前迭代次數(shù)，max gen為最大迭代次數(shù)。慣性權(quán)重ω可以影響雞群算法的局部最優(yōu)能力和全局最優(yōu)能力。較大的ω有利于提高雞群算法的全局搜索能力，而較小的ω會(huì)增強(qiáng)算法的局部搜索能力［18］。ω會(huì)隨著迭代次數(shù)的增加逐漸減小，使得小雞一開始能一開始能跳出局部最小點(diǎn)，而隨著迭代次數(shù)的增加，小雞可以在當(dāng)前的搜索區(qū)域進(jìn)行精確的局部搜索，有利于算法的收斂。

3.4 算法流程

本文雞群算法的步驟如下：

輸入：模板圖像

輸出：與匹配的圖像以及圖像左上角的坐標(biāo)位置。

步驟1.使用混沌系統(tǒng)初始化雞群，設(shè)置相關(guān)參數(shù)，包括最大迭代次數(shù)max gen、雞群規(guī)模popsize、雞群角色更新次數(shù)G、公雞數(shù)量比例rpercent、母雞數(shù)量比例hpercent、小雞數(shù)量比例cpercent等參數(shù)。

步驟2.計(jì)算雞群中所有雞的適應(yīng)度函數(shù)值。

步驟3.判斷雞群角色的更新條件：當(dāng)t==1或者mod（t，G）==0時(shí)，執(zhí)行步驟4，否則執(zhí)行步驟5，其中t代表當(dāng)前迭代次數(shù)。

步驟4.將雞群的適應(yīng)度值按照從小到大的順序排序，并記錄適應(yīng)度最優(yōu)的值與個(gè)體。依據(jù)排序確定公雞、母雞和小雞角色，并為每只母雞生成一個(gè)標(biāo)號(hào)，標(biāo)號(hào)代表要跟隨的公雞；為每只小雞生成一個(gè)標(biāo)號(hào)，標(biāo)號(hào)代表要跟隨的母雞。

步驟5.依照上文介紹的公雞、母雞和小雞的更新公式對(duì)其進(jìn)行位置更新，并計(jì)算它們的適應(yīng)度值，然后記錄雞群中最優(yōu)的適應(yīng)度值和最優(yōu)的個(gè)體位置。

步驟6.不斷重復(fù)步驟3～步驟5，直到達(dá)到規(guī)定的最大迭代次數(shù)為止，輸出最優(yōu)位置和匹配圖像，完成匹配搜索。

4 實(shí)驗(yàn)結(jié)果分析

本文將對(duì)序貫相似性檢測算法（SSDA）、DCT變換與雞群優(yōu)化算法結(jié)合（DCSO）、DCT變換與粒子群算法結(jié)合（DPSO）、DCT變換與人工蜂群算法結(jié)合（DABC）這四種方法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)使用了四張圖像，包含兩張經(jīng)典圖像、一張衛(wèi)星圖像、一張紅外圖像；圖像畸變類型分別有原圖、加入強(qiáng)度0.1的椒鹽噪聲、逆時(shí)針旋轉(zhuǎn)3°、灰度減弱25%四種類型。

相關(guān)實(shí)驗(yàn)參數(shù)：SSDA中閾值和最小累計(jì)誤差設(shè)為2×105。DCT矩陣選擇選擇左上角0.5m*0.5n大小的矩陣，其中m、n為模板的長和寬。雞群優(yōu)化算法中，種群數(shù)量為60，迭代次數(shù)100次，公雞比例0.2，母雞比例0.4，小計(jì)比例0.4，雞群角色更新代數(shù)G為10，慣性權(quán)重ωmax=0.9，ωmin=0.4。粒子群算法中，種群數(shù)目為60，迭代次數(shù)100次，粒子最大飛行速度為100像素，C1=C2=1.49445。人工蜂群算法中雇傭蜂和非雇傭蜂的數(shù)量都為60，迭代次數(shù)100次，每只蜂的試驗(yàn)次數(shù)上限為6。

首先，本文提出的方法DCSO在4副圖像上的4類畸變狀態(tài)下的匹配結(jié)果如圖1所示。圖1中，圖（a）表示圖像原圖，圖（b）表示要搜索的模板，圖（c）表示在原圖中搜索模板的結(jié)果，圖（d）表示在原圖加入強(qiáng)度為0.1的椒鹽噪聲后的搜索結(jié)果，圖（e）表示將原圖逆時(shí)針旋轉(zhuǎn)3°之后的搜索結(jié)果，圖（f）表示原圖灰度降低25%之后的搜索結(jié)果。圖1中從1到4分別代表著兩張經(jīng)典普通圖像、一張遙感衛(wèi)星圖像、一張夜間紅外圖像。

本文將從以下幾個(gè)方面說明幾種方法的實(shí)驗(yàn)情況。下文提到的位置均指的是圖像左上角的位置。

1）以圖1的圖（1a）為例來說明四種方法在無畸變圖像上搜索模板時(shí)的準(zhǔn)確率、運(yùn)行時(shí)間、收斂速度情況。模板在圖像中的正確位置為（240，230），每種方法運(yùn)行20次，表1展示了這幾種方法的準(zhǔn)確率、平均運(yùn)行時(shí)間、平均收斂代數(shù)情況；圖2展示了3種群智能算法的收斂曲線。

圖1 本文方法的仿真結(jié)果

從實(shí)驗(yàn)匹配結(jié)果中可以看到，幾種方法的準(zhǔn)確率都為100%，但是在運(yùn)行時(shí)間上，與傳統(tǒng)的SSDA相比，群智能方法擁有巨大的優(yōu)勢(shì)。另外，雖然這3種群智能方法運(yùn)行消耗的時(shí)間相差不大，但是從表1和圖2收斂曲線上可以發(fā)現(xiàn)，雞群優(yōu)化算法的收斂速度要比粒子群算法和人工蜂群算法快的多。

表1 四種方法在原圖上的實(shí)驗(yàn)結(jié)果

圖2 三種群智能方法的收斂性

2）以圖1中圖（4d）為例來說明幾種方法在噪聲環(huán)境下的結(jié)果。（4d）這張圖是一張夜間紅外圖像，加噪的這張圖像很具有代表性，紅外攝像頭等設(shè)備產(chǎn)生的夜間圖像常常會(huì)有噪點(diǎn)。原圖像加入了強(qiáng)度為0.1的椒鹽噪聲，模板圖像的正確位置為（240，205），每種方法運(yùn)行20次。接下來引入兩個(gè)評(píng)價(jià)指標(biāo)：最大歐式距離和平均平方差度量（MSD）。

最大歐式距離指的是搜索到的最差位置到正確位置的歐氏距離。

平均平方差度量從像素級(jí)別來衡量兩者之間的差異，它按照以下公式計(jì)算：

其中（u，v）是指圖像左上角頂點(diǎn)所在的位置，m和n為模板的長和寬。J為匹配結(jié)果圖像，I為模板圖像。

表2展示了四種方法在噪聲情況下的實(shí)驗(yàn)結(jié)果。

表2 四種方法在噪聲影響下的實(shí)驗(yàn)結(jié)果

通過對(duì)比可以看出，傳統(tǒng)的SSDA方法在有噪聲的圖像上無法匹配到正確的圖像，而結(jié)合了DCT變換的群智能方法，一方面保持了高準(zhǔn)確率，另一方面即使沒有完全匹配正確，但是離正確位置的差距也不是非常大，產(chǎn)生巨大的MSD應(yīng)該是大量噪點(diǎn)的原因。實(shí)驗(yàn)結(jié)果可以體現(xiàn)出DCT變換在抗噪性能方面的良好表現(xiàn)。

3）以圖1中圖（2e）為例來說明幾種方法在圖像旋轉(zhuǎn)情況下的匹配情況。圖（2e）是（2a）原圖逆時(shí)針旋轉(zhuǎn)3°得到的，旋轉(zhuǎn)后不為整數(shù)點(diǎn)的像素通過雙線性插值得到。正確位置為（190，258），每種方法運(yùn)行20次，實(shí)驗(yàn)結(jié)果如表3所示。

表3 四種方法在旋轉(zhuǎn)情況下的實(shí)驗(yàn)結(jié)果

從表中可以看出，傳統(tǒng)的SSDA方法在圖像產(chǎn)生輕微旋轉(zhuǎn)時(shí)，也完全失效，而圖像發(fā)生輕微旋轉(zhuǎn)的前后，其DCT矩陣也有一定的相似性，因此DCT變換有一定的魯棒性。這三種群智能算法在匹配效果上，差距不大。在粒子群算法的結(jié)果中，即使其100%地匹配到了正確結(jié)果，其MSD也不為0，原因是匹配到的結(jié)果是有旋轉(zhuǎn)變化的，不可能和模板100%的相同。

4）以圖1中的圖（3f）為例，這是張衛(wèi)星遙感圖像，經(jīng)常受到光照影響，產(chǎn)生灰度變化的這張圖具有代表性。這張圖的處理是灰度降低25%，正確位置為（155，135），每種方法運(yùn)行20次，實(shí)驗(yàn)結(jié)果如表4所示。

表4 四種方法在灰度變化情況下的實(shí)驗(yàn)結(jié)果

從表中可以看出，SSDA方法在碰到灰度變化時(shí)，也不奏效。粒子群算法和人工蜂群算法雖然準(zhǔn)確率和雞群優(yōu)化算法相比，差了很多，但是在實(shí)驗(yàn)中匹配出錯(cuò)時(shí)，匹配結(jié)果大部分都是在正確位置附近，只有少數(shù)幾次落到了表中展示的最差位置。由此可見，雞群優(yōu)化算法不容易陷入局部最優(yōu)。

綜上所述，基于DCT變換和雞群優(yōu)化算法的匹配方法，在運(yùn)行時(shí)間和匹配精度上遠(yuǎn)遠(yuǎn)好于傳統(tǒng)的SSDA方法，在收斂速度上比其他兩種群智能方法要快，不易陷入局部最優(yōu)，具有較好的可行性。

5 結(jié)語

根據(jù)DCT矩陣左上角集中了圖像主要信息這一特點(diǎn)，本文將DCT變換與近年來提出的雞群優(yōu)化算法相結(jié)合，提出了一種基于DCT變換和雞群優(yōu)化算法的圖像匹配方法。然后，本文設(shè)置了一系列的對(duì)比仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的基于DCT變換和雞群優(yōu)化算法的圖像匹配方法在噪聲、旋轉(zhuǎn)、灰度變化等情況下都能有良好的匹配效果，有一定的魯棒性，同時(shí)還有收斂速度快、精度高，不易陷入局部最優(yōu)的優(yōu)點(diǎn)，對(duì)于圖像匹配具有比較實(shí)用的價(jià)值。