Vector Quantization(VQ)

Presentation on theme: "Vector Quantization(VQ)"— Presentation transcript:

1 Vector Quantization(VQ)
96/09/27 指導教授:廖元甫 演講者:黃重傑

2 Outline Goal Introduction VQ codebook的產生

3 Goal 對一組參數同時做量化，將位元率降低 為了做MLVQ(EM)而做的前置作業(分群)

4 Scalar & Vector Quantization
量化對象為一個實數所表示的數量，就叫做數 量量化(Scalar Quantization) 如果我們同時對一組實數做量化，將這組實數 看成是一個向量，就叫做向量量化 (Vector Quantization)

5 Uniform & non uniform quatization
均勻量化 固定量化間距，相對於小訊號SNR較小 ，相對於大訊號SNR較大 非均勻量化 非固定量化間距，小訊號使用小量化間距，大訊號使用大量化間距 可降低平均量化誤差

6 Uniform & non uniform quatization

7 VQ as space partition Codeword (中心點) Partition (群)

8 VQ Introduction 一個向量x落在Ci這個區域，我們就用一個代表向量來代表。 Input vector:
mapping vector: 每一個cell（region）Ci 會有一個codeword zi 。

9 Distortion measure 其中量化誤差標示為 Overall average distortion:

10 Two necessary conditions for optimality
using a nearest-neighbor selection rule if and only if each codeword zi is chosen to minimize the average distortion in cell Ci

11 Codebook的產生 量化器中需有一張對照表，記載每個codewords對應的B個位元，稱之為碼本(codebook)
如何用一群資料來得出碼本，以下為常用的三種方法: K-means algorithm LBG algorithm Centroid splitting algorithm

12 K-mean A. 初始化 選擇一些適當的方法取得初始的VQ codebook， k， k = 1, 2, …, K，對每一群計算其平均值，作為初始的中心點， ， k = 1, 2, …, K。 B. 遞迴演算 1. 將每一個訓練資料x，對所有K個中心點計算與其之間的距離，讓它歸屬到距 離最短的中心點去。 2. 所有屬於 資料x形成一個群，重新計算其中心點 。 3. 如果新的一組中心點與原來一組中心點一樣，沒有改變，就表示訓練結束。否則，就以新的一組中心點替代原來的一組中心 點，回到(步驟 1)繼續遞迴演算。

13 LBG A. 初始化 選擇一些適當的方法取得初始的VQ codebook ， ，k=1,2,….,K，組成初始碼本。 B. 遞迴演算
1.將每個訓練資料x，對codebook去做量化，歸屬到相對應的中心點。 ， 其中 ， 。 2.計算總失真量 如果D的值小於預設值，則停止遞迴演算，否則繼續下一步驟。 3.所有屬於 的x形成一個群，重新計算中心點 ，組成新的codebook。 如果遞迴次數未達到預設值，就回到步驟(1)，繼續遞迴演算。

14 中心點分裂 A. 初始化 將全部訓練資料一起計算一個中心點，作為最開始的碼字，另外設定兩個指標值 n = 0, k = 1。 B. 遞迴演算 1. 在 n 階段，有2n個中心點，將中心點分裂為兩個中心點。 為一個小值，一般取為0.01，因此得出22n個中心點。 2. 每一個訓練資料x對所有中心點計算距離，找出歸屬的中心點。 3. 每個中心點所屬的訓練資料集合起來，計算新的中心點。 4.如果n+1已經是預訂要達到的遞迴條件，就代表訓練結束，否則以n+1替代n ，回到步驟(1)，繼續下一階段的分裂。

15 Demo for VQ