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

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

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

4、組的中心，得到新的碼書，轉(zhuǎn)而把新碼書作為初始碼書再進行上述過程，直到滿意為止。LBG算法描述如下：(1)初始化。給定碼書有N個碼字，失真閾值E，一個訓練序列 Xj;j=0， ，M 一1，某個初始N級碼本A0= yi=1，N，令 =0，D-1=。(2)給定An =yi;i=1，N，找到訓練序列xj ；j=0，M 一1關(guān)于An的最小失真劃分P(A )=Si；i=1， ，N，其中Si =xj ：d( xj,yj)=limd(xj ,yj)，對任意L =1，2，N，計算出總平均失真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，使得新碼書對于當前向量空間劃分的總失真最小。對于均方差誤差標準,X(Sj)是當前向量空間劃分的歐氏中心，即X(Sj)=1/(|Sj|),其中|sj|表示Sj中訓練樣本向量的個數(shù)。如果|Sj|=0，則令X(Sj)=yj ，即碼字不變。(5)An+1=X(sj)，令n=n+1，并轉(zhuǎn)去執(zhí)行步驟(2)。算法基于最佳矢量量化器設(shè)計的最佳劃分和最佳碼書這兩個必要條件，是勞埃德算法在矢量空間的推廣，其特點為物理概念清晰、算法理論嚴密及算法實現(xiàn)容易。但是，它有3個主要缺點：(1)在每次迭代的最佳劃

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

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

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

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