基于SURF與GPU加速數(shù)字圖像處理

周亮君， 肖世德， 李晟堯， 譚芳喜

(西南交通大學(xué) 機(jī)械工程學(xué)院，四川 成都 610031)

0 引 言

在現(xiàn)今信息化時(shí)代，互聯(lián)網(wǎng)給人們帶來(lái)了便利的同時(shí)，為應(yīng)對(duì)復(fù)雜多變的社會(huì)監(jiān)測(cè)環(huán)境，故對(duì)數(shù)字圖像處理速度提出了更高要求。隨著圖像處理器(graphic processing unit,GPU)的內(nèi)核數(shù)量和存儲(chǔ)帶寬的急速增長(zhǎng)，使得其非常適合大規(guī)模的并行運(yùn)算[1]，就浮點(diǎn)數(shù)的運(yùn)算速度來(lái)說(shuō)，GPU是中央處理器(CPU)的幾倍，甚至更快。2006年末，NVIDIA GeForce 8800的浮點(diǎn)運(yùn)算數(shù)達(dá)到520 GFlops，而Intel雙核64位CPU僅為32 GFlops。現(xiàn)在單純的依靠CPU進(jìn)行圖像運(yùn)算處理，運(yùn)行速度較慢。Lowe D G提出SIFT算法，檢測(cè)圖像的局部特征，接著Bay H首次提出了比SIFT算法快幾倍的SURF算法[2]，利用SURF特征的快速響應(yīng)和GPU強(qiáng)大的浮點(diǎn)運(yùn)算功能，通過(guò)GPU和CPU的并行運(yùn)算處理，提高圖像的特征檢測(cè)速度。

本文提出基于SURF與GPU加速數(shù)字圖像處理方案，并通過(guò)實(shí)驗(yàn)驗(yàn)證所提方案的可行性。實(shí)驗(yàn)結(jié)果表明本方案能夠提高圖像特征檢測(cè)的速度。

1 SURF特征檢測(cè)算法的基本原理

1.1 特征點(diǎn)檢測(cè)

SURF特征檢測(cè)算法主要由4個(gè)部分構(gòu)成，分別是特征點(diǎn)檢測(cè)、特征點(diǎn)的精確定位、特征點(diǎn)的主方向確定以及特征點(diǎn)的匹配[3]。SURF算法通過(guò)近似Hessian矩陣的方法來(lái)檢測(cè)圖像關(guān)鍵點(diǎn)，利用Hessian矩陣求解函數(shù)的局部曲率，其行列式表示曲率的大小，在局部曲率的大小在尺度域和空間域達(dá)到極小值或極大值時(shí)，判斷該處的像素點(diǎn)為圖像的特征點(diǎn)。

特征點(diǎn)的檢測(cè)過(guò)程首先需要建立高斯尺度空間，且選取的特征點(diǎn)在尺度域內(nèi)具有無(wú)關(guān)性，故在尺度域內(nèi)構(gòu)造Hessian矩陣前，需對(duì)圖像進(jìn)行高斯濾波處理。圖像的尺度空間表示圖像I與二維高斯函數(shù)G進(jìn)行卷積的結(jié)果。表示為

L(x,σ)=G(σ)*I(x,σ)

(1)

圖像I中任意一點(diǎn)P(x,y)在尺度上的Hessian矩陣σ表示為

(2)

(3)

Lxy(x,σ),Lyy(x,σ)的含義類似。通過(guò)動(dòng)態(tài)調(diào)整參數(shù)σ的大小得到表征尺度空間的高斯金字塔。

1.2 特征點(diǎn)定位

由于DOG算子會(huì)產(chǎn)生邊緣響應(yīng)，檢測(cè)的特征點(diǎn)是離散空間的極值點(diǎn)，不是真正的極值點(diǎn)，故利用子像素插值法對(duì)特征點(diǎn)進(jìn)行精確定位。尺度空間函數(shù)L(x,σ)在極值點(diǎn)X0=(x0,σ0)處的泰勒展開式為

(4)

對(duì)上式求導(dǎo)得到極值點(diǎn)Xmax

(5)

如果|L(Xmax)|>0.03，則保留該特征點(diǎn)，同時(shí)獲取該特征點(diǎn)的準(zhǔn)確尺度和位置信息。

1.3 特征點(diǎn)主方向確定

在特征點(diǎn)中心的領(lǐng)域進(jìn)行采樣，利用梯度直方圖統(tǒng)計(jì)鄰域內(nèi)像素的梯度方向?qū)?yīng)的幅值大小，將360°分為12個(gè)柱，每30°一個(gè)，直方圖的主峰代表的方向，即為該特征點(diǎn)的主方向。

1.4 特征點(diǎn)匹配

采用歐氏距離d作為判斷特征點(diǎn)的匹配程度。操作過(guò)程為：在基準(zhǔn)圖像中選取特征點(diǎn)P，在目標(biāo)圖像中計(jì)算得出歐氏距離最近的兩個(gè)特征點(diǎn)，分別記為Q1，Q2對(duì)應(yīng)的歐氏距離為d1，d2。如果d1,d2的比值小于設(shè)定的閾值f,則認(rèn)為本次匹配過(guò)程有效，選取歐氏距離最小的點(diǎn)作為匹配結(jié)果；如果d1,d2的比值大于設(shè)定的閾值f，則本次匹配過(guò)程無(wú)效，進(jìn)行下一個(gè)特征點(diǎn)的匹配。

2 基于SURF與GPU數(shù)字圖像相關(guān)方法

2.1 基于GPU圖像特征提取

在計(jì)算機(jī)系統(tǒng)中，CPU主要負(fù)責(zé)復(fù)雜的算法邏輯與控制，而GPU[4]相較于CPU具有更加強(qiáng)大的計(jì)算能力，尤其大規(guī)模的并行浮點(diǎn)運(yùn)算。伴隨GPU的高度并行、可編程化的實(shí)現(xiàn)，在SURF算法中合理使用CPU端和GPU端的資源，可以提升圖像的運(yùn)算速度。

本文提出一種基于SURF與GPU加速數(shù)字圖像處理方案。在并行計(jì)算過(guò)程中，GPU執(zhí)行整個(gè)程序中的計(jì)算密集型的模塊。完成圖像的積分、Hessian矩陣行列式計(jì)算、構(gòu)造多尺度空間、特征點(diǎn)和特征點(diǎn)方向計(jì)算并生成特征點(diǎn)描述子[5,6]。在SURF算法中合理利用GPU的計(jì)算優(yōu)勢(shì)，提高圖像檢測(cè)速度。基于GPU的SURF特征提取流程如圖1所示。

圖1 算法流程框圖

2.2 積分圖像計(jì)算

為提高GPU并行圖像積分的運(yùn)算速度，可以通過(guò)構(gòu)造多層掃描數(shù)據(jù)前來(lái)實(shí)現(xiàn)前綴加法。并在前綴加法中引入分段的方式，降低線程間存在高度的數(shù)據(jù)依賴。充分利用GPU強(qiáng)大的浮點(diǎn)運(yùn)算能力。

對(duì)于一個(gè)數(shù)組a(x)，進(jìn)行前綴加法的輸出結(jié)果b(x)表示為

(6)

對(duì)于圖像I(x,y)，其積分圖像S(x,y)可表示為

(7)

(8)

設(shè)一幅輸入圖像的行尺寸大小表示為M×kN(如果圖像行尺寸不是N的整數(shù)倍，則將其擴(kuò)展為N的整數(shù)倍)，令Sx(-1,y)=0，則Sx(x,y)表示為

(9)

故行前綴加法可以通過(guò)分段的方式完成，式(9)右邊第一項(xiàng)為所處理的數(shù)據(jù)段的前面所有段的像素和，第二項(xiàng)為處理的數(shù)據(jù)段的前綴加法結(jié)果。故所求解數(shù)據(jù)的前綴加法被分成三段完成。原理如圖2所示。

圖2 前綴加法示意

2.3 構(gòu)造多尺度空間

根據(jù)目標(biāo)的原始圖像尺度空間的組數(shù)和每組層數(shù)來(lái)構(gòu)造尺度空間，分配線程對(duì)每一個(gè)像素點(diǎn)進(jìn)行計(jì)算。以并行的方式計(jì)算像素點(diǎn)的x方向，y方向和xy方向?yàn)V波卷積值，計(jì)算結(jié)果記為Dxx,Dxy,Dyy。由式(10)計(jì)算得到其尺度空間所對(duì)應(yīng)的Hessian的矩陣行列式值

det(H)=DxxDyy-(ωDxy)2

(10)

并行計(jì)算的實(shí)現(xiàn)過(guò)程如圖3所示。

圖3 并行計(jì)算流程框圖

2.4 確定主方向并生成特征點(diǎn)描述子

為保證特征算子的旋轉(zhuǎn)不變特性，需要為特征點(diǎn)賦予主方向[7]。首先將尺度空間中每一個(gè)尺度對(duì)應(yīng)的圖像加載到共享內(nèi)存區(qū)中，再將每個(gè)特征點(diǎn)的計(jì)算置于GPU的一個(gè)線程中，將每一層圖像放在一個(gè)核函數(shù)中計(jì)算。為避免線程塊在計(jì)算過(guò)程中去判斷區(qū)域能否符合運(yùn)算要求，將所選取區(qū)域超過(guò)圖像有效像素邊界的無(wú)效區(qū)域的像素點(diǎn)的灰度值賦值為0。

通過(guò)調(diào)用核函數(shù)統(tǒng)計(jì)所有關(guān)鍵點(diǎn)對(duì)應(yīng)的Haar小波值[8]。依據(jù)關(guān)鍵點(diǎn)的位置，在核函數(shù)內(nèi)部對(duì)Haar小波值進(jìn)行分塊統(tǒng)計(jì)。選取關(guān)鍵點(diǎn)為圓心，以關(guān)鍵點(diǎn)所對(duì)應(yīng)尺度的倍數(shù)為半徑的圓形鄰域，將鄰域劃分至n個(gè)扇形，利用高斯函數(shù)進(jìn)行加權(quán)，得到每個(gè)扇形所包含的圖像點(diǎn)的Haar小波值。將扇形區(qū)域環(huán)繞一周所獲取關(guān)鍵點(diǎn)的Haar小波值進(jìn)行比較，取最大的Haar值，其對(duì)應(yīng)的方向?yàn)樵撎卣鼽c(diǎn)所對(duì)應(yīng)的方向。

為得到特征點(diǎn)描述子，首先確定以特征點(diǎn)為中心的正方形鄰域，分配一個(gè)線程計(jì)算一個(gè)關(guān)鍵點(diǎn)描述子，得到鄰域內(nèi)像素點(diǎn)的Haar小波響應(yīng)值；將圖像數(shù)據(jù)傳至共享區(qū)域，加快線程塊對(duì)數(shù)據(jù)訪問(wèn)的速度；并得到與關(guān)鍵點(diǎn)相對(duì)應(yīng)的64維的描述子特征向量，將描述子特征向量數(shù)據(jù)儲(chǔ)存在全局內(nèi)存中，從而獲得圖像所有的特征點(diǎn)描述子。

3 實(shí)驗(yàn)結(jié)果分析

為準(zhǔn)確評(píng)估基于SURF與GPU加速的數(shù)字圖像特征檢測(cè)方案對(duì)數(shù)字圖像特征檢測(cè)速度的提升，本文進(jìn)行了傳統(tǒng)SURF特征檢測(cè)算法與GPU加速特征檢測(cè)算法的實(shí)驗(yàn)比較。當(dāng)前集成的開發(fā)環(huán)境為Visual Stdio 2015,并以CUDA Toolkit 3.4.3及NVIDIA GPU Computing SDK作為開發(fā)工具，實(shí)驗(yàn)開發(fā)詳細(xì)環(huán)境配置:GPU為NVIDIA GeFore GTX 960 M，GPU Memory為4GB，CPU為Inter?CoreTMi5—6300HQ，CPU Memory為4GB，CUDA Toolkit為v3.4.3。

表1列出不同分辨率圖像的檢測(cè)結(jié)果，(每組圖片集為500張，時(shí)間為圖像檢測(cè)的平均耗時(shí))可以得出，基于GPU的數(shù)字圖像特征檢測(cè)速度遠(yuǎn)遠(yuǎn)高于普通CPU圖像特征檢測(cè)速度。隨著圖像分辨率的提高，GPU對(duì)圖像特征檢測(cè)速度的提高越明顯。由于受到硬件資源等條件的限制，如共享內(nèi)存，以及圖像特征點(diǎn)數(shù)量都對(duì)特征檢測(cè)速度有影響。由于在本實(shí)驗(yàn)中，線程塊設(shè)置的線程較小，若能確保GPU被足夠的活動(dòng)線程填充，發(fā)揮GPU并行運(yùn)算能力，可以更大地提高特征檢測(cè)速度。

表1 特征檢測(cè)速度對(duì)比

4 結(jié) 論

本文提出的基于SURF和GPU的加速數(shù)字圖像特征檢測(cè)方案，結(jié)合GPU強(qiáng)大的浮點(diǎn)運(yùn)算能力，以部分冗余計(jì)算增加為代價(jià)，降低數(shù)據(jù)之間的依賴，優(yōu)化內(nèi)存的訪問(wèn)，明顯提高了特征檢測(cè)的速度。本文提出的方案，較基于傳統(tǒng)的SURF特征檢測(cè)方案，能提高特征檢測(cè)速度至少5倍。通過(guò)實(shí)驗(yàn)驗(yàn)證了其方案的有效性，為進(jìn)一步提高數(shù)字圖像處理速度提供依據(jù)。