孫 冬，高清維，盧一相，竺 德

(安徽大學(xué)電氣工程與自動(dòng)化學(xué)院，安徽合肥 230601)

作為新一代的圖像壓縮技術(shù)，分形編碼自20世紀(jì)80年代提出以來(lái)，由于具有極高的壓縮比和較好的解碼質(zhì)量，引起了人們的廣泛關(guān)注.然而分形編碼時(shí)間過長(zhǎng)是其固有的缺點(diǎn)，這也限制了它的推廣和應(yīng)用.為減少編碼時(shí)間，近30年來(lái)許多學(xué)者對(duì)此開展了深入研究［1－3］，他們的工作主要集中于:如何在不明顯降低圖像解碼質(zhì)量的基礎(chǔ)上，盡可能地減少待搜索父塊的數(shù)量.在已經(jīng)提出的諸多改進(jìn)方案中，以Davids的工作最為出色，他提出的小波域分形(wavelet－fractal，簡(jiǎn)稱FW)編碼算法［1］能夠極大地縮短編碼時(shí)間，而且解碼圖像質(zhì)量更高.雖然后人對(duì)FW編碼方案又進(jìn)行了許多改進(jìn)，但編碼時(shí)間距實(shí)時(shí)化仍有約2個(gè)數(shù)量級(jí)的差距.

現(xiàn)代處理器的架構(gòu)已經(jīng)將并行計(jì)算作為提高性能的一個(gè)最重要途徑.高性能的CPU由于很難克服提高時(shí)鐘頻率后的散熱問題，轉(zhuǎn)而使用增加運(yùn)算核心的方法來(lái)加速.作為CPU的協(xié)處理器，圖形處理器(graphics processor unit，簡(jiǎn)稱GPU)的計(jì)算能力在近年內(nèi)以遠(yuǎn)超摩爾定律的速度爆炸性增長(zhǎng).據(jù)報(bào)道2013年nVidia公司基于開普勒架構(gòu)GK110核心的GTX Titan型GPU單精度浮點(diǎn)運(yùn)算峰值速度達(dá)每秒4.5萬(wàn)億次，擁有2 688個(gè)流處理單元，由71億個(gè)晶體管組成，而熱設(shè)計(jì)功耗僅為250 W.由于GPU擁有CPU所不具有的超密集高并行的計(jì)算特點(diǎn)，將GPU用于非圖形領(lǐng)域的通用科學(xué)計(jì)算逐漸成為人們關(guān)注的熱點(diǎn)，具有重要的理論意義和應(yīng)用價(jià)值［4－7］.受此啟發(fā)，作者將GPU應(yīng)用到圖像分形編碼中，以尋求一種高實(shí)時(shí)性的編碼方案.

1 FW編碼原理

Barnsley認(rèn)為，自然界的圖像具有局部自相似性［8］.Jacqain根據(jù)這一假設(shè)，把圖像描述成一個(gè)帶灰度映射的局部迭代函數(shù)系統(tǒng)(local iterated function system with gray level maps，簡(jiǎn)稱LIFSM)的吸引子.文獻(xiàn)［9－10］中給出了LIFSM的編碼原理，將圖像分割成若干不重疊的塊，并為每個(gè)塊尋找一個(gè)與其相似的父塊及對(duì)應(yīng)的映射關(guān)系.

由于空域中大小為2J×2J的塊交流成分在小波域中近似地對(duì)應(yīng)為根在第J級(jí)子帶上的小波樹SJ，因此，當(dāng)空域中的兩個(gè)塊具有相似性時(shí)，它們?cè)谛〔ㄓ蛑兴鶎?duì)應(yīng)樹的各級(jí)數(shù)據(jù)之間也具有相似性，并且這種相似性是一致的(空域塊的自相似性和相應(yīng)小波域中樹的自相似性請(qǐng)參見圖1，圖1b中，每棵樹由3個(gè)方向的分支組成).Davis根據(jù)這一事實(shí)，把LIFSM編碼引入小波域，提出了FW編碼算法，將空域中塊的相似性用小波域中樹的相似性來(lái)近似等價(jià).與LIFSM編碼相比，F(xiàn)W編碼算法能夠極大地縮短編碼時(shí)間，而且解碼圖像的視覺質(zhì)量也更高.

圖1 自相似性Fig.1 Self-similarity

gm，n為對(duì)比度變換因子，定義為

其中:Cov為協(xié)方差運(yùn)算.

因?yàn)镕W編碼是有損的，所以為了能夠在編碼時(shí)對(duì)圖像質(zhì)量進(jìn)行控制，可以對(duì)(1)式中的誤差e設(shè)定上限閾值E，并且規(guī)定當(dāng)e＞E時(shí)，不再對(duì)樹進(jìn)行FW碼的近似存儲(chǔ)，而是直接儲(chǔ)其小波系數(shù).顯然，當(dāng)E充分大時(shí)，F(xiàn)W編碼將退化為小波編碼，但是編碼時(shí)間不會(huì)減少，因?yàn)樽顑?yōu)父樹的搜索是必需的.

FW的解碼是逐級(jí)迭代完成的.因?yàn)楦诘贘+1級(jí)子帶(u，v)處的父樹與根在第J級(jí)子帶(m，n)處的子樹具有相似性，因此可以使用下式從父樹中恢復(fù)子樹數(shù)據(jù)

J次迭代后，解碼完成.

2 并行化算法

計(jì)算統(tǒng)一設(shè)備架構(gòu)(compute unified device architecture，簡(jiǎn)稱CUDA)是通用GPU計(jì)算的一種技術(shù)規(guī)范，由NVidia公司于2007年提出.與傳統(tǒng)的通用GPU計(jì)算方式不同，在CUDA規(guī)范下，用戶可以用C或其他語(yǔ)言進(jìn)行自由的GPU編程，而不再需要調(diào)用圖形API.CUDA程序由在CPU上執(zhí)行的Host部分和在GPU上執(zhí)行的Device部分共同組成，其中，Host部分主要負(fù)責(zé)Host端資源(內(nèi)存)的分配與釋放、Device端資源(全局顯存、紋理顯存、共享顯存、寄存器)的分配與釋放、內(nèi)存與顯存之間數(shù)據(jù)的I/O;Device部分主要負(fù)責(zé)顯存中數(shù)據(jù)的計(jì)算、計(jì)算線程的同步.在Device中執(zhí)行的代碼稱為內(nèi)核(Kernal).基于CUDA的GPU編程模型如圖2所示.

圖2 基于CUDA的GPU編程模型Fig.2 The GPU programming model based on CUDA

從圖2可知，Device部分?jǐn)?shù)據(jù)并行處理在邏輯上是由眾多的線程(Thread)共同完成的，這些線程將各自處理顯存中數(shù)據(jù)的一小部分.CUDA中的線程是分級(jí)組織的:多個(gè)線程可以組成一個(gè)塊(Block)，多個(gè)塊又可以組成一個(gè)網(wǎng)格(Grid).一般情況下，一個(gè)網(wǎng)格就代表一個(gè)計(jì)算任務(wù).因?yàn)榫W(wǎng)格和塊可以在程序中定義成一維或多維(網(wǎng)格最多可定義為二維，塊最多可定義為三維)，所以在實(shí)際編程中，可根據(jù)需要對(duì)計(jì)算任務(wù)進(jìn)行自由的切割以方便程序的編寫.

由FW編碼原理可知，對(duì)圖像進(jìn)行編碼的實(shí)質(zhì)是為每棵根在第J級(jí)子帶處的子樹搜索一棵與其最為相似的父樹.為了加速這一過程，可以使用并行的方法，為所有的子樹同時(shí)進(jìn)行最優(yōu)父樹搜索.根據(jù)CUDA編程模型，作者提出的并行化的FW編碼算法如圖3所示.

圖3 并行FW編碼算法Fig.3 The parallelized version of FW encoding algorithm

在圖3中，每個(gè)子樹的編碼過程都由一個(gè)Device線程進(jìn)行處理.因?yàn)槊總€(gè)GPU核心只能同時(shí)運(yùn)行一個(gè)線程，所以GPU核心數(shù)量N越大，線程運(yùn)行的并發(fā)性就越好，總的編碼速度也就越快.可以證明，若一個(gè)算法中有P部分(0≤P≤1)可以做并行處理時(shí)，理想情況下的加速比為

在FW編碼中，因?yàn)樾〔ㄗ儞Q部分的計(jì)算量遠(yuǎn)小于編碼部分，所以P≈1，此時(shí)加速比可接近最大值N.考慮到當(dāng)今的主流GPU都具有數(shù)量眾多的核心，所以當(dāng)使用GPU代替CPU進(jìn)行編碼時(shí)，性能會(huì)有本質(zhì)上的提升.

3 實(shí)驗(yàn)

為驗(yàn)證該文算法的正確性和有效性，使用一幅512×512的標(biāo)準(zhǔn)測(cè)試圖像“Lena”，分別用CPU和GPU對(duì)其進(jìn)行FW編碼和解碼，并對(duì)解碼圖像和編碼時(shí)間進(jìn)行對(duì)比.其中FW編碼算法中的小波變換部分采用“sym4”小波，作4級(jí)變換，分形編碼部分誤差閾值E=200.程序開發(fā)環(huán)境為Visual C++2005，軟件運(yùn)行環(huán)境為32位Windows 7，內(nèi)存為4 GB.

圖4給出了分別使用CPU和GPU對(duì)測(cè)試圖像進(jìn)行編碼后的解碼圖像(50%的比例顯示)，其中PSNR=32.69.

圖4 FW解碼圖像Fig.4 FW decoded images

由圖4可知，采用GPU的解碼圖像和CPU的解碼圖像是一致的，這證明了GPU編碼的正確性.表1給出了不同規(guī)格GPU對(duì)測(cè)試圖像進(jìn)行編碼的時(shí)間，并與CPU的編碼時(shí)間進(jìn)行對(duì)比.其中編碼時(shí)間的計(jì)算從小波變換之后開始到FW碼由顯存拷貝回內(nèi)存后結(jié)束，運(yùn)行10次取最小值;CPU的計(jì)算時(shí)間為僅使用1顆核心時(shí)的結(jié)果.

表1 GPU與CPU的FW編碼時(shí)間對(duì)比Tab.1 The comparison of FW encoding time between GPU and CPU

由表1可見，采用GPU的編碼時(shí)間遠(yuǎn)小于CPU的編碼時(shí)間，因此采用GPU進(jìn)行FW編碼是快速有效的，且具有較高的實(shí)時(shí)性.

4 結(jié)束語(yǔ)

借助于GPU強(qiáng)大的計(jì)算能力，作者所提出的并行FW編碼方案可以在不降低圖像質(zhì)量的情況下，大幅減少編碼所需的時(shí)間，實(shí)現(xiàn)了圖像分形編碼的實(shí)時(shí)化，具有重要的實(shí)用價(jià)值.

［1］Davis G.A wavelet－based analysis of fractal image compression［J］.IEEE Trans on Image Processing，1998，7(2):141－154.

［2］Hyun J，Lickho S.A spectrum－based searching technique for the most favorable section of digital music［J］.IEEE Trans Consumer Electronics，2009，55(4):2122－2126.

［3］Lv J，Ye Z X，Zou Y R.Huber fractal image coding based on a fitting plane［J］.IEEE Trans on Image Processing，2013，22(1):134－145.

［4］馮娜.基于GPU的檔案數(shù)據(jù)庫(kù)應(yīng)用研究［J］.武漢理工大學(xué)學(xué)報(bào)，2011，33(6):148－151.

［5］Chen Y W.Fast virus signature matching based on the high performance computing of GPU［C］∥IEEE International Conference on Communication Software and Networks，2010:513－515.

［6］楊正龍，金林，李蔚清.基于GPU的圖形電磁計(jì)算加速算法［J］.電子學(xué)報(bào)，2007，35(6):1056－1060.

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

［8］Barnsley M F，Sloan A D.A better way to compress images byte［M］.McGraw－Hill:Inc Hightstown NJ USA，1988:215－223.

［9］Jacqain A E.A novel frctal block－coding technique for digital image［C］∥IEEE International Conference on Acoustics，Speech，and Signal Processing，1990:2225－2228.

［10］Wohlberg B，Jager B D.A review of the fractal image coding literature［J］.IEEE Trans on Image Processing，1999，8(12):1716－1729.

［11］趙健，雷蕾，蒲小勤.分形理論及其在信號(hào)處理中的應(yīng)用［M］.北京:清華大學(xué)出版社，2008:57－75.