基于OpenCL的尺度不變特征變換算法的并行設(shè)計(jì)與論文

　　針對尺度不變特征變換(SIFT)算法實(shí)時(shí)性差的問題，提出了利用開放式計(jì)算語言(OpenCL)并行優(yōu)化的SIFT算法。首先，通過對原算法各步驟進(jìn)行組合拆分、重構(gòu)特征點(diǎn)在內(nèi)存中的數(shù)據(jù)索引等方式對原算法進(jìn)行并行化重構(gòu)，使得計(jì)算機(jī)網(wǎng)絡(luò)算法的中間計(jì)算結(jié)果能夠完全在顯存中完成交互;然后，采用復(fù)用全局內(nèi)存對象、共享局部內(nèi)存、優(yōu)化內(nèi)存讀取等策略對原算法各步驟進(jìn)行并行設(shè)計(jì)，提高數(shù)據(jù)讀取效率，降低傳輸延時(shí);最后，利用OpenCL語言在圖形處理單元(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)。

0引言

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

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

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

　　針對以上問題，本文對SIFT算法步驟及數(shù)據(jù)索引方式進(jìn)行重構(gòu)，提高其并行度，然后通過優(yōu)化內(nèi)存讀取、合理利用OpenCL內(nèi)存層次等策略對該算法進(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)檢測。

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

　　D(x)=D+DTxx+12xT2Dx2x(4)

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

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

　　這個(gè)公式是經(jīng)典文獻(xiàn)[1]中此算法的原作者提出的公式，也是用這種方式表述的。為保持統(tǒng)一，所以我覺得可以不用修改。=(x，y，σ)T;(x，y，σ)在該極值點(diǎn)處的值為D;令D(x)x=0，可通過式(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)對應(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)存、局部內(nèi)存和全局內(nèi)存/常量內(nèi)存等類型[16]，所以在利用OpenCL優(yōu)化算法時(shí)，充分挖掘GPU內(nèi)存的存儲(chǔ)層次，合理分配工作組大小是提高并行運(yùn)算效率的關(guān)鍵[17]。為提高算法并行度方便數(shù)據(jù)劃分、降低內(nèi)存帶寬要求，本文對SIFT算法作了以下重構(gòu)。

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

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

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

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