基于并行计算的多目标跟踪系统时间复杂度优化策略探索

刘 杰，洪月华

(广西经济管理干部学院计算机系，广西 南宁 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）阶段性研究成果。