基于小波變換的分形圖像編碼壓縮算法

趙 蓉 王 輝 張愛華

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

0 引 言

分形圖像編碼最早是將原始圖像表示為圖像空間中一系列壓縮映射的吸引子。后來基于方塊分割的算法又被提出，但因花費時間過多，不能被廣泛應用。近年來，新提出的特征向量法應用方便、效果好。根據圖像子圖的特征點的選取原則，本文選取規范化圖像子塊的九塊(4個頂點，4條邊上的中點及一個中心點)位置上的像素點作為特征點，并以這些特征點的歸一化值的絕對值和來定義圖像子塊的九塊和特征。先在理論上證明九塊和與均方誤差的關系不等式，再對碼本中的碼本塊按照其九塊和的大小進行排序，找到R塊的初始匹配塊之后，直接在鄰域內進行匹配搜索。這樣可以有效地縮小搜索范圍，從而減少分形編碼時間。

分形編碼的發展有力地推動了圖像編碼技術的發展，但是壓縮時間較長，不能滿足實時處理的要求。近年來，將分形編碼與小波結合的混合編碼方法取得了巨大的成功[1-7]。小波變換不可以直接用于壓縮，但可以用來分解圖像。圖像經小波變換后，得到小波系數。雖然小波變換前后的數據量相同，但小波變換后，圖像的能量得到了重新分配，低頻子帶集中了絕大部分能量，3個高頻子帶擁有的能量少，因此對低頻子帶采用盡量多的量化級別，其他子帶采用較少的量化級別。并且圖像經過多級小波分解后，得到的各級子帶間具有較強的相似性，而分形的優勢就是在于自相似性強的圖像[6]。因此，本文將小波與九塊和特征相結合，取得了一些進展。

1 小波變換的理論基礎

1.1 小波定義和連續小波變換

小波定義：對于任意一函數ψ(t),若ψ(t)∈L2(R)，即函數平方可積，當滿足：

(1)

則稱ψ(t)為基本小波或母小波，當ψ(t)隨著t的變化而上下浮動時，形成小波。

連續小波變換定義：對于f(t)∈L2(R)，ψ(t)∈L2(R)，滿足：

Wf(a,b)=〈f,ψa,b〉=

(2)

則稱Wf(a,b)是f(t)的連續小波變換，ψ(t)為小波函數，參數a、b分別代表尺度因子和平移因子。

連續小波的逆變換定義：對于f(t)∈L2(R)，有:

(3)

1.2 小波基的性質

選擇小波時，要綜合考慮其正則性、消失矩、緊支撐性三個方面。正則性好的小波，在圖像經過小波逆運算后，還可以恢復完整的圖像，支撐區間的長短決定了運算量，從而影響運算速率。

(1) 正則性：可以判斷函數的光滑度，也可以記錄函數在頻域部分能量的集中度。

(2) 消失矩：消失據越大，圖像經過小波變換后的能量越集中，此時，壓縮比變高，所以消失矩越高性能越好。

(3) 緊支撐性：濾波器太長會造成計算量過大。

為了取得更好的壓縮效果，我們應該選擇正則性好、消失矩高、支撐區間短的小波，但是小波的消失矩和緊支撐性關系密切，在實際問題中常采用折中選擇。本文綜合考慮以上三個要素后，選取sym1小波。

1.3 二級小波分解

圖像經過一級小波分解后，得到4個子帶：包含圖像絕大部分信息的低頻子帶LL、包含紋理特征及邊緣信息的水平子帶HL、垂直子帶LH、對角子帶HH。文獻[6]給出了多級小波分解方法，本文選用二級小波分解，如圖1所示。

圖1 二級小波分解示意圖

2 九塊和特征的理論依據

定義1設子塊X=(xi,j)∈Rn×n,則X規范化為:

(4)

(5)

定義2九塊和特征定義為：

(6)

定理1設R,D∈Rn×n,則有如下不等式成立：

(7)

證明:定義子塊Q=(qi,j)∈Rn×n如下：

(n=2k+1)

(n=2k)

根據向量2-范數和九塊和定義有：

(8)

(9)

結合式(9)，得到：

(10)

證畢。

3 小波變換和九塊和特征相結合的圖像壓縮方法

分形圖像壓縮的過程中會出現“方塊效應”，而將小波變換用于圖像壓縮領域，可以避免該現象的發生，由此提出了將小波變換和九塊和特征相結合的圖像壓縮方法。該方法用選好的小波，對待編碼的圖像作二級小波分解，得到圖像的7個子帶，如圖1所示，其中低頻子帶LL2保留了原始圖像的大部分特征信息，所以本文中保留了LL2子帶，不對其作分形壓縮。而對其余子帶選用九塊和特征進行分形壓縮。其中：LH1、HL1、HH1為一級子帶，LH2、HL2、HH2為二級子帶，由于一級和二級子帶大小不同，所以在對其進行壓縮編碼時二級子帶R塊和D塊大小分別取為一級子帶R塊和D塊大小的1/4。

小波變換不具備壓縮功能，其能被應用到圖像壓縮的主要原因是：圖像經過小波變換后，能量得到了重新分配，可以對得到的小波系數進行編碼，從而實現壓縮。

3.1 算法分析

在分形編碼中，如果D是R的最佳匹配塊，則E(R,D)會很小，結合式(7)，此時會出現兩種情況，R的標準差σR很小或R與D的特征值比較接近[9]。為了排除σR很小的情況，設定一個閾值τ?0，當σRτ，則定義R塊為平滑塊，否則屬于非平滑塊。對于平滑塊R，有：

(11)

由式(12)可知，只要給定D塊標準差大，得到的|s|就小,那么其小于1的可能性就越大，就不會被截斷處理，這樣解碼得到的圖像質量就越好。因此，設定門限η?τ，去掉σDη的碼塊D，構成容許碼本Ωη={D∈Ω|σD≥η}。此時，R與D的特征值比較接近。

如果子塊R與碼本D是匹配的，必有q(R)≈q(D)成立,且子塊R的最佳匹配塊D在九塊和意義下，定在R的近鄰里。當q(R)≈q(D)代表兩個子塊可能匹配，但匹配的兩個子塊不一定滿足q(R)≈q(D)這個條件。這表明q(R)≈q(D)只是子塊能夠匹配的一個必要條件，但不是充要條件。

3.2 算法實現

通過以上分析，本文算法具體步驟如下：

1) 通過二級小波分解，將圖像分解為7個子帶，保留低頻子帶的小波系數，對其余6個子帶小波系數的符號單獨編碼。

2) 對這6個子帶，再進行基于九塊和特征的分形圖像編碼。

(1) 對于一級子帶圖像，將其分割成R塊(不能重疊，8×8 大小)及D塊(能重疊，16×16大小)。對于二級子帶圖像，將其分割成R塊(不能重疊，4×4大小)及D塊(能重疊，8×8大小)。

(2) 將每個D塊收縮后的全體作為碼本Ω，然后設定τ、η、k(R塊的標準差閾值、碼塊的標準差閾值、鄰域半徑)，并篩選碼本構成新碼本Ωη={D∈Ω|σD≥η}，根據九塊和特征大小賦序。

(3) 對于子塊R，如果σRτ，則用作為新R；如果σR≥τ，計算q(R)，在Ωη中尋找其初始匹配塊Dinit(用二分法)。

3) 將各個子帶的分形碼合成整個原圖像的分形碼。

4) 根據分形碼信息對各個子帶進行解碼操作，得到解碼后的圖像，在進行反小波變換，生成重構圖像。

4 實驗結果分析

測試圖像: couple; Lena; woman2; crowd等(方塊分割)，實驗平臺是：Windows 10操作系統(2.3 GHz i5-6300HQ/8 GB內存)，算法由MATLAB R2016a軟件實現。實驗結果如下：

選取多組圖片用于實驗，來比較本文算法與基本分形算法，實驗結果見表1。可以看出，本文算法在k=1的情況下，就差不多達到基本分形算法的PSNR值，并且可以實現加速至少111倍以上。說明，本文算法優于基本分形算法。

表1 基本分形算法與文中算法對比結果

算法的編碼時間和重建圖像的質量都依賴于:R塊的標準差閾值τ和D塊的標準差閾值η這兩個控制參數。本文在比較新算法結果與叉跡算法、小波加相似比算法的結果時，調整各自的τ和η，達到最好效果，對搜索鄰域控制變量。根據文獻[10]，叉跡算法參數默認τ=4、η=30。經過反復實驗，本文算法及小波加相似比算法選取τ=4、η=3。

選用叉跡算法、小波加相似比算法[2]及本文算法，分別對Lena、woman2 兩幅圖進行實驗，通過不斷變化搜索鄰域k,獲得大量PSNR值及其耗時的數據，其中：對Lena圖進行實驗得到的數據記錄在表2；對woman2圖進行實驗得到的數據記錄在表3。由表2、表3可知，同一幅圖在同一搜索鄰域下，本文算法與叉跡算法的耗時相近，但是本文算法的PSNR大大高于叉跡算法結果。分析Lena圖像的數據，叉跡算法在k=50時，PSNR=31.1、t=6.12,而本文算法在k=0時，PSNR就達到了32.06，用時0.75，說明在圖像質量變好的情況下，還可以實現加速8倍(同理，選用woman2圖像，實現加速7倍)。

表2 叉跡算法、小波加相似比算法與文中算法對比結果(實驗圖像Lena)

表3 叉跡算法、小波加相似比算法與文中算法對比結果(實驗圖像woman2)

改進算法的目的是為了提高圖像質量或減少編碼時間，所以為了更加直觀地比較小波加相似比算法和本文算法，以時間為橫坐標，PSNR為縱坐標，將同一幅圖在不同鄰域下獲得的PSNR及時間數據繪制成二維圖像，結果見圖2、圖3。圖2數據是對Lena圖像編碼得到，圖3數據是對woman2圖像編碼得到。可以看出，在耗時相同時，本文算法的PSNR明顯高于小波加相似比算法；在獲得相同PSNR時，本文算法耗時更少，說明本文算法優于小波加相似比算法。用三種算法分別對woman2、Lena、man三幅圖在k=1條件下進行實驗，實驗效果圖見圖4。

圖2 三種算法的性能對比圖(實驗圖像Lena)

圖3 三種算法的性能對比圖(實驗圖像woman2)

(a) 叉跡算法(b) 小波加相似比算法(c) 本文算法圖4 基本分形算法，叉跡算法，本文算法效果圖

5 結 語

本文提出將小波與九塊和特征相結合的算法，并明確給出九塊和特征下，關于均方誤差的理論證明，把在大量碼本D中搜索R塊的全搜索問題轉化為九塊和特征意義下初始匹配塊Dinit的近鄰問題。實驗結果顯示本文算法在與基本分形算法比較時，能在保證圖像質量前提下，實現加速216倍，并且優于叉跡算法和小波加相似比算法。因此，本文提出的基于九塊和特征的算法是有效的。