自適應(yīng)模糊聚類LBG矢量量化算法

孫 燕

青海民族大學(xué) 計(jì)算機(jī)學(xué)院，西寧 810007

自適應(yīng)模糊聚類LBG矢量量化算法

孫 燕

青海民族大學(xué) 計(jì)算機(jī)學(xué)院，西寧 810007

1 引言

LBG-VQ算法[1]能找出使矢量量化誤差達(dá)到最小的矢量中心集，這個(gè)中心集就是最佳碼本。傳統(tǒng)的LBG-VQ算法是硬聚類算法[2-3]，一個(gè)樣本僅僅屬于某一個(gè)類，量化后碼本尺寸大小固定，如果碼本尺寸巨大，存儲(chǔ)量顯而易見。模糊C-均值聚類算法（Fuzzy C-means，F(xiàn)CM）允許樣本以不同的隸屬程度分別屬于不同的類[4]，本文在傳統(tǒng)LBG-VQ算法確定的矢量中心集時(shí)，采用模糊聚類FCM改進(jìn)確定，自適應(yīng)確定型心，使碼本尺寸顯著減小。

2 LBG算法

LBG算法是矢量量化碼本訓(xùn)練的傳統(tǒng)算法，由Lindey，Buzo，Gray三人最先提出來的[1，5]。LBG算法描述如下：

（1）已知碼書尺寸M，給定設(shè)計(jì)的失真閾值即停止門限 ε(0＜ε＜1)，給定一個(gè)出示碼書。已知一個(gè)訓(xùn)練序列 [Xj，j=0，1，…，m-1]。先取 n=0（n 為迭代次數(shù)），并設(shè)出示平均失真

（2）用給定的碼本YM，求出平均失真最小條件下的所有區(qū)域邊界Si(i=1，2，…，M)。即根據(jù)最佳劃分準(zhǔn)則把訓(xùn)練序列劃分為M個(gè)胞腔。應(yīng)該用訓(xùn)練序列Xj∈Si，使 d(Xj，Yi)＜d(Xj，Y)(Y∈YM)，從而得出最佳區(qū)域邊界然后，計(jì)算在該區(qū)域下訓(xùn)練序列的平均失真D(n)=在這一步中要累計(jì)最小失真并在最后計(jì)算平均失真。

（4）按前面給出的最佳碼書設(shè)計(jì)方法，計(jì)算這時(shí)劃分的各胞腔的形心，由這M個(gè)新形心構(gòu)成(n+1)次迭代的新形心。置n=n+1，返回到步驟（2）再進(jìn)行計(jì)算，直到滿足失真測度公式，得到所要求的碼書為止。

LBG算法有3個(gè)主要缺點(diǎn)：（1）碼書的自適應(yīng)性不強(qiáng)，不能根據(jù)訓(xùn)練矢量集數(shù)據(jù)的隨機(jī)分布來自適應(yīng)地取得初始碼書；（2）在每次迭代的最佳劃分階段，從碼書中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算；（3）初始碼書的選擇影響碼書訓(xùn)練的收斂速度和最終碼書的性能。

3 模糊C-均值算法

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

式中，xi為訓(xùn)練樣本；n為訓(xùn)練樣本的數(shù)目；mj為聚類中心；c為聚類數(shù)；b為控制聚類速度的參數(shù)，一般取2；μj(xi)為第i個(gè)樣本對于第 j類的隸屬度函數(shù)。算法步驟是：（1）設(shè)定聚類數(shù)目c和參數(shù)b；（2）初始化每個(gè)聚類中心mj；（3）重復(fù)下面的運(yùn)算，直到各個(gè)樣本的隸屬度值穩(wěn)定：①用當(dāng)前的聚類中心用式（2）計(jì)算隸屬度函數(shù)；②由當(dāng)前的隸屬度函數(shù)用式（1）更新計(jì)算各類聚類中心。當(dāng)算法收斂時(shí)，就得到了各類的聚類中心和各個(gè)樣本對于各類的隸屬度值，從而完成模糊聚類。

4 模糊聚類改進(jìn)的LBG算法

1973年Bezdek提出的模糊聚類C-均值聚類[6-9]是用隸屬度確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類程度的聚類算法。算法改進(jìn)是在LBG-VQ算法的第二步中，對于給定的區(qū)域邊界Si找出最佳碼本矢量 yik(i=1，2，…，M)，使平均失真最小，這里的使平均失真最小，是指求出給定區(qū)域邊界的型心，即該區(qū)域空間的幾何中心，這些型心就是最佳碼本[10-12]。即碼本中的第i個(gè)碼矢應(yīng)為：yi

模糊聚類改進(jìn)的LBG碼本[13-14]的尺寸和訓(xùn)練樣本集如下：文章的LBG初始矢量碼本[15-16]是語音MFCC參數(shù)碼本尺寸20×622。

圖1 算法原理圖

在實(shí)驗(yàn)室環(huán)境下錄制語音文件。語料為短詩；8 kHz采樣、8 bit量化、線性PCM編碼的數(shù)字語音；以syj.wav存盤，分幀提取語音MFCC參數(shù)，每幀的MFCC參數(shù)即為一矢量，建立大小為20×622的碼本訓(xùn)練樣本集。

5 算法仿真實(shí)驗(yàn)

將模糊聚類確定區(qū)域邊界中心改進(jìn)LBG算法對語音參數(shù)MFCC矢量量化進(jìn)行仿真實(shí)驗(yàn)。

實(shí)驗(yàn)用語音是syj.wav語音段，仿真結(jié)果如圖2～圖5所示。

圖2 原始語音圖

圖3 原始MFCC矩陣

圖4，圖5彩色線條的數(shù)量代表碼本尺寸，從兩圖線條的數(shù)量比較中可見，圖4的線條數(shù)量明顯小于圖5，實(shí)際FCM-LBG算法碼本尺寸是20×15，與LBG算法的碼本尺寸20×622相比，碼本尺寸大小顯著降低，碼本尺寸大小由模糊聚類算法自適應(yīng)確定。

圖4 FCM-LBG算法最佳碼本矩陣

圖5 LBG算法最佳碼本矩陣

5.1 編碼失真

通?？梢杂眉夥逍旁氡龋≒SNR）來描述矢量量化的編碼失真。即峰值信噪比，它是原失真測度與被處理失真測度之間的均方誤差相對于(2n-1)2的對數(shù)值，PSNR值越大，就代表失真越少。PSNR定義如下：

5.2 實(shí)驗(yàn)數(shù)據(jù)

表1給出了仿真實(shí)驗(yàn)在迭代過程中LBG算法和FCM-LBG算法的PSNR比較。

表1LBG與FCM-LBG的PSNR值 dB

通過比較LBG與FCM-LBG的PSNR，二者基本相近，在最后一次迭代中FCM-LBG比LBG的PSNR還要高出0.002 4 dB，可以看出FCM-LBG算法有著與傳統(tǒng)LBG算法一致量化誤差，且FCM-LBG算法的碼本尺寸較小，F(xiàn)CM-LBG較傳統(tǒng)LBG算法有著更好的性能。

6 結(jié)論

將模糊聚類作為求解區(qū)域邊界中心改進(jìn)LBG算法，將語音MFCC參數(shù)矢量量化，對此算法仿真，結(jié)果表明：在量化誤差一致的情況下FCM-LBG算法具有自適應(yīng)確定碼本大小碼，碼本尺寸顯著降低，減小了碼本的存儲(chǔ)量效果。

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

[2]侯波，普運(yùn)偉.基于模糊聚類的矢量量化的聲紋識(shí)別研究[J].昆明理工大學(xué)學(xué)報(bào)：理工版，2010，35（5）：56-59.

[3]邊肇褀，張學(xué)工.模式識(shí)別[M].2版.北京：清華大學(xué)出版社，2005：234-283.

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

[5]王炳錫.語音編碼[M].西安：西安電子科技大學(xué)出版社，2003：275-293.

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

[7]樓順天，胡昌華，張偉.基于MATLAB的系統(tǒng)分析與設(shè)計(jì)——模糊系統(tǒng)[M].西安：西安電子科技大學(xué)出版社，2001.

[8]裴繼紅，范九倫，謝維信.一種新的高效軟聚類方法：截集模糊c-均值聚類算法[J].電子學(xué)報(bào)，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均值聚類確定型心改進(jìn)LBG算法，實(shí)現(xiàn)語音參數(shù)MFCC碼本的矢量量化，實(shí)驗(yàn)結(jié)果表明，該算法有著與單一LBG算法相近的量化誤差，自適應(yīng)確定碼本大小碼，碼本尺寸顯著降低，減小碼本的存儲(chǔ)量。

LBG算法；自適應(yīng)；梅爾頻率倒譜系數(shù)（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網(wǎng)絡(luò)優(yōu)先出版：2013-03-21,http://www.cnki.net/kcms/detail/11.2127.TP.20130321.0939.008.html