李亞榮，劉佳

(大連交通大學(xué) 機(jī)械工程學(xué)院，遼寧 大連 116028)

0 引言

圖形處理器(GPU)，其概念相對(duì)于CPU，是一種專門用于處理圖像的核心處理器.隨著GPU性能的提升，并且GPU可編程操作，它廣泛用于繁瑣復(fù)雜的計(jì)算領(lǐng)域中，如圖像和視頻處理、計(jì)算生物學(xué)和化學(xué)、流體力學(xué)模擬、CT圖像再現(xiàn)、光線跟蹤等.特別是GPU在并行加速方面所具備的優(yōu)勢(shì)體現(xiàn)在［1］:①大量的并發(fā)式線程，②極高的運(yùn)算密度，③顯存的快速訪問(wèn)，④低數(shù)據(jù)耦合.因此加速計(jì)算方法正在從CPU“中央處理”向CPU與GPU“協(xié)同處理”的方向發(fā)展.為了實(shí)現(xiàn)協(xié)同處理的計(jì)算模式，NVIDIA公司發(fā)明了一致CUDA并行計(jì)算架構(gòu).該架構(gòu)利用GPU的并行處理能力，可大幅度提升計(jì)算性能.

圖形旋轉(zhuǎn)是數(shù)字圖像處理中常見(jiàn)的算法.傳統(tǒng)的旋轉(zhuǎn)算法中，CPU承擔(dān)了所有的數(shù)值計(jì)算，當(dāng)需要處理的圖形達(dá)到幾十或者上百兆時(shí)，CPU會(huì)耗費(fèi)大量的計(jì)算時(shí)間，且為了保證圖形的處理質(zhì)量和精度，相對(duì)的會(huì)增加CPU的負(fù)荷，影響其它線程的運(yùn)行.而普通的并行運(yùn)算不僅硬件成本高，且原有的旋轉(zhuǎn)算法無(wú)法適應(yīng)并行運(yùn)算的架構(gòu)，因此，基于CUDA架構(gòu)并行處理的圖形旋轉(zhuǎn)算法具有十分重要的意義，它將圖形旋轉(zhuǎn)繁瑣的計(jì)算從CPU轉(zhuǎn)移到GPU，利用GPU的強(qiáng)大性能極大地加快運(yùn)行的速度.

1 現(xiàn)有的圖像旋轉(zhuǎn)算法及其特點(diǎn)

1.1 直接旋轉(zhuǎn)法

笛卡爾坐標(biāo)系中，將一個(gè)圖像繞著坐標(biāo)軸順時(shí)針旋轉(zhuǎn)α角度后，圖1所示為旋轉(zhuǎn)之前的圖像，圖2為旋轉(zhuǎn)之后的圖像，二者的坐標(biāo)和旋轉(zhuǎn)角度具有一定幾何關(guān)系.

假設(shè)用(x0，y0)表示一幅xoy坐標(biāo)系下的數(shù)字圖像中的任意點(diǎn)，(x'，y')為(x0，y0)旋轉(zhuǎn)α角度后圖像對(duì)應(yīng)點(diǎn).那么 (x，y)與(x'，y')有如下的關(guān)系式:

因?yàn)閳D像在旋轉(zhuǎn)過(guò)程中引入三角函數(shù)sina，cosa值，這些值均為小于1的浮點(diǎn)數(shù)，而圖像的坐標(biāo)值只能為整數(shù)，因此很多點(diǎn)坐標(biāo)需強(qiáng)制取整.這樣很多像素取整后精度不夠，即如果采用直接發(fā)由原始圖像的各個(gè)像點(diǎn)對(duì)應(yīng)到旋轉(zhuǎn)后的圖像像點(diǎn)，會(huì)造成圖像的空洞.為了避免空洞，采取反向逆推法來(lái)求旋轉(zhuǎn)后的點(diǎn).即根據(jù)式(1)的逆運(yùn)算公式求出原始圖像.但是旋轉(zhuǎn)圖像和原始圖像不是一一對(duì)應(yīng)的映射關(guān)系，反向旋轉(zhuǎn)方法求取的像素大多亦為浮點(diǎn)型［1］，因此需要根據(jù)插值的方法來(lái)確定具體的像素值.

一般采用的插值法為最近鄰插值算法［2］、線性插值算法［3］和高階插值算法［4］.由(1)式可知，直接法效率低，它對(duì)每個(gè)像素點(diǎn)進(jìn)行后向映射和插值，并會(huì)產(chǎn)生大量的浮點(diǎn)取整運(yùn)算，一次浮點(diǎn)數(shù)轉(zhuǎn)化到整數(shù)的取整運(yùn)算的時(shí)間開銷很大，約為1次浮點(diǎn)數(shù)乘法開銷的10倍［5］，因此會(huì)增加CPU運(yùn)算時(shí)間.

1.2 三步分解法

使用直接法計(jì)算圖像旋轉(zhuǎn)α角時(shí)，例如處理一幅大小為N×N的圖像，由式(1)和式(2)可知需要4N2次浮點(diǎn)乘法以及2N2次浮點(diǎn)加法.由于浮點(diǎn)數(shù)的加法和乘法計(jì)算以及取整運(yùn)算增加CPU運(yùn)算時(shí)間，所以當(dāng)N較大時(shí)，算法的運(yùn)行速度非常緩慢.因此根據(jù)圖像的錯(cuò)切［6］原理對(duì)于直接法進(jìn)行優(yōu)化得到新的算法——三步分解法.它提高了圖像的旋轉(zhuǎn)速度.三步分解法的基本原理如下:

根據(jù)矩陣變換的基本原理對(duì)于旋轉(zhuǎn)矩陣R做如下變換:

根據(jù)矩陣變換公式得到

根據(jù)上述變換，矩陣R被分解成三個(gè)矩陣相乘.由于數(shù)字圖像處理在實(shí)現(xiàn)過(guò)程中多采用逆向映射法，因此對(duì)式(3)求逆矩陣得到了R逆矩陣R－1，可以得出三步法實(shí)現(xiàn)圖像旋轉(zhuǎn)的步驟如下圖3所示.

圖3 三步分解法實(shí)現(xiàn)的圖像旋轉(zhuǎn)

通過(guò)分析，在理論上三步法把直接法的o(n2)次取整運(yùn)算簡(jiǎn)化到o(n)次，其效率優(yōu)于直接法，減少了CPU的運(yùn)行時(shí)間，但存在以下問(wèn)題:①經(jīng)過(guò)幾次矩陣相乘(即平移計(jì)算)，每次變換都進(jìn)行插值，因此旋轉(zhuǎn)后的圖像精度會(huì)受到很大影響.②處理像素很高的圖像時(shí)，三步法處理緩慢，在性能上仍具有缺陷.

2 基于GPU并行處理算法

分析以上兩種傳統(tǒng)旋轉(zhuǎn)方法后，可見(jiàn)圖像旋轉(zhuǎn)算法性能的提升需要達(dá)到算法精度與時(shí)間復(fù)雜度兩者的相互平衡.為了解決上述兩種算法中的運(yùn)算時(shí)間長(zhǎng)、精度不高的問(wèn)題，本文提出一種新的圖像快速旋轉(zhuǎn)算法來(lái)達(dá)到兩者之間的平衡.該算法基于CUDA架構(gòu)，且使用Bresenham畫線算法在處理計(jì)算機(jī)繪制直線等基本圖形元素時(shí)，可以避免大量的浮點(diǎn)及取整運(yùn)算.

2.1 Bresenham劃線算法原理

Bresenham算法采用遞推步進(jìn)的方法，即令每次變化方向的坐標(biāo)步進(jìn)一個(gè)像素，同時(shí)另一個(gè)方向的坐標(biāo)依據(jù)誤差判別式的符號(hào)來(lái)決定是否要步進(jìn)一個(gè)像素［7］.圖4可見(jiàn)，下一個(gè)最近鄰像素處于當(dāng)前像素的八領(lǐng)域［8］中.設(shè)當(dāng)前映射點(diǎn)為(x1，y1)，由式(1)可知，下一個(gè)映射點(diǎn)

所有的映射點(diǎn)都在同一條直線上.設(shè)距離(x2，y2)最近的像素點(diǎn)為(m2，n2)，根據(jù)最近鄰像素八領(lǐng)域原理得出下一個(gè)與前一個(gè)像素點(diǎn)的關(guān)系為:素點(diǎn)保持不變且像素點(diǎn)向前偏移一個(gè)單位［9］.

為了確定下一個(gè)像素點(diǎn)的位置，需引入Bresenham算法中誤差項(xiàng).記錄映射點(diǎn)與最近鄰接點(diǎn)之間的誤差，定義x和y方向的誤差為:mx=xm，my=y－n.更新為下一個(gè)鄰結(jié)點(diǎn)時(shí)，首先需更新誤差項(xiàng):

(1)mx＞ 0.5，x ～ 0，mx=mx－1

(2)mx＜ 0.5，m 不變.

(3)my＜ －0.5，n=n+1，my=my－1

(4)my＞ －0.5，n不變.

此算法避免了大量的浮點(diǎn)乘法和取整運(yùn)算，只需判別誤差項(xiàng)即可定位最近領(lǐng)近像素點(diǎn)，減少了運(yùn)算量.基于Bresnham畫線算法的圖像旋轉(zhuǎn)算法如下:

(1)原有圖像尺寸大小為(h0，w0)，根據(jù)旋轉(zhuǎn)的角度a值得到新的圖像尺寸為(h1，w1).

(2)根據(jù)Bresenham算法原理開始計(jì)算每行每一個(gè)點(diǎn)的后向映射點(diǎn)的精確位置.

圖4 Bresenham算法原理圖

2.2 CUDA并行庫(kù)優(yōu)化

現(xiàn)使用CUDA并行庫(kù)對(duì)Bresenham旋轉(zhuǎn)算法中雙層循環(huán)進(jìn)行優(yōu)化.GPU進(jìn)行并行計(jì)算會(huì)加快算法旋轉(zhuǎn)的速度.圖5為CUDA架構(gòu)的編程模型.

由圖5可知，一個(gè)內(nèi)核中存在著兩個(gè)層次的并行，即網(wǎng)格中的塊之間的并行以及塊之間的線程并行.每個(gè)網(wǎng)格有若干個(gè)線程塊組成，而每個(gè)線程塊由若干個(gè)線程組成.內(nèi)核以網(wǎng)格為單位執(zhí)行并行，各網(wǎng)格之間是并行的.網(wǎng)格間無(wú)法通信，但是同一網(wǎng)格間的Thread可以通信.采用這種編程模式，既可以運(yùn)行單個(gè)線程塊的程序，又可以運(yùn)行上百個(gè)線程塊的程序.這樣可以將基于Bresenham算法的圖像旋轉(zhuǎn)算法進(jìn)行并行化.在CUDA中，一個(gè)線程塊中的線程最多只能有512個(gè)，為了提高并行性，可以增加線程塊的數(shù)量，這樣會(huì)有更多的線程參與運(yùn)算.設(shè)此時(shí)圖片大小為w1×h1，令DATA_SIZE=w1×h1，所以每個(gè)線程處理的元素個(gè)數(shù)為DATA_SIZE/(blocks_num*threads_num).顯卡的內(nèi)存是DRAM，因此最有效率的存取方式是以連續(xù)方式進(jìn)行存取.此時(shí)線程0讀取第一個(gè)數(shù)字，線程1讀取第二個(gè)數(shù)字，依此類推.所以，將原有的程序進(jìn)行修改，每個(gè)線程處理圖片的一部分，類似的原理如圖6所示，此時(shí)將圖片實(shí)現(xiàn)邏輯上的分塊，每一塊線程處理圖片的一部分，根據(jù)GPU的體系結(jié)構(gòu)，大量的線程可以并發(fā)執(zhí)行，極大地提高了運(yùn)行速度.當(dāng)所有線程運(yùn)行完畢后，從顯存中拷貝數(shù)據(jù)回內(nèi)存即可得到結(jié)果.

3 實(shí)驗(yàn)結(jié)果與結(jié)論

本實(shí)驗(yàn)平臺(tái)為 Intel core Duo E6700，4GB RAM，GeForce GTX 560 Ti，操作系統(tǒng)是32位Windows XP.CUDA工具包版本為3.2.分別使用上述三種算法測(cè)試不同大小圖像的旋轉(zhuǎn)處理所花費(fèi)的時(shí)間，其結(jié)果如附表所示(處理時(shí)間不包括主存與顯存間的數(shù)據(jù)傳輸時(shí)間).時(shí)間單位:ms，圖像數(shù)據(jù)大小以字節(jié)為單位.

附表 三種算法在處理時(shí)間上的比較

由實(shí)驗(yàn)數(shù)據(jù)可知，圖片越大，直接法和三步法耗時(shí)越長(zhǎng)，無(wú)法滿足圖像實(shí)時(shí)處理方面的性能要求，而CUDA的加速性能卻越明顯;對(duì)于較小的圖片，CUDA加速性能與其它兩種算法性能相近.在GPU上使用CUDA架構(gòu)實(shí)現(xiàn)算法的并行設(shè)計(jì)簡(jiǎn)單，關(guān)鍵需知道算法的哪些部分可使用GPU進(jìn)行并行化處理.本論文中圖像旋轉(zhuǎn)屬于像素級(jí)［10］操作，因此圖像旋轉(zhuǎn)算法進(jìn)行并行化優(yōu)化較易實(shí)現(xiàn)，性能也得到極大的提升.即使用GPU的并行處理具有明顯的優(yōu)勢(shì).

［1］胡海濤，平子良，吳斌.具有旋轉(zhuǎn)不變性的圖像矩的快速算法［J］.光學(xué)學(xué)報(bào)，2010，30(2):394-398.

［2］劉鑫，姜超，馮存永，等.基于CUDA和OpenCV的圖像并行處理方法研究［J］.測(cè)繪科學(xué)，2011，20(1):178-181.

［3］梁娟娟，任開新，郭利財(cái)，等.CPU上的矩陣乘法的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20(1):178-181.

［4］劉耀林，邱飛岳，王麗萍.基于GPU的圖像快速旋轉(zhuǎn)算法的研究及實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與科學(xué)，2008，30(6):48-51.

［5］陳芳.圖像旋轉(zhuǎn)插值算法和基于鏈碼技術(shù)計(jì)算圖像幾何矩的算法研究［D］.上海:華東師范大學(xué)，2006.

［6］王濱海，許正飛，陳西廣，等.圖像旋轉(zhuǎn)算法的分析與對(duì)比［J］.光學(xué)與光電技術(shù)，2011，30(6):46-49.

［7］石慎，張艷寧，郗潤(rùn)平，等.基于Bresenham畫線算法的圖像快速－高精度旋轉(zhuǎn)算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，19(11):1381-1397.

［8］RAFAEL C GONZALEZ，RACHARD E Woods.岡薩雷斯數(shù)字圖像處理［M］.北京:電子工業(yè)出版社，2009:51-55.

［9］孫勇國(guó)，文必龍，巴鈾.機(jī)械工程圖圖像快速旋轉(zhuǎn)算法［J］.哈爾濱科學(xué)技術(shù)大學(xué)學(xué)報(bào)，1996，30(6):21-26.

［10］蓋素麗.基于GPU的數(shù)字圖像并行處理方法［J］.電子產(chǎn)品世界，2009，30(6):39-40.