SIFT算法GPU并行化研究

鄧伯勝

（四川大學計算機學院，成都 610065）

SIFT算法GPU并行化研究

鄧伯勝

（四川大學計算機學院，成都 610065）

SIFT是計算機視覺領域一個基礎算法，從綜合評估上看，SIFT目前仍是最具使用價值的特征檢測、特征描述算法。總結SIFT算法原理，針對算法耗時問題，參考多位學者研究者的并行計算解決方案，并利用CUDA具體實現實驗，歸納出一種三級并行方案。實驗表明，與CPU架構下SIFT實現方案相比，該方案大幅提升SIFT特征提取性能，加速比隨著圖片數目或特征點數目增加而增加。

SIFT；CUDA；三級并行；加速

0 引言

尺度不變特征變換（SIFT）是一種基于尺度空間理論的提取圖像局部特征的優秀算法。SIFT特征魯棒性強，受旋轉、縮放、平移、噪聲、關照變化影響很小。但SIFT算法復雜度高，計算耗時，難以應用到實時性要求高的場合。隨著可編程圖像處理器GPU技術成熟，國內外很多學者針對SIFT計算效率問題做了很多研究，設計出很多并行加速方案。但就目前為止，這些方案的并行級別都不超過兩級。例如Sinha等人基于OpenGL和Gg語言在NVIDIA 7900GTX顯卡上實現SIFT，僅僅實現了一級并行 （像素級）；田文等人提出一種基于CUDA的SIFT實現方案，性能達到30-50倍，但僅僅針對特定圖片并且未考慮顯卡和CPU端數據傳輸時間，并行級別只有像素級和高斯組（Octave）兩級。本文考慮到SIFT主要應用于多張圖片檢測特征點，采用CUDA流（cudaStream）實現了首末數據傳輸和中間計算的并行，隱藏了多張處理圖片上傳圖片數據和返回計算結果的數據傳輸時間，同時提高了計算并行度，達到了三級并行，在考慮到數據傳輸時間后，性能能達到CPU實現的20倍左右。

1 SIFT算法原理

SIFT檢測圖片特征點主要有兩大步驟：提取特征點和描述特征點。提取特征點即計算出某個滿足條件的圖像像素點的坐標、尺度、方向值，描述特征點即統計出特征點及其領域點像素值變化的梯度值。包括的環節有：構建高斯金字塔，構建高斯差分金字塔，計算精選極值點，計算主方向和描述符。

1.1 建立高斯金字塔，即生成不同尺度 （模糊程度）、不同大小的多組圖片。

圖1

1.2 建立高斯差分金字塔，高斯差分金字塔組數同高斯金字塔一樣，每組的層數為S+2（高斯金字塔每組層數為S+3），構建過程如圖1中所σ示。

高斯差分金字塔第i組的第k層由高斯金字塔的第i組的第k層與第k+1相減而得。

1.3 計算、精選極值點，如圖1右所示，極值點為高斯差分金字塔中，極值點為其值為領域內最大或最小的點。領域包括8+9+9=26個點。

精選特征點包括校正特征點坐標值、尺度值，去除低對比度和邊緣響應點。

高斯差分金字塔某組某層可視為一個二元離散函數D（x，y），加上尺度信息，離合出一個三元連續函數（1），對函數（1）求導得到導函數，令導函數等于0得到校正后的極值點坐標尺度值（2）。

去除低對比度點是除去D（x）和D（X）小于某個閾值的點。邊緣響應點是滿足條件（5）的點。

式（5）中H矩陣的跡Tr（H）=Dxx+Dyy，行列式|H| =Dxx*Dyy-Dxy*Dxy.r是H的較大特征值與較小特征值的比值，David Lowe在論文中推薦為10。

1.4 計算主方向和描述符。主方向和描述符均屬于特征點及其領域點的灰度變化的梯度值的一個統計量，特征點及其領域點的梯度值和方向由（6）計算。

區別在于，主方向的統計劃分區間僅為方向，而描述符的統計劃分區間除了方向還有子領域的縱橫坐標；主方向的方向區間一般為36個（每區間10度），而描述符的為8個（每區間45度），描述符的方向需要進行旋轉，旋轉大小為主方向大小；主方向為最大梯度值對應的方向，描述符向量為統計的各梯度值。

2 基于CUDA的SIFT并行性分析設計

顯卡端業務數據用CUDA數組cudaArrayt存儲。由于在cudaArrayt上結合cudaTextureObjectt和 cuda-SurfaceObjectt有如下優勢：a.數據讀寫性能遠遠高于直接把數據存儲在顯卡的全局內存；b.能在硬件上自動進行雙線性插值；c.能在硬件上自動把超出邊界的下標值校正為邊界值；d.方便坐標值計算。

（1）構建高斯金字塔。計算卷積核及其半徑由于計算量少在CPU段實現，高斯模糊分行列兩次進行，每個線程塊負責一行或一列的像素點模糊，線程和線程塊均組織為線性結構。在圖像進行降采樣（圖像長寬都縮小一半）時，每個線程負責算得一個降采樣后的像素點，每個線程塊負責處理連續的像素點，線程和線程塊均組織為線性結構。

（2）構建高斯差分金字塔。每個線程負責一個差分點的計算，線程塊組織成二維結構，一個線程塊處理一組連續的點，第二個維度代表一個高斯差分金字塔一組中的一層，一個高斯差分組將一次得到。

（3）尋找極值點。線程組織結構與構建高斯差分金字塔類似，每個線程探測一個差分點是否為極值點，如果是極值點則采用原子操作將全局計數器累加。

（4）宏觀流程。前期工作均是按照高斯組Octave進行，每組將產生大量極值點。按照David Lowe算法，前后期都分別對各組金字塔建立，極值點精選，計算主方向和描述符。這種方式對于串行執行有一些好處，在處理后一組時就可以釋放前一組的大部分數據。但在并行算法中，這樣并行度會大大降低，特別是在較后組圖片大小較小時，每組檢測出的極值點不多。最重要的是，每次計算極值點之后，精選極值點之后，計算主方向之后，都必須將數據從設備端（顯存）將數據copy到CPU端，因為后期的CUDE核函數線程配置要用到前期的探測到的特征數（而CPU和GPU之間數據傳輸極度影響性能）。這樣，主機和設備端的數據I/O時間復雜度為O（log2（min（width，height）））。因而，本文重新設計計算流程，精選極值點時，前期的全部組的計算都應結束，這樣一則增加后期運行的并行度，二則把IO時間復雜度降為O（0）。由于數據在顯存和主存間的傳輸帶寬遠遠小于顯存和顯存之間的數據傳輸帶寬，這將大大減少數據傳輸時間。

圖2 串并行方式比較

（5）執行和數據I/O的并行化。每張圖片利用顯卡進行SIFT特征檢測時，必然前期要把數據上傳到設備端，后期處理結束要將結果傳輸回CPU端。由于SIFT往往用于多張圖片的特征點檢測，因而利用cudaS-tream實現數據I/O和執行并行。如圖4所示，使用此機制后 ，程序的運行時間由（執行時間+I/O時間）降為（執行時間+I/O時間/流的數量），數據傳輸時間得到了有效的隱藏，在實際編程時，要向設備端上傳數據前或從設備端返回數據后，各個流均進行同步，具體而言，包括在上傳灰度值到顯存之前，返回極值點個數到主機端之后，返回精選后極值點個數之后，返回計算主方向特征點個數之后，以及返回最終結果之后（開始使用檢測到的SIFT特征點之前）。

（6）精選極值點。一個線程處理一個極值點，線程和線程塊均設計為線性結構。計算過程中的向量矩陣臨時變量使用共享內存（shared）。

（7）計算主方向描述符。線程組織結構同上一步。計算過程中重量級變量均使用共享內存（shared），如描述符的128維向量，特征點方向的36個統計值等。

圖3 左：CPU版本SIFT；右：GPU版本實驗圖像分辨率：4416×2480顯示的特征點數占0.88%

（8）三級并行說明。在3.1，3.2和3.3中每個線程處理一個像素點，3.6和3.7中每個線程處理一個極值點或特征點，這屬于第一級并行，這種并行是GPU加速方案的共性，限于GPU開始發展的硬件限制，最初的GPU加速方案大都僅做到了這一級并行度；3.4將需多次進行的針對不同數據的極值點精選，特征點主方向計算和描述符計算縮減為一次針對一張圖片的所有數據的，這不但減少了數據傳輸次數，也提高了計算并行度，這是本方案的二級并行；3.5實現了對多張圖片同時檢測特征點的并行，不但可以提高計算的并行度，也能讓數據傳輸和計算同時進行，隱藏了數據傳輸時間，是第三級并行。

3 實驗結果分析

如圖2所示，CPU版本與GPU版本的運行結果是一致的（特征點相差1是由于GPU的float類型精度比CPU版本稍低引起的，特征點顯示不同是由于都只顯示了很少部分），差別在于運行速率。

圖表1：縱軸表示GPU并行加速比，橫軸表示單張圖片的特征點數，單張圖片特征點數量變化直接通過縮小圖片分辨率得到。

從圖表1可知：當圖片分辨率小，特征點數目較少時，單張圖片加速比很小，這時同時處理多張圖片加速比會提高，但圖片量增加到一定程度之后加速比保持不變，當圖片分辨率較大時，同時處理多張圖片和單張圖片加速比幾乎一致，主要是受GPU內存和計算資源限制。下一步的工作是提高顯存使用率以及破除實現中的大量原子操作，以進一步提高加速比。

圖5

[1]David G.Lowe.Distinctive Image Features from Scale-Invariant Keypoints[C].Canada:Computer Science Department University of British Columbia Vancouver.2004.pp.1-28

[2]Nabeel Khan，Brendan McCane，Steven Mills.Better than SIFT[C].New Zealand:Machine Vision and Applications，2015.

[3]Zddhub.SIFT算法詳解.Published Blog:http://blog.csdn.net/zddblog/article/details/7521424，2012.

[4]Marten Bjorkman.A CUDA Implementation of SIFT for NVidia GPUs.https://github.com/Celebrandil/CudaSIFT.

[5]占正鋒.基于GPU的SIFT立體匹配算法研究[D].黑龍江：哈爾濱工業大學機電工程學院，2014.7:23-42.

[6]NVIDIA.CUDA C Best Practice Guide，March 2015.pp.31-67:http://developer.nvidia.com/cuda-downloads.

An Improved Algorithm of the Screen Space Ambient Occlusion

DENG Bo-sheng
（College of Computer Science，Sichuan University，Chengdu 610065）

SIFT is a fundamental algorithm in the field of Computer Vision.From the comprehensive evaluation,so far,SIFT is still the most valuable feature detection and description algorithm.Presents a three-level parallel solution to the time-consuming problem in SIFT feature extracting,refers to others parallel computation methods proposed by many scholars and researchers,with the implement and experiment on the platform of CUDA,summarizes its algorithm theory and experiment experience.Experimental results show that, compared with the CPU-based implement,this solution improves its performance radically,and the speedup ratio increases together with the addition of images or SIFT feature points.

SIFT;CUDA;Three-Level Parallel;Speedup

1007-1423（2017）09-0054-04

10.3969/j.issn.1007-1423.2017.09.014

鄧伯勝（1989-），男，四川資中人，在讀碩士研究生，研究方向為計算機圖形學、數字圖像處理、并行計算

2017-02-06

2017-03-10