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

趙 蓉 王 輝 張愛華

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

0 引 言

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

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

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

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

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

(1)

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

連續(xù)小波變換定義：對(duì)于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ù)小波的逆變換定義：對(duì)于f(t)∈L2(R)，有:

(3)

1.2 小波基的性質(zhì)

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

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

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

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

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

1.3 二級(jí)小波分解

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

圖1 二級(jí)小波分解示意圖

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é)合的圖像壓縮方法

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

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

3.1 算法分析

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

(11)

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

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

3.2 算法實(shí)現(xiàn)

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

1) 通過二級(jí)小波分解，將圖像分解為7個(gè)子帶，保留低頻子帶的小波系數(shù)，對(duì)其余6個(gè)子帶小波系數(shù)的符號(hào)單獨(dú)編碼。

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

圖2 三種算法的性能對(duì)比圖(實(shí)驗(yàn)圖像Lena)

圖3 三種算法的性能對(duì)比圖(實(shí)驗(yàn)圖像woman2)

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

5 結(jié) 語

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