一种采用Snake轮廓模型的视频对象跟踪分割方法

摘要

一种采用Snake轮廓模型的视频对象跟踪分割方法，采用时空融合的方式，在时域通过分段帧间形心矢量预测的方式进行Snake轮廓粗定位，然后在空域采用改进后的Snake贪婪方法由初始轮廓演变得到视频对象的精确轮廓。具体地，在时域，将视频序列划分成每四帧一组的分割小组，选取组内前两帧为关键帧，其初始轮廓为通过运动变化检测得到的运动区域的外接矩形，而第三、四帧的初始轮廓是由前一帧的精确轮廓与前两帧的运动矢量投影映射得到的。在空域，在轮廓点迭代更新时考虑到了误差较大的情况，将不可能的轮廓点进行及时剔除。相比于传统方法，本发明克服了手动绘制初始轮廓的缺点，而且精确度高，速度快。

说明书

技术领域

本发明涉及一种视频对象提取中的处理方法，特别涉及一种采用Snake轮廓模型的视频跟踪分割方法。

背景技术

利用视频对象跟踪技术来生成视频对象平面(VOP)的方法，不但能够提高分割结果的精度，而且符合MPEG-4基于内容的图像表示方式。其实质是：利用前一帧的分割结果在当前帧寻找到对象的最佳匹配位置。

目前，国内外也涌现出一些基于对象跟踪的视频分割的方法。视频对象跟踪通常采用模型匹配，主要做法有以下几类：把在当前帧中分割出的对象轮廓根据运动信息投影到下一帧，作为下一帧中运动对象分割的初始轮廓，再结合其它特征在空域内进行精细匹配跟踪；或者把当前帧中的对象轮廓与下一帧中提取的粗轮廓沿图像进行匹配，以便确定跟踪的对象；或者根据当前帧中对象的特征合并下一帧中分割的各个区域从而得到跟踪的对象。常用的方法有基于Hausdorff距离的跟踪(参见张晓波，刘文耀.基于块仿射分类和HD跟踪的视频分割方法[J].计算机应用研究，2008，25(4)：1084-1086)、基于卡尔曼滤波的跟踪(参见张贝贝，肖国强，江建民.基于运动估计的Kalman滤波视频对象跟踪[J].计算机应用，2008，28(8)：2052-2054)、基于区域的跟踪、基于网格的匹配跟踪(参见冯远，黄凤岗，苏菡，王桐.一种基于二维网格的自动视频对象分割及跟踪方法[J].哈尔滨工程大学学报，2003，24(4)：449-452)和基于变形模板的跟踪(参见Shijun Sun，David R.Haynor，Yongmin Kim.Semiautomatic video object segmentation using VSnakes[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，13(1)：75-82)等。

张晓波采用基于块仿射分类和HD跟踪的视频分割方法，自动得到运动对象的二值模型并在随后帧中使用Hausdorff距离进行跟踪，将视频对象运动分为慢变和快变两部分，分别结合背景边缘模型进行匹配更新，分割效果较好，但是计算较为复杂。李兵(参见李兵，须德，王方石.一种基于对象跟踪的视频分割算法[J].北京交通大学学报.2005，29(5)：89-91)利用运动信息，对目标进行跟踪，通过初始帧的精确模板，自动对后续图像进行分割，但是该方法需要通过手动绘制关键帧的初始粗轮廓，而且在对象变形较大时会失效。宋立锋(参见宋立锋，韦岗，王群生.一种半自动分割视频对象的方法[J].华南理工大学学报，2002，30(8)：49-54)模板匹配形成一个闭环来限制后继帧的分割结果，从而避免在对象跟踪过程中分割误差向后不断传递、扩大，精度较高，但仍需手动勾勒初始视频序列的第一帧，无法实现自动快速的分割。

可以看出，采用视频对象跟踪的难点在于如何建立前后帧之间运动对象的对应匹配关系。另外，如何在保证跟踪分割精度的前提下，实现自动快速的分割也是需要继续研究的重点方向。

发明内容

本发明要解决的技术问题是：克服现有技术的不足，提供一种采用Snake轮廓模型的视频跟踪分割方法，在时域实现对各帧运动对象初始轮廓的自动、准确的定位；在空域通过Snake贪婪方法将初始轮廓快速、准确地演变到运动对象的实际精确轮廓。

本发明解决其技术问题所采用的技术方案：采用Snake轮廓模型的视频跟踪分割方法，包括以下具体步骤：

步骤1：对空域Snake贪婪方法进行改进。

步骤2：以四帧F₁、F₂、F₃、F₄为一分割小组，将原始视频序列划分成若干组)，选取F₁、F₂为关键帧，F₁、F₂进行帧间差分得CDM1，F₂、F₃进行帧间差分得CDM2，对关键帧进行运动变化检测，获取运动对象的大致位置，并求出运动区域的外接矩形作为关键帧的初始轮廓，分别为Rect1，Rect2。

步骤3：对F₁、F₂灰度图像进行高斯滤波后进行Sobel边缘检测，然后分别在F₁、F₂内采用改进的贪婪方法以前面得到的初始轮廓、边缘梯度图为输入进行迭代演变，如果没有达到指定的迭代数目或轮廓变动数目小于指定值则继续迭代，若符合条件得到F₁、F₂运动对象的精确轮廓。

步骤4：分别计算F₁、F₂运动对象的精确轮廓的形心Pos1，Pos2，并计算这两个形心间的运动矢量(MV_1to2.x，MV_1to2.y)。

步骤5：投影映射得到非关键帧F₃、F₄的初始轮廓。

步骤6：对非关键帧F₃、F₄灰度图像进行高斯滤波后进行Sobel边缘检测，然后分别在F₃、F₄内采用改进的贪婪方法以前面得到的初始轮廓、边缘梯度图为输入进行迭代演变，得到F₃、F₄运动对象的精确轮廓。

步骤7：将下一个分割小组转入步骤2开始新一轮的分割，直至所有帧分割完毕。

本发明的原理：

(1)空域Snake贪婪方法的改进：在更新控制点到新的轮廓点时，考虑到了新的轮廓点与初始轮廓的位置关系对轮廓演变的影响，剔除了超出初始轮廓之外的轮廓点，将与当前轮廓点欧式距离最近的梯度边缘点作为新的轮廓点；

(2)时域分段帧间形心矢量预测：采用运动变化检测获取关键帧运动对象大致的运动区域；找到运动区域的外接矩形，并计算其形心位置；计算相邻帧形心间的运动矢量；投影映射得到非关键帧的初始轮廓。

由于视频帧间具有很强的时间冗余性，因此短时间内相邻帧的运动趋势的差异比较小，即运动的速度及方向基本不变。如果将视频序列分成较小的帧组，可以由前几帧的运动矢量，及时准确地预测当前帧的运动对象的大致位置。

根据短时间内相邻帧的运动趋势差异相似的前提，可以将视频序列首先分成若干个小段，每段有k帧视频，选取段内的前两帧为关键帧，通过运动检测的方式自动得到这两帧中运动对象的大致区域，然后进行帧内Snake演变，搜索精确轮廓，最后以关键帧间运动对象形心的运动矢量来预测勾勒后续帧的初始轮廓，再在此基础进行帧内Snake精确轮廓定位，从而实现所有帧的视频对象分割。

本发明与现有技术相比所具有的优点在于：

(1)本发明由于采用了时域分段帧间形心矢量预测的方式，能自动地准确地定位各帧运动对象的初始轮廓，克服了Snake轮廓演变中需要手动绘制初始轮廓的缺点。

(2)本发明在空域对Snake贪婪方法进行了改进，因此提取视频对象速度更快、精度更高。

(3)实验证明，本发明方法成功地实现了前后帧之间运动对象的对应匹配关系，并通过改进后的Snake贪婪方法得到了精确的分割结果。

附图说明

图1是本发明采用Snake轮廓模型的视频跟踪分割方法的流程图；

图2是采用本发明改进的Snake贪婪方法进行迭代求解的实验过程；其中(a)表示原始帧的初始轮廓(细线)；(b)表示迭代10次后的轮廓线(粗线)；(c)表示迭代22次后的轮廓线(粗线)；(d)表示迭代30次后的最终提取到的精确轮廓线(粗线)；

图3是BlueBox视频序列前8帧采用本发明方法提取到的轮廓结果(细线为自动定位的初始轮廓，粗线为提取到的精确轮廓线)；其中(a)表示BlueBox视频序列第1帧的提取结果；(b)表示BlueBox视频序列第2帧的提取结果；(c)表示BlueBox视频序列第3帧的提取结果；(d)表示BlueBox视频序列第4帧的提取结果；(e)表示BlueBox视频序列第5帧的提取结果；(f)表示BlueBox视频序列第6帧的提取结果；(g)表示BlueBox视频序列第7帧的提取结果；(h)表示BlueBox视频序列第8帧的提取结果；

图4是FireAlarm视频序列前8帧采用本发明方法提取到的轮廓结果(细线为自动定位的初始轮廓，粗线为提取到的精确轮廓线)；其中(a)表示FireAlarm视频序列第1帧的提取结果；(b)表示FireAlarm视频序列第2帧的提取结果；(c)表示FireAlarm视频序列第3帧的提取结果；(d)表示FireAlarm视频序列第4帧的提取结果；(e)表示FireAlarm视频序列第5帧的提取结果；(f)表示FireAlarm视频序列第6帧的提取结果；(g)表示FireAlarm视频序列第7帧的提取结果；(h)表示FireAlarm视频序列第8帧的提取结果；

图5是本发明方法时域匹配跟踪的示意图，以五角星为例表述了时域跟踪过程，其中F2中实线为MV1，F3中实线为MV2。

具体实施方式

本发明采用Snake轮廓模型的视频跟踪分割方法如图1所示，包括以下步骤：

步骤1：对空域Snake贪婪方法进行改进。

改进思路为：在更新控制点到新的轮廓点时，剔除了处于初始轮廓之外的轮廓点，并将其替换为与当前轮廓点欧式距离最近的梯度边缘点；改进后的Snake贪婪方法的具体步骤如下：

Step1：对于每个控制点i，在它的M邻域查找最大最小梯度值Grand_max，Grand_min；

Step2：计算控制点i及其邻近点的曲率项能量E_curvature(i)、E_{curvature_max}、连续性能量E_continuity(i)、E_{continuity_max}及内部梯度能量E_grandInter(i)；

Step3：规范化能量值，具体公式如下：

E_curvature(i)＝E_curvature(i)/E_{curvature_max}

E_continuity(i)＝E_continuity(i)/E_{continuity_max}

E_grandInter(i)＝(Grand(i)-Grand_min)/(Grand_max-Grand_min)

Step4：计算每个控制点i的总能量，具体如下：

E_snake(i)＝α×E_continuity(i)+β×E_curvature(i)-γ×E_grandInter(i)

Step5：按照Step1-Step4的步骤，同样计算该控制点i附近M邻域的各个点的总能量并找出包括i能量在内的M×M个点的总能量的最小值；

Step6：更新控制点到新的轮廓点。其原则为：

如果控制点i处的能量不是Step5中计算出来的最小能量点：当最小能量点在初始轮廓矩形内，则将控制点更新为最小能量点；当最小能量点不在初始轮廓矩形内，则计算梯度图中与当前控制点i的欧氏距离最近的点，然后将控制点更新为与其欧氏距离最近的点。如果控制点是最小能量点，则不需更新。

Step7：处理下一个控制点i+1，直到轮廓中的所有控制点全部访问完为止。

Step8：统计移动的控制点的比例Th及循环的次数n，若有一个达到预先设定的值，则终止循环，否则从首个控制点开始，重新转入Step1进行搜索。

图2为采用改进的Snake贪婪方法进行迭代求解的实验过程。

步骤2：以四帧F₁、F₂、F₃、F₄为一分割小组，将原始视频序列划分成若干组，选取F₁、F₂为关键帧，F₁、F₂进行帧间差分得CDM1，F₂、F₃进行帧间差分得CDM2，对关键帧进行运动变化检测，获取运动对象的大致位置，并求出运动区域的外接矩形作为关键帧的初始轮廓，分别为Rect1，Rect2。

设视频序列灰度化后f_k(x，y)、f_k+δ(x，y)分别表示点(x，y)在第k帧、第k+δ帧的像素值，δ为对称帧距，则第k帧的累计帧差结果d_k(x，y)，即运动变化区域，可表示为：

$d_k(x,y)=\left(\begin{array}{cc}255& \mathrm{if}(\mathrm{abs}(f_{k+\delta }(x,y)-f_k(x,y))>T_1||\mathrm{abs}(f_{k-\delta }(x,y)-f_k(x,y))>T_2)\\ 0& \mathrm{else}\end{array}\right)$

其中T₁，T₂为帧差阈值，其取值根据视频序列中运动目标的运动速度、幅度，以及噪声分布情况来选取，具体实现时可通过多次实验来确定(运动目标的运动速度和幅度越大T₁，T₂取值就越大，否则越小。通常T₁，T₂取值范围为[1，20])。abs()为取绝对值操作。

然后，将得到的运动变化区域进行逐像素遍历，找到运动区域的水平和垂直方向的边界坐标，具体表示为：

X_max＝max(x|d_k(x，y)＝＝255)    X_min＝max(x|d_k(x，y)＝＝255)

Y_max＝max(y|d_k(x，y)＝＝255)    Y_min＝max(y|d_k(x，y)＝＝255)

d_k(x，y)表示第K帧的累计帧差结果。max()表示取最大值操作。X_max表示运动区域在水平方向的最大位置，X_min表示运动区域在水平方向的最小位置。Y_max表示运动区域在垂直方向的最大位置，Y_min表示运动区域在垂直方向的最小位置。

由以上四个边界位置围成的封闭矩形即为运动区域的外接矩形，也就作为关键帧的初始轮廓，分别为Rect1，Rect2。图3(a)(b)(e)(f)、图4(a)(b)(e)(f)中的细线矩形即为采用这种方法自动定位的关键帧的初始轮廓。

步骤3：对F₁、F₂灰度图像进行高斯滤波后进行Sobel边缘检测，然后分别在F₁、F₂内采用改进的贪婪方法以步骤1得到的初始轮廓、边缘梯度图为输入进行迭代演变，如果没有达到指定的迭代数目或轮廓变动数目小于指定值则继续迭代，若符合条件得到F₁、F₂运动对象的精确轮廓。图3(a)(b)(e)(f)、图4(a)(b)(e)(f)中的粗线即为关键帧采用贪婪方法迭代演变后确定的精确轮廓。

步骤4：分别计算F₁、F₂运动对象的精确轮廓的形心Pos1，Pos2，并计算这两个形心间的运动矢量(MV_1to2.x，MV_1to2.y)。

设(x，y)为精确轮廓S上的任意一点，则形心(X，Y)中：

$X=\underset{x\in S}{\Sigma }x$$Y=\underset{y\in S}{\Sigma }y$

设关键帧F₁、F₂对应的经过Snake贪婪方法收缩得到的精确轮廓的形心分别为(X₁，Y₁)＝(Pos1.x，Pos1.y)，(X₂，Y₂)＝(Pos2.x，Pos2.y)，则精确轮廓的运动矢量(MV_1to2.x，MV_1to2.y)可以表示为：

MV_1to2.x＝Pos2.x-Pos1.x

MV_1to2.y＝Pos2.y-Pos1.y

其中，Pos1.x，Pos2.x分别表示关键帧F₁、F₂形心横坐标，Pos1.y，Pos2.y分别表示关键帧F₁、F₂形心纵坐标。

图5为时域跟踪匹配的示意图，以五角星为例表述了时域跟踪过程。其中的实线箭头即为采用该方法获取到的运动矢量。

步骤5：投影映射得到非关键帧F₃、F₄的初始轮廓。

设每个分割小组的非关键帧为F₃、F₄，F₃、F₄都是由前一帧的精确轮廓根据形心间的运动矢量投影映射得到的。F₃的初始轮廓就是将F₂的精确轮廓以形心Pos3为中心，(MV_1to2.x，MV_1to2.y)为偏移量向F₃的边缘图像映射。其中，Pos3为：

Pos3.x＝Pos2.x+MV_1to2.x

Pos3.y＝Pos2.y+MV_1to2.y

同样，F₄的初始轮廓是将F₃的精确轮廓以形心Pos4为中心，(MV_2to3.x，MV_2to3.y)为偏移量向F₄的边缘图像映射。

其中，(MV_2to3.x，MV_2to3.y)为：

MV_2to3.x＝Pos3.x-Pos2.x

MV_2to3.y＝Pos3.y-Pos2.y

公式中Pos2.x，Pos2.y表示精确轮廓F₂的形心横纵坐标，Pos3.x，Pos3.y表示非关键帧F₃形心的横纵坐标。

Pos4为

Pos4.x＝Pos3.x+MV_2to3.x

Pos4.y＝Pos3.y+MV_2to3.y

图3(c)(d)(g)(h)、图4(c)(d)(g)(h)中的细线即为非关键帧投影映射后得到的初始轮廓。

步骤6：对非关键帧F₃、F₄灰度图像进行高斯滤波后进行Sobel边缘检测，然后分别在F₃、F₄内采用改进的贪婪方法以前面得到的初始轮廓、边缘梯度图为输入进行迭代演变，得到F₃、F₄运动对象的精确轮廓。图3(c)(d)(g)(h)、图4(c)(d)(g)(h)中的粗线即为非关键帧采用贪婪方法迭代演变后确定的精确轮廓。

步骤7：将下一个分割小组转入步骤2开始新一轮的分割，直至所有帧分割完毕。

本发明方法采用两个自拍视频序列BlueBox和FireAlarm进行了实验。由于篇幅的原因，这里只是给出了BlueBox和FireAlarm两个序列前8帧的提取结果(如图3、图4所示)，但在实验中，本发明实施例选取了近150帧进行测试，每一帧的结果都比较精确。

为了客观评价本发明方法的正确性和有效性，采用在MPEG-4核心实验中由Wollborn等提出的评价准则进行评价。该准则定义每帧的分割对象掩膜的空间准确度SA(spatial accuracy)为：

$\mathrm{SA}=1-\frac{{\Sigma }_{(x,y)}{A}_t^{\mathrm{est}}(x,y)\oplus A_t^{\mathrm{ref}}(x,y)}{{\Sigma }_{(x,y)}{A}_t^{\mathrm{ref}}(x,y)}$

式中，和分别表示第t帧的参考分割和实际分割方法所得到的对象模板；代表二值的“异或”操作。SA的取值范围为[0，1]。空间准确度反映了每一帧的分割结果与参考分割模板之间的形状相似程度，SA越接近于1，表明分割越准确，SA越接近于0，表明分割越不准确。

本发明通过手工方式来获取参考分割的对象模板。表1和表2给出了通过实验获取的空间分割的准确度SA。

表1  BlueBox前20帧采用本发明提取的空间准确度

表2  FireAlarm前20帧采用本发明提取的空间准确度

从图3、图4看出，采用本发明提出的基于Snake的视频跟踪分割方法对背景比较单一的视频序列分割效果非常好，每个视频段的前两帧关键帧能够自动捕获运动对象的初始位置，如图3的(a)(b)(e)(f)和图4的(a)(b)(e)(f)中的细线矩形位置所示，每个视频段的后两帧初始轮廓定位也比较接近真实轮廓，虽然并不是很完整，但是最终经贪婪方法搜索的精确轮廓精度比较高而且较连续。

表1和表2的40帧提取精度都在0.95左右，说明本发明提出的基于Snake的视频跟踪分割方法对于背景单一的视频序列能够实现较准确的提取。

本发明说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。