一種基于字典的快速分形圖像編碼方法

孫媛媛，孔瑞卿

(大連理工大學計算機科學與技術學院，遼寧 大連 116024)

1 概述

圖像壓縮技術是解決圖像傳輸和存儲的主要途徑之一，利用圖像壓縮可減少圖像在傳輸和存儲中的網絡負擔，使圖像可以在網絡上快速傳輸和實時處理。目前有多種圖像壓縮方法，按照在編碼過程中是否存在信息損耗可以將它們分為2類：無失真編碼和限失真編碼。無失真編碼在實際應用中一般不能達到很高的壓縮比，因此，在實際應用中一般采用限失真編碼。一般的限失真編碼主要包括DPCM、DCT、VQ等，這類方法一般是以獨立的像素和圖像塊作為編碼對象，沒有考慮到圖像本身的結構特點和頻率分布特性[1]。

分形圖像編碼是根據現實圖像具有自相似性來實現圖像的一種有損編碼方法。利用分形實現圖像壓縮的思想由 Barnsley于 1988年提出，并由其學生Jacquin提出可用于實際的編碼方法[2]。分形圖像編碼有許多優點，如具有與分辨率無關的解碼特性，編碼過程簡單，解碼過程無需搜索，并突破以往熵壓縮編碼的界限。但同時分形圖像編碼也有自己的缺點，如編碼時間過長，容易出現方塊效應，壓縮比通常在10左右，并不能達到分形理論上的壓縮比，且壓縮比率僅與值域塊的大小有關。

由于分形編碼本身是一種有損編碼，因此在保持圖像質量的前提下，盡量加快編碼速度是分形編碼研究的一個重要內容。近年來，許多專家和學者對分形圖像壓縮算法進行了研究和改進，并取得了一定的效果，如利用特征向量快速分形編碼[3]、基于行列式的匹配查找算法[4]、與小波變換結合的算法[5]、基于子塊特征分形編碼[6]、基于四叉樹查找算法編碼[7]等，但這些算法均傾向于在原圖中的定義域塊內進行查找。

在采用字典進行分形編碼的算法研究方面，文獻[8]將量化的Julia曲線用于圖像壓縮編碼。文獻[9]利用復平面M集結合Logistic映射建立了常用壓縮編碼字典，圖像的定義域塊即取自字典。文獻[10]提出一種基于 Julia-CK 集和 Logistic映射的非線性分形壓縮算法，該算法通過對Julia-CK集圖像塊的圓盤變換，能得到更為豐富的壓縮字典。上述編碼算法均以M-J集為壓縮字典，字典固定且數量較少，能夠加速編碼時間，但解碼效果不如仿射變換(傳統編碼采用的方法)的效果好。影響解碼效果的因素主要在于字典不夠豐富，以及圖像中的值域塊直接由字典圖像中的定義域塊替代。

針對上述問題，本文提出一種新的編碼方法，使用一種新的字典生成算法，生成一個合適的字典文件，以改進圖像的編碼效果和編碼速度。

2 基本方法

本文主要是基于離散局部迭代函數系統(DLFS)進行圖像編碼，其基本思想如下：圖像被分成大小2類子塊，這些子塊作為一個矩陣存儲圖像中的元素，并記大塊為Di和小塊為Ri，小塊Ri互不重疊且覆蓋整幅圖像，一般稱 R塊為定義域塊。大塊 Di尺寸一般取Ri塊的 2倍，且可以相互重疊，一般稱 Di塊為值域塊。稱 Di塊的集合為碼本，對每一個 Di塊采取四鄰域元素平均法得到的與 R塊相同大小的像素塊。

設有一個N×N的灰度圖像，可以把一幅圖像I看成一個灰度矩陣(Ii,j)N×N，其中 I(i,j)表示圖像在(i, j)處的灰度值。假定有2個大小相同的圖像XN×N、YN×N，定義 d是作為失真判據的完備度量，在 DLFS中稱d為匹配范數，d的計算公式如下：

其中，s和o分別表示亮度調整和亮度偏移，因此，分形編碼的過程主要是尋找最小匹配范數的過程。利用最小二乘法，可以計算出，當 s和 o滿足式(2)和式(3)時，匹配范數d可以取到最小值。

解碼過程是一個相對簡單的迭代過程，每次迭代過程需要的碼本是由上一次迭代的結果提供的，初始圖像可以任意指定，迭代過程如下：

D(m,n)j代表在 j次迭代后產生的結果在點(m, n)處的像素值。一般進行 7次～8次迭代即可得到原圖像。

3 基于字典的圖像編碼方法

傳統的分形編碼過程中主要有 2個過程比較耗時：(1)定義域塊的生成，在每一次對圖像進行編碼時都要在原圖的基礎上重新生成定義域塊，定義域的數量會隨著圖像的大小而加速增加。(2)查找編碼塊，對于用原圖生成的定義域塊，利用全搜索方法來查找合適的定義域塊，這樣搜索會大大增加其計算時間。而在解碼的過程中，由于要采用迭代的方法，而計算機在保存數據時有精度丟失問題，在每次迭代的時候都會產生一定量精度損失問題，在多次迭代的過程中這些誤差會累積，因此解碼過程中就不可避免的產生迭代誤差。考慮到分形解碼過程中，初始圖像與最終解碼圖像無關，可以在分形圖像編碼的過程中采用固定定義域池的方法，稱這個固定定義域池為字典，在編碼過程中，對于原圖中每一個值域塊，只需要在字典文件中查找具有最小匹配范數的定義域塊，而不需要對每一幅圖像生成一次定義域塊集合。

同樣在解碼的過處程中無需迭代，只需要找到相應的定義域塊，做一次運算即可完成解碼過程，不會產生迭代誤差，同時也加快了解碼的速度。編解碼系統如圖1所示。

圖1 編解碼系統

3.1 字典生成算法

分形圖像利用較少的參數集合，就可以生成紋理比較復雜的圖像，因此，本文選取分形圖像作為字典的生成圖像。M集和 Julia集(簡稱 J集)是傳統的分形圖像。對于 J集來說，其生成參數都可以體現在M集中，利用M集可以方便的構造出多種生成參數下的J集，并且其可在不同的尺度上重復出現自身的結構。因此本文主要結合 Julia集生成字典圖像，生成字典的過程中選取 M集上不同的點生成豐富多變的J集圖像。算法步驟如下：

(1)生成參數：利用標準的 M集生成J集的生成參數集合，記為 ΦN，其中，N是選取的可生成 J集參數的個數。

(2)生成J集：利用逃逸時間算法，對每個參數生成一個M×M大小的J集圖像，并在生成的過程中記錄每個點的迭代次數，記為V(k,l)，如下式所示：

其中，Max_Iterative表示最大的迭代次數。

(3)量化分形圖像：得到一幅M×M的J集圖像后，對圖像中每一個 V(k,l)值乘以一個整數值 H，可以得到一個J集圖像，選取不同的H值，就可以得到多種不同的圖像。因為實驗只要求灰度圖像，所以在計算中要對256求模。

(4)生成定義域塊：對每一個圖像采用四元素平均法，得到一組灰度圖像，每一個灰度圖像塊稱為定義域塊，把所有定義域塊存放到一個字典文件中。

本文在選取 J集參數時，只選擇位于 M集邊界的點，這樣可以使得生成的圖像中具有較多的紋理塊。字典生成后，為保證字典的充分有效性，對字典進行以下優化：

(1)字典內定義域塊的數量，字典內的定義域塊數量必須達到一定的數量，這樣才可以充分地保證字典對于盡可能多的圖像值域塊都可以找到合適定義域塊。同時，圖像的編碼速度同和字典塊的數量有正比例關系，因此，也要保證字典內定義域塊的數量不可以太多，保證編碼速度。

(2)冗余性改進，由于 M集圖像自身相似性，因此在生成字典中，也存大一定數量的相似塊，可以把它們認為是重復塊，這時可以通過一定的方法來去除掉這些重復塊，使得字典冗余度盡量降低。

(3)字典要盡量覆蓋很多種類的圖像。在速度可以得到保證的情況下，使得字典內的定義域塊盡可能豐富，這樣才可以保證對于任意圖像都可以得到較好的編碼文件。

3.2 編碼算法

編碼算法描述如下：

(1)加載字典：將在3.1節生成的字典中的每一個定義域塊Ti加載到內存中，構成碼本塊池TN。

(2)分割圖像：將待編碼的圖像劃分成互不重疊的值域塊Ri，構成值域塊池R。

(3)獲取分形碼：對于 R池塊中的碼塊，在碼本池塊中查找其最好的匹配塊Tm(i)，使這兩塊之間的匹配范數d(Rj,Tm(ij))最小，可以按以下步驟查找：

1)對于每一個Ti∈TN，計算Rj與Ti的對比因子 s和亮度o。

2)計算它們的匹配范數，如果匹配范數小于當前最小的匹配范數，則記錄當前的匹配范數，與相應的編碼參數，包括定義域塊在字典文件中的位置，相應的對比因子s和亮度o。

3)輸出具有最小匹配范數的分形碼參數。

(4)對每個 Ri中的塊進行編碼，重復進行第(3)步，直到R中所有塊均完成。

(5)輸出分形編碼參數，就可以得到分形編碼文件。

3.3 解碼算法

解碼時需要讀入分形編碼參數文件，對記錄的參數采用解碼算法。因為字典固定，所以在解碼過程只要迭代一次，即可完成解碼的過程，解碼算法描述如下：

(1)加載字典：圖像文件中編碼字典加載到內存中去，同樣按8種仿射變換，對內存中的定義域塊進行擴展。

(2)加載編碼文件：讀取編碼文件中的編碼參數，包括在字典文件中的偏移量，對比引子和高度。

(3)恢復原圖：對于讀入每一組參數，利用式(5)解碼，把解碼后的8×8值域塊放到對應的位置。

(4)輸出圖像文件。

4 實驗結果與分析

為驗證上述算法的有效性，本文隨機選擇3幅大小分別為512×512像素和256×256像素2組圖像進行實驗，由于分形圖像壓縮率和值域塊大小存在線性關系，對于大小相同值域塊，其壓縮率相差不大，因此本文把峰值信噪比和運行時間作為要的比較參數。峰值信噪比(Peak Signal to Noise Ratio, PSNR)定義如下：

本文實驗選取的J集的映射公式如下：

本文在實驗中選取的 3幅圖，分別是 Lena、Peppers和 Elain，并使用傳統的分形編碼結果進行比較。

實驗最后生成的字典具有定義域塊數為3 086塊，分別利用本文算法和傳統算法對 512×512像素和256×256像素大小的圖像進行實驗得到結果如表1和表2所示。解碼后的圖像如圖2所示。

表1 對512×512像素圖像編碼后的PSNR及時間

表2 對256×256像素圖像編碼后的PSNR及時間

圖2 解碼效果

由表1和表2的比較結果可以看出，在不降低圖像質量的前提下，利用字典進行圖像編碼可以大幅降低運行時間，速度優勢在圖像尺寸較大的情況下更為明顯。伴隨圖像尺寸的增大，編碼時間增加的幅度也很小，而傳統分形編碼在圖像大小增加的同時，也會大幅度增加編碼時間。

5 結束語

本文提出了一種基于字典進行圖像壓縮編碼的方法，該方法的優勢在于利用固定的字典作為定義域塊，改善了匹配進程，使得對不同圖像可以使用同一個固定字典集。實驗結果表明，利用字典作為圖像的碼本，在保證圖像質量的情況下，可以大幅提高編碼速度，減少編碼時間，尤其對于大圖片進行分形編碼，更能顯示出算法在時間上的優越性，因此，該算法的實用性較高。下一步工作是改進字典內的查找算法，進一步提高編碼速度。

[1]李高平.分形法-圖像壓縮編碼[M].成都: 西南交通大學出版社, 2010.

[2]Jacquin A E.Fractal Image Coding: A Review[J].Proceedings of the IEEE, 1993, 81(10): 1454-1461.

[3]劉 明, 葉正麟, 陳作平.基于二維特征向量的快速分形編碼方法[J].計算機工程與應用, 2007, 43(8): 82-84.

[4]何傳江, 劉維勝, 申小娜.基于行列式的快速分形圖像編碼算法[J].中國圖象圖形學報, 2008, 13(3): 435-439.

[5]Qu Xilong, Dai Mian, Li Zhenhui.Research and Implementation of Fast Image Fractal Coding Algorithm[J].Advanced Materials Research, 2010, (34-35): 1360-1364.

[6]吳曉燕, 劉希玉, 徐 慶.基于子塊特征的快速分形圖像壓縮算法[J].計算機系統應用, 2010, 19(1): 176-179.

[7]Moreno J, Otazu X.Image Coder Based on Hilbert Scanning of Embedded QuadTrees[C]//Proceedings of Data Compression Conference.[S.l.]: IEEE Press, 2011.

[8]朱志良, 趙德平, 朱偉勇.“Julia曲線”與分形圖像壓縮編碼[J].中國科學院研究生院學報, 2002, 19(2): 177-181.

[9]趙德平, 彭 鵬, 張東偉.基于Mandelbrot集和Logistic映射的分形圖像壓縮編碼[J].計算機工程與設計, 2008,29(11): 2851- 2856.

[10]鄭 瑩, 李光耀, 孫燮華.一種新的非線性分形壓縮方法[J].計算機工程, 2008, 34(11): 21-22, 25.