论文部分内容阅读
[摘要]论述经典的LBG算法的基本原理、量化器设计的关键之处和存在的问题。以矢量量化技术在图像压缩领域的应用作为研究目标，总结分析现有典型的LBG算法，并针对LBG算法的不足，提出改进的算法，减少计算复杂度，缩短程序运行时间。通过理论推导和具体实现，证明改进方法的可行性和有效性。
[关键词]矢量量化 LBG算法
中图分类号：TP3 文献标识码：A 文章编号：1671－7597（2008）0320039－02
一、引言
矢量量化（VQ Vector Quantization）是70年代后期发展起来的一种数据压缩技术，是一种高效的有损数据压缩技术，它具有压缩比大、解码简单和失真较小等优点。其基本思想是：将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，从而压缩了数据而不损失多少信息。矢量量化是仙农信息论在信源编码理论方面的发展，它的理论基础是仙农的率失真理论，率失真理论是一个存在性定理，并非是一个构造性定理，它未给出如何构造矢量量化器的方法，矢量量化总是优于标量量化，这是因为矢量量化能有效地应用矢量中各分量之间的4种相互关联性质来消除数据中的冗余度。自从1980年提出矢量量化器（Vector Quantizater）码书设计的LBG算法以来，矢量量化（Vector Quantization）技术[Gray（1984）]已经成功地应用到图像压缩和语音编码中[1]。
二、LBG算法中最佳量化器的设计
LBG算法中的最佳矢量量化器设计的关键是最佳划分和最佳码书的设计[2]。
一是给定码书条件下，寻找信源空间的最佳划分，使平均失真最小，由码书 和NNR得最佳划分。信源空间中的任一点矢量，，如果它和码字的失真小于它和其它码字的失真，
二是在给定划分条件下，寻找最佳码书，使平均失真最小
给定了划分后为了使码书的平均失真最小，码字必须为相应划分的形心（质心），即：
式中表示选取的Y是使平均失真为最小的Y，对于一般的失真测度和信源分布，很难找到形心的计算方法。对于训练序列分布和常用的均方失真测度，形心可由下式给出：
式中 表示集合中元素的个数，即集中有 个X。
三、矢量量化器的设计算法
经典的码书设计算法是LBG算法[2]，它是Y.Linde，A.Buzo与R.M.Gray在1980年推出的，其思想是对于一个训练序列，先找出其中心，再用分裂法产生一个初始码书A^0，最后把训练序列按码书A^0中的元素分组，找出每组的中心，得到新的码书，转而把新码书作为初始码书再进行上述过程，直到满意为止。设计矢量量化器的主要任务是设计码书，在给定码书大小N的情况下，由最佳划分和最佳码书两个必要条件得到矢量量化器的设计算法，LBG算法既可用于已知信源分布特性情况，又可用于未知信源分布特性情况：
LBG算法流程描述如下：
此算法基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件，是劳埃德算法在矢量空间的推广，其特点为物理概念清晰、算法理论严密及算法实现容易。但是，它有3个主要缺点:
（1）在每次迭代的最佳划分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算。
（2）初始码书的选择影响码书训练的收敛速度和最终码书的性能。
（3）码书的自适应能力不强。
四、改进的算法
由上所述，LBG算法是一个不断迭代、不断调整聚类中心的过程，聚类速度慢，初始点的选取对聚类结果的影响大。因此，针对LBG算法的不足和图像压缩的特征，提出了另一种新算法，此算法的基本思想是求出一组领域，将相似度大的样本聚合在一起，将相似度小的样本分隔开来，达到聚类的效果。即给定一输入集
（K是n维欧式空间的点集），设K分为s个子集}
每个子集就是一个覆盖。对于领域覆盖比较少的样本点采用最短距离法（这里采用欧式距离）进行聚类，这样形成椭球形覆盖领域，即选择圆心距离最近的一对覆盖合并成一个新覆盖。计算新覆盖和其他覆盖的圆心的距离，再将距离最近的两个覆盖合并。根据实际需要，重复以上合并步骤，每次减少一个覆盖，最终得到合理的覆盖划分，且所有相似点分布在一个领域（球形或者椭球形）[4]。
按照上面的聚类准则和欧式距离函数，并根据图像压缩特点和实际处理图像的情况，归纳出如下的新算法:
（1）求所有矢量的重心，矢量重心用该矢量中所含像素点灰度值的平均值来表示。
（2）取一个矢量，求此矢量重心与其它未聚类矢量重心的距离，找出最小距离对应的矢量作为类覆盖的圆心。
（3）以这个最小距离的1.02倍作为半径r，形成一个球覆盖，即根据各矢量重心将相应的矢量归于此类，同时记录类中的个数。
（4）求这个类的质心，以此得到一个码矢量和其对应的矢量。
（5）找离当前覆盖的圆心最远的矢量作为下一步覆盖的圆心。
（6）重复（2）-（6）直到所有的样本全部覆盖结束。
（7）对于包含点比较少的覆盖采用最短距离法合并，具体步骤如下:
①对于要用最短距离法合并的覆盖，计算出两覆盖的圆心的距离。
②将离得最近的两个覆盖合并为一个新覆盖。
③更新其它覆盖与新覆盖的最短距离。
④根据实际需要，重复②、③步，确定最后的聚类数。
（8）结束。
五、测试结果与分析
实验条件:矢量维数为4，以“mandrill”作为产生码书的图像，对“Lena”进行处理。
实验环境:微型计算机:Intel P4处理器， 512MB的内存；系统:Microsoft Windows XP Profes-sional，版本2002。
编译平台:Visual C++ .NET 2003。
结果分析：通过反复实验测量，程序运行时间有明显的差异，采用LBG算法需要的时间为38.26s，而采用刚才提出的新算法只需2.28s，大约快了18倍。克服了LBG算法因迭代次数过大而导致程序运行时间长的缺点，大大地缩短了程序运行时间。这是由于此算法是在覆盖和最短距离相结合的基础上进行的，另外该算法的初始点选取对系统影响不大，具有一定的抗干扰能力。此种新算法主要解决了经典算法LBG算法难以解决的问题:初值的选取对系统的影响和聚类速度慢等问题。该算法是覆盖后求重心，再对覆盖做调整，得到新覆盖。因此，初值的选择对系统性能影响小于LBG算法对系统产生的影响；覆盖聚类大量减少了迭代次数，且只用最短距离法处理少量样本，聚类速度有较大提高。另外，覆盖聚类算法还可在事先不需知道聚类数目的情况下，根据实际需要确定聚类数目。
但通过新算法产生的码书解码出来的图像质量有明显的下降。这是主要是因为虽然覆盖聚类算法可以用较快的速度获得较合理的聚类结果，但该算法覆盖半径的确定、下一个覆盖中心的选择等问题，因此我们应该进一步对此算法的研究，以便既能缩短运行的时间，同时又能提高解码出来后图形的质量。
参考文献：
[1]赵力，语音信号处理[M].北京：机械工业出版社，2003.
[2]孙圣和、陆哲明，矢量量化技术及应用[M].北京:北京科学出版社，2002.
[3]胡征，矢量量化原理与应用[M].西安：西安电子科技大学出版社.1988.
[4]赵姝、张燕平、张铃，覆盖聚类算法[J].安徽大学学报（自然科学版），2005，29（2）.
作者简介：
孔勇平，男，助教，硕士，从事网络软件开发环境，CAD和三维设计的研究。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]矢量量化 LBG算法
中图分类号：TP3 文献标识码：A 文章编号：1671－7597（2008）0320039－02
一、引言
矢量量化（VQ Vector Quantization）是70年代后期发展起来的一种数据压缩技术，是一种高效的有损数据压缩技术，它具有压缩比大、解码简单和失真较小等优点。其基本思想是：将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，从而压缩了数据而不损失多少信息。矢量量化是仙农信息论在信源编码理论方面的发展，它的理论基础是仙农的率失真理论，率失真理论是一个存在性定理，并非是一个构造性定理，它未给出如何构造矢量量化器的方法，矢量量化总是优于标量量化，这是因为矢量量化能有效地应用矢量中各分量之间的4种相互关联性质来消除数据中的冗余度。自从1980年提出矢量量化器（Vector Quantizater）码书设计的LBG算法以来，矢量量化（Vector Quantization）技术[Gray（1984）]已经成功地应用到图像压缩和语音编码中[1]。
二、LBG算法中最佳量化器的设计
LBG算法中的最佳矢量量化器设计的关键是最佳划分和最佳码书的设计[2]。
一是给定码书条件下，寻找信源空间的最佳划分，使平均失真最小，由码书 和NNR得最佳划分。信源空间中的任一点矢量，，如果它和码字的失真小于它和其它码字的失真，
二是在给定划分条件下，寻找最佳码书，使平均失真最小
给定了划分后为了使码书的平均失真最小，码字必须为相应划分的形心（质心），即：
式中表示选取的Y是使平均失真为最小的Y，对于一般的失真测度和信源分布，很难找到形心的计算方法。对于训练序列分布和常用的均方失真测度，形心可由下式给出：
式中 表示集合中元素的个数，即集中有 个X。
三、矢量量化器的设计算法
经典的码书设计算法是LBG算法[2]，它是Y.Linde，A.Buzo与R.M.Gray在1980年推出的，其思想是对于一个训练序列，先找出其中心，再用分裂法产生一个初始码书A^0，最后把训练序列按码书A^0中的元素分组，找出每组的中心，得到新的码书，转而把新码书作为初始码书再进行上述过程，直到满意为止。设计矢量量化器的主要任务是设计码书，在给定码书大小N的情况下，由最佳划分和最佳码书两个必要条件得到矢量量化器的设计算法，LBG算法既可用于已知信源分布特性情况，又可用于未知信源分布特性情况：
LBG算法流程描述如下：
此算法基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件，是劳埃德算法在矢量空间的推广，其特点为物理概念清晰、算法理论严密及算法实现容易。但是，它有3个主要缺点:
（1）在每次迭代的最佳划分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算。
（2）初始码书的选择影响码书训练的收敛速度和最终码书的性能。
（3）码书的自适应能力不强。
四、改进的算法
由上所述，LBG算法是一个不断迭代、不断调整聚类中心的过程，聚类速度慢，初始点的选取对聚类结果的影响大。因此，针对LBG算法的不足和图像压缩的特征，提出了另一种新算法，此算法的基本思想是求出一组领域，将相似度大的样本聚合在一起，将相似度小的样本分隔开来，达到聚类的效果。即给定一输入集
（K是n维欧式空间的点集），设K分为s个子集}
每个子集就是一个覆盖。对于领域覆盖比较少的样本点采用最短距离法（这里采用欧式距离）进行聚类，这样形成椭球形覆盖领域，即选择圆心距离最近的一对覆盖合并成一个新覆盖。计算新覆盖和其他覆盖的圆心的距离，再将距离最近的两个覆盖合并。根据实际需要，重复以上合并步骤，每次减少一个覆盖，最终得到合理的覆盖划分，且所有相似点分布在一个领域（球形或者椭球形）[4]。
按照上面的聚类准则和欧式距离函数，并根据图像压缩特点和实际处理图像的情况，归纳出如下的新算法:
（1）求所有矢量的重心，矢量重心用该矢量中所含像素点灰度值的平均值来表示。
（2）取一个矢量，求此矢量重心与其它未聚类矢量重心的距离，找出最小距离对应的矢量作为类覆盖的圆心。
（3）以这个最小距离的1.02倍作为半径r，形成一个球覆盖，即根据各矢量重心将相应的矢量归于此类，同时记录类中的个数。
（4）求这个类的质心，以此得到一个码矢量和其对应的矢量。
（5）找离当前覆盖的圆心最远的矢量作为下一步覆盖的圆心。
（6）重复（2）-（6）直到所有的样本全部覆盖结束。
（7）对于包含点比较少的覆盖采用最短距离法合并，具体步骤如下:
①对于要用最短距离法合并的覆盖，计算出两覆盖的圆心的距离。
②将离得最近的两个覆盖合并为一个新覆盖。
③更新其它覆盖与新覆盖的最短距离。
④根据实际需要，重复②、③步，确定最后的聚类数。
（8）结束。
五、测试结果与分析
实验条件:矢量维数为4，以“mandrill”作为产生码书的图像，对“Lena”进行处理。
实验环境:微型计算机:Intel P4处理器， 512MB的内存；系统:Microsoft Windows XP Profes-sional，版本2002。
编译平台:Visual C++ .NET 2003。
结果分析：通过反复实验测量，程序运行时间有明显的差异，采用LBG算法需要的时间为38.26s，而采用刚才提出的新算法只需2.28s，大约快了18倍。克服了LBG算法因迭代次数过大而导致程序运行时间长的缺点，大大地缩短了程序运行时间。这是由于此算法是在覆盖和最短距离相结合的基础上进行的，另外该算法的初始点选取对系统影响不大，具有一定的抗干扰能力。此种新算法主要解决了经典算法LBG算法难以解决的问题:初值的选取对系统的影响和聚类速度慢等问题。该算法是覆盖后求重心，再对覆盖做调整，得到新覆盖。因此，初值的选择对系统性能影响小于LBG算法对系统产生的影响；覆盖聚类大量减少了迭代次数，且只用最短距离法处理少量样本，聚类速度有较大提高。另外，覆盖聚类算法还可在事先不需知道聚类数目的情况下，根据实际需要确定聚类数目。
但通过新算法产生的码书解码出来的图像质量有明显的下降。这是主要是因为虽然覆盖聚类算法可以用较快的速度获得较合理的聚类结果，但该算法覆盖半径的确定、下一个覆盖中心的选择等问题，因此我们应该进一步对此算法的研究，以便既能缩短运行的时间，同时又能提高解码出来后图形的质量。
参考文献：
[1]赵力，语音信号处理[M].北京：机械工业出版社，2003.
[2]孙圣和、陆哲明，矢量量化技术及应用[M].北京:北京科学出版社，2002.
[3]胡征，矢量量化原理与应用[M].西安：西安电子科技大学出版社.1988.
[4]赵姝、张燕平、张铃，覆盖聚类算法[J].安徽大学学报（自然科学版），2005，29（2）.
作者简介：
孔勇平，男，助教，硕士，从事网络软件开发环境，CAD和三维设计的研究。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”