賀 杰， 郭 慧， 李 琳

(1.梧州學(xué)院 廣西高校行業(yè)軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西 梧州 543002；2.梧州學(xué)院 信息與電子工程學(xué)院，廣西 梧州 543002；3.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

?

基于SNAMG分割的分形圖像壓縮方法

賀 杰1*， 郭 慧2， 李 琳3

(1.梧州學(xué)院 廣西高校行業(yè)軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西 梧州 543002；2.梧州學(xué)院 信息與電子工程學(xué)院，廣西 梧州 543002；3.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

針對分形圖像壓縮的編碼速度與解碼質(zhì)量難以均衡優(yōu)化的問題，依據(jù)人類視覺系統(tǒng)特性，使用視覺閾值對圖像的SNAMG分割方法進(jìn)行優(yōu)化，建立了自適應(yīng)子塊分割機(jī)制，并將其用于改進(jìn)編碼過程．實(shí)驗(yàn)表明，較之Jacquin的經(jīng)典分形算法，本文算法能夠獲得30～40倍的加速比和更好的解碼質(zhì)量．

分形圖像壓縮；視覺閾值；SNAMG

圖像的分形編碼是同等解碼質(zhì)量下壓縮比最高的空間域壓縮方法之一，并具備解碼速度快、解碼分辨率無關(guān)等優(yōu)點(diǎn)，已有學(xué)者將分形編碼的圖像自相似性描述思想用于解決圖像檢索[1]、圖像分割[2]、圖像修復(fù)[3]、數(shù)字水印[4]等問題．

分形圖像壓縮方法也存在編碼時(shí)間過長、解碼易出現(xiàn)塊狀效應(yīng)等不足．一些學(xué)者通過子塊分類和鄰域搜索來縮短編碼時(shí)間。K. Jaferzadeh等利用像素值空間和1D-DCT矢量實(shí)現(xiàn)子塊的模糊聚類[5]；鄭秋梅等使用脈沖耦合神經(jīng)網(wǎng)絡(luò)算法對原圖像進(jìn)行不規(guī)則區(qū)域分割，然后利用所得二值圖像的灰度值與原圖像的灰度值兩個(gè)特征對圖像塊進(jìn)行聯(lián)合分類[6]，這兩種方法均在保證解碼質(zhì)量的前提下，大幅減少了編碼時(shí)間。李高平等則使用轉(zhuǎn)動(dòng)慣量特征來實(shí)現(xiàn)鄰域搜索，從而有效縮小匹配搜索范圍，提高編碼效率[7]。也有學(xué)者通過改進(jìn)分割方法或結(jié)合其他算法來提高解碼質(zhì)量。屠添翼、石躍祥將圖像的小波樹加權(quán)處理、然后再結(jié)合分形編碼進(jìn)行混合壓縮，在壓縮比相同的情況下提高解碼圖像質(zhì)量[8]；Hui Guo等則使用視覺閾值改進(jìn)了四叉樹分形編碼方法，將解碼時(shí)的失真控制在人眼無法察覺的范圍內(nèi)[9]；牟宇飛等對圖像小波變換后的最低分辨率子帶進(jìn)行均勻量化編碼，對高分辨率子帶通過閾值控制采用四叉樹分形編碼，實(shí)現(xiàn)解碼質(zhì)量的提升[10]。

上述研究均可使分形壓縮在速度或解碼質(zhì)量某一單方面獲得優(yōu)化，但無法做到兩方面性能的均衡提升。分割方法是控制編碼子塊總量、保留圖像局部紋理特征的關(guān)鍵，SNAMG(Square Non-symmetry and Anti-packing Model for Gray Images)分割方法能夠自適應(yīng)圖像紋理，根據(jù)灰度分布自動(dòng)調(diào)節(jié)子塊大小，產(chǎn)生的子塊總量少于已經(jīng)廣泛應(yīng)用的四元樹等表示方法[11]．因此，本文嘗試?yán)萌祟愐曈X系統(tǒng)特性，通過視覺閾值與雙線性內(nèi)插法優(yōu)化SNAMG分割，并將其用于改進(jìn)分形編碼，從而做到編碼速度與解碼質(zhì)量的均衡優(yōu)化．

1 分形圖像壓縮方法

分形圖像壓縮將圖像分割為定義域塊(D塊)與值域塊(R塊)，利用圖像的局部自相似性尋找它們之間的對應(yīng)關(guān)系[12]．對于大小為256×256的圖像，首先將圖像分割為互不重疊的8×8的值域塊，構(gòu)成值域池(Range Pool)；然后以2個(gè)像素為步進(jìn)值，將圖像分割為重疊的16×16的定義域塊，構(gòu)成定義域池(Domain Pool)．分割過程如圖1所示．

編碼時(shí)每個(gè)值域塊必須在定義域池中尋找最佳匹配的定義域塊．仿射變換如式(1)，說明了值域塊對應(yīng)至定義域塊的轉(zhuǎn)換關(guān)系．

(1)

W為值域塊的仿射變換，x、y、z分別為值域塊的橫坐標(biāo)、縱坐標(biāo)及灰度值，i與j為定義域塊的坐標(biāo)，p為對比度平移系數(shù)，q為亮度平移系數(shù)．a(chǎn)k、bk、ck及dk則構(gòu)成等距變換的8種系數(shù)矩陣，代表空間域的8種同構(gòu)旋轉(zhuǎn)，如式(2)所示．

(2)

編碼完畢后，記錄(i,j)、p、q及表征旋轉(zhuǎn)方式的系數(shù)k作為分形碼．解碼時(shí)則通過局部迭代函數(shù)系統(tǒng)，不斷地迭代并逐步收斂以獲得重建圖像．

2 人類視覺系統(tǒng)

人類視覺系統(tǒng)無法完全辨別出圖像中所有紋理及灰度變化，這種特性使人眼在邊緣區(qū)域能夠容忍較大的量化誤差，視覺閾值即指恰好能夠被感覺到的量化誤差值．在現(xiàn)有圖像的參考灰度值基礎(chǔ)上加減不同閾值，然后用人眼觀察與原圖像的差別，若人眼辨別不出圖像的變化則說明該閾值為最佳閾值．由圖3可知，最佳閾值應(yīng)設(shè)定在30左右．

3 SNAMG分割方法

分割方法對灰度紋理的適應(yīng)性直接影響子塊總量與解碼效果．經(jīng)典分形編碼算法采取的固塊分割方式簡單易行，但不具備紋理自適應(yīng)性．為彌補(bǔ)其不足，F(xiàn)isher將四叉樹分割方法引入分形編碼[13]，通過靈活的分塊機(jī)制提高了編碼速度和壓縮比．

灰度圖像的SNAMG方法對于圖像紋理的自適應(yīng)性顯著優(yōu)于四元樹方法，產(chǎn)生的子塊數(shù)量也遠(yuǎn)少于四元樹等表示方法．其原理可簡述如下：預(yù)定義灰度正方形子塊框架，對于給定的灰度圖像，利用逆布局算法，依據(jù)匹配灰度值，分割提取并記錄正方形、線段、點(diǎn)子塊，然后用其組合來表示該給定的灰度圖像．圖3是一幅給定大小為8×8、位深為3的灰度圖像及其逆布局表示結(jié)果，共從原圖中抽取出了S1～S7共7個(gè)正方形，L1～L8共8個(gè)線段和2個(gè)孤立點(diǎn)P1、P2．

4 基于HVS特性與SNAMG分割的分形編碼算法

4.1 基于HVS閾值的SNAMG分割

經(jīng)典四元樹方法與SNAMG方法仍從直觀上對圖像進(jìn)行分割成塊，均未顧及到人類視覺系統(tǒng)特性，而人眼對灰度誤差的容忍度有助于在分割時(shí)更充分地保存局部紋理，從而使局部相似性更有效地落在子塊內(nèi)，故可通過閾值優(yōu)化SNAMG分割，尋找像素灰度值在分割閾值范圍內(nèi)、覆蓋面積最大的子塊，從而盡可能保留圖像局部灰度紋理，減少子塊的總量．其基本原理是在逆布局分割時(shí)以正方形初始點(diǎn)的灰度值g為參考值，假設(shè)閾值為x,則在分割過程中，只要近鄰像素點(diǎn)的灰度值處于g+/-(x/2)的區(qū)間，即可歸為同一正方形．

如圖4所示，未設(shè)置閾值時(shí)會(huì)形成較多線段與孤立點(diǎn)，圖5中設(shè)置閾值后，則將線段和點(diǎn)盡可能地納入正方形，減少編、解碼復(fù)雜度，節(jié)省存儲(chǔ)空間．

4.2 基于HVS閾值的SNAMG分割應(yīng)用于分形編碼

SNAMG分割方案與固塊分割方法的區(qū)別如圖6所示．

固塊分割未估計(jì)圖像灰度分布特征，相鄰像素值之間相差不大也會(huì)被按規(guī)則分割，破壞局部紋理的整體性．圖6(b)體現(xiàn)出使用HVS閾值的SNAMG分割方法的優(yōu)勢，即能夠較好的適應(yīng)灰度紋理特征并有效減少子塊數(shù)量，從而減少后續(xù)算法的運(yùn)算量，縮短編碼時(shí)間．

4.3 算法描述

編碼算法的具體步驟如下：

輸入:尺寸為M×M的單幅灰度圖像G．

輸出:最佳匹配塊D的左上角坐標(biāo)，等距變換序號，對比度因子，灰度平移因子，均方誤差．

步驟 1：設(shè)置一個(gè)計(jì)數(shù)變量square_num，記錄逆布局編碼過程中生成的正方形子塊的個(gè)數(shù)，并設(shè)其初值為0．

步驟 2：采用SNAMG逆布局分割方法，以形成面積最大的正方形為目標(biāo)．依據(jù)反對角掃描方式，從本次循環(huán)進(jìn)入G的首個(gè)像素點(diǎn)開始逐個(gè)搜索圖中未被標(biāo)識的像素點(diǎn)，搜索到某個(gè)正方形子塊的左上頂點(diǎn)(x,y)時(shí)，取其為起點(diǎn)，并將其灰度值z作為匹配參考值，設(shè)定一個(gè)閾值w，若后續(xù)被搜索的像素點(diǎn)灰度值處于z±w區(qū)間，則將其納入該正方形，搜索持續(xù)至此正方形子塊的面積停止增大時(shí)，在G中將其包含的所有像素點(diǎn)標(biāo)識．

步驟 3：使square_num=square_num+1，將該正方形子塊的左上頂點(diǎn)坐標(biāo)(x,y)、邊長length和灰度值z，存儲(chǔ)到隊(duì)列square中．

步驟 4：重復(fù)執(zhí)行步驟2與步驟3，直到無法提取出新的正方形子塊時(shí)則停止，從而獲得若干互不相交且尺寸相異的正方形值域塊，形成R塊池．

步驟 5：對G采取水平方向和垂直方向上的1/2次采樣操作，獲得大小為(M/2)×(M/2)的次采樣圖像G’，并通過閾值SNAMG分割構(gòu)造D塊池．

步驟 6：為每個(gè)R塊在D塊池中搜索最佳匹配子塊D，D通過灰度仿射變換操作與空間變換操作后，所獲得的D′與R之間的平方誤差值最小．

步驟 7：對于任一值域塊R，均記錄以下3個(gè)特征參數(shù)，形成分形碼：

(1) 最佳匹配子塊D的左上頂點(diǎn)坐標(biāo)．

(2) 令R與D形成最佳匹配的等距變換的類型序號．

(3) 灰度對比度因子，灰度平移因子．

假定R中的任意一個(gè)像素值為ri，D′中的任意一個(gè)像素值為di，其中1≤i≤n，n代表R中的像素的總數(shù)目，則本算法中s和p的計(jì)算方法如下：由于

(3)

且

D′=s×T2×T1(D)+p×I,

(4)

欲求mse的最小值，只需令

(5)

聯(lián)立以上兩個(gè)方程易解出：

(6)

(7)

解碼算法步驟與經(jīng)典算法基本一致，最后通過雙線性內(nèi)插法對編碼產(chǎn)生的點(diǎn)和線段填充補(bǔ)償．

5 實(shí)驗(yàn)及分析

實(shí)驗(yàn)環(huán)境為Windows 7.0、Corei5 2.26G處理器、2G內(nèi)存、Matlab7.0集成開發(fā)工具．實(shí)驗(yàn)圖像如圖7所示，均為256×256的灰度圖像．

實(shí)驗(yàn)以Jacquin的基本分形算法為比較對象．Jacquin算法中R塊尺寸為4×4，D塊尺寸為8×8，D池的滑動(dòng)窗口的步長為8，值域塊總數(shù)為 (256/4)×(256/4)=4 096．由于不同圖像的紋理相異，使用SNAMG方法達(dá)到最佳分割效果的閾值Q也有不同，如表1所示．

表1 兩種分割方法的值域塊總數(shù)

由表1可知，閾值SNAMG方法獲得的值域塊數(shù)量顯著少于基本分形算法的值域塊數(shù)量．兩種方法的編碼時(shí)間T、壓縮比、相對加速比、PSNR如表2所示.

表2 兩種方法的性能對比

由表2可知，本文算法是基本算法編碼速度的35倍左右，且解碼圖像質(zhì)量優(yōu)于基本算法．其中oldhouse的加速比最高，解碼質(zhì)量最好．該圖的灰度分布比較均勻，通過SNAMG分割后，紋理平滑部分形成的子塊較大，從而使值域塊數(shù)目最少，故編碼時(shí)間比其他幾幅圖要少，其加速比隨之增高．同時(shí)該圖的邊緣細(xì)節(jié)變化較為明顯，因而在邊緣細(xì)節(jié)形成較小子塊，確保了該圖在解碼時(shí)能夠獲得最好的圖像質(zhì)量．同理可知，由于bird灰度分布復(fù)雜且細(xì)節(jié)較多，導(dǎo)致該圖加速比最低且還原圖像質(zhì)量最差．

Jacquin算法分割所獲得的值域塊總數(shù)是一個(gè)固定值，實(shí)驗(yàn)圖像大小均為256×256、位深為8，因而壓縮比C為256×256×8/(S×(8+8+3+5+7))= 4.13．其中S為值域塊總量，定義域塊左上頂點(diǎn)的縱橫坐標(biāo)值均量化為8 比特，等距變換的類型號被量化為3 比特，灰度對比度因子與平移因子則分別量化為5 比特與7 比特．由于S為固定值4 096，故每幅實(shí)驗(yàn)圖像的壓縮比均相同．采用本文的SNAMG分形算法時(shí)，壓縮比C′=256×256×8/(S×(8+8+3+5+7)．S也為值域塊的總量，其余參數(shù)量化值不變．每幅圖像經(jīng)SNAMG分割產(chǎn)生的值域塊總量均少于固塊分割，故壓縮比得以提高．

圖8是使用Jaquin經(jīng)典分形算法解碼重建后的圖像，圖9是本文算法在取最佳閥值Q時(shí)解碼重建后的圖像，表2中數(shù)據(jù)表明本文算法所獲得的PSNR均高于經(jīng)典算法，解碼質(zhì)量更高，且此時(shí)從人眼視覺上已經(jīng)無法看出與原始圖像的差異．使用兩種算法重建的oldhouse、plane圖像的PSNR差值均大于4，圖10是將這兩幅圖像的局部放大5倍后的細(xì)節(jié)對比，左側(cè)為經(jīng)典分形算法重建圖像，右側(cè)為本文算法重建圖像，從主觀視覺上即可觀察出本文算法的解碼效果更好．

6 總 結(jié)

利用視覺閾值優(yōu)化SNAMG分割方案，將其應(yīng)用于分形圖像壓縮，通過與Jacquin基本分形算法的實(shí)驗(yàn)對比，證明了本文算法有效、全面，能夠使編碼速度、解碼質(zhì)量、壓縮比均得以提高．今后的工作將與分類、鄰域搜索等方法結(jié)合，進(jìn)一步提高分形圖像壓縮的性能．

[1] 洪安祥,陳剛,吳炯鋒,等.基于分形編碼的圖像相似匹配研究[J].電子學(xué)報(bào),2002, 30(5):624-627.

[2] IDA T, SALNBONSUGI Y. Image segmentation and contour detection using fractal coding[J].IEEE Transactions on Circuits and Systems for Video Technology,1998,8(8):968-975.

[3] 張彩明,范輝,原達(dá).基于分形的圖像修復(fù)算法[J].電子學(xué)報(bào),2010,38(10):2 430-2 435.

[4] 聶道聰,鄭洪源.一種使用正交分形編碼的彩色圖像水印算法[J]. 計(jì)算機(jī)與數(shù)字工程，2014, 42(1):129-133.

[5] JAFERZADEH K,KIANI K,MOZAFFARI S.Acceleration of fractal image compression sing fuzzy clustering and discrete-cosine-transform-based Metric[J]. Image Processing, 2012，6 (7) :1 024-1 030.

[6] 鄭秋梅，趙敏，王風(fēng)華，等.基于不規(guī)則區(qū)域分割及灰度排序分類的分形壓縮算法[J].中國石油大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,38(3):169-173.

[7] 李高平,楊軍，陳毅紅.改進(jìn)轉(zhuǎn)動(dòng)慣量特征的快速分形圖像編碼算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(24):144-148.

[8] 屠添翼，石躍祥.基于小波域的加權(quán)分形圖像編碼[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2004,26(2):25-28.

[9] GUO H,ZHENG Y P,HE J. A fast fractal image compression algorithm using improved quadtree partitioning scheme[C].Proceedings of the 2011 International Conference on Electrical, Information Engineering and Mechatronics, Jiaozuo, 2011,2: 745-751.

[10] 牟宇飛,張文普,王志中,等.基于小波變換和四叉樹的圖像分形編碼算法研究[J]. 微電子學(xué)與計(jì)算機(jī), 2013, 30(10):54-57.

[11] HE J, ZHENG Y P,GUO H. A novel gray image representation method based on NAM using nonoverlapping square subpatterns[C]. Proceedings of the 2011 International Conference on Electrical Information and Mechatronics, Jiaozuo,2011, 3: 760-764.

[12] ARNAUD E J. Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Processing, 1992, 1: 18-30.

[13] FISHER Y. Fractal image compression with quadtrees [A]. FISHER Y Ed. Fractal image compression-theory and application, New York: Springer-Verlay, 1995：55-77.

責(zé)任編輯：龍順潮

Fratcal Image Compression Based on the Segmentation of Square Non-Symmetry Anti-Packing

HEJie1*,GUOHui1,LILin2

(1．Guangxi Collegesand Universities Key Laboratory of Professional Software Technology, Wuzhou University, Wuzhou 543002;2.School of Information and Electronic Engineering, Wuzhou University, Wuzhou 543002;3.College of Computer Science and Technology, Wuhan University of Science and Technology, Wuzhou 430081 China)

Directed against the balanced optimization of the fratcal coding speed and decoding quality, based on the characteristics of human visual system, this paper uses visual threshold to optimize the non-overlapping square anti-packing segmentation method of images, establishes a self-adaptive segmentation mechanism of sub-blocks and applies it to improve fractal encoding. According to the experimental result, the algorithm in this paper can obtain 30 to 40 times speed-up ratio and better decoding quality compared with the classical fractal algorithm of Jacquin.

Fratcal Image Compression; Visual Threshold; SNAMG

2015-01-17

廣西自然科學(xué)基金項(xiàng)目(2013GXNSFBA019276，2013GXNSFBA019275);廣西高校科研項(xiàng)目(2013YB227, 2013YB228);武漢科技大學(xué)青年科研骨干基金項(xiàng)目(2014XZ017)

賀杰(1982— ),男，湖北 荊門人， 副教授.E-mail:guohui928@qq.com

TP391.4

A

1000-5900(2015)03-0093-08