楊　超，賀一君，任建存，宋家康，劉云飛

（1.海軍航空工程學(xué)院 電子信息工程系，山東 煙臺(tái)　264001；2.中國(guó)人民解放軍92853部隊(duì)，遼寧 葫蘆島　125199；3.海軍航空工程學(xué)院 控制工程系，山東 煙臺(tái)　264001；4.中國(guó)人民解放軍91006部隊(duì)，安徽 合肥　231600；5.海軍航空工程學(xué)院 青島校區(qū)，山東 青島　266041）

碼本均衡矢量編碼算法

楊超1，賀一君2，任建存3，宋家康4，劉云飛5

（1.海軍航空工程學(xué)院 電子信息工程系，山東 煙臺(tái)264001；2.中國(guó)人民解放軍92853部隊(duì)，遼寧 葫蘆島125199；3.海軍航空工程學(xué)院 控制工程系，山東 煙臺(tái)264001；4.中國(guó)人民解放軍91006部隊(duì)，安徽 合肥231600；5.海軍航空工程學(xué)院 青島校區(qū)，山東 青島266041）

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

矢量量化；初始碼書(shū)；LBG算法；聚類算法

0　引　言

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

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

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

LBG算法的思想是：對(duì)于一個(gè)訓(xùn)練序列，先找出其中心，再用分裂法產(chǎn)生一個(gè)初始碼書(shū)0，再把訓(xùn)練序列按碼書(shū)0中的元素分組，對(duì)這一分組再找每組的中心得到新的碼書(shū)，轉(zhuǎn)而把新碼書(shū)作為初始碼書(shū)再進(jìn)行上述過(guò)程，直至滿意為止。

研究用分裂法選取初始碼本的LBG算法對(duì)圖像壓縮發(fā)現(xiàn)，有些胞腔矢量數(shù)較少或?yàn)榱?，?duì)應(yīng)的聚類矢量在圖像量化中沒(méi)有用到，顯然不合理；對(duì)應(yīng)胞腔矢量數(shù)較少的聚類矢量，在圖像量化中用到的概率也較小。碼本均衡法的思想是：把胞腔矢量數(shù)為零或較小的聚類矢量重新賦值，使它們等于胞腔矢量個(gè)數(shù)較多的胞腔矢量值，并和其余聚類矢量一并做為一組再生初始碼本，用LGB算法重新計(jì)算最終碼本，并以最終碼本重新劃分圖像灰度矢量空間，則胞腔矢量的最小值將增加，總的圖像矢量量化誤差將減小，圖像質(zhì)量將會(huì)提高，進(jìn)而以較短的碼本長(zhǎng)度達(dá)到（用LBG算法時(shí)的）用較長(zhǎng)的碼本長(zhǎng)度計(jì)算的圖像壓縮質(zhì)量，由于碼本長(zhǎng)度減小，使圖像矢量編碼壓縮率提高。更進(jìn)一步地說(shuō)，無(wú)論是否用分裂法產(chǎn)生初始碼本和是否用LBG法產(chǎn)生最終碼書(shū)，只要胞腔矢量數(shù)很小時(shí)，都可以用碼本均衡法對(duì)碼本進(jìn)行進(jìn)一步修正，以減小滿足圖像質(zhì)量要求的碼書(shū)長(zhǎng)度，進(jìn)而提高圖像壓縮率。

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

根據(jù)碼本均衡算法思想，設(shè)計(jì)的碼本均衡算法如下：

（1）初始化：給定技術(shù)N，失真閾值ε，一個(gè)訓(xùn)練序列 ｛xj：j=0，1，2，…，m-1｝，某個(gè)初始 N級(jí)碼本0=｛yi：i=1，2，…，N｝，令n=0，D-1=∞。

計(jì)算總平均失真：

（3）如果Dn-1-Dn≤ε，轉(zhuǎn)步驟（6）；否則繼續(xù)。

式中：‖sj‖表示 sj中訓(xùn)練樣本向量的個(gè)數(shù)。如果‖sj‖=0，則令（sj）=yj，即碼字不變。

（7）找出最大的‖sj‖對(duì)應(yīng)的序列號(hào)max和對(duì)應(yīng)序列空間的訓(xùn)練樣本 smax=｛xj：d（xj-ymax）≤d（xj-yl）｝，對(duì)任意l=1，2，…，N。在smax中找出 p個(gè)相互之間歐式距離較大的訓(xùn)練矢量xq，由這 p個(gè)xq和‖sj‖＞2的yi組成二級(jí)初始碼書(shū)n=｛yi：i=1，2，…，N｝。

計(jì)算總平均失真：

（9）如果Dn-1-Dn≤ε停止；n為最終碼本；否則繼續(xù)。

式中：‖sj‖表示sj中訓(xùn)練樣本向量的個(gè)數(shù)，如果‖sj‖=0，則令（sj）=yj，即碼字不變。

3　碼本均衡實(shí)驗(yàn)

3.1實(shí)驗(yàn)過(guò)程和結(jié)果

為了證明碼本均衡算法對(duì)提高圖像壓縮率的有效性，本文對(duì)一幅128×128的lena灰度圖像進(jìn)行了實(shí)際的碼本均衡壓縮；為了計(jì)算碼書(shū)，在網(wǎng)上隨機(jī)選取了100幅圖片，并將圖片處理成128×128的灰度圖像，然后將處理后的圖像作為訓(xùn)練圖像。實(shí)驗(yàn)結(jié)果如下：

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

圖1　lena圖像

圖2　碼本長(zhǎng)度為1 024的壓縮結(jié)果

圖3　碼本長(zhǎng)度為256的壓縮結(jié)果（LBG算法）

圖4　碼本長(zhǎng)度為256的壓縮結(jié)果（碼本均衡算法）

3.2結(jié)果分析和結(jié)論

比較圖1和圖2以及圖1和圖3可知，作為對(duì)圖1原始圖像的恢復(fù)，圖2的圖像質(zhì)量滿足要求，但圖3的質(zhì)量與圖1相差較大，不滿足要求。原因是圖2對(duì)應(yīng)的矢量編碼碼書(shū)長(zhǎng)度為1 024，圖3對(duì)應(yīng)的矢量編碼碼書(shū)長(zhǎng)度為256，由于在碼書(shū)矢量維數(shù)相同（都為4）的情況下，較短的碼書(shū)長(zhǎng)度對(duì)圖像量化后恢復(fù)的圖像與原圖像像素總的灰度差較大，因此，圖像3的質(zhì)量較圖像2差（比如，與圖像2相比，圖像3中l(wèi)ena的頭發(fā)光滑度較差），因此，對(duì)圖像1進(jìn)行維數(shù)為4的矢量編碼，碼書(shū)長(zhǎng)度應(yīng)選擇1 024。圖像4是在圖像3的基礎(chǔ)上進(jìn)行碼本均衡壓縮。由于碼本均衡算法使解壓縮的圖像的總的量化誤差較不用碼本均衡算法解壓縮的圖像的量化誤差減小，因此，圖4的圖像質(zhì)量比圖3的圖像質(zhì)量好（比如，與圖像4比較，圖像3中l(wèi)ena的頭發(fā)光滑度較差）。且通過(guò)觀察可見(jiàn)，圖4的圖像質(zhì)量達(dá)到了圖2的圖像質(zhì)量，也滿足圖像壓縮的要求。即選擇碼書(shū)為4維且碼本長(zhǎng)度為256，通過(guò)分裂法產(chǎn)生初始碼本，通過(guò)碼本均衡算法對(duì)圖1進(jìn)行壓縮和解壓后的圖像滿足圖像壓縮要求。這樣，滿足對(duì)圖1原始圖像壓縮要求的4維碼書(shū)長(zhǎng)度由原來(lái)的1 024變到了256，由于碼書(shū)長(zhǎng)度變成原來(lái)的116，對(duì)應(yīng)的矢量量化編碼壓縮率是原來(lái)的4倍。

由這些實(shí)驗(yàn)數(shù)據(jù)得出用碼本均衡法可以提高矢量量化編碼壓縮率的結(jié)論。

4　結(jié)　語(yǔ)

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

［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參數(shù)轉(zhuǎn)換分裂矢量量化的卡爾曼后濾波增強(qiáng)方法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（10）：228-231.

［3］郭艷菊，陳雷，陳國(guó)鷹.基于改進(jìn)人工群的圖像矢量量化碼書(shū)設(shè)計(jì)算法［J］.計(jì)算機(jī)應(yīng)用，2013，33（9）：2573-2576.

［4］楊超，董世錕.矢量量化圖像壓縮方法［J］.海軍航空工程學(xué)院學(xué)報(bào)，2011，26（1）：11-14.

［5］胡云，謝俊元，王崇駿.基于組合碼字的矢量量化編碼算法［J］.南京大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，47（5）：559-565.

［6］黃榜，謝林柏.一種新的矢量量化碼書(shū)設(shè)計(jì)算法［J］.科學(xué)技術(shù)與工程，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ìn)的小波域子矢量高光譜圖像壓縮處理技術(shù)［J］.科技通報(bào)，2014，30（8）：149-151.

［9］楊淑瑩，劉旭鵬，陶沖，等.基于免疫貓群優(yōu)化算法的矢量量化的碼書(shū)設(shè)計(jì)及語(yǔ)音識(shí)別［J］.模式識(shí)別與人工智能，2014，27（7）：577-583.

［10］趙文博，王艇艇，張生，等.基于矢量量化的嬰兒哭聲識(shí)別算法［J］.微計(jì)算機(jī)信息，2011，27（4）：224-225.

［11］孫榮坤，韓紀(jì)慶.基于矢量量化的弦樂(lè)顫音自動(dòng)檢測(cè)［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（31）：199-201.

［12］劉斌，陶建華，莫福源.面向窄帶通信的極低速率語(yǔ)音編碼算法研究［J］.信號(hào)處理，2013（9）：1134-1141.

［13］楊剛，都思丹.基于矢量量化壓縮編碼的數(shù)字水?。跩］.現(xiàn)代電子技術(shù)，2014，37（1）：70-74.

Codebook equilibrium algorithm for vector coding

YANG Chao1，HE Yijun2，REN Jiancun3，SONG Jiakang4，LIU Yunfei5
（1.Department of Electronics and Information Engineering，NAAU，Yantai 264001，China；2.Unit 92853 of PLA，Huludao 125199，China；3.Department of Control Engineering，NAAU，Yantai 264001，China；4.Unit 91006 of PLA，Hefei 231600，China；5.Qingdao Branch，NAAU，Qingdao 266041，China）

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.

vector quantization；initial codebook；LBG algorithm；clustering algorithm

TN919.81-34

A

1004-373X（2016）13-0038-03

10.16652/j.issn.1004-373x.2016.13.010

2015-09-24

國(guó)家自然科學(xué)基金（61201445）

楊超（1964—），女，湖南桃源人，博士，副教授。研究方向?yàn)樾畔⑿盘?hào)處理。