粒子群算法在矢量量化圖像壓縮中的應用

黃志超 喬振華

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

關鍵詞：粒子群算法；矢量量化；圖像壓縮

中圖分類號：TP18 文獻標識碼：A

文章編號：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引言

粒子群優化算法（PSO）是一種進化計算技術（evolutionary computation），由Eberhart博士和Kennedy博士于1995 年提出[1，2]，通過研究鳥群捕食的行為，得到啟示從而引申出該算法。粒子群算法是用來尋找最優解的算法，是較為常見的一種優化算法。

矢量量化是一種效率較高的數據壓縮編碼方式，碼書的設計是其關鍵之處，碼書設計的好壞直接決定了其性能問題，Linde，Buzo和Gray于1980年提出了LBG矢量量化碼書設計方法[3]。經典的LBG算法存在一個缺陷，即容易陷入局部最優[4]，且解碼后的圖像細節邊緣部分失真較嚴重，且存在方塊效應。

由于LBG算法容易陷入局部最優解，因此結合粒子群算法的全局搜索策略解決該問題，并將其用于實現圖像壓縮。

2 粒子群算法簡介

粒子群優化算法[5]主要研究鳥群隨機搜索食物，在本區域內只有一塊食物，然而，鳥群中所有的鳥都不知道那塊食物具體在哪里，他們所知道的是當前自己所在的位置與那塊食物的距離，那么找到那塊食物最直接有效的方法就是尋找目前與那塊食物距離最近的鳥的周圍區域。

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

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

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

首先，將圖像劃分為若干個像素塊，其中，每個像素塊中包含若干個像素點。把若干個像素點組成的像素塊，用一個特定碼書中的像素塊來表示，碼書中像素塊的數目一般遠小于這些像素塊所有可能顏色的組合。其次，對圖像中的每個塊（矢量），用一個碼書中的碼字來近似，這樣只需要用這個碼字的編號來編碼這個圖像矢量即可，由此達到壓縮的目的，但由于LBG算法易于陷入局部最優解，從而通過結合粒子群算法解決該問題。具體算法步驟如下：

（1）將圖像轉換為[M×L]的二維數組；

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

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

（4）k=k+1；

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

（6）根據公式（2）更新每個粒子的位置；

（7）對每個粒子執行LBG算法（具體計算方法參見第3章節），得到更新之后的位置；

6結束語

壓縮圖像是在保證圖像的質量情況下，用盡量少的比特數去表示圖像。本論文通過結合粒子群算法和LBG算法對圖像進行壓縮。從碼書中選擇一個特定的碼字用來表示由若干個像素點組成的像素塊，這些像素塊所有的可能組合一般遠大于碼書中碼字的數目。通過此方法可實現圖像的壓縮，壓縮效果較好。但是，本論文所討論的方法，對于小圖像失真較嚴重。

參考文獻：

[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.一種矢量量化設計算法[J].IEEE通信會刊，1980，18（1）：84-95.

[4] 李殷，李飛.基于量子粒子群優化算法的矢量量化碼書設計[J].數字視頻，2012（17）：14.

[5] 紀震，廖惠連，吳清華.粒子群算法及應用[M].北京：科學出版社，2009.

[6] 葛繼科，邱玉輝，吳春明，蒲國林.遺傳算法研究綜述[J].計算機應用研究，2008（10）.

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

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

【通聯編輯：唐一東】