一種分形彩色圖像壓縮編碼方法

1、一種分形彩色圖像壓縮編碼方法焦華龍陳剛1,21(浙江大學計算機圖象圖形研究所，浙江杭州 310027)2(寧波大學 數(shù)字技術與應用軟件研究所，浙江 寧波 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的相關性和分形四叉樹編碼層次信息冗余性的根底上，提岀了一種分形彩色圖像壓縮編碼方法.它將圖像的3個獨立的顏色分量按某種方式組合成1個來搜索匹配塊，從而將需要存儲和搜索的3個顏色分量匹配塊(SFC方法)減少為1個，并且對四叉樹層次信息進行壓縮.此外，采用不同的組合，得到了幾個圖像壓縮比和解碼質量相近的編碼方法，其中使用亮度分量的方法比使用其他方法速度更快.實驗結果說明，它優(yōu)于SFC方法及標準JPEG方法，不失為一種好的分形彩色圖像壓

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

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

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

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

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

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

13、次信息壓縮倍數(shù) 較大，因而有較好的壓縮效果.推導過程如下：;ni表示圖像分塊中大小為2i+1 2i+1的R塊個數(shù)(i=1,2,3,4).對于一般圖像來說，山(1)沒有壓縮之前需要的空間為2(nn2 n3n4)個bit;間,即可得到上述壓縮倍數(shù)計算公式.例如，對于如圖1所示的四叉樹剖分設整個塊大小是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個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及標志信息0 0 1 0 1 0 0 1 0 1 0 0,再經(jīng)過一次編碼后成為最終的01及標志信息0 1 1 1和0 0 1 0 1 0 01 0 1 0 0表示，由于最終的信息非標志信息只是32 32和16 16兩種遨只要1bit表示即可01可用1來表示, 也就是說，最后我們用了共17bit,壓縮倍數(shù)為50/17 3.解碼時只需將編碼過程反過來，就能恢復所有的層次信息.2編碼方法2.1三色相關性在將圖像中每個像素的三色分量r,g,b各自單獨抽取出來作為灰度圖像在該點的灰度值的觀察中，我

15、們發(fā)現(xiàn)它們在結構上具有非常相似的地方，有差異的只是在不同的地方，其亮度有所不同如圖2所示.也就是說，當我們用分形方法進行圖像編碼時，如果有一個分量的 R塊和D塊相似，那么另外兩個分量的相同位置的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)計分析亮度Y及r,g,b顏色之間的相關性，我們得到了表1的結

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

17、看，當Y顏色分量的匹配誤差小于給定的閾 值時,r,g,b顏色分量的匹配誤差是可以接受的，實驗得到的解碼圖像質量與SFC并沒有太大的差異.這也說明了該方法的可行性.相關性系數(shù)的計算公式為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對彩色Fruit圖像分割為4 4小塊得到的各顏色分量兩兩之間相關性系數(shù)大于0.8所占百分數(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對應匹配誤差所占百分數(shù)Matching errorrgb7.590.275.095.310.094.079.496.32.2具體的編解碼方法步驟從圖像三色相關性出發(fā)，我們形成了彩色圖像的如下的編、解碼方法方法1.(1) 對要編碼的彩色圖像I每一像素點的r,g,b進行組合(實驗中取亮度分量Y=0.301r+0.586g+0.113b),得到一幅灰度圖I .(2) 對灰度圖I進行傳統(tǒng)的分形四叉樹搜索，使I中的每個R塊找到相匹配的 D塊.(3) 將編碼彩色圖像I的r (紅色)分量所組成的灰度圖Ir中R塊和D塊匹配的位置對稱旋轉變換，樹結構用I中得到的

20、來替代，只是將反映亮度的局部(即灰度仿射變換系數(shù)和)用從Ir中計算得到的最正確匹配值重新計算進行修正;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) 對彩色圖像I的每個R塊,存儲從I得到的匹配D塊位置，對稱旋轉變換及r,g,b分量的6個亮度修正 值,R塊的四叉樹層次信息用我們前面所提出的方法存儲解碼過程：先恢復R塊的樹結構，再分別對r,g,b分量用IFS(迭代函數(shù)系)迭代得到3幅灰度圖Ir,Ig,Ib，

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

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

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

24、很大的提高.與標準JPEG(編碼時采用JPEG標準所提供的量化表，并使用經(jīng)過優(yōu)化的Huffman碼表)相比，在圖像解碼質量相似甚至更高的情況下，該方法即使對系數(shù)沒有進行其他無損編碼，也有相對較高的壓縮比.表3和圖3分別給岀了各種方法比擬的結果數(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各種方法圖像壓縮比及解碼質量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