碼本均衡矢量編碼算法

摘 要： 提高矢量編碼的壓縮率是矢量編碼的一個重要研究方向。提出一種提高矢量編碼壓縮率的碼本均衡算法。它是對LBG算法得到的碼本進行修正，將胞腔矢量個數較小的聚類矢量用胞腔矢量個數較大的胞腔矢量取而代之，以此完成再生初始矢量的選擇，然后再用LBG算法進行壓縮，該算法以較短的碼本長度完成矢量壓縮，從而提高了壓縮率。給出了碼本均衡算法的思想和具體算法步驟，仿真結果證明了該方法的有效性。

關鍵詞： 矢量量化； 初始碼書； LBG算法； 聚類算法

中圖分類號： TN919.81?34 文獻標識碼： A 文章編號： 1004?373X（2016）13?0038?03

Abstract： The improvement of vector coding compression ratio is an important research content of vector coding. A codebook equilibrium algorithm to improve the vector coding compression ratio is proposed in this paper. It can modify the codebook obtained by LBG algorithm. The clustering vectors with lesser cell lumens are replaced by the ones with more cell lumens to select the regenerative initial vectors. And then the vectors are compressed with LBG algorithm. The algorithm can accomplish the vector compression with shorter codebook to improve the compression ratio. The concept and specific steps of the codebook equilibrium algorithm are given. The validity of the algorithm was proved by simulation results.

Keywords： vector quantization； initial codebook； LBG algorithm； clustering algorithm

0 引 言

矢量編碼理論研究始于20世紀50年代，1956年Steinhaus首次從理論上闡述了最佳矢量量化問題，矢量量化編碼研究在世界范圍內展開，1980年Y.Linde，A.Buzo與R.M.Gray提出的LBG算法是矢量量化編碼研究的一個里程碑[1]。LBG算法在以后的矢量量化編碼研究中得到不斷完善[2?7]。如今，矢量編碼在衛星遙感圖片的壓縮傳輸[8]、聲音識別[9?11]、語音通信[12]、數字水印[13]等方面得到了應用，而且矢量編碼的應用范圍還在日益擴展。對矢量編碼的研究方興未艾，其中，提高矢量編碼的壓縮率是矢量編碼的一個重要方向。本文提出一種對LBG算法進一步改進的矢量碼本均衡算法，旨在減小矢量編碼的碼本長度，從而提高矢量編碼的壓縮率。

本文在闡述LBG算法思想的基礎上，介紹碼本均衡算法思想和算法步驟，然后用碼本均衡算法對lena圖像進行壓縮，并研究壓縮結果。

1 碼本均衡矢量編碼算法思想

LBG算法的思想是：對于一個訓練序列，先找出其中心，再用分裂法產生一個初始碼書再把訓練序列按碼書中的元素分組，對這一分組再找每組的中心得到新的碼書，轉而把新碼書作為初始碼書再進行上述過程，直至滿意為止。

研究用分裂法選取初始碼本的LBG算法對圖像壓縮發現，有些胞腔矢量數較少或為零，對應的聚類矢量在圖像量化中沒有用到，顯然不合理；對應胞腔矢量數較少的聚類矢量，在圖像量化中用到的概率也較小。碼本均衡法的思想是：把胞腔矢量數為零或較小的聚類矢量重新賦值，使它們等于胞腔矢量個數較多的胞腔矢量值，并和其余聚類矢量一并做為一組再生初始碼本，用LGB算法重新計算最終碼本，并以最終碼本重新劃分圖像灰度矢量空間，則胞腔矢量的最小值將增加，總的圖像矢量量化誤差將減小，圖像質量將會提高，進而以較短的碼本長度達到（用LBG算法時的）用較長的碼本長度計算的圖像壓縮質量，由于碼本長度減小，使圖像矢量編碼壓縮率提高。更進一步地說，無論是否用分裂法產生初始碼本和是否用LBG法產生最終碼書，只要胞腔矢量數很小時，都可以用碼本均衡法對碼本進行進一步修正，以減小滿足圖像質量要求的碼書長度，進而提高圖像壓縮率。

2 碼本均衡矢量編碼算法步驟

根據碼本均衡算法思想，設計的碼本均衡算法如下：

（1） 初始化：給定技術失真閾值一個訓練序列某個初始級碼本令=∞。

（2） 給定找到訓練序列關于的最小失真分劃其中，對任意

（5） 令轉步驟（2）。

（6） 找出≤2的的個數；

（7） 找出最大的對應的序列號max和對應序列空間的訓練樣本，對任意在中找出個相互之間歐式距離較大的訓練矢量由這個和>2的組成二級初始碼書

（8） 給定找到訓練序列關于的最小失真分劃其中，對任意

初始碼書的選擇有許多方法，不同初始碼書往往有較大的影響。以下是本文中將用到的分裂法產生初始碼書的方法。設要得到級量化器。分裂法產生碼本的具體步驟如下：

① 初始化：令定義即整個訓練序列的中心。

② 已知有個向量將每個向量分裂成兩個相近向量和其中為擾動向量，這樣有個向量，置

③ 如果停止，令否則，令轉步驟②。

3 碼本均衡實驗

3.1 實驗過程和結果

為了證明碼本均衡算法對提高圖像壓縮率的有效性，本文對一幅128×128的lena灰度圖像進行了實際的碼本均衡壓縮；為了計算碼書，在網上隨機選取了100幅圖片，并將圖片處理成128×128的灰度圖像，然后將處理后的圖像作為訓練圖像。實驗結果如下：

圖1是128×128的lena灰度圖像。圖2是選擇碼書為4維且碼本長度為1 024，通過分裂法產生初始碼本，通過LGB算法對圖1進行壓縮和解壓后的圖像。圖3是選擇碼書為4維且碼本長度為256，通過分裂法產生初始碼本，通過LGB算法對圖1進行壓縮和解壓后的圖像。圖4是在圖3的基礎上，用碼本均衡算法進行圖像壓縮后恢復的圖像，具體做法是：將用圖3碼本劃分的圖像灰度矢量空間中，訓練樣本數不大于2對應的碼本矢量被新的碼本初始矢量替代，新的碼本矢量從用圖3碼本劃分的圖像灰度矢量空間中，對應訓練矢量比較多的空間中選取（選取中使被選訓練矢量之間歐式距離盡量大），用部分矢量被替換后的新碼本作為初始碼本，用LBG算法計算得到最終碼本。用該碼本對圖1編解碼后得到圖4。

3.2 結果分析和結論

比較圖1和圖2以及圖1和圖3可知，作為對圖1原始圖像的恢復，圖2的圖像質量滿足要求，但圖3的質量與圖1相差較大，不滿足要求。原因是圖2對應的矢量編碼碼書長度為1 024，圖3對應的矢量編碼碼書長度為256，由于在碼書矢量維數相同（都為4）的情況下，較短的碼書長度對圖像量化后恢復的圖像與原圖像像素總的灰度差較大，因此，圖像3的質量較圖像2差（比如，與圖像2相比，圖像3中lena的頭發光滑度較差），因此，對圖像1進行維數為4的矢量編碼，碼書長度應選擇1 024。圖像4是在圖像3的基礎上進行碼本均衡壓縮。由于碼本均衡算法使解壓縮的圖像的總的量化誤差較不用碼本均衡算法解壓縮的圖像的量化誤差減小，因此，圖4的圖像質量比圖3的圖像質量好（比如，與圖像4比較，圖像3中lena的頭發光滑度較差）。且通過觀察可見，圖4的圖像質量達到了圖2的圖像質量，也滿足圖像壓縮的要求。即選擇碼書為4維且碼本長度為256，通過分裂法產生初始碼本，通過碼本均衡算法對圖1進行壓縮和解壓后的圖像滿足圖像壓縮要求。這樣，滿足對圖1原始圖像壓縮要求的4維碼書長度由原來的1 024變到了256，由于碼書長度變成原來的對應的矢量量化編碼壓縮率是原來的4倍。

由這些實驗數據得出用碼本均衡法可以提高矢量量化編碼壓縮率的結論。

4 結 語

矢量編碼是信號編碼的一個重要分支。本文提出了一種在LBG算法基礎上的碼本均衡矢量壓縮算法，給出了碼本均衡算法的思想和具體算法步驟，并以lena圖像為例，利用碼本均衡計算圖像壓縮（初始碼本選用分裂法產生）。用碼本均衡算法可以使lena圖像矢量壓縮的4維碼本長度由1 024減小到256，圖像壓縮率是原來的4倍，結果證明用碼本均衡算法可以使矢量編碼的碼本長度減小，從而提高信號壓縮率。

參考文獻

[1] LINDE Y， BUZO A， GRAY R M. An algorithm for vector quantizer design [J]. IEEE transactions on communications， 1980， 28（1）： 84?85.

[2] 熊燕.LSF參數轉換分裂矢量量化的卡爾曼后濾波增強方法[J].計算機工程與應用，2013，49（10）：228?231.

[3] 郭艷菊，陳雷，陳國鷹.基于改進人工群的圖像矢量量化碼書設計算法[J].計算機應用，2013，33（9）：2573?2576.

[4] 楊超，董世錕.矢量量化圖像壓縮方法[J].海軍航空工程學院學報，2011，26（1）：11?14.

[5] 胡云，謝俊元，王崇駿.基于組合碼字的矢量量化編碼算法[J].南京大學學報（自然科學版），2011，47（5）：559?565.

[6] 黃榜，謝林柏.一種新的矢量量化碼書設計算法[J].科學技術與工程，2011，11（1）：46?50.

[7] SHEN F， HASEGAWA O. An adaptive incremental LBG for vector quantization [J]. Nature networks， 2006， 19（5）： 694?704.

[8] 黃日勝.一種改進的小波域子矢量高光譜圖像壓縮處理技術[J].科技通報，2014，30（8）：149?151.

[9] 楊淑瑩，劉旭鵬，陶沖，等.基于免疫貓群優化算法的矢量量化的碼書設計及語音識別[J].模式識別與人工智能，2014，27（7）：577?583.

[10] 趙文博，王艇艇，張生，等.基于矢量量化的嬰兒哭聲識別算法[J].微計算機信息，2011，27（4）：224?225.

[11] 孫榮坤，韓紀慶.基于矢量量化的弦樂顫音自動檢測[J].計算機工程與應用，2010，46（31）：199?201.

[12] 劉斌，陶建華，莫福源.面向窄帶通信的極低速率語音編碼算法研究[J].信號處理，2013（9）：1134?1141.

[13] 楊剛，都思丹.基于矢量量化壓縮編碼的數字水印[J].現代電子技術，2014，37（1）：70?74.