基于并行計(jì)算的多目標(biāo)跟蹤系統(tǒng)時間復(fù)雜度優(yōu)化策略探索

劉 杰，洪月華

(廣西經(jīng)濟(jì)管理干部學(xué)院計(jì)算機(jī)系，廣西 南寧 530007)

基于并行計(jì)算的多目標(biāo)跟蹤系統(tǒng)時間復(fù)雜度優(yōu)化策略探索

劉 杰，洪月華*

(廣西經(jīng)濟(jì)管理干部學(xué)院計(jì)算機(jī)系，廣西 南寧 530007)

為了降低多目標(biāo)、多特征跟蹤系統(tǒng)的時間復(fù)雜度，分析了跟蹤系統(tǒng)運(yùn)行的特性，引入了并行計(jì)算模型對跟蹤系統(tǒng)的串行部分重新設(shè)計(jì)，提出了檢測模塊與跟蹤模塊的并行化策略，理論分析表明并行計(jì)算模型可在較大程度上降低多目標(biāo)跟蹤系統(tǒng)的時間復(fù)雜度。

多目標(biāo)跟蹤系統(tǒng)；并行計(jì)算

多目標(biāo)跟蹤(MOT)是實(shí)時圖像處理中的一個熱點(diǎn)問題，由于現(xiàn)實(shí)場景的復(fù)雜性，要求多目標(biāo)跟蹤系統(tǒng)在設(shè)計(jì)上能夠滿足較高水平的實(shí)時性和精確性，并具有一定的系統(tǒng)容錯性。隨著工業(yè)級相機(jī)硬件水平的逐步提升，圖像的數(shù)據(jù)容量與監(jiān)控視頻場景尺寸也越來越大，使用目前先進(jìn)的全天候?qū)嵕肮I(yè)相機(jī)甚至能夠達(dá)到30FPS的高幀率，按照這樣的速度，在短短一分鐘內(nèi)大概產(chǎn)生2GB左右的視頻圖片序列，這么大的數(shù)據(jù)量要求多目標(biāo)跟蹤系統(tǒng)不得不在算法上考慮實(shí)時性能，否則將會出現(xiàn)掉幀和丟幀的現(xiàn)象；其次，現(xiàn)實(shí)業(yè)務(wù)對被跟蹤物體的描述提出更為精確的要求，如部分卡口場景要求MOT不僅能夠跟蹤到車輛，還要識別到司機(jī)的人臉以進(jìn)行身份校驗(yàn)，部分關(guān)鍵街道要求MOT對行人實(shí)現(xiàn)有效跟蹤的同時還要求能夠識別行人的姿態(tài)以進(jìn)行事故檢測。為了達(dá)到對物體的精確跟蹤，MOT里的核心跟蹤算法日趨復(fù)雜化，這導(dǎo)致了視頻跟蹤系統(tǒng)在實(shí)時性和精確性的實(shí)現(xiàn)考量上存在日趨尷尬的矛盾，通常為了實(shí)時性要求不得不降低和犧牲算法的精確性。

針對這樣的問題，大量的改進(jìn)算法被提出，其中利用并行計(jì)算思維對問題規(guī)模進(jìn)行優(yōu)化處理是其中一種非常好的思路，楊偉健、姚慶棟[1]采用兩種不同的并行技術(shù)所代表的處理器研究底層圖像算法運(yùn)行效率和資源分配問題；趙冉、楊碩[2]提出將并行計(jì)算引入到工業(yè)級別的嵌入式圖像系統(tǒng)；余霞等[3]使用MPI對醫(yī)學(xué)圖像進(jìn)行并行處理，并比較了圖像Sobel算子在圖像處理的串行執(zhí)行和并行執(zhí)行的效率；周鵬飛等[4]利用Hadoop平臺的海量存儲和高性能分布式處理能力設(shè)計(jì)了視頻處理系統(tǒng)，該系統(tǒng)能夠?qū)Ａ繄D像進(jìn)行特征檢索。

圖像處理技術(shù)一般應(yīng)用在工業(yè)級的嵌入式設(shè)備較多，這些設(shè)備大都采用單處理器的串行執(zhí)行結(jié)構(gòu)，目前，由于低功耗的多處理器和GPU圖像處理單元的廣泛應(yīng)用，專門針對全天候監(jiān)控場景的多核心圖像處理嵌入式設(shè)備研發(fā)也突破了原有的技術(shù)瓶頸。因此可以預(yù)見，在后續(xù)的將來，如何利用現(xiàn)有的并行計(jì)算平臺和并行程序設(shè)計(jì)技術(shù)對圖像處理進(jìn)行進(jìn)一步的優(yōu)化改進(jìn)，將圖像處理的串行算法優(yōu)化成并行算法將成為圖像領(lǐng)域的研究熱點(diǎn)和難點(diǎn)。

1 圖像處理技術(shù)引入并行計(jì)算模型

圖像處理技術(shù)引入并行計(jì)算模型不可避免的要考慮到的兩個問題，一個是如何把原來的串行執(zhí)行的圖像算法任務(wù)進(jìn)行重新劃分成若干個可以并行執(zhí)行的子任務(wù)，分配到并行的處理器上處理，各個子任務(wù)具有一定的獨(dú)立性，另一個就是要考慮如何將執(zhí)行完成的子任務(wù)的計(jì)算結(jié)果歸并匯總到最后的結(jié)果[5]。

1.1 并行計(jì)算技術(shù)中的圖像處理任務(wù)分配

圖像算法任務(wù)分配的方式大體可以分為兩類，一類是將串行的圖像處理任務(wù)進(jìn)行線性劃分成若干個可以并行執(zhí)行的子任務(wù)，比如提取一幅圖像的特征，不僅需要sobel算子的特征圖，同時還需要candy算子的特征圖，就可以將這兩個獨(dú)立的圖像子任務(wù)放到不同的處理器去執(zhí)行。第二類是將圖像的數(shù)據(jù)處理區(qū)域進(jìn)行數(shù)據(jù)劃分，然后將對不同數(shù)據(jù)區(qū)域的圖像處理過程分配到多個處理器去處理，最后再將處理后的子圖拼接成最后的圖像。

圖像處理中的任務(wù)分配，要根據(jù)圖像算法框架和實(shí)時需求因地制宜的采取不同的任務(wù)劃分方式，隨著圖像處理算法的日趨復(fù)雜化，在整個算法周期會對串行任務(wù)多次并行化以滿足算法上的實(shí)時性和精確性需求。

1.2 子任務(wù)處理結(jié)果匯總

當(dāng)子任務(wù)在各個處理器處理完畢后，系統(tǒng)要能正確的將子任務(wù)的運(yùn)行結(jié)果進(jìn)行匯總。對于以數(shù)據(jù)分配方式的并行任務(wù)進(jìn)行匯總，要將處理好的各個子圖像數(shù)據(jù)塊進(jìn)行拼接成最后的結(jié)果圖像數(shù)據(jù)，而對于非數(shù)據(jù)方式劃分的子任務(wù)，要將子任務(wù)的運(yùn)行結(jié)果信息匯總到最后的公共結(jié)果數(shù)據(jù)區(qū)域。

2 多目標(biāo)跟蹤并行運(yùn)算體系設(shè)計(jì)

2.1 多特征檢測運(yùn)算模塊并行化處理

多目標(biāo)跟蹤系統(tǒng)從總體算法任務(wù)來看，分為檢測模塊、跟蹤模塊、軌跡分析模塊等幾個較大的處理模塊。其中較為耗時的圖像處理運(yùn)算位于檢測模塊中的特征檢測、跟蹤模塊中的特征提取和目標(biāo)匹配模塊。

首先需要觀測的是多目標(biāo)跟蹤系統(tǒng)檢測運(yùn)算中最為耗時的部分，檢測模塊中，如果采用簡單的運(yùn)動分割和背景前景分割，耗時不大，但如果采用了更為精細(xì)化的特征檢測（如使用adaboost強(qiáng)分類進(jìn)行多尺度的特征檢測在車輛車身中檢測一個車牌特征），將會產(chǎn)生較為復(fù)雜的檢測運(yùn)算和時間損耗。對于這樣的方式，可以采取數(shù)據(jù)分割的方式給圖像進(jìn)行方格式分解處理，為了避免被檢測特征正好位于圖像數(shù)據(jù)的分割邊界，可以采取將分割框重置到圖像邊界進(jìn)行再次截取，這樣會產(chǎn)生局部圖像數(shù)據(jù)比原圖要大一些，具體的大小根據(jù)被檢測的特征目標(biāo)估測尺寸而定。

2.2 跟蹤目標(biāo)特征提取模塊的并行化處理

對圖像多個特征的提取處理的先決條件大部分為圖像原圖，因此可以將檢測模塊中的特征提取的任務(wù)并行化，如表1所示。特征點(diǎn)和輪廓特征的提取運(yùn)算一般通過不同算子卷積運(yùn)算以獲得穩(wěn)定特征點(diǎn)和輪廓信息，顏色特征通過一系列的直方圖或HSV變換獲得塊信息，小波特征通過小波變換來提取。這些特征需要原圖或原圖的多尺度圖像來處理，因此可以將這些特征提取任務(wù)并行化。

表1 不同的特征提取先決條件

2.3 多目標(biāo)跟蹤模塊并行計(jì)算策略

檢測模塊在檢測到多個跟蹤目標(biāo)之后，跟蹤系統(tǒng)依據(jù)已經(jīng)提取的特征在一個估測的ROI區(qū)域進(jìn)行特征匹配，匹配成功則輸出下一幀目標(biāo)物體的位置。由于對每個物體的跟蹤都是獨(dú)立的運(yùn)算模式，因此可以將多目標(biāo)的跟蹤在高層邏輯上進(jìn)行動態(tài)任務(wù)分配的方式來并行化處理。

假設(shè)在T時刻只有一個物體被跟蹤，當(dāng)T+1時刻又檢測到了第二個目標(biāo)物體，那么就把第二個目標(biāo)物體的跟蹤任務(wù)分配給第二個處理核心，依次往復(fù)，直到所有處理單元被分配完為止，任務(wù)分派的關(guān)鍵點(diǎn)是在任意時刻，新分派的目標(biāo)任務(wù)總是要分派到空閑的或任務(wù)量少的處理核心。這樣，就能最大程度的在高層邏輯上將算法復(fù)雜度降下來。

由于在高層邏輯上已經(jīng)對跟蹤物體進(jìn)行了邏輯劃分，而每個物體所對應(yīng)的圖像區(qū)域位置固定，因此需要每個獨(dú)立的處理單元能夠共享到完整的圖像特征數(shù)據(jù)，而每個處理單元會根據(jù)當(dāng)前跟蹤物體的多個特征的強(qiáng)弱對比從特征數(shù)據(jù)中自適應(yīng)尋找最為穩(wěn)健的跟蹤特征來匹配。

當(dāng)每個物體的跟蹤處理單元完成了對物體的特征匹配跟蹤后，要將跟蹤物體的關(guān)鍵數(shù)據(jù)信息，物體當(dāng)前幀的位置坐標(biāo)、軌跡、跟蹤的特征向量等寫入到共享區(qū)域進(jìn)行任務(wù)的歸并。軌跡分析模塊將根據(jù)這些關(guān)鍵信息對物體進(jìn)行圖像標(biāo)記和軌跡分析。

3 實(shí)時性評估方法分析

假設(shè)在理想環(huán)境下（處理器核心足夠多，通信時間代價為0），多目標(biāo)跟蹤系統(tǒng)在串行設(shè)計(jì)上的運(yùn)行時間可表述為檢測耗時與跟蹤耗時，假設(shè)在原圖的上每一幀的檢測耗時為Ts，在進(jìn)行數(shù)據(jù)劃分任務(wù)后，理論運(yùn)行時間變?yōu)閙ax(Ts1,…,Tsn)，其中表示原圖的數(shù)據(jù)大小，si表示數(shù)據(jù)并行化后的每個子任務(wù)的數(shù)據(jù)塊。而跟蹤時間原有的時間復(fù)雜度表示為T01+…+T0n，而如果成功并行化后，跟蹤時間降為max(T01,…,T0n)，問題規(guī)模的時間復(fù)雜度獲得較為可觀的改進(jìn)。但一般現(xiàn)實(shí)條件而言，會受到機(jī)器體系的制約，如處理器核心數(shù)量和低功耗的要求，以及通信代價，這些都是要在實(shí)際應(yīng)用中要考慮進(jìn)去的關(guān)鍵因素。

4 結(jié)論

本文在探索了并行計(jì)算模型的基礎(chǔ)上，研究了如何將其加入到多目標(biāo)跟蹤系統(tǒng)以改進(jìn)其實(shí)時性能，并在多目標(biāo)跟蹤系統(tǒng)的復(fù)雜度較高的模塊給出了并行化的任務(wù)分派思想，同時還提出了串行化與并行化的實(shí)時性優(yōu)化指標(biāo)，但真實(shí)的并行計(jì)算系統(tǒng)環(huán)境還存在通信時間代價、任務(wù)分配時間代價需要考慮驗(yàn)證，今后研究工作要考慮多個并行任務(wù)的通信瓶頸和通信代價的問題，這樣更貼合實(shí)際的多目標(biāo)跟蹤系統(tǒng)并行處理的情況。

[1]楊偉健,姚慶棟.在圖像處理應(yīng)用中幾種并行計(jì)算技術(shù)的比較[J].信號處理,2000,16(4):367-369.

[2]趙冉,楊碩.基于可并行計(jì)算的嵌入式圖像處理方法的分析[J].信息技術(shù)，2012，(10)：80-81.

[3]余霞,葛紅,何俊,等.基于MPI的并行醫(yī)學(xué)圖像處理[J].計(jì)算機(jī)工程與科學(xué),2009,31(3):32-35.

[4]周鵬飛,郭喬進(jìn),胡杰.基于Hadoop平臺的視頻處理系統(tǒng)設(shè)計(jì)[J].信息化研究,2016,42(6):64-67 .

[5]劉杰,一種基于多特征融合的自適應(yīng)目標(biāo)跟蹤算法的研究[J],大眾科技,2016,14(1):6-10.

［編校：楊 琴］

Time Complexity Optimization of Multi-target Tracking System Based on Parallel Computing Strategy

LIU Jie, HONG Yue-hua*
(Department of Computer Science, Guangxi Cadre University of Economics and Management, Nanning Guangxi530007)

In order to reduce time complexity of the multi-target and multi-feature tracking system, the paper analyzed the characteristic of the tracking system, and redesigned the serial part of the tracking system based on parallel computing model, and in addition, it proposed the parallelization strategy of detection module and tracking module. Theoretical analysis shows that the parallel computation model can reduce the time complexity of multi-target tracking system to a great extent.

multi-target tracking system; parallel computing

TP391.41

A

1671-9654(2017)03-0093-03

10.13829/j.cnki.issn.1671-9654.2017.03.028

2017-07-04

劉杰(1982- )，男，廣西扶綏人，工程師，工學(xué)碩士，研究方向?yàn)閳D像處理技術(shù)。*洪月華(1973- )，女，廣西貴港人，教授，工學(xué)碩士，研究方向?yàn)椴⑿杏?jì)算，人工智能。

本文為2015年國家社會科學(xué)基金項(xiàng)目“大數(shù)據(jù)并行聚類關(guān)鍵技術(shù)研究”（編號:15XTQ010）、2015年廣西高?？茖W(xué)技術(shù)研究項(xiàng)目“人工智能算法在傳感器網(wǎng)絡(luò)中分布式挖掘應(yīng)用研究”（編號:KY2015YB351）和2015年廣西高?？茖W(xué)技術(shù)研究項(xiàng)目“多變場景下的特征融合目標(biāo)跟蹤算法的研究”（編號：KY2015LX566）階段性研究成果。