Vector Quantization(VQ) 96/09/27 指導教授:廖元甫 演講者:黃重傑
Outline Goal Introduction VQ codebook的產生
Goal 對一組參數同時做量化，將位元率降低 為了做MLVQ(EM)而做的前置作業(分群)
Scalar & Vector Quantization 量化對象為一個實數所表示的數量，就叫做數 量量化(Scalar Quantization) 如果我們同時對一組實數做量化，將這組實數 看成是一個向量，就叫做向量量化 (Vector Quantization)
Uniform & non uniform quatization 均勻量化 固定量化間距，相對於小訊號SNR較小 ，相對於大訊號SNR較大 非均勻量化 非固定量化間距，小訊號使用小量化間距，大訊號使用大量化間距 可降低平均量化誤差
Uniform & non uniform quatization
VQ as space partition Codeword (中心點) Partition (群)
VQ Introduction 一個向量x落在Ci這個區域，我們就用一個代表向量來代表。 Input vector: mapping vector: 每一個cell（region）Ci 會有一個codeword zi 。
Distortion measure 其中量化誤差標示為 Overall average distortion:
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
Codebook的產生 量化器中需有一張對照表，記載每個codewords對應的B個位元，稱之為碼本(codebook) 如何用一群資料來得出碼本，以下為常用的三種方法: K-means algorithm LBG algorithm Centroid splitting algorithm
K-mean A. 初始化 選擇一些適當的方法取得初始的VQ codebook， k， k = 1, 2, …, K，對每一群計算其平均值，作為初始的中心點， ， k = 1, 2, …, K。 B. 遞迴演算 1. 將每一個訓練資料x，對所有K個中心點計算與其之間的距離，讓它歸屬到距 離最短的中心點去。 2. 所有屬於 資料x形成一個群，重新計算其中心點 。 3. 如果新的一組中心點與原來一組中心點一樣，沒有改變，就表示訓練結束。否則，就以新的一組中心點替代原來的一組中心 點，回到(步驟 1)繼續遞迴演算。
LBG A. 初始化 選擇一些適當的方法取得初始的VQ codebook ， ，k=1,2,….,K，組成初始碼本。 B. 遞迴演算 1.將每個訓練資料x，對codebook去做量化，歸屬到相對應的中心點。 ， 其中 ， 。 2.計算總失真量 如果D的值小於預設值，則停止遞迴演算，否則繼續下一步驟。 3.所有屬於 的x形成一個群，重新計算中心點 ，組成新的codebook。 如果遞迴次數未達到預設值，就回到步驟(1)，繼續遞迴演算。
中心點分裂 A. 初始化 將全部訓練資料一起計算一個中心點，作為最開始的碼字，另外設定兩個指標值 n = 0, k = 1。 B. 遞迴演算 1. 在 n 階段，有2n個中心點，將中心點分裂為兩個中心點。 為一個小值，一般取為0.01，因此得出22n個中心點。 2. 每一個訓練資料x對所有中心點計算距離，找出歸屬的中心點。 3. 每個中心點所屬的訓練資料集合起來，計算新的中心點。 4.如果n+1已經是預訂要達到的遞迴條件，就代表訓練結束，否則以n+1替代n ，回到步驟(1)，繼續下一階段的分裂。
Demo for VQ