第八章 矢量量化技術

1、 第七章 矢量量化技術 (vector quantization VQ)(vector quantization VQ) 7.1 概述 7.2 矢量量化的基本原理 7.3 矢量量化的失真測度 7.4 矢量量化的最佳碼本設計 7.1 概述 一、矢量量化的應用 二、標量量化和矢量量化的區(qū)別 矢量量化技術技術是一種數(shù)據(jù)壓縮和編碼技術，矢量量化技術技術是一種數(shù)據(jù)壓縮和編碼技術， 矢量量化壓縮技術的應用領域非常廣闊，如軍事部門矢量量化壓縮技術的應用領域非常廣闊，如軍事部門 和氣象部門的衛(wèi)星和氣象部門的衛(wèi)星( (或航天飛機或航天飛機) )遙感照片的壓縮編碼遙感照片的壓縮編碼 和實時傳輸、雷達圖像和軍用地圖

2、的存儲與傳輸、數(shù)和實時傳輸、雷達圖像和軍用地圖的存儲與傳輸、數(shù) 字電視和字電視和DVDDVD的視頻壓縮、醫(yī)學圖像的壓縮與存儲、的視頻壓縮、醫(yī)學圖像的壓縮與存儲、 網(wǎng)絡化測試數(shù)據(jù)的壓縮和傳輸、語音編碼、圖像識別網(wǎng)絡化測試數(shù)據(jù)的壓縮和傳輸、語音編碼、圖像識別 和語音識別等等和語音識別等等 。 一、矢量量化的應用 整個動態(tài)范圍被分成若干個小區(qū)間，每個小區(qū)間整個動態(tài)范圍被分成若干個小區(qū)間，每個小區(qū)間 有一個代表值，量化時落入小區(qū)間的信號值就用這個有一個代表值，量化時落入小區(qū)間的信號值就用這個 代表值代替，或者叫被量化為這個代表值。這時的信代表值代替，或者叫被量化為這個代表值。這時的信 號量是一維的，所

3、以稱為標量量化。號量是一維的，所以稱為標量量化。 二、標量量化和矢量量化的區(qū)別 采樣采樣量化量化 x xa a(t)(t) x xa a(nT)(nT) x(n)x(n) x xa1 a1 x x1 1x xk k x xak ak x xak+1 ak+1 x xk+1 k+1 x xL L x xaL aL x xaL+1 aL+1 x(n)=Qxx(n)=Qxa a(nT)(nT)。 1.標量量化： 2 2 - - -2-2 2 2 標量量化標量量化 1-dimensional VQ is shown below: 2. 矢量量化： 若干個標量數(shù)據(jù)組成一個矢量，若干個標量數(shù)據(jù)組成一個矢量

4、，矢量量化是矢量量化是 對矢量進行量化，和標量量化一樣，它把矢量空間對矢量進行量化，和標量量化一樣，它把矢量空間 分成若干個小區(qū)域，每個小區(qū)域?qū)ふ乙粋€代表矢量，分成若干個小區(qū)域，每個小區(qū)域?qū)ふ乙粋€代表矢量， 量化時落入小區(qū)域的矢量就用這個代表矢量代替，量化時落入小區(qū)域的矢量就用這個代表矢量代替， 或者叫著被量化為這個代表矢量。例如，所有可能或者叫著被量化為這個代表矢量。例如，所有可能 的二維矢量就構(gòu)成了一個平面，將平面分成的二維矢量就構(gòu)成了一個平面，將平面分成7 7個小個小 區(qū)域。區(qū)域。 Y Y1 1 Y Y2 2 Y Y3 3 Y Y4 4 Y Y5 5 Y Y6 6 Y Y7 7 x1 x

5、2 Y Yi i（x x1i 1i ,x ,x2i 2i） ） 假設聲道濾波器傳輸函數(shù)用假設聲道濾波器傳輸函數(shù)用4 4個系數(shù)來描述，個系數(shù)來描述， 而且，又假設聲道只能為而且，又假設聲道只能為4 4個可能的形狀之一。這個可能的形狀之一。這 意味著只存在意味著只存在4 4組可能的聲道濾波器傳輸函數(shù)。組可能的聲道濾波器傳輸函數(shù)。 現(xiàn)在考慮對每一個濾波器系數(shù)單獨進行標量量現(xiàn)在考慮對每一個濾波器系數(shù)單獨進行標量量 化，需要化，需要2bit2bit，每一分析幀需要，每一分析幀需要8 8個比特來進行編個比特來進行編 碼。碼。 3、舉例說明標量量化與矢量量化的區(qū)別、舉例說明標量量化與矢量量化的區(qū)別 如果我們

6、知道只有如果我們知道只有4 4種可能的聲道形狀，與種可能的聲道形狀，與 4 4個可能的聲道濾波器系數(shù)組成的矢量相對應，個可能的聲道濾波器系數(shù)組成的矢量相對應， 若某一個濾波器系數(shù)知道了，其它系數(shù)就知道若某一個濾波器系數(shù)知道了，其它系數(shù)就知道 了，也就是矢量中的標量值之間是高度相關的，了，也就是矢量中的標量值之間是高度相關的， 在這種情況下，一個分析幀，只需要一個在這種情況下，一個分析幀，只需要一個 2bits2bits對對4 4個濾波器系數(shù)進行編碼，這樣降低了個濾波器系數(shù)進行編碼，這樣降低了 所需的比特數(shù)。矢量量化就是利用數(shù)據(jù)之間的所需的比特數(shù)。矢量量化就是利用數(shù)據(jù)之間的 相關性來降低所需的比

7、特率。相關性來降低所需的比特率。 4.2 矢量量化的基本原理 一、矢量量化的基本原理 二、矢量量化在語音通信中的應用 三、矢量量化在語音識別中的應用 四、矢量量化的關鍵之處 1.1.基礎知識 一、矢量量化的基本原理 若干個標量數(shù)據(jù)組成一個矢量，標量的個數(shù)就為若干個標量數(shù)據(jù)組成一個矢量，標量的個數(shù)就為 矢量的維數(shù)。如語音信號某一幀中提取的聲道參數(shù)，矢量的維數(shù)。如語音信號某一幀中提取的聲道參數(shù)， 共共P P個個,X,Xi i=a=ai1 i1,a ,ai2 i2,a ,aiP iP 。則 。則X Xi i是一個是一個P P維矢量。設維矢量。設 共有共有N N個個P P維矢量維矢量X=XX=X1 1

8、,X,X2 2,X,XN N,其中第其中第i i個矢量為個矢量為X Xi i， ， i=1,2,Ni=1,2,N。類比過來，。類比過來，N N個語音幀，每幀中共有個語音幀，每幀中共有P P個個 聲道參數(shù)，共組成聲道參數(shù)，共組成N N個個P P維矢量。維矢量。 a a11 11,a ,a12 12,a ,a1K 1K a aN1 N1,a ,aN2 N2,a ,aNK NK 第第1 1幀幀第第N N幀幀 X X1 1=a=a11 11,a ,a12 12,a ,a1P 1P X X2 2=a=a21 21,a ,a22 22,.,a ,.,a2P 2P X XN N=a=aN1 N1,a ,aN

9、2 N2,.,a ,.,aNP NP N個矢量，每個矢量的維數(shù)為個矢量，每個矢量的維數(shù)為P 第一幀第一幀 第二幀第二幀 第第N幀幀 將一個將一個P維隨機矢量映射成另一個離散取值的實維隨機矢量映射成另一個離散取值的實P 維矢量的過程。維矢量的過程。 ()q XY 所有所有P P維矢量構(gòu)成了一個空間為維矢量構(gòu)成了一個空間為R RP P，無遺漏地劃，無遺漏地劃 分成分成J J個互不相交的子空間個互不相交的子空間R R1 1,R,R2 2RRJ J , ,將 將R Rj j稱為胞腔。稱為胞腔。 在每一個子空間在每一個子空間R Rj j找一代表矢量找一代表矢量Y Yj j，則，則J J個代表矢量個代表矢

10、量 可以組成矢量集為：可以組成矢量集為： Y=YY=Y1 1,Y,Y2 2,Y,YJ J 構(gòu)成了一個矢量量化器，構(gòu)成了一個矢量量化器，Y Y叫著叫著 碼本，碼本，J J稱為碼本長度稱為碼本長度, Y, Yj j稱為碼字，有：稱為碼字，有： Y Yj j=y=yj1 j1,y ,yj2 j2,y ,yjP jP ， ，j=1,2,Jj=1,2,J。 2.2.矢量空間的劃分 舉例 以以P=2P=2為例來說明。當為例來說明。當P=2P=2時，所得到的是二維時，所得到的是二維 矢量。所有可能的二維矢量就構(gòu)成了一個平面。第矢量。所有可能的二維矢量就構(gòu)成了一個平面。第 i i個二維矢量記為：個二維矢量記為

11、： X Xi i=x=xi1 i1,x ,xi2 i2 。先把這個平面 。先把這個平面 劃分成劃分成J J塊互不相交的子區(qū)域，從每個子區(qū)域中找塊互不相交的子區(qū)域，從每個子區(qū)域中找 出一個代表矢量。如出一個代表矢量。如J=7J=7。 Y Y1 1 Y Y2 2 Y Y3 3 Y Y4 4 Y Y5 5 Y Y6 6 Y Y7 7 x1 x2 碼本碼本 Y=YY=Y1 1,Y,Y2 2,Y,YJ J 碼本長度碼本長度 J=7J=7 碼字碼字 Y Yj j=x=xj1 j1,x ,xj2 j2 ， ，j=1,2,Jj=1,2,J 維數(shù)為維數(shù)為P P，碼本長度為，碼本長度為J J的矢量量化器的矢量量化

12、器Q Q定義：定義： 為從為從P P維歐幾里德空間維歐幾里德空間R RP P到一包含到一包含J J個輸出個輸出( (重構(gòu)重構(gòu)) ) 點的有限集合點的有限集合C C的映射，的映射， Q Q：R RP PCC，其中，其中C=yC=y1 1 ,y ,y2 2 , ,y , ,yJ J y yi i R RP P， ，i i1,J1,J 集合集合C C稱作稱作碼本或碼書碼本或碼書，碼本長度碼本長度為為J J 。 碼本的碼本的J J個元素稱作個元素稱作碼字碼字或碼矢量，它們均或碼矢量，它們均 為為R RP P中的矢量，中的矢量，P P維矢量。維矢量。 矢量量化器定義：矢量量化器定義： An exampl

13、e of a 2-dimensional VQ is shown below: 當給矢量量化器輸入一個任意矢量當給矢量量化器輸入一個任意矢量X Xi i進行矢量進行矢量 量化時，矢量量化器首先判斷它屬于那個子空間，量化時，矢量量化器首先判斷它屬于那個子空間， 然后輸出該子空間的代表矢量然后輸出該子空間的代表矢量Y Yj j。矢量量化過程就。矢量量化過程就 是用是用Y Yj j代替代替X Xi i的過程。的過程。 Y Yj jQ(XQ(Xi i) 1) 1 j j J 1J 1 i i N N 3.3.矢量量化的過程 矢量矢量 量化器量化器 X Xi iY Yj j 當給矢量量化器輸入一個任意矢

14、量當給矢量量化器輸入一個任意矢量X Xi i進行矢進行矢 量量化時，矢量量化器首先判斷它屬于那個子空量量化時，矢量量化器首先判斷它屬于那個子空 間，如何判斷就是要依據(jù)一定的規(guī)則，選擇一個間，如何判斷就是要依據(jù)一定的規(guī)則，選擇一個 合適的失真測度，分別計算每個碼字代替合適的失真測度，分別計算每個碼字代替X Xi i所帶所帶 來的失真，當確定產(chǎn)生最小失真的那個碼字來的失真，當確定產(chǎn)生最小失真的那個碼字Y Yj j時，時， 就將就將X Xi i量化成量化成Y Yj j， Y Yj j就是就是X Xi i的重構(gòu)矢量（和恢復的重構(gòu)矢量（和恢復 矢量）。矢量）。 4.判斷規(guī)則 X Xi i=a=ai1 i

15、1,a ,ai2 i2,a ,aiP iP Y Y2 2 Y Y1 1= y y11 11,y ,y12 12,y ,y1P 1P Y Y2 2= y y21 21,y ,y22 22,y ,y2P 2P Y YJ J= y yJ1 J1,y ,yJ2 J2,y ,yJP JP 矢量量化器矢量量化器 （碼本）（碼本） 最小失真最小失真 計算失真計算失真 x 4 矢量量化矢量量化 3 3 2 3 1 3 2 2 2 1 3 4 341 1 1 3 4 碼書碼書 碼字碼字c0 碼字碼字c1 碼字碼字c2 碼字碼字c3 索引索引0 d(x,c0)=5 d(x,c1)=11 d(x,c2)=8 d(x

16、,c3)=8 argmind(x,cj) x 4 1 2 )(),( i ii cxCXd 圖像編碼例子：圖像編碼例子： 原圖象塊（原圖象塊（4灰度級，矢量維數(shù)灰度級，矢量維數(shù) k=44=16） x 0 1 2 3 碼書碼書C y0, y1 , y2, y3 y0 y1 y2 y3 碼字碼字y1最接近輸入矢量圖象塊最接近輸入矢量圖象塊 x，故用索引，故用索引“01”編編 碼碼 d(x,y0)=25 d(x,y1)=5 d(x,y2)=25 d(x,y3)=46 標量量化是維數(shù)為標量量化是維數(shù)為1的矢量量化。一般矢量量化均指的矢量量化。一般矢量量化均指 大于大于1的多維量化。的多維量化。 一個一

17、個P維最佳矢量量化器的性能總是優(yōu)于維最佳矢量量化器的性能總是優(yōu)于P個最佳標量個最佳標量 量化器。量化器。 在相同的編碼速率下，矢量量化的失真明顯比標量量在相同的編碼速率下，矢量量化的失真明顯比標量量 化的失真小；而在相同的失真條件下，矢量量化所需化的失真小；而在相同的失真條件下，矢量量化所需 的碼速率比標量量化所需的碼速率低得多。的碼速率比標量量化所需的碼速率低得多。 由于矢量量化的復雜度隨矢量維數(shù)成指數(shù)形式增加，由于矢量量化的復雜度隨矢量維數(shù)成指數(shù)形式增加， 故矢量量化的復雜度比標量量化的復雜度高故矢量量化的復雜度比標量量化的復雜度高。 標量量化和矢量量化比較標量量化和矢量量化比較 二、矢量

18、量化在語音通信中的應用 通信系統(tǒng)中有通信系統(tǒng)中有兩個完全相同的碼本兩個完全相同的碼本，一個在，一個在編碼編碼 器（發(fā)送端），器（發(fā)送端），另一個在另一個在解碼器（接收端）解碼器（接收端）。每個碼。每個碼 本包含本包含J J個碼字個碼字Y Yj j, ,每個碼字是一個每個碼字是一個P P維矢量。維矢量。VQVQ編碼器編碼器 的運行原理是根據(jù)輸入矢量的運行原理是根據(jù)輸入矢量X Xi i從編碼器碼本中選擇一從編碼器碼本中選擇一 個與之失真誤差最小的碼字個與之失真誤差最小的碼字Y Yj j ，其輸出的，其輸出的V V就是該碼就是該碼 字的下標，字的下標，V V是一個數(shù)字，因而可以通過任何數(shù)字信是一個數(shù)

19、字，因而可以通過任何數(shù)字信 道傳輸或任何數(shù)字存儲器來存儲。如在編碼速率為道傳輸或任何數(shù)字存儲器來存儲。如在編碼速率為 2.4kbit/s2.4kbit/s的的LPCLPC聲碼器中，將每幀的聲碼器中，將每幀的1010個預測系數(shù)加個預測系數(shù)加 以以1010維的矢量量化，編碼速率降低到維的矢量量化，編碼速率降低到800bit/s800bit/s，而語，而語 音質(zhì)量沒有下降。音質(zhì)量沒有下降。 特征特征 矢量矢量 形成形成 語音語音 信號信號 幀幀Xi 碼本碼本 Y1 Y2 YJ VQ 編碼編碼 器器 傳輸傳輸 或或 存儲存儲 V VQ 譯碼譯碼 器器 V Yj 碼本碼本 Y1 Y2 YJ 矢量量化在語

20、音通信中的應用矢量量化在語音通信中的應用 信信 源源 用用LBG(GLA)算算 法生成法生成 最近鄰最近鄰 搜索搜索 信信 宿宿 查表查表 信道信道 索引索引索引索引 碼書碼書碼書碼書 輸入輸入 矢量矢量 輸出輸出 矢量矢量 編碼編碼 器器 解碼解碼 器器 矢量量化編碼與解碼結(jié)構(gòu)圖：矢量量化編碼與解碼結(jié)構(gòu)圖： XX1 1 , X , X2 2 , , X , , XN N 模板庫模板庫 語語 碼本碼本 YY1 1 ,Y ,Y2 2 ,Y ,YJ J 學學 碼本碼本 音音 碼本碼本 文文 碼本碼本 wenwen 22 , 4, , 1, 4, , 1 N個特征矢量個特征矢量 三、矢量量化在語音識

21、別中的應用 先對系統(tǒng)中的每個字，做一個碼本作為該字先對系統(tǒng)中的每個字，做一個碼本作為該字 的參考（標準）模板的參考（標準）模板, ,共有共有M M個字，故共有個字，故共有M M個碼個碼 本，組成一個模板庫。本，組成一個模板庫。 識別時，對于任意輸入的語音識別時，對于任意輸入的語音特征矢量序列特征矢量序列X X XX1 1 , X , X2 2 , , X , , XN N ，計算該序列中每一個特，計算該序列中每一個特 征矢量對模板庫中的每個碼本的總平均失真量誤征矢量對模板庫中的每個碼本的總平均失真量誤 差，找出最小的失真誤差對應的碼本（代表一個差，找出最小的失真誤差對應的碼本（代表一個 字），

22、將對應的字輸出作為識別的結(jié)果。字），將對應的字輸出作為識別的結(jié)果。 特征矢量序列特征矢量序列 X XXX1 1 , X , X2 2 , , X , , XN N 模板庫模板庫 Y Y1 1 , Y , Y2 2 , , Y , , YM M 特征矢量特征矢量 序列形成序列形成 任意任意 語音語音 X X 碼本碼本 Y Y1 1 Y Y2 2 Y YM M 計算計算 失真誤差失真誤差 判決判決 輸出結(jié)果輸出結(jié)果Y Yi i 每一個字做一每一個字做一 個碼本，共個碼本，共M M個字個字 模板庫模板庫 XX1 1 , X , X2 2 , , X , , XN N 模板庫模板庫 語語 碼本碼本 Y

23、Y1 1 ,Y ,Y2 2 ,Y ,YN N 學學 碼本碼本 音音 碼本碼本 文文 碼本碼本 wenwen 四、矢量量化的關鍵之處 1. 1. 首先設計首先設計一個一個好好碼本。關鍵在于如何劃分碼本。關鍵在于如何劃分 J J個區(qū)域邊界。這需要大量的輸入信號矢量，經(jīng)個區(qū)域邊界。這需要大量的輸入信號矢量，經(jīng) 過統(tǒng)計實驗才能確定，這個過程稱為過統(tǒng)計實驗才能確定，這個過程稱為“訓練訓練”或或 “學習學習”。 應用聚類算法，按照一定的應用聚類算法，按照一定的失真度準則失真度準則（失 真測度），對訓練的數(shù)據(jù)進行，對訓練的數(shù)據(jù)進行分類分類，從而把訓，從而把訓 練數(shù)據(jù)在多維空間中劃分成一個以碼字為中心的練數(shù)據(jù)

24、在多維空間中劃分成一個以碼字為中心的 胞腔，常用的是胞腔，常用的是LBGLBG算法來實現(xiàn)。算法來實現(xiàn)。 2. 2. 未知矢量的量化。按照選定的未知矢量的量化。按照選定的失真度準則失真度準則 （失真測度），把未知矢量，量化為失真度最，把未知矢量，量化為失真度最 小的碼字。小的碼字。 失真測度就是兩矢量之間的失真測度就是兩矢量之間的距離距離。 7.3 矢量量化的失真測度 一、失真測度的定義 二、歐氏距離測度 三、線性預測失真測度 四、識別失真測度 一、失真測度的定義 失真測度（距離測度）就是將輸入矢量失真測度（距離測度）就是將輸入矢量X Xi i用碼用碼 本重構(gòu)矢量本重構(gòu)矢量Y Yj j來表征時所

25、產(chǎn)生的來表征時所產(chǎn)生的誤差或失真的度量誤差或失真的度量 方法方法，它可以描述兩個或多個模型矢量之間的相，它可以描述兩個或多個模型矢量之間的相 似程度。常用的失真測度為歐氏距離測度、加權(quán)似程度。常用的失真測度為歐氏距離測度、加權(quán) 歐氏距離測度和識別失真測度。歐氏距離測度和識別失真測度。 K K維語音特征矢量維語音特征矢量X X和碼本和碼本Y Y的失真測度的失真測度d(X,Y)d(X,Y)需需 滿足滿足下列條件下列條件： （1 1）對稱性）對稱性 d(X,Y)d(X,Y)d(Y,X) d(Y,X) （2 2）正值性）正值性 d(X,Y)0,d(X,X)=0 d(X,Y)0,d(X,X)=0 （3

26、3）d(X,Y)=d(X,Z)+d(Z,Y)d(X,Y)=d(X,Z)+d(Z,Y) （4 4）對）對d(X,Y)d(X,Y)有高效率的計算方法有高效率的計算方法 二、歐氏距離測度 K K維特征矢量：維特征矢量： X Xi ixxi1 i1 , x , xi2 i2 , , x , , xiK iK Y Yj jyyj1 j1 , y , yj2 j2 , , y , , yjK jK K i ii yx K YXd 1 2 2 )( 1 ),( 1.1.均方誤差歐氏距離均方誤差歐氏距離 K i ii yx K YXd 1 1 | 1 ),( 2.2.絕對值平均誤差絕對值平均誤差 3.3.加權(quán)

27、歐氏距離測度加權(quán)歐氏距離測度 K i ii yxiw K YXd 1 2 )( 1 ),( 三、線性預測失真測度 當語音信號特征矢量使用線性預測方法求出當語音信號特征矢量使用線性預測方法求出 的的LPCLPC系數(shù)時，系數(shù)時，不宜直接用歐氏距離。不宜直接用歐氏距離。應該直接應該直接 用預測系數(shù)所描述的信號模型的用預測系數(shù)所描述的信號模型的功率譜功率譜來進行來進行 比較。通過推導，采用對數(shù)似然比失真測度和比較。通過推導，采用對數(shù)似然比失真測度和 模型失真測度。模型失真測度。 Raa aRa YXd T T LLR )( ln),( 1.1.對數(shù)似然比失真測度對數(shù)似然比失真測度 R R是輸入語音信號

28、的是輸入語音信號的(p(p1)1)（p+1p+1）自相關矩）自相關矩 陣陣 ,., 1 21p T aaaa 輸入語音信號的預輸入語音信號的預 測系數(shù)矢量測系數(shù)矢量 ,., 1)( 21p T aaaa 碼字預測系數(shù)矢量碼字預測系數(shù)矢量 )0()2()( )2()0() 1 ( )() 1 ()0( nnn nnn nnn RpRpR pRRR pRRR R 1 )( ),( Raa aRa YXd T T M 2. 2. 模型失真測度模型失真測度 R R是輸入語音信號的是輸入語音信號的(p+1)(p+1)（p+1p+1）自相關矩陣）自相關矩陣 ,., 1 21p T aaaa 輸入語音信號的

29、預輸入語音信號的預 測系數(shù)矢量測系數(shù)矢量 ,., 1)( 21p T aaaa 碼字預測系數(shù)矢量碼字預測系數(shù)矢量 7.4 矢量量化的最佳碼本設計 一、最佳碼本設計的原則 二、LBG算法 三、碼字搜索 碼本設計碼本設計 碼字搜索碼字搜索 碼字索引分配碼字索引分配 . . . . . . x 訓練集合訓練集合X M 訓練矢量訓練矢量 . . . . . . . 碼本碼本C y1 y2 yN N 個碼字個碼字 . . . . . . . x d(x,y1) d(x,y0) d(x, yN-1) min d(x,yj) 碼本碼本C y0 y1 yN-1 所謂最佳設計，就是從大量信號樣本中訓所謂最佳設計

30、，就是從大量信號樣本中訓 練出好的碼本；從實際效果出發(fā)尋找到好的失練出好的碼本；從實際效果出發(fā)尋找到好的失 真測度定義公式；用最少的搜索和計算失真的真測度定義公式；用最少的搜索和計算失真的 運算量。運算量。 一、最佳碼本設計的原則 最佳碼本的設計，就是在一定條件下，使得最佳碼本的設計，就是在一定條件下，使得 d(X,Y)d(X,Y)的統(tǒng)計平均最小。需滿足下列條件：的統(tǒng)計平均最小。需滿足下列條件： （1 1）最鄰）最鄰近近準則；根據(jù)該條件對信號空間進行最佳準則；根據(jù)該條件對信號空間進行最佳 劃分，得到劃分，得到S Sl l稱為一個胞腔。稱為一個胞腔。 （2 2）所有選擇碼字）所有選擇碼字Y Yl

31、 l的輸入矢量的輸入矢量X X的集合為的集合為S Sl l， Y Yl l 是是S Sl l中所有矢量的質(zhì)心。根據(jù)這兩條原則，這個算中所有矢量的質(zhì)心。根據(jù)這兩條原則，這個算 法就是法就是LBGLBG算法。算法。 l SX l l X N Y 1N Nl l為集合中矢量的個數(shù)為集合中矢量的個數(shù) JiliYXdYXdRXS il K l , 1,);,(),(: x x x x x x x x x x x i S K S ),(),(: ik K k YXdYXdRXS k Y i Y k SX k k X N Y 1 i SX i i X N Y 1 質(zhì)心的形成質(zhì)心的形成 X1( 220, 40

32、0, 430, 390, 300 )X1( 220, 400, 430, 390, 300 ) X2( 220, 400, 410, 380, 310 )X2( 220, 400, 410, 380, 310 ) X3( 220, 450, 410, 390, 300 )X3( 220, 450, 410, 390, 300 ) X4( 220, 450, 420, 370, 290 )X4( 220, 450, 420, 370, 290 ) 所有選擇碼字所有選擇碼字Y Y的輸入矢量的輸入矢量X X的集合為的集合為S S， Y Y是是S S中所有矢量的質(zhì)心。中所有矢量的質(zhì)心。 300,5.3

33、82,425,220XXXX 4 1 XXXX 4 11 4321 4321 SX X N Y LBG LBG算法是一種遞推算法，從一個事先選定的算法是一種遞推算法，從一個事先選定的 初始碼本開始迭代。把訓練序列按照碼本中的元素初始碼本開始迭代。把訓練序列按照碼本中的元素 根據(jù)最鄰近準則分組，對每一分組找質(zhì)心，得到新根據(jù)最鄰近準則分組，對每一分組找質(zhì)心，得到新 的碼本，又作為初始碼本，再進行分組，重復上述的碼本，又作為初始碼本，再進行分組，重復上述 過程，直到系統(tǒng)性能滿足要求和不再有明顯的改進過程，直到系統(tǒng)性能滿足要求和不再有明顯的改進 為止。為止。 二、LBG算法 （1 1）初始碼本的選擇）

34、初始碼本的選擇 隨機選取法：從訓練序列中隨機選取隨機選取法：從訓練序列中隨機選取J J個矢個矢 量作為初始碼字，從而構(gòu)成初始碼本。量作為初始碼字，從而構(gòu)成初始碼本。 . . . . . . x . . . . 訓練集合訓練集合X . . 初始碼本初始碼本 J=2J=2個碼字個碼字 （1 1）求出）求出S S中全體訓練序列的質(zhì)心中全體訓練序列的質(zhì)心 （2 2）然后在）然后在S S中找一個與此質(zhì)心的失真測度最大的中找一個與此質(zhì)心的失真測度最大的 矢量矢量 ，再在再在S S中找一個與中找一個與 的失真測度最大的矢量的失真測度最大的矢量 （3 3）以）以 和和 為基準，根據(jù)最鄰近準則，進行為基準，根據(jù)

35、最鄰近準則，進行S S 的劃分，得到兩個子集的劃分，得到兩個子集 和和 ，求其質(zhì)心；，求其質(zhì)心； （4 4）對這兩個子集分別按同樣方法進行處理，可以）對這兩個子集分別按同樣方法進行處理，可以 得到四個子集。依次類推，經(jīng)過得到四個子集。依次類推，經(jīng)過r r次分裂，得到次分裂，得到J=2J=2r r 個子集，分別求子集的質(zhì)心，得到個子集，分別求子集的質(zhì)心，得到J J個初始碼字，構(gòu)個初始碼字，構(gòu) 成初始碼本。成初始碼本。 分裂法分裂法 0 1 Y ii XYXd),(max 0 1 kik XXXd),(max i X i X k X i S K S x x x x x x x x x x x x

36、x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x質(zhì)心質(zhì)心 x x x x x x x x x x x ii XYXd),(max 0 1 x x x x x x x x x x x kik XXXd),(max i S K S k SX k X N Y 1 1 1 分裂分裂1 1次，得到次，得到2 2個碼字個碼字 J=2 2J=2 2個碼字的初始碼本構(gòu)成個碼字的初始碼本構(gòu)成 ),(),(: ikk XXdXXdSXS S i SX i X N Y 1 1 2 SX X N Y 1 0 1 （2）最佳碼本的設計）最佳碼

37、本的設計 第一步：初始化。給定全部參考矢量集合第一步：初始化。給定全部參考矢量集合S S，設定，設定 失真控制門限失真控制門限 , , 算法最大迭代次數(shù)算法最大迭代次數(shù)L,L,以及初始碼以及初始碼 本本 ，設置總失真，設置總失真 ，初始迭代，初始迭代 次數(shù)次數(shù)m=1m=1，最大迭代次數(shù)為，最大迭代次數(shù)為L L。 第二步：迭代。第二步：迭代。 （1 1）根據(jù)最鄰近準則將）根據(jù)最鄰近準則將S S分成分成J J個子集，個子集， （2 2）計算總失真）計算總失真 00 2 0 1J YYY )0( D m J mm SSS 21 JlJili YXdYXdRX S m i m l K m l , 1;

38、, 1, );,(),(: 11 J lSX m l m m l YXdD 1 1) ,( （3 3）計算新碼字：每一個碼字為其對應子集的質(zhì)心。）計算新碼字：每一個碼字為其對應子集的質(zhì)心。 （4 4）計算相對失真改進量，）計算相對失真改進量， 與與失真控制門限比較，失真控制門限比較， 轉(zhuǎn)入（轉(zhuǎn)入（5 5）；）； 轉(zhuǎn)入（轉(zhuǎn)入（6 6）。）。 （5 5）若）若m m大于大于L L，則轉(zhuǎn)入，則轉(zhuǎn)入(6)(6)，否則，否則m+1m+1，轉(zhuǎn)入，轉(zhuǎn)入(1)(1) （6 6）得到最終的碼書）得到最終的碼書 m J mm YYY 21 m l SXl m l X N Y 1 m mm m D DD| 1 m

39、m m J mm YYY 21 x x x x x x x x x x x xx x x x x x x x x S x x x x x x x x x x x xx x x x x x x x x 1 4 1 3 1 2 1 1 SSSS J=4,m=1 0 4 0 3 0 2 0 1 YYYY 4, 2 , 1, );,(),(: 00 1 lili YXdYXdRX S il K l 4 1 01 ),( lSX l m l YXdD x x x x x x x x x x x x x x x x x x x x x 新碼字新碼字 1 4 1 3 1 2 1 1 YYYY 1 10 1

40、| D DD 1 if m+1=2m+1=2重新開始重新開始 2 4 2 3 2 2 2 1 SSSS 4, 2 , 1, );,(),(: 11 2 lili YXdYXdRX S il K l 4 1 22 ),( lSX l m l YXdD 新碼字新碼字 2 4 2 3 2 2 2 1 YYYY 2 21 2 | D DD 2 if m+1=3m+1=3重新開始重新開始 1 4 1 3 1 2 1 1 YYYY x x x x x x x x x x x x x x x x x x x x x J=4,m=2 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 最佳碼本的設計方法之一：遺傳算法最佳碼本的設計方法之一：遺傳算法 （Genetic Algorithm,GAGenetic Al