1、VECTOR QUANTIZA TION矢量量化(Vector Quantization)一.矢量量化初步1. 基本原理2. 設計碼本 (LBG)3. 量化二矢量量化進一步1. 分裂矢量量化 (Splitted VQ)2. 多極矢量量化 (Cascaded VQ)3. 樹形矢量量化器4. 其它各種類型矢量量化器三. 幾個矢量量化的工程實現問題21. 分級矢量量化中的多路徑搜索問題2. 用模擬退火 (Simulated Annealing)算法訓練最佳碼本矢量量化的應用1VECTOR QUANTIZA TION一. 矢量量化初步1. 基本原理結論：在信息論中已證明，矢量量化優于標量量化。矢量量化

2、是先將 K個（K _2）個采樣值形成K維空間Rk中的一個矢量，然后將這個矢量一次進 行量化。它可以大大降低數碼率?；A是信息論的分支：率失真（畸變）理論對于一定的量化速率 R（以每個采樣信號平均所用的量化比特數來衡量，bit/采樣），量化失真D（以量化信號與原信號之間的誤差均方值和原信號均方值之比來衡量）是一定的。矢量量化總是優于標量量化的。這是因為矢量量化有效地應用了矢量中各分量間的四種相 互關聯的性質：線性依賴性，非線性依賴性，概率密度函數的形狀以及矢量維數。定義：1）源：若將M *個信號采樣組成的信源序列中每K個為一組分為 M 個隨機矢量，構成信源空間X =X1，X2,，Xm ?（ X在

3、K維歐氏空間RK中），其中第j個矢量可記為X j =洛，X2, xj， j =1,2, ,M。K'n2）子空間：把R無遺漏地劃分成N = 2個互不相交的子空間 R1, R2 / , Rn，滿足：NUs =rk丿i士Ri Rj =0, i = j3）碼本：在每個子空間Ri中找一個代表矢量 Yi，令恢復矢量集為：丫 丫，丫2,，Yn二丫也叫輸出空間、碼本或碼書（Code Book），Yi稱為碼矢（Code Vector）或碼字（Code Word），丫內矢量的數目 n ,則叫做碼本長度。4）碼本搜索：當矢量量化器輸入任意矢量Xj RK時，它首先判斷Xj屬于那個子空間，然后輸出該子空間R的代

4、表矢量丫丫 丫 RK,i =1,2,N幾矢量量化過程就是用Yj代表Xj ,即Yi =Q X j ,1乞i乞N , 1豈j乞M。式中Q為量化函數。5）完整系統：VQ編譯碼的全過程完成一個從K維歐氏空間RK到RK空間中有限子集的映射：Q : R K _： X > Y 山飛,，丫n ?。發端完成映射C:XI二訃2, N匚收端完成映射D:I > Y，矢量量化Q則是C和D的結合。圖1中給出了這種映射關系。- 編碼X > I- 解碼I t Y圖1矢量量化示意圖3VECTOR QUANTIZA TION6）矢量量化的比特率：log 2 NR 二K:log 2 N ：每個矢量所需要的編碼比特

5、數:K：每個矢量所包含的信號樣點數:K=1時,VQ退化成SQ波形量化采樣頻率為10kHz、振幅量化為16bit的語音信號的傳輸速率是： 16x10000=160,000bit/s（bps）。波形特征參數量化對階數為10、每秒100個特征矢量（如頻譜包絡參數），如振幅量化也為 16bit 的話，其傳輸速率是：16x100x10=16,000bit/s。波形特征參數矢量量化：設L = 1024 （40種語音單位，每個對應25種變形），即為了指定碼本中任意碼矢需要10bit，則對每秒100個特征矢量的傳輸需率就為 1,000bit/s。7）矢量量化的特點：壓縮能力強。一定產生失真，但失真易控制：X的

6、分類越細，失真越小。由于X j和Yj都是K計算量大：每輸入一個X j ,都要和N個Yj逐一比較，搜索出畸變最小的。維矢量，故搜索的矢量運算，工作量大。-VQ是定長碼。2. 設計碼本1）目的：在VQ中，碼本的生成是一個關鍵。若設計K維N級碼本，則要根據M L失真最小的準5VECTOR QUANTIZA TION#VECTOR QUANTIZA TION則，分別決定如何對 RK進行劃分，以得到合適的N個胞腔（Cell） Ci , 1乞i乞N ；以及求出Ci ,1乞i乞N的代表矢量Yi , 1乞i乞N。最佳量化就要滿足使其平均失真d q最小，即D Q = mind X ,Y F2）原則：最佳多維量化

7、器必須滿足K分割條件：對R的分割應滿足(Voronoi 分割)#VECTOR QUANTIZA TION#VECTOR QUANTIZA TIONR X RK : d(X ,YJ 豈 d (X ,Yj) : i = j?#VECTOR QUANTIZA TION質心（Centroid）條件：當子空間分割 X -巳固定時，Voronoi胞腔的質心就是量化器的碼字, 即Yj= E 取 X R 1矢量徒是胞腔Ci的質心。對于最佳胞腔的分割、最佳質心的計算與畸變的度量準則有關。對于均方誤差準則及加權均方誤差準則，胞腔Ci的質心Y :1YPx2XCi表示胞腔Ci中元素的個數，即胞腔 Ci中有Ci個X。矢

8、量量化由碼本丫和劃分Ri的條件唯一確定。當碼本確定后，分割就可以通過最近鄰域準則（NNR-Nearest Neighbor Rule）唯一確定。最佳量化器q的設計也就是最佳碼本 Y的設計。通常采用迭代類 聚的方法。3）訓練碼本的LBG算法Linde, Buzo和Gray將標量最優量化的 M L算法推廣到了多維空間LBG算法。圖2、圖3分別給出已知訓練序列和已知信源分布特性的算法流程圖。a）初始化條件：給出- 碼本長度N-初始碼本 Yn , &（° ）,丫（°】,，丫（° 1 計算停止門限；，01初始平均失真D ' '訓練序列 Ts Xn；

9、n =1,2,M ? M J7VECTOR QUANTIZA TION#VECTOR QUANTIZA TION（開甘算停止門限巧覺. f弊闔霜鬻翻JYi. 了疋少糾r , -1彳衛佇否是（蟻 束）圖2已知訓練序列的算法流程圖b）用碼本Yn n為已知質心，根據最佳劃分原則把訓練序列T胞腔，即= 'Xn； n = 1,2, ,M 劃分為 N 個nSjl=嘆 d（X ,Yj ）蘭 d（X ,Yj9VECTOR QUANTIZA TION#VECTOR QUANTIZA TION其中 i = j,YYj Yn ,X Ts , j =1,2, N 。c）計算平均失真與相對失真r A1 K其中

10、d Xr，Yd Xr,k，ym,kK k J_-平均失真：巾=汰囲嚴,丫是K維輸入矢量xr的量化畸變。若 6 n乞；，則停止計算，當前碼本即是設計好的碼本 Yn，否則進行d）生成新碼字-計算這時劃分的各胞腔的質心，可由下式計算F Si :集合Si中元素的個數-由這n個新質心匕（2）,丫（2廠，丫（心門構成新的碼本ynD- 設置 n=n+1-返回2）再進行計算，直到D C*）蘭E，得到所要求的碼本 Yn =Y（n N為止。4）初始碼本的生成LBG算法：總失真單調下降的算法 要求：避免陷入局部最小點 方法：a）隨機選取法b）分裂法分裂原則擾亂系數距離最大原則c）綜合法（合并法）5）失真測度1）基本

11、定義：失真測度是反映用碼字 丫代替信源矢量x所付出的代價。這種代價的統計平均值描述了矢量量化器的工作特性，即D = E d X , Q X 12）常用失真測度:平方失真測度:2 2d X,丫二 X _YXi _Yii加權平方失真測度：d(X,Y )=(X -Y J W (X -Y )W :正定加權矩陣。絕對誤差失真測度：d X,Y一丫八 Xi -Yi與被量化矢量信號意義相關的失真測度:例如反映語音譜包絡的預測 (LP)矢量，定義頻譜失真為,fl11 rd10 log 10 log d:打 °P)曰(co)式中P(.)是原始LP能量譜，F?()是量化后的LP能量譜似然比失真測度 板倉-

12、齋田失真測度3. 矢量量化的量化過程全搜索碼本中有N個碼字，每個碼字為 K維矢量,完成一次搜索的計算代價:(歐氏距離)加法：N(2K-1)次乘法:NK次比較:N-1次樹形搜索的矢量量化系統圖4-5二叉鞫捜索方法11VECTOR QUANTIZA TION#VECTOR QUANTIZA TION二叉樹或多叉樹#VECTOR QUANTIZA TION優點：降低運算量缺點：增加存儲量衰4訂三更鞫擡哄與全銀*方玉的性糜比較 11U. 比較唾算r1'1151 i * -L；.|r i最桂栓度胡L Hi ,全體:二3 a2(/-1)(-14)F_-”仝，UN :水喪中J為科本尺寸。二. 矢量量

13、化進一步分裂矢量量化（Splitted VQ） !=樹搜索矢量量化器分裂矢量量化：首先將一個K維矢量分裂成P（ P>1 ）個子矢量，然后對各個子矢量分別獨立進行矢量化。對于一個實用的 vq系統，例如用 20個比特對10個LSF進行量化。如果用全搜索方案，碼本容量 將達到220 *10 （LSF矢量為10維），無論是從碼本的存儲容量還是搜索的運算量，在現有的硬件條件下難 以實時實現。如果采用分裂矢量量化算法，將10維的LSF矢量分裂為兩個5維的矢量，分別用10比特進行VQ，這樣，碼本容量降為2* 210 *5。由此可見分裂矢量量化可以大大降低了碼本的存儲量和最佳矢量搜索的計算量。2. 多極

14、矢量量化 （Cascaded VQ）1）多級矢量量化器的構造多級矢量量化器可以較大幅度的降低矢量量化器的計算復雜度和存貯量。多級矢量量化器由碼本大小分別為N , N 2，,Nm ,的m個小碼本構成。圖4所示的是m級矢量量化器的編碼器原理圖。13VECTOR QUANTIZA TION圖4多級矢量量化器的編碼器m級矢量量化器的量化原理：第一級矢量量化器是量化原始輸入矢量X，在碼本1中找到失真最小的碼字Yi，并將其下標i編碼送到信道中。第二級量化器的輸入矢量是：原始輸入矢量X與第一級輸出矢量Y之差的誤差矢量e X -Y。 e,在碼本2中找到失真最小的碼字E j1，并將其下標jl編碼送到信道中。第三

15、級 量化器 的輸入矢 量是：第二級的 輸入矢 量ei與第二級的輸 出矢量E j1之差的誤 差矢量 e2 = e, - E j,。同樣e2在碼本3中找到失真最小的碼字E j2，并將其下標j2編碼送到信道中。依此類推，第m級量化器的輸入矢量e(m/)與第(m-1)級的輸出矢量E j(m之差的誤差矢量 e(m)=e(m<)- Ej(m)。e(mJ)在碼本m中找到失真最小的碼字Ej(1)，并將其下標j(m-1)的編碼信號送到信道中。這樣，信道中傳輸的將是i,j1,j2,jm等下標的編碼信號。m這m個小碼本，等價于一個 碼本尺寸為N二 Ni的全搜索矢量量化器的碼本，并稱此全搜索矢i =1量量化器為

16、與此m級矢量量化器相當的量化器。2) 多級矢量量化器碼本的設計多級矢量量化器各級碼本設計仍可采用LBG算法，只是訓練序列有所不同。下面給出一個m級矢量量化器的碼本設計算法。(a)第一級碼本設計設第一級碼本大小為 N1，訓練序列TS的長度為M (即有M個訓練矢量)。采用 LBG算法進行計算，得到第一級碼本Yj(i =1,2,，N1)。(b)第二及多級碼本設計第二級碼本仍按 LBG算法進行設計。不過它的訓練序列是第一級矢量量化器的誤差信號e1長度仍為M。同樣用LBG算法進行類聚、遞歸，得到第二級碼本的N2個碼字Eji(j =1,2,., N 2)。余者類推。例如設計一個 LSF參數的三級矢量量化器

17、：在實際算法中，采用16萬幀以上的訓練序列 TS進行訓練，三級矢量量化，分別是7比特，7比特和6比特。同樣用20比特對LSF矢量進行編碼，碼本容量降為(27 +27 +26)*10,相對于分裂矢量量化，存儲量降低了 60%，相應的搜索計算量也大大減少。而合成語音質量與相同比特的分裂矢量量化基本相當。多級矢量量化系統無論在減少搜索計算量方面，還是減少碼本儲存量方面都有可觀的改進。3. 模糊矢量量化減少碼本的量化誤差模糊聚類(Fuzzy Clustering)模糊k均值聚類，隸屬度函數4. 其它各種類型矢量量化器全搜索矢量量化器sparsity)o 節約計算量(稀疏碼本 o 節約存儲量固定預測矢量

18、量化器乘積碼矢量量化器o 增益/o 均值/自適應矢量量化器自適應預測矢量量化器三. 幾個矢量量化的工程實現問題1. 分級矢量量化中的多路徑搜索問題在分級矢量量化中，每一級量化過程都是在所定義的最小誤差意義下最優的。但多級量化作為一個整體并 不一定是最優的。然而要用全路徑搜索的方法找出全局最優，運算量巨大。現階段的硬件無法滿足實時運 算的要求。所以工程上采用搜索路徑數為 M的部分路徑搜索分級矢量量化。例如：1) 在第一級搜索中找到誤差測度最小的M個碼字，并保留對應的 M個誤差矢量。2) 在第二級搜索中分別以這 M個誤差矢量為輸入矢量，分別進行碼本搜索。找到并保留M個(輸入 誤差矢量、碼字和輸出誤

19、差矢量)搜索路徑，這些路徑所對應的誤差測度也是最小的。3) 整個分級搜索完成時，就保留了M條完整的從第一級到最后一級的搜索路徑。從中挑選一條最終誤差測度最小的路徑上的碼字序列作為分級矢量量化的輸出。以4級，每級碼本大小為128,搜索路徑數為8為例。共要進行128+8*128*3=3200次誤差測度計算， 而傳 統搜索需要128*4=512次誤差測度計算。以部分增加計算量為代價從工程上逼近全局最優量化。2. 用模擬退火(Simulated Annealing)算法訓練最佳碼本2VQ碼本的形成也是一個優化問題。就是通過一種迭代預算使對全部訓練矢量而言的平均量化畸變(目標 函數)達到最小值。但這個目

20、標函數在由 M個碼字矢量構成的狀態空間中是一個非凸函數，它有很多極小值，其中一個是全局最小值，其它都是局部最小值。由于LBG算法中每次迭代目標函數總是下降的，是一種最陡下降算法(Steepest descend Algorithm)。LBG迭代預算的結果是目標函數落入哪一個極小值取決于 碼本中碼字矢量初值的設置。工程上很難保證LBG算法給出的結果達到目標函數的全局最小點。解決這一問題的一種方法，可以形象的表示為，將系統狀態通過加擾，從局部最小點拔出來。這種算法稱為“隨 機松弛算法”，簡記為SR算法(Stochastic Relaxation)。SR算法中最重要的是一種“模擬退火算法”，簡記為SA算法(Simulated Annealing)。SA算法能夠從理論上嚴格證明，在滿足一定條件下， 保證目標函數收斂到全局最小點的概率為1。以解碼器擾動 SA算法為例：1) 設系統的狀態(碼本內容)用S表示，系統的目標函數(平均畸變)用E表示，E是S的函數，記為E(S)。 設迭代的節拍為 m, m=1,2,3,。設第m次節拍時系統狀態為 Sm。設二(Sm)是對Sm機型某種隨機擾動后的狀態。這種擾動的