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)計(jì)數(shù)據(jù)顯示，YouTube網(wǎng)站每分鐘有60 h時(shí)長的視頻被上傳，F(xiàn)acebook存儲的圖片量超過2 000億張。如何從這些數(shù)據(jù)中提取有用的信息并進(jìn)行高效的分析和處理變得越來越重要，各種新型的圖像檢索類應(yīng)用也不斷涌現(xiàn)。

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

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

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

1 SIFT算法和GPGPU簡介

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

　　1.1 SIFT算法

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

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

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

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

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

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

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

　　1.2 GPGPU簡介

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

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

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

2 GPGPU加速算法

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

　　2.1 算核并行化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)評估

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

　　3.1 評估環(huán)境

　　實(shí)驗(yàn)中使用Rob Hess的開源實(shí)現(xiàn)作為SIFT的基準(zhǔn)，以英特爾E7-4807處理器上串行處理時(shí)間作為基準(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）主機(jī)是Intel Core 2 Quad Q8300的4核CPU，內(nèi)存2 GB。GPGPU為GeForce GTX 260，共216個(gè)核，時(shí)鐘率為1.24 GHz，顯存的大小為1 GB。（2）主機(jī)是Intel Core i7 930的4核CPU，內(nèi)存為2 GB。GPGPU是GeForce GTX 295，共480個(gè)核，時(shí)鐘率為1.24 GHz，顯存的大小為1 792 MB。

　　3.2 性能評估

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

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

　　為了更直觀的比較加速效果，圖2分別給出了GTX 260和GTX 295上SIFT各階段GPGPU加速的柱形圖。可以看出，各個(gè)算核在GPGPU上都有較好的加速效果，并具有較好的可擴(kuò)展性。

　　3.3 整體性能評估

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

4 相關(guān)工作

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

5 結(jié)論

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

參考文獻(xiàn)

　　[1] BERRANI S，AMSALEGL，GROS P.Robust content-based image searches for copyright protection[C].In Proceedings ofACM 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 com-puting[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 clus-ters[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 oflocal descriptors[J].IEEE Trans.Pattern Anal.Mach.Intell，2005，27（10）：1615-1630.

　　[9] BAUER J，S?譈NDERHAUF N，PROTZEL P.Comparing severalimplementations of two recently published feature detectors[C].In Proceedings of the International Conference on Intelligentand Autonomous Systems，2007.

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

　　[11] FENG H，LI E，CHEN Y，et al.Parallelization and charac-terization of sift on multi-core systems[C].IEEE Interna-tional 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 Confer-ence 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 CommodityArchitectures（EDGE），Chapel Hill，NC，2006：6-12.

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