矢量量化圖像壓縮方法

楊 超，董世錕

（1.海軍航空工程學院電子信息工程系，山東 煙臺 264001；2.海軍大連艦艇學院學員旅，遼寧 大連 116018）

0 引言

圖像的數據量非常大。為了有效地傳輸和存儲圖像，常有壓縮圖像數據的必要。圖像壓縮就是在沒有明顯失真的前提下，將圖像的位圖信息轉變成另外一種能將數據量縮減的表達形式。這樣做是有理論基礎的。首先，盡管圖像中數據量很大，但數據之間不是完全獨立的，圖像中存在著各種各樣的相關性或冗余信息。即一部分數據可以由另一部分數據完全推算出來。其次，大部分圖像視頻信號的最終接收者是人眼，而人類的視覺系統是一種高度復雜的系統，它能從極為雜亂的圖像中抽象出有意義的信息，并以非常精練的形式反映給大腦。人眼對圖像中的不同部分的敏感程度是不同的，如果去除圖像中對人眼不敏感或意義不大的部分，對圖像的主觀質量是不會有很大影響的。

正由于圖像壓縮的必要性和可行性，圖像壓縮編碼研究成為一個越來越活躍的領域。在諸如基于Internet的多媒體通信、可視電話、數字電視、多媒體計算機等領域得到了廣泛的應用。

圖像編碼技術包括三個主要方面：①圖像壓縮的新算法的研究；② 基于VLSI技術的壓縮算法的硬件實現；③面向不同應用場合的壓縮編碼標準的制定。其中，壓縮算法的研究是圖像編碼技術的關鍵。

本文介紹的基于矢量量化（Vector Quantization，VQ）的圖像壓縮方法是20世紀70年代后期發展起來的一種數據壓縮技術，是在圖像編碼技術中研究得較多的新型量化編碼方法。其基本思想是[1]：矢量量化編碼優于標量量化，將若干個標量數據組構成一個矢量，然后在矢量空間給以整體量化，從而壓縮了數據而不損失多少信息。

LBG算法[1]是Y.Linde，A.Buzo與R.M.Gray在1980年給出的矢量量化算法，以后有許多人進行了改進。其思想是：對于一個訓練序列，先找出其中心，再用分裂法產生一個初始碼書，再把訓練序列按碼書中的元素分組，對這一分組再找每組的中心得到新的碼書，轉而把新碼書作為初始碼書再進行上述過程直至滿意為止。

本文在介紹基于矢量量化的圖像壓縮方法基礎上，將按照LBG算法以均方誤差法計算兩向量之間的距離，以分裂法產生初始碼書（以4×4塊圖像組成的256 碼書），通過全搜索算法進行碼字搜索，對64×64的Lena 灰度圖像進行矢量壓縮編碼，計算還原結果；LBG算法的缺陷是運行時間長，圖像質量有較大的提升空間，對此許多論文都進行了探討[2-14]，但是，文章大多在討論算法，對影響運行速度的重要因素——訓練樣本數目的討論卻鮮見文章發表。有鑒于此，本文就選擇合適數目的圖像樣本與運算速度的關系進行討論，試圖找到提高LBG算法運算速度的有效途徑。

1 基于矢量量化的圖像壓縮法及LBG算法

1）基于矢量量化的圖像壓縮方法。

在數據與圖像的壓縮中，無論是數據還是圖像，都可以看成是一串數據。設這段數據是m個數據，把它截成M段（一般是相等的，例如每段k個數據），即把m個數據變成M個數據向量，再把M個向量分成N個組，對每個組挑選一個數據向量，作為這個組的代表，例如，第j個組中的代表為yj，j=0,1,…,N?1。所謂壓縮，就是圖像上的數據向量，如果屬于第j個組，則這個數據向量就用這個組的代表向量 yj代替，這時的編碼就是在碼書的相應位置上記下編號j，而不必記下yj本身。而記錄{yj}的文件稱為碼書。如上N為量化向量yj的個數，即碼書長度為N，這時傳輸或存儲下標所需比特數為log2N。因此，平均傳輸一個像素所需的比特數為(log2N)/k。例如一個圖像的每個像素用256級灰度，則每個像素點占用8 比特。如果壓縮后平均每個像素點占R 比特，則有 R=(log2N)/k，即N應滿足關系 N=2kR。實用中，一般總令kR為正整數以便用于計算。這樣，向量量化方法的壓縮比是可以控制的。

2）LBG算法是典型的矢量量化算法。

a.初始化：給定級數N，失真閾值ε，一個訓練序列，某個初始N級碼本令

其中，si={xj:d(xj?yi)≤d(xj?yl)}，l=1,2,…,N。

計算總平均失真

c.如果（Dn?1?Dn）/Dn≤ε，停止；為最終碼本；否則繼續。

2 方案設計

1）中心向量。

在矢量量化編碼中，關鍵是碼本的建立和碼字搜索算法。如上所述，在數據和圖像的壓縮中，當k 確定后，問題就變成了如何分組及如何對每個組挑選代表的問題。當然，這個代表可以是組中的向量，也可以不是組中的向量，這個理想的代表當然應當是組中各向量的中心向量。為求中心，需要引入兩向量x與yj之間距離 d (x,yj)）的概念。當然，兩向量之間的距離多種多樣，最常用的幾個如下：

d.加權均方誤差

本設計的碼本的生成算法是在未知信源分布，但已知信源的一列具有代表性且足夠長的樣點集合（即訓練序列）的設計算法，具體采用的是LBG算法，兩向量之間的距離采用均方誤差法。

選擇有許多方法，不同初始碼書對最終碼書往往有較大的影響。本文采用分裂法產生初始碼書。設kR=l，得到2lN=級量化器，具體步驟如下：

3）搜索過程。

碼字搜索是矢量量化中的一個最基本問題，矢量量化過程本身實際上就是一個搜索過程，即搜索出與輸入最為匹配的碼本。矢量量化中最常用的搜索方法是全搜索算法和樹搜索算法。全搜索算法與碼本生成算法是基本相同的，在給定速率下其復雜度隨矢量維數K以指數形式增長，全搜索矢量量化器性能好但設備較復雜。樹搜索算法又有二叉樹和多叉樹之分，它們的原理是相同的，但后者的計算量和存儲量都比前者大，性能比前者好。樹搜索的過程是逐步求近似的過程，中間的碼字是起指引路線的作用，其復雜度比全搜索算法顯著減少，搜索速度較快。由于樹搜索并不是從整個碼本中尋找最小失真的碼字，因而它的量化器并不是最佳的，其量化信噪比低于全搜索。本文采用全搜索算法。

為了討論選擇合適訓練樣本數以減少運算時間方法的有效性，本文首先討論訓練樣本圖像數與壓縮結果的關系，在圖像解壓質量較好的前提下，計算、比較不同訓練樣本數對應的圖像編碼時間。

3 仿真實驗

用數碼相機拍攝10幅圖像，經過photoshop 軟件的處理，使其變換成大小為64×64的灰度圖像，并分別以JPG形式存儲。將這些訓練圖像分劃成4×4 并且不相交的小塊，通過LBG算法計算256個碼本構成的碼書。按照LBG算法以均方誤差法計算兩向量之間的距離，通過全搜索算法進行碼字搜索，得到的壓縮Lena圖像還原結果如圖1所示，其中，a）為原始圖像；b）為經過VQ 編碼后解碼出來的圖像，壓縮信噪比SNRrms為21.554 8 dB，碼本維數k=16，碼書長度N=256，壓縮后平均每個像素點占比特數R=0.5 bpp，壓縮率為1/16。

為了研究訓練樣本圖像數與圖像壓縮編碼效果的關系，本文由仿真試驗給出了圖2曲線。

圖2是用LBG算法對64×64的Lena 灰度圖像進行矢量編碼時，訓練樣本個數與量化信噪比PSNR的關系，k=16，R=0.5 bpp。

圖1 Lena數字圖像壓縮編碼結果

圖2 訓練樣本個數與量化信噪比PSNR的關系

圖3是當訓練樣本數分別為10、20、30、50和100時，用本文的矢量量化壓縮編碼方法對64×64的Lena 灰度圖像進行壓縮編碼后得到的解碼圖像，k=16，R=0.5 bpp。

圖3 圖像還原效果

由圖2和圖3可見，訓練樣本數為10幅圖像以上時，用LBG算法對64×64的Lena 灰度圖像進行矢量編碼圖像質量較好。

圖4是用LBG算法對64×64的Lena 灰度圖像進行矢量編碼時，訓練樣本個數與編碼運算時間的關系，k=16，R=0.5 bpp。

由圖4可見，圖像訓練樣本數為10幅、20幅和100幅圖像時，LBG圖像壓縮算法運行時間分別是50 min、90 min和360 min。

用100幅圖像作為訓練樣本圖像進行運算需要的時間大約是以10幅圖像為訓練樣本圖像的5 倍。

圖4 訓練樣本個數與運算時間的關系

4 結束語

本文按照LBG算法以均方誤差法計算兩向量之間的距離，通過全搜索算法進行碼字搜索，以分裂法產生初始碼書（以4×4塊圖像組成的256 碼書），得到壓縮Lena圖像還原結果。仿真實驗表明，以100個圖像為訓練樣本，對64×64的灰度圖像，以4×4塊圖像組成的256 碼書進行恢復，按照LBG算法以均方誤差法計算兩向量之間的距離，通過全搜索算法進行碼字搜索，可以得到較高的數字圖像壓縮比（壓縮率為1/16）；另外，圖像訓練樣本數在10個以上時，用本文的矢量量化壓縮編碼方法對圖像進行壓縮編碼，都可以得到較高的數字圖像壓縮比，但用100幅圖像作為訓練樣本圖像進行運算需要的時間是以10幅圖像為訓練樣本圖像的5 倍。由此可見，尋找合適的訓練樣本圖像數，可以大大縮短圖像壓縮編碼時間。

[1]張春田,蘇育挺,張靜.數字圖像壓縮編碼[M].北京:清華大學出版社,2006:284-291.

[2]張濤,于鳳萍,要強,等.高效的模糊聚類初始碼書生成算法[J].紅外與激光,2010,39(1):179-183.

[3]陳善學.矢量量化的初始碼書算法[J].計算機工程與應用,2010,11:26-28.

[4]鄧宏貴,郭晟偉.采用分量均值正交分割法設計矢量量化初始碼書[J].中南大學學報:自然科學版,2010,41(2):628-631.

[5]胡光波,周勇,徐騫.改進向量量化算法的圖像壓縮研究[J].科學技術與工程,2010,10(14):3517-3519.

[6]榮秋生,潘梅森,顏君彪.基于Hopfiled神經網絡的圖像矢量量化[J].微計算機信息:管理一體化,2007,23(2-3):301-302.

[7]李霆,王東進,劉發林.基于混合遺傳算法的碼書設計方法[J].電訊技術,2007,47(1):151-153.

[8]胡俊.基于小波變換的多級矢量量化圖像編碼算法[J].現代電子技術,2007,241(2):56-58.

[9]華宇寧,楊潔.基于遺傳算法的碼本設計及其在說話人識別中的應用[J].沈陽理工大學學報,2007,26(5):62-64.

[10]紀震,廖惠連,許文煥,等.粒子對算法在圖像矢量量化中的應用[J].電子學報,2007,35(10):1916-1920.

[11]王冬芳,廖裕民,余寧梅.矢量量化碼書旋轉壓縮的研究[J].計算機工程與應用,2008,44(24):53-58.

[12]劉剛,劉晶,王泉.一種基于覆蓋域密度的LBG算法[J].計算機應用,2008,28(12):319-325.

[13]郭瑩,董吉文.一種快速的碼本設計算法[J].山東科學,2008,21(1):57-60.

[14]李碧,林土勝,姜靈敏.應用協同進化的圖像矢量量化碼書設計方法[J].計算機應用,2008,44(36):29-31.