基于小波變換和改進(jìn)的粒子群的新型圖像匹配算法的研究

解冰　李海娟

摘要：伴隨著圖像處理技術(shù)不斷發(fā)展，圖像匹配是指根據(jù)圖像的特征在圖像數(shù)據(jù)庫中檢索相似或相同的圖像。傳統(tǒng)圖像檢索算法計(jì)算量大、精度小，為了減少計(jì)算量提高精度，本文在傳統(tǒng)算法基礎(chǔ)上將圖像匹配問題轉(zhuǎn)化成在圖像數(shù)據(jù)庫中根據(jù)模板圖像數(shù)據(jù)對(duì)目標(biāo)進(jìn)行鎖定的模型：第一步將模板圖像和源圖像分區(qū)并取灰度直方圖信息。第二步將尋找模板圖像最相似的問題轉(zhuǎn)化成通過粒子群優(yōu)化進(jìn)行分類第三步：通過對(duì)相似度大的那類圖像進(jìn)行精確匹配得出最相似的圖像。實(shí)驗(yàn)結(jié)果表明：基于粒子群和新分類思想的圖像匹配（PBIM）算法能夠在源圖像數(shù)據(jù)庫中快速匹配出相似的圖像組。

關(guān)鍵詞：新分區(qū)；圖像檢索；粒子群優(yōu)化算法；分類

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）11-0175-04

1 引言

信息飛速發(fā)展的今天，各行各業(yè)中圖像檢索已經(jīng)成為不可或缺關(guān)鍵技術(shù)，目前使用者在搜集目標(biāo)圖片的時(shí)候使用的大部分是圖片的文字標(biāo)題，而基于內(nèi)容的圖片搜索是十分 少見的，但是基于文字標(biāo)題的檢索效率低，精度差，往往會(huì)檢索出大量的結(jié)果讓用戶苦不堪言。圖形圖像檢索越來越多的使用在各行各業(yè)，特別是大數(shù)據(jù)和智能計(jì)算的今天，生活中越來越多的使用圖形圖像處理，本文引入對(duì)圖像通過改進(jìn)的粒子群（Particle Swarm Optimization， PSO）和小波變換思想加以改進(jìn)[1]，期望通過實(shí)驗(yàn)證明，在降低空間復(fù)雜度允許的情況下，同時(shí)降低時(shí)間復(fù)雜度。

通過將圖像分塊后提取直方圖信息計(jì)算距離從而將直方圖的距離轉(zhuǎn)化為模板圖像的位置，同時(shí)運(yùn)用粒子群算法，將模板圖像的信息轉(zhuǎn)化為粒子的目標(biāo)值，粒子群通過迭代學(xué)習(xí)，將與目標(biāo)圖像接近的圖像進(jìn)行匯總分類，即模板圖像在源圖像中的位置。實(shí)驗(yàn)結(jié)果證明此法在不失匹配精度的情況下，在速度方面也有較明顯的改善，這種方法是切實(shí)可行的，與傳統(tǒng)的方法相比更高效[2]。

2 圖像檢索模型

圖像檢索的用途支撐者很多學(xué)者與專家進(jìn)行不斷的改進(jìn)。其原理是指通過算法在圖像數(shù)據(jù)庫中搜索模板圖像的相似或相同圖像[3][4]。問題的模型：給定一副大小分別為[K1×G1]的圖像，源圖像：[Pic1={C1（x，y），1≤x≤K1，1≤y≤G1}] ，模板圖像：式中[C1]為圖像的灰度值。本文采用灰度值比較方法，在計(jì)算機(jī)圖像處理領(lǐng)域還可以利用其他特征：紋理[5]、形狀[6]等。

圖像或者圖片的整體參數(shù)就是采集灰度值并計(jì)算總和 ，一組像素的直方圖信息用函數(shù)[H（h1，h2，L，hi）]表示。本文提出的方法不再是按照挨個(gè)像素灰度直接比較的方法，經(jīng)過反復(fù)改造和計(jì)算得出下公式：直方圖間的距離可使用歐氏距離函數(shù)[ME[M（K，G，x，y），R（K，G，x，y）]]衡量：

[ME（M（K，G，x，y），R（K，G，x，y））=i=1L[HM（K，G，x，y）（i）-HR（K，G，x，y）（i）]2]

則可定義：

[M（position（i，j））=][si=1L[HM（K，G，0，0）（si）-HR（K，G，i，j）（si）]2] （3）

公式的含義是以模板圖像為基準(zhǔn)，在源圖像中找相同大小的模塊進(jìn)行直方圖信息比較，[Pic2]在[Pic1]中的最優(yōu)位置[position（i，j）]，為了使得目標(biāo)位置匹配準(zhǔn)確、迅速，必然有

[M（Pic1（i，j），Pic2）]為0或接近0。這是解決問題的核心，找到最優(yōu)位置意味著完成了圖像的匹配。

圖像的可用特征有很多，在不失精度的情況下為了簡(jiǎn)單方便的評(píng)價(jià)圖像，我們采用了灰度值。若為了全方位的評(píng)價(jià)圖像

3 新的分區(qū)思想

在計(jì)算機(jī)圖像處理領(lǐng)域很多思想是為了提高處理效果。但是要評(píng)價(jià)一個(gè)圖像可以根據(jù)很多種屬性。比如顏色直方圖、灰度直方圖、紋理特征還有材質(zhì)。還可以綜合利用各種特征。傳統(tǒng)的圖像匹配都是將兩幅圖像的全部像素按著順序進(jìn)行比較。這種思想是最基礎(chǔ)，也是最容易浪費(fèi)時(shí)間和精確度的。因?yàn)閮煞鶊D像的內(nèi)容大多數(shù)情況下是不一樣的，如果其中有一部分不相似那就沒必要將所有的像素特征再進(jìn)行比較了。

為了節(jié)省圖像評(píng)價(jià)的時(shí)間，本文中提出了新的分區(qū)思想，圖像匹配的思想是找到相同或者最大接近的內(nèi)容的圖像，所以新的分區(qū)思想在判斷內(nèi)容上做了大膽的改進(jìn)。 首先將原始圖像和模板圖像取中間寬度為邊長(zhǎng)五分之一的中間帶狀相交區(qū)域，然后在圖中A、B、C、D空白處取邊長(zhǎng)為圖像邊長(zhǎng)五分之一的圖像塊，如圖中 A、B、C、D區(qū)，在進(jìn)行直方圖，如圖所示：

信息評(píng)價(jià)時(shí)，先讓兩幅圖像的中間橫豎相交的黑色區(qū)域進(jìn)行對(duì)比，然后A區(qū)進(jìn)行比對(duì)，如果結(jié)果在設(shè)定的閾值之內(nèi)則繼續(xù)進(jìn)行B區(qū)，以此類推，這樣將很多不一樣的圖像在比對(duì)A區(qū)的時(shí)候就淘汰了，所以節(jié)省了四分之三以上的計(jì)算量。通過實(shí)驗(yàn)驗(yàn)證該思想能夠在不失精度的前提下很大程度的縮短了匹配時(shí)間降低了計(jì)算復(fù)雜度。

4 改進(jìn)的粒子群優(yōu)化算法

計(jì)算機(jī)領(lǐng)域中有很多優(yōu)化算法。粒子群優(yōu)化算法（Particle Swarm Optimization PSO）是一種用無質(zhì)量、無體積的粒子作為個(gè)體，并為每個(gè)粒子制定了簡(jiǎn)單的行為規(guī)則，從而使整個(gè)粒子群表現(xiàn)出復(fù)雜的特性，可用來對(duì)復(fù)雜問題進(jìn)行優(yōu)化求解。

粒子群優(yōu)化算法（PSO）是一種進(jìn)化計(jì)算技術(shù)（evolutionary computation），1995 年由Eberhart 博士和kennedy 博士提出，源于對(duì)鳥群捕食的行為研究 。該算法最初是受到飛鳥集群活動(dòng)的規(guī)律性啟發(fā)，進(jìn)而利用群體智能建立的一個(gè)簡(jiǎn)化模型。粒子群算法在對(duì)動(dòng)物集群活動(dòng)行為觀察基礎(chǔ)上，利用群體中的個(gè)體對(duì)信息的共享使整個(gè)群體的運(yùn)動(dòng)在問題求解空間中產(chǎn)生從無序到有序的演化過程，從而獲得最優(yōu)解。

在優(yōu)化過程中粒子追隨群體中當(dāng)前位置和速度最優(yōu)的粒子而移動(dòng)，并經(jīng)逐代迭代搜索后得到最優(yōu)解。在每一代中，粒子將跟蹤本身迄今找到的最優(yōu)解pbest和迄今找到的最優(yōu)解gbest進(jìn)行搜索。公式（1）（2）是粒子群更新的依據(jù)，

[v[]=w*v[]+c1*random（）*（pbest[]-present[]）+c2*random（）*（gbest[]-present[]）（1）//速度更新公式][present[]=present[]+v[]] [（2）]

c1，c2一般取2，[rand（）]?。?，1）之間的隨機(jī)數(shù)，這樣是算法更有隨機(jī)性。公式（1）中第一項(xiàng)v[]是動(dòng)量項(xiàng)，第二項(xiàng)是認(rèn)知項(xiàng)，通常認(rèn)為粒子認(rèn)識(shí)到自身經(jīng)驗(yàn)，從而增強(qiáng)學(xué)習(xí)，第三項(xiàng)是社會(huì)項(xiàng)，代表了粒子之間相互影響，相互合作。認(rèn)知項(xiàng)代表粒子之間的競(jìng)爭(zhēng)，社會(huì)項(xiàng)代表粒子之間的合作，從而實(shí)現(xiàn)群體智能搜索[8][9]。

在粒子群優(yōu)化算法中，我們添加了隨機(jī)的粒子和隨機(jī)速度與隨機(jī)位置，在仿真程度上使得算法更接近于現(xiàn)實(shí)，比如公式1和公式2中最后一項(xiàng)，經(jīng)過實(shí)驗(yàn)數(shù)據(jù)的驗(yàn)證，添加了隨機(jī)值的學(xué)習(xí)效果更佳，不同的參數(shù)對(duì)應(yīng)不同的粒子群優(yōu)化模型，對(duì)于粒子群來說算法參數(shù)選取和收斂性是影響算法性能和效率的關(guān)鍵因素，并且有緊密的聯(lián)系，直接影響著粒子群的搜索過程和收斂特性[10]。

5 改進(jìn)的算法及其分析

5.1算法解決問題的具體原理

根據(jù)之前提出的問題模型，我們將一個(gè)在海量圖像中進(jìn)行圖像匹配的問題或者在一副圖像中進(jìn)行內(nèi)容匹配的問題轉(zhuǎn)換為一個(gè)樣本空間在全局的范圍內(nèi)模擬粒子群算法優(yōu)化問題，基于灰度的圖像匹配的基本思想是將圖像的不同歸結(jié)為其直方圖信息的差距[11]，從而將圖像的檢索轉(zhuǎn)化為直方圖的距離計(jì)算。

原圖像參數(shù)為[K1×G1]，模板圖像尺寸為[K2×G2]，具體在PSO算法編程時(shí)候，我們采用粒子數(shù)為[s]，迭代[n]代。每個(gè)粒子用一分辨率為[l×l]像素的小方格模擬，用隨機(jī)函數(shù)[Vi（Vi1，Vi2）=（rand（m1-m2+1，m1），rand（n1-n2+1，n1））]均勻初始化粒子的坐標(biāo)位置。

5.2 小波變換處理原理

小波變換在圖形圖像處理領(lǐng)域經(jīng)常采用，圖像的低頻部分保存的是圖像的輪廓信息，而高頻保存的是圖像的邊緣和細(xì)節(jié)信息，大量的研究表明，幅值低的高頻信息對(duì)于圖像共享較小，所以丟棄對(duì)圖像質(zhì)量的影響不大，所以小波變換的特性給了圖像壓縮一個(gè)很好的工具，將原圖進(jìn)行小波分解以后，為高頻信息設(shè)置一個(gè)閾值a，假如該點(diǎn)的值小于a則置零這樣就拋棄掉了圖像中影響不大的低幅值高頻信息，還原出來的圖像沒有明顯的質(zhì)量下降，但是占用空間卻變小了。

本文是為了降低計(jì)算量，提高圖像匹配的速度和效率，小波變換之后的低頻部分仍然可以進(jìn)行進(jìn)一步處理。而后繼續(xù)采用優(yōu)化算法，是本文提出的核心思想。

5.3算法步驟

PSO中的粒子信息對(duì)應(yīng)于本問題中要求解的模板在源圖中的位置信息[position（i，j）]。具體算法步驟：

Step1：輸入一幅源圖像和一幅模板圖像。

Step2：對(duì)兩幅圖像進(jìn)行一次小波變換，分別取原圖像的高頻部分。

Step3：分別將小波變換后的源圖像和模板圖像進(jìn)行整體新分區(qū)（按圖1）

Step4：對(duì)圖像相同坐標(biāo)位置的高頻部分按照新分區(qū)計(jì)算直方圖信息并將結(jié)果記錄在[c1]中；對(duì)模板圖像低頻部分算直方圖信息并將結(jié)果記錄在[c1]中。

Step5：粒子群算法參數(shù)設(shè)置：設(shè)置權(quán)值參數(shù)[c1]和[c2]，將當(dāng)前迭代代數(shù)置為t=1，在源圖像（新分區(qū)后的低頻部分）隨機(jī)產(chǎn)生[s]個(gè)粒子，如圖6所示，形成初始樣本值，并隨機(jī)產(chǎn)生各粒子的初始速度。

Step6：粒子群運(yùn)動(dòng)過程中進(jìn)行評(píng)測(cè)，粒子學(xué)習(xí)不出現(xiàn)早收斂現(xiàn)象視為正常。

Step7：取單個(gè)粒子當(dāng)前的適應(yīng)值與整個(gè)樣本空間最優(yōu)值比較。

Step8：按公式[（1）（2）]更新粒子的速度和位置，產(chǎn)生新的種群。

Step9：檢查是否滿足算法結(jié)束條件（或停機(jī)條件），若滿足，計(jì)算結(jié)束，輸出[gbest]，否則[t=t+1]，轉(zhuǎn)到第6步，直到滿足結(jié)束條件。

經(jīng)過多次采集樣本和反復(fù)實(shí)驗(yàn)，我們討論的范圍與實(shí)際是比較接近的。

5.3算法的評(píng)價(jià)

適應(yīng)度評(píng)價(jià)函數(shù)是PSO算法的一個(gè)重要因素，在圖像匹配問題中適應(yīng)度評(píng)價(jià)函數(shù)就是上述提到的度量

[ME（M（w，h，x，y），R（w，h，x，y））=]，我們采用的原理是：

[ME（M（w，h，x，y），R（w，h，x，y））=] （3） [ME（M（w，h，x，y），R（w，h，x，y））=]

[i=1L[HM（K，G，x，y）（i）-HR（K，G，x，y）（i）]2] （4）

評(píng)價(jià)函數(shù)公式：

[f（position（row，col））=1（m1-m2）*（n1-n2）]*

[row=1K1-K2col=1G1-G2si=1L[HM（m1，n1，0，0）（si）-HR（m2，n2，row，col）（si）]2] （5）

其中公式（5）是改進(jìn)的公式，[f（position（row.col））]是粒子群算法評(píng)價(jià)函數(shù)，[HM（m2，n2，0，0）（Si）]是模板圖像低頻部分M的寬為[m2]，高為[n2]，左上角坐標(biāo)為（0，0）的圖像的直方圖信息 ，同理[HR（m1，n1，0，0）（Si）]是源圖像低頻部分上寬為[m1]高為[n1]，左上角坐標(biāo)為[（row，col）]的直方圖信息，[row]，[col] 分別表示模板中某像素的位置。粒子群速度位置更新公式如上文所述公式[（1）（2）]。

該公式經(jīng)過修改和實(shí)驗(yàn)，在參數(shù)優(yōu)化和實(shí)驗(yàn)學(xué)習(xí)效果上比傳統(tǒng)的算法都有較先進(jìn)的改進(jìn)。

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

6.1實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)主要用C++語言實(shí)現(xiàn)，編譯環(huán)境：VS2008 和matlab7.0，所使用的圖像是384*384，模板圖像是128×128，64×64，32×32。粒子個(gè)數(shù)是70，如圖7所示，匹配時(shí)間復(fù)雜度及同傳統(tǒng)算法比較數(shù)據(jù)如圖8所示。模板部分處理后處的效果如圖6。其中圖6是將源圖像新分區(qū)后低頻部分通過PSO算法將最優(yōu)解時(shí)的粒子的按著坐標(biāo)位置在matlab 7.0中畫出。

從而使得粒子在整個(gè)源圖像空間內(nèi)搜索，圖6為本算法停止運(yùn)算后放大的效果圖（模糊是因?yàn)樾路謪^(qū)后低頻部分放大產(chǎn)生的失真現(xiàn)象的結(jié)果）。

6.2 實(shí)驗(yàn)數(shù)據(jù)比較分析及結(jié)論

進(jìn)行多次實(shí)驗(yàn)采集是驗(yàn)證問題的基本步驟，本試驗(yàn)中針對(duì)粒子群算法設(shè)置了一個(gè)最大迭代次數(shù)如圖6中， PSO算法進(jìn)行匹配我們得出的精確匹配率結(jié)論如圖7：

圖7中將本文提出的算法和未改進(jìn)的算法經(jīng)過改進(jìn)的比較，縱軸是匹配準(zhǔn)確度。從圖易知經(jīng)改進(jìn)的算法能做到精確匹配，比其兩種傳統(tǒng)的更算法高效理論上講：按上述實(shí)驗(yàn)對(duì)灰度圖像進(jìn)行傳統(tǒng)匹配，由于傳統(tǒng)圖像是逐像素進(jìn)行匹配，在執(zhí)行傳統(tǒng)算法時(shí)要對(duì)兩幅圖像進(jìn)行完全匹配處理，從而我們可以得出傳統(tǒng)方法計(jì)算量公式[（K1-K2）×（G1-G2）]，傳統(tǒng)算法計(jì)算次數(shù)應(yīng)該為[（384-128）×（384-128）= 65536]次，根據(jù)筆者實(shí)驗(yàn)實(shí)際設(shè)定的粒子數(shù)，基于新分區(qū)后用PSO算法則只需要計(jì)算[80×200=16000]次；實(shí)驗(yàn)過程中筆者根據(jù)實(shí)際情況和查閱文獻(xiàn)材料發(fā)現(xiàn)，粒子個(gè)數(shù)的選取對(duì)結(jié)果有重要的影響，群體粒子數(shù)目的選擇不能過大或者過小，粒子數(shù)過大，計(jì)算量增加難以體現(xiàn)PSO的精確性，數(shù)量過小不能保證解的精確度，同理迭代次數(shù)也是有要求的，經(jīng)過多次實(shí)驗(yàn)群體數(shù)在[50?80]之間，迭代次數(shù)在[140?360]之間時(shí)，都能得到同圖7相近的結(jié)果，由此可見粒子數(shù)量和迭代次數(shù)在上述數(shù)據(jù)之間取值較為理想。

圖8中縱軸表示時(shí)間（單位秒），從圖中我們可以看到，改進(jìn)的算法的時(shí)間復(fù)雜度和傳統(tǒng)的算法相比有了明顯的降低。綜上實(shí)驗(yàn)表明，該算法有效地減少了運(yùn)算量，提高了圖像匹配的精度。實(shí)驗(yàn)中，為了方便實(shí)現(xiàn)，采用的是圖像的直方圖的信息距離作為評(píng)價(jià)圖像匹配的標(biāo)準(zhǔn)，在實(shí)際應(yīng)用中還可能有其他的評(píng)價(jià)方法，如采用ML法中的ML距離作為適應(yīng)度來進(jìn)行評(píng)價(jià)當(dāng)前搜解，還可以用文獻(xiàn)[12][13]中提到的圖像特征匹配方法，減少計(jì)算量，提高算法的效率。

7 結(jié)束語

本文的創(chuàng)新點(diǎn)在進(jìn)行小波變換的基礎(chǔ)上引入智能學(xué)習(xí)算法和對(duì)圖像進(jìn)行新分區(qū)，將圖像進(jìn)行新分區(qū)后提取圖像主要信息，這樣在計(jì)算時(shí)降低了計(jì)算復(fù)雜度，提高了算法效率，實(shí)驗(yàn)證明經(jīng)PSO算法優(yōu)化后算法在滿足精確要求的情況下時(shí)間復(fù)雜度大大降低。這是在傳統(tǒng)的算法基礎(chǔ)上進(jìn)行的改進(jìn)，通過實(shí)驗(yàn)證實(shí)是可行的不足之處，實(shí)驗(yàn)中得出改進(jìn)的算法的匹配精確率隨著模板的增大而減小。如何避免這一現(xiàn)象將是筆者下一步的研究對(duì)象。

參考文獻(xiàn)：

[1] 何清法，李國杰.綜合分塊主色和相關(guān)反饋技術(shù)的圖像檢索方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2001，13（10）：912-917.

[2] Qiu G P， Lam K M. Frequency layered color indexing for content-based image retrieval [J]. IEEE Transactions on Image Processing， 2003， 12（1）：102-113.

[3] 汪祖媛，梁棟，李斌.基于樹狀小波分解的紋理圖像檢索[J].中國圖象圖形學(xué)報(bào)，2001，6（11）：1065-1069.

[4] Mallat， S. G， A Theory for Multiresolution Signal Decomposition： The Wavelet Representation， IEEE Trans. PAMI， 1989，11（ 7）： 674-693.

[5] 廖云濤，任仙怡，張桂林，等.一種新的基于對(duì)應(yīng)像素距離度量的圖像相關(guān)匹配方法[J].紅外與激光工程，2001， 30（6）： 418-421.

[6] 劉哲，任金昌，李言俊.面向遙感應(yīng)用的圖像融合的原理和方法[J].航空計(jì)算技術(shù)，2001（4）： 9-12

[7] 孫勁光.基于顏色特征的圖像數(shù)據(jù)管理模式研究[D].遼寧：遼寧工程技術(shù)大學(xué)，2006.

[8] 史燕. 基于新分區(qū)的圖像檢索技術(shù)研究[D]. 西安： 西北大學(xué)， 2006.

[9] R C Eberhart， J Kennedy. Particles Swarm Optimization[C]， In：IEEE International Conference on Neural Network， Perth， Australia， 1995

[10] 曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社，2004.

[11]Zhang，A.KanKanhalli，andS.W.Smoliar，“Automatic Partitioning of Full-Motion Video”，ACM Multimedia System， Apr.1993.

[12] Flickner， M.， etc. Query by image and video content： The QBIC System [J]. IEEE Computer， 1995， 28（9）：23-32.

[13] Rui Y， Huang T S. Optimizing learning in image retrieval[C]. IEEE Conf. on CVPR， South Carolina， USA， 2000.