劉 杰，洪月華

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

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

劉 杰，洪月華*

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

[1]楊偉健,姚慶棟.在圖像處理應(yīng)用中幾種并行計(jì)算技術(shù)的比較[J].信號(hào)處理,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ái)的視頻處理系統(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年國(guó)家社會(huì)科學(xué)基金項(xiàng)目“大數(shù)據(jù)并行聚類(lèi)關(guān)鍵技術(shù)研究”（編號(hào):15XTQ010）、2015年廣西高?？茖W(xué)技術(shù)研究項(xiàng)目“人工智能算法在傳感器網(wǎng)絡(luò)中分布式挖掘應(yīng)用研究”（編號(hào):KY2015YB351）和2015年廣西高?？茖W(xué)技術(shù)研究項(xiàng)目“多變場(chǎng)景下的特征融合目標(biāo)跟蹤算法的研究”（編號(hào)：KY2015LX566）階段性研究成果。