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

孫媛媛，孔瑞卿

(大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024)

1 概述

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

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

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

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

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

2 基本方法

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

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

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

解碼過程是一個(gè)相對(duì)簡(jiǎn)單的迭代過程，每次迭代過程需要的碼本是由上一次迭代的結(jié)果提供的，初始圖像可以任意指定，迭代過程如下：

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

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

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

同樣在解碼的過處程中無需迭代，只需要找到相應(yīng)的定義域塊，做一次運(yùn)算即可完成解碼過程，不會(huì)產(chǎn)生迭代誤差，同時(shí)也加快了解碼的速度。編解碼系統(tǒng)如圖1所示。

圖1 編解碼系統(tǒng)

3.1 字典生成算法

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

(1)生成參數(shù)：利用標(biāo)準(zhǔn)的 M集生成J集的生成參數(shù)集合，記為 ΦN，其中，N是選取的可生成 J集參數(shù)的個(gè)數(shù)。

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

其中，Max_Iterative表示最大的迭代次數(shù)。

(3)量化分形圖像：得到一幅M×M的J集圖像后，對(duì)圖像中每一個(gè) V(k,l)值乘以一個(gè)整數(shù)值 H，可以得到一個(gè)J集圖像，選取不同的H值，就可以得到多種不同的圖像。因?yàn)閷?shí)驗(yàn)只要求灰度圖像，所以在計(jì)算中要對(duì)256求模。

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

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

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

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

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

3.2 編碼算法

編碼算法描述如下：

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

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

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

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

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

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

(4)對(duì)每個(gè) Ri中的塊進(jìn)行編碼，重復(fù)進(jìn)行第(3)步，直到R中所有塊均完成。

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

3.3 解碼算法

解碼時(shí)需要讀入分形編碼參數(shù)文件，對(duì)記錄的參數(shù)采用解碼算法。因?yàn)樽值涔潭?，所以在解碼過程只要迭代一次，即可完成解碼的過程，解碼算法描述如下：

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

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

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

(4)輸出圖像文件。

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

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

本文實(shí)驗(yàn)選取的J集的映射公式如下：

本文在實(shí)驗(yàn)中選取的 3幅圖，分別是 Lena、Peppers和 Elain，并使用傳統(tǒng)的分形編碼結(jié)果進(jìn)行比較。

實(shí)驗(yàn)最后生成的字典具有定義域塊數(shù)為3 086塊，分別利用本文算法和傳統(tǒng)算法對(duì) 512×512像素和256×256像素大小的圖像進(jìn)行實(shí)驗(yàn)得到結(jié)果如表1和表2所示。解碼后的圖像如圖2所示。

表1 對(duì)512×512像素圖像編碼后的PSNR及時(shí)間

表2 對(duì)256×256像素圖像編碼后的PSNR及時(shí)間

圖2 解碼效果

由表1和表2的比較結(jié)果可以看出，在不降低圖像質(zhì)量的前提下，利用字典進(jìn)行圖像編碼可以大幅降低運(yùn)行時(shí)間，速度優(yōu)勢(shì)在圖像尺寸較大的情況下更為明顯。伴隨圖像尺寸的增大，編碼時(shí)間增加的幅度也很小，而傳統(tǒng)分形編碼在圖像大小增加的同時(shí)，也會(huì)大幅度增加編碼時(shí)間。

5 結(jié)束語

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

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

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

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

[4]何傳江, 劉維勝, 申小娜.基于行列式的快速分形圖像編碼算法[J].中國圖象圖形學(xué)報(bào), 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].計(jì)算機(jī)系統(tǒng)應(yīng)用, 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].中國科學(xué)院研究生院學(xué)報(bào), 2002, 19(2): 177-181.

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

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