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

關(guān)鍵詞:特征提取; 描述符; SIFT; SIFT GPU

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 等人在總結(jié)現(xiàn)有基于局部不變量技術(shù)的特征提取方法的基礎(chǔ)上提出的 SIFT (Scale-Invariant Feature Transform)算法是一種提取圖像局部特征的算法[1]，SIFT算法對(duì)圖像間存在縮放、旋轉(zhuǎn)、平移等幾何形變及噪聲、光照變化等圖像變化因素有非常好的穩(wěn)定性，在圖像匹配、目標(biāo)識(shí)別、遙感影像配準(zhǔn)等領(lǐng)域得到了很好的應(yīng)用。但該算法復(fù)雜性較高，在一般的應(yīng)用中算法的實(shí)現(xiàn)都依賴于CPU完成，會(huì)耗費(fèi)大量的CPU周期，很難達(dá)到實(shí)際應(yīng)用中實(shí)時(shí)性的要求。與此同時(shí)，隨著可編程圖像處理器GPU的不斷走向成熟，當(dāng)前的GPU已經(jīng)具有了很強(qiáng)的并行計(jì)算能力，浮點(diǎn)運(yùn)算能力甚至可以達(dá)同代CPU的10倍以上，尤其是Nvidia公司的CUDA(Compute Unified Device Architecture，統(tǒng)一計(jì)算設(shè)備架構(gòu))結(jié)構(gòu)的推出，使得GPU具有了更好的可編程性，這種可編程能力使其對(duì)一些圖像處理操作進(jìn)行加速成為可能[2]。本文通過實(shí)驗(yàn)對(duì)傳統(tǒng)的SIFT算法實(shí)現(xiàn)與利用GPU實(shí)現(xiàn)SIFT算法原理進(jìn)行了分析闡述，并通過實(shí)驗(yàn)對(duì)兩種方式的實(shí)現(xiàn)結(jié)果進(jìn)行了對(duì)比分析。

1 SIFT算法原理

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

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

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

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

(1)

將DoG尺度空間每個(gè)點(diǎn)與其相鄰尺度和相鄰位置的26個(gè)點(diǎn)逐個(gè)進(jìn)行比較，以確保在尺度空間和二維空間檢測(cè)到極值點(diǎn)。

(2) 確定關(guān)鍵點(diǎn)位置。通過擬合三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度(達(dá)到亞像素精度)，同時(shí)根據(jù)曲面擬合的方法對(duì)關(guān)鍵點(diǎn)進(jìn)行進(jìn)一步的精確定位，同時(shí)剔除對(duì)比度低的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)(因?yàn)镈oG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng))。

(3) 關(guān)鍵點(diǎn)方向分配。以關(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向，直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。

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

2 SIFT算法的GPU實(shí)現(xiàn)

2.1 GPU概述

GPU是一種針對(duì)圖形進(jìn)行處理的專用處理器，這種圖形處理器強(qiáng)大的并行處理能力和可編程流水線，使得用流處理器處理非圖形數(shù)據(jù)成為可能。特別是在面對(duì)單指令流多數(shù)據(jù)流(SIMD)且數(shù)據(jù)處理的運(yùn)算量遠(yuǎn)大于數(shù)據(jù)調(diào)度和傳輸?shù)男枰獣r(shí)，通用圖形處理器在性能上大大超越了傳統(tǒng)的中央處理器應(yīng)用程序，因此GPU非常適合于高效率低成本的高性能并行數(shù)值計(jì)算[2]。

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

2.2 SIFT GPU實(shí)現(xiàn)過程

利用GPU技術(shù)實(shí)現(xiàn)David Lowe的SIFT算法，算法中有多個(gè)步驟是由GPU以并行計(jì)算的方式進(jìn)行[5]，如下:

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

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

(3) 關(guān)鍵點(diǎn)檢測(cè)(亞像素和亞尺度級(jí)的定位)。

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

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

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

圖1 SIFT GPU實(shí)現(xiàn)流程圖

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

關(guān)鍵點(diǎn)位置、尺度將在CPU中恢復(fù)。由于將儲(chǔ)存在紋理存儲(chǔ)器的梯度金字塔回讀到CPU需要花費(fèi)大量的時(shí)間，因此隨后的過程在GPU上也同時(shí)運(yùn)行。關(guān)鍵點(diǎn)附近的梯度向量被另一個(gè)片段程序進(jìn)行高斯加權(quán)并累加建立方向直方圖。隨后方向直方圖被回讀到CPU，并且檢測(cè)直方圖的峰值，確定關(guān)鍵點(diǎn)方向。這是因?yàn)樵贕PU上檢測(cè)直方圖的峰值并確定關(guān)鍵點(diǎn)方向所花費(fèi)的時(shí)間超過通過一個(gè)小的回讀把數(shù)據(jù)傳遞到CPU上進(jìn)行計(jì)算的時(shí)間。

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

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

3 實(shí)驗(yàn)與結(jié)果

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

圖2顯示的是不同像素大小的5組的圖像分別使用標(biāo)準(zhǔn)SIFT算法與SIFT GPU進(jìn)行特征提取的實(shí)現(xiàn)結(jié)果(每幅圖像左圖為標(biāo)準(zhǔn)SIFT算法實(shí)現(xiàn)，右圖為SIFT GPU實(shí)現(xiàn))，同時(shí)對(duì)兩種方法的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了整理，表1列出了5組圖像分別通過標(biāo)準(zhǔn)SIFT算法與SIFT GPU實(shí)現(xiàn)時(shí)的對(duì)比數(shù)據(jù)。

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)表

圖像圖像大小

標(biāo)準(zhǔn)SIFT算法SIFT GPU

特征點(diǎn)/個(gè)耗時(shí) /ms特征點(diǎn) /個(gè)耗時(shí) /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

實(shí)驗(yàn)結(jié)果分析:

(1) SIFT GPU算法檢測(cè)的特征點(diǎn)略多于經(jīng)典SIFT算法實(shí)現(xiàn)，這是由于算法的參數(shù)設(shè)置中門限的設(shè)定略有不同造成的。

(2) 對(duì)同一副圖像進(jìn)行特征點(diǎn)檢測(cè)時(shí)，可以發(fā)現(xiàn)隨著圖像越大越復(fù)雜，計(jì)算量越大，SIFT GPU方法比經(jīng)典SIFT方法的計(jì)算速度提高的幅度越大，如試驗(yàn)中處理300×211圖像時(shí)只有接近3倍的加速，而在處理1 600×1 200圖像時(shí)甚至可達(dá)近15倍的加速比，極大地提高了SIFT算法應(yīng)用中的實(shí)時(shí)性。

(3) 處理不同的圖像時(shí)，在特征點(diǎn)相近的情況下SIFT GPU方法比經(jīng)典SIFT方法的計(jì)算速度可提高達(dá)6~10倍。

圖2 標(biāo)準(zhǔn)SIFT算法實(shí)現(xiàn)與SIFT GPU實(shí)現(xiàn)對(duì)比圖

4 結(jié) 語

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

參考文獻(xiàn)

[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邊緣檢測(cè)算法[J].光電工程，2009，36(1):8-12.

[3]李曉明，鄭鏈，胡占義.基于SIFT特征的遙感影像自動(dòng)配準(zhǔn)[J].遙感學(xué)報(bào)，2006，10(6):885-892.

[4]王國(guó)美，陳孝威.SIFT特征匹配算法研究[J].鹽城工學(xué)院學(xué)報(bào):自然科學(xué)版，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編程模型的應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2008，36(12):177-180.