針對尺度不變特徵變換(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的內核運行時，可方便地部署大規模的工作組和工作項，實現計算任務的細粒度劃分。經過以上設計後不僅能提高數據訪問速度，而且能夠避免潛在的內存訪問衝突。
3SIFT算法的OpenCL實現
圖1為並行設計的SIFT特徵提取流程。整個設計充分利用全局內存以降低數據傳輸延時。主機端首先分配相應內存對象，然後依次入列高斯模糊、DOG金字塔和極值點檢測3個OpenCL內核，完成後即可生成尺度空間和DOG金字塔，從全局優化考慮，將這兩部的結果駐留在全局內存中，只返回經壓縮的極值點座標。接着按序運行極值點精確定位、特徵點方向計算和特徵向量生成3個步驟，計算完成後即完成特徵提取全過程。整個流程僅有返回極值點座標和返回特徵點結果兩次讀回操作，其餘的中間結果全部在顯存中完成交互，提高數據利用率，降低顯存帶寬要求。
3.1高斯模糊+DOG+極值點檢測內核設計
深入發掘算法的並行潛力，充分利用OpenCL的內存層次、合理配置工作項數量和工作組大小是性能提升的關鍵，也是內核設計的難點。
3.1.1高斯濾波內核設計及工作項分配
為降低計算量，將二維高斯變換分解為沿水平和垂直方向的一維變換，分解後可減少(N2-2×N)×W×H次乘法運算(N為高斯核大小，W、H為圖像的寬和高)。由於每個像素相互獨立，所以在NDRange函數入列高斯濾波內核時將工作項大小設置為W×H-N，即每個工作項完成一個像素的卷積。另外，進行卷積時相鄰像素(圖2黑實線框內數據)要重複讀取圖2灰色部分的數據，為提高讀取效率，本文通過配置工作組，實現原始數據在局部內存中共享。圖2為水平高斯核寬度為7、工作組大小設置為8時的數據分配，圖2表示每8個工作組讀取14個數據，完成8個點(圖2黑虛線框內數據)的卷積運算。
在工作組內共享局部內存通常能提高計算性能，但並不絕對[18]。為找到工作組的最佳大小，本文測試了不同工作組大小時，寬度為11的高斯核對分辨率為1280×960的圖片進行水平卷積的耗時，測試結果如圖3所示。隨着工作組的增大，耗時逐漸減少，當工作組大於128後，耗時基本不再改變，又因為局部內存的限制，工作組不宜太大，於是本文將工作組大小配置為128。如此設計需考慮同一工作組中工作項的同步化問題，本文采用OpenCL提供的barrier(CLK_LOCAL_MEM_FENCE)障礙函數來實現，垂直濾波與此類似，不再贅述。
3.1.2DOG金字塔構建
此步驟的內核有兩種設計方法：1)一次入列內核，只將高斯金字塔相鄰兩層相減，得到一層DOG圖像;2)一次入列內核，將高斯金字塔整組圖像傳入內核，計算完成後即可得到一組DOG圖像。
經實驗發現，第2種方法數據利用率高，耗時較短。又因為高斯金字塔每組層數固定，所以第2種設計的參數也固定，於是本文采用第2種設計方法，數據劃分如圖4所示。為進一步提高運算效率，對數據的運算都以float4型向量進行，共配置(W×H+3)/4個工作項，即每個工作項完成一組高斯金字塔對應位置(圖4單個虛線框內數據)的float4型向量相減。
3.1.3極值點檢測及內核精確定位
入列極值點精確定位內核前，主機端需預先分配內存，而事先並不知道需要為多少個特徵點分配內存，所以本文將極值點檢測和精確定位作為兩個內核先後入列，為減少數據傳輸，極值點檢測內核只返回壓縮的極值點座標數組。
極值點檢測內核計算完成後，根據返回的極值點座標在CPU端統計極值點位置和個數N，然後為N個特徵點分配內存，如圖5所示(實際分配1.5×N個，Lowe[1]文中指出實際的特徵點數會是極值點數N的1.15倍左右)。圖5中每個虛線框用來保存一個特徵點的完整信息。最後入列極值點精確定位內核，每個極值點配置一個工作項，計算出的精確座標按工作項索引存入圖5對應的位置。
3.2計算梯度方向直方圖
至此，已經得到每個特徵點的座標、尺度，並按線性存儲在圖5所示的全局內存中。因為每個特徵點在內存中按線性排列，相互獨立，所以為每個特徵點配置一個工作組來計算梯度方向直方圖，工作組分配如圖6(a)所示。將工作組內工作項設置為2維，為確定工作組最佳大小，本文嘗試了{1，RAD}、{2，RAD}、{4，RAD}、{8，RAD}四種方式，經測試{2，RAD}效果最好(其中RAD為特徵點的鄰域寬度)。當RAD=5時，每個工作組分配10個工作項，工作組中的數據分配如圖6(b)所示，圖6(b)中標有相同數字的像素被同一工作項處理。為實現數據共享，在工作組local_memory中構建方向直方圖，這時必須使用OpenCL提供的atomic_add原子累加操作才能保證多個工作項同時累加直方圖同一位置時不會出錯。直方圖生成後統計出大於直方圖極值80%的點的個數和角度，作為獨立的候選特徵點，將結果填入圖5中對應的.位置。
3.3特徵向量生成
計算出特徵點主方向後，即可入列特徵向量生成內核，因數據重構後各特徵點在內存中線性存儲且可獨立計算，所以為每個特徵點分配一個工作組。又因每個特徵點鄰域被劃分為4×4個子區域，所以為每個工作組配置16個工作項分別計算每個子區域的8個方向，數據劃分如圖7。圖7中每個箭頭的長度表示每個方向的梯度累計值，箭頭越長代表值越大。所有工作組計算完畢後，整個SIFT特徵提取算法執行完畢，提取出的特徵點全部存儲在圖5所示的線性內存中。
利用以上方法對兩幅圖片進行特徵提取後，即可利用歐氏距離準則完成兩幅圖片特徵點的粗匹配，然後用隨機抽樣一致(RANdom Sample Consensus， RANSAC)算法對粗匹配對進行提純，計算得到兩幅圖片之間的變換矩陣，完成兩幅圖片的匹配。
4優化後的算法在CPU上的移植
為進一步驗證OpenCL的可移植性並比較OpenCL在不同平台上的加速性能，本文將優化後的OpenCL_GPU_SIFT算法移植為能在CPU上運行的OpenCL_CPU_SIFT版本。儘管OpenCL具有跨平台特性，但由於硬件資源的差異，仍需注意以下兩點：
1)本文采用的Intel core i5 3210m CPU不支持OpenCL 32位原子操作，所以在3.2節的內核設計中無法使用atomic_add原子累加操作，只能將3.2節的工作組大小配置為1，此時每個工作組中只有一個工作項，因而不能實現局部內存共享。
2)工作組中工作項的數量上限一般受限於兩點：一是設備所能提供的資源數，二是內核所需的資源數，這裏的資源主要指的是局部內存。針對3.2節的內核，GT635m GPU的局部內存為47KB(K表示×1024)，工作組上限為512，而Intel 3210m CPU的局部內存只有32KB(K表示×1024)，工作組上限為352，所以工作組大小一定要根據硬件平台來設置，這點尤為重要。針對以上兩點修改後得到的OpenCL_CPU_SIFT版本即可運行於Intel 3210m CPU中，可見OpenCL具有較好的可移植性。
5實驗結果及分析
5.1實驗平台
本實驗的實驗平台CPU為Intel Core i5 3210m，雙核心四線程，2.5GHz;GPU採用NVIDA GeForce GT 635m，核心頻率660MHz，96個流處理器單元，128位總線寬度;開發環境為Vs2013，OpenCV版本2.4.9，OpenCL版本1.1。
5.2實驗方法
本文實驗的代碼是在Rob Hess維護的SIFT算法(http：//，本文稱之為CPU_SIFT)的基礎上修改而來。實驗分別測試並行化的OpenCL_CPU_SIFT和OpenCL_GPU_SIFT這兩個版本用時，並與未優化的CPU_SIFT版本用時作比較分別計算兩個版本的加速比。實驗選取a，b兩組圖片。a組有a1～a5共5幅圖片，b組有b1～b4 4對共8幅圖片。為使實驗結果更具有參考性，其中a1選取Rob Hess採用的behavior圖，分辨率為320×300;a2選取國際通用的Lena圖，分辨率為512×512;a3此處是否描述有誤?即a2～a5，共4幅圖像，而後面的描述中卻有3幅，所以請作相應調整。～a5為利用CCD攝像頭獲取的3幅紋理從簡單到複雜的測試圖片，分辨率分別為960×720、1280×960、2560×1440。另外為了測試優化後的算法對不同圖片的適應性，b組圖片選取4對有角度、光照和尺度變化的圖片，分辨率統一為1280×960。
5.3實驗結果
在與原CPU_SIFT算法匹配效果一致的情況下，各圖片的耗時如表2所示，利用OpenCL優化後的CPU版本和GPU版本的加速比最大分別為4倍和19倍左右，如圖8所示。這表明OpenCL不僅具有優秀的並行計算能力，而且具有較好的跨平台特性，這也是OpenCL相對於CUDA的一大優勢。
通過對比表1和表2可知，本文在PC平台實現的SIFT算法的加速比比文獻[9]中實現的加速比更高，特別是當圖像分辨率較大時，本文實現的加速比會進一步增大。這主要是因為兩點：1)數據量越大，越能充分發揮GPU並行運算的能力，越能隱藏數據傳輸延時;2)由於移動處理器架構的限制，文獻[9]只針對SIFT特徵點檢測部分進行了優化，而本文則是對整個SIFT算法流程進行統一優化，充分利用了GPU的全局內存，數據讀取效率更高。另外，通過對比進一步證明了OpenCL對移動平台和PC平台都具有廣泛的適用性，再次説明OpenCL具有較好的可移植性和跨平台性。
圖9為本文算法對a組圖像的特徵提取結果。由圖9可知，優化的算法對圖像處理領域常用的Lena圖和behavior圖都能有效地提取特徵點，a3～a5三張圖片的紋理由簡單到複雜，優化後的算法均能有效提取特徵點。在b組圖片中，b1的兩幅圖片有角度變化，b2有光照變化，b3既有角度又有光照變化，b4的角度、光照和尺度均有變化，匹配結果如圖10所示。綜合圖9和圖10的實驗結果可知，優化後的算法對不同分辨率、不同紋理複雜度的圖像都能提取穩定的特徵點，對具有角度、光照和尺度變化的圖像都能正確匹配，這表明並行化後的算法對各種圖片都有較好的適應性。
為進一步分析不同平台不同數據規模對OpenCL加速性能的影響，針對a3、a4和a5三幅不同分辨率的圖像，本文分別統計了優化後的GPU和CPU版本各步驟的加速比，結果如圖11和圖12。圖11和圖12中步驟1為高斯模糊+高斯差分金字塔生成，步驟2為極值點定位，步驟3為計算方向直方圖，步驟4為特徵向量生成。對比圖11和圖12可知，無論是GPU還是CPU平台，優化後，高斯模糊+高斯差分金字塔生成步驟加速比都最大，GPU版本甚至達到了50倍，這是因為該步驟中各工作項數據獨立無分支，並行度高。而極值點定位步驟有大量的選擇判斷語句，並行度較差，閆鈞華等[19]將此步驟放在CPU端執行，本文將此步驟一併優化，速度有一定提升但不夠理想，這是因為在並行編程中無論CPU還是GPU都受分支語句的影響，GPU尤其如此。另外，與圖11不同，圖12中的三條曲線無交叉，隨着圖片分辨率的增大各步驟的加速比都逐步增大，説明數據規模越大越能發揮並行運算的優勢。另外OpenCL_CPU_SIFT版本的特徵向量生成步驟比計算方向直方圖步驟的加速效果更好，這是因為前者通過工作組共享局部內存能充分利用CPU的L1 cache，從而提升運算性能。
6結語
本文對SIFT算法進行合併、拆分和數據重構等並行化設計，改善提高了算法的並行度，並通過合理設置工作組和工作項大小，充分利用內存層次等方法對算法進一步優化。利用OpenCL並行程式語言的跨平台特性，本文分別在NVIDIA GPU和Intel CPU平台上對該算法進行並行優化，分別取得了10.51～19.33和2.34～4.74倍的加速，並利用OpenCL的可移植性解決了CUDA對硬件平台的依賴問題。本文的研究內容及結果可應用於提升遙感圖像拼接、醫學影像配準和流水線工件定位等領域的圖像匹配速度。
目前本文的優化方法在同一時刻只將OpenCL內核入列到CPU或者GPU中，即同一時刻只能充分利用CPU或GPU的計算能力，接下來本文將進一步研究異構系統中不同平台間的並行性，將可並行運行的內核同時入列到CPU和GPU中運行，進而擴展到多核多CPU和多GPU的複雜異構系統中，進一步提高算法的運行速度。
文萃咖
