基于OpenCL的尺度不變特征變換算法的并行設(shè)計(jì)與實(shí)現(xiàn)

許川佩 王光

摘要：針對(duì)尺度不變特征變換（SIFT）算法實(shí)時(shí)性差的問(wèn)題，提出了利用開(kāi)放式計(jì)算語(yǔ)言（OpenCL）并行優(yōu)化的SIFT算法。首先，通過(guò)對(duì)原算法各步驟進(jìn)行組合拆分、重構(gòu)特征點(diǎn)在內(nèi)存中的數(shù)據(jù)索引等方式對(duì)原算法進(jìn)行并行化重構(gòu)，使得算法的中間計(jì)算結(jié)果能夠完全在顯存中完成交互；然后，采用復(fù)用全局內(nèi)存對(duì)象、共享局部?jī)?nèi)存、優(yōu)化內(nèi)存讀取等策略對(duì)原算法各步驟進(jìn)行并行設(shè)計(jì)，提高數(shù)據(jù)讀取效率，降低傳輸延時(shí)；最后，利用OpenCL語(yǔ)言在圖形處理單元（GPU）上實(shí)現(xiàn)了SIFT算法的細(xì)粒度并行加速，并在中央處理器（CPU）上完成了移植。與原SIFT算法配準(zhǔn)效果相近時(shí)，并行化的算法在GPU和CPU平臺(tái)上特征提取速度分別提升了10.51～19.33和2.34～4.74倍。實(shí)驗(yàn)結(jié)果表明，利用OpenCL并行加速的SIFT算法能夠有效提高圖像配準(zhǔn)的實(shí)時(shí)性，并能克服統(tǒng)一計(jì)算設(shè)備架構(gòu)（CUDA）因移植困難而不能充分利用異構(gòu)系統(tǒng)中多種計(jì)算核心的缺點(diǎn)。

關(guān)鍵詞：

尺度不變特征變換算法；開(kāi)放式計(jì)算語(yǔ)言；復(fù)用內(nèi)存對(duì)象；細(xì)粒度并行；異構(gòu)系統(tǒng)

中圖分類(lèi)號(hào)： TP391.4 文獻(xiàn)標(biāo)志碼：A

0引言

以尺度不變特征變換（Scale Invariant Feature Transform， SIFT）算法[1]為代表的基于特征的圖像匹配方法近幾年發(fā)展迅速，該算法對(duì)光照、角度或尺度變化的圖像都有較好的匹配精度和適應(yīng)性，但實(shí)時(shí)性差。為了提高實(shí)時(shí)性，在此基礎(chǔ)上又衍生出了主成分分析（Principal Component Analysis， PCA）SIFT[2]、快速魯棒特征（Speed Up Robust Feature， SURF）檢測(cè)[3]等改進(jìn)算法。這些改進(jìn)的算法盡管在速度方面有所提升，但實(shí)時(shí)性仍然不能滿足實(shí)際應(yīng)用要求且在抗尺度和抗旋轉(zhuǎn)方面性能都有不同程度的下降，因此仍無(wú)法取代經(jīng)典的SIFT算法[4]。

近年來(lái)隨著圖形處理器（Graphics Processing Unit， GPU）計(jì)算能力的不斷提升，利用GPU天然硬件并行的特性來(lái)加速非圖形通用大規(guī)模運(yùn)算逐漸受到人們的青睞，目前較為成熟并得到廣泛應(yīng)用的GPU并行編程模型為英偉達(dá)（NVIDIA）公司開(kāi)發(fā)的統(tǒng)一計(jì)算設(shè)備架構(gòu)（Compute Unified Device Architecture， CUDA）模型。文獻(xiàn)[5-7]利用CUDA實(shí)現(xiàn)了SIFT算法關(guān)鍵步驟的GPU并行加速，取得了一定的加速效果。文獻(xiàn)[8-9]在移動(dòng)GPU平臺(tái)上利用開(kāi)放式計(jì)算語(yǔ)言（Open Computing Language， OpenCL）實(shí)現(xiàn)了SIFT算法的并行加速，相對(duì)于移動(dòng)中央處理器（Central Processing Unit， CPU）取得了4.6～7.8倍的加速效果。另外，完成同樣的計(jì)算，GPU比CPU的功耗低87%，即利用OpenCL實(shí)現(xiàn)的GPU并行運(yùn)算相對(duì)于傳統(tǒng)的CPU具有更高的性能功耗比，但以上方法大多采用步驟分離的優(yōu)化，沒(méi)能充分利用GPU全局內(nèi)存以及算法各步驟的中間計(jì)算結(jié)果，加速效果受顯存帶寬的制約。

另外利用CUDA實(shí)現(xiàn)的算法只適用于NVIDIA顯卡，移植困難，而目前的計(jì)算機(jī)系統(tǒng)大多是“CPU+協(xié)處理器”的異構(gòu)系統(tǒng)[10]，這使得CUDA無(wú)法充分利用異構(gòu)系統(tǒng)中不同類(lèi)型的計(jì)算核心。具有跨平臺(tái)特性的開(kāi)放式并行編程語(yǔ)言O(shè)penCL的出現(xiàn)為解決此問(wèn)題提供了契機(jī)，利用OpenCL設(shè)計(jì)的并行算法能夠在CPU+（GPU、數(shù)字信號(hào)處理器（Digital Signal Processor， DSP）、現(xiàn)場(chǎng)可編程門(mén)陣列（FieldProgrammable Gate Array， FPGA）等異構(gòu)系統(tǒng)間移植[11-12]，該特性使得經(jīng)OpenCL優(yōu)化的算法能夠擺脫對(duì)硬件平臺(tái)的依賴(lài)。自2010年OpenCL1.1發(fā)布以來(lái)，對(duì)OpenCL技術(shù)的應(yīng)用研究逐漸興起。陳鋼等[13]對(duì)OpenCL內(nèi)存操作作了深入的分析；Yan等[14]利用OpenCL實(shí)現(xiàn)了SURF算法的并行加速。OpenCL編程相比CUDA更為復(fù)雜[15]，在軟件開(kāi)發(fā)方面也面臨更多的挑戰(zhàn)和困難，目前在PC平臺(tái)上還沒(méi)有利用OpenCL并行優(yōu)化的SIFT算法出現(xiàn)。

針對(duì)以上問(wèn)題，本文對(duì)SIFT算法步驟及數(shù)據(jù)索引方式進(jìn)行重構(gòu)，提高其并行度，然后通過(guò)優(yōu)化內(nèi)存讀取、合理利用OpenCL內(nèi)存層次等策略對(duì)該算法進(jìn)一步優(yōu)化，在NVIDIA GPU平臺(tái)上實(shí)現(xiàn)了SIFT特征的快速提取。為研究OpenCL的可移植性，將優(yōu)化的GPU版本移植到Intel雙核CPU平臺(tái)上，實(shí)驗(yàn)表明優(yōu)化后的算法在兩種計(jì)算平臺(tái)上的實(shí)時(shí)性都有一定提升。

1SIFT特征提取算法流程

SIFT算法最早由Lowe[1]在1999年提出并于2004年完善，由于其良好的匹配特性，目前已得到廣泛研究與應(yīng)用。SIFT特征點(diǎn)提取實(shí)質(zhì)是在不同尺度空間上查找關(guān)鍵點(diǎn)（特征點(diǎn)），算法基本步驟如下。

1）尺度空間構(gòu)建。

2）高斯差分金字塔空間構(gòu)建。

3）DOG空間極值點(diǎn)檢測(cè)。

DOG空間極值點(diǎn)檢測(cè)就是將DOG圖像中每個(gè)像素與它同尺度的8鄰域點(diǎn)及上下相鄰尺度對(duì)應(yīng)的9×2個(gè)鄰域點(diǎn)進(jìn)行比較，若為極值點(diǎn)則作為候選特征點(diǎn)，記錄其位置和對(duì)應(yīng)的尺度。為獲得更精確的特征點(diǎn)位置，在候選特征點(diǎn)處進(jìn)行泰勒展開(kāi)，得到式（4）：

D（x）=D+DTxx+12xT2Dx2x（4）

其中：關(guān)鍵點(diǎn)偏移量為x此處的偏移量x，與后面的x的命名重復(fù)，不太規(guī)范，因一篇論文中，一個(gè)變量?jī)H能代表一個(gè)含義，若包括兩個(gè)含義，則指代不清晰，是否可以用另一個(gè)變量對(duì)此進(jìn)行說(shuō)明？

回復(fù)：這兩個(gè)變量x是使用字體來(lái)區(qū)分的，一個(gè)是粗斜體表示向量，一個(gè)是細(xì)斜體，表示普通變量。是可以區(qū)分的。

這個(gè)公式是經(jīng)典文獻(xiàn)[1]中此算法的原作者提出的公式，也是用這種方式表述的。為保持統(tǒng)一，所以我覺(jué)得可以不用修改。=（x，y，σ）T；（x，y，σ）在該極值點(diǎn)處的值為D；令D（x）x=0，可通過(guò)式（5）求得極值：

=-2D-1x2Dx（5）

在Lowe[1]的文章中當(dāng)在任意方向上的偏移量大于0.5時(shí)，認(rèn)為該點(diǎn)與其他關(guān)鍵點(diǎn)很相似，將其剔除；否則保留該點(diǎn)為候選特征點(diǎn)，并計(jì)算該點(diǎn)對(duì)應(yīng)的尺度。

4）特征點(diǎn)主方向計(jì)算。

5）SIFT特征矢量生成。

將特征點(diǎn)鄰域內(nèi)圖像坐標(biāo)根據(jù)步驟4）計(jì)算出的特征點(diǎn)主方向進(jìn)行旋轉(zhuǎn)，使得特征向量具有旋轉(zhuǎn)不變性，旋轉(zhuǎn)后以特征點(diǎn)為中心劃分成4×4個(gè)子區(qū)域，在每個(gè)子區(qū)域內(nèi)計(jì)算8方向的梯度方向直方圖，即可構(gòu)成4×4×8共128維SIFT特征矢量。

2SIFT算法的并行化重構(gòu)

OpenCL標(biāo)準(zhǔn)將內(nèi)核可用的內(nèi)存分為私有內(nèi)存、局部?jī)?nèi)存和全局內(nèi)存/常量?jī)?nèi)存等類(lèi)型[16]，所以在利用OpenCL優(yōu)化算法時(shí)，充分挖掘GPU內(nèi)存的存儲(chǔ)層次，合理分配工作組大小是提高并行運(yùn)算效率的關(guān)鍵[17]。為提高算法并行度方便數(shù)據(jù)劃分、降低內(nèi)存帶寬要求，本文對(duì)SIFT算法作了以下重構(gòu)。

1）步驟合并。將構(gòu)造尺度空間、創(chuàng)建高斯金字塔及極值點(diǎn)檢測(cè)三步驟統(tǒng)一設(shè)計(jì)，目的是充分利用OpenCL的global memory和local memory的訪問(wèn)機(jī)制，使得這3個(gè)步驟的中間計(jì)算結(jié)果最大限度地在顯存中完成交互，減少內(nèi)存與顯存間的數(shù)據(jù)交換次數(shù)，隱藏帶寬延時(shí)。

2）步驟拆分。將極值點(diǎn)定位分為極值點(diǎn)坐標(biāo)檢測(cè)和極值點(diǎn)精確定位兩步：第1步只返回極值點(diǎn)坐標(biāo)，目的是輔助主機(jī)端完成內(nèi)存分配；第2步完成極值點(diǎn)精確定位。

3）重構(gòu)數(shù)據(jù)索引。本文全面摒棄基于隊(duì)列的特征點(diǎn)索引方式，而是采用線性存儲(chǔ)的方式管理特征點(diǎn)集，這對(duì)OpenCL內(nèi)核的工作項(xiàng)劃分、提高數(shù)據(jù)讀取效率以及降低內(nèi)存訪問(wèn)沖突都非常有效。

4）任務(wù)細(xì)粒度并行。經(jīng)過(guò)數(shù)據(jù)索引重構(gòu)，在OpenCL的內(nèi)核運(yùn)行時(shí)，可方便地部署大規(guī)模的工作組和工作項(xiàng)，實(shí)現(xiàn)計(jì)算任務(wù)的細(xì)粒度劃分。經(jīng)過(guò)以上設(shè)計(jì)后不僅能提高數(shù)據(jù)訪問(wèn)速度，而且能夠避免潛在的內(nèi)存訪問(wèn)沖突。

3SIFT算法的OpenCL實(shí)現(xiàn)

圖1為并行設(shè)計(jì)的SIFT特征提取流程。整個(gè)設(shè)計(jì)充分利用全局內(nèi)存以降低數(shù)據(jù)傳輸延時(shí)。主機(jī)端首先分配相應(yīng)內(nèi)存對(duì)象，然后依次入列高斯模糊、DOG金字塔和極值點(diǎn)檢測(cè)3個(gè)OpenCL內(nèi)核，完成后即可生成尺度空間和DOG金字塔，從全局優(yōu)化考慮，將這兩部的結(jié)果駐留在全局內(nèi)存中，只返回經(jīng)壓縮的極值點(diǎn)坐標(biāo)。接著按序運(yùn)行極值點(diǎn)精確定位、特征點(diǎn)方向計(jì)算和特征向量生成3個(gè)步驟，計(jì)算完成后即完成特征提取全過(guò)程。整個(gè)流程僅有返回極值點(diǎn)坐標(biāo)和返回特征點(diǎn)結(jié)果兩次讀回操作，其余的中間結(jié)果全部在顯存中完成交互，提高數(shù)據(jù)利用率，降低顯存帶寬要求。

3.1高斯模糊+DOG+極值點(diǎn)檢測(cè)內(nèi)核設(shè)計(jì)

深入發(fā)掘算法的并行潛力，充分利用OpenCL的內(nèi)存層次、合理配置工作項(xiàng)數(shù)量和工作組大小是性能提升的關(guān)鍵，也是內(nèi)核設(shè)計(jì)的難點(diǎn)。

3.1.1高斯濾波內(nèi)核設(shè)計(jì)及工作項(xiàng)分配

為降低計(jì)算量，將二維高斯變換分解為沿水平和垂直方向的一維變換，分解后可減少（N2-2×N）×W×H次乘法運(yùn)算（N為高斯核大小，W、H為圖像的寬和高）。由于每個(gè)像素相互獨(dú)立，所以在NDRange函數(shù)入列高斯濾波內(nèi)核時(shí)將工作項(xiàng)大小設(shè)置為W×H-N，即每個(gè)工作項(xiàng)完成一個(gè)像素的卷積。另外，進(jìn)行卷積時(shí)相鄰像素（圖2黑實(shí)線框內(nèi)數(shù)據(jù)）要重復(fù)讀取圖2灰色部分的數(shù)據(jù)，為提高讀取效率，本文通過(guò)配置工作組，實(shí)現(xiàn)原始數(shù)據(jù)在局部?jī)?nèi)存中共享。圖2為水平高斯核寬度為7、工作組大小設(shè)置為8時(shí)的數(shù)據(jù)分配，圖2表示每8個(gè)工作組讀取14個(gè)數(shù)據(jù)，完成8個(gè)點(diǎn)（圖2黑虛線框內(nèi)數(shù)據(jù)）的卷積運(yùn)算。

在工作組內(nèi)共享局部?jī)?nèi)存通常能提高計(jì)算性能，但并不絕對(duì)[18]。為找到工作組的最佳大小，本文測(cè)試了不同工作組大小時(shí)，寬度為11的高斯核對(duì)分辨率為1280×960的圖片進(jìn)行水平卷積的耗時(shí)，測(cè)試結(jié)果如圖3所示。隨著工作組的增大，耗時(shí)逐漸減少，當(dāng)工作組大于128后，耗時(shí)基本不再改變，又因?yàn)榫植績(jī)?nèi)存的限制，工作組不宜太大，于是本文將工作組大小配置為128。如此設(shè)計(jì)需考慮同一工作組中工作項(xiàng)的同步化問(wèn)題，本文采用OpenCL提供的barrier（CLK_LOCAL_MEM_FENCE）障礙函數(shù)來(lái)實(shí)現(xiàn)，垂直濾波與此類(lèi)似，不再贅述。

3.1.2DOG金字塔構(gòu)建

此步驟的內(nèi)核有兩種設(shè)計(jì)方法：1）一次入列內(nèi)核，只將高斯金字塔相鄰兩層相減，得到一層DOG圖像；2）一次入列內(nèi)核，將高斯金字塔整組圖像傳入內(nèi)核，計(jì)算完成后即可得到一組DOG圖像。

經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)，第2種方法數(shù)據(jù)利用率高，耗時(shí)較短。又因?yàn)楦咚菇鹱炙拷M層數(shù)固定，所以第2種設(shè)計(jì)的參數(shù)也固定，于是本文采用第2種設(shè)計(jì)方法，數(shù)據(jù)劃分如圖4所示。為進(jìn)一步提高運(yùn)算效率，對(duì)數(shù)據(jù)的運(yùn)算都以float4型向量進(jìn)行，共配置（W×H+3）/4個(gè)工作項(xiàng)，即每個(gè)工作項(xiàng)完成一組高斯金字塔對(duì)應(yīng)位置（圖4單個(gè)虛線框內(nèi)數(shù)據(jù)）的float4型向量相減。

3.1.3極值點(diǎn)檢測(cè)及內(nèi)核精確定位

入列極值點(diǎn)精確定位內(nèi)核前，主機(jī)端需預(yù)先分配內(nèi)存，而事先并不知道需要為多少個(gè)特征點(diǎn)分配內(nèi)存，所以本文將極值點(diǎn)檢測(cè)和精確定位作為兩個(gè)內(nèi)核先后入列，為減少數(shù)據(jù)傳輸，極值點(diǎn)檢測(cè)內(nèi)核只返回壓縮的極值點(diǎn)坐標(biāo)數(shù)組。

極值點(diǎn)檢測(cè)內(nèi)核計(jì)算完成后，根據(jù)返回的極值點(diǎn)坐標(biāo)在CPU端統(tǒng)計(jì)極值點(diǎn)位置和個(gè)數(shù)N，然后為N個(gè)特征點(diǎn)分配內(nèi)存，如圖5所示（實(shí)際分配1.5×N個(gè)，Lowe[1]文中指出實(shí)際的特征點(diǎn)數(shù)會(huì)是極值點(diǎn)數(shù)N的1.15倍左右）。圖5中每個(gè)虛線框用來(lái)保存一個(gè)特征點(diǎn)的完整信息。最后入列極值點(diǎn)精確定位內(nèi)核，每個(gè)極值點(diǎn)配置一個(gè)工作項(xiàng)，計(jì)算出的精確坐標(biāo)按工作項(xiàng)索引存入圖5對(duì)應(yīng)的位置。

3.2計(jì)算梯度方向直方圖

至此，已經(jīng)得到每個(gè)特征點(diǎn)的坐標(biāo)、尺度，并按線性存儲(chǔ)在圖5所示的全局內(nèi)存中。

因?yàn)槊總€(gè)特征點(diǎn)在內(nèi)存中按線性排列，相互獨(dú)立，所以為每個(gè)特征點(diǎn)配置一個(gè)工作組來(lái)計(jì)算梯度方向直方圖，工作組分配如圖6（a）所示。將工作組內(nèi)工作項(xiàng)設(shè)置為2維，為確定工作組最佳大小，本文嘗試了{(lán)1，RAD}、{2，RAD}、{4，RAD}、{8，RAD}四種方式，經(jīng)測(cè)試{2，RAD}效果最好（其中RAD為特征點(diǎn)的鄰域?qū)挾龋?。?dāng)RAD=5時(shí)，每個(gè)工作組分配10個(gè)工作項(xiàng)，工作組中的數(shù)據(jù)分配如圖6（b）所示，圖6（b）中標(biāo)有相同數(shù)字的像素被同一工作項(xiàng)處理。為實(shí)現(xiàn)數(shù)據(jù)共享，在工作組local_memory中構(gòu)建方向直方圖，這時(shí)必須使用OpenCL提供的atomic_add原子累加操作才能保證多個(gè)工作項(xiàng)同時(shí)累加直方圖同一位置時(shí)不會(huì)出錯(cuò)。直方圖生成后統(tǒng)計(jì)出大于直方圖極值80%的點(diǎn)的個(gè)數(shù)和角度，作為獨(dú)立的候選特征點(diǎn)，將結(jié)果填入圖5中對(duì)應(yīng)的位置。

3.3特征向量生成

計(jì)算出特征點(diǎn)主方向后，即可入列特征向量生成內(nèi)核，因數(shù)據(jù)重構(gòu)后各特征點(diǎn)在內(nèi)存中線性存儲(chǔ)且可獨(dú)立計(jì)算，所以為每個(gè)特征點(diǎn)分配一個(gè)工作組。又因每個(gè)特征點(diǎn)鄰域被劃分為4×4個(gè)子區(qū)域，所以為每個(gè)工作組配置16個(gè)工作項(xiàng)分別計(jì)算每個(gè)子區(qū)域的8個(gè)方向，數(shù)據(jù)劃分如圖7。圖7中每個(gè)箭頭的長(zhǎng)度表示每個(gè)方向的梯度累計(jì)值，箭頭越長(zhǎng)代表值越大。所有工作組計(jì)算完畢后，整個(gè)SIFT特征提取算法執(zhí)行完畢，提取出的特征點(diǎn)全部存儲(chǔ)在圖5所示的線性內(nèi)存中。

利用以上方法對(duì)兩幅圖片進(jìn)行特征提取后，即可利用歐氏距離準(zhǔn)則完成兩幅圖片特征點(diǎn)的粗匹配，然后用隨機(jī)抽樣一致（RANdom Sample Consensus， RANSAC）算法對(duì)粗匹配對(duì)進(jìn)行提純，計(jì)算得到兩幅圖片之間的變換矩陣，完成兩幅圖片的匹配。

4優(yōu)化后的算法在CPU上的移植

為進(jìn)一步驗(yàn)證OpenCL的可移植性并比較OpenCL在不同平臺(tái)上的加速性能，本文將優(yōu)化后的OpenCL_GPU_SIFT算法移植為能在CPU上運(yùn)行的OpenCL_CPU_SIFT版本。盡管OpenCL具有跨平臺(tái)特性，但由于硬件資源的差異，仍需注意以下兩點(diǎn)：

1）本文采用的Intel core i5 3210m CPU不支持OpenCL 32位原子操作，所以在3.2節(jié)的內(nèi)核設(shè)計(jì)中無(wú)法使用atomic_add原子累加操作，只能將3.2節(jié)的工作組大小配置為1，此時(shí)每個(gè)工作組中只有一個(gè)工作項(xiàng)，因而不能實(shí)現(xiàn)局部?jī)?nèi)存共享。

2）工作組中工作項(xiàng)的數(shù)量上限一般受限于兩點(diǎn)：一是設(shè)備所能提供的資源數(shù)，二是內(nèi)核所需的資源數(shù)，這里的資源主要指的是局部?jī)?nèi)存。針對(duì)3.2節(jié)的內(nèi)核，GT635m GPU的局部?jī)?nèi)存為47KB（K表示×1024），工作組上限為512，而Intel 3210m CPU的局部?jī)?nèi)存只有32KB（K表示×1024），工作組上限為352，所以工作組大小一定要根據(jù)硬件平臺(tái)來(lái)設(shè)置，這點(diǎn)尤為重要。針對(duì)以上兩點(diǎn)修改后得到的OpenCL_CPU_SIFT版本即可運(yùn)行于Intel 3210m CPU中，可見(jiàn)OpenCL具有較好的可移植性。

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

5.1實(shí)驗(yàn)平臺(tái)

本實(shí)驗(yàn)的實(shí)驗(yàn)平臺(tái)CPU為Intel Core i5 3210m，雙核心四線程，2.5GHz；GPU采用NVIDA GeForce GT 635m，核心頻率660MHz，96個(gè)流處理器單元，128位總線寬度；開(kāi)發(fā)環(huán)境為Vs2013，OpenCV版本2.4.9，OpenCL版本1.1。

5.2實(shí)驗(yàn)方法

本文實(shí)驗(yàn)的代碼是在Rob Hess維護(hù)的SIFT算法（http：//robwhess.github.io/opensift/，本文稱(chēng)之為CPU_SIFT）的基礎(chǔ)上修改而來(lái)。實(shí)驗(yàn)分別測(cè)試并行化的OpenCL_CPU_SIFT和OpenCL_GPU_SIFT這兩個(gè)版本用時(shí)，并與未優(yōu)化的CPU_SIFT版本用時(shí)作比較分別計(jì)算兩個(gè)版本的加速比。實(shí)驗(yàn)選取a，b兩組圖片。a組有a1～a5共5幅圖片，b組有b1～b4 4對(duì)共8幅圖片。為使實(shí)驗(yàn)結(jié)果更具有參考性，其中a1選取Rob Hess采用的behavior圖，分辨率為320×300；a2選取國(guó)際通用的Lena圖，分辨率為512×512；a3此處是否描述有誤？即a2～a5，共4幅圖像，而后面的描述中卻有3幅，所以請(qǐng)作相應(yīng)調(diào)整?！玜5為利用CCD攝像頭獲取的3幅紋理從簡(jiǎn)單到復(fù)雜的測(cè)試圖片，分辨率分別為960×720、1280×960、2560×1440。另外為了測(cè)試優(yōu)化后的算法對(duì)不同圖片的適應(yīng)性，b組圖片選取4對(duì)有角度、光照和尺度變化的圖片，分辨率統(tǒng)一為1280×960。

5.3實(shí)驗(yàn)結(jié)果

在與原CPU_SIFT算法匹配效果一致的情況下，各圖片的耗時(shí)如表2所示，利用OpenCL優(yōu)化后的CPU版本和GPU版本的加速比最大分別為4倍和19倍左右，如圖8所示。這表明OpenCL不僅具有優(yōu)秀的并行計(jì)算能力，而且具有較好的跨平臺(tái)特性，這也是OpenCL相對(duì)于CUDA的一大優(yōu)勢(shì)。

通過(guò)對(duì)比表1和表2可知，本文在PC平臺(tái)實(shí)現(xiàn)的SIFT算法的加速比比文獻(xiàn)[9]中實(shí)現(xiàn)的加速比更高，特別是當(dāng)圖像分辨率較大時(shí)，本文實(shí)現(xiàn)的加速比會(huì)進(jìn)一步增大。這主要是因?yàn)閮牲c(diǎn)：1）數(shù)據(jù)量越大，越能充分發(fā)揮GPU并行運(yùn)算的能力，越能隱藏?cái)?shù)據(jù)傳輸延時(shí)；2）由于移動(dòng)處理器架構(gòu)的限制，文獻(xiàn)[9]只針對(duì)SIFT特征點(diǎn)檢測(cè)部分進(jìn)行了優(yōu)化，而本文則是對(duì)整個(gè)SIFT算法流程進(jìn)行統(tǒng)一優(yōu)化，充分利用了GPU的全局內(nèi)存，數(shù)據(jù)讀取效率更高。另外，通過(guò)對(duì)比進(jìn)一步證明了OpenCL對(duì)移動(dòng)平臺(tái)和PC平臺(tái)都具有廣泛的適用性，再次說(shuō)明OpenCL具有較好的可移植性和跨平臺(tái)性。

圖9為本文算法對(duì)a組圖像的特征提取結(jié)果。由圖9可知，優(yōu)化的算法對(duì)圖像處理領(lǐng)域常用的Lena圖和behavior圖都能有效地提取特征點(diǎn)，a3～a5三張圖片的紋理由簡(jiǎn)單到復(fù)雜，優(yōu)化后的算法均能有效提取特征點(diǎn)。在b組圖片中，b1的兩幅圖片有角度變化，b2有光照變化，b3既有角度又有光照變化，b4的角度、光照和尺度均有變化，匹配結(jié)果如圖10所示。綜合圖9和圖10的實(shí)驗(yàn)結(jié)果可知，優(yōu)化后的算法對(duì)不同分辨率、不同紋理復(fù)雜度的圖像都能提取穩(wěn)定的特征點(diǎn)，對(duì)具有角度、光照和尺度變化的圖像都能正確匹配，這表明并行化后的算法對(duì)各種圖片都有較好的適應(yīng)性。

為進(jìn)一步分析不同平臺(tái)不同數(shù)據(jù)規(guī)模對(duì)OpenCL加速性能的影響，針對(duì)a3、a4和a5三幅不同分辨率的圖像，本文分別統(tǒng)計(jì)了優(yōu)化后的GPU和CPU版本各步驟的加速比，結(jié)果如圖11和圖12。圖11和圖12中步驟1為高斯模糊+高斯差分金字塔生成，步驟2為極值點(diǎn)定位，步驟3為計(jì)算方向直方圖，步驟4為特征矢量生成。對(duì)比圖11和圖12可知，無(wú)論是GPU還是CPU平臺(tái)，優(yōu)化后，高斯模糊+高斯差分金字塔生成步驟加速比都最大，GPU版本甚至達(dá)到了50倍，這是因?yàn)樵摬襟E中各工作項(xiàng)數(shù)據(jù)獨(dú)立無(wú)分支，并行度高。而極值點(diǎn)定位步驟有大量的選擇判斷語(yǔ)句，并行度較差，閆鈞華等[19]將此步驟放在CPU端執(zhí)行，本文將此步驟一并優(yōu)化，速度有一定提升但不夠理想，這是因?yàn)樵诓⑿芯幊讨袩o(wú)論CPU還是GPU都受分支語(yǔ)句的影響，GPU尤其如此。另外，與圖11不同，圖12中的三條曲線無(wú)交叉，隨著圖片分辨率的增大各步驟的加速比都逐步增大，說(shuō)明數(shù)據(jù)規(guī)模越大越能發(fā)揮并行運(yùn)算的優(yōu)勢(shì)。另外OpenCL_CPU_SIFT版本的特征向量生成步驟比計(jì)算方向直方圖步驟的加速效果更好，這是因?yàn)榍罢咄ㄟ^(guò)工作組共享局部?jī)?nèi)存能充分利用CPU的L1 cache，從而提升運(yùn)算性能。

6結(jié)語(yǔ)

本文對(duì)SIFT算法進(jìn)行合并、拆分和數(shù)據(jù)重構(gòu)等并行化設(shè)計(jì)，改善提高了算法的并行度，并通過(guò)合理設(shè)置工作組和工作項(xiàng)大小，充分利用內(nèi)存層次等方法對(duì)算法進(jìn)一步優(yōu)化。利用OpenCL并行編程語(yǔ)言的跨平臺(tái)特性，本文分別在NVIDIA GPU和Intel CPU平臺(tái)上對(duì)該算法進(jìn)行并行優(yōu)化，分別取得了10.51～19.33和2.34～4.74倍的加速，并利用OpenCL的可移植性解決了CUDA對(duì)硬件平臺(tái)的依賴(lài)問(wèn)題。本文的研究?jī)?nèi)容及結(jié)果可應(yīng)用于提升遙感圖像拼接、醫(yī)學(xué)影像配準(zhǔn)和流水線工件定位等領(lǐng)域的圖像匹配速度。

目前本文的優(yōu)化方法在同一時(shí)刻只將OpenCL內(nèi)核入列到CPU或者GPU中，即同一時(shí)刻只能充分利用CPU或GPU的計(jì)算能力，接下來(lái)本文將進(jìn)一步研究異構(gòu)系統(tǒng)中不同平臺(tái)間的并行性，將可并行運(yùn)行的內(nèi)核同時(shí)入列到CPU和GPU中運(yùn)行，進(jìn)而擴(kuò)展到多核多CPU和多GPU的復(fù)雜異構(gòu)系統(tǒng)中，進(jìn)一步提高算法的運(yùn)行速度。

參考文獻(xiàn)：

[1]

LOWE D G.Distinctive image features from scaleinvariant keypoints [J]. International Journal of Computer Vision， 2004， 60（2）： 91-110.

[2]

KE Y， SUKTHANKAR R. PCASIFT： a more distinctive representation for local image descriptors [C]// CVPR 2004： Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2004： II506-II513.

[3]

BAY H， TUYTELAARS T， VAN GOOL L. SURF： speeded up robust features [C]// ECCV 2006： Proceedings of the 9th European Conference on Computer Vision， Part Ⅰ. Berlin： Springer， 2006： 404-417.

[4]

LUO J， GWUN O. A comparison of SIFT， PCASIFT and SURF [J]. Journal of Business Education， 2009， 3（4）： 143-152.

[5]

張杰，柴志雷，喻津.基于GPU的圖像特征并行計(jì)算方法[J].計(jì)算機(jī)科學(xué)，2015，42（10）：297-324.（ZHANG J， CHAI Z L， YU J. Parallel computation method of image features based on GPU [J]. Computer Science， 2015， 42（10）： 297-324.）

[6]

肖漢，郭運(yùn)宏，周清雷.面向CPU+GPU異構(gòu)計(jì)算的SIFT特征匹配并行算法[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，41（11）：1732-1737.（XIAO H， GUO Y H， ZHOU Q L. Parallel algorithm of CPU and GPUoriented heterogeneous computation in SIFT feature matching [J]. Journal of Tongji University （Natural Science）， 2013， 41（11）： 1732-1737.）

[7]

LU M. Fast implementation of scale invariant feature transform based on CUDA [J]. Applied Mathematics & Information Sciences， 2013， 7（2）： 717-722.

[8]

WANG G， RISTER B， CAVALLARO J R. Workload analysis and efficient OpenCLbased implementation of SIFT algorithm on a smartphone [C]// GlobalSIP 2013： Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing. Piscataway， NJ： IEEE， 2013： 759-762.

[9]

RISTER B， WANG G， WU M， et al. A fast and efficient SIFT detector using the mobile GPU [C]// ICASSP 2013： Proceedings of 2013 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway， NJ： IEEE， 2013： 2674-2678.

[10]

董小社，劉超，王恩東，等.面向GPU異構(gòu)并行系統(tǒng)的多任務(wù)流編程模型[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（7）：1638-1646.（DONG X S， LIU C， WANG E D， et al. A multi taskstream programing model for GPU based on heterogeneous parallel system [J]. Chinese Journal of Computers， 2014， 37（7）： 1638-1646.）

[11]

PENNYCOOK S J， HAMMOND S D， WRIGHT S A， et al. An investigation of the performance portability of OpenCL [J]. Journal of Parallel & Distributed Computing， 2013， 73（11）： 1439-1450.

[12]

TIAN L， MENG C， ZHOU F. A twolevel task scheduler on multiple DSP system for OpenCL [J]. Advances in Mechanical Engineering， 2014： Article ID 754835.

[13]

陳剛，吳百鋒.面向OpenCL模型的GPU性能優(yōu)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23（4）：571-581.（CHEN G， WU B F. GPU performance optimization targeting OpenCL model [J]. Journal of ComputerAided Design & Computer Graphics， 2011， 23（4）： 571-581.）

[14]

YAN W， SHI X， YAN X， et al. Computing OpenSURF on OpenCL and general purpose GPU [J]. International Journal of Advanced Robotic Systems， 2013， 10（4）： 301-319.

[15]

SANCHEZ L M， FERNANDEZ J， SOTOMAYOR R， et al. A comparative study and evaluation of parallel programming models for sharedmemory parallel architectures [J]. New Generation Computing， 2013， 31（3）： 139-161.

[16]

JANG B， CHOI M， KIM K K. Algorithmic GPGPU memory optimization [C]// ISOCC 2013： Proceedings of the 2013 International SoC Design Conference. Piscataway， NJ： IEEE， 2013： 154-157.

[17]

肖漢，馬歌，周清雷.面向OpenCL架構(gòu)的Harris角點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)科學(xué)，2014，41（7）：306-309.（XIAO H， MA G， ZHOU Q L. Harris corner detection algorithm on OpenCL architecture [J]. Computer Science， 2014， 41（7）： 306-309.）

[18]

FANG J， SIPS H， VARBANESCU A L. Aristotle： a performance impact indicator for the OpenCL kernels using local memory [J]. Scientific Programming， 2014， 22（3）： 239-257.

[19]

閆鈞華，杭誼青，許俊峰，等.基于CUDA的高分辨率數(shù)字視頻圖像配準(zhǔn)快速實(shí)現(xiàn)[J].儀器儀表學(xué)報(bào)，2014，35（2）：380-386.（YAN J H， HANG Y Q， XU J F， et al. Quick realization of CUDAbased registration of highresolution digital video images [J]. Chinese Journal of Scientific Instrument， 2014， 35（2）： 380-386.）