基于矢量量化編碼的數據壓縮算法的研究與實現
加入技術交流群
Step 4：如果 >0，則交換索引n和引起最大失真下降的索引j，并轉Step 2；
Step 5：終止算法。如果n=N一1，則終止算法，否則，轉Step 3。
可以看出，BSA算法根據函數值 將碼字進行排列而選擇出哪一個碼字最先進行交換，從而在運算上給出了一個方向性引導。如果由于程序運行時間的限制而使算法的迭代次數有限，則這種方向性引導將顯得尤為重要。每一次成功交換的完成，代表一次迭代的結束。若一次迭代中的所有試驗性交換產生的失真下降都不大于O，則說明算法已經達到一個局部最優(yōu)解.應該指出的是:從不同的初始碼字排序出發(fā)，可獲得不同的局部最優(yōu)解，從而保證BSA算法對于碼字交換的限制不會影響它獲得全局最優(yōu)碼字索引分配方案的可能性。實驗證明，該算法獲得的碼字索引分配方案的失真比隨機碼字索引分配方案的失真有較大改進。
3．3．2 禁止搜索碼字索引算法
禁止搜索的基本思想是通過一系列移動來搜尋所有可行解的搜索空間，并且在當前迭代中禁止某些搜索方向以避免死循環(huán)和跳入局部極小。由當前解到其鄰域解的移動被部分地或完全地記錄在禁止表中，目的是為了禁止以后迭代中的重復操作。
令 為測試解的集合，其中元素si可以被表示為式【8】（3.22）：
（3.22）
其中，N為碼書的尺寸，Si(j)表示在解si中分配給碼字Yj的索引， 令 和 分別表示當前解和最優(yōu)解。中碼字Yj的索引，Sb(j)仍表示分配給解Sb中碼字Yi的索引。
令 ， 和 分別代表測試解組的目標函數值集合，當前解的目標函數值和最優(yōu)解的目標函數值，其中 是測試解 的目標函數值，0iNs-1。初始的當前解是隨機產生的，通過隨機交換當前解中的兩個索引來產生測試解。禁止表中只存儲交換的索引。如果從當前解中產生測試解的交換索引與禁止表中任何記錄相同，則稱該測試解為禁止解。該算法的具體步驟如下:
Step 1：設置禁止表大小Ts測試解個數N，以及迭代次數Im。令迭代計數器i=1，禁止表插入點t=1。隨機產生當前解 ，計算其相應的目標函數值V}。令Sb=Sc以及Vb=Vc
Step 2：把當前解Sc拷貝給每一個測試解si, 0iNs-1。對每一個測試解si，0i Ns-1，產生兩個隨機整數r1和r2， ， ， 。N為碼字個數，然后通過交換索引 和 產生新測試解組。計算測試解的函數值 。
Step 3：如果最優(yōu)測試解的目標函數值比最優(yōu)解的目標函數值Vb還小，則把它作為新的當前解，并令其目標函數值作為當前解的目標函數值Vc，轉Step 3。否則，選出測試解中最好的非禁止解。如果能選到，則把它作為新的當前解Sc并令其目標函數值作為當前解的目標函數值Vc，轉Step 3；否則，轉Step 1。
Step 4： 如果vb>vc，令Sb=Sc，Vb＝Vc，把從舊當前解到新當前解所交換過的索引插入禁止表中。禁止表的插入點設為ti=ti+1;如果ti>Ts，令ti＝l，如果iIm，令i=i+1轉Step 1；否則，算法結束。本文引用地址：http://cafeforensic.com/article/172694.htm
第四章 矢量量化算法的實現
4．1 需求分析與整體設計
4．1．1需求分析
隨著數字技術的飛速發(fā)展，越來越多的信息(文本、圖形、圖像、動畫、音頻及視頻影像等)采用數字化的形式存儲、傳輸和檢索。由于網絡上的數據流量飛速增長，而且網絡的帶寬總是滿足不了需求，數據壓縮編碼技術的迅猛發(fā)展，要求在盡量不損傷多媒體質量的情況下壓縮數據量。
正是由于這種需求的存在，要求開發(fā)一套完整的數據壓縮軟件，利用矢量量化的數據壓縮算法，能夠調用BMP格式的圖像，對載入的圖像進行壓縮并顯示解壓后的圖像效果，能夠選擇路徑保存解壓后的圖像實現SNR信噪比的計算，便于對壓縮軟件性能的評價。
4．1．2 整體設計
軟件的設計在Eclipse開發(fā)工具下編譯Java應用程序。利用Java語言的面向對象的特點，充分利用他的可封裝性，重用性和多態(tài)性等特點，開發(fā)一整套完整的基于矢量量化數據壓縮算法的壓縮軟件。
將這個數據壓縮軟件從整體上分五個模塊來實現的。Bmp格式圖像的調入和保存模塊，圖像矢量塊的劃分模塊，初始碼書生成模塊，LBG量化模塊，圖像解壓模塊。如圖4.1所示：
圖4.1程序模塊框圖
軟件界面的設計。在JAVA的運行環(huán)境下要實現基于矢量量化數據壓縮算法對BMP格式的靜止圖像進行壓縮與解壓。軟件界面的設計，在圖像界面的左側可以顯示調入的圖像，右側顯示圖像信息。在瀏覽按鈕上可以調入待壓縮的圖像，并且可以選擇解壓后的圖像的保存位置。選擇好解壓圖像后點擊壓縮按鈕即可開始對圖像進行矢量量化的壓縮。最后顯示壓縮的結果，包括原始圖像的大小，壓縮后的大小，壓縮比，壓縮時間及PSNR值等信息。軟件運行的初始界面如圖4.2所示：
圖4.2程序運行初始界面
4．2 矢量量化算法的實現過程及說明
4．2．1 初始碼書的生成
這個程序利用了隨機編碼生成碼書的方法，即根據輸入信源分布直接從訓練序列中隨機選擇N個訓練矢量作為初始碼字以構成初始碼書。該方法的優(yōu)點是計算量低，初始碼書的生成較為容易。雖然可能出現碼書的分布不均勻的現象，但是配合LBG算法的多次迭代可以得到補償。需要注意，這里所說的隨機編碼是說初始碼書的選擇方式是隨機的，而一旦碼書選定，編碼器的工作方式則是按著最近鄰方式進行的。隨機碼書的生成代碼如下：
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碼書設計流程圖
如圖4.2所示的流程圖，對隨機生成初始碼書，碼書大小N，訓練矢量序列，停止計算門限和起始平均失真的初始碼書進行勞埃德迭代。用初始碼書為已知的心形，把訓練序列重新劃分為N個胞腔。計算新的平均失真和相對失真，判斷新的失真是否滿足門限條件，如果滿足則退出勞埃德迭代否則繼續(xù)進行勞埃德迭代直到滿足門限條件，生成碼書。LBG算法的關鍵代碼如下：
flag=0;//循環(huán)標識
tcb(s,tv);//訓練集和碼本建立關系
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);
在這段代碼中，首先建立碼本與訓練矢量的關系，并經過多次的勞埃德迭代直到滿足門限條件，生成新的碼書。這里應用了LBG算法他具有如下的優(yōu)點：
1.不用初始化計算，可大大減少計算時間
2.初始碼字選自訓練序列，無空胞腔問題
雖然LBG算法有如上的優(yōu)點，但是他本身也存在一些缺點和不足的地方，比如在計算的過程中可能會選到一些非典型矢量作碼字，因而該胞腔中只有很少矢量，甚至只有一個初始碼字，而且每次迭代又都保留了這些非典型矢量的形心；還可能會造成在某些空間把胞腔分得過細，而有些空間分得太大。這些缺點都會導致碼書中有限個碼字得不到充分利用，還需要進一步的改進算法。
程序整體流程圖如圖4.3所示：
圖4.3 軟件流程圖
4．2．3 矢量量化碼字索引與恢復
在這個程序中沒有考慮快速碼字搜索的算法，應用了最佳碼字搜索的方法，使輸入矢量與所有的碼字進行比較，選出距離最小的那個碼字成為匹配碼字，生成索引。這種算法雖然增加了計算量，但是減少了圖像數據壓縮過程中的失真。
在輸出端，將編碼過后生成的索引對照碼書，將圖像數據進行還原。
4．3 實驗結果及評價
在初始界面點擊瀏覽按鈕調入.BMP圖像。圖像就會顯示在程序運行初始界面的左側，如圖4.3所示：
圖4.4 壓縮前的程序界面
點擊”壓縮”按鈕，程序就會自動進行矢量量化的壓縮，下面的進度條會顯示壓縮的百分比，當進度達到100％時，程序就會將解壓好的圖像顯示在程序界面的左側。并顯示一系列的壓縮信息，包括壓縮源文件的大小，壓縮后的碼本大小，壓縮比，壓縮過程所需要的時間以及峰信噪比PSNR等信息。壓縮后的界面如圖4.5所示：
圖4.5 恢復后的程序界面
程序顯示的壓縮結果的壓縮比和壓縮時間上可以看出，這個利用矢量量化編碼算法的壓縮軟件可以達到16：1的高壓縮比，并且壓縮時間比較短。所以矢量量化壓縮編碼是一種非常有效的壓縮算法。
從壓縮圖像的效果來看，實驗測試的圖像均采用的512×512，8比特/象素的women圖像作為訓練圖像產生各種大小的碼書，矢量維數均為16，對壓縮程序進行測試。通過變換碼書的大小，運行程序得到不同的信噪比。測試結果如下表4.1所示：
表4.1 不同碼書的信噪比
序號 碼書大小 PSNR
1 64 27.36
2 128 27.74
3 256 28.54
4 512 29.28
如上表所示，隨著碼書的加大，系統(tǒng)的信噪比在升高，當碼書大小為512時，PSNR可以達到29.28。圖像雖然有一定程度上的失真，但是并不是十分明顯，基本上保持了圖像原有的圖像質量。
這個程序采用的是矢量量化碼書生成算法中的LBG算法，通過運行程序以及對運行結果的分析可以看出這種從標量量化勞埃德迭代操作推廣出來的迭代算法具有以下兩個優(yōu)點：
1．不用初始化計算，可大大減少計算時間
2．初始碼字選自訓練序列，無空胞腔問題
雖然LBG算法在具有如上的優(yōu)點，但是因為LBG算法是一種下降算法，每次迭代總能減少(至少保持不變)平均失真，而且每次迭代通常只能產生碼書的局部變化，即每次迭代后，與舊碼書相比，新碼書不可能有非常大的變化。所以初始碼書的選擇影響碼書訓練的收斂速度和最終碼書的性能，一旦選定初始碼書，該算法只能得到局部最優(yōu)的碼書，即LBG算法一般不能得到全局最優(yōu)的碼書。
在每次迭代的最佳劃分階段，從碼書中搜索訓練矢量的最近碼字需要大量的存儲空間和繁瑣的計算；這對軟件大的運行要求比較高的運行環(huán)境。這個可以通過快速碼字搜索的算法來解決這個問題。
第五章 結論與展望
本文主要針對矢量量化的算法和實現研究與探討，本章主要對本文內容與研究工作進行一下總結。最后對矢量量化技術在今后發(fā)展方向上作了一些展望。
矢量量化技術作為數據壓縮領域里的一個分支，主要優(yōu)點是壓縮比大以及解碼簡單，在圖像壓縮方面已經得到成功地應用。目前， 矢量量化技術的研究主要集中在三個方面：矢量量化器的碼本設計，矢量量化碼字快速搜索算法設計，矢量量化碼字索引分配問題。本文主要研究了矢量量化碼本設計算法和碼字快速搜索算法，并討論了矢量量化技術的應用問題。全文主要工作可以總結如下:
首先，介紹了數據壓縮算法的基本理論和發(fā)展現狀，討論了數據壓縮算法的分類體系和發(fā)展歷程。
其次，介紹了矢量量化技術的來源和發(fā)展歷程，重點介紹了關于矢量量化技術的技術基礎和矢量量化算法中的關鍵技術。
再次，研究了經典的矢量量化的設計算法，分別研究討論了矢量量化中的LBG算法，最大下降算法；快速搜索算法中的基于不等式的快速搜索算法和碼字索引分配中的BSA算法等，并討論了現有各種矢量量化算法。
最后，介紹了一種LBG矢量量化算法的實現方法，并對實驗結果進行了性能評價。
以上是本文內容的總結。還有許多問題沒有涉足或研究的深度不夠。矢量量化技術領域雖然已經取得了長足的進步，但總體上來說還有許多問題需要進一步研究。下面對矢量量化未來發(fā)展的展望：
(1) 矢量量化是一種信源編碼技術，在矢量量化器設計的過程中，考慮如何降低信道傳輸中可能造成的噪聲干擾的影響，可以提高矢量量化系統(tǒng)的整體性能。歸結起來，可以用矢量量化碼書索引分配問題來描繪，即研究如何合理的安排碼書中碼字的排序，使得編碼系統(tǒng)在信道傳輸中的容錯能力增強。
(2) 矢量量化作為一種數據壓縮技術，如何更好地應用到實際的數據壓縮和傳輸系統(tǒng)中去，在實際應用中體現編碼算法的優(yōu)越性，是一個很實際的問題，在設計算法的同時，要考慮應用的實際情況。
(3) 本文中在圖像的編碼方面對矢量量化進行研究，矢量量化技術并不僅僅用在圖像編碼中，可以根據實際需要，可以深入對其進行深入研究，如可以在語音壓縮編解碼、音視頻壓縮和遠程會議等方面，還可以將這些成果應用到其方面一數字水印、語音識別、語音合成以及文字合成以及文字的識別等。
評論