基于OpenCL的尺度不變特征變換算法的并行設計與論文

　　針對尺度不變特征變換(SIFT)算法實時性差的問題，提出了利用開放式計算語言(OpenCL)并行優化的SIFT算法。首先，通過對原算法各步驟進行組合拆分、重構特征點在內存中的數據索引等方式對原算法進行并行化重構，使得計算機網絡算法的中間計算結果能夠完全在顯存中完成交互;然后，采用復用全局內存對象、共享局部內存、優化內存讀取等策略對原算法各步驟進行并行設計，提高數據讀取效率，降低傳輸延時;最后，利用OpenCL語言在圖形處理單元(GPU)上實現了SIFT算法的細粒度并行加速，并在中央處理器(CPU)上完成了移植。與原SIFT算法配準效果相近時，并行化的算法在GPU和CPU平臺上特征提取速度分別提升了10.51～19.33和2.34～4.74倍。實驗結果表明，利用OpenCL并行加速的SIFT算法能夠有效提高圖像配準的實時性，并能克服統一計算設備架構(CUDA)因移植困難而不能充分利用異構系統中多種計算核心的缺點。

0引言

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

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

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

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

1SIFT特征提取算法流程

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

　　1)尺度空間構建。

　　2)高斯差分金字塔空間構建。

　　3)DOG空間極值點檢測。

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

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

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

　　回復：這兩個變量x是使用字體來區分的，一個是粗斜體表示向量，一個是細斜體，表示普通變量。是可以區分的。

　　這個公式是經典文獻[1]中此算法的原作者提出的公式，也是用這種方式表述的。為保持統一，所以我覺得可以不用修改。=(x，y，σ)T;(x，y，σ)在該極值點處的值為D;令D(x)x=0，可通過式(5)求得極值：

　　=-2D-1x2Dx(5)

　　在Lowe[1]的文章中當在任意方向上的偏移量大于0.5時，認為該點與其他關鍵點很相似，將其剔除;否則保留該點為候選特征點，并計算該點對應的尺度。

　　4)特征點主方向計算。

　　5)SIFT特征矢量生成。

　　將特征點鄰域內圖像坐標根據步驟4)計算出的特征點主方向進行旋轉，使得特征向量具有旋轉不變性，旋轉后以特征點為中心劃分成4×4個子區域，在每個子區域內計算8方向的梯度方向直方圖，即可構成4×4×8共128維SIFT特征矢量。

　　2SIFT算法的并行化重構

　　OpenCL標準將內核可用的內存分為私有內存、局部內存和全局內存/常量內存等類型[16]，所以在利用OpenCL優化算法時，充分挖掘GPU內存的存儲層次，合理分配工作組大小是提高并行運算效率的關鍵[17]。為提高算法并行度方便數據劃分、降低內存帶寬要求，本文對SIFT算法作了以下重構。

　　1)步驟合并。將構造尺度空間、創建高斯金字塔及極值點檢測三步驟統一設計，目的是充分利用OpenCL的global memory和local memory的訪問機制，使得這3個步驟的中間計算結果最大限度地在顯存中完成交互，減少內存與顯存間的數據交換次數，隱藏帶寬延時。

　　2)步驟拆分。將極值點定位分為極值點坐標檢測和極值點精確定位兩步：第1步只返回極值點坐標，目的是輔助主機端完成內存分配;第2步完成極值點精確定位。

　　3)重構數據索引。本文全面摒棄基于隊列的特征點索引方式，而是采用線性存儲的方式管理特征點集，這對OpenCL內核的工作項劃分、提高數據讀取效率以及降低內存訪問沖突都非常有效。

　　4)任務細粒度并行。經過數據索引重構，在OpenCL的內核運行時，可方便地部署大規模的工作組和工作項，實現計算任務的細粒度劃分。經過以上設計后不僅能提高數據訪問速度，而且能夠避免潛在的內存訪問沖突。