码本均衡矢量编码算法

杨　超，贺一君，任建存，宋家康，刘云飞

（1.海军航空工程学院 电子信息工程系，山东 烟台　264001；2.中国人民解放军92853部队，辽宁 葫芦岛　125199；3.海军航空工程学院 控制工程系，山东 烟台　264001；4.中国人民解放军91006部队，安徽 合肥　231600；5.海军航空工程学院 青岛校区，山东 青岛　266041）

码本均衡矢量编码算法

杨超1，贺一君2，任建存3，宋家康4，刘云飞5

（1.海军航空工程学院 电子信息工程系，山东 烟台264001；2.中国人民解放军92853部队，辽宁 葫芦岛125199；3.海军航空工程学院 控制工程系，山东 烟台264001；4.中国人民解放军91006部队，安徽 合肥231600；5.海军航空工程学院 青岛校区，山东 青岛266041）

提高矢量编码的压缩率是矢量编码的一个重要研究方向。提出一种提高矢量编码压缩率的码本均衡算法。它是对LBG算法得到的码本进行修正，将胞腔矢量个数较小的聚类矢量用胞腔矢量个数较大的胞腔矢量取而代之，以此完成再生初始矢量的选择，然后再用LBG算法进行压缩，该算法以较短的码本长度完成矢量压缩，从而提高了压缩率。给出了码本均衡算法的思想和具体算法步骤，仿真结果证明了该方法的有效性。

矢量量化；初始码书；LBG算法；聚类算法

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算法的思想是：对于一个训练序列，先找出其中心，再用分裂法产生一个初始码书0，再把训练序列按码书0中的元素分组，对这一分组再找每组的中心得到新的码书，转而把新码书作为初始码书再进行上述过程，直至满意为止。

研究用分裂法选取初始码本的LBG算法对图像压缩发现，有些胞腔矢量数较少或为零，对应的聚类矢量在图像量化中没有用到，显然不合理；对应胞腔矢量数较少的聚类矢量，在图像量化中用到的概率也较小。码本均衡法的思想是：把胞腔矢量数为零或较小的聚类矢量重新赋值，使它们等于胞腔矢量个数较多的胞腔矢量值，并和其余聚类矢量一并做为一组再生初始码本，用LGB算法重新计算最终码本，并以最终码本重新划分图像灰度矢量空间，则胞腔矢量的最小值将增加，总的图像矢量量化误差将减小，图像质量将会提高，进而以较短的码本长度达到（用LBG算法时的）用较长的码本长度计算的图像压缩质量，由于码本长度减小，使图像矢量编码压缩率提高。更进一步地说，无论是否用分裂法产生初始码本和是否用LBG法产生最终码书，只要胞腔矢量数很小时，都可以用码本均衡法对码本进行进一步修正，以减小满足图像质量要求的码书长度，进而提高图像压缩率。

2　码本均衡矢量编码算法步骤

根据码本均衡算法思想，设计的码本均衡算法如下：

（1）初始化：给定技术N，失真阈值ε，一个训练序列 ｛xj：j=0，1，2，…，m-1｝，某个初始 N级码本0=｛yi：i=1，2，…，N｝，令n=0，D-1=∞。

计算总平均失真：

（3）如果Dn-1-Dn≤ε，转步骤（6）；否则继续。

式中：‖sj‖表示 sj中训练样本向量的个数。如果‖sj‖=0，则令（sj）=yj，即码字不变。

（7）找出最大的‖sj‖对应的序列号max和对应序列空间的训练样本 smax=｛xj：d（xj-ymax）≤d（xj-yl）｝，对任意l=1，2，…，N。在smax中找出 p个相互之间欧式距离较大的训练矢量xq，由这 p个xq和‖sj‖＞2的yi组成二级初始码书n=｛yi：i=1，2，…，N｝。

计算总平均失真：

（9）如果Dn-1-Dn≤ε停止；n为最终码本；否则继续。

式中：‖sj‖表示sj中训练样本向量的个数，如果‖sj‖=0，则令（sj）=yj，即码字不变。

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。

图1　lena图像

图2　码本长度为1 024的压缩结果

图3　码本长度为256的压缩结果（LBG算法）

图4　码本长度为256的压缩结果（码本均衡算法）

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，由于码书长度变成原来的116，对应的矢量量化编码压缩率是原来的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.

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

国家自然科学基金（61201445）

杨超（1964—），女，湖南桃源人，博士，副教授。研究方向为信息信号处理。