朱 超，吳素萍

寧夏大學(xué) 信息工程學(xué)院，銀川 750021

1 引言

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

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

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

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

2 特征點(diǎn)檢測(cè)并行算法

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

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

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

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

即可將DoG表示為：

即：

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

圖1 尋找極值點(diǎn)

2.1 算法步驟

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

特征點(diǎn)檢測(cè)步驟如算法1。

算法1 DoG特征點(diǎn)檢測(cè)算法

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

輸出：圖像特征點(diǎn)數(shù)量，每個(gè)特征點(diǎn)坐標(biāo)。

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

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

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

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

2.2 OpenMP并行算法

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

圖2 基于OpenMP的DoG算法流程

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

特征點(diǎn)檢測(cè)并行算法如算法2。

算法2 基于OpenMP的并行算法

輸入：圖像，n個(gè)不同尺度的高斯卷積模板，尺度由標(biāo)準(zhǔn)差σi確定。

輸出：圖像特征點(diǎn)數(shù)量，每個(gè)特征點(diǎn)坐標(biāo)。

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

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

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

2.3 CUDA并行算法

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

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

圖3 基于CUDA的DoG算法流程

并行特征點(diǎn)檢測(cè)算法步驟如算法3。

算法3 基于CUDA的并行特征點(diǎn)檢測(cè)算法

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

輸出：圖像特征點(diǎn)數(shù)量，每個(gè)特征點(diǎn)坐標(biāo)。

主機(jī)端：

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

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

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

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

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

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

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

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

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

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

（5）把結(jié)果拷貝至主機(jī)端。

（6）釋放GPU顯存。

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

2.4 OpenCL并行算法

OpenCL 模型是針對(duì)異構(gòu)平臺(tái)編程的開(kāi)放工業(yè)標(biāo)準(zhǔn)，OpenCL有一套完整的并行程序編寫框架，由程序設(shè)計(jì)語(yǔ)言、函數(shù)庫(kù)、運(yùn)行時(shí)系統(tǒng)、API幾部分構(gòu)成[20]。

OpenCL 平臺(tái)模型為一主機(jī)加多OpenCL 設(shè)備。一個(gè)OpenCL設(shè)備又由多個(gè)計(jì)算單元（CU）組成，而一個(gè)計(jì)算單元又可分解為多個(gè)處理單元（PE），處理單元用來(lái)進(jìn)行計(jì)算。主機(jī)端完成OpenCL程序的開(kāi)始和終止，分配計(jì)算資源[20]。

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

基于OpenCL的DoG特征點(diǎn)檢測(cè)算法步驟如算法4。

算法4 基于OpenCL的并行特征點(diǎn)檢測(cè)算法

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

輸出：圖像特征點(diǎn)數(shù)量，每個(gè)特征點(diǎn)坐標(biāo)。

主機(jī)端：

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

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

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

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

圖4 圖像中像素點(diǎn)與實(shí)際存儲(chǔ)位置對(duì)應(yīng)關(guān)系圖

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

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

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

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

3.1 實(shí)驗(yàn)環(huán)境

（1）硬件

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

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

（2）軟件

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

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

3.2 實(shí)驗(yàn)測(cè)試圖像用例

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

圖5 測(cè)試圖像

3.3 測(cè)試結(jié)果與分析

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

3.3.1 標(biāo)準(zhǔn)測(cè)試圖像數(shù)據(jù)可擴(kuò)展性實(shí)驗(yàn)

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

針對(duì)尺寸大小不同的圖像，在實(shí)驗(yàn)平臺(tái)1上分別進(jìn)行了算法運(yùn)行耗時(shí)統(tǒng)計(jì)，為保證測(cè)試時(shí)間準(zhǔn)確性，實(shí)驗(yàn)結(jié)果取10次測(cè)試時(shí)間的平均值。實(shí)驗(yàn)記錄結(jié)果如表1、表2所示。

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

表1 kermit圖像實(shí)驗(yàn)結(jié)果

表2 hallFeng圖像實(shí)驗(yàn)結(jié)果

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

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

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

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

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

3.3.2 CPU多核可擴(kuò)展性實(shí)驗(yàn)

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

表3 kermit和hallFeng圖像不同平臺(tái)多核CPU實(shí)驗(yàn)結(jié)果

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

圖10 kermit和hallFeng圖像不同核數(shù)（平臺(tái)）多核CPU實(shí)驗(yàn)結(jié)果

3.3.3 并行算法GPU平臺(tái)可擴(kuò)展性實(shí)驗(yàn)

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

表4 hallFeng圖像不同平臺(tái)CUDA和OpenCL實(shí)驗(yàn)結(jié)果

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

圖11 hallFeng圖像不同平臺(tái)CUDA和OpenCL實(shí)驗(yàn)結(jié)果

3.3.4 Tesla C2070 GPU上數(shù)據(jù)擴(kuò)展性實(shí)驗(yàn)

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

表5 Tesla C2070平臺(tái)上hallFeng圖像DoG實(shí)驗(yàn)結(jié)果

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

圖12 Tesla C2070平臺(tái)hallFeng圖像DoG并行加速比曲線圖

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

3.4 并行算法精度分析

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

表6 kermit特征點(diǎn)檢測(cè)數(shù)量

表7 hallFeng特征點(diǎn)檢測(cè)數(shù)量

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

4 結(jié)束語(yǔ)

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