向量量化編碼法 Vector Quantization 鄭松賓02/10/30.

Presentation on theme: "向量量化編碼法 Vector Quantization 鄭松賓02/10/30."— Presentation transcript:

1 向量量化編碼法 Vector Quantization 鄭松賓02/10/30

2 向量量化編碼法(VQ ,Vector Quantization)
是以一向量值用另一量化值取代，已達成資料壓縮的目的 將影像分割成許多大小相同的小方格，每個小方格包含了許多的像素，通常是由左而右、由上而下地串成一個向量。每個方格都有不同的像素值，編碼時只要是先收集完成具有代表性的向量，組成編碼簿 (Code book) ，找出其中跟此一個影像方格最接近的編碼字 (Code word)，的 索引值取代此向量(方格) ，組成一張索引表。 解壓縮時只需利用索引值至編碼部中取出該區對應的向量即可還原。索引表即是VQ 壓縮後的結果，因為索引表的體積通常會比原影像小方格的體積小很多，故VQ 能有很好的壓縮效果(壓縮率通常是十六分之一) 。但因壓縮時是取最接近的向量，所以會造成部分原始資料有失真，屬於失真影像壓縮法。 適用於允許失真的數位影像、聲音等資料上，此法為學術界所廣泛使用

3 向量量化編碼法(VQ ,Vector Quantization)
壓縮端: 尋找最接近的編碼字 編 碼 簿 w … k k = w x h h 編 碼 字 i i … … … … 壓 縮 碼 原 始 影 像 (索 引 表)

4 向量量化編碼法(VQ ,Vector Quantization)
解碼端: 編 碼 簿 查表 壓縮索引 i k k = w x h w 編 碼 字 h 重建影像 i 近似區塊

5 向量量化編碼法(VQ ,Vector Quantization)
尋找最接近的編碼字 輸入向量 X 編碼簿 C, 包含K個編碼字 {Yi} 則最接近的編碼字 Yj定義如下: || X-Yj ||2  || X-Yi ||2 for all YiC L 其中 X=(x1, x2, … XL) 且 ||X||2 =  xi2 i=1 Euclidean distance

6 LBG 演算法 LBG演算法由Linde、Buzo和Gray三位學者所提出的方法。其主要精神是從一堆編碼字的樣本中以分群法找出代表每個群的編碼字，再由這些其代表性的編碼字形成一本編碼簿。 訓練出一本含有256個編碼字的編碼簿，其中每個編碼字均由16維向量所組成，其步驟如下: 步驟1 選出三至五張具代表性的影像。將每一張影像切割成4x4的區塊。考 慮一張512x512的影像，則共可被切割成 (512x512)/(4x4)=16,384個區塊，其中每個區塊我們可視之為一個16維的向量。 步驟2 首先從這些區塊中隨意挑出256個區塊當作初始編碼簿。 步驟3 以這256個初始向量為重心，將其餘區塊分別歸群到這256個重心， 也就是每個區塊去尋找與其距離最近的重心，以形成256個群。 步驟4 重新計算這256個群的重心，得到新的一本編碼簿。重複步驟3及4， 直到每個群重心的變化不再很大時(收斂)，即完成了編碼簿的訓練工 作。

7 ── ── √ √ LBG 演算法 標準VQ編碼法~~Full search
標準編碼的做法相當直接，將每個編碼字的向量一一計算它們之間的距離 (Euclidean distance) ，並從中找出最接近的一組編碼字進行隻索引值來 當向量的編碼。 設X=(x1,x2,x3,…,xk)為欲進行編碼的一組向量，Y={Y1,Y2,…Ym}為編碼簿， 其中共有i個編碼字，每個編碼自均為一個k為向量，即Yi =(yi1,yi2,yi3,…,yik) 。向量x所得的編碼為c 。 ── ── √ √ k m k  (xv-Ycv) = min  (xv-Ylv) v=1 l=1 l=1 此法是最直接且最簡單的方法，但也是最耗時的方法。

8 細胞分裂法演算法 細胞分裂法其主要精神是將初始編碼簿儘量分開，如此可以改善LBG演算法初始值過於集中的缺點，並且可以改進製作編碼簿的速度，以下是細胞分裂法的演算過程: 步驟1 選出三至五張具代表性的影像。將每一張影像切割成4x4的區塊。考 慮一張512x512的影像，則共可被切割成 (512x512)/(4x4)=16,384個區塊，其中每個區塊我們可視之為一個16維的向量。 步驟2 從這些區塊中隨意挑出一個區塊X = (x1, x2, ..., xk)為初始向量。 步驟3 將X向量分別減去一個值形成二個向量，分別為Y = (y1, y2, ..., yk) 以及Z = (z1, z2, ..., zk)，其中yi=xi-，zi=xi+，且值為一常數值。 當yi<0時，取yi=0且當zi>255時，取zi=255。 步驟4 以這Y及Z為重心，將其餘區塊分別去尋找與其距離最接近的重心； 亦即將所有的區塊歸到這兩個重心，並重新計算各群之重心，得到Y’ 及Z’。 步驟5 將Y’及Z’各分裂成兩個向量，並重複第３、４步驟，如此每一回合群 的個數會以2的倍數成長，一直到產生足夠的編碼字個數。

9 細胞分裂法演算法 X = (x1, x2, ..., xk) Z = (z1, z2, ..., zk)
Y = (y1, y2, ..., yk) zi=xi+ yi=xi- 以Y為重心分群後 重新計算各群重心 以Z為重心分群後 Y’ = (y’1, y’2, ..., y’k) Z’ = (z’1, z’2, ..., z’k) P = (p1, p2, ..., pk) pi=y’i+ Q = (q1, q2, ..., qk) qi=y’i- R = (r1, r2, ..., rk) ri=z’i+ S = (s1, s2, ..., sk) si=z’i-

10 細胞分裂法演算法 演算法中為一常數值，該值大小可一實驗來取得較佳的經驗值。
利用樹狀結構漸進的方式產生編碼簿，可以不用每次都計算編碼簿個分群重心，因此可以有效的減少計算量。 初始向量的選擇對編碼簿的結果，不會有絕對性的影響。 較LBG演算法具有更好的效能，包括編碼簿可產生較佳的壓縮品質， 以及製作編碼簿所花費的時間較少等優點。

11 邊緣吻合向量量化法 一般的向量量化壓縮法，都是針對事先劃分好的每個區塊分別做壓縮。完全不考慮區塊間的關聯性，但是一般的影像大多具有局部相似的性質，因此有效的利用已知的相鄰區塊資料來對尚未解碼的區塊做有效的預測，可增加壓縮效率。

12 U L X 邊緣吻合向量量化法 ( Side Match Vector Quantization ~~SMVQ)
利用已知的相鄰區塊來改進 VQ 壓縮率的方法，稱之為邊緣吻合向量量化法 ( Side Match Vector Quantization SMVQ) ，其作法是先用傳統的VQ編碼法對影像最上方第一列區塊及最左方第一行區塊作編碼，這些區塊稱之為seed block。 其餘剩下來的區塊(residual blocks)則只須利用這些seed blocks來設法還原即可。 還原方法如下所述，先參考右圖，其中U和L為以還原的區塊，因此這兩個區塊內所有像素值皆為已知，而X則為未還原區。將 X1這個像素值設為(U13+L14)/2，和U、L相鄰的像素值設為 之後，從編碼簿中找出最接近的編碼字來還原 X ，此時只需和編碼字中的這幾個相對位置比較，也就是16維向量的編碼字中的第1 、2 、 3 、4 、5 、9及第13個位置上的值。 X2=U14,X3=U15,X4=U16,X5=L8,X9=L12,X13=L16 L13 L14 L15 L16 L4 X1 X2 X3 X4 L8 X6 L12 X9 X16 U L X

13 邊緣吻合向量量化法 ( Side Match Vector Quantization ~~SMVQ)
除非該影像是一張幾乎完全沒變化的影像，否則其壓縮品質將會是無法被接受的。其原因是當上一回合所還原出的區塊有很大的誤差時， 則下一回合還原出來的結果將會更差，而令人難以接受，此一問題稱為derailment。 一種用來提昇 side-match VQ的壓縮品質的方法。利用交叉的方式，將奇數行或列的區塊儲作 seed block ，而偶數位的區塊則用 SMVQ來還原。如此，每個未還原的區塊就可以利用四面八方的區塊資訊，如upper 、right 、down 及left block來求得更加的編碼字。由於已知資訊增加了，相對的正確率也就可以提高。

14 其他邊緣吻合向量量化法 分類邊緣吻合向量量化法 Variable-rate SMVQ with a block classifier (CSMVQ) 以樣式為基礎的SMVQ Pattern-based SMVQ (PSMVQ)