基于GPU并行處理的圖像快速旋轉(zhuǎn)算法

李亞榮，劉佳

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

0 引言

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

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

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

1.1 直接旋轉(zhuǎn)法

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

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

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

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

1.2 三步分解法

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

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

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

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

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

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

2 基于GPU并行處理算法

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

2.1 Bresenham劃線算法原理

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

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

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

(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不變.

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

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

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

圖4 Bresenham算法原理圖

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

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

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

3 實驗結(jié)果與結(jié)論

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

附表 三種算法在處理時間上的比較

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

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

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

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

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

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

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

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

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

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

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