一種基于模糊聚類的矢量量化碼書生成算法

張 濤，于鳳萍，張 海，韓笑青

(天津大學(xué)電子信息工程學(xué)院，天津 300072)

量化是模擬信號轉(zhuǎn)化為數(shù)字信號的必要環(huán)節(jié)，也是現(xiàn)代語音和音頻編碼中的一項(xiàng)關(guān)鍵技術(shù)．而在量化技術(shù)中，又可分為標(biāo)量量化和矢量量化[1]兩大類．由于矢量量化能夠有效地利用矢量中各個(gè)分量間的關(guān)聯(lián)性降低數(shù)據(jù)中的冗余度，因此，被廣泛應(yīng)用于要求高質(zhì)量、高編碼效率的數(shù)字語音頻編碼領(lǐng)域．

在矢量量化中，碼書的設(shè)計(jì)至關(guān)重要，碼書的質(zhì)量對整個(gè)語音頻編解碼系統(tǒng)的編碼效率和恢復(fù)信號的質(zhì)量有著決定性的作用．LBG算法 1980年由Linde等[2]提出，是經(jīng)典的碼書設(shè)計(jì)算法之一，其本身是一種迭代算法．近些年來，以成對最近鄰(pariwise nearest neighbor，PNN)算法和漸進(jìn)構(gòu)造聚類(progressive constructive clustering，PCC)算法為代表的一些非迭代的碼書生成算法也得到了迅猛的發(fā)展．此外，各種基于數(shù)學(xué)的方法，比如基于神經(jīng)網(wǎng)絡(luò)的碼書設(shè)計(jì)方法[3]、基于主分量分析的碼書設(shè)計(jì)方法[4]和模擬退火碼書設(shè)計(jì)算法[5]等也得到了很大的發(fā)展．但是由于LBG算法簡單實(shí)用，而且基于LBG算法的稍許改進(jìn)也能有效提升矢量量化的性能，因此，很多學(xué)者致力于 LBG算法的改進(jìn)與優(yōu)化[6-7]，通過提升初始碼書的性能而提高最終碼書的質(zhì)量，改進(jìn)后的算法失真度降低，恢復(fù)數(shù)據(jù)的效果更好．

需指出的是，對于基于初始碼書生成矢量量化碼書的算法，初始碼書選取是生成碼書性能好壞的關(guān)鍵，不合理的初始碼書更有可能使生成的碼書陷入局部最優(yōu)，且會導(dǎo)致迭代次數(shù)增大而降低碼書生成速度．文獻(xiàn)[8]中詳細(xì)分析了 LBG算法對初始碼書的敏感度；文獻(xiàn)[9]采用模糊聚類的算法優(yōu)化了初始碼書的設(shè)計(jì)，并在圖像編碼領(lǐng)域取得了令人滿意的結(jié)果．

筆者以非迭代算法的基本思想為基礎(chǔ)，采用模糊聚類對典型的非迭代算法 PCC進(jìn)行改進(jìn)．為了獲得更具典型性的碼書，根據(jù)矢量空間的密度有效地使初始碼本的矢量在矢量空間中散開，并在稠密區(qū)域占據(jù)更多的碼矢，以更精確地劃分胞腔．與傳統(tǒng)的 LBG算法相結(jié)合能夠減少迭代次數(shù)，加快收斂速度，并使最后生成的碼書更接近全局最優(yōu)．

1 經(jīng)典的矢量量化碼書生成算法

1.1 LBG算法

最經(jīng)典的矢量量化碼書設(shè)計(jì)方法是 LBG算法，它是對 Lloyd-Max標(biāo)量量化的多維推廣．LBG算法基于最近鄰域準(zhǔn)則和質(zhì)心條件2條優(yōu)化準(zhǔn)則．對于1個(gè)訓(xùn)練序列，首先生成 1個(gè)初始碼書，按照最近鄰域準(zhǔn)則把訓(xùn)練序列按碼書中的元素分組，找出每組的質(zhì)心，得到新的碼書，將其作為新的初始碼書；重復(fù)上述過程，直到平均失真度小于預(yù)定的閾值為止．

最常用的初始碼書生成方法是隨機(jī)法，也稱為訓(xùn)練矢量集隨機(jī)抽取法．該方法的主要缺點(diǎn)有：①訓(xùn)練矢量集隨機(jī)抽取法可能會選取到非典型的矢量作為碼矢，根據(jù)最近鄰域準(zhǔn)則該胞腔只有很少矢量，而每次迭代中這些非典型矢量或非典型矢量的質(zhì)心又都被保留下來；②會造成空間的胞腔分配不均，有些分得過細(xì)，有些分得太粗．這樣都會導(dǎo)致碼書中的部分碼矢無法得到充分利用，從而影響碼書性能以及整個(gè)LBG算法的收斂速度．

文獻(xiàn)[10]介紹了一種基于迭代思想生成初始碼書的方法——分裂法．首先計(jì)算整個(gè)訓(xùn)練序列的形心Y，并把它作為碼書的第一個(gè)碼字 Y0．然后選擇擾動矢量 Delta，以{Y0-Delta，Y0+Delta}為初始碼書，利用LBG算法，設(shè)計(jì)僅有2個(gè)碼字的碼書，并以新分裂形成的2個(gè)碼字分別進(jìn)行擾動，經(jīng)再次分裂形成4個(gè)碼字.迭代進(jìn)行，直到得到所需大小的碼書為止．分裂法可以得到比隨機(jī)法性能更好的初始碼書，但是分裂法的計(jì)算量是呈指數(shù)式增長的，而且，關(guān)于如何選取最佳的擾動矢量目前尚沒有確切的理論依據(jù)，因此，無法穩(wěn)定地生成高性能的初始碼書．

1.2 非迭代碼書生成算法

近年來，又出現(xiàn)了一些非迭代的碼書生成算法．典型的非迭代算法有PNN算法和PCC算法．PNN算法[11]是一種刪除算法，它不斷地把最相近的2個(gè)腔胞合并起來，直到得到所需數(shù)目的腔胞；PCC算法[12]的特點(diǎn)在于僅對訓(xùn)練序列進(jìn)行1次掃描，漸進(jìn)地生成碼字．該算法首先以訓(xùn)練序列中第 1個(gè)矢量作為碼書，將每個(gè)輸入矢量映射到1個(gè)最近相鄰的碼字中，若其失真距離大于預(yù)先設(shè)置的閾值，并且碼書中的碼字還不夠，則該矢量被確定為新的碼字，否則與該矢量最近相鄰的碼字將被合并到最近的聚類中，計(jì)算合并后聚類的形心，將其作為調(diào)整后的碼字，重復(fù)上述操作，直至掃描完整個(gè)訓(xùn)練序列．

只使用 LBG算法，或僅僅使用非迭代算法生成的碼書質(zhì)量都不理想．雖然 LBG算法具有堅(jiān)實(shí)的理論基礎(chǔ)，且實(shí)施過程簡便實(shí)用，但是該算法對初始碼書非常敏感，雖然能夠收斂，但容易陷入局部最優(yōu)，從而導(dǎo)致碼書有“優(yōu)”、“劣”之分；而非迭代算法盡管能夠保證較快的收斂速度，但是其關(guān)鍵的閾值的選取方法又是一個(gè)因沒有理論指導(dǎo)而很難解決的問題．改進(jìn)算法的思想在第2.1節(jié)中描述．

2 基于模糊聚類的碼書生成算法

2.1 算法的基本思想

文獻(xiàn)[12]中通過自適應(yīng)調(diào)整保護(hù)區(qū)閾值的上下限，對PCC算法進(jìn)行改進(jìn)．新的碼書生成算法基于傳統(tǒng)的 LBG算法，通過優(yōu)化碼書來提高碼書質(zhì)量．優(yōu)化的碼書生成算法基于模糊聚類的思想將迭代算法(LBG算法)與非迭代算法(PCC算法)相結(jié)合以提高矢量量化的性能．

從迭代算法的角度來看，新算法通過訓(xùn)練矢量和聚類矢量之間距離門限的迭代使得初始碼書的碼字在矢量空間中按照概率密度很好地散開，并進(jìn)一步利用 LBG算法迭代生成最終的碼書，新算法的距離門限逐級迭代也有助于防止此后的LBG算法陷入局部最優(yōu)，使得設(shè)計(jì)出的碼書更加接近全局最優(yōu)．

從非迭代算法的角度來看，新算法是對 PCC算法的改進(jìn)，通過對循環(huán)逐級遞減的方式調(diào)整距離門限，不僅提高迭代的收斂速度，而且可以防止新聚類生成得太快，從而更可能得到更多有代表性的碼字．

另外，為了使生成的碼字在矢量空間中盡可能地分散開，以占據(jù)概率密度較大的區(qū)域，從而保證獲得的碼字更具代表性，最后選取碼字時(shí)，新算法采用了擇優(yōu)選取的方法：當(dāng)聚類矢量集中的矢量數(shù)量大于原定的碼書尺寸時(shí)，按照胞腔中矢量個(gè)數(shù)從大到小的順序進(jìn)行排序，選擇所需個(gè)數(shù)最大的那些腔胞作為碼字；當(dāng)聚類矢量集中的矢量數(shù)量小于原定的碼書尺寸時(shí)，則先將矢量集中的矢量全部選作碼字，然后再調(diào)整門限，進(jìn)行下一次 PCC迭代，生成新的碼字，直至碼字的數(shù)量達(dá)到要求為止．

2.2 優(yōu)化的矢量量化碼書生成算法

圖1為優(yōu)化的初始碼書生成算法的主要步驟，其中 delta為空間劃分距離門限；siz_book為待設(shè)計(jì)的碼書大?。籹iz_count為當(dāng)前生成的矢量量化碼字個(gè)數(shù)計(jì)數(shù)器；siz_plus為碼字增量計(jì)數(shù)器．

圖1 優(yōu)化的矢量量化碼書生成算法流程Fig.1 Flow chart of a novel algorithm of vector quantizetion codebook

本算法的計(jì)算過程是一個(gè)迭代的過程．

(2) PCC迭代，即先把第1個(gè)矢量放入碼書作為第 1個(gè)碼字，隨后遍歷所有矢量，凡是距碼書中每個(gè)矢量距離都大于門限delta的就作為新的碼字寫入碼書，反之進(jìn)行聚類；

(3) 如果當(dāng)前碼字siz_count加上此次循環(huán)帶來的碼字增量siz_plus超出設(shè)計(jì)所需的碼書大小siz_book，則將聚類矢量按照胞腔內(nèi)矢量的個(gè)數(shù)由大到小排序，取前siz_book-siz_count個(gè)聚類矢量作為新碼字寫入碼書，生成所需碼字個(gè)數(shù)的碼書，并盡可能地占據(jù)矢量空間密集的區(qū)域，算法結(jié)束；否則，如果當(dāng)前碼字siz_count加上此次循環(huán)帶來的碼字增量siz_plus小于所需的碼書大小siz_book，即尚未生成所需個(gè)數(shù)的碼字，那么將 siz_plus個(gè)聚類矢量作為新碼字寫入碼書，siz_count+＝siz_plus．調(diào)整距離門限delta，轉(zhuǎn)步驟(2)．

3 新的碼書生成算法在移動語音頻編碼中的應(yīng)用

近幾年，3G無線網(wǎng)絡(luò)迅速發(fā)展，手機(jī)、PDA等移動通信設(shè)備普及率越來越高，移動語音頻業(yè)務(wù)的種類、數(shù)量均日益增多．因此以 ITU的移動語音頻編碼標(biāo)準(zhǔn) AMR WB+[13]為參考，中國國家音視頻編碼標(biāo)準(zhǔn)(Audio Video Coding Standard，AVS)工作組從2005年開始制定相應(yīng)的語音頻編碼標(biāo)準(zhǔn)，被稱為AVS-M音頻，即AVS第10部分[14]．

在AMR WB+和AVS-M語音頻編碼標(biāo)準(zhǔn)中都采用了一種基于交錯(cuò)分組和幀內(nèi)預(yù)測的線譜頻率系數(shù)矢量量化技術(shù)，其中用了 5個(gè)矢量量化碼書：cb_lsf_1_3_5[1,024][3]，cb_lsf_7_9_11[512][3]，cb_lsf_13_15_2[512][3]，cb_lsf_4_6_8[512][3]，cb_lsf_10_12_14_16[512][3]．

用本訓(xùn)練方法，對每16個(gè)線譜頻率(linear spectrum frequency，LSF)構(gòu)成一個(gè)矢量進(jìn)行矢量量化．訓(xùn)練序列選用25,min、單聲道、16,kHz采樣頻率的測試序列，共產(chǎn)生131-072個(gè)LSF矢量的訓(xùn)練集．

3.1 算法效率分析

新的初始碼書生成算法與采用均勻抽取初始碼書生成算法的LBG迭代次數(shù)和信噪比對比結(jié)果如表1、圖2和圖3所示．可見在碼書大小為512和1,024的情況下，本算法相比均勻抽取初始碼書生成算法信噪比分別提高2,dB和4,dB，而迭代次數(shù)分別降低為5/17和2/3．

表1 算法迭代次數(shù)Tab.1 Iteration times of algorithm

圖2 碼書為512時(shí)新舊初始碼書方法對比Fig.2 Comparison between new and old methods when codesize is 512

圖3 碼書為1 024時(shí)新舊初始碼書方法對比Fig.3 Comparison between new and old methods when codesize is 1 024

采用新算法訓(xùn)練得到的碼書與標(biāo)準(zhǔn)中的原有碼書對比的主客觀實(shí)驗(yàn)結(jié)果如下所述．

3.2 客觀測試結(jié)果

目前所用的客觀評價(jià)方法可以分為時(shí)域客觀評價(jià)和頻域客觀評價(jià)．時(shí)域客觀評價(jià)常見的方法如信噪比，很難與人感知到的聲音質(zhì)量相匹配，因此在語音和音頻客觀質(zhì)量評價(jià)中普遍采用頻域評價(jià)方法，如譜失真[15]測度．此外，ITU-T P.862建議書提供的以客觀方法評價(jià)語音主觀質(zhì)量的方法，被稱為感知質(zhì)量評價(jià)(perceptual evaluation of speech quality，PESQ)[16]，普遍用于編解碼或系統(tǒng)評估、選擇和優(yōu)化．

在12,kb/s碼率下，對AVS音頻組規(guī)定的雙聲道16,kHz采樣的20個(gè)語音頻測試序列的客觀測試的結(jié)果如下．

3.2.1譜失真

表 2為譜失真測試結(jié)果．新碼本平均譜失真減小 0.122，2～4,dB減少 3.49%，大于 4,dB的概率幾乎為零，可見譜失真有較大改善．

表2 新算法訓(xùn)練的碼本與AVS-M碼本及AMR WB+譜失真比較Tab.2 Comparison of spectrum distortion among codebooks of new algorithm，AVS-M and AMR WB+

3.2.2ITU的PESQ語音質(zhì)量評測結(jié)果

圖4為PESQ測試結(jié)果，平均PESQ有0.028,75的提升．

圖4 PESQ語音質(zhì)量評測結(jié)果Fig.4 PESQ result

3.3 主觀測試結(jié)果

主觀評價(jià)是在一組測試者對原始語音和處理后語音進(jìn)行對比測試的基礎(chǔ)上，根據(jù)某種預(yù)先約定的尺度來對失真語音劃分質(zhì)量等級．主觀評價(jià)符合人類聽音時(shí)對語音質(zhì)量的感覺，因而得到了廣泛應(yīng)用．

對在 24,kb/s碼率下對 AVS音頻組規(guī)定的雙聲道 16,kHz采樣的 20個(gè)語音頻測試序列，按照 AVS音頻組制定的語音頻編碼標(biāo)準(zhǔn)主觀測試規(guī)范[17]，隨機(jī)選取 10名正常聽音者的主觀測試結(jié)果如圖 5所示．采用新碼本編解碼后語音頻的主觀質(zhì)量比原碼本的CMOS分值平均高0.005．

圖5 編解碼后音頻的主觀質(zhì)量比較Fig.5 Comparison of objective quality between new and old Fig.5 methods

4 結(jié) 語

本文提出了一種基于模糊聚類的新的矢量量化碼書生成算法，通過逐級調(diào)整門限以減少迭代次數(shù)，降低新聚類生成的速度，從而得到更好的更具典型性的碼書．此外，通過對胞腔中矢量按從大到小的順序擇優(yōu)選取，使得設(shè)計(jì)出的碼書性能更好，更加接近全局最優(yōu)．

本算法應(yīng)用于數(shù)字語音頻編碼的實(shí)驗(yàn)結(jié)果表明，該算法在保證語音頻編碼質(zhì)量(信噪比)的前提下能夠有效提高碼書生成速度(迭代次數(shù))；在給定編碼碼率的情況下，語音頻編碼主客觀質(zhì)量與現(xiàn)有相關(guān)語音頻編碼標(biāo)準(zhǔn)相比均有一定的提高．本算法可以廣泛應(yīng)用于數(shù)字圖像和數(shù)字音視頻編碼中的矢量量化．

［1］Vasuki A，Vanathi P T. A review of vector quantization techniques [J]. IEEE Potentials，2006，25(4)：39-47.

［2］Linde Y，Buzo A，Gray R. An algorithm for vector quantizer design[J].IEEE Transactions on Communications，1980，28(1)：84-95.

［3］Krishnamarthy A，Ahalt S，Melton E，et al. Neural networks for vector quantization of speech and images[J].Neural Networks，1990，3(3)：277-290.

［4］Chang C，Lin D，Chen T. An improved VQ codebook search algorithm using principal component analysis[J].Journal of Visual Communication and Image Representation，1997，8(1)：27-37.

［5］Fabian V. Simulated annealing simulated[J].Computers Math Application，1997，33(1/2)：81-94.

［6］Franti P，Kaukoranta T，Shen D-F. Fast and memory efficient implementation of the exact PNN[J].IEEE Transactions on Image Processing，2000，9(5)：773-777.

［7］吳婷婷，曾毓敏，李 平. 利用PNN算法改進(jìn)初始碼書的GLA 算法[J]. 數(shù)據(jù)采集與處理，2007，22(2)：242-244.

Wu Tingting，Zeng Yumin，Li Ping. GLA algorithm for ameliorated original codebook using PNN algorithm[J].Journal of Data Acquisition and Processing，2007，22(2)：242-244(in Chinese).

［8］王茂芝，徐文皙. LBG算法對初始碼書敏感的實(shí)驗(yàn)性能分析[J]. 物探化探計(jì)算技術(shù)，2004，26(4)：374-378.

Wang Maozhi，Xu Wenxi. Experiment performance analysis on sensitivity to initial codebook of LBG[J].Computing Techniques for Geophysical and Geochemical Exploration，2004，26(4)：374-378(in Chinese).

［9］張 濤，于鳳萍，要 強(qiáng)，等. 高效的模糊聚類初始碼書生成算法[J]. 紅外與激光工程，2010，39(1)：179-183.

Zhang Tao，Yu Fengping，Yao Qiang，et al. Novel and efficient generation algorithm of initial codebook based on the fuzzy clustering theory[J]. Infrared and Laser Engineering，2010，39(1)：179-183(in Chinese).

［10］George L，Al-Abudi B. Fast multi-level image vector quantization[C]//Proceedings of IEEE International Conference on Signal Processing and Communications.Dubai，United Arab Emirates， 2007：121-124.

［11］韓俊萍，程培巖. 模糊聚類法實(shí)現(xiàn)初始碼書的優(yōu)化[J].科技情報(bào)開發(fā)與經(jīng)濟(jì)，2006，16(11)：157-158，161.

Han Junping，Cheng Peiyan. Realize the optimization of the initial codebook by using the fuzzy clustering method[J].Sci-Tech Information Development and Economy，2006，16(11)：157-158，161(in Chinese).

［12］張 一，成禮智. 結(jié)合改進(jìn)的PCC算法與LBG算法的高效碼書設(shè)計(jì)[J]. 系統(tǒng)工程與電子技術(shù)，2006，28(3)：470-473.

Zhang Yi，Cheng Lizhi. Efficient algorithm for codebook design based on improved PCC algorithm and improved LBG algorithm[J].System Engineering and Electronics，2006，28(3)：470-473(in Chinese).

［13］3GPP. TS 26. 290 Extended Adaptive Multi-Rate-Wideband(AMR-WB+),Codec；Transcoding Functions(Release 6)[S]. France：3GPP，2006.

［14］AVS. AVS-P10 Mobile Speech and Audio Coding Standard[S]. China：AVS，2009.

［15］Norden F，Eriksson T. A speech spectrum distortion measure with interframe memory[C]//Proceedings of IEEE International Conference on Acoustics，Speech and Signal Processing. Salt Lake，USA，2001：717-720.

［16］International Telecommunication Union. ITU-T P. 826 An Objective Method for End-to-End Speech Quality Assessment of Narrow-Band Telephone Networks and Speech Coder[S]. USA：ITU，2007.

［17］AVS. AVS音頻內(nèi)部主管聽力測試參考規(guī)范[S]. 中國：AVS，2005.

AVS. Reference Rules for AVS Audio Objective Quality Evaluation[S]. China：AVS，2005(in Chinese).