馬永軍，袁 贏，李 灝

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

面向CPU＋GPU異構平臺的模板匹配目標識別并行算法

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

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

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

模板匹配；目標識別；并行計算；統(tǒng)一設備計算架構；圖形處理器

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

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

本文提出一種采用最新的NVIDIA Tesla GPU構建CPU＋GPU異構平臺，并進行CUDA并行編程的方法，利用CPU＋GPU異構多核的高并行能力，使用最新的NVIDIA Tesla K20c GPU對模版匹配目標識別并行算法進行設計．

1 GPU和CUDA編程介紹

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

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

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

2 模板匹配目標識別的GPU并行算法設計

2.1 滑動模板匹配目標識別算法分析

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

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

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

2.2 模板匹配并行算法總體設計

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 存儲器層次結構圖Fig. 4 Memory hierarchy

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

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

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

2.4 模板匹配目標識別并行算法總體流程

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

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

3 實 驗

3.1 實驗環(huán)境

硬件平臺：超云服務器，GPU為Tesla K20c，含有13顆極致流多處理器，每個極致流多處理器上有192顆CUDA核心，其核心頻率為706,MHz，顯存帶寬為320,bit，顯存為4,GB；CPU為Intel Xeon CPU 3.1,GHz；系統(tǒng)內存為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 實驗結果與分析

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

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

3種方法的實驗對比見表1．分析表1可知：(1)對同一幅圖像進行特征點檢測時，方法3(基于GPU的優(yōu)化并行模板匹配目標識別算法)與方法1(基于CPU的串行模板匹配目標識別算法)和方法2(基于GPU的未優(yōu)化并行模板匹配目標識別算法)相比，極大地提高了算法的實時性，能夠滿足實際需求．(2)對于本實驗，雖然將串行算法(方法1)翻譯成在GPU上運行的并行程序(方法2)提高了算法效率，但是優(yōu)化后的算法(方法3)能夠取得更好的算法實時性．可見，并行算法的設計和開發(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 結 語

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

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

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

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

［4］ 馬永軍，吳文旭，何鏘鏘. 一種利用多核計算的目標檢測算法[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]. 西安交通大學學報，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編程技術：從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.

責任編輯：常濤

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.