郭 慧， 賀 杰， 盧振坤

(1.梧州學(xué)院 信息與電子工程學(xué)院，廣西 梧州 543002；2.廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，廣西 南寧 530006)

結(jié)合分類方法的并行分形圖像編碼算法研究*

郭 慧1*， 賀 杰1， 盧振坤2

(1.梧州學(xué)院 信息與電子工程學(xué)院，廣西 梧州 543002；2.廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，廣西 南寧 530006)

針對(duì)分形圖像編碼計(jì)算密集的特點(diǎn)，建立編碼步驟的串行-并行轉(zhuǎn)化機(jī)制，利用計(jì)算統(tǒng)一設(shè)備架構(gòu)CUDA的單指令、多線程執(zhí)行特性，建立分形編碼在圖像處理器GPU上的并行計(jì)算模型，將耗時(shí)量較大的搜索最佳匹配塊的串行執(zhí)行過(guò)程并行化處理，并在此基礎(chǔ)上結(jié)合方差法對(duì)值域塊進(jìn)行分類以減少搜索次數(shù).實(shí)驗(yàn)結(jié)果表明，該文算法與原始算法相比可達(dá)到1 200多倍的加速并保持較好的解碼圖像質(zhì)量，滿足了實(shí)時(shí)編碼的要求.

分形圖像壓縮；計(jì)算統(tǒng)一設(shè)備架構(gòu)；并行計(jì)算；分類；方差

分形圖像編碼方法是一種建立在空間域的有損圖像壓縮技術(shù)，其理論基礎(chǔ)是迭代函數(shù)系統(tǒng)及拼貼定理.該方法根據(jù)自然圖像的不同局部之間存在的跨尺度自相似性來(lái)進(jìn)行編碼，從而減少圖像的數(shù)據(jù)冗余，具有分辨率無(wú)關(guān)及解碼快速等優(yōu)點(diǎn).但分形編碼也存在搜索匹配計(jì)算量大，耗時(shí)長(zhǎng)等不足，難以滿足實(shí)時(shí)性需求，因而加速編碼過(guò)程成為分形編碼改進(jìn)的重要方向.為減少匹配塊的搜索時(shí)間，劉小丹等人[1]提出了一種改進(jìn)的 K-means聚類優(yōu)化的圖像分割方法.吳一全、孫子翼[2]則針對(duì)K-均值聚類分形編碼算法依賴數(shù)據(jù)分布等問(wèn)題，提出了一種基于免疫粒子群優(yōu)化和核模糊聚類的方法，與基本分形編碼算法相比可達(dá)到6倍的加速.Hui Guo[3]等結(jié)合人類視覺系統(tǒng)特性改進(jìn)了四叉樹分形編碼方法，以求將解碼時(shí)的失真控制在人眼無(wú)法識(shí)別的范圍之內(nèi)，但提速效果最多也只是27倍.屠添翼[4]等人提出一種對(duì)小波樹進(jìn)行加權(quán)處理，然后進(jìn)行分形編碼的方法來(lái)進(jìn)行加速.Hui Yua等人[5]以前一最佳匹配塊為中心、在其鄰域搜索當(dāng)前最佳匹配塊，改進(jìn)了四叉樹分形編碼方法.Yih-Lon Lin[6]利用邊緣形狀相似的塊集中于某些特定區(qū)域這一現(xiàn)象來(lái)實(shí)現(xiàn)鄰域搜索.Wu YG等提出的方差法[7],將值域塊分成簡(jiǎn)單塊和復(fù)雜塊，再結(jié)合近鄰搜索法來(lái)減少搜索的碼本.

以上研究都是從編碼算法的優(yōu)化方面來(lái)縮短編碼時(shí)間.分形編碼呈現(xiàn)出典型的串行執(zhí)行特征，其匹配過(guò)程是逐個(gè)對(duì)每個(gè)R塊進(jìn)行D塊池全局或分類局部搜索，可視為對(duì)相同步驟的串行重復(fù)執(zhí)行，因此，將這類步驟并行化執(zhí)行是一種可行的優(yōu)化方法.特別是目前已有許多硬件具有并行運(yùn)算結(jié)構(gòu)，如能將分形編碼與某種普及程度高、成本低廉的并行硬件結(jié)合，建立相應(yīng)的實(shí)施機(jī)制，將會(huì)顯著提升編碼速度.圖形處理器GPU具有大量并行的硬件運(yùn)算單元，適用于對(duì)多個(gè)數(shù)據(jù)對(duì)象進(jìn)行并行運(yùn)算.計(jì)算統(tǒng)一設(shè)備架構(gòu)CUDA則是一種處理與管理GPU計(jì)算的新型軟件架構(gòu)和編程模型，具有單指令、多數(shù)據(jù)的執(zhí)行模式，能夠利用CPU處理應(yīng)用程序的順序部分,同時(shí)通過(guò)API在GPU上以線程為基本單位進(jìn)行計(jì)算密集型部分的并行執(zhí)行[8].

本文提出一種建立在GPU的基礎(chǔ)上，利用CUDA架構(gòu)進(jìn)行并行編碼的快速分形圖像壓縮算法.該方法由四部分構(gòu)成：采用四鄰域平均法對(duì)定義域塊進(jìn)行空間壓縮、值域塊和定義域塊的預(yù)處理、值域塊的分類、最小均方誤差的計(jì)算.在對(duì)定義域塊的空間壓縮過(guò)程中，使用一種并行執(zhí)行方案，即GPU的每個(gè)線程完成一個(gè)定義域塊的平均采樣工作；在預(yù)處理階段中，GPU的每個(gè)線程會(huì)分別計(jì)算出每個(gè)值域塊及被搜索的定義域塊的像素和；在分類過(guò)程中，結(jié)合Wu YG等提出的方差法[7]把值域塊分為簡(jiǎn)單塊和復(fù)雜塊，只對(duì)復(fù)雜塊進(jìn)行編碼；在最小均方誤差的計(jì)算中，每個(gè)復(fù)雜塊均會(huì)有對(duì)應(yīng)的獨(dú)立線程進(jìn)行匹配搜索和求解最小均方誤差.實(shí)驗(yàn)結(jié)果表明，本文所提出的改進(jìn)算法與傳統(tǒng)的分形圖像壓縮方法相比，可提速1200多倍，并保持較好的解碼圖像質(zhì)量，滿足分形編碼的實(shí)時(shí)性要求.

1 傳統(tǒng)分形編碼方法

Mandelbrot首次提出分形圖像是一個(gè)迭代函數(shù)系統(tǒng)[9]，他認(rèn)為自然界中很多事物的結(jié)構(gòu)都具有相似的部分，并指出一片分形云可以用一個(gè)簡(jiǎn)單的數(shù)學(xué)函數(shù)來(lái)描述.1988年，Barnsly 和 Sloan提出分形圖像壓縮方法，利用圖像的局部的自相似性來(lái)進(jìn)行壓縮[10].1992年，Jacquin提出的實(shí)用分形塊編碼實(shí)現(xiàn)了計(jì)算機(jī)自動(dòng)分形編碼[11]，分形編碼方法首先要將圖像劃分成互不重疊的R×R方塊及可重疊的D×D方塊，分別稱為值域塊(R塊)與定義域塊(D塊)，定義域塊的尺寸要大于值域塊.隨后對(duì)定義域塊進(jìn)行平均采樣，使得定義域塊與值域塊的尺寸一致，所有的定義域塊可存放在定義域池SD中.

一幅大小為N×N的圖像可劃分為i個(gè)定義域塊和j個(gè)值域塊，i=0,1,2,…，(N-2R+1)2，j=0,1,2,…,(N/R)2.通過(guò)最小平方誤差準(zhǔn)則為每個(gè)值域塊從定義域池SD中搜索最佳匹配的定義域塊，其仿射變換公式如式(1)所示.

(1)

(2)

(3)

(4)

(5)

假設(shè)I為原始圖像，R為值域塊大小，D為定義域塊大小.具體算法步驟如下：

Step1:將原圖像I分割為互不重疊的值域塊Rj，塊大小為R×R.

Step2:將原圖像I分割為可重疊的定義域塊Di，塊大小為D×D.

Step3:對(duì)定義域塊進(jìn)行平均采樣，使得定義域塊的大小與值域塊一致.

Step4:對(duì)于每個(gè)值域塊Rj，在定義域池SD中找到對(duì)應(yīng)的定義域塊Di，確保對(duì)Di進(jìn)行仿射變換后，若得到Rj與Di之間的均方誤差值最小，該Di為Rj的最佳匹配塊.

Step5:對(duì)于每一個(gè)值域塊Rj，記錄變換庫(kù)wi(dx，dy，n,si，oi)構(gòu)成的分形碼(IFS碼)：

(1) 搜索到的最佳匹配塊Di的左上角坐標(biāo)dx,dy；

(2) 使Rj與Di成為等距變換編號(hào)n(n為0～7)；

(3) 對(duì)比度調(diào)整系數(shù)Si和亮度調(diào)整系數(shù)Oi.

2 分類算法

(6)

(7)

3 結(jié)合分類方法的并行分形圖像編碼算法

CUDA是一種新的處理和管理GPU計(jì)算的硬件和軟件架構(gòu)，應(yīng)用程序可通過(guò)CPU處理順序執(zhí)行部分,并通過(guò)CUDA相關(guān)API在GPU上完成計(jì)算密集部分的并行執(zhí)行，從而更充分發(fā)揮顯卡的大規(guī)模并行計(jì)算能力.在程序運(yùn)行時(shí)，CUDA 程序中的并行處理部分由內(nèi)核函數(shù)來(lái)完成，運(yùn)行在GPU上的內(nèi)核函數(shù)的基本單位是線程.CUDA會(huì)產(chǎn)生很多地址不同的并行線程，這些線程執(zhí)行內(nèi)核函數(shù)，實(shí)現(xiàn)對(duì)數(shù)據(jù)的并行處理.圖2 展示了CUDA的基本執(zhí)行原理，用CUDA編程實(shí)現(xiàn)的應(yīng)用程序主要構(gòu)成有兩部分：主機(jī)端(Host)代碼和設(shè)備端(Device)代碼.運(yùn)行在CPU上的串行處理部分為主機(jī)端代碼，而設(shè)備端代碼(即內(nèi)核kernel)則是運(yùn)行在顯示芯片GPU上的并行處理部分.Host端代碼一般主要是負(fù)責(zé)調(diào)度總體和邏輯性強(qiáng)的串行運(yùn)算，如初始化GPU以及數(shù)據(jù)交換等；而Device端代碼主要負(fù)責(zé)程序中并行化程度高的并行數(shù)據(jù)處理.

從圖3可知，在進(jìn)行搜索匹配之前，先要對(duì)定義域池中的D塊進(jìn)行平均采樣，這部分的計(jì)算工作是平均分配到各個(gè)線程上去計(jì)算完成的，將處理好的數(shù)據(jù)存到紋理內(nèi)存中.平均采樣的具體過(guò)程如圖4所示.

(8)

(9)

(10)

(11)

結(jié)合分類方法的并行分形圖像編碼算法的具體步驟如下：

輸入：一幅大小為N×N灰度圖像，象素灰度為8 比特量化，N一般為2 的方冪.

輸出：分形碼，即wi(dx，dy，n,si，oi).

Step 1：在CPU端讀入圖像數(shù)據(jù)，將原圖像I分割為互不重疊的值域塊Rj，塊大小為R×R；將原圖像I分割為可重疊的定義域塊Di，塊大小為D×D.并將這些數(shù)據(jù)傳輸?shù)皆O(shè)備內(nèi)存中.

Step 2：進(jìn)行平均采樣，構(gòu)成碼本.將每個(gè)定義域塊的平均采樣工作分配給每一個(gè)線程，即一個(gè)定義域塊的子采樣工作由一個(gè)線程去完成.

Step 6：將分形碼由設(shè)備端傳輸?shù)紺PU端.

Step 7：輸出分形碼wi(dx，dy，n,si，oi).

本文算法的解碼流程跟傳統(tǒng)算法的解碼流程基本一致，僅多了一個(gè)是否是簡(jiǎn)單塊的判斷條件，對(duì)于簡(jiǎn)單塊，直接取其像素平均值覆蓋該塊；對(duì)于復(fù)雜塊，則讀取分形碼進(jìn)行迭代解碼.

4 實(shí)驗(yàn)數(shù)據(jù)及結(jié)果分析

為了驗(yàn)證算法的有效性，本文采用256×256×8的Lena、Pepper、 Cat、Rose、Heci這5幅標(biāo)準(zhǔn)測(cè)試圖像進(jìn)行測(cè)試，這5幅圖像在紋理及邊緣細(xì)節(jié)的均衡與變化等方面均有代表意義，能很好的測(cè)試各種圖像處理算法.所有待測(cè)試圖像均設(shè)定值域塊大小為4×4，定義域塊大小為8×8.程序開發(fā)環(huán)境為Microsoft Visual Studio 2010+ CUDA6.0+Opencv2.3，系統(tǒng)為64位Windows 8.1，內(nèi)存為4 GB，顯卡為Nvidia Geforce GT 630M，CPU為Core I3.下面分別采用傳統(tǒng)分形編碼算法、并行分形編碼算法、結(jié)合分類的并行分形編碼算法對(duì)這5幅圖像進(jìn)行編碼，在解碼的時(shí)候，創(chuàng)建一個(gè)空白的矩陣，經(jīng)過(guò)9次迭代，即可逼近原圖，實(shí)驗(yàn)結(jié)果如圖6～圖8所示.

由圖6～圖8可知，從肉眼來(lái)看，采用這三種算法的解碼圖像的效果是基本一致的，這證明了并行算法的可行性.表1是采用這三種算法進(jìn)行編碼的時(shí)間T、解碼圖像的PSNR值及加速比.

表1 使用三種算法的實(shí)驗(yàn)數(shù)據(jù)

由表1的數(shù)據(jù)可知，并行算法與傳統(tǒng)分形編碼算法相比，編碼時(shí)間要要明顯少于傳統(tǒng)的分形編碼算法，最大的加速比可達(dá)135倍，其PSNR值與傳統(tǒng)算法一致.這是因?yàn)樵诓⑿兴惴ㄖ?，利用了圖形處理器GPU的并行硬件運(yùn)算單元，將耗時(shí)量較大的搜索最佳匹配塊的串行執(zhí)行過(guò)程并行化處理，從而縮短了編碼時(shí)間，并保證了解碼圖像的質(zhì)量不變.

隨后在并行算法的基礎(chǔ)上，加入對(duì)值域塊的分類機(jī)制，構(gòu)成結(jié)合分類方法的并行分形編碼算法，這比采用單一的并行算法提速更快，與傳統(tǒng)算法相比較，加速比最大可達(dá)1 222倍，而解碼圖像的PSNR值只是略有下降，這是由于簡(jiǎn)單塊在解碼過(guò)程中采用像素平均值代替原像素值導(dǎo)致的.因此，利用CUDA架構(gòu)對(duì)分形圖像壓縮的編碼過(guò)程進(jìn)行并行化執(zhí)行，并在此基礎(chǔ)上對(duì)算法進(jìn)行優(yōu)化，可使編碼時(shí)間達(dá)到毫秒級(jí)，基本滿足實(shí)時(shí)編碼的要求.

傳統(tǒng)分形編碼方法壓縮比C的計(jì)算公式為：C=256×256×8/(h×(8+8+3+5+7))，其中h表示值域塊的總數(shù)，定義域塊的左上角坐標(biāo)dx和dy分別被量化為8 bit，等距變換的矩陣號(hào)n被量化為3 bit，灰度對(duì)比度因子S被量化為5 bit，灰度亮度因子O被量化為7 bit.當(dāng)設(shè)定值域塊大小為4×4時(shí)，對(duì)圖像進(jìn)行分割后所獲得的值域塊的總數(shù)是一個(gè)固定值：h=256/4×256/4=4 096，壓縮比C=4.13.而采用本文的分類并行算法時(shí)，壓縮比C的計(jì)算方法為：C=256×256×8/(S1×(1+8)+S2×(7+7+3+5+7))，這里S1表示簡(jiǎn)單塊的總數(shù)，S2表示復(fù)雜塊的總數(shù).對(duì)簡(jiǎn)單塊，在矩陣中用0做標(biāo)記，量化為1比特，像素平均值被量化為8 bit；復(fù)雜塊左上角坐標(biāo)dx和dy分別被量化為7 bit，其他參數(shù)與傳統(tǒng)算法一致.

表2 使用兩種算法的壓縮比

5 總 結(jié)

本文提出了結(jié)合分類方法的并行分形編碼算法.這種并行的分形圖像壓縮方法結(jié)合Wu YG[7]等提出的分類方法，充分利用GPU上的線程把分形編碼中對(duì)匹配塊的搜索并行化執(zhí)行，使編碼時(shí)間達(dá)到毫秒級(jí).實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的分形圖像壓縮方法相比，本文算法在保持較好的解碼圖像質(zhì)量的基礎(chǔ)上可達(dá)到1 200多倍的加速，且壓縮比更高.在今后的工作中，將進(jìn)一步開發(fā)使用GPU去優(yōu)化CPU代碼縮短編碼時(shí)間、提高解碼圖像質(zhì)量，并把這些方法用于其他領(lǐng)域中，如動(dòng)態(tài)圖像的編碼等.

[1] 劉小丹,牛少敏.一種改進(jìn)的K-means聚類彩色圖像分割方法[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào)，2012, 34(2):90-93.

[2] 吳一全，孫子翼. 免疫粒子群核模糊聚類快速分形圖像編碼[J] .北京郵電大學(xué)學(xué)報(bào)，2011,34(1):69-74.

[3] GUO H,ZHENG Y P,HE J. A new HVS-based fractal image compression algorithm[J].Lecture Notes in Electrical Engineering，2012，138：753-759.

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

[5] YU H,LI L D,LIU H,et al.Based on quadtree fractal image compression improved algorithm for research[C]// E-Product E-Service and E-Entertainment，2010: 1-3.

[6] LIN Y L,WU M S.An edge property-based neighborhood region search strategy for fractal image compression[J]. Computers & Mathematics with Applications, 2011, 62 (1)：310-318.

[7] WU Y G,HUANG M Z,WEN Y L.Fractal image compression with variance and mean[C]//Proc IEEE ICME. Maryland,2003: 353.

[8] 馬巍巍，孫東，吳先良. 基于GPU的高階辛FDTD算法的并行仿真研究[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2012,35(7)：926-929.

[9] MANDELBROT B B. The Fractal Geometry of Nature[M].2 ed.New York:Times Books,1982.

[10] BARNSLEY M,SLOAN A. A better way to compress images[M].BYTE, 1988.

[11] JACQUIN A E. Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Trans, Image Processing,1992,1(1):18-30.

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

Research on Parallel Fractal-Image Coding Algorithm Combined with Classification Method

GUOHui1*,HEJie1，LUZhen-kun2

(1.School of Information and Electronic Engineering, Wuzhou University, Wuzhou 543002;2.College of Information Science and Engineering, Guangxi University for Nationlities,Nanning 530006 China)

Directed against the characteristic of computational intensity of fractal image encoding, a serial-parallel transfer mechanism is built for encoding procedures. By utilizing the properties of single instruction and multithreading execution of compute unified device architecture (CUDA), the parallel computational model of fractal encoding is built on the graphic processor unit(GPU) in order to parallelize the considerably time-consuming serial execution process of searching for the block of best match, on which base to classify the blocks of range in combination with the variance method in order to reduce the frequency of search. The experimental result indicates, the algorithm in this paper, as compared with the original algorithm, can achieve an acceleration of 1 200 and more times and keep the decoded image in good quality, which addresses the demand for real-time encoding.

fractal image compression; compute unified device architecture; parallel computing; classification; variance

2014-03-25

國(guó)家自然科學(xué)基金項(xiàng)目(61362038);廣西自然科學(xué)基金青年項(xiàng)目(2013GXNSFBA019276，2013GXNSFBA019275,2014GXNSFBB118005);廣西高校科研項(xiàng)目(2013YB227, 2013YB228)

郭慧(1981— ),女，廣西 梧州人，副教授.E-mail:guohui928@qq.com

TP391

A

1000-5900(2015)01-0097-06