運(yùn)動(dòng)目標(biāo)檢測(cè)與特征提取算法的多層次并行優(yōu)化

彭 彪，張重陽(yáng)，2，鄭世寶，2，田 廣

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

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

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

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

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

1 運(yùn)動(dòng)目標(biāo)檢測(cè)與特征提取串行算法簡(jiǎn)介

本文的運(yùn)動(dòng)目標(biāo)檢測(cè)與描述串行算法的流程如圖1所示，主要包括視頻采集、前景檢測(cè)、團(tuán)塊檢測(cè)與跟蹤和特征提取4個(gè)模塊。前景檢測(cè)模塊采用的是GMM背景建模［2］，團(tuán)塊檢測(cè)與跟蹤模塊采用的是基于連通區(qū)域的檢測(cè)跟蹤算法，特征提取模塊提取了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個(gè)子模塊［13－14］。對(duì)于實(shí)際監(jiān)控視頻，串行算法子模塊較多，耗時(shí)大，難以實(shí)現(xiàn)實(shí)時(shí)處理。

圖1 運(yùn)動(dòng)目標(biāo)檢測(cè)與特征提取串行算法流程圖

2 運(yùn)動(dòng)目標(biāo)檢測(cè)與特征提取三層并行算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果

本文將提出的3層雙模塊并行算法應(yīng)用于一個(gè)四核CPU平臺(tái)上，針對(duì)多個(gè)實(shí)際監(jiān)控場(chǎng)景中的視頻進(jìn)行測(cè)試驗(yàn)證。

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

圖7 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)平臺(tái)為一個(gè)四核工控機(jī)，CPU為Intel Core i5－2510E 2.5 GHz，內(nèi)存為 2 Gbyte。

實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)為并行加速比S［4－5］，即

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

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

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

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

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

表1 頂層流水線并行算法實(shí)驗(yàn)結(jié)果

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

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

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

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

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

表3 特征提取模塊各子模塊耗時(shí)分析

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

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

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

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

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

表5 HTD子模塊耗時(shí)統(tǒng)計(jì)表

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

4 小結(jié)

本文針對(duì)監(jiān)控視頻中的運(yùn)動(dòng)目標(biāo)檢測(cè)與特征提取的串行算法，分別從頂層流水線結(jié)構(gòu)、中層特征提取模塊功能獨(dú)立性和底層HTD子模塊數(shù)據(jù)獨(dú)立性三個(gè)層次提出了一個(gè)面向多核CPU平臺(tái)的多層次多模塊并行優(yōu)化算法。通過(guò)針對(duì)多個(gè)實(shí)際監(jiān)控視頻場(chǎng)景的實(shí)驗(yàn)結(jié)果表明，本文提出的并行算法獲得了預(yù)期的加速比(平均為3.56，Amdahl理論極限為4)，基本能實(shí)現(xiàn)對(duì)實(shí)際監(jiān)控視頻的實(shí)時(shí)處理(對(duì)于目標(biāo)數(shù)適中的VGA分辨率的場(chǎng)景處理速率為31 f/s)。此外，本文由串行算法出發(fā)，從多個(gè)層次分析其并行潛能，提出的并行優(yōu)化方法對(duì)于所有的串行算法的并行優(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］陳國(guó)良，孫廣中，徐云，等.并行算法研究方法學(xué)［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31(9):1493－1502.

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

［8］楊凌云.基于多核技術(shù)的并行圖像檢索系統(tǒng)的研究［D］.北京:北京化工大學(xué)，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算法的并行實(shí)現(xiàn)及應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(020):56－59.

［11］王成良，謝克家，劉昕.多核圖像處理并行設(shè)計(jì)范式多核圖像處理并行設(shè)計(jì)范式的研究與應(yīng)用［J］.計(jì)算機(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.