基于并行計算的多目標跟蹤系統時間復雜度優化策略探索

劉 杰，洪月華

(廣西經濟管理干部學院計算機系，廣西 南寧 530007)

基于并行計算的多目標跟蹤系統時間復雜度優化策略探索

劉 杰，洪月華*

(廣西經濟管理干部學院計算機系，廣西 南寧 530007)

為了降低多目標、多特征跟蹤系統的時間復雜度，分析了跟蹤系統運行的特性，引入了并行計算模型對跟蹤系統的串行部分重新設計，提出了檢測模塊與跟蹤模塊的并行化策略，理論分析表明并行計算模型可在較大程度上降低多目標跟蹤系統的時間復雜度。

多目標跟蹤系統；并行計算

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

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

圖像處理技術一般應用在工業級的嵌入式設備較多，這些設備大都采用單處理器的串行執行結構，目前，由于低功耗的多處理器和GPU圖像處理單元的廣泛應用，專門針對全天候監控場景的多核心圖像處理嵌入式設備研發也突破了原有的技術瓶頸。因此可以預見，在后續的將來，如何利用現有的并行計算平臺和并行程序設計技術對圖像處理進行進一步的優化改進，將圖像處理的串行算法優化成并行算法將成為圖像領域的研究熱點和難點。

1 圖像處理技術引入并行計算模型

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

1.1 并行計算技術中的圖像處理任務分配

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

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

1.2 子任務處理結果匯總

當子任務在各個處理器處理完畢后，系統要能正確的將子任務的運行結果進行匯總。對于以數據分配方式的并行任務進行匯總，要將處理好的各個子圖像數據塊進行拼接成最后的結果圖像數據，而對于非數據方式劃分的子任務，要將子任務的運行結果信息匯總到最后的公共結果數據區域。

2 多目標跟蹤并行運算體系設計

2.1 多特征檢測運算模塊并行化處理

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

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

2.2 跟蹤目標特征提取模塊的并行化處理

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

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

2.3 多目標跟蹤模塊并行計算策略

檢測模塊在檢測到多個跟蹤目標之后，跟蹤系統依據已經提取的特征在一個估測的ROI區域進行特征匹配，匹配成功則輸出下一幀目標物體的位置。由于對每個物體的跟蹤都是獨立的運算模式，因此可以將多目標的跟蹤在高層邏輯上進行動態任務分配的方式來并行化處理。

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

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

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

3 實時性評估方法分析

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

4 結論

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

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

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

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

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

[5]劉杰,一種基于多特征融合的自適應目標跟蹤算法的研究[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- )，男，廣西扶綏人，工程師，工學碩士，研究方向為圖像處理技術。*洪月華(1973- )，女，廣西貴港人，教授，工學碩士，研究方向為并行計算，人工智能。

本文為2015年國家社會科學基金項目“大數據并行聚類關鍵技術研究”（編號:15XTQ010）、2015年廣西高校科學技術研究項目“人工智能算法在傳感器網絡中分布式挖掘應用研究”（編號:KY2015YB351）和2015年廣西高校科學技術研究項目“多變場景下的特征融合目標跟蹤算法的研究”（編號：KY2015LX566）階段性研究成果。