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

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

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

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

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

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

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

1.1 LBG算法

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

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

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

1.2 非迭代碼書(shū)生成算法

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

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

2 基于模糊聚類(lèi)的碼書(shū)生成算法

2.1 算法的基本思想

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

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

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

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

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

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

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

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

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

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

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

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

在A(yíng)MR WB+和AVS-M語(yǔ)音頻編碼標(biāo)準(zhǔn)中都采用了一種基于交錯(cuò)分組和幀內(nèi)預(yù)測(cè)的線(xiàn)譜頻率系數(shù)矢量量化技術(shù)，其中用了 5個(gè)矢量量化碼書(shū)：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)練方法，對(duì)每16個(gè)線(xiàn)譜頻率(linear spectrum frequency，LSF)構(gòu)成一個(gè)矢量進(jìn)行矢量量化．訓(xùn)練序列選用25,min、單聲道、16,kHz采樣頻率的測(cè)試序列，共產(chǎn)生131-072個(gè)LSF矢量的訓(xùn)練集．

3.1 算法效率分析

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

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

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

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

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

3.2 客觀(guān)測(cè)試結(jié)果

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

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

3.2.1譜失真

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

表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語(yǔ)音質(zhì)量評(píng)測(cè)結(jié)果

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

圖4 PESQ語(yǔ)音質(zhì)量評(píng)測(cè)結(jié)果Fig.4 PESQ result

3.3 主觀(guān)測(cè)試結(jié)果

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

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

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

4 結(jié) 語(yǔ)

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

本算法應(yīng)用于數(shù)字語(yǔ)音頻編碼的實(shí)驗(yàn)結(jié)果表明，該算法在保證語(yǔ)音頻編碼質(zhì)量(信噪比)的前提下能夠有效提高碼書(shū)生成速度(迭代次數(shù))；在給定編碼碼率的情況下，語(yǔ)音頻編碼主客觀(guān)質(zhì)量與現(xiàn)有相關(guān)語(yǔ)音頻編碼標(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)初始碼書(shū)的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算法對(duì)初始碼書(shū)敏感的實(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)，等. 高效的模糊聚類(lèi)初始碼書(shū)生成算法[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］韓俊萍，程培巖. 模糊聚類(lèi)法實(shí)現(xiàn)初始碼書(shū)的優(yōu)化[J].科技情報(bào)開(kāi)發(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ū)設(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)部主管聽(tīng)力測(cè)試參考規(guī)范[S]. 中國(guó)：AVS，2005.

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