面向CPU＋GPU異構(gòu)平臺的模板匹配目標(biāo)識別并行算法

馬永軍，袁 贏，李 灝

(1. 天津科技大學(xué)計算機科學(xué)與信息工程學(xué)院，天津 300222；2. 天津瑞和天孚科技有限公司，天津 300384)

面向CPU＋GPU異構(gòu)平臺的模板匹配目標(biāo)識別并行算法

馬永軍1，袁 贏1，李 灝2

(1. 天津科技大學(xué)計算機科學(xué)與信息工程學(xué)院，天津 300222；2. 天津瑞和天孚科技有限公司，天津 300384)

針對大數(shù)據(jù)量導(dǎo)致模板匹配目標(biāo)識別算法計算時間長，難以滿足快速檢測的實際需求問題，在采用最新NVIDIA Tesla GPU構(gòu)建的CPU＋GPU異構(gòu)平臺上，設(shè)計了一種模板匹配目標(biāo)識別并行算法．通過對模板圖像數(shù)據(jù)常量化、輸入圖像數(shù)據(jù)極致流多處理器片上化和簡化定位參數(shù)計算3方面優(yōu)化了并行算法，并對算法進(jìn)行性能測試．實驗表明，該算法在保證識別效果的同時實時性明顯提高．

模板匹配；目標(biāo)識別；并行計算；統(tǒng)一設(shè)備計算架構(gòu)；圖形處理器

模板匹配運動目標(biāo)識別已廣泛應(yīng)用到視頻監(jiān)控等領(lǐng)域，然而隨著視頻信息高清化、數(shù)字化發(fā)展，在視頻處理領(lǐng)域中基于模板匹配的運動目標(biāo)識別算法的計算代價高，實時性降低，因而迫切需要提高計算能力．目前在此領(lǐng)域已取得了一些成果：于志華等[1]提出一種基于FPGA的并行超標(biāo)量匹配處理架構(gòu)加速算法，但僅局限于語音系統(tǒng)；李俊山等[2]提出基于K元2-立方體網(wǎng)絡(luò)結(jié)構(gòu)的圖像模板匹配并行算法，適用于LS MPP(Li-Shan massive parallel processing)計算機．另外，趙東明等[3]利用DNA計算的并行性實現(xiàn)模板匹配算法的并行化；馬永軍等[4]利用多核平臺使用OpenMP對模板匹配進(jìn)行加速．這2種算法均基于CPU實現(xiàn)，而CPU并不擅長并行計算，無法解決在高清環(huán)境下視頻數(shù)據(jù)量大、實時處理性能不佳的問題．Rajasekaran[5]通過FFT技術(shù)獲得有效的模板匹配并行算法，但存在算法計算量巨大的問題；Anderson等[6]通過GPU對模板匹配進(jìn)行加速，但沒有充分挖掘異構(gòu)平臺的優(yōu)勢，仍有提升空間．因此，提高基于模板匹配目標(biāo)識別算法性能具有現(xiàn)實意義.

NVIDIA公司最新的Tesla系列圖形處理單元(GPU)完全針對并行計算而設(shè)計，利用NVDIA公司統(tǒng)一設(shè)備計算架構(gòu)(compute unified device architec-ture，CUDA)的高可擴展性，完全可以滿足高性能計算機的需要．而且，由CPU＋GPU組成的異構(gòu)處理平臺相比傳統(tǒng)的同構(gòu)多處理機系統(tǒng)，能夠提供更好的計算性能和功耗效率，已經(jīng)成為解決大數(shù)據(jù)量引發(fā)的計算復(fù)雜、代價高等問題的主流并行解決方案．其中，如何高效地利用異構(gòu)系統(tǒng)中CPU和GPU進(jìn)行協(xié)同并行計算是目前研究的熱點問題[7]．

本文提出一種采用最新的NVIDIA Tesla GPU構(gòu)建CPU＋GPU異構(gòu)平臺，并進(jìn)行CUDA并行編程的方法，利用CPU＋GPU異構(gòu)多核的高并行能力，使用最新的NVIDIA Tesla K20c GPU對模版匹配目標(biāo)識別并行算法進(jìn)行設(shè)計．

1 GPU和CUDA編程介紹

Tesla GPU憑借開普勒(Kepler)架構(gòu)可以提供強大的處理功能以及優(yōu)化，并具有提高GPU上并行執(zhí)行工作負(fù)載的新方法．Kepler架構(gòu)GPU的核心是極致流多處理器(next generation streaming multiprocessor，SMX)[8]，與上一代Fermi架構(gòu)使用的流多處理器(streaming multiprocessor，SM)相比，計算和功能單元的數(shù)量、安置方式有了很大變化．這一新型的流式多處理器設(shè)計讓應(yīng)用到處理核心上的空間比例遠(yuǎn)高于應(yīng)用到控制邏輯單元上的空間比例，從而可實現(xiàn)更高的處理性能和效率．

CUDA核心包含線程組層次、共享存儲器和柵欄同步3個重點抽象，用于引導(dǎo)程序員將問題劃分為可以被多個塊內(nèi)線程獨立并行處理的細(xì)粒度子問題；然后，每個子問題在1片SMX上被1個塊內(nèi)線程并行協(xié)作處理，以提高執(zhí)行效率．

由于CUDA并未封裝存儲器系統(tǒng)的異構(gòu)性，用戶可以針對具體存儲器的特點，有選擇地使用[9]. CUDA將優(yōu)化程序的自主權(quán)交給了用戶，可提高用戶自主解決問題的靈活性．

2 模板匹配目標(biāo)識別的GPU并行算法設(shè)計

2.1 滑動模板匹配目標(biāo)識別算法分析

滑動模板匹配算法的匹配過程如圖1所示．模板匹配目標(biāo)識別算法的基本原理是讓包含目標(biāo)的模板圖像T在輸入圖像I中滑動，對模板圖像和其覆蓋的對應(yīng)輸入圖像區(qū)域利用去均值歸一化相關(guān)系數(shù)公式(式(1))[10]進(jìn)行定位參數(shù)計算，選擇相關(guān)系數(shù)最優(yōu)值所在位置作為最佳目標(biāo)匹配位置．

由式(1)可以看出，在滑動模板匹配過程中，每次僅計算1個像素點位置的定位參數(shù)，按照匹配順序依次計算每個像素點的定位參數(shù)，完成整幅輸入圖像匹配的過程需要大量簡單、計算方式相同的重復(fù)計算．因為在滑動匹配過程中，各個像素點的計算過程是相互獨立、互不干擾的，所以適合通過大規(guī)模的線程并發(fā)執(zhí)行來加速計算．

圖1 滑動模板匹配算法的匹配過程Fig. 1Matching procedure of sliding template matching algorithm

2.2 模板匹配并行算法總體設(shè)計

為了通過GPU執(zhí)行大量并發(fā)線程，發(fā)揮高性能并行計算優(yōu)勢，實現(xiàn)減少模板匹配過程時間的目的，將圖像區(qū)域模板匹配的并行算法按照“先整體區(qū)域分塊，再局部并行計算”的策略分為2步實現(xiàn)(圖2)：第1步，在GPU中將圖像區(qū)域?qū)?yīng)的CUDA線程分塊(Block)，進(jìn)行圖像數(shù)據(jù)分配；第2步，在每個Block中對每個CUDA線程對應(yīng)的像素點進(jìn)行定位參數(shù)計算，存儲局部統(tǒng)計結(jié)果，然后匯總局部結(jié)果，求整體極值得到整幅輸入圖像中的最佳匹配位置．

圖2 模板匹配并行算法總體設(shè)計Fig. 2Overall design of parallel sliding template matching algorithm

根據(jù)滑動匹配的過程，將每個像素點位置處的匹配過程映射到CUDA線程上，1個線程處理與之對應(yīng)的1個像素點的匹配過程．其中，并行化過程中需要在滿足線程映射關(guān)系的前提下進(jìn)行線程關(guān)鍵參數(shù)計算，程序如下：

2.3 并行算法的優(yōu)化

根據(jù)GPU硬件特性可知，GPU存儲系統(tǒng)中各存儲單元為層次結(jié)構(gòu)，其中包括：常量存儲器、共享存儲器、紋理存儲器、全局存儲器等，它們的作用域和訪問效率各不相同[9]．基于GPU的編程框架并未封裝存儲器系統(tǒng)的異構(gòu)性，在總體設(shè)計的第1步中，針對模板圖像數(shù)據(jù)在計算過程保持不變的特點，選用常量存儲器存儲模板圖像數(shù)據(jù)，進(jìn)行常數(shù)化參數(shù)存儲優(yōu)化；針對存儲在紋理存儲器中的輸入圖像數(shù)據(jù)訪問延遲大的特點，選用SMX片上共享存儲器存儲局部數(shù)據(jù)，進(jìn)行SMX片上數(shù)據(jù)存儲優(yōu)化，從而提高算法訪問圖像數(shù)據(jù)和存儲計算結(jié)果的效率．

另外，在總體設(shè)計第2步中，可以通過簡化定位參數(shù)的計算過程降低并行化過程中的計算量，進(jìn)一步提高計算效率．

2.3.1 模板圖像參數(shù)常數(shù)化

針對模板圖像的參數(shù)在匹配操作的相關(guān)系數(shù)計算過程中始終保持不變的特點，算法中將與模板圖像相關(guān)的參數(shù)提前計算出來存儲于GPU的常量存儲器中，從而實現(xiàn)模板圖像參數(shù)常數(shù)化存儲．然后，在定位參數(shù)計算過程中可直接讀取存儲器中的參數(shù)．雖然常量存儲器僅有64,KB[8]，但是訪存速度要比設(shè)備存儲器快，通常在1～100個時鐘周期內(nèi)就可以獲取所需要的數(shù)據(jù)．

假設(shè)輸入圖像為W像素×H像素，在計算任意像素點定位參數(shù)時，模板圖像的參數(shù)都會被計算1次，整個圖像則會被重復(fù)計算WH次．通過利用常量存儲器，計算次數(shù)為原來的1/WH，在模板圖像參數(shù)獲取上的性能提高了WH倍．具體過程見圖3．

圖3 模板圖像數(shù)據(jù)復(fù)用原理Fig. 3 Reuse of template image data

2.3.2 輸入圖像數(shù)據(jù)SMX片上化

用于存儲輸入圖像數(shù)據(jù)的GPU紋理存儲器屬于SMX片外存儲器，通常有幾百個時鐘周期的訪問延遲．因此，如何縮短紋理存儲器的訪問時間是加速的關(guān)鍵．

存儲器層次結(jié)構(gòu)如圖4所示．其中SMX片上共享存儲器的訪問速度比紋理存儲器快10倍左右[9]．因此，在計算過程中把在本線程塊中使用到的局部輸入圖像的數(shù)據(jù)存儲在SMX片上共享存儲器中，然后用SMX片上共享存儲器中的局部原始輸入圖像與常量存儲器中的模板圖像數(shù)據(jù)進(jìn)行定位參數(shù)計算．通過充分利用SMX片上共享存儲器解決紋理存儲器訪問效率低下的問題．

圖4 存儲器層次結(jié)構(gòu)圖Fig. 4 Memory hierarchy

在串行算法中，圖像數(shù)據(jù)在主機內(nèi)存中始終只有1份，而在CPU＋GPU異構(gòu)平臺下，需要拷貝紋理存儲器中的圖像數(shù)據(jù)到SMX片上共享存儲器中保留第2份副本．這樣做雖然使用了更多的GPU存儲空間，但是減少了運算時間，可取得更好的算法性能．

2.3.3 簡化定位參數(shù)計算

而且，由于NVIDIA Tesla K20c GPU中的極致流多處理器(SMX)包含用于整數(shù)乘法和加法的硬件結(jié)構(gòu)，因此能夠在GPU上快速實現(xiàn)該函數(shù)的求值．

2.4 模板匹配目標(biāo)識別并行算法總體流程

根據(jù)模板圖像數(shù)據(jù)常數(shù)化、輸入圖像數(shù)據(jù)SMX片上化和簡化定位參數(shù)計算3方面的優(yōu)化，在Tesla GPU的核心上建立大量線程，將像素點與CUDA線程一一對應(yīng)，并為每個像素的計算開辟空間，利用GPU將多個像素計算的時間縮短成和1個像素點計算的時間相似，從而提高算法執(zhí)行效率．基于GPU加速的模板匹配目標(biāo)識別并行算法流程見圖5．

圖5 模板匹配目標(biāo)識別并行算法流程Fig. 5 Float chart of template matching target recognition parallel algorithm

3 實 驗

3.1 實驗環(huán)境

硬件平臺：超云服務(wù)器，GPU為Tesla K20c，含有13顆極致流多處理器，每個極致流多處理器上有192顆CUDA核心，其核心頻率為706,MHz，顯存帶寬為320,bit，顯存為4,GB；CPU為Intel Xeon CPU 3.1,GHz；系統(tǒng)內(nèi)存為16,GB．

軟件平臺：操作系統(tǒng)為Microsoft Windows 7中文專業(yè)版；集成開發(fā)平臺為Visual Studio C++ 2010；并行開發(fā)環(huán)境包括CUDA 5.0，CUDA Toolkit 5.0；計算機視覺庫采用OpenCV 2.4.3．

3.2 實驗結(jié)果與分析

為了驗證算法的并行加速效果，采用固定模板圖像大小為52像素×52像素、變化輸入圖像大小的4組數(shù)據(jù)(圖6)，對比基于CPU的串行模板匹配目標(biāo)識別算法(方法1)、基于GPU的未優(yōu)化并行模板匹配目標(biāo)識別算法(方法2)、基于GPU的優(yōu)化并行模板匹配目標(biāo)識別算法(方法3)的執(zhí)行效果．為了減小實驗誤差，算法分別運行50次，記錄平均運行時間．

圖6 輸入圖像和模板圖像Fig. 6 Input image and template image

3種方法的實驗對比見表1．分析表1可知：(1)對同一幅圖像進(jìn)行特征點檢測時，方法3(基于GPU的優(yōu)化并行模板匹配目標(biāo)識別算法)與方法1(基于CPU的串行模板匹配目標(biāo)識別算法)和方法2(基于GPU的未優(yōu)化并行模板匹配目標(biāo)識別算法)相比，極大地提高了算法的實時性，能夠滿足實際需求．(2)對于本實驗，雖然將串行算法(方法1)翻譯成在GPU上運行的并行程序(方法2)提高了算法效率，但是優(yōu)化后的算法(方法3)能夠取得更好的算法實時性．可見，并行算法的設(shè)計和開發(fā)需要根據(jù)算法本身和所使用的GPU硬件特性，有針對性的優(yōu)化之后才能更好地發(fā)揮GPU的性能，獲得滿意的加速效果．

表1 串行算法、并行算法、優(yōu)化并行算法的平均運行時間Tab. 1 Average processing time of serial algorithm，parallel algorithm and optimal parallel algorithm

4 結(jié) 語

本文在構(gòu)建的CPU＋GPU異構(gòu)平臺基礎(chǔ)上設(shè)計了模板匹配目標(biāo)識別并行算法，給出了實現(xiàn)的步驟和性能優(yōu)化的方法，并在NVIDIA Tesla K20,c GPU上進(jìn)行性能測試．結(jié)果表明，在Kepler架構(gòu)下利用CUDA編程模型進(jìn)行程序并行化處理和優(yōu)化可明顯提高算法的實時性，能夠適應(yīng)現(xiàn)在視頻高清化、數(shù)字化、網(wǎng)絡(luò)實時性等方面的要求．

［1］ 于志華，張興明，楊鎮(zhèn)西，等. 一種高性能固定語音識別并行處理架構(gòu)[J]. 計算機應(yīng)用研究，2013，30(8)： 2419–2421.

［2］ 李俊山，沈緒榜. K元2–立方體網(wǎng)絡(luò)SIMD計算機圖像模板匹配并行算法[J]. 計算機學(xué)報，2001，24(11)：1296–1301.

［3］ 趙東明，羅亮. 基于DNA計算的圖像模板匹配算法[J]. 華中科技大學(xué)學(xué)報：自然科學(xué)版，2013，41(2)：97–101.

［4］ 馬永軍，吳文旭，何鏘鏘. 一種利用多核計算的目標(biāo)檢測算法[C]//Proceedings of 2010 International Conference on Services Science，Management and Engineering. Hongkong：IITA，2010：209–212.

［5］ Rajasekaran S. Efficient parallel algorithms for template matching[J]. Parallel Processing Letters，2002，12(3/4)：359–364.

［6］ Anderson R F，Kirtzic J S，Daescu O. Applying parallel design techniques to template matching with GPUs[M]. High Performance Computing for Computational Science：VECPAR 2010. Berlin，Heidelberg：Springer Berlin Heidelberg，2011：456–468

［7］ 張保，董小社，白秀秀，等. CPU-GPU系統(tǒng)中基于剖分的全局性能優(yōu)化方法[J]. 西安交通大學(xué)學(xué)報，2012，46(2)：17–23.

［8］ NVIDIA. NVIDIA CUDA C Programming Guide：Version 5.0[EB/OL].[2012–10–01]. http：//www.nvidia. cn/object/maintenance-cudazone-cn.html.

［9］ 仇德元. GPGPU編程技術(shù)：從GLSL，CUDA到OpenGL[M]. 北京：機械工業(yè)出版社，2011.

［10］ Yoo J C，Han T H. Fast normalized cross-correlation [J]. Circuits，Systems and Signal Processing，2009，28(6)：819–843.

責(zé)任編輯：常濤

Parallel Algorithm of CPU and GPU-oriented Heterogeneous Computation in Template Matching Target Recognition

MA Yongjun1，YUAN Ying1，LI Hao2

(1. College of Computer Science and Information Engineering，Tianjin University of Science & Technology，Tianjin 300222，China；2. Tianjin Ruihe Tianfu Science & Technology Ltd.Co.，Tianjin 300384，China)

Moving object recognition algorithm with high-definition video data suffers from large computation complexities and slow speed. With NVIDIA Tesla K20,c GPU，a method of accelerating the template matching target tracking algorithm with the heterogeneous system integrated with CPU and GPU was proposed. The parallel algorithm was designed by three optimizing means：constant memory，the internal memory of SMX and the brief calculation of correlation coefficient. Finally，the program was coded on compute unified device architecture and tested. The results show that the designed algorithm can obviously improve the real-time performance of the algorithm and guarantee the recognition effect.

template matching；target recognition；parallel computing；compute unified device architecture(CUDA)；graphic processing unit(GPU)

TP311

A

1672-6510(2014)04-0048-05

10.13364/j.issn.1672-6510.2014.04.011

2014–02–24；

2014–05–04

天津市科技支撐計劃重點資助項目(12ZCZDGX02400)

馬永軍（1970—），男，吉林長春人，教授，yjma@tust.edu.cn.