一種基于小波零樹編碼和K—mean聚類的圖像壓縮的實現

陳慧++龍飛++段智云

摘要：針對在低比特率時圖像存在嚴重的方塊效應等不足，本文提出了一種基于小波零樹編碼和K-mean聚類的圖像壓縮算法。其中基于小波零樹的圖像編碼克服了圖像JPEG標準壓縮算法在統計值較少時的方塊效應現象，通過K-mean聚類算法可以改善小波零樹編碼算法中沒有充分考慮到小波系數同一子帶中相鄰元素之間相關性的缺陷。實驗結果表明，此改進的圖像編碼算法具有較好的信噪比和壓縮比。

關鍵詞：圖像編碼；小波變換；K-mean聚類

中圖分類號：TN919.81

文獻標識碼：A

DOI： 10.3969/j.issn.1003-6970.2016.02.008

引言

目前為止，JPEG標準在中高碼率對于靜止的圖像取得了較好的壓縮性能，并且具有壓縮效率高和圖像質量損失少的優點，但自身也存在局限性。比如，圖像在低比特率時，重構圖像存在嚴重的方塊效應，不能很好地適應網絡傳輸中傳描圖像的需要；JPEG的壓縮比普遍不高，一般小于50%；基于DCT變換的JPEG標準壓縮算法，如果圖像的重要信息集中在相對窄小的頻段，DCT變換能得到較好的結果，然而如果圖像的細節是非平穩的，需要較寬的頻帶來表示，即需要許多變換系數的表述。基于小波零樹編碼和K-mean聚類的圖像壓縮算法，國內外學者已經進行了深入而廣泛的探討與研究。張琦在論文中提到了基于小波變換的圖像壓縮技術，但復原之后的圖像有明顯的方塊效應；柳斌等將基于零樹量化的小波編碼用于圖像壓縮中，但是圖像細節描述時間長，算法復雜度較高；吳青等手巴基于層次聚類的方法用于圖像壓縮算法的優化中，雖然可以實現時間優化，但也存在壓縮率低的缺點。

本文采用小波系數變換的圖像編碼，既可以克服了JPEG標準壓縮算法在低比特率下嚴重的方塊效應，又可以通過K-mean聚類算法改善小波零樹編碼算法中沒有充分考慮到小波系數同一子帶中相鄰元素之間相關性的缺陷，因此，在圖像壓縮的應用中有一定的價值和前景。

1 基于小波零樹編碼和K-mean聚類的圖像壓縮算法

l.l 小波變換的零樹編碼

小波零樹編碼用于圖像壓縮是小波分析應用的一個重要方面，它的特點是壓縮比高，壓縮速度快，壓縮后能保持信號與圖像的特征不變，且在傳遞中可以抗干擾。本文采用嵌入式小波變換（EZW），它是以相對適中的復雜度等級產生達到最新技術發展水平的壓縮性能。

通過掃描小波變換后生成二進制樹結構子帶的零樹來進行編碼，每一棵零樹的形成需要對圖像進行2次掃描。在生成第1棵零樹時，首先找出變換后圖像的最大絕對值系數，用它的一半作為初始閾值，對圖像進行第1次掃描，將變換圖像中絕對值小于閾值的系數看作0，在按照零樹符號的定義形成零樹；在第2次掃描中，對那些絕對值大于閾值的節點按其絕對值是否超過閾值的2.5倍附加一個比特l或0來描述其精度。然后將閾值減半再經2次掃描生成第2棵零樹，在第1次掃描生成零樹時，以前已經大于閾值的節點不再考慮，而第2次掃描附加比特時則要考慮以前非零的節點以繼續求精，如此往復下去，不斷生成零樹編碼直到達到需要為止。

1.2 K-mean聚類算法

K-me an聚類最早是由Mac Queer所提出來的，是以最小化適應函數作為判斷準則將所要分類的數據依次劃分到事先設定的類中。K均值聚類算法是采用多次迭代的反復循環過程的聚類算法，算法結束的標志是迭代結束，換句話說也就是聚類間的數據元素不會再一次被調整。K-mean聚類算法實現的一般步驟如下：

步驟一：將所要聚類的樣本數據量{Zii=l，2…n}聚成k類，則需要隨機產生聚類中心作為初始化類中心

步驟四：如果J不變或代表點未發生變化則算法結束，否則程序轉向步驟二。

2 基于小波零樹編碼和K-mean聚類的圖像壓縮算法的實現

基于小波零樹編碼和K-mean聚類算法的圖像壓縮，可獲得更高的壓縮效率，且其計算復雜度低，其具體步驟如下：

第一步：對輸入的圖像進行小波變換，分別低頻小波子帶系數和高頻子帶系數；

第二步：將具有相同屬性的圖像小波變換后的低頻系數組織起來進行描述，利用K-mean聚類算法分類低頻的小波子帶系數，劃分成K類，對聚類后的低頻系數做移位預處理；

第三步：圖像中每個低頻小波系數按照所屬的類中心，進行小波零樹編碼；

第四步：對圖像中其余的高頻小波系數進行小波零樹編碼。

3 實驗結果

實驗采用的圖像是標準測試庫圖像，在處理器為Intel Core 2，主頻1.26GHz的計算機上，通過MATLAB7.0對算法進行仿真，本文采用最優線性算法、JPEG算法和本文基于小波零樹編碼和K-mean聚類的圖像壓縮算法對Lena（256x256）圖像進行實驗并進行比較，計算峰值信噪比PSNR，表達式如下所示。

設f（i，i）表示原圖像的第i列j行的像素值，f（i，j）表示插值后圖像的第i列i行的像素值，M為圖像的高，N為圖像的寬。

同時選擇Borb、Boat和Lena圖像在相同的信噪比PSNR=20時進行壓縮比的比較。

本文算法克服了JPEG標準壓縮算法存在的方塊效應，其中，K代表的是K-mean聚類算法選取的類別數。表1給出了最優線性算法、JPEG標準壓縮算法和本文算法在聚類類別數為K=50、100下的MSE和PSNR。從表1中可以看出，本文算法兩個指標均優于JPEG算法，隨著聚類類別數K的增大，效果會更好；本文算法比最優線性和JPEG算法有更好的均方誤差和信噪比。表2給出，了相同PSNR條件下的壓縮比，即具有相同圖像質量條件下的壓縮比，從表2中看出，本文算法能夠在保證圖像質量一致的條件下，獲得比JPEG標準算法更大的壓縮比；相同信噪比下三幅圖像的壓縮比隨著K-mean聚類算法的類數增加有所增加。

4 結論

本文提出了一種通過小波零樹編碼和K-mean聚類算法的圖像壓縮算法，在客觀評價方面得到了較好的結果，通過小波系數分成高頻和低頻信息，分別采用不同的方法進行量化編碼，取得了理想的效果，有一定的使用價值。本文通過采用小波域系數的零樹編碼算法，克服了JPEG標準壓縮算法在低比特率下嚴重的方塊效應，通過K-mean聚類算法，克服了嵌入式零樹編碼算法沒有充分考慮到圖像小波系數同一子帶中相鄰元素之間相關性的缺陷。本文算法的輸出碼可進一步利用熵編碼提高壓縮比，或通過碼率分配進一步提高壓縮性能。另外，如何結合實際應用，更好地選擇聚類參數K值，亦可作為下一步研究的一個重點，嘗試使用不同的聚類方法加以改進也是研究的難點。