基于GPU的SIFT算法耗時改進研究

文君城

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

0 引言

在圖像配準算法中，主要有分為兩大類的配準方法：基于區域和基于特征的圖像配準。在基于區域的圖像配準方法中，可以分為基于空間域和基于變換域這兩大類，基于空間域的配準方法的思想是，利用圖像的灰度信息，通過某種查找算法，來確定一個變換模型可以使兩圖像間的相似區域的相似性測度達到最大。這種思想的算法優點是操作簡單，而問題是首先計算量極大，需要以全圖做相似性測度估計，并且受噪聲的影響很大且不能解決旋轉、縮放等問題；基于變換域的算法思想則是，根據傅里葉變換的平移不變性，將空間域上的像素的平移轉換到了頻域上相位的平移，該類算法優點是相對基于空間域的配準算法，解決了旋轉和尺度縮放的問題，但是缺點則是其適用范圍有限，一般對配準圖像的重合度要求較高，且實現較為復雜。

基于特征的配準算法以其適用范圍的廣泛性、更高的魯棒性以及更快的計算速度，成為如今更為主流的配準算法。與基于區域的算法相比，基于特征的配準算法不需要使用到圖像的全部信息，只需要使用到諸如輪廓、角點或是特征點的部分信息，故而計算量大為降低。其中尺度不變特征變換（SIFT）算法[1～2]以其高魯棒性、穩定性和強適應性，成為了如今圖像配準算法中使用最為廣泛的算法，諸多改進算法諸如PCA-SIFT[3]、Harris-SIFT[4]乃至SURF[5]算法，都是基于SIFT算法的思想而提出。針對SIFT算法計算量大并且具有較高的時間復雜度的問題，提出一種降低時間復雜度及運算量的改進SIFT算法。實驗結果表明，該改進算法在具有較高的魯棒性的前提下，運行速度大為提升。

1 SIFT算法介紹

SIFT算法的思想是，通過降采樣和高斯函數構造尺度空間，再在差分金字塔中提取潛在極值點作為特征點并去除干擾點，根據特征點鄰域內的像素的梯度作為特征點的描述符，最后根據計算特征向量的歐氏距離作為匹配的特征點對，該特征點具有尺度不變性、旋轉不變性，以及光照不變性，是SIFT算法的主要優點。下面簡單介紹一下SIFT算法的實現。

1.1 尺度空間中檢測關鍵點

SIFT算法通過對圖像降采樣，并且使用高斯函數[6]G(x ,y,σ ) 對圖像 I(x ,y)做卷積，構建圖像尺度空間L(x ,y,σ )，公式如下：

其中：

σ0是高斯正態分布的標準差初始值，一般建議取值為 1.6；t∈[0 , …，T-1]，T是高斯圖像金字塔的總級數，并且T=log[ ]min(X,Y)-2，X×Y為原圖像尺寸；，s為每級金字塔的尺度空間層數，并且s>3。

通過對圖像降采樣和高斯函數卷積形成高斯金字塔后，在高斯金字塔每一級中相鄰尺度圖像兩兩相減，得到高斯差分金字塔（DoG），即：

其中 fi，i∈[0,s]，是尺度空間圖像，最后構建出級數為T，每級包含有s-1層圖像的DoG高斯差分金字塔。

特征點的檢測即是在DoG高斯差分金字塔中進行的。每一個像素點會和它上下相鄰3×3范圍像素點內所有相鄰點作比較，當某像素點的灰度值為該范圍內的極值時，該點則為潛在特征點。再將位于曲率較低的邊緣特征點剔除，通過擬合特征點所在的行和列的像素灰度值曲線，最終確定特征點的實際位置，得到最終的特征點。如圖1所示。

圖1特征點檢測

1.2 特征點描述

確定特征點的位置之后，為使其保證旋轉不變性，將為特征點指定方向參數。SIFT算法中，首先在特征點附近的一個圓形鄰域內（一般選取3×1.5σ為半徑）計算每個點的梯度和角度，根據角度作為橫坐標計算直方圖，縱坐標為幅值的疊加，選取縱坐標最大的方向作為特征點的主方向；再選取特征點16×16范圍內為鄰域，再將16×16鄰域劃分為16個4×4的子領域，在16個子領域內以45度為間隔，統計8個角度區間內的梯度幅值之和作為子領域的種子點，如圖2所示；16個種子點各有8個方向，共構成8×16共128維的特征點描述符，如圖3所示。最后對128維的特征向量歸一化，去除光照的影響以保證光照不變性。

圖2由特征點鄰域梯度信息生成種子點

圖3特征點128維描述符

2 改進的SIFT算法

為確定在SIFT算法中，在各個算法步驟具體哪些步驟最為耗時，通過將算法步驟分為：尺度空間建立、極值點檢測、關鍵點主方向分配、特征描述4個步驟，并選取了3種不同分辨率的3張圖片，經過實驗，統計了各個步驟不同分辨率圖片情況下的耗時在總耗時中的平均占比情況，如表1。

表1不同分辨率下SIFT算法各步驟耗時對比

從表中可以看出，隨著分辨率的增大，可檢測到的特征點數成倍上升，耗時也在成倍的增加。SIFT算法具體實現步驟中，最為耗時的步驟是極值點檢測（包含去除邊緣響應點及通過擬合函數來確定特征點的位置及尺度）的過程，占了總耗時一半以上的時間。而相對來說，SIFT算法中尺度空間的建立和特征點的128維描述符也是比較耗時的步驟，兩步驟耗時占比也占了40%以上。通過對算法實現的分析，大致造成以上情況的原因如下：

原因1：構建尺度空間具有一定的復雜性，需要不斷的降采樣和高斯卷積，構建的層數越多，耗時也越多。

原因2：關鍵點是由DoG空間的局部極值點組成的，而關鍵點的初步探查是通過對同一組內各個DoG相鄰兩層圖像之間的比較完成。為了尋找DoG函數的極值點，每一個像素點都要和它所有相鄰的點比較，看其是否比它的圖像域和尺度域相鄰的點大還是小。而這映射到算法實現上，則是通過一個三重循環來實現的，需要分別遍歷相鄰上下兩層及各層3×3區域內所有像素點，故而是個時間復雜度很大且計算量龐大的實現過程，耗時嚴重。

原因3：為了保證旋轉不變性，SIFT中的描述子使用在關鍵點尺度空間內4×4的窗口中計算8個方向的梯度信息，共4×4×8=128維的向量來表征，而分辨率越大，圖像信息越復雜，可檢測到的特征點也就越多，為每一個特征點分配一個128維的特征向量描述符計算量過大，造成耗時嚴重。

針對上述SIFT算法在實現過程中存在的問題，提出一種基于GPU的SIFT改進算法，具體改進措施為：

（1）針對SIFT算法中構建尺度空間及極值點檢測計算量大的問題，基于GPU強大的并行計算能力，提出使用GPU加速尺度空間的建立及在差分金字塔中檢測極值點兩步驟的實現。

（2）針對SIFT算法中，特征點的128維描述子維數過高，計算量過大的問題，提出一種以帶權值的圓形梯度計算區域取代原算法中的4×4方形區域，將128維描述子降為64維描述子，在保證一定旋轉不變性前提下降低數據量以提升算法運行效率。

2.1 SIFT算法GPU實現

（1）GPU 簡介

圖形圖像處理單元GPU（Graphic Processing Unit），NVIDIA公司于1999年發布GeForce256圖形處理芯片的時候首次提出了GPU的概念，是由硬件實現的，一個專門的圖形的核心處理器。相較于CPU而言，CPU的架構設計注重的是程序執行的效率，大部分為控制器和寄存器，擅長的是如操作系統、通用應用程序這類擁有復雜的指令調度、循環、分支或是邏輯判斷等復雜的程序任務。而GPU的架構則是面向適合于矩陣類型的數值計算而設計的，擁有更多的ALU（Arithmetic Logic Unit，邏輯運算單元）用于數據處理，其架構設計復雜度遠低于CPU，其最大的優勢是處理大量同類型數據的密集計算，例如圖形數據的矩陣運算[7]。CPU在執行計算任務時，同一時刻只會處理一個數據，不存在真正意義上的并行。而GPU具有多個處理器核，可以同時并行處理上千個沒有邏輯關系的數值計算線程。GPU具有強大的浮點數編程和計算能力，在計算吞吐量和內存帶寬上遠超CPU，即當算法中具有大量無邏輯聯系的密集計算，且可并行處理的計算部分時，通過使用GPU加速，可以大大提升算法的運算效率。

（2）GPU加速SIFT算法過程

由表1分析所得SIFT算法各步驟的耗時情況，且由于GPU加速的數據處理并行條件約束，并不是所有步驟都適用于采取GPU進行加速，故將采取GPU+CPU混合實現的方式[8]，通過GPU加速SIFT算法中尺度空間的創建及極值點的檢測過程，再將處理數據傳回CPU，進行主方向分配，再通過降維的特征點描述子算法獲取描述符。具體實現流程如下。

首先圖像上傳GPU設備端，分析構建尺度空間并行性可知，假設高斯金字塔有s組，每組有o層的圖像，首先對每層圖像的高斯卷積是互不影響的，可以并行實現；其次，每一組的各層圖像降采樣也只依賴于第0層的第一張圖像尺寸，故對每層圖像的降采樣也可并行執行；所以在構建高斯金字塔時，對每組每層的降采樣及模糊操作都可GPU加速處理。得到高斯金字塔后，由于每個差分金字塔的構建過程只跟其相鄰上下兩層有關，因此也可并行化差分金字塔構建。具體實現步驟為：線程格按二維地址排序，每個線程格（block）含16×16個線程，給圖像每一像素綁定一個線程ID，每一像素都和高斯核的所有元素（由外部輸入）相乘并累加權值，而多次使用的變量使用共享內存進行緩存，將得到的高斯模糊結果存入全局存儲器中。此后，按照高斯金字塔不同層和不同組，交由不同的線程塊（block）處理，并行計算得到各個像素的差分值后，最后整合所有block的值，得到差分金字塔，再將每層圖像劃分為16×16的塊，而線程塊對應16×16的結構設計，以減少循環次數，而對圖像不是16×16的倍數的情況按補0處理。這樣每一個線程對應求取一個極值點。最終將極值點傳回CPU端。

考慮到對極值點的過濾、對關鍵點的定位以及對關鍵點主方向的分配，GPU端對于處理分支、判斷等邏輯語句的效率較低[9]，故需將極值點檢測結果傳回CPU端，而CPU端和GPU端之間數據傳輸也是一個較為耗時的操作，為保證CPU端及GPU端只需一次數據傳輸以減少時間損耗，提出一種降維的特征點描述子算法來優化SIFT算法的效率。

2.2 改進的特征描述符

借鑒于SURF算法中基于圓形的特征描述符的區域選擇，且由于圓形區域自帶的良好的旋轉不變性[10]，在獲得關鍵點特征描述符的過程中，提出一種采用圓環形取代原SIFT算法中方形區域的方法以降低描述符的維數達到降低計算數據量，減少獲取特征描述符的耗時。

圖5圓形的特征描述構造

如圖5所示，考慮到所選取的環形區域對特征點的描述貢獻，距離特征點越近的區域描述特征點的貢獻越大[11]，故在基于16×16的關鍵點鄰域內，考慮采用（3，2，2，1）的環數構造，距離關鍵點最近的局域設置為3環，而距離關鍵點最遠的區域設置為1環，由此劃分為4個環形區域。具體實現步驟如下：

（1）建立以關鍵點為中心的16×16像素點領域區域，按（3，2，2，1）的環數構造劃分為 4 個環形區域。

（2）以36度為間隔，統計4個環形區域10個方向的梯度累加值，得到4×10共40維的特征向量。

（3）為了降低光照對特征向量的影響，最終對其做歸一化處理，使用公式為：

其中di為各特征向量，D為歸一化后的向量。

（4）考慮到可能存在大梯度的異常特征向量影響，設定一個閾值，對梯度差值大于閾值的描述符做舍棄處理，經過實驗，閾值取經驗值0.12。

3 實驗結果

為了檢測改進算法的特征檢測效果，以及改進算法的特征檢測在速度上的提升，實驗主要通過對三組不同分辨率的圖片進行改進算法的特征檢測實驗，與原算法對比其特征檢測效果及具體耗時情況。

圖6不同分辨率實驗組圖

實驗首先統計了改進算法各步驟耗時情況，并與原算法各步驟耗時進行了比較，如表2所示。

表2不同分辨率改進算法與原SIFT算法對比

實驗結果表明，改進算法檢測到的特征點數量相比于原算法，由于對算法相關參數并未改變，所以相差無幾，這說明改進算法繼承了原算法對圖像特征檢測方面的優越性，保證了改進算法的特征檢測精度。其次，耗時情況上，使用GPU加速的建立尺度空間和極值點檢測兩步驟耗時降低最為明顯，相比于原算法表1，平均加速比達到了20倍以上。而對于改進的特征描述耗時，大約與原算法相比，有近一倍的提升。體現在總耗時上，改進算法總耗時相比于SIFT原算法，有5倍以上加速比。

其次，實驗針對特征檢測描述效果，也做了相應對比實驗，如圖7所示：

圖7不同分辨率下特征描述對比

通過實驗，首先改進算法的特征描述對于大梯度下的異常特征向量有一個很明顯的區分。其次，改進算法的特征描述較原算法而言，對于輪廓的描述稍有不足，但仍有不錯的局部描述效果，且在耗時情況上有一個很大的提升。

4 結語

針對SIFT算法計算量大，耗時嚴重的問題，提出了一種基于GPU和降低描述子的改進算法。首先通過提取出SIFT算法中可并行部分，使用GPU加速該部分計算來提升運算速度，其次，改進了特征點的描述構造，采用圓形取代方形，降低了特征描述維度來加快運算速度。實驗表明，本改進算法在保證特征點檢測精度的前提下，稍降低了特征描述精度，但在耗時方面大為提升，保證了原算法大致魯棒性的情況下，本算法具有了更快速的特點。