運動目標檢測與特征提取算法的多層次并行優(yōu)化

彭 彪，張重陽，2，鄭世寶，2，田 廣

(1.上海交通大學電子工程系圖像通信與網(wǎng)絡(luò)工程研究所，上海 200240;

2.上海市數(shù)字媒體處理與傳輸重點實驗室，上海 200240;3.博康智能網(wǎng)絡(luò)科技有限公司，上海 200233)

智能視頻監(jiān)控系統(tǒng)中最關(guān)鍵的模塊是運動目標的檢測與特征描述。對于運動目標檢測［1］，同時考慮準確率與實時性，混合高斯模型［2］(Gaussian Mixed Model，GMM)應(yīng)用得非常普遍。對于運動目標特征描述，MPEG－7［3］標準定義了大量底層特征描述子，廣泛應(yīng)用于目標描述。

隨著多核平臺的普及，并行計算［4－5］逐漸被廣泛應(yīng)用于各個領(lǐng)域，文獻［6］介紹了常用的并行優(yōu)化方法。圖像和視頻的處理牽涉到了大量粗粒度的計算，非常適合并行優(yōu)化。文獻［7］將流水線優(yōu)化方法應(yīng)用到了高清視頻的實時解碼，并針對其中的瓶頸模塊設(shè)計了一個數(shù)據(jù)劃分并行算法;文獻［8］將功能劃分優(yōu)化方法應(yīng)用到了圖像檢索，加快了圖像檢索系統(tǒng)的響應(yīng)速度;文獻［9－11］分別將數(shù)據(jù)劃分優(yōu)化方法應(yīng)用到神經(jīng)網(wǎng)絡(luò)算法、SIFT算法和二維傅里葉變換，都取得了可觀的加速比。

基于上述優(yōu)化方法，結(jié)合運動目標檢測和特征提取描述具體算法特點，本文提出了一種多核CPU平臺上的三層雙模塊并行算法，并在OpenMP［12］和四核CPU平臺上利用該并行算法實現(xiàn)了對監(jiān)控視頻目標檢測與特征提取的實時處理。本文提出的多層次并行優(yōu)化方法對分析串行算法的并行優(yōu)化具有普適性。

1 運動目標檢測與特征提取串行算法簡介

本文的運動目標檢測與描述串行算法的流程如圖1所示，主要包括視頻采集、前景檢測、團塊檢測與跟蹤和特征提取4個模塊。前景檢測模塊采用的是GMM背景建模［2］，團塊檢測與跟蹤模塊采用的是基于連通區(qū)域的檢測跟蹤算法，特征提取模塊提取了MPEG－7中定義的6種底層視頻特征［3］，包含了 DCD(Dominant Color Descriptor)，SCD(Scalable Color Descriptor)，CSD(Color Structure Descriptor)，CLD(Color Layout Descriptor)和 HTD(Homogeneous Texture Descriptor)、RSD(Region Shape Descriptor)6個子模塊［13－14］。對于實際監(jiān)控視頻，串行算法子模塊較多，耗時大，難以實現(xiàn)實時處理。

圖1 運動目標檢測與特征提取串行算法流程圖

2 運動目標檢測與特征提取三層并行算法設(shè)計

對于圖1的串行算法，各模塊相互間具有數(shù)據(jù)依賴，前后連接構(gòu)成了流水線，因而可以考慮設(shè)計流水線并行算法［6］進行優(yōu)化。此外，由于各模塊耗時不均衡，對于頂層流水線結(jié)構(gòu)中的瓶頸模塊(特征提取模塊)，利用模塊內(nèi)部的功能獨立性和數(shù)據(jù)獨立性，可以設(shè)計基于功能劃分［8］和數(shù)據(jù)劃分［9－11］的并行算法，在中層子模塊和底層子模塊中做進一步優(yōu)化。下文，針對圖1的串行算法分別從3個層次設(shè)計具體的并行優(yōu)化算法。

2.1 頂層流水線并行優(yōu)化算法

對圖1的串行算法，由于視頻采集和團塊檢測與跟蹤耗時較小，而特征提取模塊耗時相對較大，可將視頻采集、團塊檢測與跟蹤、前景檢測3個模塊合并為一個目標檢測模塊，與特征提取模塊組成兩級流水線結(jié)構(gòu)，如圖2所示。

圖2 頂層流水線結(jié)構(gòu)及其數(shù)據(jù)依賴關(guān)系

由圖2也可以得出目標檢測模塊與特征提取模塊的數(shù)據(jù)依賴情況。目標檢測模塊生產(chǎn)目標數(shù)據(jù)，而特征提取模塊消費目標數(shù)據(jù)，生產(chǎn)目標特征。由于特征提取模塊的耗時大于目標檢測模塊，即兩個模塊的耗時不均衡，且兩者存在數(shù)據(jù)依賴，因而需要設(shè)計緩存處理目標檢測模塊與特征提取模塊的數(shù)據(jù)交互。本文設(shè)計了一個深度為N(N=8)的FIFO緩存隊列，由N個目標數(shù)據(jù)指針組成，至多存儲N幀目標數(shù)據(jù)。FIFO緩存隊列以數(shù)組形式存儲目標數(shù)據(jù)指針，每個元素或為空，或指向由目標檢測模塊生成的某一幀的目標數(shù)據(jù)。此外，F(xiàn)IFO緩存隊列還包含了一個讀指針blob_read和一個寫指針blob_write，并具有3種狀態(tài)，如圖3所示。隊列正常時，目標檢測模塊生產(chǎn)目標數(shù)據(jù)，并將其寫入寫指針blob_write，在寫入完成后blob_write后移，而特征提取模塊從讀指針blob_read中讀入數(shù)據(jù)進行處理，在處理完成后釋放讀指針blob_read指向的目標數(shù)據(jù)，并將blob_read后移;隊列為滿時，目標檢測模塊暫停生產(chǎn)目標數(shù)據(jù);隊列為空時，特征提取模塊暫停消費目標數(shù)據(jù)。為了獲取FIFO緩存隊列的狀態(tài)，流水線并行算法需要額外設(shè)計一個FIFO緩存隊列管理模塊，負責判斷隊列的狀態(tài)。緩存隊列管理模塊由一個獨立的線程運行，目標檢測模塊或特征提取模塊的線程執(zhí)行完畢后觸發(fā)其執(zhí)行一次。

圖3 頂層流水線結(jié)構(gòu)的FIFO緩存隊列

結(jié)合上述的流水線并行原理和緩存管理策略，頂層流水線并行優(yōu)化算法如圖4所示。對于視頻的每一幀，目標檢測模塊生產(chǎn)目標數(shù)據(jù)，將其寫入FIFO緩存隊列的寫指針blob_write，并將其后移;特征提取模塊讀取讀指針blob_read的目標數(shù)據(jù)，生成目標特征，處理完成后釋放blob_read指向的目標數(shù)據(jù)，并將其后移;緩存管理模塊由目標檢測模塊和特征提取模塊觸發(fā)，負責判斷FIFO緩存隊列的狀態(tài)。兩個模塊并行執(zhí)行，且由于緩存管理模塊耗時(判斷隊列狀態(tài))可以忽略不計，故總耗時應(yīng)為瓶頸模塊(特征提取模塊)的耗時。

在OpenMP中，使用parallel sections語句將主線程分支為兩個并行執(zhí)行的子線程，使用nowait子句控制各子線程異步執(zhí)行，設(shè)置全局FIFO緩存隊列處理各子線程間的數(shù)據(jù)交互，具體算法偽代碼為:

圖4 頂層流水線并行優(yōu)化算法

2.2 中層功能劃分并行優(yōu)化算法

頂層流水線并行算法中，兩個模塊耗時不均衡，瓶頸為特征提取模塊，為進一步提升性能，需要深入分析特征提取模塊。

由圖1可知，特征提取模塊由6個子模塊組成(DCD，SCD，CLD，CSD，HTD和RSD)，由于6個子模塊輸入相同(目標檢測模塊生產(chǎn)的目標數(shù)據(jù))且功能相互獨立(各子模塊對輸入數(shù)據(jù)只有讀操作，且獨立地生成各自的特征信息)，因而可以考慮設(shè)計功能劃分并行算法［8］進行優(yōu)化。具體地，依據(jù)各子模塊的平均耗時，將6個子模塊劃分為2個子模塊組，HTD單獨為HTD子模塊組，DCD，SCD，CSD，CLD和RSD組成其他子模塊組。兩個子模塊組分別由獨立的線程在不同的處理器核心上并行執(zhí)行。由于兩個子模塊組對輸入數(shù)據(jù)都只有讀操作，因而相互之間沒有數(shù)據(jù)依賴，無需設(shè)計緩存隊列處理數(shù)據(jù)交互。

功能劃分并行優(yōu)化算法如圖5所示。特征提取模塊讀入目標數(shù)據(jù)后，HTD子模塊組和其他子模塊組同時并行地處理目標數(shù)據(jù)，生成各自的特征信息。所有子線程完全處理完成后，在主線程中同步，生成最終的目標特征信息。

圖5 中層功能劃分并行優(yōu)化算法

中層并行算法的OpenMP實現(xiàn)和表1類似，采用parallel sections將主線程分支為兩個獨立的子線程并行執(zhí)行。值得注意的是，由于兩個子模塊組的不均衡性(HTD子模塊組耗時較大)，兩個子線程需要同步，因而存在線程等待，故特征提取模塊的總執(zhí)行時間等于瓶頸子模塊組(HTD)的執(zhí)行時間。

2.3 底層數(shù)據(jù)劃分并行優(yōu)化算法

頂層和中層并行優(yōu)化算法的瓶頸為HTD子模塊，為了進一步提升并行算法的性能，需要深入到底層HTD子模塊做進一步分析。

HTD子模塊的執(zhí)行流程可參考文獻［13］，其核心步驟為針對目標數(shù)據(jù)逐像素的傅里葉變換。對于快速傅里葉變換算法，頻域參數(shù)的計算相互之間是獨立的，具有數(shù)據(jù)獨立性，可考慮設(shè)計針對HTD生成結(jié)果的數(shù)據(jù)劃分并行優(yōu)化算法［9－11］。具體地，對于HTD要生成的頻域參數(shù)，將其劃分為兩個大小相等的子數(shù)據(jù)組，分別指派兩個子線程并行地處理。數(shù)據(jù)劃分并行算法如圖6所示。

圖6 底層數(shù)據(jù)劃分并行優(yōu)化算法

數(shù)據(jù)劃分并行算法的OpenMP實現(xiàn)也與表1類似，將HTD要生成的頻域參數(shù)劃分為兩個子數(shù)據(jù)級，采用parallel sections將主線程分支為兩個子線程并行地處理兩個子數(shù)據(jù)集。由于兩個子數(shù)據(jù)集大小相同，因而HTD子模塊的執(zhí)行時間將減半。

3 實驗與結(jié)果

本文將提出的3層雙模塊并行算法應(yīng)用于一個四核CPU平臺上，針對多個實際監(jiān)控場景中的視頻進行測試驗證。

實驗數(shù)據(jù)集如圖7所示，包括了不同場景、不同目標數(shù)、不同分辨率的監(jiān)控視頻。

圖7 實驗數(shù)據(jù)集

實驗平臺為一個四核工控機，CPU為Intel Core i5－2510E 2.5 GHz，內(nèi)存為 2 Gbyte。

實驗結(jié)果評價指標為并行加速比S［4－5］，即

由于本文并行算法中串行比例為0，依據(jù)Amdahl定律［4－5］，對于四核平臺，加速比的極限值為4。

為了驗證實時處理性能，本文還給出了并行算法的處理速率，單位為幀/秒(f/s)。

3.1 頂層流水線并行優(yōu)化算法實驗結(jié)果及分析

針對數(shù)據(jù)集中視頻，在處理結(jié)果誤差在可接受范圍內(nèi)的情況下，頂層流水線并行算法的實驗結(jié)果如表1所示。

頂層流水線并行算法將特征提取模塊與目標檢測模塊分配到兩個核處理，由于兩個模塊耗時的不均衡性，總的執(zhí)行時間應(yīng)等于瓶頸模塊(特征提取)的耗時。由表1可見，加速比基本達到了預(yù)期結(jié)果。

表1 頂層流水線并行算法實驗結(jié)果

表1中值得注意的是，對于Mid視頻，并行執(zhí)行時間少于串行瓶頸(特征提取)的耗時，出現(xiàn)了超線性加速［4－5］的情況。初步分析，可能的原因是并行執(zhí)行提高了高速緩存的命中率，與串行相比提高了處理器訪問數(shù)據(jù)的速度，加速了線程的執(zhí)行，下文將通過實驗對此進行佐證。

3.2 中層特征提取模塊功能劃分并行優(yōu)化算法實驗結(jié)果及分析

針對數(shù)據(jù)集中視頻，在處理結(jié)果誤差在可接受范圍內(nèi)的情況下，頂層流水線并行算法結(jié)合特征提取模塊功能劃分并行優(yōu)化算法的實驗結(jié)果如表2所示。

表2 頂層流水線并行結(jié)合中層特征提取模塊功能劃分并行算法實驗結(jié)果

對比表2與表1可見，結(jié)合了中層功能劃分算法后，總的執(zhí)行時間有了一定的優(yōu)化。為了進一步分析中層功能劃分并行算法的實驗結(jié)果，特征提取模塊各子模塊的串行耗時和功能劃分并行算法耗時如表3所示。中層功能劃分并行算法將HTD子模塊組與其他子模塊組分別指派到獨立的處理器核上處理，特征提取模塊的總執(zhí)行時間等于瓶頸子模塊組(HTD子模塊組)的執(zhí)行時間。由表3可見，功能劃分并行算法基本達到了預(yù)期的優(yōu)化效果。

表3 特征提取模塊各子模塊耗時分析

值得注意的是，在表3中，Road，Pets和Mid都出現(xiàn)了實驗3.1節(jié)中提到的超線性加速現(xiàn)象，即并行特征提取耗時低于串行瓶頸耗時(HTD)。下面通過設(shè)計一個簡單的實驗驗證前文分析的出現(xiàn)這種現(xiàn)象的原因。以Mid為例，特征提取模塊只包含HTD子模塊，分別執(zhí)行串行算法和頂層流水線并行算法，得到特征提取模塊的耗時分別為串行54.591 274 s和并行42.230 714 s。由于特征提取模塊只包含HTD，流水線并行算法與串行算法的唯一區(qū)別在于特征提取模塊是否與目標檢測模塊具有緩存交互，而緩存數(shù)據(jù)的訪問速率與CPU高速緩存的命中率有關(guān)，因而可以初步驗證前文分析原因的正確性，即并行算法增大了處理器高速緩存對數(shù)據(jù)的命中率，導致了超線性加速的出現(xiàn)。

3.3 三層并行優(yōu)化算法實驗結(jié)果及分析

針對數(shù)據(jù)集中視頻，在處理結(jié)果在可接受范圍內(nèi)的情況下，結(jié)合了頂層流水線、中層功能劃分和底層數(shù)據(jù)劃分的三層并行優(yōu)化算法的實驗結(jié)果如表4所示。

表4 3層并行優(yōu)化算法實驗結(jié)果

由表4可知，增加了底層數(shù)據(jù)劃分并行算法后，算法的總耗時有了明顯的優(yōu)化。為了進一步分析底層數(shù)據(jù)劃分并行算法的實驗結(jié)果，HTD子模塊的耗時如表5所示。結(jié)合表5和表4可知，底層數(shù)據(jù)劃分并行算法基本達到了預(yù)期的加速比。

表5 HTD子模塊耗時統(tǒng)計表

綜合上述實驗結(jié)果可知，本文提出的三層雙模塊并行優(yōu)化算法，對于目標檢測與特征描述串行算法，在四核CPU平臺上，針對不同的實際監(jiān)控視頻場景達到了預(yù)期的加速比(平均為3.56，理論極限為4)，基本能滿足實時處理的需要(對于VGA分辨率處理速率為31 f/s)。本文由串行算法出發(fā)，通過多層次的分析提出了并行優(yōu)化方法，對于所有串行算法的并行優(yōu)化具有普遍適用性。

4 小結(jié)

本文針對監(jiān)控視頻中的運動目標檢測與特征提取的串行算法，分別從頂層流水線結(jié)構(gòu)、中層特征提取模塊功能獨立性和底層HTD子模塊數(shù)據(jù)獨立性三個層次提出了一個面向多核CPU平臺的多層次多模塊并行優(yōu)化算法。通過針對多個實際監(jiān)控視頻場景的實驗結(jié)果表明，本文提出的并行算法獲得了預(yù)期的加速比(平均為3.56，Amdahl理論極限為4)，基本能實現(xiàn)對實際監(jiān)控視頻的實時處理(對于目標數(shù)適中的VGA分辨率的場景處理速率為31 f/s)。此外，本文由串行算法出發(fā)，從多個層次分析其并行潛能，提出的并行優(yōu)化方法對于所有的串行算法的并行優(yōu)化具有普遍適用性。

:

［1］HU W，TAN T，WANG L，et al.A survey on visual surveillance of object motion and behaviors［J］.IEEE Trans.Systems，Man.，and Cybernetics:Applications and Reviews，2004，34(3):334－352.

［2］ZIVKOVIC Z.Improved adaptive Gaussian mixture model for background subtraction［C］//Proc.17th International Conference on Pattern Recognition.［S.l.］:IEEE Press，2004:28－31.

［3］SIKORA T.The MPEG－7 visual standard for content description－an overview［J］.IEEE Trans.Circuits and Systems for Video Technology，2001，11(6):696－702.

［4］ASANOVIC K，BODIK R，DEMMEL J，et al.A view of the parallel computing landscape［J］.Communications of the ACM，2009，52(10):56－67.

［5］ASANOVIC K，BODIK R，CATANZARO B C，et al.The landscape of parallel computing research:a view from Berkeley［R］.Berkeley:University of California，2006.

［6］陳國良，孫廣中，徐云，等.并行算法研究方法學［J］.計算機學報，2008，31(9):1493－1502.

［7］呂明洲，陳耀武.基于異構(gòu)多核處理器的H.264并行編碼算法［J］.計算機工程，2012，38(16):35－39.

［8］楊凌云.基于多核技術(shù)的并行圖像檢索系統(tǒng)的研究［D］.北京:北京化工大學，2008.

［9］JANG H，PARK A，JUNG K.Neural network implementation using cuda and openmp［C］//Proc.DICTA’08. ［S.l.］:IEEE Press，2008:155－161.

［10］韓龍，郭立，李玉云.SIFT算法的并行實現(xiàn)及應(yīng)用［J］.計算機工程與應(yīng)用，2010，46(020):56－59.

［11］王成良，謝克家，劉昕.多核圖像處理并行設(shè)計范式多核圖像處理并行設(shè)計范式的研究與應(yīng)用［J］.計算機工程，2011，37(14):220－222.

［12］DAGUM L，MENON R.OpenMP:an industry standard API for sharedmemory programming［J］.Computational Science&Engineering，IEEE，1998，5(1):46－55.

［13］RO Y M，KIM M，KANG H K，et al.MPEG－7 homogeneous texture descriptor［J］.ETRI Journal，2001，23(2):41－51.

［14］BOBER M.MPEG－7 visual shape descriptors［J］.IEEE Trans.Circuits and Systems for Video Technology，2001，11(6):716－719.