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

馬永軍，袁 贏，李 灝

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

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

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

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

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

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

模板匹配運(yùn)動(dòng)目標(biāo)識(shí)別已廣泛應(yīng)用到視頻監(jiān)控等領(lǐng)域，然而隨著視頻信息高清化、數(shù)字化發(fā)展，在視頻處理領(lǐng)域中基于模板匹配的運(yùn)動(dòng)目標(biāo)識(shí)別算法的計(jì)算代價(jià)高，實(shí)時(shí)性降低，因而迫切需要提高計(jì)算能力．目前在此領(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)計(jì)算機(jī)．另外，趙東明等[3]利用DNA計(jì)算的并行性實(shí)現(xiàn)模板匹配算法的并行化；馬永軍等[4]利用多核平臺(tái)使用OpenMP對模板匹配進(jìn)行加速．這2種算法均基于CPU實(shí)現(xiàn)，而CPU并不擅長并行計(jì)算，無法解決在高清環(huán)境下視頻數(shù)據(jù)量大、實(shí)時(shí)處理性能不佳的問題．Rajasekaran[5]通過FFT技術(shù)獲得有效的模板匹配并行算法，但存在算法計(jì)算量巨大的問題；Anderson等[6]通過GPU對模板匹配進(jìn)行加速，但沒有充分挖掘異構(gòu)平臺(tái)的優(yōu)勢，仍有提升空間．因此，提高基于模板匹配目標(biāo)識(shí)別算法性能具有現(xiàn)實(shí)意義.

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

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

1 GPU和CUDA編程介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4 結(jié) 語

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

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

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

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

［4］ 馬永軍，吳文旭，何鏘鏘. 一種利用多核計(jì)算的目標(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é)報(bào)，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]. 北京：機(jī)械工業(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

天津市科技支撐計(jì)劃重點(diǎn)資助項(xiàng)目(12ZCZDGX02400)

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