矢量量化編碼

1、 矢量量化編碼 1. 引言矢量量化是一種高效的數(shù)據(jù)壓縮技術(shù)，它具有壓縮比大、解碼簡(jiǎn)單和失真較小等優(yōu)點(diǎn)。自從1980年提出矢量量化器(Vector Quantizater)碼書設(shè)計(jì)的LBG算法Linde et al(1980)以來，矢量量化(Vector Quantization)技術(shù)Gray(1984)已經(jīng)成功地應(yīng)用到圖像壓縮和語音編碼中。矢量量化壓縮中最核心的技術(shù)是碼書的設(shè)計(jì)，碼書的優(yōu)化性直接影響到壓縮效率和圖像復(fù)原質(zhì)量。這里主要對(duì)碼書設(shè)計(jì)算法進(jìn)行討論。首先介紹了經(jīng)典的LBG算法及其在圖像壓縮中的應(yīng)用；然后，針對(duì)LBG算法的不足，結(jié)合圖像處理的特點(diǎn)，提出了改進(jìn)的覆蓋聚類算法，有效改善了系統(tǒng)性

2、能。2 .碼書的設(shè)計(jì)碼書設(shè)計(jì)是矢量量化壓縮系統(tǒng)的關(guān)鍵環(huán)節(jié)。碼書設(shè)計(jì)得越優(yōu)化，矢量量化器的性能就越好。實(shí)際中，不可能單獨(dú)為每幅待編碼的圖像設(shè)計(jì)一個(gè)碼書，因此通常是以一些代表性圖像構(gòu)成的訓(xùn)練集為基礎(chǔ)，為一類圖像設(shè)計(jì)一個(gè)最優(yōu)碼書。從數(shù)學(xué)的觀點(diǎn)看，矢量量化中的碼書設(shè)計(jì)，實(shí)質(zhì)是把系統(tǒng)的率失真函數(shù)看成目標(biāo)函數(shù)，并使之在高維空間中成為最小的全局優(yōu)化問題。假設(shè)采用平方誤差測(cè)度作為失真測(cè)度，訓(xùn)練集中的矢量數(shù)為M，目的是生成含N(N<M)個(gè)碼字(碼矢量)的碼書。碼書設(shè)計(jì)過程就是尋求把M 個(gè)訓(xùn)練矢量分成N類的一種最佳方案(使均方誤差最小)，而把各類的質(zhì)心矢量作為碼書的碼字。可以證明，各種可能的碼書個(gè)數(shù)為(1/

3、 N!)(一1)(N-i)CNiM，其中( 為組合數(shù)。通過測(cè)試所有碼書的性能可得到全局最優(yōu)碼書。然而，在N 和M 比較大的情況下，搜索全部碼書是根本不可能的。為了克服這個(gè)困難，各種碼書設(shè)計(jì)方法都采取搜索部分碼書的方法得到局部最優(yōu)或接近全局最優(yōu)的碼書。因此，研究碼書設(shè)計(jì)算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼書以提高碼書性能，并盡可能減少計(jì)算復(fù)雜度。3 LBG算法描述經(jīng)典的碼書設(shè)計(jì)算法是LBG算法它是YLinde，ABuzo與RMGray在1980年推出的，其思想是對(duì)于一個(gè)訓(xùn)練序列，先找出其中心，再用分裂法產(chǎn)生一個(gè)初始碼書A0，最后把訓(xùn)練序列按碼書A0中的元素分組，找出每

4、組的中心，得到新的碼書，轉(zhuǎn)而把新碼書作為初始碼書再進(jìn)行上述過程，直到滿意為止。LBG算法描述如下：(1)初始化。給定碼書有N個(gè)碼字，失真閾值E，一個(gè)訓(xùn)練序列 Xj;j=0， ，M 一1，某個(gè)初始N級(jí)碼本A0= yi=1，N，令 =0，D-1=。(2)給定An =yi;i=1，N，找到訓(xùn)練序列xj ；j=0，M 一1關(guān)于An的最小失真劃分P(A )=Si；i=1， ，N，其中Si =xj ：d( xj,yj)=limd(xj ,yj)，對(duì)任意L =1，2，N，計(jì)算出總平均失真Dn=D(An,P(An)=(1/M)limd(xj,y)。(3)如果(Dn-1一Dn)Dn e，且An 為最終的碼本；停

5、止，否則繼續(xù)。(4)不改變空間劃分，只修正各組的中心，得到新的碼書X(P(An )=；X(sj)；j=1， ，N，使得新碼書對(duì)于當(dāng)前向量空間劃分的總失真最小。對(duì)于均方差誤差標(biāo)準(zhǔn),X(Sj)是當(dāng)前向量空間劃分的歐氏中心，即X(Sj)=1/(|Sj|),其中|sj|表示Sj中訓(xùn)練樣本向量的個(gè)數(shù)。如果|Sj|=0，則令X(Sj)=yj ，即碼字不變。(5)An+1=X(sj)，令n=n+1，并轉(zhuǎn)去執(zhí)行步驟(2)。算法基于最佳矢量量化器設(shè)計(jì)的最佳劃分和最佳碼書這兩個(gè)必要條件，是勞埃德算法在矢量空間的推廣，其特點(diǎn)為物理概念清晰、算法理論嚴(yán)密及算法實(shí)現(xiàn)容易。但是，它有3個(gè)主要缺點(diǎn)：(1)在每次迭代的最佳劃

6、分階段，從碼書中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算。(2)初始碼書的選擇影響碼書訓(xùn)練的收斂速度和最終碼書的性能。(3)碼書的自適應(yīng)能力不強(qiáng)。碼書設(shè)計(jì)的第一個(gè)缺點(diǎn)可采用各種快速碼字搜索算法來解決，但這些算法無法改善碼書的性能。4 改進(jìn)的覆蓋聚類算法由上所述，LBG算法是一個(gè)不斷迭代、不斷調(diào)整聚類中心的過程，聚類速度慢，初始點(diǎn)的選取對(duì)聚類結(jié)果的影響大。因此，針對(duì)LBG算法的不足和圖像壓縮的特征，采用另一種算法覆蓋聚類算法。覆蓋算法基本思想是求出一組領(lǐng)域，將相似度大的樣本聚合在一起，將相似度小的樣本分隔開來，達(dá)到聚類的效果。即給定一輸入集K= X1，X2，Xk(K是 維歐式空間的點(diǎn)

7、集)，設(shè)K分為S個(gè)子集Kl= x1，x2 ，Xm(1),Ks= Xm(s-1)+1，,Xk每個(gè)子集就是一個(gè)覆蓋。對(duì)于領(lǐng)域覆蓋比較少的樣本點(diǎn)采用最短距離法(這里采用歐式距離)進(jìn)行聚類，這樣形成橢球形覆蓋領(lǐng)域，即選擇圓心距離最近的一對(duì)覆蓋合并成一個(gè)新覆蓋。計(jì)算新覆蓋和其他覆蓋的圓心的距離，再將距離最近的兩個(gè)覆蓋合并。根據(jù)實(shí)際需要，重復(fù)以上合并步驟，每次減少一個(gè)覆蓋，最終得到合理的覆蓋劃分，且所有相似點(diǎn)分布在一個(gè)領(lǐng)域(球形或者橢球形)。參照上面的聚類準(zhǔn)則和歐式距離函數(shù)，并根據(jù)圖像壓縮特點(diǎn)和實(shí)際處理圖像的情況，歸納出如下的改進(jìn)覆蓋聚類算法：(1)求所有矢量的重心，矢量重心用該矢量中所含像素點(diǎn)灰度值的平

8、均值來表示；(2)取一個(gè)矢量，求此矢量重心與其它未聚類矢量重心的距離，找出最小距離對(duì)應(yīng)的矢量作為類覆蓋的圓心center；(3)以這個(gè)最小距離的102倍(倍數(shù)可以根據(jù)實(shí)際情況改變)作為半徑r，形成一個(gè)球覆蓋，即根據(jù)各矢量重心將相應(yīng)的矢量歸于此類，同時(shí)記錄類中的個(gè)數(shù)；(4)求這個(gè)類的質(zhì)心(質(zhì)心定義與LBG算法中的相同)，以此得到一個(gè)碼矢量和其對(duì)應(yīng)的矢量；(5)找離當(dāng)前覆蓋的圓心最遠(yuǎn)的矢量作為下一步覆蓋的圓center； (6)重復(fù)(2)一(6)直到所有的樣本全部覆蓋結(jié)束；(7)對(duì)于包含點(diǎn)比較少的覆蓋采用最短距離法合并，具體步驟如下： 對(duì)于要用最短距離法合并的覆蓋，計(jì)算出兩覆蓋的圓心的距離； 將離

9、得最近的兩個(gè)覆蓋合并為一個(gè)新覆蓋； 更新其它覆蓋與新覆蓋的最短距離； 根據(jù)實(shí)際需要，重復(fù) 、步，確定最后的聚類數(shù)。(8)結(jié)束。5 實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)條件：矢量維數(shù)為4，以訓(xùn)練集中的13幅圖象作為產(chǎn)生碼書的圖像，對(duì)“cman”進(jìn)行處理。其中產(chǎn)生碼書時(shí)，請(qǐng)根據(jù)你的具體情況輸入你所需要的訓(xùn)練集個(gè)數(shù)。實(shí)驗(yàn)環(huán)境：微型計(jì)算機(jī)：系統(tǒng)：Microsoft WindoWS XP Professional，版本2002。編譯平臺(tái)：matlab6.5實(shí)驗(yàn)結(jié)果如圖所示。產(chǎn)生碼本的執(zhí)行時(shí)間為7.331000 secs測(cè)試圖象的時(shí)間t為15 secs壓縮比：接近5倍；6. 實(shí)驗(yàn)結(jié)論改進(jìn)的覆蓋聚類算法的優(yōu)點(diǎn)主要解決了LBG算法難以解決的問題：初值的選取對(duì)系統(tǒng)的影響和聚