标准向量量化编码法-Read.pptVIP

* * 向量量化編碼法 鄭松賓02/10/30 Vector Quantization 向量量化編碼法(VQ ,Vector Quantization) 是以一向量值用另一量化值取代，已達成資料壓縮的目的 將影像分割成許多大小相同的小方格，每個小方格包含了許多的像素，通常是由左而右、由上而下地串成一個向量。每個方格都有不同的像素值，編碼時只要是先收集完成具有代表性的向量，組成編碼簿 (Code book) ，找出其中跟此一個影像方格最接近的編碼字 (Code word)，的 索引值取代此向量(方格) ，組成一張索引表。 解壓縮時只需利用索引值至編碼部中取出該區對應的向量即可還原。索引表即是VQ 壓縮後的結果，因為索引表的體積通常會比原影像小方格的體積小很多，故VQ 能有很好的壓縮效果(壓縮率通常是十六分之一) 。但因壓縮時是取最接近的向量，所以會造成部分原始資料有失真，屬於失真影像壓縮法。 適用於允許失真的數位影像、聲音等資料上，此法為學術界所廣泛使用 向量量化編碼法(VQ ,Vector Quantization) … … … … … w h k k = w x h i i 原 始 影 像 編 碼 字 編 碼 簿 (索 引 表) 壓 縮 碼 尋找最接近的編碼字 壓縮端: 向量量化編碼法(VQ ,Vector Quantization) k k = w x h i 編 碼 字 編 碼 簿 查表 近似區塊 重建影像 w h 解碼端: 壓縮索引 i 尋找最接近的編碼字 輸入向量 X 編碼簿 C, 包含K個編碼字 {Yi} 則最接近的編碼字 Yj定義如下: || X-Yj ||2 ? || X-Yi ||2 for all Yi?C 其中 X=(x1, x2, … XL) 且 ||X||2 = ? xi2 i=1 L Euclidean distance 向量量化編碼法(VQ ,Vector Quantization) LBG 演算法 LBG演算法由Linde、Buzo和Gray三位學者所提出的方法。其主要精神是從一堆編碼字的樣本中以分群法找出代表每個群的編碼字，再由這些其代表性的編碼字形成一本編碼簿。 步驟1 選出三至五張具代表性的影像。將每一張影像切割成4x4的區塊。考 慮一張512x512的影像，則共可被切割成 (512x512)/(4x4)=16,384個區塊，其中每個區塊我們可視之為一個16維的向量。 訓練出一本含有256個編碼字的編碼簿，其中每個編碼字均由16維向量所組成，其步驟如下: 步驟2 首先從這些區塊中隨意挑出256個區塊當作初始編碼簿。 步驟3 以這256個初始向量為重心，將其餘區塊分別歸群到這256個重心， 也就是每個區塊去尋找與其距離最近的重心，以形成256個群。 步驟4 重新計算這256個群的重心，得到新的一本編碼簿。重複步驟3及4， 直到每個群重心的變化不再很大時(收斂)，即完成了編碼簿的訓練工 作。 LBG演算法的結果取決於初始向量是否足夠分散。 也就是說，若初始向量太過集中的話， 所編出來的編碼簿通常不具有很好的代表性。 LBG 演算法 標準編碼的做法相當直接，將每個編碼字的向量一一計算它們之間的距離 (Euclidean distance) ，並從中找出最接近的一組編碼字進行隻索引值來 當向量的編碼。 標準VQ編碼法~~Full search LBG演算法的結果，屬於較不穩定的， 而且此方法需要大量的計算， 是其缺點之一 。 設X=(x1,x2,x3,…,xk)為欲進行編碼的一組向量，Y={Y1,Y2,…Ym}為編碼簿， 其中共有i個編碼字，每個編碼自均為一個k為向量，即Yi =(yi1,yi2,yi3,…,yik) 。向量x所得的編碼為c 。 此法是最直接且最簡單的方法，但也是最耗時的方法。 v=1 ? (xv-Ycv) k l=1 ? (xv-Ylv) k = min m l=1 √ ── √ ── 細胞分裂法演算法 細胞分裂法其主要精神是將初始編碼簿儘量分開，如此可以改善LBG演算法初始值過於集中的缺點，並且可以改進製作編碼簿的速度，以下是細胞分裂法的演算過程: 步驟1 選出三至五張具代表性的影像。將每一張影像切割成4x4的區塊。考 慮一張512x512的影像，則共可被切割成 (512x512)/(4x4)=16,384個區塊，其中每個區塊我們可視之為一個16維的向量。 步驟2 從這些區塊中隨意挑出一個區塊X = (x1, x2, ..., xk)為初始向量。 步驟3 將X向量分別減去一個?值形成二個向量，分別為Y = (y1, y2, ..., yk)