基于小波變換與分形結合的圖像壓縮算法

汪瑋瑋，張愛華

(南京郵電大學 理學院，江蘇 南京 210046)

0 引 言

將分形理論[1]用在圖像壓縮上之所以有作用，是因為根據此理論，從計算的角度很多復雜的圖像信息含量很少，可以通過簡單的算法迭代出來。比如自然界中的蕨類植物圖像，看起來比較復雜，如果用一般圖形表示法需要上萬個數據，但是如果采用分形理論方法，只需要24個數據，建立迭代函數系統就可以在計算機上產生這類圖像。因此，通過迭代函數系統，利用參數不多的算法可以將相當復雜的自然圖像顯示在計算機上，也就是說，通過簡單的算法就可以控制復雜圖像，這是分形理論在圖像壓縮領域應用的主要根據之一[2-7]。此外，分形意味著自然界是許多復雜形態中潛藏著有組織的結構，如果能在這些復雜的形態中提取出關鍵的有效信息，很容易就可以將自然界的復雜圖像進行清晰的展現，這是分形理論在圖像壓縮領域應用的另一個重要依據[8-11]。當今，眾多學者研究此類問題的關鍵指向了如何在保證圖像質量的前提下加快分形編碼的速度[12]。

小波變換理論在圖像壓縮處理領域的應用也非常廣泛[13-16]。眾所周知，一幅圖像經過小波變換處理后，總數據量既沒有增加也沒有減少，由于一幅圖像的低頻區域包含主要信息，而一些其他的細節信息保存在高頻區域。因此不難想到一種簡單的圖像壓縮方法就是將圖像高頻區域部分的信息去除，而保存低頻區域部分的信息。這種方法雖然簡單，但是在圖像壓縮后沒有了細節信息，影響效果。因此文中提出一種結合小波變換和分形特征的方法。由于圖像經過小波變換后，其自相似性被破壞，在引入分形特征時，對于低頻區域圖像信息不再進行分形壓縮，直接保存處理；在高頻區域則利用提出的相似比特征，進行分形編碼壓縮。

1 算法的理論基礎

1.1 小波變換的定義

1.2 小波變換壓縮方法

考慮到二維尺度函數式可分離，也就是φ(x,y)=φ(x)φ(y)，其中φ(x)是一個尺度函數。二維尺度函數的伸縮和平移變換記為φj,m,n(x,y)=2jφ(x-2jm,y-2jn)，其中j,m,n是整數。簡單概括一下，小波變換壓縮方法的過程是從一幅2N×2N原始圖像f1(x,y)開始，在每一次變換中，利用一個小波基圖像與原始圖像做內積運算，然后與x和y坐標上每隔兩個點取出一個點抽樣而生成，這樣每次變換可以分解成四個1/4大小的、分辨率不同的子圖像。

利用小波變換分解圖像，分解后圖像的總數據信息量沒有發生變化，但是圖像中的數據信息發生了轉移，分解之后的一系列子圖像，它們的分辨率都不相同。子圖像的分辨率與頻率呈正比，其中高頻率的子圖像上的數據信息比較少，大部分數值接近于零。所以一幅圖像的低頻區域包含主要信息，而一些其他的細節信息保存在高頻區域，因此提出一種將小波變換和分形特征相結合的方法。

2 基于子塊特征的快速分形編碼方法

根據基本分形編碼算法的公式知，碼本池Ω容量的大小決定了編碼過程中所耗費的時間。如果能夠通過定義圖像子塊的特征，將全局搜索轉變為該特征下的近鄰搜索，這樣就縮減了匹配搜索的空間，即能減少編碼過程中的時間消耗。

在基本分形編碼算法中，為了尋求R塊的最佳匹配塊，需要求解下面的極小化問題：

(1)

其中，m表示R塊的最佳匹配塊序號；I∈Rn×n表示所有元素均為1的常值塊；R=(r1,…,rk,…,rN)，D=(d1,…,dk,…,dN)分別表示R塊、D塊像素點灰度值按某種方式向量化后的向量。

每個待編碼的R塊通過自仿射變換ω在碼本池Ω中尋找均方根誤差最小的D塊作為其最佳匹配塊，即：

R≈ω(D)=s·D+o·I

(2)

用最小二乘法求得極小化問題的解為：

(3)

此時，匹配的誤差就為：

(4)

將式3中的ο代入式2有：

(5)

若將與R塊、D塊相同位置的小塊R1和D1取出來，那它們也應該滿足：

(6)

將式5、6兩邊同時做比值，得到：

(7)

由此可以看出，如果R塊和D塊能夠匹配成對，那么它們的自相似比也應當比較接近。

下面給出了圖像子塊的一種新特征定義，并對該特征與匹配誤差之間的關系進行了說明。

首先將每一幅圖像的子塊R與D平均分成四個部分(見圖1)，再分別求出每個部分的灰度均值。根據它們的空間位置，令其對角線兩元素之差組成叉乘向量：

圖1 D塊(左)和R塊(右)

下面給出相似比特征φ(D)的可行性分析：

R≈s·D+ο·I

所以，φ(R)≈φ(D)。

3 小波與分形相結合的圖像壓縮方法

為了實現圖像處理的批量化，將小波變換與分形特征相結合，先利用小波變換對圖像進行壓縮處理，再將分形特征算法引入進來，將這兩種方法疊加進行處理。

首先，將待壓縮的圖像處理成一幅二維數字圖像，對其分別進行垂直和水平方向的小波濾波處理，從而將圖像分成四個離散的子帶。四個子帶分別是：垂直和水平方向的低頻子帶LL1(它能夠反映原圖像的基本特性)、水平方向的低頻和垂直方向的高頻子帶LH1、水平方向的高頻和垂直方向的低頻子帶HL1以及水平和垂直方向的高頻子帶HH1。這三個子帶所反映的主要是該圖像在水平方向、垂直方向與對角線方向的邊緣、紋理和輪廓等特征信息。圖像經過小波分解后被分成低頻區域和高頻區域，低頻區域在很小的空間內卻包含了原始圖像的大部分特征信息，然而高頻區域往往占用很大的空間，卻只散布著原始圖像的小部分特征信息。所以，正是由于圖像經過小波變換，其自相似性被破壞，在引入分形特征時，對于低頻區域的圖像信息不再進行分形壓縮，直接保存處理即可；而在高頻區域則利用上述提出的相似比特征，進行分形編碼壓縮。

4 算法實現

4.1 算法步驟

根據以上分析，文中提出的方法實現如下：

(2)進行小波變換分解后，每一個子分量會分成七個子帶，將LL1量化后直接保存，對LH1、HL1、HH1、LH2、HL2、HH2再次進行分形特征的編碼處理。

①將低頻圖像分割成大小為B×B的R塊，同時，以橫縱方向步長均為x的像素形成大小為2B×2B的D塊池，由這些子塊構成的集合稱為碼本Ωη={D∈Ω|σD≥η}。其中η為碼塊標準差閾值，y1為R塊的標準差閾值。

②對于子塊R：如果σR

③在Dm的t鄰域內搜索最佳匹配塊，如果E(R,D)

④記錄下最佳匹配塊D的位置、s、o的值以及變換的類型。對于剩下的子塊R，重復上述步驟。

(3)對經過分形壓縮編碼處理后的各子帶進行解碼，通過迭代操作，得到各子帶解碼后的圖像信息。

(4)對解碼完成的圖像進行小波反變換，最終得到壓縮后的圖像信息。

4.2 實驗結果及分析

用MATLAB R2012b對大小為512×512的Lena圖像進行實驗，將圖像壓縮編碼的時間和峰值信噪比作為評價算法性能的指標。其中取D塊的標準差閾值η=1 225，R塊的標準差閾值y1=1。將得到的實驗結果分別與基本分形算法和小波與歐氏比特征結合的算法進行比較，結果如圖2～4以及表1所示。

圖2 Lena圖像

圖3 文中算法(t=10)

圖4 小波與歐氏比特征結合算法(t=10)

迭代次數鄰域參數(t)文中算法基本分形算法小波+歐氏比算法PSNR/dBTime/sPSNR/dBTime/sPSNR/dBTime/s1145.933.83339.5213.84538.9230.5223.64342.4545.8715.2443.2132.4139.63110.135148.294.13352.2514.18552.9633.5055.87355.0748.769.8950.5841.5452.6890.3110148.294.33352.2514.62552.9531.0256.04365.9848.7812.4050.6241.3652.7391.12

根據以上仿真數據分析可以知道，與基本分形理論算法相比，文中提出的方法在保證一定重構圖像質量的前提下，大大縮短了圖像壓縮編碼的時間；而與文獻[10]提出的算法相比，文中方法不僅提高了圖像壓縮編碼的速度，而且在一定程度上改善了重構圖像的質量。

5 結束語

基于子塊特征縮短編碼時間的現狀，結合小波變換的特點，選用分形與小波變換相結合的圖像壓縮方法，以進一步減少編解碼時間，同時改善重構圖像的質量。仿真結果表明，與基本分形算法以及同類特征算法相比較，該算法在壓縮時間上效果更優，這也為今后研究多種混合編碼算法打下了鋪墊。