基于跨时空域相似邻接图的视频分割算法

张洪超， 张 磊， 黄 华

（1. 西安交通大学电子与信息工程学院，陕西 西安 710049 2. 北京理工大学计算机学院，北京 100081）

随着视频数据规模的日渐扩大以及视频内容的不断丰富，如何准确高效的提取视频中的对象目标是视频分析和处理的重要任务。视频分割是将前景物体从背景中抠取出来，形成单独的对象序列，从而达到对象提取的目标。分割的前景物体可以进一步用于视频压缩、目标识别、视频检索、编辑合成等应用，为语义级别的视频处理提供了素材。因此，视频分割一直是视频处理研究的热点问题，在模式识别、计算机图形学以及计算机视觉等领域受到了广泛的关注[1-5]。

最近几年，出现了很多有效的视频分割算法，这些方法大致可以分为自动分割算法和人工交互分割算法。

视频自动分割算法不需要人工交互，大致可分为基于光流法的分割[6-7]、运动跟踪法[8]和基于变化区域检测的时空法[9-10]3种。由于视频分割问题的复杂性，自动分割算法有时很难分割出理想的前景目标。适当地引入人工交互，可以在很大程度上提高视频分割的效果。

Wang等[1]将基于最小割算法的图像分割算法推广到视频领域，取得了比较好的视频分割效果。该算法允许用户在图像平面空间和时间构成的三维空间中进行交互，提高了交互效率。Li等[2]将二维图像分割中的图割算法推广到视频分割领域，每一个结点不仅与同帧中的邻居结点相连，而且与其前一帧和后一帧中空间距离较近的局部结点相连，从而将视频分割问题转化为三维的图割问题。Bai等[4]引入局部分类器，提出SnapCut视频分类算法，该算法基于运动跟踪结果，可以将用户在关键帧上的交互分割结果传递到下一帧，有效地减少了用户的交互。从颜色建模方面入手，Bai等[5]将运动估计加入颜色模型的创建过程中，得到了运动自适应的颜色模型，该模型可以根据运动的局部特征对所建模型参数进行自适应地调整，并根据建立的运动模型，实现对运动物体的分割。

无论是基于视频局部邻域关系建图[1-2]，还是引入运动跟踪来辅助视频分割[4-5]，都要求视频的前景目标在相邻帧之间的位移较小。对于一些帧率较小或者前景目标发生快速运动、遮挡等情况的视频进行分割时，上述算法往往失效。Huang等[11]对图割算法进行了改进，基于该改进图割算法提出了RepSnapping图像分割方法，用户只需要很少的交互，即可对图像中大量的重复物体进行快速有效的分割。本文将上述算法推广到视频分割领域，并且认为视频片段中每一帧图像的待分割前景目标具有一定的相似性，并且视频背景没有发生较大的变化。在上面两条假设的前提下，对于待分割视频片段，用户只需要在一帧图像上进行交互，同时对少数帧进行修正，即可实现对整段视频的分割。实验结果表明，本文所提出的算法在保证分割效果的同时，有效地解决了上面提到的待分割目标遮挡、快速运动等情况；并且，只需要用户在关键帧图像上进行少量的交互，所需交互量远少于上述分割方法。

1 算法介绍

RepSnapping算法通过求解一基于相似特征构建的二维图得到最优化目标函数的解，实现对重复物体快速、有效地分割。本算法将上述二维图推广到视频领域，通过求解相似性邻接图分割问题，得到最优化目标函数的解，实现对视频片段的分割。下面首先对RepSnapping算法进行简要介绍，然后详细介绍视频分割问题模型的建立和相应相似性邻接图分割问题的构建与求解。

1.1 RepSnapping图像分割算法简介

对于输入图像I，图像分割的目的是为每一个像素p∈I指定一个标签，得到前景像素集合｝和背景像素集合标签集合｛fp｝通常是通过最优化一个能量函数得到。首先，将输入图像用一个图G=(N , E)来表示，其中N表示图中的结点集合，每一个结点ni∈N对应于输入图像中的一个像素，E表示图中结点之间的边的集合，每一条边对应于一对具有特定关系的结点。

RepSnapping图像分割算法在传统的基于马尔可夫随机场的图像分割方法[12]的基础上进行了改进，在其最优化目标函数的基础上增加了一项基于特定特征相似性的平滑项惩罚，使其适用于同时分割多个重复物体。RepSnapping算法的最优化目标函数如下

其中，Dn( fn)表示将结点n的标签设为fn时带来的数据项惩罚，即按照先验知识，该结点为前景，系统将其判为背景带来的惩罚，或者按照先验知识，该结点为背景，系统将其判为前景带来的惩罚； np＜nq表示图中相邻结点之间的单向组合，这里的“相邻”可以是四邻域相邻或者八邻域相邻；表示两相邻结点分别被判为前、背景时带来的基于空间连续性的平滑项惩罚；H表示相似像素点对的集合，表示两相似结点分别被判为前、背景时带来的基于特定特征相似性的平滑项惩罚。各结点的标签｛fn｝通过最小化上述目标函数得到。

1.2 跨时空域相似性邻接图的建立

本文算法将RepSnapping算法的框架推广到视频领域，实现对视频片段的快速、高效的分割，并且对前景目标发生遮挡、快速运动等现象的视频分割具有很好的稳定性。

假设待分割视频片段中的连续k帧图像为fr1, fr2,… , f rk，则输入视频片段可以用 1个相似性邻接图来表示，其第 1、2个维度对应于视频图像所在的平面空间，第3个维度为时间轴，对应于视频片段中的帧数，如图1所示。对视频片段进行前景分割的目的是为每一个像素p ∈ f rs = ｛ fr1, fr2, … , f rk｝指定一个标签 fp∈ ｛ 0,1｝，得到每一帧图像的前景像素集合 F =｛p : fp=0｝和背景像素集合 B =｛p : fp= 1 ｝。假设对于视频片段中的图像帧frj，其像素点集合对应的在相似性邻接图中的结点集合为Nj，则整个相似性邻接图中的结点集合 N = ｛ N1, N2,… ,Nk｝，整个相似性邻接图中的边的集合E中的元素对应于一对具有特定关系的结点 np, nq，其中np和nq是结点集合N中的两个结点。如果在第i帧fri上进行交互，则标签集合通过最优化下述能量函数得到

其中， Dn( fn)表示将交互帧fri中的像素对应的结点n的标签设为 fn时带来的数据项惩罚；np＜nq表示图中相邻结点之间的单向组合，这里的“相邻”除了包括该帧图像中与特定结点相邻的8个结点外，还包括前一帧和后一帧图像中与该结点相邻的18个结点；H表示N中相似结点对的集合，如果两像素特定的特征空间中的距离小于一个给定的阈值，其中ni和nj分别为像素i和 j对应的结点；义同式（1），只是这里的“相邻”和“相似”关系已经被推广到了三维相似性邻接图中。

图1 相似性邻接图割算法图构建示意图

下面详细介绍求解式（2）所用的相似性邻接图的具体构建过程。首先，用户通过在第i帧进行交互，确定种子前景区域F和种子背景区域B，用作分割时的先验信息。根据用户提供的先验信息，确定式（2）中的数据惩罚项Dp，在相似性邻接图中对应于交互帧fir中的像素对应的结点与s、t结点（如图1中红色结点所示）之间的连接权值Dp

其中C( p)表示像素p在给定特征空间中的坐标。

其中， np, nq∈N，λ为常量，用来平衡数据惩罚项和平滑惩罚项之间的权重，β为常量，用来控制在分割过程中对梯度变化的容忍程度。

根据像素点对在给定特征空间中的距离，确定结点集合N中的相似点对集合H：如果结点ni对应的像素i和结点nj对应的像素 j在给定特征空间中的距离小于一个给定的阈值ε，则应的式(2)中的第3项，在相似性邻接图中对应于结点np与其相似结点（如图1中绿色结点所示）之间的连接权值，定义为

1.3 最大流/最小割的视频图分割

根据上述对数据项惩罚、基于空间连续性的平滑项惩罚和基于相似性的平滑项惩罚的定义，可以通过最大流/最小割优化算法对所构建的跨时空域相似性邻接图（如1所示）在多项式时间内进行快速求解，从而实现对视频片段的分割[12-14]。

由于基于像素所构建的图通常包含大量的结点和边，计算复杂度较高。为了降低计算量，本算法借鉴 Lazy Snapping[15]的方法，对输入视频片段各帧采用均值偏移算法[16]进行过分割预处理，并以分割得到的区域为基础进行相似性邻接图的构建。图的结点对应于每个分块，图的边对应于相邻、相似分块，其中分块之间的相邻关系除了同帧图像中直接毗邻的区域外，还包括相邻帧中包含具有相同空间坐标的像素的区域对，如图2中蓝色结点代表的区域，相似关系定义为在给定特征空间中的坐标距离小于给定阈值的区域对，如图2中绿色结点代表的区域所示。由于分割所得分块数目相对于原像素数目大为减少，所得相似性邻接图在复杂性上远远小于基于像素所构建的图；同时，过分割所得分块很好地保留了物体的局部结构，从而保证了在加入预分割过程之后，分割效果不会降低。经过均值偏移进行预分割之后，本算法在保证分割效果的基础上，大大提升了运算速度，对于用户的交互，可以实时得到分割结果。

图2 基于均值偏移预分割图的构建示意图

2 实验结果及分析

为了验证本文算法的有效性，我们实验了很多视频片段。在相似性特征选取方面，本文实验以 RGB颜色特征为例进行，也可以选取 Gabor纹理特征或者SIFT特征进行相似性检测。并且将实验结果与 Bai等[4]于 2009年提出的 Video SnapCut方法进行了比较。Video SnapCut方法（Roto Brush）已经集成到了After Effects CS5中，是一个比较成熟的方法。

本实验需要调节的参数包括同时分割的视频片段帧数k、式（3）中的λ和β、式（4）中的μ和求解相似性结点对集合H时的阈值ε。实验中，k取10，即每次同时分割10帧图像；式（2）中各惩罚项之间的平衡参数λ=2、u=10；β直接影响最终分割结果的平滑程度，实验中取为0.1；ε决定着相似性结点对集合H中的元素，实验中取为4。预分割过程所用的均值偏移算法中的3个参数设定如下：位置空间带宽设为5，颜色空间带宽设为5，分割区域最小面积设为50个像素。

实验中所用的机器配置如下：AMD速龙双核CPU，2GHz，2GB内存，32位操作系统。实验中以 10帧为单位进行同时分割，各阶段所用时间和交互笔画数比较见表1。

表1 视频分割所用时间及交互笔画数比较

本文算法在能量函数中引入了基于相似性的平滑项惩罚，使得在应用本文算法进行视频分割时，只需要用户在第1帧图像上进行交互，算法可以自动将用户交互信息传递到其它各帧，大大减少了用户的交互量（如图 3所示）；并且用户交互信息的传递不会因为前景目标出现快速运动（如图3中视频1、2所示）、遮挡（如图3中视频3所示）等情况而中断，提高了算法的稳定性。

图3 本文实验结果与SnapCut方法[4]的对比（在分割结果中，红色笔画表示前景，蓝色笔画表示背景）

由于在实验过程中仅仅选用了颜色特征进行相似性判断，而没有考虑纹理等特征，在对一些前、背景颜色特征比较相似的视频片段进行分割时会出现比较大的误差，甚至失败，如图4所示。

图4 视频分割结果（这两幅图像分别为待分割视频序列中的第1、4帧图像）

3 结 论

本文将RepSnapping图像分割算法推广到视频领域，通过基于整个时空域相似性构建扩展的邻接图，将视频序列中出现的前景物体关联，从而借助高效的最大流/最小割算法实现视频的快速分割。相比于以前的视频分割，该方法大大减少了用户交互，而且对于前景目标被遮挡、运动快速等情况可以得到更准确的视频分割结果，具有很好的稳定性。

尽管本文的方法可以取得很好的分割结果，但是，当视频片段的前景目标和背景在选定的特征空间中比较相似的情况下，应用本文算法不能得到令人满意的分割结果。作为以后的工作方向，我们拟引入更具甄别性的特征，如 SIFT特征，进行相似性区域检测，从而进一步提高视频分割的准确度，在少量用户交互的前提下提取满足用户需求的前景对象序列。

[1]Wang J, Thiesson B, Xu Y, et al. Image and video segmentation by anisotropic kernel mean shift [C]//European Conference on Computer Vision, 2004:238-249.

[2]Li Y, Sun J, Shum H. Video object cut and paste [J].ACM Transactions on Graphics (TOG), 2005, 24(3):595-600.

[3]Wang J, Bhat P, Colburn R, et al. Interactive video cutout [C]//ACM SIGGRAPH, 2005: 585-594.

[4]Bai X, Wang J, Simons D, et al. Video snap cut: robust video object cutout using localized classifiers [C]//ACM SIGGRAPH, 2009: 1-11.

[5]Bai X, Wang J, Sapiro G. Dynamic color flow: a motion-adaptive color model for object segmentation in video [C]// European Conference on Computer Vision, 2010: 617-630.

[6]Stiller C. A statistical image model for motion estimation [C]//International Conference on Acoustics,Speech, and Signal Processing, 1993: 193-196.

[7]Chang M, Sezan M, Tekalp A. An algorithm for simultaneous motion estimation and scene segmentation [C]//International Conference on Acoustics, Speech, and Signal Processing, 1994:V/221-V/224.

[8]Meyer F, Bouthemy P. Region-based tracking using affine motion models in long image sequences [J].CVGIP Image Understanding, 1994, 60(2): 199-140.

[9]Mech R, Wollborn M. 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.

[10]Kim M, Choi JG, Lee M H. ISO/IEC JTC1/SC29/WG11 MPEG97/m2387, Performance analysis of an ETRI's global motion compensation and Scene cut detection algorithms for automatic segmentation [S].

[11]Huang H, Zhang L, Zhang H C. RepSnapping:efficient image cutout for repeated scene elements [J].Computer Graphics Forum, 2011, 30(7): 2059-2066.

[12]Kolmogorov V, Zabih R. What energy functions can be minimized via graph cuts? [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004,26(2): 147-159.

[13]Boykov Y, Jolly M. Interactive graph cuts for optimal boundary & region segmentation of objects in ND images [C]//International Conference on Computer Vision, 2001: 105-112.

[14]Felzenszwalb P, Huttenlocher D. Efficient graphbased image segmentation [J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

[15]Li Y, Sun J, Tang C, et al. Lazy snapping [J]. ACM Transactions on Graphics (TOG), 2004, 23(3):303-308.

[16]Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(5): 603-619.