基于GPU并行處理的圖像快速旋轉算法

李亞榮，劉佳

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

0 引言

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

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

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

1.1 直接旋轉法

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

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

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

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

1.2 三步分解法

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

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

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

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

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

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

2 基于GPU并行處理算法

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

2.1 Bresenham劃線算法原理

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

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

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

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

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

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

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

圖4 Bresenham算法原理圖

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

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

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

3 實驗結果與結論

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

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

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

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

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

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

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

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

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

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

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

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

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