自适应模糊聚类LBG矢量量化算法

孙 燕

青海民族大学 计算机学院，西宁 810007

自适应模糊聚类LBG矢量量化算法

孙 燕

青海民族大学 计算机学院，西宁 810007

1 引言

LBG-VQ算法[1]能找出使矢量量化误差达到最小的矢量中心集，这个中心集就是最佳码本。传统的LBG-VQ算法是硬聚类算法[2-3]，一个样本仅仅属于某一个类，量化后码本尺寸大小固定，如果码本尺寸巨大，存储量显而易见。模糊C-均值聚类算法（Fuzzy C-means，FCM）允许样本以不同的隶属程度分别属于不同的类[4]，本文在传统LBG-VQ算法确定的矢量中心集时，采用模糊聚类FCM改进确定，自适应确定型心，使码本尺寸显著减小。

2 LBG算法

LBG算法是矢量量化码本训练的传统算法，由Lindey，Buzo，Gray三人最先提出来的[1，5]。LBG算法描述如下：

（1）已知码书尺寸M，给定设计的失真阈值即停止门限 ε(0＜ε＜1)，给定一个出示码书。已知一个训练序列 [Xj，j=0，1，…，m-1]。先取 n=0（n 为迭代次数），并设出示平均失真

（2）用给定的码本YM，求出平均失真最小条件下的所有区域边界Si(i=1，2，…，M)。即根据最佳划分准则把训练序列划分为M个胞腔。应该用训练序列Xj∈Si，使 d(Xj，Yi)＜d(Xj，Y)(Y∈YM)，从而得出最佳区域边界然后，计算在该区域下训练序列的平均失真D(n)=在这一步中要累计最小失真并在最后计算平均失真。

（4）按前面给出的最佳码书设计方法，计算这时划分的各胞腔的形心，由这M个新形心构成(n+1)次迭代的新形心。置n=n+1，返回到步骤（2）再进行计算，直到满足失真测度公式，得到所要求的码书为止。

LBG算法有3个主要缺点：（1）码书的自适应性不强，不能根据训练矢量集数据的随机分布来自适应地取得初始码书；（2）在每次迭代的最佳划分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算；（3）初始码书的选择影响码书训练的收敛速度和最终码书的性能。

3 模糊C-均值算法

模糊C均值聚类算法原理是求解式（1）、（2）。

式中，xi为训练样本；n为训练样本的数目；mj为聚类中心；c为聚类数；b为控制聚类速度的参数，一般取2；μj(xi)为第i个样本对于第 j类的隶属度函数。算法步骤是：（1）设定聚类数目c和参数b；（2）初始化每个聚类中心mj；（3）重复下面的运算，直到各个样本的隶属度值稳定：①用当前的聚类中心用式（2）计算隶属度函数；②由当前的隶属度函数用式（1）更新计算各类聚类中心。当算法收敛时，就得到了各类的聚类中心和各个样本对于各类的隶属度值，从而完成模糊聚类。

4 模糊聚类改进的LBG算法

1973年Bezdek提出的模糊聚类C-均值聚类[6-9]是用隶属度确定每个数据点属于某个聚类程度的聚类算法。算法改进是在LBG-VQ算法的第二步中，对于给定的区域边界Si找出最佳码本矢量 yik(i=1，2，…，M)，使平均失真最小，这里的使平均失真最小，是指求出给定区域边界的型心，即该区域空间的几何中心，这些型心就是最佳码本[10-12]。即码本中的第i个码矢应为：yi

模糊聚类改进的LBG码本[13-14]的尺寸和训练样本集如下：文章的LBG初始矢量码本[15-16]是语音MFCC参数码本尺寸20×622。

图1 算法原理图

在实验室环境下录制语音文件。语料为短诗；8 kHz采样、8 bit量化、线性PCM编码的数字语音；以syj.wav存盘，分帧提取语音MFCC参数，每帧的MFCC参数即为一矢量，建立大小为20×622的码本训练样本集。

5 算法仿真实验

将模糊聚类确定区域边界中心改进LBG算法对语音参数MFCC矢量量化进行仿真实验。

实验用语音是syj.wav语音段，仿真结果如图2～图5所示。

图2 原始语音图

图3 原始MFCC矩阵

图4，图5彩色线条的数量代表码本尺寸，从两图线条的数量比较中可见，图4的线条数量明显小于图5，实际FCM-LBG算法码本尺寸是20×15，与LBG算法的码本尺寸20×622相比，码本尺寸大小显著降低，码本尺寸大小由模糊聚类算法自适应确定。

图4 FCM-LBG算法最佳码本矩阵

图5 LBG算法最佳码本矩阵

5.1 编码失真

通常可以用尖峰信噪比（PSNR）来描述矢量量化的编码失真。即峰值信噪比，它是原失真测度与被处理失真测度之间的均方误差相对于(2n-1)2的对数值，PSNR值越大，就代表失真越少。PSNR定义如下：

5.2 实验数据

表1给出了仿真实验在迭代过程中LBG算法和FCM-LBG算法的PSNR比较。

表1LBG与FCM-LBG的PSNR值 dB

通过比较LBG与FCM-LBG的PSNR，二者基本相近，在最后一次迭代中FCM-LBG比LBG的PSNR还要高出0.002 4 dB，可以看出FCM-LBG算法有着与传统LBG算法一致量化误差，且FCM-LBG算法的码本尺寸较小，FCM-LBG较传统LBG算法有着更好的性能。

6 结论

将模糊聚类作为求解区域边界中心改进LBG算法，将语音MFCC参数矢量量化，对此算法仿真，结果表明：在量化误差一致的情况下FCM-LBG算法具有自适应确定码本大小码，码本尺寸显著降低，减小了码本的存储量效果。

[1]Linde Y，Buzo A，Gray R M.An algorithm for vector quantizerdesign[J].IEEE Transactionson Communications，1980，28（1）：84-95.

[2]侯波，普运伟.基于模糊聚类的矢量量化的声纹识别研究[J].昆明理工大学学报：理工版，2010，35（5）：56-59.

[3]边肇褀，张学工.模式识别[M].2版.北京：清华大学出版社，2005：234-283.

[4]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].New York：Plenum Press，1981.

[5]王炳锡.语音编码[M].西安：西安电子科技大学出版社，2003：275-293.

[6]Dunn J C.Well separated clusters and optimal fuzzy partitions[J].JCybernet，1974，4（1）：95-104.

[7]楼顺天，胡昌华，张伟.基于MATLAB的系统分析与设计——模糊系统[M].西安：西安电子科技大学出版社，2001.

[8]裴继红，范九伦，谢维信.一种新的高效软聚类方法：截集模糊c-均值聚类算法[J].电子学报，1998，26（2）：83-86.

[9]Nasser M，Nasrabad I，King R A.Summary on image coding application of vector quantization[J].IEEE Transactions on Communications，1998，36（8）：957-971.

[10]Li J H，Ling N.A novel VQ codebook design technique[J]. IEEE Trans on Consumer Electronics，1997，43（4）.

[11]Bei C，Gray R M.An improvement of the minimum distortion encoding algorithm for vector quantization[J]. IEEE Trans on Commun，1985，33：1132-1133.

[12]Huang H，Chen S H.Fast encoding algorithm for VQ-based imagecoding[J].ElectronicsLetters，1990，26：1618-1619.

[13]Ra S W，Kim J K.A fast mean-distance-ordered partial codebook search algorithm for image vector quantization[J].IEEE Trans on Circuits and Systems-II：Analog and Digital Signal Processing，1993，40（9）：576-579.

[14]Chang C C，Lin D C，Chen T S.An improved VQ codebook search algorithm using principal component analysis[J].Journal of Visual Communication and Image Representation，1997，8（1）：27-37.

[15]Chang C C，Chang R F，Lee W T，et al.Fast algorithmsforvectorquantization[J].JournalofInformation Science and Engineering，1996，12（4）：593-602.

[16]Chang C C，Lee W T，Chen T S.Two improved codebook search methods of vector quantization based on orthogonal checking and fixed range search[J].Journal of Electronic Imaging，1997.

SUN Yan

School of Computer,Qinghai University for Nationalities,Xining 810007,China

In this paper,a self-adaptive fuzzy c-means clustering algorithm is proposed.It is designed to overcome the shortcomings of the traditional LBG vector-quantization algorithm.Experimental results on MFCC quantization show that the proposed algorithm has similar quantization error compared to the classic LBG algorithm while significantly reducing codebook size and memory footprint.

LBG algorithm;self-adaption;Mel Frequency Cepstrum Coefficient（MFCC）;fuzzy clustering;Vector Quantization（VQ）

采用模糊聚类C均值聚类确定型心改进LBG算法，实现语音参数MFCC码本的矢量量化，实验结果表明，该算法有着与单一LBG算法相近的量化误差，自适应确定码本大小码，码本尺寸显著降低，减小码本的存储量。

LBG算法；自适应；梅尔频率倒谱系数（MFCC）；模糊聚类；矢量量化

A

TP391

10.3778/j.issn.1002-8331.1301-0257

SUN Yan.Self-adaption fuzzy clustering LBG vector-quantization algorithm.Computer Engineering and Applications,2014,50（23）：203-205.

孙燕（1973—），女，副教授，主要从事语音处理和语音编码方面的研究。

2013-01-23

2013-03-11

1002-8331（2014）23-0203-03

CNKI网络优先出版：2013-03-21,http://www.cnki.net/kcms/detail/11.2127.TP.20130321.0939.008.html