向量量化編碼法

向量量化編碼法向量量化編碼法(VQ,VectorQuantization)是以一向量值用另一量化值取代，已達(dá)成資料壓縮的目的將影像分割成許多大小相同的小方格，每個小方格包含了許多的像素，通常是由左而右、由上而下地串成一個向量。每個方格都有不同的像素值，編碼時只要是先收集完成具有代表性的向量，組成編碼簿(Codebook)，找出其中跟此一個影像方格最接近的編碼字(Codeword)，的索引值取代此向量(方格)，組成一張索引表。解壓縮時只需利用索引值至編碼部中取出該區(qū)對應(yīng)的向量即可還原。索引表即是VQ壓縮後的結(jié)果，因?yàn)樗饕淼捏w積通常會比原影像小方格的體積小很多，故VQ能有很好的壓縮效果(壓縮率通常是十六分之一)。但因壓縮時是取最接近的向量，所以會造成部分原始資料有失真，屬於失真影像壓縮法。適用於允許失真的數(shù)位影像、聲音等資料上，此法為學(xué)術(shù)界所廣泛使用向量量化編碼法(VQ,VectorQuantization)……………whkk=wxhii原始影像編碼字編碼簿(索引表)壓縮碼尋找最接近的編碼字壓縮端:向量量化編碼法(VQ,VectorQuantization)kk=wxhi編碼字編碼簿查表近似區(qū)塊重建影像wh解碼端:壓縮索引i尋找最接近的編碼字輸入向量X編碼簿C,包含K個編碼字{Yi}則最接近的編碼字Yj定義如下:||X-Yj||2

||X-Yi||2forallYiC其中X=(x1,x2,…XL)且||X||2=

xi2i=1LEuclideandistance向量量化編碼法(VQ,VectorQuantization)LBG演算法LBG演算法由Linde、Buzo和Gray三位學(xué)者所提出的方法。其主要精神是從一堆編碼字的樣本中以分群法找出代表每個群的編碼字，再由這些其代表性的編碼字形成一本編碼簿。步驟1選出三至五張具代表性的影像。將每一張影像切割成4x4的區(qū)塊。考慮一張512x512的影像，則共可被切割成(512x512)/(4x4)=16,384個區(qū)塊，其中每個區(qū)塊我們可視之為一個16維的向量。訓(xùn)練出一本含有256個編碼字的編碼簿，其中每個編碼字均由16維向量所組成，其步驟如下:步驟2首先從這些區(qū)塊中隨意挑出256個區(qū)塊當(dāng)作初始編碼簿。步驟3以這256個初始向量為重心，將其餘區(qū)塊分別歸群到這256個重心，也就是每個區(qū)塊去尋找與其距離最近的重心，以形成256個群。步驟4重新計(jì)算這256個群的重心，得到新的一本編碼簿。重複步驟3及4，直到每個群重心的變化不再很大時(收斂)，即完成了編碼簿的訓(xùn)練工作。LBG演算法的結(jié)果取決於初始向量是否足夠分散。也就是說，若初始向量太過集中的話，所編出來的編碼簿通常不具有很好的代表性。LBG演算法標(biāo)準(zhǔn)編碼的做法相當(dāng)直接，將每個編碼字的向量一一計(jì)算它們之間的距離(Euclideandistance)，並從中找出最接近的一組編碼字進(jìn)行隻索引值來當(dāng)向量的編碼。標(biāo)準(zhǔn)VQ編碼法~~FullsearchLBG演算法的結(jié)果，屬於較不穩(wěn)定的，而且此方法需要大量的計(jì)算，是其缺點(diǎn)之一。設(shè)X=(x1,x2,x3,…,xk)為欲進(jìn)行編碼的一組向量，Y={Y1,Y2,…Ym}為編碼簿，其中共有i個編碼字，每個編碼自均為一個k為向量，即Yi=(yi1,yi2,yi3,…,yik)。向量x所得的編碼為c。此法是最直接且最簡單的方法，但也是最耗時的方法。v=1(xv-Ycv)kl=1(xv-Ylv)k=minml=1√──√──細(xì)胞分裂法演算法細(xì)胞分裂法其主要精神是將初始編碼簿儘量分開，如此可以改善LBG演算法初始值過於集中的缺點(diǎn)，並且可以改進(jìn)製作編碼簿的速度，以下是細(xì)胞分裂法的演算過程:步驟1選出三至五張具代表性的影像。將每一張影像切割成4x4的區(qū)塊。考慮一張512x512的影像，則共可被切割成(512x512)/(4x4)=16,384個區(qū)塊，其中每個區(qū)塊我們可視之為一個16維的向量。步驟2從這些區(qū)塊中隨意挑出一個區(qū)塊X=(x1,x2,...,xk)為初始向量。步驟3將X向量分別減去一個值形成二個向量，分別為Y=(y1,y2,...,yk)以及Z=(z1,z2,...,zk)，其中yi=xi-，zi=xi+，且值為一常數(shù)值。當(dāng)yi<0時，取yi=0且當(dāng)zi>255時，取zi=255。步驟4以這Y及Z為重心，將其餘區(qū)塊分別去尋找與其距離最接近的重心；亦即將所有的區(qū)塊歸到這兩個重心，並重新計(jì)算各群之重心，得到Y(jié)’

及Z’。步驟5將Y’及Z’各分裂成兩個向量，並重複第３、４步驟，如此每一回合群的個數(shù)會以2的倍數(shù)成長，一直到產(chǎn)生足夠的編碼字個數(shù)。細(xì)胞分裂法演算法X=(x1,x2,...,xk)Z=(z1,z2,...,zk)Y=(y1,y2,...,yk)zi=xi+yi=xi-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-以Y為重心分群後重新計(jì)算各群重心以Z為重心分群後重新計(jì)算各群重心演算法中為一常數(shù)值，該值大小可一實(shí)驗(yàn)來取得較佳的經(jīng)驗(yàn)值。利用樹狀結(jié)構(gòu)漸進(jìn)的方式產(chǎn)生編碼簿，可以不用每次都計(jì)算編碼簿個分群重心，因此可以有效的減少計(jì)算量。初始向量的選擇對編碼簿的結(jié)果，不會有絕對性的影響。細(xì)胞分裂法演算法較LBG演算法具有更好的效能，包括編碼簿可產(chǎn)生較佳的壓縮品質(zhì)，以及製作編碼簿所花費(fèi)的時間較少等優(yōu)點(diǎn)。邊緣吻合向量量化法一般的向量量化壓縮法，都是針對事先劃分好的每個區(qū)塊分別做壓縮。完全不考慮區(qū)塊間的關(guān)聯(lián)性，但是一般的影像大多具有局部相似的性質(zhì)，因此有效的利用已知的相鄰區(qū)塊資料來對尚未解碼的區(qū)塊做有效的預(yù)測，可增加壓縮效率。邊緣吻合向量量化法(SideMatchVectorQuantization~~SMVQ)利用已知的相鄰區(qū)塊來改進(jìn)VQ壓縮率的方法，稱之為邊緣吻合向量量化法(SideMatchVectorQuantizationSMVQ)，其作法是先用傳統(tǒng)的VQ編碼法對影像最上方第一列區(qū)塊及最左方第一行區(qū)塊作編碼，這些區(qū)塊稱之為seedblock。其餘剩下來的區(qū)塊(residualblocks)則只須利用這些seedblocks來設(shè)法還原即可。還原方法如下所述，先參考右圖，其中U和L為以還原的區(qū)塊，因此這兩個區(qū)塊內(nèi)所有像素值皆為已知，而X則為未還原區(qū)。將X1這個像素值設(shè)為(U13+L14)/2，和U、L相鄰的像素值設(shè)為之後，從編碼簿中找出最接近的編碼字來還原X，此時只需和編碼字中的這幾個相對位置比較，也就是16維向量的編碼字中的第1、2、3、4、5、9及第13個位置上的值。X2=U14,X3=U15,X4=U16,X5=L8,X9=L12,X13=L16L13L14L15L16L4X1X2X3X4L8X6L12X9L16X16ULX邊緣吻合向量量化法(SideMatchVectorQuantization~~SMVQ)SMVQ的壓縮率是相當(dāng)高的，因?yàn)檎嬲幋a的只有第一列及第一行區(qū)塊的編碼而已。其餘的區(qū)塊均是利用相鄰的區(qū)塊來加以還原。除非該影像是一張幾乎完全沒變化的影像，否則其壓縮品質(zhì)將會是無法被接受的。其原因是當(dāng)上一回合所還原出的區(qū)塊有很大的誤差時，則下一回合還原出來的結(jié)果將會更差，而令人難以接受，此一問題稱為derailment。一種用來提昇side-matchVQ的壓縮品質(zhì)的方法。利用交叉的方式，將奇數(shù)行或列的區(qū)塊儲作seedblock，而偶數(shù)位的區(qū)塊則用SMVQ來還原。如此，每