特征點檢測DoG并行算法

朱 超，吳素萍

寧夏大學 信息工程學院，銀川 750021

1 引言

異構計算環(huán)境下高效算法的研究是大數(shù)據(jù)關鍵問題的重要內(nèi)容。大數(shù)據(jù)計算模式與大數(shù)據(jù)計算方法主要研究分布式環(huán)境下的大數(shù)據(jù)分析與處理的新型計算模式與高效基礎算法，包括分布實時計算問題（分布并行的計算架構與編程新模型、分布式計算的可行性理論、大數(shù)據(jù)算法設計等），現(xiàn)代超算問題（異構計算環(huán)境下的計算優(yōu)化、多粒度分布式并行環(huán)境下的新編程模型、大數(shù)據(jù)超算算法等），非結構化信息處理，多源異構信息融合。

高性能計算技術迅速發(fā)展，目前已成為解決大數(shù)據(jù)量問題的有效方式。同時，異構并行系統(tǒng)已成為當前高性能計算機系統(tǒng)發(fā)展的重要趨勢之一，在眾多異構混合平臺中，基于CPU 和GPU 異構計算平臺具有很大的發(fā)展?jié)摿Α?/p>

特征點檢測被廣泛應用于目標識別與跟蹤、三維重建、圖像拼接等視覺領域[1-6]?，F(xiàn)階段，圖像局部不變特征的檢測及匹配算法取得了很好的效果。尺度不變特征變換（Scale-Invariant Feature Transform，SIFT）[7]具有尺度和旋轉不變性，SIFT 描述子用三維直方圖對特征一定領域中像素點梯度的方向與模值進行統(tǒng)計，具有很強的抗噪聲能力，但是由于維數(shù)較高，使得進行圖像匹配時速度較慢。為了解決SIFT 算法的時效性，Bay 等[8]提出了一種加速魯棒性算子（Speeded Up Robust Features，SURF），SURF描述符維數(shù)低，速度較快，但是無法保留大量的較穩(wěn)定的特征點，會導致重建過程中依據(jù)匹配特征點生成的三維點云較稀疏。Harris角點檢測[9]是最著名的基于圖像灰度值的特征點提取方法，但不能保證尺度不變。高斯差分（Difference-of-Gaussian，DoG）算法同時在二維平面空間和尺度空間檢測局部極值作為特征點，這種特征點具備良好的穩(wěn)定性，滿足尺度不變。Harris算法趨向于提取梯度變化劇烈的點，而DoG算法一般提取均勻區(qū)域的中心點，也稱斑點。針對Harris算法文獻[10]提出了一種基于OpenCL設計思想的并行算法，相比CPU加速比可達77倍。文獻[11]利用OpenCL技術對SIFT 算法進行加速，大大降低了原算法的耗時。文獻[12]提出了一種基于GPU 和CPU 異構計算平臺的Canny并行算法，相比CPU加速比可達5.39倍。文獻[13]提出了一種基于GPU的HOG（Histogram of Oriented Gradient）特征提取與描述算法，相比CPU獲得了40 倍左右的加速。文獻[14]提出了一種基于DAGS+GPU的去塊濾波算法，相比串行獲得了11～24倍的解碼加速比。文獻[15]提出了一種基于OpenCL 架構的SURF并行實現(xiàn)方法，對不同分辨率的圖片均實現(xiàn)了10倍以上的加速比，一些高分辨率的圖片甚至可以達到39.5 倍。文獻[16]提出了一種基于CPU 多線程和GPU兩級粒度并行策略，其中特征提取最高加速13 倍。文獻[17]在求取點云特征時提出了一種基于OpenCL實現(xiàn)的點云分割算法，利用OpenCL 的并行處理能力，使得運行效率為基于CPU實現(xiàn)的16倍。

基于DoG特征點檢測算法研究主要是基于CPU串行架構，算法性能的提升效果不理想，不能很好地滿足實時處理。另一方面，三維重建中運算量大，特征點檢測效率較低，為了提高特征點檢測的效率，本文在目前主流的多核CPU、CUDA 及OpenCL 架構上，提出三種DoG特征點檢測的并行算法，給出不同并行架構環(huán)境下的并行算法，實現(xiàn)特征點檢測的多平臺并行算法，提高特征點檢測效率和多平臺可應用性，實現(xiàn)特征點檢測的多核CPU和GPU并行算法。本文給出的特征點檢測并行算法是在彩色圖像上直接進行并行化，不同于其他在灰度圖上進行，或者將彩色圖像先轉換為灰度圖像再進行的方法。本文算法獲得了較高加速比，最高可獲得96倍多的加速比，并具有良好的數(shù)據(jù)和平臺可擴展性，可有效提升特征點檢測和三維重建過程的效率。

2 特征點檢測并行算法

DoG 算法在考慮尺度不變性的同時減小了特征點檢測過程中LoG（Laplace of Gaussian）算法的計算復雜度。DoG對高斯函數(shù)進行差分運算，高斯函數(shù)二維表示為：

首先使圖像與高斯函數(shù)進行若干次卷積運算，每次運算對模糊因子賦不同值，創(chuàng)建高斯尺度空間：

這里g1(x,y)為高斯濾波后圖像，I(x,y)為原始圖像。

然后使高斯尺度空間中緊鄰的兩幅圖像進行減法運算，創(chuàng)建出高斯差分尺度空間，即DoG 尺度空間，公式表示為：

即可將DoG表示為：

即：

DoG空間中局部極值點即為特征點。如圖1所示，將圖中所標記的點分別與該點本層尺度鄰近8 個點以及上下層尺度各9個點共27個點進行比較，若該點為極值點，則確定為特征點[6]。

圖1 尋找極值點

2.1 算法步驟

算法主要是創(chuàng)建DoG尺度空間，并進行比較，判斷是否為極值點，若為極值點，則確定為特征點。

特征點檢測步驟如算法1。

算法1 DoG特征點檢測算法

輸入：圖像，高斯模糊因子。

輸出：圖像特征點數(shù)量，每個特征點坐標。

（1）初始化圖像。將圖像數(shù)據(jù)讀入到一維image 數(shù)組，為保證計算精度，算法中將一維image 數(shù)組轉換為三通道。浮點型二維數(shù)組存儲在m_image數(shù)組中。

（2）創(chuàng)建高斯尺度空間。使輸入圖像與不同模糊因子所對應的高斯函數(shù)進行指定次數(shù)的卷積運算，創(chuàng)建圖像的高斯尺度空間，對圖像每個點卷積處理可獨立進行。

（3）創(chuàng)建DoG 尺度空間。對（2）中所創(chuàng)建的高斯尺度空間，對緊鄰兩幅圖像進行減法運算，得到圖像的DoG尺度空間。

（4）判斷是否為極值點。在（3）所創(chuàng)建的DoG 尺度空間中，使每一個點與本層以及上下層相鄰點進行比較，求得的極值點即為特征點。

2.2 OpenMP并行算法

OpenMP 是由OpenMP Architecture Review Board所推出的，基于共享內(nèi)存的一套多線程程序設計指導性的編譯處理方案。OpenMP可移植性高，可擴展性好[18]。

圖2 基于OpenMP的DoG算法流程

通過合理的任務分配和同步，可保證計算任務的均衡性和正確性。在圖2中，使用Fork-Join[18]執(zhí)行模式，讀入圖像數(shù)據(jù)后，當程序執(zhí)行到圖像初始化并行域時會生成多個從線程，執(zhí)行完畢后從線程合并為一個主線程，步驟之間需要同步來確保本步驟的完成和下一個步驟的正確性。

特征點檢測并行算法如算法2。

算法2 基于OpenMP的并行算法

輸入：圖像，n個不同尺度的高斯卷積模板，尺度由標準差σi確定。

輸出：圖像特征點數(shù)量，每個特征點坐標。

（1）生成與CPU核數(shù)相同數(shù)量的線程，創(chuàng)建并行區(qū)。

（2）進行循環(huán)任務的分配，在并行算法中圖像被劃分為與線程數(shù)相同數(shù)量的區(qū)域，每一個區(qū)域由（1）中所生成的線程進行處理，一個線程完成所負責區(qū)域圖像的初始化，高斯卷積相減(n-2)，判斷是否為極值點一系列任務，找出該區(qū)域中的特征點。

在多核CPU中，在調(diào)用的最內(nèi)層進行并行，派生線程與合并線程次數(shù)會減少，也會使時間開銷降低，相對于在外層進行并行或在兩層都進行并行時速度會有所提升。

2.3 CUDA并行算法

計算機統(tǒng)一設備架構（Computer Unified Device Architecture，CUDA），是由 NVIDIA 公司推出的一種GPU 并行計算框架，能夠利用GPU 的計算能力提供一套高效的密集型數(shù)據(jù)計算解決方案[19]。

CUDA 模型為CPU 端完成串行及調(diào)度工作，GPU端為多個線程并行執(zhí)行內(nèi)核函數(shù)完成計算工作。GPU線程采用塊狀劃分，即所有的線程以二維方式組織，線程與圖像中的像素點一一對應。開始由CPU端將數(shù)據(jù)拷貝至GPU端，調(diào)用內(nèi)核函數(shù)進行計算，計算完成后再將結果拷貝至CPU端?；贑UDA的DoG特征點檢測過程如圖3所示。

圖3 基于CUDA的DoG算法流程

并行特征點檢測算法步驟如算法3。

算法3 基于CUDA的并行特征點檢測算法

輸入：圖像，高斯模糊因子。

輸出：圖像特征點數(shù)量，每個特征點坐標。

主機端：

（1）高斯模板初始化，創(chuàng)建n個不同尺度的高斯卷積模板尺度由標準差σi確定。

（2）配置block：blockSize=16×l6，即一個block 含有256個thread。

（3）開辟顯存空間，把圖像數(shù)據(jù)保存至image數(shù)組，把數(shù)據(jù)傳輸至GPU顯存。

（4）DoG 特征點檢測，主要由主機端進行調(diào)度，在GPU端并行執(zhí)行，其步驟如（4.1）～（4.11）所示：

（4.1）進行圖像的初始化。調(diào)用GPU端計算每個線程的全局坐標，與將要處理對應像素點的關系，取到該線程所要處理的像素點，進行數(shù)據(jù)類型的轉換，完成圖像初始化任務。

（4.2）創(chuàng)建不同模糊因子所對應的高斯模板，并拷貝至GPU端。

（4.3）取到本線程對應處理的像素點，對該像素點分別進行x方向、y方向的高斯模糊運算，即g1(x,y)=，其中表示標準差為σ1的高斯濾波模板，I(x,y)為原始圖像，計算出模糊后的結果存儲在數(shù)組中，即第一層模糊圖像。

（4.4）計算出第二層高斯模糊圖像，即g2(x,y)=2，其中表示標準差為σ2的高斯濾波模板，把結果存儲在數(shù)組中。

（4.8）此時已經(jīng)得到兩層DoG 空間，即第一層DoG空間及第二層DoG空間。

（4.9）繼續(xù)迭代執(zhí)行（4.7）、（4.8）得到第三層高斯差分尺度空間，此時在第二層DoG空間中，即可判斷本線程所對應的像素點在本層尺度鄰近8 個點和上下相鄰兩層尺度各9個點共27個點中是否為極值點，若為極值點，則確定為特征點。繼續(xù)迭代執(zhí)行（4.7）、（4.8），每得到一層DoG 空間后即可進行極值點的判斷，并確定是否為特征點。

（5）把結果拷貝至主機端。

（6）釋放GPU顯存。

并行算法的具體實現(xiàn)過程為：將整個檢測過程分解為若干子任務，一個子任務由一個對應的global函數(shù)進行處理，算法運行過程中，global 函數(shù)與grid 一一對應，grid 將任務分配給 block，block 再分配給 thread 進行處理，所有函數(shù)都由主機端進行調(diào)用，在GPU端運行。

2.4 OpenCL并行算法

OpenCL 模型是針對異構平臺編程的開放工業(yè)標準，OpenCL有一套完整的并行程序編寫框架，由程序設計語言、函數(shù)庫、運行時系統(tǒng)、API幾部分構成[20]。

OpenCL 平臺模型為一主機加多OpenCL 設備。一個OpenCL設備又由多個計算單元（CU）組成，而一個計算單元又可分解為多個處理單元（PE），處理單元用來進行計算。主機端完成OpenCL程序的開始和終止，分配計算資源[20]。

OpenCL執(zhí)行模式為CPU端主要完成平臺初始化、設備選擇、創(chuàng)建執(zhí)行上下文、設置工作空間與啟動Kernel等任務。GPU端并行完成Kernel執(zhí)行等任務。

基于OpenCL的DoG特征點檢測算法步驟如算法4。

算法4 基于OpenCL的并行特征點檢測算法

輸入：圖像，高斯模糊因子。

輸出：圖像特征點數(shù)量，每個特征點坐標。

主機端：

創(chuàng)建平臺對象；獲得平臺相關設備；由設備得到上下文；由上下文生成命令隊列；設置工作節(jié)點個數(shù)，創(chuàng)建和設置 Kernel，執(zhí)行 DoG 算法中的 Kernel，進行 DoG 特征點檢測。

并行算法的具體實現(xiàn)過程為：將整個檢測過程分解為若干子任務，分別完成圖像初始化操作，圖像模糊操作，即；圖像相減操作，即D=，計算出該像素點的DoG值；圖像的多次迭代模糊運算；尋找極值點操作。子任務與Kernel一一對應，在工作節(jié)點中進行運算。

為了使硬件性能得到充分發(fā)揮，本文選擇將工作組大小設置為16×16，即一個工作組包含256個工作節(jié)點。

不同于灰度圖，本文是在三通道彩色圖像上進行特征點檢測的并行化，即R 通道、G 通道、B 通道。不僅需要計算線程或工作節(jié)點與圖像中的像素點對應關系，還需要計算線程或工作節(jié)點與圖像中的一個像素點中每個通道的對應關系，由主機端傳輸至GPU 端的圖像數(shù)據(jù)是一個一維數(shù)組的結構，如圖4所示。

圖4 圖像中像素點與實際存儲位置對應關系圖

在圖4中，(x1,y1)、(x2,y2)為圖像中的任意兩點，圖像的每一像素點實際存儲該點的RGB 三通道值，即圖像中每個點需要存儲三個值。CUDA 與OpenCL 架構中，線程或工作節(jié)點與像素點為一對一的處理關系，本文算法根據(jù)線程的位置計算出對應處理點的三通道值，具體計算公式為公式如下：

其中，blockIdx.x為線程塊編號，blockDim.x為線程塊大小，threadIdx.x為線程塊內(nèi)線程編號。通過式（6）首先計算出該線程對應處理像素點的R通道值所在位置，然后再依次通過式（7）與式（8）計算出該像素點的G 通道值與B 通道值所在位置。

3 實驗測試與結果分析

由于并行算法實驗環(huán)境，沒有統(tǒng)一的配置環(huán)境，在比較并行算法的性能時，主要是將并行算法的實驗結果與串行算法的實驗結果進行比較，主要比較的指標為：（1）并行算法與串行算法相比較所取得的加速比。（2）并行算法的可擴展性，包括數(shù)據(jù)可擴展性和平臺可擴展性。數(shù)據(jù)可擴展性指在同一硬件平臺下，并行算法隨著實驗數(shù)據(jù)量增大，相應的加速比也在增大。平臺可擴展性指在同一類型平臺下并行算法隨著平臺配置的提高，相應的加速比也隨著在提高。（3）并行算法的精度，主要指并行算法一般要保證串行算法的精度。本文實驗主要從上述三方面進行比較。

3.1 實驗環(huán)境

（1）硬件

平臺1：CPU（2 核）為Pentium Dual Core T4300@2.10 Hz；顯卡為NIVIDA GeForce G210M。

平臺2：CPU（6 核）為 Intel Xeon E5-2620@2.00 GHz；顯卡為NVIDIA Tesla C2070。

（2）軟件

操作系統(tǒng)：Windows-7。

開發(fā)環(huán)境：VisualStudio2010、CUDAToolkit6.5、OpenCLl.0。

3.2 實驗測試圖像用例

本文選取kermit、hallFeng 兩組圖像數(shù)據(jù)集作為實驗數(shù)據(jù)集。該數(shù)據(jù)集來源于PMVS（基于面片的三維多視角立體視覺算法）主網(wǎng)，其中kermit 為一組從不同角度對青蛙模型拍攝的連續(xù)圖像，hallFeng 為一組從不同角度對一座大樓拍攝的連續(xù)圖像，如圖5所示。

圖5 測試圖像

3.3 測試結果與分析

本文對兩組數(shù)據(jù)集在串行、基于OpenMP 多核并行、基于CUDA并行架構、基于OpenCL并行架構下分別進行特征點檢測測試，記錄各算法執(zhí)行時間并進行分析。

3.3.1 標準測試圖像數(shù)據(jù)可擴展性實驗

實驗分別從kermit圖像數(shù)據(jù)集與hallFeng圖像數(shù)據(jù)集中選取標準圖像，對圖像進行降采樣處理，取得多張尺寸大小不同的圖像，用以進行對比實驗。

針對尺寸大小不同的圖像，在實驗平臺1上分別進行了算法運行耗時統(tǒng)計，為保證測試時間準確性，實驗結果取10次測試時間的平均值。實驗記錄結果如表1、表2所示。

為更直觀表現(xiàn)在不同數(shù)據(jù)集上算法在串行與在不同并行架構上的運行時間，繪制柱狀圖6 和圖7。從圖中可以看出，DoG并行算法相比較串行算法的運行時間大幅度降低?；贑UDA 和OpenCL 的并行算法的運行時間更少，兩種環(huán)境下的并行算法具有基本相同的性能，說明本文基于CUDA和OpenCL的并行算法是穩(wěn)定的?；贠penMP 算法的加速比接近CPU 核數(shù)?；贑UDA的并行算法和基于OpenCL的并行算法對kermit圖像，最高加速比達到36倍多，對hallFeng圖像，最高加速比可達到40倍多。加速比隨圖像大小的增加呈現(xiàn)明顯上升趨勢，都表現(xiàn)出很好的加速效果，并行算法表現(xiàn)出較好的數(shù)據(jù)可擴展性。

表1 kermit圖像實驗結果

表2 hallFeng圖像實驗結果

圖6 kermit數(shù)據(jù)集運行時間柱狀圖

圖7 hallFeng數(shù)據(jù)集運行時間柱狀圖

為能直觀展現(xiàn)算法在不同并行架構下加速性能，本文計算出DoG算法在不同并行架構下的運行時間和在串行算法運行時間的比值，求取加速比，繪制出加速比曲線圖，如圖8、圖9 所示。從圖中可以看出，在一定范圍內(nèi)，加速比隨著圖像大小的增加呈上升趨勢，兩種并行算法都表現(xiàn)出了較好的數(shù)據(jù)可擴展性，在數(shù)據(jù)較大時基于OpenCL的并行算法加速較快一點。

圖8 kermit圖像并行加速比曲線圖

圖9 hallFeng圖像并行加速比曲線圖

3.3.2 CPU多核可擴展性實驗

本小節(jié)對并行算法的多核可擴展性進行實驗與分析，分別在兩數(shù)據(jù)集中選取一張測試圖片，尺寸固定，分別在 2 核 CPU 與 6 核 CPU 上做基于 OpenMP 的 DoG 并行算法可擴展性實驗，對運行時間進行統(tǒng)計，并計算加速比，結果如表3所示。

表3 kermit和hallFeng圖像不同平臺多核CPU實驗結果

為了直觀進行觀察，計算出不同平臺多核CPU 并行算法加速比，繪制曲線圖10。從圖中可以看出，加速比隨著CPU 核數(shù)的增加呈上升趨勢，并且加速比曲線相對來講較為陡峭，也就是說加速比提高相對也較快，表明本文并行算法表現(xiàn)出較好的多核可擴展性。

圖10 kermit和hallFeng圖像不同核數(shù)（平臺）多核CPU實驗結果

3.3.3 并行算法GPU平臺可擴展性實驗

為驗證本文并行算法具備良好的可移植性，即GPU平臺可擴展性，在具有較高計算能力的GPU 上同樣可以達到較高的性能。在hallFeng中選取一張測試圖片，尺寸為 752×500，在 NIVIDA GeForce G210M 顯卡與NVIDIA Tesla C2070顯卡上進行特征點檢測并行算法實驗，對算法運行時間進行統(tǒng)計，并計算加速比，結果如表4所示。

表4 hallFeng圖像不同平臺CUDA和OpenCL實驗結果

為了直觀觀察實驗結果，繪制出曲線圖11。從圖中可以看出，將算法在計算能力為1.2的NIVIDA GeForce G210M上的加速比與在計算能力為2.0的NVIDIA Tesla C2070 上的加速比進行比較，加速比最多提升了兩倍多，說明本文并行算法在GPU 上具有良好的可移植性和可擴展性。

圖11 hallFeng圖像不同平臺CUDA和OpenCL實驗結果

3.3.4 Tesla C2070 GPU上數(shù)據(jù)擴展性實驗

為驗證本文的并行算法在Tesla C2070顯卡上具有數(shù)據(jù)可擴展性，對hallFeng 數(shù)據(jù)集不同尺寸圖像在NVIDIA Tesla C2070顯卡上進行并行特征點檢測算法實驗，統(tǒng)計算法耗時，計算出加速比，結果如表5所示。

表5 Tesla C2070平臺上hallFeng圖像DoG實驗結果

為了直觀觀察實驗結果，繪制曲線圖12?？梢钥闯?，hallFeng數(shù)據(jù)集中圖像尺寸從188×125擴展到1 504×1 000 時，兩種并行算法加速比曲線呈上升趨勢，基于CUDA 并行算法在小數(shù)據(jù)量時加速效果也很好，逐漸趨于穩(wěn)定。當圖像尺寸增大時，數(shù)據(jù)量增多，數(shù)據(jù)的傳輸延遲也會延長，計算時間對傳輸延遲的隱藏性也逐漸減弱?；贠penCL并行算法加速比從7.3倍提升到83.07 倍。兩個并行算法最高加速比超過95 倍。加速比隨著圖像數(shù)據(jù)量的增大呈現(xiàn)出上升趨勢，說明并行算法在NVIDIA Tesla C2070顯卡上具有較好的數(shù)據(jù)可擴展性。

圖12 Tesla C2070平臺hallFeng圖像DoG并行加速比曲線圖

從本文的實驗結果可以看出，在GPU 環(huán)境下本文基于CUDA 和基于OpenCL 的并行算法都具有很好的加速效果。OpenCL 是一個開放的行業(yè)標準，可運行在通用GPU上。CUDA由NIVIDA開發(fā)，可運行在NIVIDA平臺上。

3.4 并行算法精度分析

特征點檢測并行算法在速度獲得大幅度提高的同時，必須確保檢測的準確度。本文統(tǒng)計出在OpenMP、CUDA、OpenCL并行框架下檢測出的特征點的數(shù)量，如表6、表7所示。

表6 kermit特征點檢測數(shù)量

表7 hallFeng特征點檢測數(shù)量

從表6、表7 中可以看出，并行算法在基于OpenCL架構下，只在hallFeng數(shù)據(jù)集中圖像尺寸大小為1 504×1 000 的情況下，與串行算法比較，少檢測出一個特征點，準確率達99.9%以上，而在其余情況下，并行算法檢測出的特征點數(shù)量與串行算法檢測出的數(shù)量及位置信息完全相同，準確率可達100%。表明本文所提出的特征點檢測并行算法不僅大幅度提升了特征點檢測的速度，同時也保證了特征點檢測的精度。

4 結束語

本文提出了基于OpenMP 多核CPU 并行算法和基于CUDA及OpenCL并行架構的GPU環(huán)境下并行算法，實驗結果表明基于多核CPU，特別是GPU的并行算法，能夠大幅度提高特征點檢測的執(zhí)行速度。隨著CPU核數(shù)增加，加速比也在增加，算法表現(xiàn)出良好的多核可擴展性。隨著圖像數(shù)據(jù)增大，算法的加速比呈上升趨勢，表現(xiàn)出良好的數(shù)據(jù)和平臺可擴展性?；贕PU的DoG特征點檢測并行算法最高可取得96倍多的加速比。