郭 慧， 賀 杰， 盧振坤

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

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

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

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

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

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

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

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

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

2 分類算法

(6)

(7)

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

CUDA是一種新的處理和管理GPU計算的硬件和軟件架構(gòu)，應(yīng)用程序可通過CPU處理順序執(zhí)行部分,并通過CUDA相關(guān)API在GPU上完成計算密集部分的并行執(zhí)行，從而更充分發(fā)揮顯卡的大規(guī)模并行計算能力.在程序運(yùn)行時，CUDA 程序中的并行處理部分由內(nèi)核函數(shù)來完成，運(yùn)行在GPU上的內(nèi)核函數(shù)的基本單位是線程.CUDA會產(chǎn)生很多地址不同的并行線程，這些線程執(zhí)行內(nèi)核函數(shù)，實(shí)現(xiàn)對數(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)行搜索匹配之前，先要對定義域池中的D塊進(jìn)行平均采樣，這部分的計算工作是平均分配到各個線程上去計算完成的，將處理好的數(shù)據(jù)存到紋理內(nèi)存中.平均采樣的具體過程如圖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)成碼本.將每個定義域塊的平均采樣工作分配給每一個線程，即一個定義域塊的子采樣工作由一個線程去完成.

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

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

本文算法的解碼流程跟傳統(tǒng)算法的解碼流程基本一致，僅多了一個是否是簡單塊的判斷條件，對于簡單塊，直接取其像素平均值覆蓋該塊；對于復(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)測試圖像進(jìn)行測試，這5幅圖像在紋理及邊緣細(xì)節(jié)的均衡與變化等方面均有代表意義，能很好的測試各種圖像處理算法.所有待測試圖像均設(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é)合分類的并行分形編碼算法對這5幅圖像進(jìn)行編碼，在解碼的時候，創(chuàng)建一個空白的矩陣，經(jīng)過9次迭代，即可逼近原圖，實(shí)驗(yàn)結(jié)果如圖6～圖8所示.

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

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

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

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

傳統(tǒng)分形編碼方法壓縮比C的計算公式為：C=256×256×8/(h×(8+8+3+5+7))，其中h表示值域塊的總數(shù)，定義域塊的左上角坐標(biāo)dx和dy分別被量化為8 bit，等距變換的矩陣號n被量化為3 bit，灰度對比度因子S被量化為5 bit，灰度亮度因子O被量化為7 bit.當(dāng)設(shè)定值域塊大小為4×4時，對圖像進(jìn)行分割后所獲得的值域塊的總數(shù)是一個固定值：h=256/4×256/4=4 096，壓縮比C=4.13.而采用本文的分類并行算法時，壓縮比C的計算方法為：C=256×256×8/(S1×(1+8)+S2×(7+7+3+5+7))，這里S1表示簡單塊的總數(shù)，S2表示復(fù)雜塊的總數(shù).對簡單塊，在矩陣中用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上的線程把分形編碼中對匹配塊的搜索并行化執(zhí)行，使編碼時間達(dá)到毫秒級.實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的分形圖像壓縮方法相比，本文算法在保持較好的解碼圖像質(zhì)量的基礎(chǔ)上可達(dá)到1 200多倍的加速，且壓縮比更高.在今后的工作中，將進(jìn)一步開發(fā)使用GPU去優(yōu)化CPU代碼縮短編碼時間、提高解碼圖像質(zhì)量，并把這些方法用于其他領(lǐng)域中，如動態(tài)圖像的編碼等.

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

[2] 吳一全，孫子翼. 免疫粒子群核模糊聚類快速分形圖像編碼[J] .北京郵電大學(xué)學(xué)報，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é)報，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é)報：自然科學(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

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

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

TP391

A

1000-5900(2015)01-0097-06