1、一種分形彩色圖像壓縮編碼方法焦華龍陳剛1,21(浙江大學(xué)計(jì)算機(jī)圖象圖形研究所，浙江杭州 310027)2(寧波大學(xué) 數(shù)字技術(shù)與應(yīng)用軟件研究所，浙江 寧波 315211)A Color Image Fractal Compressi on Coding MethodJIAO Hua-Long 1+, CHEN Gang 1,2Institute of Computer Graphics and Imaging Processing, Zhejiang University, Hangzhou 310027, China) Institute of Digital Technology and A

2、pplication Software, Ningbo University, Ningbo 315211, China) + Corresponding author: Phn: 86-21-64325854 ext 814, Fax: 86-21-64325842, E-mail: Received 2002-04-09; Accepted 2002-07-02Jiao HL, Chen G. A color image fractal compression coding method.Journal of Software , 2003,14:864868.Abstract : In

3、this paper, a color image fractal compression coding method is proposed by analyzing the correlation of r, g, b components of a color image and the remnant of layer information in quadtree scheme. It merges three-color components into one. Accordingly this method will reduce the matching blocks, whi

4、ch need to be saved and encoded by SFC (separated fractal coding) algorithm, into one and at one time the source data and layer information in quadtree scheme can sustain non-losses and high-proportion compression. Furthermore, by selecting different combinations, a series of coding methods that bea

5、r very close compression ratio and qual ity of decoded image are obtained. Moreover the coding speed of the luminosity method among them is faster than the other ones. Experimental results indicate that this approach excels SFC or standard JPEG and can be a good color image fractal compression algor

6、ithm.Key words :color image fractal coding; quadtree structure摘 要：在分析彩色圖像色彩三分量r,g,b的相關(guān)性和分形四叉樹編碼層次信息冗余性的根底上，提岀了一種分形彩色圖像壓縮編碼方法.它將圖像的3個(gè)獨(dú)立的顏色分量按某種方式組合成1個(gè)來搜索匹配塊，從而將需要存儲(chǔ)和搜索的3個(gè)顏色分量匹配塊(SFC方法)減少為1個(gè)，并且對(duì)四叉樹層次信息進(jìn)行壓縮.此外，采用不同的組合，得到了幾個(gè)圖像壓縮比和解碼質(zhì)量相近的編碼方法，其中使用亮度分量的方法比使用其他方法速度更快.實(shí)驗(yàn)結(jié)果說明，它優(yōu)于SFC方法及標(biāo)準(zhǔn)JPEG方法，不失為一種好的分形彩色圖像壓

7、縮方法Supported by the National Natural Science Foundation of China under Grant No.60202102 國家自然科學(xué)基金第一作者簡介:焦華龍1976 -，男，安徽無為人，碩士，主要研究領(lǐng)域?yàn)閳D像編碼，圖像檢索，計(jì)算機(jī)圖形學(xué).關(guān)鍵詞：分形彩色圖像編碼；四叉樹結(jié)構(gòu)中圖法分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A自20世紀(jì)80年代Barnsley等人提出圖像的分形壓縮1以來，分形圖像編碼作為一種新的具有高壓縮比潛在能力的圖像編碼方法，受到了廣泛的關(guān)注.但是,其研究主要還是集中在灰度圖像方面，對(duì)真彩色圖像壓縮算法的研究那么相對(duì)較少經(jīng)過壓縮

8、后,4 4塊占用標(biāo)志信息空間為0個(gè)bit,8占用標(biāo)志信息空間為 n3 n2/4山/16個(gè)bit,32 32占 用非標(biāo)志信息空間為 n4 n3/ 4 n2 /16 n1 / 64個(gè)bit,總 計(jì)為(21山 84n2 80n3 64帀)/64 個(gè) bit;.與黑白圖像相比，彩色圖像的色彩局部是其特有的，并且與人眼的視覺特性關(guān)系非常緊密,因而對(duì)彩色圖像的處理也應(yīng)有獨(dú)特的方法.顯然，編碼真彩色圖像的一個(gè)最直接的方法就是將真彩色圖像看成是3個(gè)獨(dú)立的灰度圖像進(jìn)行單獨(dú)編碼的SFC(separated fractal coding)方法將沒有壓縮之前所需空間除以壓縮后所占空.這種方法由于沒有考慮彩色圖像3個(gè)顏

9、色分量之間的相關(guān)性，因而壓縮比擬低而且很費(fèi)時(shí).本文首先在分析灰度圖像分形四叉樹壓縮編碼2方法中樹結(jié)構(gòu)層次信息的冗余性的根底上，提岀了改良這種存儲(chǔ)方式的壓縮算法，并且給岀了樹結(jié)構(gòu)層次信息的壓縮比計(jì)算公式；之后，我們對(duì)由一幅真彩色圖像分別抽岀的三色分量所組成的灰度圖進(jìn)行統(tǒng)計(jì)比擬，發(fā)現(xiàn)它們有很大的相似性，在此根底上，我們提岀了將三色分量組合成一個(gè)特征量來搜索匹配塊的分形彩色圖像壓縮 方法.由于此方法需要存儲(chǔ)和搜索的匹配塊信息相當(dāng)于與它同等大的灰度圖像，因而編碼所需要的計(jì)算量和所能到達(dá)的壓縮比要比 SFC方法有較為明顯的提高，在恢復(fù)圖像質(zhì)量相近，且沒有做Huffman編碼或算術(shù)編碼等 無損壓縮的情況下

10、，壓縮比也超過了標(biāo)準(zhǔn)JPEG方法.1四叉樹層次信息的冗余性及其壓縮存儲(chǔ)在分形壓縮的四叉樹方法當(dāng)中，每一個(gè) R塊需要記錄以下 6個(gè)參數(shù):(1)找到的最正確匹配子塊D的位置(dx,dy)(子塊左上角坐標(biāo));(2)對(duì)稱和旋轉(zhuǎn)變換的序號(hào) n;(3)灰度仿射變換系數(shù)和;(4)子塊R的層次信息1(一般是32 32到4 4四層，用2bit存儲(chǔ)).以這6個(gè)參數(shù)作為R的碼本，就可以從任意圖像經(jīng)過迭代恢復(fù)到原圖像.四叉樹剖分是最常見的一種方案，基于初始的正方形剖分 ，一般要求 R塊大小為 2r 2，剖分后得到 4個(gè)2r 1 2r 1的子塊由于這種方案比擬簡單，在計(jì)算量要求較高的分形編碼中比擬通用事實(shí)上，在R塊的6

11、個(gè)參數(shù)當(dāng)中的層次信息I有很多的冗余以剖分從32 32到4 4四層為例，當(dāng)有一個(gè)R塊分到最小(4 4)時(shí)，緊跟它的3個(gè)塊也一定是分到最小的塊 ，這樣，只需存儲(chǔ)第1個(gè)R塊層次信息即可，其他3塊的層次信息屬于冗余局部 ；在 作了對(duì)最小塊的層次信息的處理之后，同樣地，次小塊(8 8)的層次信息依然存在這種冗余，即當(dāng)有一個(gè) R塊分到次小時(shí)，緊跟它的3個(gè)存儲(chǔ)的層次信息次小層或最小層信息 (這里，一個(gè)最小層信息已經(jīng)代表4個(gè)最小塊，也相當(dāng)于一個(gè)次小塊),這樣我們就可以用一個(gè)次小層信息加4個(gè)標(biāo)志位(最小層用0,次小層用1)來表示；如此下去,直到最大塊(32 32)為止.在解碼階段，用最后得到的塊信息加上存儲(chǔ)的所

12、有標(biāo)志位，就可以恢復(fù)整個(gè)四叉樹.在經(jīng)過了上述無損的消除層次信息冗余的處理之后，對(duì)于原先用 2bit表示的R塊,最小塊我們只用了約0.25bit,其他非最小塊也只用了約1bit,起到了一定的壓縮作用(從實(shí)驗(yàn)來看，對(duì)于256 256塊，一般會(huì)壓縮大約 38塊占用標(biāo)志信息空間為n2 n1 /4個(gè)bit,16 16Fig.1 An example of quadtree partition structure圖1四叉樹剖分結(jié)構(gòu)例如倍).這里給出可以從壓縮過程推導(dǎo)出來的層次信息壓縮倍數(shù)的計(jì)算公式如下(剖分從32 32到4 4):c128山 n2 n3 帀Cr,21n184n280n364加其中Cr表示層

13、次信息壓縮倍數(shù) 較大，因而有較好的壓縮效果.推導(dǎo)過程如下：;ni表示圖像分塊中大小為2i+1 2i+1的R塊個(gè)數(shù)(i=1,2,3,4).對(duì)于一般圖像來說，山(1)沒有壓縮之前需要的空間為2(nn2 n3n4)個(gè)bit;間,即可得到上述壓縮倍數(shù)計(jì)算公式.例如，對(duì)于如圖1所示的四叉樹剖分設(shè)整個(gè)塊大小是32 32的，塊4 4到32 32在層次信息中分別用11,10,01,00 表示,沒有經(jīng)過編碼之前的表示為01 10 10 11 11 11 11 10 11 11 11 11 10 10 11 11 11 11 10 11 11 1111 10 10,用了 50個(gè)bit.經(jīng)過一次處理之后變?yōu)?1 1

14、0 10 11 10 11 10 10 11 10 11 10 10,經(jīng)過兩次處理后變?yōu)?110 10 10及標(biāo)志信息0 0 1 0 1 0 0 1 0 1 0 0,再經(jīng)過一次編碼后成為最終的01及標(biāo)志信息0 1 1 1和0 0 1 0 1 0 01 0 1 0 0表示，由于最終的信息非標(biāo)志信息只是32 32和16 16兩種遨只要1bit表示即可01可用1來表示, 也就是說，最后我們用了共17bit,壓縮倍數(shù)為50/17 3.解碼時(shí)只需將編碼過程反過來，就能恢復(fù)所有的層次信息.2編碼方法2.1三色相關(guān)性在將圖像中每個(gè)像素的三色分量r,g,b各自單獨(dú)抽取出來作為灰度圖像在該點(diǎn)的灰度值的觀察中，我

15、們發(fā)現(xiàn)它們?cè)诮Y(jié)構(gòu)上具有非常相似的地方，有差異的只是在不同的地方，其亮度有所不同如圖2所示.也就是說，當(dāng)我們用分形方法進(jìn)行圖像編碼時(shí)，如果有一個(gè)分量的 R塊和D塊相似，那么另外兩個(gè)分量的相同位置的R塊和D塊也非常相似，只是在亮度上有差異Fig.2 From left to right are gray images of picture Fruit composed by three-color components r, g, b respectively 圖2從左到右分別是彩色水果圖Fruit的r,g,b顏色分量組成的灰度圖像通過統(tǒng)計(jì)分析亮度Y及r,g,b顏色之間的相關(guān)性，我們得到了表1的結(jié)

16、果.該表中的數(shù)據(jù)顯示r,g,b之間確實(shí)存在著很大的相關(guān)性，證實(shí)了原先觀察得岀的結(jié)論，于是我們考慮利用這種相關(guān)性進(jìn)行彩色圖像編碼.由于分形中有對(duì)像素的灰度進(jìn)行匹配修正的仿射變換系數(shù)和，可以利用這個(gè)修正來彌補(bǔ)亮度的差異.在實(shí)驗(yàn)中發(fā)現(xiàn)下面的方法有不錯(cuò)的結(jié)果，即用r,g,b的線性組合得到的亮度YY0.301r 0.586g 0.113b來搜索匹配D塊,把該D塊也分別作為r,g,b的匹配塊，只是修改3個(gè)顏色分量中與亮度相關(guān)的信息和，這樣就將SFC方法中的3色分量單獨(dú)搜索、單獨(dú)存儲(chǔ)的過程簡化為用一個(gè)3色分量的組合特征量來搜索和存儲(chǔ)，這既縮減了匹配時(shí)間變?yōu)樵瓉淼?/3,又提高了壓縮比是原來的2倍多.從表2來

17、看，當(dāng)Y顏色分量的匹配誤差小于給定的閾 值時(shí),r,g,b顏色分量的匹配誤差是可以接受的，實(shí)驗(yàn)得到的解碼圖像質(zhì)量與SFC并沒有太大的差異.這也說明了該方法的可行性.相關(guān)性系數(shù)的計(jì)算公式為Exy ExEyXy 麗后，其中x,y為兩向量,Ex,Dx分別為表示x的所有分量的平均值和方差.Table 1 Percentages of correlation coefficient over 0.8 proportioned by every two-color components,which are obtained from 44 image segmentations of colorful pi

18、cture Fruit表1對(duì)彩色Fruit圖像分割為4 4小塊得到的各顏色分量兩兩之間相關(guān)性系數(shù)大于0.8所占百分?jǐn)?shù)YrgbY10094.597.489.1r94.510090.281.097.490.210087.189.181.087.1100Table 2 Percentages of the corresponding matching errors against r, g, b which are obtained from searching the matching blocks (threshold is 5.0) by Y in picture Fruit表2 Fruit圖

19、像用Y來搜索匹配塊(閾值取為5.0)所得r,g,b對(duì)應(yīng)匹配誤差所占百分?jǐn)?shù)Matching errorrgb7.590.275.095.310.094.079.496.32.2具體的編解碼方法步驟從圖像三色相關(guān)性出發(fā)，我們形成了彩色圖像的如下的編、解碼方法方法1.(1) 對(duì)要編碼的彩色圖像I每一像素點(diǎn)的r,g,b進(jìn)行組合(實(shí)驗(yàn)中取亮度分量Y=0.301r+0.586g+0.113b),得到一幅灰度圖I .(2) 對(duì)灰度圖I進(jìn)行傳統(tǒng)的分形四叉樹搜索，使I中的每個(gè)R塊找到相匹配的 D塊.(3) 將編碼彩色圖像I的r (紅色)分量所組成的灰度圖Ir中R塊和D塊匹配的位置對(duì)稱旋轉(zhuǎn)變換，樹結(jié)構(gòu)用I中得到的

20、來替代，只是將反映亮度的局部(即灰度仿射變換系數(shù)和)用從Ir中計(jì)算得到的最正確匹配值重新計(jì)算進(jìn)行修正;g,b也作與r相同的處理.(r r)(di d )-2, r d ,(di d )i其中R=( ri)是Ir中子塊R像素灰度值組成的 n維向量，D =( di )是I r中D塊經(jīng)四鄰域平均的與R等大的子塊，廠和d分別是R和D的平均值.(4) 對(duì)彩色圖像I的每個(gè)R塊,存儲(chǔ)從I得到的匹配D塊位置，對(duì)稱旋轉(zhuǎn)變換及r,g,b分量的6個(gè)亮度修正 值,R塊的四叉樹層次信息用我們前面所提出的方法存儲(chǔ)解碼過程：先恢復(fù)R塊的樹結(jié)構(gòu)，再分別對(duì)r,g,b分量用IFS(迭代函數(shù)系)迭代得到3幅灰度圖Ir,Ig,Ib，

21、最后將 它們合成為一幅彩色圖.此外，我們還對(duì)彩色圖像求取R相匹配的D塊嘗試采用了其他方法.方法2.將每一點(diǎn)的顏色值看作一個(gè)3維向量 淀義兩點(diǎn)P (rp, gp, bp),Q( rq, gq, bq )的距離為d(P,Q) . r(rp rq)2g(gp gq)2b(bp bq)2,其中r, g , b為每個(gè)分量的權(quán)重，r>0, g >0, b>0且r+ g + b =1(在本文的實(shí)驗(yàn)中，取=0.1875, g = 0.675, b =0.1875). R塊與D塊是否匹配，就看R與D每個(gè)對(duì)應(yīng)點(diǎn)的距離的平方之和是否小于給定閾值，即下式是否滿足.2d(ri,di),i這里,R=(r

22、i)是子塊R像素點(diǎn)組成的n維向量，D =( di )是D塊經(jīng)四鄰域平均的與R等大的子塊，是給定閾值.方法3.與方法1相似，只是將顏色模型轉(zhuǎn)換到Y(jié)UV空間,再在YUV空間作彩色圖像兩點(diǎn)的距離定義，然后再將對(duì)應(yīng)點(diǎn)的距離的平方之和是否小于給定閾值作為R塊和D塊是否匹配的標(biāo)準(zhǔn).對(duì)于彩色圖像質(zhì)量衡量問題，由于顏色感知與人眼的視覺特征密切相關(guān)，對(duì)于不同的顏色以及顏色的不同變化方向，人眼的感知靈敏度是不一樣的，因而顏色的度量是一個(gè)復(fù)雜的過程.這就使得彩色圖像質(zhì)量的評(píng)價(jià)比起灰度圖像要困難得多.為了簡單、客觀起見，仍然采用PSNR作為彩色圖像恢復(fù)質(zhì)量的評(píng)價(jià)，但是我們將分別 列出圖像三色分量的PSNR.3實(shí)驗(yàn)結(jié)果

23、及分析我們用本文的方法對(duì)隨機(jī)抽取的256 256的24位真彩色圖像進(jìn)行了實(shí)驗(yàn).在尋找塊時(shí)，采用金字塔小波的加速算法4來提高編碼速度，在Pm 700型微機(jī)上根本上能夠在2秒之內(nèi)完成對(duì)一幅圖像的編碼(在實(shí)驗(yàn)中，我們沒有引入旋轉(zhuǎn)對(duì)稱變換，同時(shí)仿射變換取為經(jīng)驗(yàn)值 0.75).從實(shí)驗(yàn)的結(jié)果來看，本文提出的幾種尋找匹配D塊的方法所得到的解碼圖像質(zhì)量和壓縮比相近，僅就速度來看，方法1編碼要好一些，大約是其他方法編碼速度的3倍.與SFC相比(這里主要是指沒有經(jīng)過Huffman或算術(shù)等無損編碼處理的SFC方法，因?yàn)槲覀兊姆椒ㄒ矝]有經(jīng)過這些處理),我們的方法在圖像解碼質(zhì)量沒有明顯下降的情況下，編碼速度及壓縮比都有

24、很大的提高.與標(biāo)準(zhǔn)JPEG(編碼時(shí)采用JPEG標(biāo)準(zhǔn)所提供的量化表，并使用經(jīng)過優(yōu)化的Huffman碼表)相比，在圖像解碼質(zhì)量相似甚至更高的情況下，該方法即使對(duì)系數(shù)沒有進(jìn)行其他無損編碼，也有相對(duì)較高的壓縮比.表3和圖3分別給岀了各種方法比擬的結(jié)果數(shù)據(jù)及解碼圖其中圖3(a)是原始圖像周3(b)是JPEG解碼圖像(Cr 12.0,PSNR分別為25.0(r),26.0(g),22.0(b),圖 3(c)是使用本文的方法1 得到的解碼圖像(Cr 14.2,PSNR 分別為 24.9(r),25.3( g), 21.4(b).Table 3 Compression ratio and PSNR of de

25、coded image among several methods 表3各種方法圖像壓縮比及解碼質(zhì)量AlgorithmsFruitDogPSNR(db)CRPSNR(db)CR24.9(r)25.4(r)Method 1 in this paper25.3(g)14.226.1(g)15.221.4(b)25.1(b)25.6(r)25.3(r)Method 2 in this paper25.3(g)13.125.8(g)15.222.4(b)25.0(b)24.7(r)24.4(r)Method 3 in this paper25.1(g)13.625.5(g)15.923.2(b)25.0(b)26.6(r)26.4(r)SFC25.5(g)8.126.2(g)8.525.0(b)26.7(b)25.0(r)25.5(r)JPEG26.0(g)12.026.4(g)12.522.0(b)24.9(b)(a)(b)(c)Fig