基于典型相关的视频运动目标检测

徐　俊，郭春生，沈　佳

(杭州电子科技大学通信工程学院，浙江 杭州 310018)

摘要：在智能监控系统中，视频运动目标检测是目标分类和行为理解的基础。由于视频背景的复杂性，考虑检测问题中能量函数的全局优化，提出了基于典型相关的树加权置信传播(TRW)算法用于视频运动目标检测。算法首先将视频图像分成一些图像块，构造有环图模型；然后运用TRW算法将环路分解成生成树的形式，实现有环图模型上的视频运动目标优化检测。仿真结果表明，算法具有较高的准确度，与传统的置信传播(BP)算法相比较，能有效降低迭代次数，提高计算效率。

关键词：置信传播；典型相关；视频运动目标检测

DOI: 10.13954/j.cnki.hdu.2015.01.009

基于典型相关的视频运动目标检测

徐俊，郭春生，沈佳

(杭州电子科技大学通信工程学院，浙江 杭州 310018)

摘要：在智能监控系统中，视频运动目标检测是目标分类和行为理解的基础。由于视频背景的复杂性，考虑检测问题中能量函数的全局优化，提出了基于典型相关的树加权置信传播(TRW)算法用于视频运动目标检测。算法首先将视频图像分成一些图像块，构造有环图模型；然后运用TRW算法将环路分解成生成树的形式，实现有环图模型上的视频运动目标优化检测。仿真结果表明，算法具有较高的准确度，与传统的置信传播(BP)算法相比较，能有效降低迭代次数，提高计算效率。

关键词：置信传播；典型相关；视频运动目标检测

DOI:10.13954/j.cnki.hdu.2015.01.009

收稿日期：2014-06-05

基金项目：国家自然科学基金资助项目(61372157)

通信作者：

作者简介：徐俊(1990-)，男，浙江嘉兴人，在读研究生，信号与信息处理.郭春生教授，E-mail: guo.chsh@gmail.com.

中图分类号：TN911.73

文献标识码：：A

文章编号：：1001-9146(2015)01-0045-04

Abstract:Video moving object detection is the foundation of the behavior understanding and target classification in the intelligent surveillance system. As the complexity of video background， consider the global optimization of the energy function in object detection. In this paper， tree re-weighted belief propagation(TRW) algorithm based on canonical correlation is proposed to detect the video moving objects. This algorithm firstly separates the video image into some blocks and constructs a loop model. Then it uses the TRW algorithm to decompose the loop into spanning tree and achieve the detection of the video moving objects on the loop model. The experimental results verify the veracity of the algorithm， compared with the traditional belief propagation(BP) algorithm， TRW can decrease the message iterations effectively and improve the computational efficiency of the algorithm.

0引言

视频运动目标检测从图像序列中划分出对象区域，是智能监控系统对目标进行分类和行为分析的基础。目前，常用的检测方法有光流法、帧差法、背景差法等。由于背景受到遮挡、光照变换、像素级的噪声和干扰等因素的影响，造成背景更新波动大，在这样复杂的背景下文献[1]结合HIS颜色空间和局部纹理模式以完成目标的有效检测；文献[2]提出一种基于相关特征匹配的检测算法，通过提取图像特征，利用特征参数欧式距离来检测目标；文献[3]在马尔科夫随机场中引入置信传播算法，完成行人、车辆的有效检测。置信传播(Belief Propagation， BP)算法[4-5]是一种重要的优化方法，它在最小化能量的框架下，对能量函数进行全局优化，但是实际上BP算法的计算复杂度是指数级的，且在环路当中BP算法的收敛性不能得到保证，这样限制了算法的应用。因此，本文在BP算法的基础上，提出了基于典型相关的树加权置信传播(Tree-Reweighted， TRW)算法用于运动目标检测，通过对图像分块、构建环路图模型，有效减少计算量，降低BP算法的计算复杂度。

1基于典型相关的TRW算法实现

本文提出的基于典型相关的TRW算法是一种优化算法，算法的流程如图1所示。首先将输入的视频图像分成子图像块；然后计算相邻子图像块间的典型相关系数，选取系数值最大的两子图像块进行连接，构建新的环路；最后利用TRW算法将有环图模型分解成生成树，迭代更新信息，计算块置信度，并和背景块置信度对比，实现运动目标检测。

图1　算法流程图

1.1　有环图模型生成

将输入的视频图像分成大小相同的若干子图像块，定义其中两子图像块变量Xi和Xj，它们的线性组合表示为Ui和Uj：

(1)

D(Ui)=D(aXi)=aCov(Xi，Xi)a′=aSiia′

(2)

D(Uj)=D(bXj)=bCov(Xj，Xj)b′=bSjjb′

(3)

Cov(Ui，Uj)=aCov(Xi，Xj)b′=aSijb′

(4)

(5)

为了寻找到一组向量a′、b′使得典型相关系数最大，由于向量乘以一个常数不会改变相关系数的大小，对Ui和Uj进行归一化处理，即D(Ui)=aSiia′=1，D(Uj)=bSjjb′=1，那么相关系数为：

(6)

这时问题就转变成了求解一组向量a′和b′使得式(6)中系数最大，根据条件极值，引入拉格朗日乘子法，问题转化为：

(7)

λij和vij是拉格朗日乘子，然后求偏导得：

(8)

且知aSijb′=λijaSiia′=λij，bSjia′=vijbSjjb′=vij。由于(bSjia′)′=aSijb′，因此λij=vij=aSijb′，根据式(6)可知，λij就是Ui和Uj的相关系数。

1.2　环路分解与树加权置信传播算法推理

在有环图中，精确推理是NP困难的，将有环图问题转换成多个无环子问题进行近似求解是一个行之有效的办法。在TRW算法中，环路图可以分解成多个凸联合生成树组合加权的形式。目前，环路图分解有三种常用的生成树方法：最大权生成树、最小权生成树和随机生成树，本文选择最大权和随机生成树组合作为环路分解的方法。

有环图分解成生成树后，通过TRW算法迭代更新信息，实现目标检测，推理如下：

(9)

(10)

式中，α为归一化常量，ρij表示边沿权重。

当信息mij(Xj)迭代稳定后，图像块和相邻图像块的置信度可以表示为：

(11)

(12)

通过计算可以得到图像块的置信度，再与背景图像块置信度作差进行比较，如果差值远大于背景图像块的置信度，则判断为目标图像块。由于视频序列背景会有一定变化，需要把最小的图像块置信度作为下一视频帧的基准背景置信度。对于确定的目标图像块，根据置信传播算法可以计算出块内每个像素点的置信度，通过和背景像素置信度的比较，确定目标像素块中的目标像素，实现运动目标检测。TRW算法中由于无环的生成树结构，加快了各节点之间的信息交换，利用置信度bi(Xi)、bij(Xi，Xj)与辅助指示变量qij(Xi，Xj)、qi(Xi)的变换关系，能够得出能量函数的上界，使信息收敛的速度加快，从而有效降低信息迭代次数，减少计算量，提高算法效率。

2实验与分析

选择PETS2006[6]和Water Surface[7]作为本文实验数据集。PETS2006是一组室内火车站图像序列，可以验证算法在简单背景下的准确度和计算效率。Water Surface是一组外湖的图像序列，可以验证算法在复杂背景下的有效性和计算效率。为了验证本文算法的准确度，将本文算法与视频运动目标检测常用的BP算法、GMM算法进行实验比较。运动目标检测的结果如图2所示。

图2　典型相关的3种算法检测结果

从图2可以看出，在室内背景变化较小或者水面波动变化较大的情况下，3种算法与真实目标都有一定的差异，但是本文算法相比于BP算法、GMM算法具有更好的适应性，可以较好地检测出目标。

为了更好地比较算法检测效果，本文采用检出率P和相似度S定量分析算法性能。P是检测出正确像素的比例，S是综合性检测指标，其值越大表示能力越好。

(13)

式中，tp表示正确像素在检测目标中的个数，fn表示错误像素在检测目标中的个数，fp表示漏检目标的像素个数。表1给出本文算法、BP算法和GMM算法对PETS2006、Water Surface图像序列的检测性能，从中可以看出本文算法检测效果优于BP算法和GMM算法。

表1　PETS2006和Water Surface的检测性能

为了验证本文算法的计算效率，将本文算法与BP算法每帧图像检测的迭代次数和计算时间进行比较，结果如表2所示。由此可以看到，相比于BP算法，本文的算法使信息收敛的速度加快，有效降低信息迭代的次数，减少计算量，提高算法的计算效率。

表2　PETS2006和Water Surface的计算效率

3结束语

本文提出一种基于典型相关的TRW算法用于运动目标检测。算法利用典型相关系数的环路构建和无环生成树的结构特性，加快了各个节点之间的信息交换，解决了BP算法复杂度过高的问题。PETS2006和Water Surface两组图像序列的实验结果证明，本文算法速度快，准确度高，具有很好的应用价值。

参考文献

[1]Ding Y， Li W H， Fan J T， et al. Robust moving object detection under complex background[J]. Computer Science and Information Systems/ComSIS，2010，7(1):201-210.

[2]王明高，王琰.一种基于相关特征匹配的移动目标检测方法[J].中国图象图形学报，2007，12(8):1 372-1 376.

[3]Yin Z， Collins R. Belief propagation in a 3D spatio-temporal MRF for moving object detection[C]//Computer Vision and Pattern Recognition， 2007. CVPR’07. IEEE Conference on. IEEE，2007:1-8.

[4]Szeliski R， Zabih R， Scharstein D， et al. A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30(6):1 068-1 080.

[5]郭春生，张大状.基于置信传播的视频运动目标检测[J].电路与系统学报，2013，18(1):237-242.

[6]Auvinet E， Grossmann E， Rougier C， et al. Left-Luggage Detection using Homographies and Simple Heuristics[C]//Proc. 9th IEEE International Workshop on Performance Evaluation in Tracking and Surveillance (PETS’06).2006:51-58.

[7]Li L， Huang W， Gu I Y H， et al. Foreground object detection from videos containing complex background[C]//Proceedings of the eleventh ACM international conference on Multimedia. ACM，2003:2-10.

Video Moving Object Detection Based on Canonical Correlation

Xu Jun， Guo Chunsheng， Shen Jia

(SchoolofCommunicationEngineering，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Key words: belief propagation; canonical correlation; video moving object detection