姜雪茸 魏威

摘 ?要：數(shù)字圖像匹配技術(shù)是數(shù)字處理領(lǐng)域中重要的環(huán)節(jié)，常運(yùn)用于圖像處理、計(jì)算機(jī)視覺、遙感數(shù)據(jù)分析。為提高圖像匹配速度，本文提出了采用并發(fā)執(zhí)行多個(gè)線程的適合于大規(guī)模、高速、通用計(jì)算任務(wù)的CUDA技術(shù)解決圖像匹配問題的方法。闡述了CUDA的編程原理和開發(fā)方法，論述了圖像匹配的基本原理，設(shè)計(jì)了圖像匹配的相關(guān)算法。

關(guān)鍵詞：圖像匹配;CUDA;算法設(shè)計(jì)

中圖分類號(hào)：TP391.41 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）18-0061-03

Abstract：Digital image matching technology is an important link in the field of digital processing，which is often used in image processing，computer vision，remote sensing data analysis. In order to improve the speed of image matching，this paper proposes a method to solve the problem of image matching by using CUDA technology which is suitable for large-scale，high-speed and general-purpose computing tasks and executes multiple threads concurrently. This paper expounds the programming principle and development method of CUDA，expounds the basic principle of image matching，and designs the relevant algorithm of image matching.

Keywords：image matching;CUDA;algorithm design

0 ?引 ?言

目前，圖像匹配技術(shù)在地形匹配、網(wǎng)絡(luò)檢索、運(yùn)動(dòng)目標(biāo)跟蹤以及工業(yè)實(shí)時(shí)監(jiān)測(cè)等領(lǐng)域中應(yīng)用廣泛，但在圖像匹配過程中圖像數(shù)據(jù)量大、計(jì)算復(fù)雜、實(shí)時(shí)性要求高，如何在保證圖像處理清晰度的情況下，提高圖像匹配的速度成為了問題。由此，本文提出采用具備強(qiáng)大通用并行計(jì)算能力的基于GPU（Graphics Processing Units）平臺(tái)的統(tǒng)一并行計(jì)算架構(gòu)（CUDA，Compute Unified Device Architecture）。CUDA運(yùn)行原理是并發(fā)執(zhí)行多個(gè)線程實(shí)現(xiàn)大規(guī)?？焖俨⑿杏?jì)算，可快速處理大規(guī)模數(shù)字圖像匹配問題，也可解決數(shù)字圖像匹配中效率低下的問題[1]?；谝陨戏治觯疚膶D像匹配的相關(guān)算法在CUDA平臺(tái)上予以實(shí)現(xiàn)并嘗試解決圖像匹配實(shí)時(shí)性技術(shù)問題。

1 ?圖像匹配和CUDA技術(shù)分析

1.1 ?圖像匹配

圖像匹配主要研究影像內(nèi)容、特征、結(jié)構(gòu)、關(guān)系、紋理及灰度等的相關(guān)關(guān)系，進(jìn)行相似性和一致性分析，尋找相似影像，是計(jì)算機(jī)圖像視覺和處理中一項(xiàng)重要的技術(shù)。主要是圖像在灰度上和特征上的匹配。

基于特征的圖像匹配：因?yàn)閳D像自身具有特征點(diǎn)、邊緣、輪廓、特征結(jié)構(gòu)及統(tǒng)計(jì)特征、重心等基本特征，因此可以通過每幅圖像的特征提取比對(duì)來進(jìn)行圖像匹配。

基于灰度匹配的方法，利用整幅圖像的灰度信息建立兩幅圖像之間的相似性度量，然后采用某種搜索方法尋找使相似性度量值最大或最小的變換模型的參數(shù)值。常用的相似性度量有：兩幅圖像灰度的平方差之和、序貫相似度檢測(cè)、互相關(guān)、相位相關(guān)[2]。

基于圖像灰度的匹配流程是將待配準(zhǔn)圖像與基準(zhǔn)圖像間所存在的像素進(jìn)行逐一比較，從而獲得其中的最佳點(diǎn)來作為匹配點(diǎn)?；诨叶鹊膱D像匹配算法中最基本的算法主要有：最小絕對(duì)差算法、最小平方差算法、最小卷積算法、最大互相關(guān)算法、不變矩算法等幾十種算法。

1.2 ?CUDA技術(shù)

實(shí)現(xiàn)圖像匹配的常用三種方法為專用ASIC器件、高速DSP、軟件。這三種方法中，面向算法的專用ASIC器件和高速DSP方法需要專業(yè)硬件，具有一定的局限性，而具備多核處理器的GPU具有高度并行計(jì)算特性，已經(jīng)在圖形圖像處理領(lǐng)域表現(xiàn)突出。因此采用基于GPU的CUDA平臺(tái)軟件編程方法實(shí)現(xiàn)圖像匹配。

CUDA是NVIDIA公司于2007年正式發(fā)布的統(tǒng)一并行計(jì)算架構(gòu)，是NVIDIA公司設(shè)計(jì)的針對(duì)異構(gòu)計(jì)算資源下的大規(guī)模并行計(jì)算的一個(gè)計(jì)算架構(gòu)，是一種由NVIDIA提出的并由其制造的圖形處理單元實(shí)現(xiàn)的一種并行計(jì)算平臺(tái)及程序設(shè)計(jì)模型，它利用GPU的多核硬件資源實(shí)現(xiàn)大規(guī)模并行計(jì)算[3]。

CUDA語言是C語言的擴(kuò)展，這使得熟悉C語言的編程人員能夠快速掌握應(yīng)用CUDA開發(fā)通用計(jì)算程序[4]。CUDA編程模型采用SIMT模式執(zhí)行程序，將CPU作為主機(jī)稱為HOST，GPU作為協(xié)處理器稱為DEVICE。

一個(gè)完整的程序主要包括處理的串行部分（即HOST端）和設(shè)備端（即DEVICE端）處理函數(shù)所實(shí)現(xiàn)的并行部分，并行處理的部分是由函數(shù)完成的。當(dāng)整個(gè)程序執(zhí)行到函數(shù)時(shí)，程序就會(huì)轉(zhuǎn)入到DEVICE端處理程序的并行部分，當(dāng)在DEVICE端并行部分處理完成后，也就是函數(shù)執(zhí)行完畢，程序繼續(xù)轉(zhuǎn)入到HOST進(jìn)行剩余部分的處理。

在CUDA架構(gòu)下，計(jì)算任務(wù)被映射為大量的可并行線程，因此顯卡的最小執(zhí)行單元為線程（thread）。一個(gè)線程塊（block）中包含多個(gè)可以溝通協(xié)作的線程，而執(zhí)行相同程序的則可以組成一個(gè)線程網(wǎng)格（grid）。每個(gè)線程都有其所在block中的ID號(hào)，同時(shí)每個(gè)block也有在grid中的ID，其中ID可以是一維、二維和三維的，每個(gè)執(zhí)行內(nèi)核函數(shù)的線程都擁有一個(gè)獨(dú)一無二的線程，而每個(gè)線程都可以使用它的線程索引和分塊索引的組合來確定其在全局網(wǎng)格的位置。如圖1所示。

2 ?基于CUDA的圖像匹配算法設(shè)計(jì)

基于圖像灰度的圖像匹配主要是將待匹配的配準(zhǔn)圖像與基準(zhǔn)圖像間的像素進(jìn)行一一比對(duì)，因此涉及到的相關(guān)計(jì)算具有圖像數(shù)據(jù)量大的特點(diǎn)，特別適合CUDA多核處理單元并行計(jì)算，且各像素是獨(dú)立的，其數(shù)據(jù)耦合度低、計(jì)算密度高，所以使用CUDA進(jìn)行基于灰度圖像的匹配是理想選擇。

2.1 ?圖像匹配算法

2.2 ?CUDA平臺(tái)算法設(shè)計(jì)

無論哪種算法在CUDA平臺(tái)上設(shè)計(jì)的流程都包括兩個(gè)方面：HOST端和DEVICE端實(shí)現(xiàn)。

HOST端實(shí)現(xiàn)的流程分為：數(shù)據(jù)初始化、數(shù)據(jù)復(fù)制、kernel函數(shù)調(diào)用、空間釋放，而在DEVICE端主要實(shí)現(xiàn)kernel函數(shù)的并行處理[6，7]。

現(xiàn)以最大互相關(guān)算法式（4）中的 ?部分為例，其并行程序的kernel函數(shù)如下：

__global__ void CJ （inti， intj，intu，intv，ints，intt， float w）

{

intw = 0;

inti=ThreaIdx.x，j=BlockIdx.y，

int u= BlockIdx.x*BlockDim.x+ ThreaIdx.x，

int v= BlockIdx.y*BlockDim.y+ ThreaIdx.y;

for （u=1; u<wwidth; u ++）

{

for （v= 1; v<wheight;v++）

{

for （j=1; j<height; j ++）

{

for （i = 1; i <width; i ++）

{

w += s[i][j]*t[i+u][j+v];

}}}}}

int main（ ）

{

...

Dim3 dimBlock（width，1，1）

Dim3 dimGrid（wwidth/width，height，1）

CJ<<<wheight/height*wwidth/width， width>>>（…）;

...

}

2.3 ?實(shí)驗(yàn)結(jié)果

經(jīng)過實(shí)際應(yīng)用，相同灰度圖像匹配，采用最大互相關(guān)算法對(duì)基準(zhǔn)圖512*512、待配準(zhǔn)圖256*256進(jìn)行實(shí)驗(yàn)，在基于CUDA的GPU平臺(tái)上并行處理運(yùn)行用時(shí)8.50ms，原始CPU運(yùn)行用時(shí)53.80ms，時(shí)間加速比達(dá)到了6.33。

3 ?結(jié) ?論

本文針對(duì)灰度圖像匹配算法中常見問題：運(yùn)算數(shù)據(jù)量大、算法繁瑣、實(shí)時(shí)性差，采用CUDA的高性能并行處理能力，進(jìn)行CUDA并行程序設(shè)計(jì)、實(shí)驗(yàn)，實(shí)現(xiàn)了圖像匹配時(shí)提高處理能力、提高運(yùn)算速度的目的。

參考文獻(xiàn)：

[1] 曾勝田，劉羽，馬夢(mèng)琦.基于CUDA的Prewitt算子并行實(shí)現(xiàn) [J].微計(jì)算機(jī)應(yīng)用，2011，32（11）：71-75.

[2] 岡薩雷斯.數(shù)字圖像信息處理 [M].第2版.北京：電子工業(yè)出版社，2007.

[3] 董犖，葛萬成，陳康力.CUDA并行計(jì)算的應(yīng)用研究 [J].信息技術(shù)，2010，34（4）：11-15.

[4] 陳茜，邱躍洪，易紅偉.基于GPU的星圖配準(zhǔn)算法并行程序設(shè)計(jì) [J].紅外與激光工程，2014，43（11）：3756-3761.

[5] 楊靚，黃士坦.最大互相關(guān)圖象匹配算法的硬件實(shí)現(xiàn) [J].微電子學(xué)與計(jì)算機(jī)，1999（5）：28-30.

[6] 賀曉佳.灰度圖像快速匹配算法研究 [D].合肥：合肥工業(yè)大學(xué)，2012.

[7] 董安國(guó).圖像匹配最大互相關(guān)快速算法 [J].浙江萬里學(xué)院學(xué)報(bào)，2005（4）：13-15.

作者簡(jiǎn)介：姜雪茸（1978-），女，漢族，山東齊河人，專任

教師，副教授，碩士，研究方向：軟件工程;魏威（1978-），男，漢族，甘肅榆中人，專任教師，副教授，學(xué)士學(xué)位，研究方向：軟件工程。