基于GPU的SIFT特征提取算法研究

摘 要:傳統SIFT算法的優化和實現都是針對常用處理器(CPU)提出的，處理速度慢，實時性很難得到保證。通過實現基于NVIDIA公司CUDA架構圖形處理器(GPU)的SIFT特征提取算法，優化了數據存儲結構，提高了數據訪問效率。實驗結果表明，基于GPU的SIFT特征提取算法充分利用GPU的并行處理能力，計算速度提高幅度明顯，圖像越大越復雜，提高的幅度越大，處理1 600×1 200圖像時甚至可達近15倍的加速比，極大地提高了SIFT算法在實際應用中的實時性。

關鍵詞:特征提取; 描述符; SIFT; SIFT GPU

中圖分類號:TP311文獻標識碼:A

文章編號:1004-373X(2010)15-0041-03

Study of SIFT Feature Extraction Algorithm Based on GPU

WANG Rui1，2， LIANG Hua1， CAI Xuan-ping1

(1.College of Electric Science Engineering， National University of Defense Technology， Changsha 410073，China;

2.Seventh Detachment，Corps Command of CAPF， Urumchi 830000，China)

Abstract: The traditional SIFT algorithm realized by CPU has low processing speed， whose real-time processing performance is difficult to obtain. The SIFT feature extraction algorithm based on graphic processing unit(GPU) of compute unified device architecture(CUDA) from NVIDIA corporation， which optimized the data storage structure and enhanced the data accessing efficiency. Experimental results show that the GPU-based SIFT feature extraction algorithm takes full advantage of the parallel processing ability of the GPU， whose calculation speed is greatly improved and nearly 20 times speedup rate can be acquired for an image with the resolution of 1 600×1 200. By virtue of GPU， the real-time processing ability of SIFT algorithm can be greatly improved in practical application.

Keywords: feature extraction; descriptor; SIFT; SIFT GPU

0 引 言

Lowe 等人在總結現有基于局部不變量技術的特征提取方法的基礎上提出的 SIFT (Scale-Invariant Feature Transform)算法是一種提取圖像局部特征的算法[1]，SIFT算法對圖像間存在縮放、旋轉、平移等幾何形變及噪聲、光照變化等圖像變化因素有非常好的穩定性，在圖像匹配、目標識別、遙感影像配準等領域得到了很好的應用。但該算法復雜性較高，在一般的應用中算法的實現都依賴于CPU完成，會耗費大量的CPU周期，很難達到實際應用中實時性的要求。與此同時，隨著可編程圖像處理器GPU的不斷走向成熟，當前的GPU已經具有了很強的并行計算能力，浮點運算能力甚至可以達同代CPU的10倍以上，尤其是Nvidia公司的CUDA(Compute Unified Device Architecture，統一計算設備架構)結構的推出，使得GPU具有了更好的可編程性，這種可編程能力使其對一些圖像處理操作進行加速成為可能[2]。本文通過實驗對傳統的SIFT算法實現與利用GPU實現SIFT算法原理進行了分析闡述，并通過實驗對兩種方式的實現結果進行了對比分析。

1 SIFT算法原理

SIFT算法是一種提取圖像局部特征的算法，它通過在尺度空間尋找極值點，提取圖像的位置、尺度、旋轉不變量，并以此來構造圖像的特征描述符。具體過程[1，3-4]如下:

(1) 建立圖像高斯金字塔及高斯差分金字塔(DoG)，檢測空間極值點。將輸入圖像通過不同尺度(σ)的高斯核函數連續濾波和下采樣，形成高斯金字塔圖像，然后利用不同尺度的高斯差分核與圖像卷積生成高斯差分金字塔。

D(x，y，σ)=[G(x，y，kσ)-G(x，y，σ)]I(x，y)

=L(x，y，kσ)-L(x，y，σ)

(1)

將DoG尺度空間每個點與其相鄰尺度和相鄰位置的26個點逐個進行比較，以確保在尺度空間和二維空間檢測到極值點。

(2) 確定關鍵點位置。通過擬合三維二次函數以精確確定關鍵點的位置和尺度(達到亞像素精度)，同時根據曲面擬合的方法對關鍵點進行進一步的精確定位，同時剔除對比度低的關鍵點和不穩定的邊緣響應點(因為DoG算子會產生較強的邊緣響應)。

(3) 關鍵點方向分配。以關鍵點為中心的鄰域窗口內采樣，并用直方圖統計鄰域像素的梯度方向，直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向，即作為該關鍵點的方向。為每個關鍵點指定方向參數，使算子具備旋轉不變性。

(4) 生成SIFT描述符。對任意一個關鍵點，在其所在的尺度空間(即高斯金字塔結構的某一層)，取以關鍵點為中心的16像素×16像素大小的鄰域，再將此鄰域均勻地分為4×4個子區域(每個子區域大小為4像素×4像素)，對每個子區域計算梯度方向直方圖(直方圖均勻分為8個方向)。然后，對4×4個子區域的8方向梯度直方圖根據位置依次排序，這樣就構成了一個4×4×8=128維的向量，該向量就是SIFT描述符。

2 SIFT算法的GPU實現

2.1 GPU概述

GPU是一種針對圖形進行處理的專用處理器，這種圖形處理器強大的并行處理能力和可編程流水線，使得用流處理器處理非圖形數據成為可能。特別是在面對單指令流多數據流(SIMD)且數據處理的運算量遠大于數據調度和傳輸的需要時，通用圖形處理器在性能上大大超越了傳統的中央處理器應用程序，因此GPU非常適合于高效率低成本的高性能并行數值計算[2]。

GPU數值計算的優勢主要是浮點運算，它執行浮點運算快是靠大量并行計算，GPU具有比CPU高一個數量級的浮點性能，但是這種數值運算的并行性在面對程序的邏輯執行時毫無用處。總的來說，CPU擅長:操作系統、系統軟件、應用程序、通用計算、系統控制等;游戲中人工智能、物理模擬等;3D建模-光線追蹤渲染;虛擬化技術——抽象硬件，同時運行多個操作系統或者一個操作系統的多個副本等。GPU擅長:圖形類矩陣運算，非圖形類并行數值計算，高端3D游戲。在1臺均衡計算的計算機系統中，CPU和GPU還是各司其職，除了圖形運算，GPU主要集中在高效率低成本的高性能并行數值計算，幫助CPU分擔這種類型的計算，提高系統這方面的性能。

2.2 SIFT GPU實現過程

利用GPU技術實現David Lowe的SIFT算法，算法中有多個步驟是由GPU以并行計算的方式進行[5]，如下:

(1) 輸入彩色圖像的灰度轉換，對輸入圖像的降采樣和升采樣。

(2) 創建高斯圖像金字塔(灰度、梯度、差分高斯圖像)。

(3) 關鍵點檢測(亞像素和亞尺度級的定位)。

(4) 采用GPU直方圖約簡產生壓縮特征列表[6]。

(5) 計算特征方向和描述子。

但不是所有的步驟都能在GPU上快速實現，因此整個實現過程處理采用CPU和GPU混合實現的方式，具體實現過程[7-8]如圖1所示。

圖1 SIFT GPU實現流程圖

圖像輸入后，利用GPU分步高斯卷積片段程序加速高斯金字塔的構建，并將圖像(象)灰度、梯度和高斯差分金字塔存儲在RGBA紋理存儲器內，以便于利用片段程序進行并行向量計算。隨后在圖形硬件內對高斯差分金字塔所有的像素進行并行計算，檢測局部極值，確定關鍵點。計算關鍵點的主曲率，通過一個2×2的Hessian矩陣計算特征值比率，檢測關鍵點主曲率是否超過設定的閾值，通過二值位圖精確標記關鍵點的位置，尺度。運行另一個片段程序將二值位圖壓縮(32 b)變成 RGBA數據，隨后被回讀到CPU，并同時進行解碼。

關鍵點位置、尺度將在CPU中恢復。由于將儲存在紋理存儲器的梯度金字塔回讀到CPU需要花費大量的時間，因此隨后的過程在GPU上也同時運行。關鍵點附近的梯度向量被另一個片段程序進行高斯加權并累加建立方向直方圖。隨后方向直方圖被回讀到CPU，并且檢測直方圖的峰值，確定關鍵點方向。這是因為在GPU上檢測直方圖的峰值并確定關鍵點方向所花費的時間超過通過一個小的回讀把數據傳遞到CPU上進行計算的時間。

最后一個步驟需要計算 128維的SIFT描述符。這些由16×16的圖像數據塊根據關鍵點的尺度、位置和方向建立SIFT描述符的過程，全部在GPU上進行計算不能夠達到最好的效率，例如:方向直方圖消除量化噪聲。因此將這一步驟在CPU和GPU之間進行分割。重采樣每個特征的梯度向量塊，在GPU上對其進行高斯加權，采樣和加權的梯度向量被傳遞到CPU，隨后計算描述符。因為把整個梯度金字塔傳遞回CPU是不切實際的，而CPU-GPU的分割將使GPU數據的回讀減到最少，并且在GPU上進行紋理的重采樣和融合的運算速度很快，同時能夠產生在一次回讀中就可以傳遞轉移到CPU的壓縮紋理塊，所以采用這種方法。

SIFT GPU在建立高斯尺度空間金字塔和關鍵點定位這一步驟上獲得巨大的加速。包含特征方向的二值位圖被采取32 b壓縮回讀，減少了回讀數據的大小。特征方向和描述符計算被分割在CPU和GPU之間分別計算，在某種程度上把從GPU到CPU的數據轉移減到最少。這些都是提高計算速度的關鍵因素。

3 實驗與結果

本文的實驗平臺采用Windows XP操作系統，CPU為Intel Dual-Core E5300，主頻2.6 GHz，系統內存2 GB;GPU為NVIDIA GeForce 9600 GSO，顯存1 GB。在試驗中兩種方法的DoG函數值門限設定略有不同(經典SIFT算法0.04，SIFT GPU為0.02/3)，其他的主要參數的設置基本相當，需要注意的是在GPU方法中設置參數–lowe，以便使像素的坐標系與Lowe的經典SIFT保持一致。

圖2顯示的是不同像素大小的5組的圖像分別使用標準SIFT算法與SIFT GPU進行特征提取的實現結果(每幅圖像左圖為標準SIFT算法實現，右圖為SIFT GPU實現)，同時對兩種方法的實驗數據進行了整理，表1列出了5組圖像分別通過標準SIFT算法與SIFT GPU實現時的對比數據。

表1 實驗數據統計表

圖像圖像大小

標準SIFT算法SIFT GPU

特征點/個耗時 /ms特征點 /個耗時 /ms

(a)300×21158697925

(b)640×48032736860148

(c)800×6401 4431 2591 79376

(d)1 200×8008351 0311 22293

(e)1 600×1 2003 4213 1735 214217

實驗結果分析:

(1) SIFT GPU算法檢測的特征點略多于經典SIFT算法實現，這是由于算法的參數設置中門限的設定略有不同造成的。

(2) 對同一副圖像進行特征點檢測時，可以發現隨著圖像越大越復雜，計算量越大，SIFT GPU方法比經典SIFT方法的計算速度提高的幅度越大，如試驗中處理300×211圖像時只有接近3倍的加速，而在處理1 600×1 200圖像時甚至可達近15倍的加速比，極大地提高了SIFT算法應用中的實時性。

(3) 處理不同的圖像時，在特征點相近的情況下SIFT GPU方法比經典SIFT方法的計算速度可提高達6~10倍。

圖2 標準SIFT算法實現與SIFT GPU實現對比圖

4 結 語

通過利用當前顯示卡中具備的大量的圖形處理單元，SIFT算法的GPU實現與普通的CPU實現相比，實時性有了很大的提高。但在其實現過程中，仍有多個步驟采用CPU實現或CPU和GPU混合實現的方式;在以后的實際應用編程實現過程中需要進一步嘗試，以尋求一個最優的計算分配方式，使運算速度在現有基礎上得到新的提升。

參考文獻

[1]LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision， 2004，60(2): 91-110.

[2]左顥睿，張啟衡，徐勇，等.基于GPU的快速Sobel邊緣檢測算法[J].光電工程，2009，36(1):8-12.

[3]李曉明，鄭鏈，胡占義.基于SIFT特征的遙感影像自動配準[J].遙感學報，2006，10(6):885-892.

[4]王國美，陳孝威.SIFT特征匹配算法研究[J].鹽城工學院學報:自然科學版，2007，20(2):1-10.

[5]WU Chang-chang. SIFTGPU[CP/OL]. [2007-02-11]. http://www.cs.unc.edu/~ccwu/siftgpu/.

[6]ZIEGLER G. GPU point list generation through histogram pyramids[R/OL]. [2006-06-02]. http://www.mpi-inf.mpg.de/~gziegler.

[7]SINHA Sudipta N， FRAHM Jan-Michael， POLLEFEYS Marc， et al. GPU-based video feature tracking and matching[R]. EDGE 2006， Workshop on Edge Computing Using New Commodity Architectures， Chapel Hill:EDGE， 2006.

[8]FERNANDO Randima. GPU Gems: programming techniques， tips and tricks for real-time graphics[M]. [S.l.]: Addison-Wesley Professional， 2006.

[9]GPGPU. General-purpose computation on GPUs[J/OL]. [2010-07-04]. http://www.gpgpu.org.

[10]錢悅.圖形處理器CUDA編程模型的應用研究[J].計算機與數字工程，2008，36(12):177-180.