基于典型相关树加权置信传播的运动目标检测

董安国，李 聪

(长安大学理学院，陕西西安 710064)

随着社会经济及信息技术的不断发展，智能视频监控技术得到了日益广泛的应用，并得到越来越多的研究工作者的关注.运动目标检测是智能视频监控技术的核心，运动目标的有效检测对目标跟踪等后期处理起着重要的作用.目前，运动目标的检测方法主要有帧间差分法［1-4］，光流法［2］，混合高斯法［4］，背景差分法［5-6］等.帧间差分法运算简单，且对动态变化环境中的运动目标检测的适应性较强，但检测结果易出现“空洞”现象，而且提取的目标比实际大.背景差分法实现比较简单，但对图像的要求比较高，要求前景和背景之间存在较大的差异.混合高斯法较前2种有较好的检测效果，对场景的适应性比较好，但运算量大，复杂度高.Z.Yin等通过在马尔科夫随机场中加入置信传播算法［7］，对车辆进行检测，效果得到了一定的改善.传统的置信传播算法［8-9］是一种全局匹配算法，利用消息传输和置信度传输机制实现全局能量函数最小化.然而，它计算量很大，容易受颜色畸变像素点的干扰，使算法精度降低.近年来出现了很多以传统置信传播算法为基础的改进算法，比如:①首先利用边缘算法计算处理图像的边缘信息，之后再运用置信传播算法进行匹配［10-11］;② 在多核服务器上通过共享内存的方式进行检测［12］;③ 加入概率推论等方法［13-14］.这些尽管在检测时都取得了一些效果，但由于方法的加入又增加了算法的计算时间，不能做到实时检测.

文中拟提出一种典型相关的tree-reweighted算法，通过将视频图像进行分块，建立环路模型，提取运动目标.

1 典型相关的tree-reweighted算法

算法思想:①将视频中的图像分成大小相同相互独立的子块;② 计算相邻子块间的典型相关系数，连接系数值最大的2个子块，形成新的环路;③运用tree-reweighted算法将生成的有环图模型分解成生成树，进行迭代，更新信息，再次计算块置信度，将其与背景块置信度进行对比，实现运动目标的检测分割.算法实现过程示意图见图1.

图1 算法实现过程示意图

1.1 树加权置信传播

在有环图中，置信传播算法在信息传递过程中重复利用自身信息，使得BP算法的收敛得不到保证，故可能出现分类标记振荡现象，因此下面简单介绍一下解决有环图中信息传递问题的方法:树加权置信传播算法.设 ζ=ζ(G)表示图G中所有的树的集合;设为包含这些树的集合的概率的集合，即为

图2 边在树中出现的概率分布

在图2a中，边b称为桥，即不管在哪棵生成树上边b都会出现，因此ub=1.边e和f出现在2棵生成树上和1棵生成树上，边e出现的概率为ue=2/3，边f出现的概率为uf=1/3.树加权置信传播算法(TRBP)从表面上看类似于有环的置信传播算法(LBP)，用表示在第t次迭代中像素点p向它的相邻像素点q传递的信息.信息的更新公式为

其中定义参数cpq时应该满足3个要求:①原图中的每条边在分解的一系列树中至少出现1次;②在一系列的树中，边以概率 ρ出现;③ 参数cpq正比于ρpq/ρp，后者表示随机地选择某棵树，这棵树包含节点p的边(p，q)的概率.如果cpq的值设定为1，那么TRBP算法就退化为LBP算法.树加权置信传播算法可计算一个能量下限，它并不保证TRBP算法在迭代过程中能量一定收敛，但是TRBP算法保证能量下线不下降.

1.2 计算生成有环图模型

将视频中的图像分成大小相同，相互独立的子块，设其中2个子块为Pi和Pj，其线性组合表示为Qi和Qj，则

此处定义:Cov(Pi)=Sii，Cov(Pj)=Sjj，Cov(Pi，Pj)=Sij=S'ji，于是:

由于向量的数乘不会改变向量的相关系数值，所以在寻求使得典型相关系数值最大的向量a'和b'时，首先归一化处理Qi和Qj，最终得到相关系数为

此处计算Qi和Qj的相关系数值即可变为寻求向量a'和b'，使得(7)式中系数最大，利用拉格朗日乘子法进行求解，最终得到基于子块的有环图模型.

1.3 环路的分解算法

利用最小权方法将有环图进行分解后形成生成树，通过tree-reweighted算法更新迭代，实现运动目标的检测，具体思路如下:

式中:kij(pi，pj)，ki(pi)为辅助指示变量;Eij为相邻块对能量;Ei为块能量;X*为全局能量值.相邻块之间的势能 φij(pi，pj)=exp(-Eij(pi，pj))=exp(-λij)，每一个子块的势能φi(pi)=exp(-Ei(pi))=exp(-i)，i为每一小块的平均像素值，迭代更新如下:

式中:α为归一化常量;ρij为边沿权重.当迭代完成后，图像块和相邻图像块的置信度可表示为

由以上计算得到块的置信度，与背景块置信度进行差分，若差值远大于背景块的置信度，则将其判断为运动目标，否则为背景，如此即可实现运动目标的检测.在现实生活中背景部分会受到噪声的影响，于是把最小的块置信度作为下一帧图像的基准置信度.对于已经确定的目标子块，利用置信传播算法计算出子块内每个像素点的置信度，将其与背景像素置信度作比较，确定目标子块内的目标像素，以实现运动目标的检测分割.

2 数值试验

下面分别用混合高斯法，帧差法，背景差法和文中提出的算法对不同视频进行相邻2帧的运动目标提取，图3为对目标提取的结果，其中第5列是给第3列视频加入噪声的试验结果.

试验结果表明，无论是简单背景还是被噪音干扰的复杂背景，文中算法能更准确地检测到运动目标，且有效避免“空洞”现象的发生.

为了能够更好地比较文中算法的检测效果，将几种算法的检出结果图像与原视频帧进行比较，此处只对视频1，4，5进行计算比较.对算法检测的结果图像f从目标四周逐点选取，以选取点为中心，取一个5×5的块，记作Ω，然后在原视频帧图像g中相同位置处也选取同样大小的像素块，计算它们的相似度指标SI，即为

再计算出相似度指标SI大于0.9的像素块在所有像素块中所占比值，从比值可以看出文中算法检测出的结果与原视频帧中的运动目标相似度更高，如表1所示.

图3 视频用不同方法进行目标提取的结果

表1 算法比较

3 结论

文中运用典型相关的tree-reweighted算法进行运动目标检测，在实际的迭代过程中，树加权置信传播算法能够计算能量的上界，使信息的收敛速度更快，并得到较为完整的目标信息，且运算速度快，准确率高.文中在试验之前对图像做了平滑处理，且选取的实际运动场景相对比较稳定，导致试验结果更趋近于理想化，但在实际运动物体周围仍然有背景被误检为运动目标;而对于更复杂，更粗糙的运动场景，文中算法还能否对运动目标进行准确实时的检测，达到较为理想的效果，后面将作进一步研究.

References)

［1］邬大鹏，程卫平，于盛林.基于帧间差分和运动估计的Camshift目标跟踪算法［J］. 光电工程，2010，37(1):55-60.

Wu Dapeng，Cheng Weiping，Yu Shenglin.Camshift object tracking algorithm based on inter-frame difference and motion prediction［J］.Opto-electronic Engineering，2010，37(1):55-60.(in Chinese)

［2］王振亚，曾黄麟.一种基于帧间差分和光流技术结合的运动车辆检测和跟踪新算法［J］.计算机应用与软件，2012，29(5):117-120，129.

Wang Zhenya，Zeng Huanglin.A new algorithm of moving vehicle detection and tracking based on combining frame difference method with optical flow technique［J］.Computer Applications and Software，2012，29(5):117-120，129.(in Chinese)

［3］甘明刚，陈 杰，刘 劲，等.一种基于三帧差分和边缘信息的运动目标检测方法［J］.电子与信息学报，2010，32(4):894-897.

Gan Minggang，Chen Jie，Liu Jin，et al.Moving object detection algorithm based on three-frame-differencing and edge information［J］.Journal of Electronics＆Information Technology，2010，32(4):894-897.(in Chinese)

［4］薛丽霞，罗艳丽，王佐成.基于帧间差分的自适应运动目标检测方法［J］.计算机应用研究，2011，28(4):1551-1552，1559.

Xue Lixia，Luo Yanli，Wang Zuocheng.Detection algorithm of adaptive moving objects based on frame difference method［J］.Application Research of Computers，2011，28(4):1551-1552，1559.(in Chinese)

［5］陈俊超，张俊豪，刘诗佳，等.基于背景建模与帧间差分的目标检测改进算法［J］.计算机工程，2011，37(S1):171-173.

Chen Junchao，Zhang Junhao，Liu Shijia，et al.Improved target detection algorithm based on background modeling and frame difference［J］.Computer Engineering，2011，37(S1):171-173.(in Chinese)

［6］Richard Szeliski.Stereo algorithms and representations for image-based rendering［C］∥Proceedings of the10th British Machine Vision Conference，1999:314-328.

［7］李鹤喜，孙玲云.基于彩色图像分割的置信传播快速立体匹配算法［J］.数字技术与应用，2013(1):115-117.

Li Hexi，Sun Lingyun.Quick stereo matching algorithm of color image segmentation based on the belief propagation［J］.Digital Technology＆Application，2013(1):115-117.(in Chinese)

［8］高恩婷，顾一清，严建峰.基于快速置信传播算法的并行主题建模方法研究［J］.南通大学学报:自然科学版，2013，12(1):1-8.

Gao Enting，Gu Yiqing，Yan Jianfeng.Parallel topic modeling techniques based on fast belief propagation［J］.Journal of Nantong University:Natural Science Edition，2013，12(1):1-8.(in Chinese)

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

Guo Chunsheng，Zhang Dazhuang.Video moving object detection based on belief propagation［J］.Journal of Circuits and Systems，2013，18(1):237-242.(in Chinese)

［10］Piatkowski Nico，Lee Sangkyun，Morik Katharina.Spatio-temporal random fields:compressible representation and distributed estimation［J］.Machine Learning，2013，93(1):115-139.

［11］周自维，樊继壮，赵 杰，等.基于置信传播的立体匹配并行算法［J］.光学精密工程，2011，19(11):2774-2781.

Zhou Ziwei，Fan Jizhuang，Zhao Jie，et al.Parallel stereo matching algorithm base on belief propagation［J］.Optics and Precision Engineering，2011，19(11):2774-2781.(in Chinese)

［12］詹永照，汪满容，柯 佳.基于人工免疫有序聚类的视频关键帧提取方法［J］.江苏大学学报:自然科学版，2012，33(2):199-204.

Zhan Yongzhao，Wang Manrong，Ke Jia.Video keyframe extraction using ordered samples clustering based on artificial immune［J］.Journal of Jiangsu University:Natural Science Edition，2012，33(2):199-204.(in Chinese)

［13］卢 俊，张保明，郭海涛，等.多视影像相对方位关系误判检测的置信传播算法［J］.测绘学报，2015，44(4):422-430.

Lu Jun，Zhang Baoming，Guo Haitao，et al.False detection of relative orientation of multi-view images based on belief propagation［J］.Acta Geodaetica et Cartographica Sinica，2015，44(4):422-430.(in Chinese)

［14］Gauglitz Steffen，Höllerer Tobias，Turk Matthew.Evaluation of interest point detectors and feature descriptors for visual tracking［J］.International Journal of Computer Vision，2011，doi:10.1007/s11263-011-0431-5.