基于随机游走和混合高斯模型的运动目标检测

李 强，陈光化，余 渊

(1.上海大学 机电工程与自动化学院，上海 200070； 2.上海电器科学研究所(集团)有限公司，上海 200333)

基于随机游走和混合高斯模型的运动目标检测

李 强1，陈光化1，余 渊2

(1.上海大学 机电工程与自动化学院，上海 200070； 2.上海电器科学研究所(集团)有限公司，上海 200333)

针对传统的混合高斯背景建模算法未考虑同一帧内相邻像素之间的联系而导致无法准确地捕捉到运动物体轮廓的问题，提出了一种将随机游走和混合高斯模型相结合的前景目标检测算法。该算法利用混合高斯模型对视频源图像进行背景建模，从而获得初始运动目标，应用随机游走算法的分割效果及处理时间来确定种子点数量，结合初始运动目标对种子点进行标记，采用随机游走算法对视频源图像进行分割，将所得到的分割目标再与初始运动目标进行“与”运算，通过形态学处理得到作为结果的运动目标。为验证所提出算法的有效性，基于Matlab对所选取的4段视频进行了仿真检测。验证实验结果表明，所提出的前景目标检测算法较好地解决了混合高斯算法所产生的边缘模糊问题，同时也明显降低了前景噪声。

混合高斯模型；随机游走；运动目标检测；种子点

0 引 言

运动目标检测是分析视频过程中一个基础而又关键的任务[1]。而背景建模作为目标跟踪检测的基础，其结果的好坏将直接影响到后期处理的效果。迄今，人们己经设计了很多背景建模的算法。常用的有：帧差法、码本法、混合高斯模型法等[2-4]。其中最经典的是混合高斯模型算法。

近年来，有文献提出了改进的混合高斯模型算法。例如，Zoran Zivkovic[5]提出将对每个像素的高斯个数进行在线选择，从而更好地适应不同的场景，同时缩短了建模时间；Dar-Shyang Lee[6]则提出使用自适应学习算法来改善收敛速度和检测精度。然而，这些改进方法并未考虑相邻像素点之间的联系，这会导致运动目标的检测产生边缘模糊的问题。也有部分文献对这方面提出了相应改进。印勇等[7]通过重新定义Markov随机场(MRF)的势能函数来融入空间邻域的相关性信息，从而对混合高斯算法进行改进；李菊等[8]采用Markov随机场(MRF)构造的间断点分布模型来检测运动目标的边缘。但这些改进算法实现起来较为繁琐。因此，结合了实现相对简单的随机游走算法，来补充相邻像素点之间的联系。

随机游走图像分割算法是根据相邻像素间的关联程度对图像进行分割处理，对微弱边缘具有良好的响应。为此，提出了将随机游走算法和基于混合高斯模型相结合的运动目标检测算法，并进行了实验。

1 相关算法研究

1.1 混合高斯背景建模算法

Grimson和Stauffer提出，使用K(一般为3～5)个相互独立的高斯分布函数来描述图像帧中的每一个像素点[3]。

(1)

其中，xN表示N时刻的某一像素值；wk表示第k个高斯分布的权重值；η(x;θk)表示第k个高斯分布函数：

(2)

其中，μk表示均值；Σk=σ2I表示第k个高斯分布的方差。

将K个高斯分布按照wk/σk的优先级进行降序排列，排序后从中挑选出比值最大的前B个高斯进行建模。wk/σk值越大，表明当前像素有较小的方差和较高的出现概率，即该像素在前后帧的时间内变化不大，体现了背景像素的特性，所以该像素呈现为背景像素的概率大于呈现为前景像素的概率。

(3)

其中，T是给定的阈值。

P.Kaewtrakulpong和R. Bowden提出可将前L帧图像当成训练样本，更新公式如下[4]：

(4)

(5)

(6)

L帧样本更新完后，按照如下方式更新：

(7)

(8)

(9)

1.2 随机游走图像分割算法

随机游走是一种基于图论的半监督图像分割方法，具有分割速度快，无需迭代，对噪声具有鲁棒性，对弱边缘具有较好的响应等优点，且易于扩展到多维空间[9]。该算法主要采用灰度差计算相邻节点间的相似度[10]。其分割思想为：将图像映射为一幅无向图，以图像的像素为无向图的顶点，相邻像素之间的四邻域或八邻域关系为边，并根据相邻像素之间特征的相似性定义各边的权值。然后由用户指定前景和背景标记，即前景物体和背景物体的种子像素，以边上的权重为转移概率，未标记像素节点为初始点，计算每个未标记节点首次到达已标记节点(即种子节点)的概率，根据概率大小，划分未标记节点，得到最终分割结果[11-13]。

无向图定义为G=(V,E,W)，其中V表示节点集合，E表示边集合，W表示权值集合。权值由高斯权函数来描述节点间的相似性，即

wi,j=exp(-β1(Ii-Ij)2)

(10)

其中，Ii表示节点vi的灰度值；Ij表示与节点vi相邻的节点vj的灰度值；β1>0表示自由度参数。

随机游走求解概率问题与Dirichlet积分求解有相同的解法。通过对图像中目标区域与背景区域进行标记，将图像中的节点分成两类，标记点集合VM和未标记点集合VU，VM∪VU=V且VM∩VU=∅。

定义拉普拉斯矩阵的元素为：

(11)

其中，dRi=∑wRi,Rj称为节点vRi的度，未标记节点vRi∈VU，标记节点vRj∈VM。

离散Dirichlet积分公式定义为：

(12)

根据节点所属不同集合，将拉普拉斯矩阵分解成对角分块矩阵形式。

(13)

其中，xM和xU分别表示对应种子点和非种子点的随机游走概率值。

对D[xU]针对xU求微分，可以得到该方法极小值的解。

LUxU=-BTxM

(14)

(15)

应用Dirichlet边界条件，计算所有未标记点到标记为s的种子点概率值。计算：

LUX=-BTM

(16)

将每个未标记点归并到概率最大值所属的类中，实现图像分割。

2 基于随机游走和混合高斯模型的运动目标检测算法

传统的混合高斯背景建模是对图像帧中每一个像素点进行建模，前后帧的像素点相互关联，但并未考虑相邻像素点之间的联系，这会导致运动目标的检测产生边缘模糊的问题，从而无法准确获得运动目标的轮廓。因此，提出将随机游走算法引入混合高斯模型算法，从而考虑了相邻像素点之间的关联性。

2.1 算法介绍

混合高斯背景建模算法保证了相邻帧之间像素的关联性，随机游走分割算法则计算了同一帧里相邻像素之间的相似性，将这二者结合能更准确地描述视频序列中的前景和背景。实现过程如下：

(1)对当前帧图像采用混合高斯模型进行背景建模，提取初步运动目标。高斯模型数目N一般设为3～5，阈值T一般设为0.7。

(2)根据式(4)～(9)对背景模型进行更新。

(3)随机选取一定数量的图像像素作为种子点。种子点的数量直接影响到随机游走分割算法的分割效果，关于种子点的选取问题，将在下一节讨论。

(4)根据混合高斯背景建模得到的初始运动目标给这些种子点定义相应的标签，背景种子点标签为0，前景种子点标签为1，然后采用随机游走分割算法对原视频帧图像进行处理，得到前景目标。

(5)将混合高斯背景建模所得到的初始运动目标(二值图像)与通过随机游走分割得到的前景目标(二值图像)进行“与”运算。

(6)进行形态学处理。

流程图如图1所示。

图1 算法流程图

2.2 随机游走种子点的选取

由于随机游走是一种交互式的图像分割算法，因此要预先指定一定数量的种子点。种子点的数量会直接影响分割效果。

种子点太少，导致图像分割不准确；种子点过多，使分割结果过分依赖于混合高斯背景建模所得到的初始运动目标(由于这些种子点会根据初始运动目标来定义标签)，影响优化效果。所以，分别随机选取0.1%～50%的图像像素作为种子点，对分割结果进行对比，如图2所示。

图2 随机选取各百分比的图像像素作为种子点得到的图像分割效果

从实验结果可以看出，随机选取5%以下的图像像素作种子点时，图像分割效果并不好；随机选取5%～20%的像素时，分割出的主体基本完整，但在细节上表现较差(如图2(f)～(h)中间两个小孩的轮廓不准确)；随机选取20%以上的像素时，分割出的主体更为准确，而且差异也越来越小。总结起来，随着种子点数量的增加，随机游走算法的分割效果越好，分割出的主体更为准确和完整。

根据1.2节的理论可知，随机游走算法计算的是所有未标记点到达已标记的种子点概率值，当种子点数量越多时，算法的处理速度越快，如图3所示。

从图3可以看出，当种子点数量在0%～20%时，算法处理时间缩短明显；20%～40%时，算法平均处理时间减少缓慢；40%之后变化更小。结合图2所示的分割效果，选取大于20%的像素作为种子点较为理想。

图3 种子点数量与随机游走算法处理时间的关系

然而当种子点数量过多时，随机游走算法的分割效果会过分依赖于混合高斯背景建模所得到的初始运动目标，这样会使改进算法失去意义。综上所述，选取了20%的像素点作为种子点，然后对图像进行分割。

2.3 形态学处理

经过随机游走分割算法处理后，噪声已经得到进一步的削弱，然而仍会有一些“空洞”或是孤立的小区域，这里采用形态学方法来去除二值图像中孤立的小区域，同时将小间隙填充。基于形态学后处理方法，进行闭运算，即先进行“膨胀”操作，使目标区域的连通块尽量少，接着进行“腐蚀”操作消除毛刺，使边界向内部收缩。对二值图像进行形态学处理后，实现了消除噪声、平滑图像的目的，检测出完整的运动目标。

3 仿真结果及分析

提出算法在Matlab R2015b下编程实现，选用的计算机配置为Intel Core i3 370M双核处理器，内存4 GB，Windows 10操作系统。为了验证提出算法的有效性，选取了4段视频进行检测，如图4所示。

通过观察和比较可以发现，单纯使用混合高斯模型所得到的前景目标会出现轮廓虚化的现象，如图4(b)列第一幅图中两边人的腿轮廓出现了一些模糊；(b)列的其他运动目标也均出现了不同程度的轮廓模糊现象。此外，(b)列第二幅、第三幅图像还出现了明显的噪声。而采用提出的方法，不仅能获得较完整的目标轮廓，边缘毛刺被消除，而且噪声也得到了较大改善，如(c)列所示。同时，可以发现(c)列图像相比(b)列图像，前景目标内部的微小“空洞”被大量填充，使整个目标看起来更完整。

通过实验可以看出，提出的改进算法较好地改善了前景目标轮廓模糊的现象，这得益于随机游走算法对微边缘的良好响应。而随机选取一定数量的种子点，也能够帮助剔除部分噪声点，同时使随机游走分割效果更好。最后的形态学处理则帮助消除了大量的微小“空洞”和边缘毛刺。

4 结束语

针对传统的混合高斯背景建模算法无法准确地捕捉到运动物体轮廓的问题，提出了将随机游走图像分割算法与混合高斯模型算法相结合的新算法。该算法根据混合高斯模型算法所得到的初始运动目标，随机选取一定数量的种子点并标记，并采用随机游走图像分割算法对视频图像进行分割，并将两种算法得到的前景目标进行“与”运算，经形态学处理得到完整的运动目标。由于种子点的数量会直接影响随机游走算法的分割效果，因而通过对比不同数量的种子点对图像的分割效果以及算法的处理时间，发现选取20%的像素作为种子点较为合理。该方法在保证前后帧像素的关联性的同时，还考虑了同一帧内相邻像素的联系，使得检测出的运动目标轮廓更为完整和准确。实验结果表明，提出的目标前景检测算法较原有的混合高斯模型算法具有更好的检测效果，同时还具有一定的降噪效果。

[1] 焦 波,李国辉,涂 丹,等.一种用于运动目标检测的快速收敛混合高斯模型[J].中国图象图形学报,2008,13(11):2139-2143.

[2] Guo Jingming,Liu Yunfu,Hsia Chih-Hsien.Hierarchical me-thod for foreground detection using codebook model[J].IEEE Transactions on Circuits and Systems for Video Technology,2011,21(6):804-815.

[3] Stauffer C,Grimson W E L.Adaptive background mixture mo-dels for real-time tracking[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,1999.

[4] Kaewtrakulpong P, Bowden R. An improved adaptive background mixture model for realtime tracking with shadow detection[M]//Video-based surveillance systems.US:Springer,2002:135-144.

[5] Zivkovic Z. Improved adaptive Gaussian mixture model for background subtraction[C]//International conference on pattern recognition.[s.l.]:IEEE Computer Society,2004:28-31.

[6] Lee Dar-Shyang.Effective Gaussian mixture learning for video background subtraction[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005,27(5):827-832.

[7] 印 勇,王亚飞.基于空间邻域相关性的运动目标检测方法[J].光电工程,2009,36(2):1-5.

[8] 李 菊,李克清,苏勇刚.Markov随机游走和高斯混合模型相结合的运动目标检测算法[J].电子测量与仪器学报,2014,28(5):533-537.

[9] 徐晓华.图上的随机游走学习[D].南京:南京航空航天大学,2008.

[10] 依玉峰，高立群，郭 丽． 基于Mean Shift随机游走图像分割算法[J]．计算机辅助设计与图形学学报，2011,23(11):1875-1881．

[11] Grady L． Random walks for image segmentation[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(11)：1768-1783．

[12] Grady L． Minimal surfaces extend shortest path segmentation methods to 3D[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(2)：321-334．

[13] Grady L,Sinop A K.Fast approximate random walker segmentation using eigenvector precomputation[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,2008:1-8.

Moving Target Detection Based on Random Walk and Gaussian Mixture Model

LI Qiang1，CHEN Guang-hua1，YU Yuan2

(1.School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200070,China; 2.Shanghai Electrical Apparatus Research Institute (Group) Co.,Ltd.,Shanghai 200333,China)

Since the conventional Gaussian mixture background modeling algorithm does not consider the correlation between adjacent pixels in the same frame,which cannot accurately capture the contour of moving objects,a foreground target detection method combined with random walk and Gaussian mixture model has been proposed.The background of the video source image has been modeled with the mixed Gauss model firstly,and the initial moving object has been obtained.Then,the number of seed points is determined by analyzing the segmentation result and the processing time of the random walk algorithm.The seed points have been labeled with the initial moving object,and the video source image is segmented by random walk algorithm.The obtained segmentation target and the initial moving object have been computed with logic AND operation.The morphological processing has been carried out to get the final moving target. In order to verify the effectiveness of the proposed algorithm, the four selected sequences of videos have been tested by Matlab.The test results show that the proposed method has solved the edge blurring problem of Gaussian mixture algorithm,and reduced the foreground noise.

mixed Gauss model;random walk;moving target detection;seed points

2016-08-10

2016-11-17 网络出版时间：2017-04-28

上海市科技成果转化和产业化项目基金(14DZ1100600)

李 强(1991-)，男，硕士研究生，研究方向为数字图像处理；陈光化，副教授，研究方向为视频编解码关键技术及其VLSI实现、嵌入式系统设计等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1704.094.html

TP301.6

A

1673-629X(2017)06-0011-06

10.3969/j.issn.1673-629X.2017.06.003