运动目标检测与特征提取算法的多层次并行优化

彭 彪，张重阳，2，郑世宝，2，田 广

(1.上海交通大学电子工程系图像通信与网络工程研究所，上海 200240;

2.上海市数字媒体处理与传输重点实验室，上海 200240;3.博康智能网络科技有限公司，上海 200233)

智能视频监控系统中最关键的模块是运动目标的检测与特征描述。对于运动目标检测［1］，同时考虑准确率与实时性，混合高斯模型［2］(Gaussian Mixed Model，GMM)应用得非常普遍。对于运动目标特征描述，MPEG－7［3］标准定义了大量底层特征描述子，广泛应用于目标描述。

随着多核平台的普及，并行计算［4－5］逐渐被广泛应用于各个领域，文献［6］介绍了常用的并行优化方法。图像和视频的处理牵涉到了大量粗粒度的计算，非常适合并行优化。文献［7］将流水线优化方法应用到了高清视频的实时解码，并针对其中的瓶颈模块设计了一个数据划分并行算法;文献［8］将功能划分优化方法应用到了图像检索，加快了图像检索系统的响应速度;文献［9－11］分别将数据划分优化方法应用到神经网络算法、SIFT算法和二维傅里叶变换，都取得了可观的加速比。

基于上述优化方法，结合运动目标检测和特征提取描述具体算法特点，本文提出了一种多核CPU平台上的三层双模块并行算法，并在OpenMP［12］和四核CPU平台上利用该并行算法实现了对监控视频目标检测与特征提取的实时处理。本文提出的多层次并行优化方法对分析串行算法的并行优化具有普适性。

1 运动目标检测与特征提取串行算法简介

本文的运动目标检测与描述串行算法的流程如图1所示，主要包括视频采集、前景检测、团块检测与跟踪和特征提取4个模块。前景检测模块采用的是GMM背景建模［2］，团块检测与跟踪模块采用的是基于连通区域的检测跟踪算法，特征提取模块提取了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个子模块［13－14］。对于实际监控视频，串行算法子模块较多，耗时大，难以实现实时处理。

图1 运动目标检测与特征提取串行算法流程图

2 运动目标检测与特征提取三层并行算法设计

对于图1的串行算法，各模块相互间具有数据依赖，前后连接构成了流水线，因而可以考虑设计流水线并行算法［6］进行优化。此外，由于各模块耗时不均衡，对于顶层流水线结构中的瓶颈模块(特征提取模块)，利用模块内部的功能独立性和数据独立性，可以设计基于功能划分［8］和数据划分［9－11］的并行算法，在中层子模块和底层子模块中做进一步优化。下文，针对图1的串行算法分别从3个层次设计具体的并行优化算法。

2.1 顶层流水线并行优化算法

对图1的串行算法，由于视频采集和团块检测与跟踪耗时较小，而特征提取模块耗时相对较大，可将视频采集、团块检测与跟踪、前景检测3个模块合并为一个目标检测模块，与特征提取模块组成两级流水线结构，如图2所示。

图2 顶层流水线结构及其数据依赖关系

由图2也可以得出目标检测模块与特征提取模块的数据依赖情况。目标检测模块生产目标数据，而特征提取模块消费目标数据，生产目标特征。由于特征提取模块的耗时大于目标检测模块，即两个模块的耗时不均衡，且两者存在数据依赖，因而需要设计缓存处理目标检测模块与特征提取模块的数据交互。本文设计了一个深度为N(N=8)的FIFO缓存队列，由N个目标数据指针组成，至多存储N帧目标数据。FIFO缓存队列以数组形式存储目标数据指针，每个元素或为空，或指向由目标检测模块生成的某一帧的目标数据。此外，FIFO缓存队列还包含了一个读指针blob_read和一个写指针blob_write，并具有3种状态，如图3所示。队列正常时，目标检测模块生产目标数据，并将其写入写指针blob_write，在写入完成后blob_write后移，而特征提取模块从读指针blob_read中读入数据进行处理，在处理完成后释放读指针blob_read指向的目标数据，并将blob_read后移;队列为满时，目标检测模块暂停生产目标数据;队列为空时，特征提取模块暂停消费目标数据。为了获取FIFO缓存队列的状态，流水线并行算法需要额外设计一个FIFO缓存队列管理模块，负责判断队列的状态。缓存队列管理模块由一个独立的线程运行，目标检测模块或特征提取模块的线程执行完毕后触发其执行一次。

图3 顶层流水线结构的FIFO缓存队列

结合上述的流水线并行原理和缓存管理策略，顶层流水线并行优化算法如图4所示。对于视频的每一帧，目标检测模块生产目标数据，将其写入FIFO缓存队列的写指针blob_write，并将其后移;特征提取模块读取读指针blob_read的目标数据，生成目标特征，处理完成后释放blob_read指向的目标数据，并将其后移;缓存管理模块由目标检测模块和特征提取模块触发，负责判断FIFO缓存队列的状态。两个模块并行执行，且由于缓存管理模块耗时(判断队列状态)可以忽略不计，故总耗时应为瓶颈模块(特征提取模块)的耗时。

在OpenMP中，使用parallel sections语句将主线程分支为两个并行执行的子线程，使用nowait子句控制各子线程异步执行，设置全局FIFO缓存队列处理各子线程间的数据交互，具体算法伪代码为:

图4 顶层流水线并行优化算法

2.2 中层功能划分并行优化算法

顶层流水线并行算法中，两个模块耗时不均衡，瓶颈为特征提取模块，为进一步提升性能，需要深入分析特征提取模块。

由图1可知，特征提取模块由6个子模块组成(DCD，SCD，CLD，CSD，HTD和RSD)，由于6个子模块输入相同(目标检测模块生产的目标数据)且功能相互独立(各子模块对输入数据只有读操作，且独立地生成各自的特征信息)，因而可以考虑设计功能划分并行算法［8］进行优化。具体地，依据各子模块的平均耗时，将6个子模块划分为2个子模块组，HTD单独为HTD子模块组，DCD，SCD，CSD，CLD和RSD组成其他子模块组。两个子模块组分别由独立的线程在不同的处理器核心上并行执行。由于两个子模块组对输入数据都只有读操作，因而相互之间没有数据依赖，无需设计缓存队列处理数据交互。

功能划分并行优化算法如图5所示。特征提取模块读入目标数据后，HTD子模块组和其他子模块组同时并行地处理目标数据，生成各自的特征信息。所有子线程完全处理完成后，在主线程中同步，生成最终的目标特征信息。

图5 中层功能划分并行优化算法

中层并行算法的OpenMP实现和表1类似，采用parallel sections将主线程分支为两个独立的子线程并行执行。值得注意的是，由于两个子模块组的不均衡性(HTD子模块组耗时较大)，两个子线程需要同步，因而存在线程等待，故特征提取模块的总执行时间等于瓶颈子模块组(HTD)的执行时间。

2.3 底层数据划分并行优化算法

顶层和中层并行优化算法的瓶颈为HTD子模块，为了进一步提升并行算法的性能，需要深入到底层HTD子模块做进一步分析。

HTD子模块的执行流程可参考文献［13］，其核心步骤为针对目标数据逐像素的傅里叶变换。对于快速傅里叶变换算法，频域参数的计算相互之间是独立的，具有数据独立性，可考虑设计针对HTD生成结果的数据划分并行优化算法［9－11］。具体地，对于HTD要生成的频域参数，将其划分为两个大小相等的子数据组，分别指派两个子线程并行地处理。数据划分并行算法如图6所示。

图6 底层数据划分并行优化算法

数据划分并行算法的OpenMP实现也与表1类似，将HTD要生成的频域参数划分为两个子数据级，采用parallel sections将主线程分支为两个子线程并行地处理两个子数据集。由于两个子数据集大小相同，因而HTD子模块的执行时间将减半。

3 实验与结果

本文将提出的3层双模块并行算法应用于一个四核CPU平台上，针对多个实际监控场景中的视频进行测试验证。

实验数据集如图7所示，包括了不同场景、不同目标数、不同分辨率的监控视频。

图7 实验数据集

实验平台为一个四核工控机，CPU为Intel Core i5－2510E 2.5 GHz，内存为 2 Gbyte。

实验结果评价指标为并行加速比S［4－5］，即

由于本文并行算法中串行比例为0，依据Amdahl定律［4－5］，对于四核平台，加速比的极限值为4。

为了验证实时处理性能，本文还给出了并行算法的处理速率，单位为帧/秒(f/s)。

3.1 顶层流水线并行优化算法实验结果及分析

针对数据集中视频，在处理结果误差在可接受范围内的情况下，顶层流水线并行算法的实验结果如表1所示。

顶层流水线并行算法将特征提取模块与目标检测模块分配到两个核处理，由于两个模块耗时的不均衡性，总的执行时间应等于瓶颈模块(特征提取)的耗时。由表1可见，加速比基本达到了预期结果。

表1 顶层流水线并行算法实验结果

表1中值得注意的是，对于Mid视频，并行执行时间少于串行瓶颈(特征提取)的耗时，出现了超线性加速［4－5］的情况。初步分析，可能的原因是并行执行提高了高速缓存的命中率，与串行相比提高了处理器访问数据的速度，加速了线程的执行，下文将通过实验对此进行佐证。

3.2 中层特征提取模块功能划分并行优化算法实验结果及分析

针对数据集中视频，在处理结果误差在可接受范围内的情况下，顶层流水线并行算法结合特征提取模块功能划分并行优化算法的实验结果如表2所示。

表2 顶层流水线并行结合中层特征提取模块功能划分并行算法实验结果

对比表2与表1可见，结合了中层功能划分算法后，总的执行时间有了一定的优化。为了进一步分析中层功能划分并行算法的实验结果，特征提取模块各子模块的串行耗时和功能划分并行算法耗时如表3所示。中层功能划分并行算法将HTD子模块组与其他子模块组分别指派到独立的处理器核上处理，特征提取模块的总执行时间等于瓶颈子模块组(HTD子模块组)的执行时间。由表3可见，功能划分并行算法基本达到了预期的优化效果。

表3 特征提取模块各子模块耗时分析

值得注意的是，在表3中，Road，Pets和Mid都出现了实验3.1节中提到的超线性加速现象，即并行特征提取耗时低于串行瓶颈耗时(HTD)。下面通过设计一个简单的实验验证前文分析的出现这种现象的原因。以Mid为例，特征提取模块只包含HTD子模块，分别执行串行算法和顶层流水线并行算法，得到特征提取模块的耗时分别为串行54.591 274 s和并行42.230 714 s。由于特征提取模块只包含HTD，流水线并行算法与串行算法的唯一区别在于特征提取模块是否与目标检测模块具有缓存交互，而缓存数据的访问速率与CPU高速缓存的命中率有关，因而可以初步验证前文分析原因的正确性，即并行算法增大了处理器高速缓存对数据的命中率，导致了超线性加速的出现。

3.3 三层并行优化算法实验结果及分析

针对数据集中视频，在处理结果在可接受范围内的情况下，结合了顶层流水线、中层功能划分和底层数据划分的三层并行优化算法的实验结果如表4所示。

表4 3层并行优化算法实验结果

由表4可知，增加了底层数据划分并行算法后，算法的总耗时有了明显的优化。为了进一步分析底层数据划分并行算法的实验结果，HTD子模块的耗时如表5所示。结合表5和表4可知，底层数据划分并行算法基本达到了预期的加速比。

表5 HTD子模块耗时统计表

综合上述实验结果可知，本文提出的三层双模块并行优化算法，对于目标检测与特征描述串行算法，在四核CPU平台上，针对不同的实际监控视频场景达到了预期的加速比(平均为3.56，理论极限为4)，基本能满足实时处理的需要(对于VGA分辨率处理速率为31 f/s)。本文由串行算法出发，通过多层次的分析提出了并行优化方法，对于所有串行算法的并行优化具有普遍适用性。

4 小结

本文针对监控视频中的运动目标检测与特征提取的串行算法，分别从顶层流水线结构、中层特征提取模块功能独立性和底层HTD子模块数据独立性三个层次提出了一个面向多核CPU平台的多层次多模块并行优化算法。通过针对多个实际监控视频场景的实验结果表明，本文提出的并行算法获得了预期的加速比(平均为3.56，Amdahl理论极限为4)，基本能实现对实际监控视频的实时处理(对于目标数适中的VGA分辨率的场景处理速率为31 f/s)。此外，本文由串行算法出发，从多个层次分析其并行潜能，提出的并行优化方法对于所有的串行算法的并行优化具有普遍适用性。

:

［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］陈国良，孙广中，徐云，等.并行算法研究方法学［J］.计算机学报，2008，31(9):1493－1502.

［7］吕明洲，陈耀武.基于异构多核处理器的H.264并行编码算法［J］.计算机工程，2012，38(16):35－39.

［8］杨凌云.基于多核技术的并行图像检索系统的研究［D］.北京:北京化工大学，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算法的并行实现及应用［J］.计算机工程与应用，2010，46(020):56－59.

［11］王成良，谢克家，刘昕.多核图像处理并行设计范式多核图像处理并行设计范式的研究与应用［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.