粒子群算法在矢量量化圖像壓縮中的應(yīng)用

黃志超 喬振華

摘要：由于矢量量化算法容易陷入局部最優(yōu)解，因此引入粒子群算法的全局搜索策略，通過(guò)結(jié)合粒子群算法實(shí)現(xiàn)矢量量化圖像的壓縮。通過(guò)Matlab7.0實(shí)驗(yàn)仿真，實(shí)驗(yàn)結(jié)果表明，此方法的壓縮效果較好，且圖像失真效果不明顯。

關(guān)鍵詞：粒子群算法；矢量量化；圖像壓縮

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）11-0193-03

Abstract：Because of the vector quantization algorithm is easy to get into the local optimal solution，the global search strategy of particle swarm optimization（pso） is instrodued to realize the image compression of vector quantization by combining particle swarm optimization.Through the simulation results of Matlab7.0， it shows that the compression effect of this method is better and the image distortion effect is not obvious.

Key words：particle swarm optimization；vector quantization；image compression

1引言

粒子群優(yōu)化算法（PSO）是一種進(jìn)化計(jì)算技術(shù)（evolutionary computation），由Eberhart博士和Kennedy博士于1995 年提出[1，2]，通過(guò)研究鳥(niǎo)群捕食的行為，得到啟示從而引申出該算法。粒子群算法是用來(lái)尋找最優(yōu)解的算法，是較為常見(jiàn)的一種優(yōu)化算法。

矢量量化是一種效率較高的數(shù)據(jù)壓縮編碼方式，碼書(shū)的設(shè)計(jì)是其關(guān)鍵之處，碼書(shū)設(shè)計(jì)的好壞直接決定了其性能問(wèn)題，Linde，Buzo和Gray于1980年提出了LBG矢量量化碼書(shū)設(shè)計(jì)方法[3]。經(jīng)典的LBG算法存在一個(gè)缺陷，即容易陷入局部最優(yōu)[4]，且解碼后的圖像細(xì)節(jié)邊緣部分失真較嚴(yán)重，且存在方塊效應(yīng)。

由于LBG算法容易陷入局部最優(yōu)解，因此結(jié)合粒子群算法的全局搜索策略解決該問(wèn)題，并將其用于實(shí)現(xiàn)圖像壓縮。

2 粒子群算法簡(jiǎn)介

粒子群優(yōu)化算法[5]主要研究鳥(niǎo)群隨機(jī)搜索食物，在本區(qū)域內(nèi)只有一塊食物，然而，鳥(niǎo)群中所有的鳥(niǎo)都不知道那塊食物具體在哪里，他們所知道的是當(dāng)前自己所在的位置與那塊食物的距離，那么找到那塊食物最直接有效的方法就是尋找目前與那塊食物距離最近的鳥(niǎo)的周?chē)鷧^(qū)域。

粒子群優(yōu)化算法與遺傳算法[6]相類似，是一種基于迭代的優(yōu)化算法，但是它沒(méi)有使用遺傳算法的交叉和變異，而是粒子在解空間中追隨最優(yōu)的粒子進(jìn)行搜索。粒子群優(yōu)化算法的思想：首先，對(duì)粒子進(jìn)行初始化，然后通過(guò)一次次的迭代找到最優(yōu)解。在每次迭代中，粒子通過(guò)粒子本身所找到的最優(yōu)解（局部最優(yōu)解）以及整個(gè)種群目前找到的最優(yōu)解（全局最優(yōu)解）來(lái)更新自己。粒子群算法的主要步驟如下：

1）初始化：初始化粒子的初始位置和每個(gè)粒子的速度；

4 基于粒子群算法的矢量量化圖像壓縮

首先，將圖像劃分為若干個(gè)像素塊，其中，每個(gè)像素塊中包含若干個(gè)像素點(diǎn)。把若干個(gè)像素點(diǎn)組成的像素塊，用一個(gè)特定碼書(shū)中的像素塊來(lái)表示，碼書(shū)中像素塊的數(shù)目一般遠(yuǎn)小于這些像素塊所有可能顏色的組合。其次，對(duì)圖像中的每個(gè)塊（矢量），用一個(gè)碼書(shū)中的碼字來(lái)近似，這樣只需要用這個(gè)碼字的編號(hào)來(lái)編碼這個(gè)圖像矢量即可，由此達(dá)到壓縮的目的，但由于LBG算法易于陷入局部最優(yōu)解，從而通過(guò)結(jié)合粒子群算法解決該問(wèn)題。具體算法步驟如下：

（1）將圖像轉(zhuǎn)換為[M×L]的二維數(shù)組；

（2）初始化粒子：首先，從M個(gè)訓(xùn)練矢量中隨機(jī)選取N個(gè)碼字；其次，初始化每個(gè)粒子的速度（在0～255之內(nèi)的隨機(jī)數(shù)）、適應(yīng)值和該局部群體中的局部最優(yōu)解；最后，初始化全局最優(yōu)解，即群體中選擇局部最優(yōu)解中的最小值即為全局最優(yōu)解。

（3）設(shè)置迭代次數(shù)k=0，并選擇最大的迭代次數(shù)itmax；

（4）k=k+1；

（5）根據(jù)公式（1）更新粒子的速度；

（6）根據(jù)公式（2）更新每個(gè)粒子的位置；

（7）對(duì)每個(gè)粒子執(zhí)行LBG算法（具體計(jì)算方法參見(jiàn)第3章節(jié)），得到更新之后的位置；

6結(jié)束語(yǔ)

壓縮圖像是在保證圖像的質(zhì)量情況下，用盡量少的比特?cái)?shù)去表示圖像。本論文通過(guò)結(jié)合粒子群算法和LBG算法對(duì)圖像進(jìn)行壓縮。從碼書(shū)中選擇一個(gè)特定的碼字用來(lái)表示由若干個(gè)像素點(diǎn)組成的像素塊，這些像素塊所有的可能組合一般遠(yuǎn)大于碼書(shū)中碼字的數(shù)目。通過(guò)此方法可實(shí)現(xiàn)圖像的壓縮，壓縮效果較好。但是，本論文所討論的方法，對(duì)于小圖像失真較嚴(yán)重。

參考文獻(xiàn)：

[1] Kennedy J，EberhartR.Particle Swarm Optimization[C].In：IEEE Int1 Conf on Neural Networks，Perth，Australia，1995：1942-1948.

[2] EberhartR，Kennedy J.A New Optimizer Using Particle Swarm Theory[C].In：Proc of the Sixth International Symposium on Micro Machine and Human Science，Nagoya，Japan，1995：39-42.

[3] LindeY，BuzoA，Gray R M.一種矢量量化設(shè)計(jì)算法[J].IEEE通信會(huì)刊，1980，18（1）：84-95.

[4] 李殷，李飛.基于量子粒子群優(yōu)化算法的矢量量化碼書(shū)設(shè)計(jì)[J].數(shù)字視頻，2012（17）：14.

[5] 紀(jì)震，廖惠連，吳清華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社，2009.

[6] 葛繼科，邱玉輝，吳春明，蒲國(guó)林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2008（10）.

[7] 王千，王成，馮振元，等.K-means算法研究綜述[J].電子設(shè)計(jì)工程，2012（4）.

[8] 謝娟英，王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法[J].計(jì)算機(jī)工程，2014（8）.

【通聯(lián)編輯：唐一東】