基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究分析

第四章 矢量量化算法的實(shí)現(xiàn)
4．1 需求分析與整體設(shè)計(jì)
4．1．1需求分析
隨著數(shù)字技術(shù)的飛速發(fā)展，越來越多的信息(文本、圖形、圖像、動(dòng)畫、音頻及視頻影像等)采用數(shù)字化的形式存儲(chǔ)、傳輸和檢索。由于網(wǎng)絡(luò)上的數(shù)據(jù)流量飛速增長，而且網(wǎng)絡(luò)的帶寬總是滿足不了需求，數(shù)據(jù)壓縮編碼技術(shù)的迅猛發(fā)展，要求在盡量不損傷多媒體質(zhì)量的情況下壓縮數(shù)據(jù)量。
正是由于這種需求的存在，要求開發(fā)一套完整的數(shù)據(jù)壓縮軟件，利用矢量量化的數(shù)據(jù)壓縮算法，能夠調(diào)用BMP格式的圖像，對(duì)載入的圖像進(jìn)行壓縮并顯示解壓后的圖像效果，能夠選擇路徑保存解壓后的圖像實(shí)現(xiàn)SNR信噪比的計(jì)算，便于對(duì)壓縮軟件性能的評(píng)價(jià)。
4．1．2 整體設(shè)計(jì)
軟件的設(shè)計(jì)在Eclipse開發(fā)工具下編譯Java應(yīng)用程序。利用Java語言的面向?qū)ο蟮奶攸c(diǎn)，充分利用他的可封裝性，重用性和多態(tài)性等特點(diǎn)，開發(fā)一整套完整的基于矢量量化數(shù)據(jù)壓縮算法的壓縮軟件。
將這個(gè)數(shù)據(jù)壓縮軟件從整體上分五個(gè)模塊來實(shí)現(xiàn)的。Bmp格式圖像的調(diào)入和保存模塊，圖像矢量塊的劃分模塊，初始碼書生成模塊，LBG量化模塊，圖像解壓模塊。如圖4.1所示：

圖4.1程序模塊框圖
軟件界面的設(shè)計(jì)。在JAVA的運(yùn)行環(huán)境下要實(shí)現(xiàn)基于矢量量化數(shù)據(jù)壓縮算法對(duì)BMP格式的靜止圖像進(jìn)行壓縮與解壓。軟件界面的設(shè)計(jì)，在圖像界面的左側(cè)可以顯示調(diào)入的圖像，右側(cè)顯示圖像信息。在瀏覽按鈕上可以調(diào)入待壓縮的圖像，并且可以選擇解壓后的圖像的保存位置。選擇好解壓圖像后點(diǎn)擊壓縮按鈕即可開始對(duì)圖像進(jìn)行矢量量化的壓縮。最后顯示壓縮的結(jié)果，包括原始圖像的大小，壓縮后的大小，壓縮比，壓縮時(shí)間及PSNR值等信息。軟件運(yùn)行的初始界面如圖4.2所示：

圖4.2程序運(yùn)行初始界面
4．2 矢量量化算法的實(shí)現(xiàn)過程及說明
4．2．1 初始碼書的生成
這個(gè)程序利用了隨機(jī)編碼生成碼書的方法，即根據(jù)輸入信源分布直接從訓(xùn)練序列中隨機(jī)選擇N個(gè)訓(xùn)練矢量作為初始碼字以構(gòu)成初始碼書。該方法的優(yōu)點(diǎn)是計(jì)算量低，初始碼書的生成較為容易。雖然可能出現(xiàn)碼書的分布不均勻的現(xiàn)象，但是配合LBG算法的多次迭代可以得到補(bǔ)償。需要注意，這里所說的隨機(jī)編碼是說初始碼書的選擇方式是隨機(jī)的，而一旦碼書選定，編碼器的工作方式則是按著最近鄰方式進(jìn)行的。隨機(jī)碼書的生成代碼如下：
codebook=new MyBlock[N];
for(int i=0;iN;i++)
{ codebook[i]=new MyBlock();
} codebook[0]=tv.randomselect();
for(int j=1;jN;j++) {
int t=0;
do{ t++;
n=0;
codebook[j]=tv.randomselect();
for(int l=0;lj;l++)
{ if(codebook[j].vcmp(codebook[l])==0)
{ n=1; break; }
}
}while(n!=0t100);}

4．2．2 LBG矢量量化
圖4.2 LBG碼書設(shè)計(jì)流程圖

如圖4.2所示的流程圖，對(duì)隨機(jī)生成初始碼書，碼書大小N，訓(xùn)練矢量序列，停止計(jì)算門限和起始平均失真的初始碼書進(jìn)行勞埃德迭代。用初始碼書為已知的心形，把訓(xùn)練序列重新劃分為N個(gè)胞腔。計(jì)算新的平均失真和相對(duì)失真，判斷新的失真是否滿足門限條件，如果滿足則退出勞埃德迭代否則繼續(xù)進(jìn)行勞埃德迭代直到滿足門限條件，生成碼書。LBG算法的關(guān)鍵代碼如下：
flag=0;//循環(huán)標(biāo)識(shí)
tcb(s,tv);//訓(xùn)練集和碼本建立關(guān)系
for(int i=0;iN;i++)
{ for(int j=0;jtv.M;j++)
{if(s[j]==i) n++;
yn[i]=n;
} }dsum=0;
for(int i=0;itv.M;i++)
{dsum=dsum+(long)min1(tv.train[i],1);
}d1=(double)(dsum/tv.M);
d=Math.abs(((double)(d0-d1)/(double)d1));
if(d1d0d>e)
{for(int i=0;iN;i++)
{if(yn[i]!=0)
{o=core(tv,i,s);
codebook[i].vcopy(o);
}d0=d1;
flag=1;
}while(flag==1);
在這段代碼中，首先建立碼本與訓(xùn)練矢量的關(guān)系，并經(jīng)過多次的勞埃德迭代直到滿足門限條件，生成新的碼書。這里應(yīng)用了LBG算法他具有如下的優(yōu)點(diǎn)：
1.不用初始化計(jì)算，可大大減少計(jì)算時(shí)間
2.初始碼字選自訓(xùn)練序列，無空胞腔問題
雖然LBG算法有如上的優(yōu)點(diǎn)，但是他本身也存在一些缺點(diǎn)和不足的地方，比如在計(jì)算的過程中可能會(huì)選到一些非典型矢量作碼字，因而該胞腔中只有很少矢量，甚至只有一個(gè)初始碼字，而且每次迭代又都保留了這些非典型矢量的形心；還可能會(huì)造成在某些空間把胞腔分得過細(xì)，而有些空間分得太大。這些缺點(diǎn)都會(huì)導(dǎo)致碼書中有限個(gè)碼字得不到充分利用，還需要進(jìn)一步的改進(jìn)算法。
程序整體流程圖如圖4.3所示：

圖4.3 軟件流程圖
4．2．3 矢量量化碼字索引與恢復(fù)
在這個(gè)程序中沒有考慮快速碼字搜索的算法，應(yīng)用了最佳碼字搜索的方法，使輸入矢量與所有的碼字進(jìn)行比較，選出距離最小的那個(gè)碼字成為匹配碼字，生成索引。這種算法雖然增加了計(jì)算量，但是減少了圖像數(shù)據(jù)壓縮過程中的失真。
在輸出端，將編碼過后生成的索引對(duì)照碼書，將圖像數(shù)據(jù)進(jìn)行還原。
4．3 實(shí)驗(yàn)結(jié)果及評(píng)價(jià)
在初始界面點(diǎn)擊瀏覽按鈕調(diào)入.BMP圖像。圖像就會(huì)顯示在程序運(yùn)行初始界面的左側(cè)，如圖4.3所示：

圖4.4 壓縮前的程序界面
點(diǎn)擊”壓縮”按鈕，程序就會(huì)自動(dòng)進(jìn)行矢量量化的壓縮，下面的進(jìn)度條會(huì)顯示壓縮的百分比，當(dāng)進(jìn)度達(dá)到100％時(shí)，程序就會(huì)將解壓好的圖像顯示在程序界面的左側(cè)。并顯示一系列的壓縮信息，包括壓縮源文件的大小，壓縮后的碼本大小，壓縮比，壓縮過程所需要的時(shí)間以及峰信噪比PSNR等信息。壓縮后的界面如圖4.5所示：

圖4.5 恢復(fù)后的程序界面
程序顯示的壓縮結(jié)果的壓縮比和壓縮時(shí)間上可以看出，這個(gè)利用矢量量化編碼算法的壓縮軟件可以達(dá)到16：1的高壓縮比，并且壓縮時(shí)間比較短。所以矢量量化壓縮編碼是一種非常有效的壓縮算法。
從壓縮圖像的效果來看，實(shí)驗(yàn)測試的圖像均采用的512×512，8比特/象素的women圖像作為訓(xùn)練圖像產(chǎn)生各種大小的碼書，矢量維數(shù)均為16，對(duì)壓縮程序進(jìn)行測試。通過變換碼書的大小，運(yùn)行程序得到不同的信噪比。測試結(jié)果如下表4.1所示：
表4.1 不同碼書的信噪比
序號(hào) 碼書大小 PSNR
1 64 27.36
2 128 27.74
3 256 28.54
4 512 29.28

如上表所示，隨著碼書的加大，系統(tǒng)的信噪比在升高，當(dāng)碼書大小為512時(shí)，PSNR可以達(dá)到29.28。圖像雖然有一定程度上的失真，但是并不是十分明顯，基本上保持了圖像原有的圖像質(zhì)量。
這個(gè)程序采用的是矢量量化碼書生成算法中的LBG算法，通過運(yùn)行程序以及對(duì)運(yùn)行結(jié)果的分析可以看出這種從標(biāo)量量化勞埃德迭代操作推廣出來的迭代算法具有以下兩個(gè)優(yōu)點(diǎn)：
1．不用初始化計(jì)算，可大大減少計(jì)算時(shí)間
2．初始碼字選自訓(xùn)練序列，無空胞腔問題
雖然LBG算法在具有如上的優(yōu)點(diǎn)，但是因?yàn)長BG算法是一種下降算法，每次迭代總能減少(至少保持不變)平均失真，而且每次迭代通常只能產(chǎn)生碼書的局部變化，即每次迭代后，與舊碼書相比，新碼書不可能有非常大的變化。所以初始碼書的選擇影響碼書訓(xùn)練的收斂速度和最終碼書的性能，一旦選定初始碼書，該算法只能得到局部最優(yōu)的碼書，即LBG算法一般不能得到全局最優(yōu)的碼書。
在每次迭代的最佳劃分階段，從碼書中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算；這對(duì)軟件大的運(yùn)行要求比較高的運(yùn)行環(huán)境。這個(gè)可以通過快速碼字搜索的算法來解決這個(gè)問題。

第五章 結(jié)論與展望
本文主要針對(duì)矢量量化的算法和實(shí)現(xiàn)研究與探討，本章主要對(duì)本文內(nèi)容與研究工作進(jìn)行一下總結(jié)。最后對(duì)矢量量化技術(shù)在今后發(fā)展方向上作了一些展望。
矢量量化技術(shù)作為數(shù)據(jù)壓縮領(lǐng)域里的一個(gè)分支，主要優(yōu)點(diǎn)是壓縮比大以及解碼簡單，在圖像壓縮方面已經(jīng)得到成功地應(yīng)用。目前， 矢量量化技術(shù)的研究主要集中在三個(gè)方面：矢量量化器的碼本設(shè)計(jì)，矢量量化碼字快速搜索算法設(shè)計(jì)，矢量量化碼字索引分配問題。本文主要研究了矢量量化碼本設(shè)計(jì)算法和碼字快速搜索算法，并討論了矢量量化技術(shù)的應(yīng)用問題。全文主要工作可以總結(jié)如下:
首先，介紹了數(shù)據(jù)壓縮算法的基本理論和發(fā)展現(xiàn)狀，討論了數(shù)據(jù)壓縮算法的分類體系和發(fā)展歷程。
其次，介紹了矢量量化技術(shù)的來源和發(fā)展歷程，重點(diǎn)介紹了關(guān)于矢量量化技術(shù)的技術(shù)基礎(chǔ)和矢量量化算法中的關(guān)鍵技術(shù)。
再次，研究了經(jīng)典的矢量量化的設(shè)計(jì)算法，分別研究討論了矢量量化中的LBG算法，最大下降算法；快速搜索算法中的基于不等式的快速搜索算法和碼字索引分配中的BSA算法等，并討論了現(xiàn)有各種矢量量化算法。
最后，介紹了一種LBG矢量量化算法的實(shí)現(xiàn)方法，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了性能評(píng)價(jià)。
以上是本文內(nèi)容的總結(jié)。還有許多問題沒有涉足或研究的深度不夠。矢量量化技術(shù)領(lǐng)域雖然已經(jīng)取得了長足的進(jìn)步，但總體上來說還有許多問題需要進(jìn)一步研究。下面對(duì)矢量量化未來發(fā)展的展望：
(1) 矢量量化是一種信源編碼技術(shù)，在矢量量化器設(shè)計(jì)的過程中，考慮如何降低信道傳輸中可能造成的噪聲干擾的影響，可以提高矢量量化系統(tǒng)的整體性能。歸結(jié)起來，可以用矢量量化碼書索引分配問題來描繪，即研究如何合理的安排碼書中碼字的排序，使得編碼系統(tǒng)在信道傳輸中的容錯(cuò)能力增強(qiáng)。
(2) 矢量量化作為一種數(shù)據(jù)壓縮技術(shù)，如何更好地應(yīng)用到實(shí)際的數(shù)據(jù)壓縮和傳輸系統(tǒng)中去，在實(shí)際應(yīng)用中體現(xiàn)編碼算法的優(yōu)越性，是一個(gè)很實(shí)際的問題，在設(shè)計(jì)算法的同時(shí)，要考慮應(yīng)用的實(shí)際情況。
(3) 本文中在圖像的編碼方面對(duì)矢量量化進(jìn)行研究，矢量量化技術(shù)并不僅僅用在圖像編碼中，可以根據(jù)實(shí)際需要，可以深入對(duì)其進(jìn)行深入研究，如可以在語音壓縮編解碼、音視頻壓縮和遠(yuǎn)程會(huì)議等方面，還可以將這些成果應(yīng)用到其方面一數(shù)字水印、語音識(shí)別、語音合成以及文字合成以及文字的識(shí)別等。