基于改進Ｍａｌｌａｔ算法的分形圖像壓縮

摘 要:根據傳統分形圖像壓縮算法的實現條件，針對現有二進小波信息量仍然存在冗余，提出了將Mallat算法應用于分形圖像壓縮。MATLAB實驗表明，通過改進Mallat算法的應用，有助于增強圖像的壓縮比以及圖像質量。

關鍵詞:正交小波變換; Mallat算法; 分形圖像壓縮; 壓縮比

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001-3695(2009)09-3569-03

doi:10.3969/j.issn.1001-3695.2009.09.107

Research of fractal image compress based on improving Mallat arithmetic

LI Feng， XUE Jing-ming

(School of Computer Telecommunications， Changsha University of Science Technology， Changsha 410076， China)

Abstract:According to the implement condition of the fractal compression algorithm， becauseits existing binary wavelet redundancy of information still existed， the paper gave a point that fractal image compress based on Mallat arithmetic. MATLAB experiments show that the improved Mallat algorithm can strengthen the image compression ratio and image quality.

Key words:orthogonal wavelet transform; Mallat algorithm; fractal image compress; compression ratio

0 引言

分形編碼是近年發展起來的一種新的圖像編碼方法，由于其簡單快速的解碼過程，特別是潛在的高壓縮比等特點而廣泛地受到重視。基于分形編碼的圖像壓縮算法受到了研究者們的廣泛關注[1，2]。Barnsley[3]首次提出將迭代函數系統應用于圖像壓縮編碼中，獲得了極好的壓縮性能，但在圖像分割過程中需要人機交互，所以無法實用。

針對文獻[3]的局限性，文獻[4]提出了基于分塊劃分的分形圖像壓縮方法，該方法通過將原始圖像劃為固定大小的方塊，然后對每一方塊通過仿射變換在原始圖像的緊縮圖像中尋找最相似的部分，這些操作都可以由計算機自動完成，它為分形圖像壓縮的研究帶來了質的飛躍。沿用這一思想，在分形圖像壓縮的研究中，Salah Ameer等人提出了將DCT與分形聯合，用仿射變換粗略描述原始圖像，而誤差圖像由DCT來完成[5~7]。這一方案有效提高了恢復圖像的細節質量。

然而，已有的研究[5~12]大多僅考慮圖像滿足自相似性強的單一理想情況，并沒有將小波變換思想有效地應用于分形壓縮，這使得將普通小波變換應用于普通圖像壓縮過程中與理論分析有一定的出入，導致算法的適用性并不理想，并且現有基于二進小波變換的圖像壓縮信息量仍然存在一定的冗余量[8]。分析了基于小波變換具有良好的空間—頻率局部化特性，針對正交小波變換中Mallat算法的優越性，提出基于Mallat算法的分形圖像壓縮，并通過MATLAB實驗表明通過Mallat算法的應用，分形圖像壓縮可以進一步地提高壓縮比以及編碼速度。

1 小波變換在分形信號中的應用

小波變換是一種新興的數學分析方法，已經受到了人們廣泛的重視，小波變換是一種全局變換，其在時域和頻域同時有良好的定位能力。由于它對圖像的高頻分量采用逐漸精細的時域和空域步長，且可以使高頻分量聚焦到被處理圖像的任何細節，很快在圖像處理領域得到了廣泛的應用[11]。為了更好地理解小波變換，采用Mexican Hat小波來實現分形信號的分解，并畫出時間尺度圖，如圖1所示;然后再提出正交小波變換中Mallat算法的理論依據。

在圖像處理中，常用的是二進小波，表示為ψ2k，τ(t)=2-k/2ψ((t-τ)/2k)。二進小波介于連續小波和離散小波之間，它具有連續小波變換的時移共變性，這個特點是正交離散小波所不具有的，所以二進小波在圖像處理方面十分有用。二進小波的信息量仍然是有冗余的，從數值計算及數據壓縮等角度來看，希望減少它們的冗余量，直至得到一組正交基，稱之為正交小波基。構造正交基的方法一般是在離散框架的基礎上，取α0=2，τ0=1，則ψj，k(t)=2-j/2ψ(2-jt-k)，j，k∈Z。

2 分形圖像壓縮的基本流程

本章主要介紹分形圖像壓縮的基本原理以及概括文獻[4]提出的分形壓縮編碼實現方案，傳統的圖像分形壓縮步驟如圖2所示。

假定有一幅灰度圖像f，為了達到圖像壓縮的目的，首先對其進行分形編碼，即必須要解決的問題如下:給定f，找到映射W，使得吸引子f=f。到目前為止，此問題并沒有解決。

文獻[3]提出的具體算法思想為:找到圖像f′∈f，使得dsup(f，f′)達到最小，而f′=f，因為f=W(f)，所以只要找到父塊D1，D2，…，Dn和相應的映射變換w1，w2，…，wn，使得f≈W(f)。這一步驟在拼貼原理的幫助下完成。

3 基于Mallat算法的分形圖像壓縮

Mallat在圖像分解與重構的塔式算法啟發下，根據多分辨率理論，提出了小波分析與重構的快速算法，稱為Mallat算法[9]，該算法大大減少了信號壓縮后的冗余量。本章主要針對Mallat算法的低冗余量以及分形編碼潛在的高壓縮比，提出基于Mallat算法的分形圖像壓縮理論，以下給出公式證明該理論的可行性。具體過程如下:

在原有多分辨率分析中，存在一個重要的結論:Pjf(t)=∑nx(j)njn(t)。當j=0時，P0f(t)=∑nx(0)n0n(t);x(1)k=〈P1f(t)，1k(t)〉=〈P0f(t)，1k(t)〉，D1f(t)與1k(t)正交，所以〈D1f(t)，1k(t)〉=0。固然可以得到

x(1)k=∑n〈0n(t)，1k(t)〉x(1)n(1)

其中:

〈0n(t)，1k(t)〉=(1/2)(t/2-k)(t-n)dt=(1/2)(t′/2)[t′-(n-2k)]dt′=h0(n-2k)

將上式代入式(1)得

x(1)k=∑nh0(n-2k)x(0)n(2)

類似還可以證明:

d(1)k=∑nh1(n-2k)x(0)n(3)

稱式(2)中的x(1)k為離散平滑逼近，式(3)中的d(1)k是離散細節信號，也就是小波信號。

對x(1)k進行由V1到V2、W2的類似分解，得到x(2)k和d(2)k，再對x(2)k進行V2到V3、W3的分解，得到x(3)k和d(3)k，…，對x(j)k進行Vj到Vj+1、Wj+1的分解而且所需電路的結構不變，且濾波器系數仍然是h0(-k)和h1(-k)。分解過程中采用二抽樣，即從x(j)k到x(j+1)k、d(j+1)k，樣點數減少一半，但無論分解幾層，總共數據的點數是保持不變的。換句話說，正交離散小波變換是非冗余性的。

由此可以得出，基于Mallat算法的分形圖像壓縮必然可以增大壓縮比。

4 基于小波變換的實驗仿真

基于小波變換的圖像壓縮算法的基本思想是，在選定合適的正交小波基的基礎上，對圖像進行二維小波分解。本章首先利用傳統基于基本二維小波分析對給定圖像M進行圖像壓縮;然后再詳細介紹基于Mallat算法的分形圖像壓縮的實驗流程，利用MATLAB 7.0編程實現算法;最后給出實驗結果對比。

4.1 基于二維小波分析的壓縮方法

基于二維小波分析的圖像壓縮步驟大致如下:

第一次壓縮提取原始圖像中小波分解第一層的低頻信息和高頻系數，此時壓縮效果較好，壓縮比比較小(大約1/4大小);第二次壓縮是提取第一層分解低頻部分的低頻部分(即第二層的低頻部分)，其壓縮比雖然比較大(約為1/12)，但壓縮效果在視覺上有明顯的失真，此時保存圖片為M′，壓縮效果如圖3所示。

4.2 基于Mallat算法的分形壓縮

基于Mallat算法的分形圖像壓縮的基本思想是，利用基于Mallat算法小波變換把圖像分解為不同空間頻帶上的子圖像，而且不同層對應的子圖像結構之間存在著很大的相似性。因此再施加分形壓縮算法就可以利用圖像空間結構信息來進行壓縮，這樣就可以在小波變換后的高層子圖像內進行基本分形壓縮，并根據分形的特點，利用不同層子圖像之間的相似性來求得更高的壓縮比。同時，由于是在小波變換后的高層子圖像內進行壓縮，圖像分割后的分類塊域和相對應的重疊塊域內的圖像塊數目大大減少，這就達到了縮短編碼壓縮時間的目的。

a)利用Mallat算法對壓縮函數進行修改，即對圖像的小波變換，進而實現對圖像的高效壓縮，并對所有高頻系數進行同樣的閾值量化處理，壓縮后的圖像保存為M″。

b)對圖像M″的每個像素(i，j)用三個基色值R(i，j)，G(i，j)，B(i，j)表示，提取R、G、B三分量分別進行小波變換編碼。由于R、G、B三分量之間存在一定的相關性，本文先將彩色圖像轉換成YUV方式表示。轉換公式為[14]

Y=0.2990R+0.5870G+0.114B

U=-0.1480R-0.2890G+0.4370B

V=0.6150R-0.5150G-0.1000B

其中:Y分量的物理含義就是亮度，U和V分量代表了色差信號。

這樣一來，圖像就消除了各分量間的相關性，并且各分量又有了主次之分，其中Y分量是主要的，而U和V分量較次要。如果將Y、U、V分量按4∶1∶1方式抽樣，再對Y、U、V三分量數據分別進行小波變換編碼。

c)對變換后的M″進行圖像分割，分割成20×20塊區域作為父塊D，再將M″分割成40×40塊區域作為子塊R。

d)對于每一個R上的圖像，從20×20個父塊中尋找適合的父塊D和相應的v(x，y)、s、o，使得父塊上的圖像經過變換后與R上的圖像最接近。

e)對于任一R上的圖像，都計算20×20×8幅平均旋轉后8×8灰度圖與其對應的s、o以及距離d，找出20×20×8幅圖中距離最小的一幅，并記錄相應的s、o、Di和Di所經過的旋轉變化，這樣就完成了對這個R上圖像的編碼，也就得到了wi。

f)對于圖像的解壓縮，圖像f為空白的I2，先求wi的所有集合，后求出W(f)…，直至連續兩幅圖像十分接近，一般迭代7或者8次就可以得到不動點。

g)按照下式將YUV圖轉換得到(R，G，B)空間的重建圖像。

R=1.000Y-0.000U+1.1398V

G=1.000Y-0.3938U-0.5809V

B=1.000Y+2.0279U+0.0018V

最終圖像壓縮效果圖如圖4所示。

4.3 實驗結果與分析

兩次實驗所用的樣本均為240×320，614 400 Byte的圖像M。實驗結果如表1所示。

從實驗效果圖可以看出，基于Mallat算法的分形圖像壓縮得到的效果圖并沒有明顯的塊狀效應，這樣得到的圖像質量比基于二維小波分析[12]得到的圖像要高得多。從實驗結果比對可以看出，本文算法比其余兩類算法在編碼時間、壓縮比、圖像質量上都有一定的改進。

5 結束語

基于Mallat算法的分形圖像壓縮主要利用了Mallat算法的低冗余量以及分形壓縮的自相似性。這樣一來，減少了圖像信息冗余量的同時，還充分利用了圖像自相似性的特點，最終實現了高壓縮比，并且也保證了圖像質量。在高壓縮比時，圖像質量甚至超過了DCT，但是分形壓縮編碼的潛在壓縮比并沒有全部挖掘出來。分形圖像壓縮的原理是利用大自然圖像所固有的自相似性，但是現實存在的大量圖片在相似性的提取方面仍然有很大的困難，很多方面還不及其他算法。因此，靈活地分割圖像信息、充分利用圖像自相似性是尤為重要的。

參考文獻:

[1]王秀妮，姜威，王立村.一種分形圖像編碼的新方法[J].中國工程科學，2006， 8(1):54-57.

[2]譚郁松，周興銘.一種新型圖像分形壓縮的改進算法[J].電子學報，2003， 31(11):1739-1742.

[3]BARNSLEY M F. A better way to compress images[J]. BYTE， 1988， 13(1):215-223.

[4]JACAUIN A E. A novel fractal block-coding technique for digital images [C]// Proc of ICASSP. [S.l.]:IEEE Press，1990:2225-2228.

[5]何傳江，蔣海軍，黃席樾.基于平均偏差排序和快速分形圖像編碼[J].中國圖象圖形學報，2004， 9(9):1130-1134.

[6]AMEER S，BASIR O. Image compression using plane fitting with inter-block prediction[J]. Image and Vision Computing，2008， 27(4):385-390.

[7]袁源，戴冠中，羅紅. 基于分形思想的差值圖像壓縮技術[J].計算機應用研究，2007， 24(4):190-191.

[8]王秀妮，姜威，王利村.基于統計特性的分形圖像壓縮[J].計算機工程與應用，2005， 41(26):75-77.

[9]王偉，崔榮一. 一種混合快速分形圖像編碼算法[J].計算機應用研究，2008， 25(11):3498-3500.

[10]TSENG C C， HSIEH J G， JENG J H. Fractal image compression using visual-based particle swarm optimization[J]. Image and Vision Computing，2008， 26(8):1154-1162.

[11]董文輝，劉明業. 應用小波分析進行圖像壓縮的研究及實現[J].計算機應用研究，2003， 20(6):57-60.

[12]潘迅宇，潘樹陸，王相海，等.基于多分辨率級小波變換的圖像壓縮方法[J].中國圖象圖形學報，2003， 8A(9):1089-1092.