趙 蓉 王 輝 張愛華

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

0 引 言

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

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

1 小波變換的理論基礎(chǔ)

1.1 小波定義和連續(xù)小波變換

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

(1)

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

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

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

(2)

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

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

(3)

1.2 小波基的性質(zhì)

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

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

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

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

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

1.3 二級小波分解

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

圖1 二級小波分解示意圖

2 九塊和特征的理論依據(jù)

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

(4)

(5)

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

(6)

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

(7)

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

(n=2k+1)

(n=2k)

根據(jù)向量2-范數(shù)和九塊和定義有：

(8)

(9)

結(jié)合式(9)，得到：

(10)

證畢。

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

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

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

3.1 算法分析

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

(11)

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

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

3.2 算法實現(xiàn)

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

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

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

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

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

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

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

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

4 實驗結(jié)果分析

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

選取多組圖片用于實驗，來比較本文算法與基本分形算法，實驗結(jié)果見表1?？梢钥闯觯疚乃惴ㄔ趉=1的情況下，就差不多達(dá)到基本分形算法的PSNR值，并且可以實現(xiàn)加速至少111倍以上。說明，本文算法優(yōu)于基本分形算法。

表1 基本分形算法與文中算法對比結(jié)果

算法的編碼時間和重建圖像的質(zhì)量都依賴于:R塊的標(biāo)準(zhǔn)差閾值τ和D塊的標(biāo)準(zhǔn)差閾值η這兩個控制參數(shù)。本文在比較新算法結(jié)果與叉跡算法、小波加相似比算法的結(jié)果時，調(diào)整各自的τ和η，達(dá)到最好效果，對搜索鄰域控制變量。根據(jù)文獻(xiàn)[10]，叉跡算法參數(shù)默認(rèn)τ=4、η=30。經(jīng)過反復(fù)實驗，本文算法及小波加相似比算法選取τ=4、η=3。

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

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

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

改進(jìn)算法的目的是為了提高圖像質(zhì)量或減少編碼時間，所以為了更加直觀地比較小波加相似比算法和本文算法，以時間為橫坐標(biāo)，PSNR為縱坐標(biāo)，將同一幅圖在不同鄰域下獲得的PSNR及時間數(shù)據(jù)繪制成二維圖像，結(jié)果見圖2、圖3。圖2數(shù)據(jù)是對Lena圖像編碼得到，圖3數(shù)據(jù)是對woman2圖像編碼得到?？梢钥闯觯诤臅r相同時，本文算法的PSNR明顯高于小波加相似比算法；在獲得相同PSNR時，本文算法耗時更少，說明本文算法優(yōu)于小波加相似比算法。用三種算法分別對woman2、Lena、man三幅圖在k=1條件下進(jìn)行實驗，實驗效果圖見圖4。

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

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

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

5 結(jié) 語

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