基于运动背景的自适应视频对象分割算法
2016-06-29王小平
王小平
(长江师范学院 计算机工程学院，重庆408100)
基于运动背景的自适应视频对象分割算法
王小平
(长江师范学院 计算机工程学院，重庆408100)
摘要：为解决运动背景中视频对象的准确提取，提出一种基于全局运动的自适应视频对象分割算法。基于特征点计算帧间运动，利用最小二乘法计算摄像机仿射参数进行运动补偿，通过二值开闭重建滤波器进行预处理消除噪声；采用改进的分水岭算法将图像标记成不同的灰度区域，以自适应的光流法对分割的对象信息进行评判，从运动背景中分割出前景对象。实验表明，该算法能准确地从运动背景中分割出视频对象，显著地减少了动态前景对象的分割误差，提高了分割质量，可应用于运动目标检测与跟踪。
关键词：运动补偿；自适应梯度；分水岭算法；重建滤波器
0引言
视频对象分割是将视频序列分割为不同意义明确的实体，在数字视频及计算机视觉领域具有广泛的应用。由于现实中的物体在光流、亮度和颜色等方面的特征并不是均匀的，从运动背景中准确地分割出视频对象成为对视频处理的先决条件。视频场景具有复杂性和多变性，只用单一的信息来分割视频会出现大量失真，目前多数分割算法综合使用帧间和帧内多种信息以得到最终结果。本文提出一种将不同时空要素进行综合的视频分割算法：首先，计算帧间运动，并根据仿射参数进行运动背景补偿，用数学形态学进行预处理；其次，用改进分水岭算法对图像进行标记；最后，用自适应算法得到运动模板，将标记区域和运动模板结合得到准确的分割对象。实验结果表明，本算法确保了视频运动对象分割的实时性、可靠性和鲁棒性，提高了分割性能。
将视频序列通过一定的算法分割出具有意义明确、空间和时间相对独立的集合，是视频分割的主要目标。虽然视频分割技术的研究已有一定的历史，众多文献也提出了许多不同分割技术，但由于不同类型的视频图像各具特点，且本身内容复杂，易受噪声影响，目前还没有通用的完全自动分割工具。
视频分割技术伴随着算法的发展而日新月异，国内和国外的学者提出了许多新算法,目前主要有基于运动的分割、时空分割和交互式分割。
基于运动的分割可以分为光流法、运动补偿法和贝叶斯算法等。其中，光流法有：Horn，Schunck[1]提出的利用光流在整个图像上的光滑变化来求解光流；Lucas，Kanade[2]用加权最小二乘法估算光流等。运动补偿或差分算法的视频图像分割包括：Mech[3]利用估计出的变化检测模板(change detection mask，CDM)来生成视频对象平面(video object plan，VOP)；Meier[4]提出将视频图像进行3D分割的参数化方法；Chan等[5]提出的利用贝叶斯模型对运动估计和对象分割。
时空分割包括时域分割法、空间域分割法和时空混合分割法。其中，Neri等[6]提出利用帧间差值求高阶统计(higher order statistic,HOS)来检测物体；Pardas[7]提出利用深度和一致性进行视频分割；Greenspan等[8]提出将六维特征空间通过高斯模型来聚类，根据高斯协方差系数求出运动信息；DeMenthon[9]利用平移不变性对时空方向和位置方向进行表示。
交互式分割包括：Marques等[10]提出的数学形态学的2次交互式分割。Kruse等[11]提出的利用活动轮廓进行基于边界的交互式视频对象分割；Marcotegui等[12]提出的利用连通性的原理进行分割。
随着网络技术和多媒体技术的发展，人们越来越关注视频信息的处理，特别是MPEG-4出现后，如何直接在压缩域提取出视频对象，不需要耗时的解码步骤更是人们关注的热点。根据视频的时域和空域信息，联合交互式分割的优点，寻找更为有效的时域分割和空域分割算法，快速识别出视频对象并自动分割成为视频分割算法的发展方向。
本文提出一种综合时空要素进行的视频分割算法。首先,通过特征点的帧差运算，分离出物体轮廓，用改进分水岭算法实现标记；然后，通过光流对信息进行评判，得到运动对象的运动模板；最后，将标记区域和运动模板结合，实现前景对象从运动背景中分割。
1算法框架
采用改进分水岭算法结合自适应Horn-Schunck光流法对运动背景下的视频图像进行分割的系统框架图如图1所示。
图1 系统框架Fig.1 System framework
图1中，首先，计算视频序列中相邻两帧特征点的差值，配合最小二乘法进行运动补偿，以抵消因摄像机运动而导致的背景变化；然后，将原始图像与经过运动补偿的相邻帧做帧间差分运算，以降低后续计算量；采用二值开闭重建滤波器完成分割预处理，再用改进的分水岭算法进行区域标记；接着用自适应光流法产生运动模板，将此运动模板和标记的图像区域对比，实现运动对象从背景中分离出来；后处理的目的是进一步消除在对象中残留的噪声区域，最后得到准确的分割对象。
2算法步骤
2.1运动补偿及帧间差分算法
由于摄像机的高速采样，通常认为视频序列背景是不动的，帧间背景的运动完全是由于摄像机的运动引起的。本文采用Moravec法进行帧间图像的配准。首先将2帧图像中提取的角点进行块匹配，即以第1帧中的图像角点(u,v)构造图像块大小为(2n+1)(2m+1)的块(其中，n，m分别为水平方向和垂直方向的像素。在第2帧中以大小为(2dx+1)·(2dy+1)(其中，dx，dy分别为水平方向和垂直方向的像素)的范围进行搜索，找到满足条件的候选特征点，一般块的大小为8×8,其搜索范围一般取10×10[13]。
最小二乘法估计仿射参数,可以补偿因摄像机运动而导致的背景改变，其具体算法如下。
设2帧间的所有特征点都满足
(1)
(1)式中：xi，yi分别为前一时刻和当前时刻图像的第i对特征点坐标的向量；α是可逆的线性变换；β为二维平移向量。
通过上述算法得到这些参数后，就可以补偿摄像机的偏移导致的背景运动，由于上述算法得到的结果是实数而非整数，所以，对每个像素点采用向前和向后映射来弥补此缺陷，用双线性插值方式得到运动补偿帧。
经过全局运动补偿，可以认为帧间背景不变。差分运算的目的是减少分割区域的数目，降低计算量，特别适合于对象内部不太平滑的这类序列。设A,B,C是经过运动补偿后的相邻帧，它们与图像A的帧间差分结果表示为
(2)
(2)式中：(i,j)表示像素坐标；D(i,j)表示帧差后的图像；T1为阀值。
2.2预处理过程
这里采用二值开闭重建滤波器进行预处理，即使用连通结构元对图像进行腐蚀，对没有被彻底腐蚀的连通区域采用二值重建恢复。图像中那些没有彻底被开闭运算滤出的边界，其轮廓在此过程中得以保留。
开闭重建滤波器是基于连通算子的形态滤波器，表示为
(3)(3)式中：γ,φ分别表示开运算和闭运算；g代表重建图像；rec代表重建运算；n代表结构元素的大小[14]。
2.3分水岭算法
为了克服传统算法存在的问题，如对图像中的噪声极敏感、易产生过分割和对低对比度图像易丢失重要轮廓的缺点[15]。本文提出一种改进的分水岭算法来标记区域，将传统的分水岭算法作用于待分割图像信号的梯度图上，增加了补充标记的过程，本算法由以下几步组成。
1)对低于某一阈值的像素点,在梯度图上作为集水盆进行淹没处理。
2)对水盆进行标记。同时按预先规定的规则，对没有被标记的像素归类到已经标记的集水盆中。
3)进一步标记剩余的像素，并进行合并。
先按(4)式得到水岭算法初步标记。
(4)
(4)式中：R(i,j)是预处理后的结果；T2为阈值；G(i,j)是R(i,j)的梯度,定义为
(5)
(5)式中：μ为膨胀操作；ν为腐蚀操作。
当N(i,j)=R(i,j)，对像素(i,j)来说，是在一个相对凹凸不平的区域。假设(a,b)表示(i,j)的8个相邻像素，存在一个最小梯度差G(a,b)-G(i,j)，将(a,b)与(i,j)的像素值标记为相同；如果有多个，则标记为其中灰度差值较小的一个。通过多次迭代，使得每个像素都有被标记的机会。对于N(i,j)=0的情况，可以认为像素(i,j)处在一个相对平滑的区域，可以采用简单的随机区域标记。
2.4自适应光流法
区域分割完成后，常规的做法是用Horn-Schunck法通过Gauss-Seidel迭代法获取运动对象的速度拉氏因子，但该算法迭代的次数与图像本身的大小和复杂情况有关，即使用估值算法也要4次有限差分才能解决。这种方法只用到了当前帧与下一帧图像数据，对于k-1和k+1帧之间的遮挡问题未作分析，本文提出一种自适应梯度的光流法来描述遮挡问题。
在图像的运动过程中，通常前一帧和后一帧之间存在遮挡问题，假定图像的运动在一个很小的时间间隔内是平滑的，利用动态规划的思想，后一帧的遮挡问题通过研究前一帧得到解决,如图2所示。
图2 遮挡问题Fig.2 Occlusion problem
前景中的运动目标用黑色表示，在k-1,k,k+1这3帧中，第k帧中被覆盖的背景在k-1帧中用水平阴影表示，没有被覆盖的背景用灰色部分表示；在k+1帧中有被覆盖的背景，但在k帧中找不到与k+1帧中匹配的区域，却在第k-1中有与之匹配的区域(灰色部分)。图2中第k+1帧中的竖形线条表示在k+2帧中被覆盖的部分。传统Horn-Schunck算法，通过计算k+1帧图像数据的时空域梯度，得到第k帧的光流矢量[16]。
改进的Horn-Schunck算法，设图像的灰度变化函数用I(a,b,c)表示，则光流方程为[17]
(6)
(6)式中，
根据(6)式，定义代价函数S，即
(7)
(7)式中：上标“f”表示前向求k,k+1帧的时空域梯度；上标“b”表示后向求k-1,k帧的时空域梯度。
通过S自动选择前向和后向图像信息，为了解决遮挡问题、半个像素的偏离和最小的半个时间间隔，提出了如下算法。
2)估计Ic。
3)估计un+1,vn+1。
4)如果MSE
6)输出u,v。
经过阈值处理删除少量的运动矢量，得到的运动模板为
(8)
(8)式中：v为光流场；T3为阈值。
最后将4标记区域与运动模板结合，除去少量的噪声区域，便得到准确的前景对象。
3仿真实验
本文采用某视频节目的一段视频序列进行实验测试，以检验本文所提出算法的可行性。图3给出了视频序列重建滤波器的每个步骤的实验结果。
从图3可以看出，在开重建后(见图3d)，图像中大部分斑点被有效滤除，并保持了前景的轮廓，然后经过图3e的运算后，填充了运动区域的小洞，也保持了轮廓，为下一步进行特征提取提供了良好的简化图像。但从实验结果看，形态学开运算对噪声区域有抑制作用，形态学闭运算对运动区域内部的小洞进行了填充，但它们对运动区域的轮廓都有一定程度破坏。
对闭重建滤波后(见图3e)的结果用改进的分水岭算法进行标记，生成标记区域；运用Horn-Schunck算法形成运动模板，将二者结合，得到最终实验结果，如图4所示。实验中阈值T1=2，T2=30。从仿真结果看，分割后的图像视觉质量高，完全可以运用于目标检测与目标跟踪。
图3 运动区域检测结果Fig.3 Result of motion area detection
图4 最终分割结果Fig.4 Final segmentation results
4结论
本文提出一种基于时空信息的运动对象分割算法，在图像分割过程中不需要人工干预，也不需要过多的统计信息，且通过数学形态学的处理能很好地抑制噪声。通过帧间图像配准和最小二乘法估计仿射参数进行背景运动补偿，以抵消背景的全局运动；运用二值开闭重建滤波器进行预处理消除背景噪声，用改进的分水岭算法实现区域标记，用自适应光流法形成运动模板，将此运动模板和颜色模板按照一定准则结合，得到分割的运动对象，通过后处理消除残留噪声区域。仿真实验表明，本算法有效降低了视频对象的分割误差，提高了分割质量。
参考文献：
[1]HORN B K P,SCHUNCK B G.Determining optical flow[J].Artificial Intelligence, 2004, 17 (81):185-203.
[2]LUCAS B D，KANADE T. An Iterative Image Registration Technique with an Application to Stereo Vision[C]//Proc.Processing of the International Joint Conference on Artificial Intelligence. [s.l.]:[s.n.]，1981:674-679.
[3]MECH Roland, WOLLBORN Michael.A Noise Robust Method for 2D Shape Estimation of Moving Objects in Video Sequences Considering a Moving Camera[J].Signal Processing,1998, 66(2): 203-217.
[4]THOMAS Meier. Segmentation for Video Object Plane Extraction and Reduction of Coding Artifacts[D]. Perth：The University of Western Australia，1998.
[5]CHAN M M, SEZAN M I, TEKALP A M. An Algorithm for Simultaneous Motion Estimation and Segmentation[C]//IEEE.IEEE Internal Conference on Acoustics, Speech and Signal Processing( ICASSP-94),Adelaide, Australia.New York,USA:IEEE Press，1994,221-224.
[6]NERI A, COLONNESE S, RUSSO G,et al. Automatic Moving Object and Background Separation[J].Signal Processing,1998, 66(2):219-232.
[7]PARDAS M.Relative Depth Estimation and Segmentation in Monocular Schemes[C]// Proc.Picture Coding Symposium(PCS97). Berlin, Germany:[s.n.]，1997: 367-372.
[8]GREENSPAN H. A Probabilistic Framework for Spatio-Temporal Video Representation and Indexing[C]//Proc.European Conference on Computer Vision, LNCS1614.Berlin,Germany：Springer-Verlag，2002: 461-475.
[9]DEMENTHON D.Spatio-Temporal Segmentation of Video by Hierarchical Mean Shift Analysis[C]//Proc.Statistical Methods in Video Processing Workshop.[s.l.]:[s.n.],2002:1-12.
[10] MARQUES F, MOLINA C. object tracking for content-based functionalities[C]//SPIE visual communication and image processing,san Jose.[s.l.]:[s.n.],1997:190-198.
[11] KRUSE S. A New Tracking Scheme for Semi-Automatic Video Object Segmentation[C]//Proc.Workshop Image Analysis for Multimedia Application Services(WIAMIS’99). Berlin,Germany:[s.n.],1999：93-99.
[12] MARCOTEGUI B. A video object Generation Tool Allowing Friendly User Interaction[C]//Proc.IEEE Internal Conference Image Processing (ICIP’99), Kobe Japan.New York,USA:IEEE Press，1999.
[13] 崔智高,李艾华. 动态背景融合运动线索和颜色信息的视频目标分割算法[J].光电子.激光,2014,8(25):1548-1557CUI Zhigao,LI Aihua.Video object segmentation algorithm based on Dynamic Background Merge Campaign trail[J]. Optoelectronics Laser, 2014,8(25):1548-1557.
[14] 刘剑秋,阮秋琦.形态学重建滤波器的研究与应用[J].通讯学报，2002,1(23):116-121LIU Jianqiu, RUAN Qiuqi.The research and application of morphological filter by reconstruction [J].Journal of China Institute of Communications，2002,1(23):116-121.
[15] 张晓燕,刘振霞.一种改进的分水岭图像分割算法[J]. 空军工程大学学报：自然科学版,2010，12(11),56-59.
ZHANG Xiaoyan, LIU Zhenxia.An image segmentation Method Based on improved Watershed Algorithm[J]. Journal of Air Force Engineer University: Natural Science Edition, 2010，12(11),56-59.
[16] 孙季丰,欧阳金华.基于分块处理的条件随机场视频分割算法[J].华南理工大学学报：自然科学版,2012,6(40):43-47.
SUN Jifeng,OUYANG Jinhua. A Conditional Random video segmentation algorithm Based on Block Processing [J].Journal Of South China University of Technology ：Natural Science Edition, 2012, 6(40):43-47.
[17] 刘毅.一种基于区域选择的视频对象分割算法[J].科学技术与工程，2014，6(14)：211-217.
LIU Yi. A video object segmentation algorithm based on the selected region [J].Science Technology and Engineering, 2014，6(14)：211-217.
Adaptive video object segmentation algorithm based on background motion
WANG Xiaoping
(College of Computer Engineering ,Yangzi Normal University, Chongqing 408100, P.R.China)
Abstract:In order to divide the video objects from movement background, the author first presents a video object segmentation algorithm based on adaptive background motion, calculates inter-frame motion and affine parameters with the least square method using feature point method, and at the same time reconstruct filter preprocessing with a value of two opening and closing. Then the author puts the image tag into a gray area of different improved watershed algorithm to get information on the object segmentation using optical flow method adaptive to judge the final segmentation of foreground moving objects. The experiment shows this algorithm can accurately segment the video object.
Keywords：motion compensation；adaptive gradient；watershed algorithm；morphological filter by reconstruction
DOI：10.3979/j.issn.1673-825X.2016.01.014
收稿日期：2014-10-21
修订日期：2015-10-20通讯作者：王小平wxp1102@163.com
基金项目：重庆市教委科学技术研究项目(KJ131320)
Foundation Item：The Science and Technology Research Project of Chongqing Municipal Education Commission of China(KJ131320)
中图分类号：TP391；TN911.73
文献标志码：A
文章编号：1673-825X(2016)01-0095-05
作者简介：
王小平(1969-)，男，重庆人，副教授，硕士，主要研究领域为模式识别及图形图像处理。E-mail:wxp1102@163.com。
(编辑：王敏琦)
