楊天天，魯云萍，張為華

（1．江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫214083；2.復(fù)旦大學(xué) 并行處理研究所，上海201203）

一種基于GPGPU的SIFT加速算法*

楊天天1，魯云萍2，張為華2

（1．江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫214083；2.復(fù)旦大學(xué) 并行處理研究所，上海201203）

SIFT是目前應(yīng)用最廣泛的基于局部特征的圖像特征提取算法之一，針對其運行速度制約其應(yīng)用范圍的問題，提出在圖像處理器（GPGPU）上設(shè)計并實現(xiàn)將算法各核心模塊映射到GPGPU的計算單元并針對GPUPU特性進行優(yōu)化的SIFT并行加速算法。測試結(jié)果表明，基于GPGPU的SIFT并行算法相比于原始串行版本達到了118.2倍的加速，吞吐量達到了 7 6.86圖片/s，相比于已有的技術(shù)獲得了明顯的性能提升。

圖像處理器GPGPU；SIFT算法；并行；加速

0　引言

隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)信息量不斷膨脹。根據(jù)Cisco的預(yù)測，到2016年每月產(chǎn)生的數(shù)據(jù)量將超過8萬PB，其中圖像和視頻已經(jīng)成為傳輸和處理的主要數(shù)據(jù)類型。統(tǒng)計數(shù)據(jù)顯示，YouTube網(wǎng)站每分鐘有60 h時長的視頻被上傳，F(xiàn)acebook存儲的圖片量超過2 000億張。如何從這些數(shù)據(jù)中提取有用的信息并進行高效的分析和處理變得越來越重要，各種新型的圖像檢索類應(yīng)用也不斷涌現(xiàn)。

圖像檢索主要分為基于全局特征的算法和基于局部特征的算法?；谌痔卣鞯臋z索算法用一個特征數(shù)據(jù)代表整個數(shù)據(jù)，精確度低，也不能識別兩幅圖像中的相似元素，處理圖像的伸縮和裁剪[1]?；诰植刻卣鞯臋z索算法通常提取成百上千個特征來描述一個圖像或視幀，保證了檢索精度，還能對圖片的變形進行處理。SIFT算法是其中最具代表性的算法之一。而局部特征提取算法要保證處理精度，其處理速度相對緩慢。如何有效提高特征提取算法的處理速度，成為圖像檢索算法需要解決的關(guān)鍵問題之一。

隨著半導(dǎo)體技術(shù)的發(fā)展和多核技術(shù)的普及，各種并行計算系統(tǒng)逐漸成為硬件處理平臺的設(shè)計主流。圖像處理單元GPGPU由于其通用性和可編程性為加速圖像特征提取算法處理速度提供了機會。

結(jié)合圖像特征提取算法面臨的處理速度挑戰(zhàn)，本文設(shè)計實現(xiàn)了一種基于GPGPU的SIFT并行加速算法。首先對SIFT算法的核心模塊進行深入分析，并在此基礎(chǔ)上對各個核心模塊進行了有針對性的細(xì)粒度并行，以適應(yīng)其在GPGPU上處理，然后通過利用GPGPU的特性對算法進行優(yōu)化。最后，通過流水化CPU和GPGPU處理的任務(wù)來進一步提升系統(tǒng)性能。

1　SIFT算法和GPGPU簡介

本節(jié)將簡單介紹SIFT算法的基本處理過程和GPGPU基本結(jié)構(gòu)。

1.1SIFT算法

如何從大量圖像和視頻數(shù)據(jù)中提取有用信息并進行分析和處理變得越來越重要，各種多媒體檢索應(yīng)用不斷涌現(xiàn)。

SIFT(Scale-Invariant Feature Transform)算法是由David Lowe于 1999年首次提出并于 2004年總結(jié)完善的[2]圖像特征提取算法。SIFT算法提取的特征基于物體上的一些局部外觀顯著的特征點而生成，它的檢測器在選擇特征點時，已將圖像縮放等情況考慮進來，而它的描述器在描述每個特征點時都會計算該特征點的方向向量。因此SIFT算法提取的特征與圖像的大小和旋轉(zhuǎn)無關(guān)，對于光線、噪聲和輕微視角改變的容忍度也相當(dāng)高，具有很強的匹配能力。目前SIFT算法已成為當(dāng)前最主流的圖像特征提取算法之一。

SIFT算法首先檢測圖像中的顯著區(qū)域，即相比于周圍的像素變化明顯的部分。在此基礎(chǔ)上結(jié)合特征點周圍的信息對這些特征加以描述。如圖1所示，其算法主要由特征檢測和特征描述兩部分組成。

圖1　SIFT處理流程及各部分所占運行時間的比例

(1)特征檢測：特征檢測的目標(biāo)是對圖像中的顯著區(qū)域的特征點進行定位。為了能對圖像的縮放進行處理，首先建立圖像不同縮放尺寸的高斯金字塔，高斯金字塔由 octave和每個 octave中的 interval兩個層次組成，octave包含一組大小相同的圖層；每個octave中的interval進行不同程度高斯模糊后用于描述不同伸縮范圍下的圖像特征。圖像高斯差金字塔是將高斯金字塔中同一個octave的連續(xù)兩個interval的圖像相減而得到的。最后通過查找金字塔中的極值找到圖像中顯著的特征點；

(2)特征描述：特征描述主要對檢測出來的圖像特征點加以描述形成特征向量。為了提高特征點的描述范圍，特征描述基于特征點及其周圍像素點的信息計算特征點的方向，之后通過對特征點進行特征值的提取，生成特征向量，以完成對特征信息的描述。

為了保證特征點的精確性，SIFT算法通常包含復(fù)雜的處理過程，從而使其具有計算密集的特點。而隨著網(wǎng)絡(luò)帶寬的增加，需處理的數(shù)據(jù)量也不斷增加，已有的串行算法已經(jīng)不能滿足實時處理的要求。

為了給后繼優(yōu)化提供更明確的優(yōu)化方向，本設(shè)計收集了SIFT算法在CPU上串行執(zhí)行時各個階段大致所需要的時間，具體如圖1所示。特征描述所占的時間比例最大，占到超過3/4的時間；特征檢測其次，占到近 1/4的時間；加載圖像和計算灰度圖像只占很少的時間。

1.2GPGPU簡介

隨著圖形處理單元GPGPU性能的快速增長及其可編程性的不斷增強，GPGPU逐漸成為一種主流的計算系統(tǒng)，成為一個具有強大算術(shù)處理能力的并行可編程處理器[3]。

GPGPU的主要廠家 NVIDIA于 2006年引入 Tesla統(tǒng)一圖形和計算體系結(jié)構(gòu)[4]擴展了 GPGPU。以 NVIDIA GeForce 8800 GTX為例，其包含16個流多處理器（SM），每個流多處理器中有 8個流處理器（SP）。流多處理器包含寄存器文件、共享存儲器、共享的指令緩存與數(shù)據(jù)緩存、指令的讀取/分發(fā)單元、特別功能單元和1個雙精度浮點計算單元。

GPGPU作為加速部件已廣泛應(yīng)用于各種計算密集領(lǐng)域。GU L等人[5]在GPGPU上設(shè)計了一個二維和三維的傅里葉變換函數(shù)；CHEN Y等人[6]在GPGPU集群上實現(xiàn)一個大規(guī)模傅里葉變換算法；NAGHMOUCHI J等人[7]使用GPGPU來加速正則表達式的匹配。GPGPU的這種特性也為提升SIFT算法的處理速度提供了可能。

2　GPGPU加速算法

為了提升SIFT算法的處理速度，本文設(shè)計和實現(xiàn)了一種基于GPGPU的加速算法。

2.1算核并行化

GPGPU具有豐富的并行計算資源，適合處理數(shù)據(jù)并行操作，需要根據(jù)SIFT每個階段算核的特點進行有針對性的細(xì)粒度的并行。

SIFT算法的特征檢測階段大多是對圖像進行變換和操作，各個部分之間不存在依賴關(guān)系。對于這部分算法的并行化，可以將圖像劃分成子塊，分到不同的線程塊執(zhí)行。在特征描述階段，主要對檢測的特征點進行操作。這個部分算核的并行化可以以特征點為基本處理單位，由不同的線程塊處理不同的特征點，然后再根據(jù)特征描述具體階段的算法并行劃分。

2.1.1特征檢測的實現(xiàn)

SIFT算法的特征檢測由以下幾個部分組成，各個組成部分并行劃分后，由一個或若干個GPGPU內(nèi)核加以實現(xiàn)：

(1)對圖像縮放形成多個octave：將圖像分成二維的圖像子塊，一個線程塊處理圖像中一個圖像塊。

(2)圖像的高斯濾波：計算圖像的高斯濾波分成兩個步驟：①將圖像分成寬度為W、高度為1的圖像塊，每個圖像塊由一個線程塊處理，線程塊中每個線程負(fù)責(zé)處理圖像塊的一列。W的值可以根據(jù)實際使用的圖像選擇不同的大小。②將圖像分成寬度為1、高度為H的圖像塊，每個圖像塊由一個線程塊處理。通過行列的分別計算，得到的結(jié)果就是高斯濾波后的圖像。

(3)計算圖像高斯差：圖像被分成二維的圖像塊，一個線程塊處理圖像中特定大小(測試中使用16×16)的圖像塊，線程塊中一個線程計算兩個相鄰高斯圖像對應(yīng)一個像素點的差值。

(4)尋找局部極值點：將圖像（上中下3層）分成二維的圖像塊，每個線程塊處理不同的圖像塊。為了記錄哪些點是極值點，使用一個寬度為w（w為圖片寬度）、高度為h/32（h為圖片高度）的二維整數(shù)數(shù)組來進行記錄。每個整數(shù)32位，每一位表示對應(yīng)高度像素點是否為極值點。

(5)計算極值點的實際位置：把極值點分成不同的組，每組由一個線程塊計算，線程塊中每個線程負(fù)責(zé)計算一個極值點的實際位置。

2.1.2特征描述的實現(xiàn)

SIFT的特征描述分為兩部分：計算特征方向和描述特征點。特征點的計算是彼此獨立的，而在計算特征方向和特征描述時，內(nèi)部的計算又可以分成不同的線程，在線程塊內(nèi)部的線程上加以并行：

(1)計算特征方向：一個線程塊負(fù)責(zé)計算一個特征點的方向，一個線程塊包含32個線程，分別負(fù)責(zé)計算32個方向的Bin的值。最后由每個線程塊中的第一個線程負(fù)責(zé)計算出32個方向Bin的最大值，作為特征點的特征方向。

(2)描述特征點：一個線程塊描述一個特征點。在描述一個特征點時，采用的是4×4個方格，每個方格8維柱狀圖，一共128維的特征值向量。一個線程塊中的一個線程負(fù)責(zé)一個方格的柱狀圖的計算。

2.2基于GPGPU特性的優(yōu)化

對SIFT進行有針對性的細(xì)粒度的并行，實現(xiàn)了算法的各個算核在GPGPU的并行處理。為了進一步優(yōu)化算法，可以利用GPGPU的特性進行優(yōu)化。

(1)內(nèi)存和顯存分配優(yōu)化：在GPGPU的處理過程中，需要不停地對輸入圖像進行處理。減少動態(tài)的存儲空間分配的次數(shù)可以有效提高性能。為了降低內(nèi)存和顯存的分配次數(shù)，只有當(dāng)處理第一張圖像或圖像大小改變時才重新進行內(nèi)存或顯存的分配和初始化，只有圖像大小改變或處理完最后一張圖像后才進行釋放。對于存儲特征點的數(shù)組，根據(jù)特征點最大值設(shè)定一個特征點數(shù)上限，數(shù)組大小就固定了，避免了每次處理重復(fù)分配內(nèi)存引入的額外開銷。

(2)針對訪存的優(yōu)化：訪存性能對整體處理性能影響很大。GPGPU的存儲層次復(fù)雜，保證各層訪問的局部性可以達到更好的性能。為此，本設(shè)計的優(yōu)化包括：設(shè)計的內(nèi)核不大，保證指令的局部性，因為由于寄存器具有最快的處理速度，小的內(nèi)核劃分盡可能讓局部變量保存在寄存器中，達到最優(yōu)的訪存效率；一些常量頻繁使用，保存在只讀的常量寄存器中；將線程需要頻繁使用的共享數(shù)據(jù)放到共享存儲器中；由于GPGPU的紋理存儲器可以實現(xiàn)數(shù)據(jù)的二維訪問，通過綁定紋理存儲器提升性能。

2.3CPU與GPGPU的協(xié)同工作

把 SIFT算法最耗時的算核部分交由 GPGPU處理后，各個部分都獲得較大的性能提升。算核通過GPGPU加速后通常可以獲得幾十甚至上百倍的性能提升。而無法交給GPGPU處理的串行部分則不能匹配GPGPU部分的執(zhí)行速度，成為性能的瓶頸。

CPU上的核負(fù)責(zé)對圖像進行預(yù)處理，GPGPU負(fù)責(zé)內(nèi)核的計算。兩部分串行執(zhí)行，將會造成較多的彼此等待，影響整體處理性能。由于處理的圖像沒有相關(guān)性，GPGPU的任務(wù)可以與 CPU為后繼運算進行的預(yù)處理并行執(zhí)行，形成流水線。這樣，GPGPU只需要計算最復(fù)雜的特征檢測和描述兩部分，其他部分由CPU完成。

目前，多核的CPU處理器已經(jīng)相當(dāng)普遍，4核已經(jīng)成為PC的通用配置。PC處理器已經(jīng)有了8核乃至16核。除去控制GPGPU的核和預(yù)處理的流水線核，多核的處理器可能還有多余的核。為了使主機系統(tǒng)資源得到完全利用，還可以在剩余的核上運行多核版本的圖像特征提取算法來提高整個系統(tǒng)的吞吐率。

3　實驗評估

為了計算算法的有效性，本文對GPGPU加速算法進行了評估。

3.1評估環(huán)境

實驗中使用Rob Hess的開源實現(xiàn)作為SIFT的基準(zhǔn)，以英特爾E7-4807處理器上串行處理時間作為基準(zhǔn)，其對SIFT串行處理速度是1.53 s/幀，吞吐量是 0.65幀/s。GPGPU程序的編寫基于NVIDIA CUDA編程模型。評估中使用的測試圖像是MIKOLAJCZYK K提供的用來評估各種特征檢測器和描述器的標(biāo)準(zhǔn)圖像集合[8-9]。操作系統(tǒng)為Ubuntu，Linux內(nèi)核版本為2.6.28-11-generic。硬件測試主要使用了兩種配置：（1）主機是Intel Core 2 Quad Q8300的4核CPU，內(nèi)存2 GB。GPGPU為GeForce GTX 260，共216個核，時鐘率為1.24 GHz，顯存的大小為1 GB。（2）主機是Intel Core i7 930的4核CPU，內(nèi)存為2 GB。GPGPU是 GeForce GTX 295，共 480個核，時鐘率為 1.24 GHz，顯存的大小為1 792 MB。

3.2性能評估

在GTX 260上實現(xiàn)的SIFT算法，吞吐率達到39.67幀/s，平均每張圖片耗時25.21 ms，其中在CPU上所花的時間包括圖像加載1.269 ms，主機對GPGPU的顯存和設(shè)備管理及 CPU處理的計算所花 6.765 ms，其余時間是GPGPU的計算時間。

在GTX 295上實現(xiàn)的SIFT算法，吞吐率達到76.15幀/s，平均每張圖片耗時13.131 ms，其中在CPU上所花的時間包括圖像加載0.440 ms，主機對GPGPU的顯存和設(shè)備管理及 CPU處理的計算所花 3.895 ms，其余時間是GPGPU的計算時間。

為了更直觀的比較加速效果，圖2分別給出了GTX 260和 GTX 295上 SIFT各階段 GPGPU加速的柱形圖?？梢钥闯?，各個算核在GPGPU上都有較好的加速效果，并具有較好的可擴展性。

圖2　GTX 260與295上SIFT實現(xiàn)各部分加速比較

3.3整體性能評估

表1給出各GPGPU實現(xiàn)的SIFT并行版本的吞吐量以及相對于串行CPU版本的加速比?？梢钥吹?，SIFT隨著GPGPU性能的增強，核數(shù)的增多，吞吐量和加速比也有相應(yīng)的提升，在GTX295上達到了118.2倍的加速，吞吐量達到76.86幀/s。從實驗結(jié)果可以看出，在GPGPU上實現(xiàn)的SIFT算法具有良好的性能，能滿足圖像特征提取的實時處理需求。流水線的使用和充分利用系統(tǒng)剩余資源可以進一步提高系統(tǒng)吞吐率。

表1　SIFT各GPGPU上的吞吐量及加速比比較

4　相關(guān)工作

由于串行的局部特征提取算法處理速度較慢，已有一些研究在并行硬件上分析和實現(xiàn)了局部特征提取算法來獲得加速。ZHANG Q等人[10]針對多核系統(tǒng)架構(gòu)提出SIFT的兩種并行算法，在8核機器上達到6.4倍的性能加速效果。FENG H等人[11]的實現(xiàn)在16核機器上達到11倍的加速。這兩者都是采用圖象的分塊并行。這兩篇文獻都對串行算法進行了局部串行優(yōu)化，這些串行優(yōu)化基本實現(xiàn)了約2倍的速度提升。這意味著在8核處理器上并行的實際加速大約為3倍，而在16核平臺上的加速只有5.5倍。CHEN P等人[12]對SIFT實現(xiàn)了一種通用的動態(tài)流水線的并行，在開啟超線程的16核處理器上對 SIFT達到 16.88倍加速。SINHA S[13]也在 GPGPU對SIFT進行了實現(xiàn)，在 GeForce 7800 GTX上處理 640×480大小圖像的速度為10幀/s。HEYMANN S等人[14]的實現(xiàn)在QuadroFX 3400上達到20幀/s。他們的實現(xiàn)沒有充分考慮GPGPU的特性，也沒有考慮到充分利用CPU資源可能對系統(tǒng)性能的影響。本文基于GPGPU的特性設(shè)計和實現(xiàn)了高效的SIFT并行加速算法，并通過充分利用CPU資源進一步提升系統(tǒng)性能，相比于已有的技術(shù)可以獲得更大的性能提升。

5　結(jié)論

本文針對海量數(shù)據(jù)環(huán)境下圖像檢索的實時處理需求，使用新型的高性能計算硬件GPGPU來加速圖像局部特征提取的SIFT算法。測試結(jié)果表明，相對于CPU上的串行版本，SIFT的實現(xiàn)達到了118.2倍的加速，吞吐量達到76.86幀/s。

[1]BERRANI S，AMSALEGL，GROS P.Robust content-based image searches for copyright protection[C].In Proceedings of ACM Workshop on Mul-timedia Databases，2003：70-77.

[2]LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：404-417.

[3]OWENS J D，HOUSTON M，LUEBKE D，et al.GPU computing[J].In Proceedings of the IEEE，May 2008，96（5）：879-899.

[4]LINDHOLM E，NICKOLLS J，OBERMAN S，et al.NVIDIA Tesla:A unified graphics and computing architecture[J]. IEEE Micro5，Mar/Apr 2008，28（2）：39-5.

[5]GU L，LI X，SIEGEL J.An empirically tuned 2D and 3D FFT library on CUDA GPU[C].In Proceedings of ICS，2010：305-314.

[6]CHEN Y，CUI X，MEI H.Large-scale FFT on GPU clusters[C].In Proceedings of ICS，2010：315-324.

[7]NAGHMOUCHI J，SCARPAZZA D P，BEREKOVIC M. Small-ruleset regular expression matching on GPGPUs：Quantitative performance analysis and optimization[C].In Proceedings of ICS，2010：337-348.

[8]MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors[J].IEEE Trans.Pattern Anal.Mach.Intell，2005，27（10）：1615-1630.

[9]BAUER J，SüNDERHAUF N，PROTZEL P.Comparing several implementations of two recently published feature detectors[C]. In Proceedings of the International Conference on Intelligent and Autonomous Systems，2007.

[10]ZHANG Q，CHEN Y，ZHANG Y，et al.Sift implementation and optimization for multi-core systems[C].In Parallel andDistributed Processing，2008.IPDPS 2008.IEEE International Symposium on，2008：1-8.

[11]FENG H，LI E，CHEN Y，et al.Parallelization and characterization of sift on multi-core systems[C].IEEE International Symposium on Workload Characterization，2008：14-23.

[12]CHEN P，YANG D，ZHANG W，et al.Adaptive pipeline parallelism for image feature extraction algorithms[C].In Parallel Processing(ICPP)，2012 41st International Conference on IEEE，2012：299-308.

[13]SINHA S，F(xiàn)RAHM J，POLLEFEYS M，et al.GPU-based video feature tracking and matching[C].In Proc.of the 2006 Workshop on Edge computing Using New Commodity Architectures（EDGE），Chapel Hill，NC，2006：6-12.

[14]HEYMANN S，MULLER K，SMOLIC A，et al.SIFT implementation and optimization for general-purpose GPU[C]. In WSCG′07，2007：317-322.

Speeded-up SIFT on GPGPU

Yang Tiantian1，Lu Yunping2，Zhang Weihua2
(1.Software of Digital Media School，Jiangnan University，Wuxi 214083，China；2.Parallel Processing Institute，F(xiàn)udan University,Shanghai 201203，China)

The modern GPGPU is not only a powerful graphic processor but also a highly parallel programmable processor. Stronger arithmetic ability and higher bandwidth bring GPGPU great competitive power in real-time processing systems and highperformance computing systems.This paper designs and implements parallel acceleration algorithms for SIFT on GPGPU.We make best use of GPGPU architectures to accelerate our implementations,including uses of shared memory and texture memory,decreasing allocation and free times of memories on GPGPU and etc.GPGPU usually cooperates with CPU to finish a job.This paper implements SIFT on GPGPU in consideration of the impacts of CPU.Experimental results show this method can achieve a speedup of 118.2X with a throughput of 76.86 images per second.

GPGPU；SIFT；parallel；acceleration

TP3

A

0258-7998(2015)01-0149-04

10.16157/j.cnki.0258-7998.2014120102015

國家自然科學(xué)基金(61370081)

2014-11-10)

楊天天（1986-），女，博士，講師，主要研究方向：傳感器、人工智能與模式識別、人機交互設(shè)計。

魯云萍（1974-），女，碩士，高級工程師，主要研究方向：網(wǎng)絡(luò)安全與模式識別。

張為華（1974-），通信作者，男，博士，副教授，主要研究方向：體系結(jié)構(gòu)與編譯優(yōu)化，Email：zhangweihua@fudan.edu.cn。