自適應模糊聚類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