矢量量化图像压缩方法

杨 超，董世锟

（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.