视频识别中基于簇的在线运动分割算法研究

徐向艺，廖梦怡

视频识别中基于簇的在线运动分割算法研究

徐向艺，廖梦怡

仿射相机模型下，运动分割问题转化为子空间分离问题，处理这类问题的算法大多是离线算法，当假设不满足时性能很不理想。针对上述问题，提出一种在线运动分割算法，通过动态标签传输和簇分割进行运动分割。首先，根据固定数量的帧进行初始化，接着，通过在线策略更新轨迹相似性，最后，利用动态标签传输技术在帧间传输信息，对簇进行评估和归一化切分成本估计，实现动态的簇分割。基于基准数据集的仿真实验结果表明，算法的运行结果与离线算法相当。

仿射相机模型；运动分割；动态标签；簇；轨迹

0 引言

最近几年，来自电视直播、网络视频流和移动设备流的视频数量大量增加。然而，大多数运动分割算法[1,2]是离线算法，且计算开销大。因此，处理流媒体视频的效率较低，需要开发新的在线运动分割算法。在线运动分割算法可为大量应用带来帮助。例如，一是基于静态相机的拍摄视频，可以使用当前背景去除技术[3]实现不同运动者的分割。一是使用运动分割技术离线处理视频。如果处理之后出现更多可用数据，则情况会更为复杂，因为必须要重头重新处理整个视频。可从在线运动分割技术获益的另一领域是3D电视处理。有了实时运动分割技术后，用户设备处于移动之中也可以进行2D到3D转换和视频重新定位。其他应用包括移动目标的在线检测和分割，以及基于移动平台的视觉监视，等等。

运动分割主要处理基于场景不同运动的特征轨迹分割问题，因此是实现目标分割和动态场景理解的重要步骤。鉴于此，本文提出一种在线运动分割算法，算法的成功实施对于动态场景理解、视频识别等应用的发展具有重要意义。marple 7序列第40帧和150帧及基于本文算法的分割结果如图1所示：

图1 marple 7序列的第40和150帧及基于本文方法获得的相应的分割结果

可以看到，即使marple 7的第40帧受到遮蔽影响，但在整个帧序列中仍然得到正确跟踪。

1 相关工作

运动分割问题是目前视频应用领域研究的热点问题，相继有众多学者提出了一系列有代表性的方法，如文献[4]提出一种基于均值偏移的自动运动分割算法。文献[5]针对已有的基于流形学习的分割算法多采取全局或局部线性化的学习策略，无法解决序列数据的局部高曲率问题，利用数据的几何特征描述运动的连贯性，提出一种时序流形学习的人体运动分割方法。文献[6]针对复杂视频监控场景中不同运动行为的人群分割，提出了将视频粒子流和有限时间李雅普诺夫指数（FTLE）场相结合的人群运动分割算法。

另外还有，文献[7]针对摄像机运动的情况，提出多目标分割和跟踪的新方法。利用主动轮廓模型，将运动估计和运动分割融合在同一基于时空域的能量泛函中。文献[8] 使用运动目标轨迹周围的局部信息来计算相似度矩阵。然后通过衡量子空间间的角度来构建仿射矩阵。然后使用谱聚类方法进行轨迹簇来实现运动目标分割。文献[9]基于分解的方法直接对轨迹矩阵进行分解。当运动独立时这些方法性能优异。然而，大多数情况下，多种刚性运动不是独立的，比如关节运动。总的来说，以上的大多数运动分割算法都还存在如下的问题：1）将视频的运动分割问题表示为轨迹矩阵的分解问题，因此许多算法假设轨迹横跨整个帧序列。为了处理部分轨迹丢失问题，这些方法借鉴矩阵填充思想。然而，这种做法的效果有限，因为它假设存在部分轨迹横跨整个帧序列；2）仿射相机的假设[3]也限制了把运动分割应用到满足假设的视频中；3）当前的算法大多是离线算法，且计算开销大。因此，处理流媒体视频的效率较低，需要开发新的在线运动分割算法。

为了解决以上方法的不足，本文提出看了一种改进的运动分割算法，与先前方法相比，本文方法是实现在线运动分割的首个算法，且每帧计算时间相同。文中明确地以簇为基础对轨迹建模，因此即使仿射相机假设没有满足，也可以处理视频。另外，本文方法在计算相似度矩阵时考虑了轨迹的整个历史信息。最后的仿真实验也验证了本文算法的有效性。

2 运动分割转化为簇分割

本节主要讨论如何把运动分割问题转化为多重分割问题。首先，给出3维空间中的轨迹如何形成3维簇。然后，给出这些轨迹如何投影到2维图片上时形成3维簇。

设X表示由构成一个刚性对象的一组 3维点构成。它与欧氏度量一起构成3维簇。时间 t = 2,… ,F时的对象运动可被分别表示为刚性转换，且为相机坐标系中的一个3维点。于是，轨迹空间可定义为如下带有子空间拓扑的集合：

此外，将3维轨迹投影到图像坐标系也将生成一个簇。

场景中的每种不同运动均会生成一个簇。在本文中，利用标签传输和密集轨迹技术解决簇分离问题。为了验证标签传输是否适合簇分离问题，如图2所示：

图2 谱聚类(a)VS标签传输(b)

图2(a)是两个月形示例。将这两个月形分离可以看成簇分离问题。然而，在对该例子实行谱聚类时，由于距离较近，一个簇泄露到另一簇上。另一方面，经过适当的初始化，标签传输可以有效分离两个月形如图2(b)所示，。如下节所述，基于先前帧进行初始化。

3 本文方法

本文方法从不断扩展和引入的密集轨迹入手，不断更新与不同运动相对应的轨迹分割。为此，首先给出如何通过在线策略更新轨迹相似性（3.1节）。然后，给出标签传输的必要背景，并谈论当簇不断变化时如何使用标签传输方法维护分割（3.2节）。最后，在3.3节提出两种不同的初始化方法。3.1 在线相似度计算

如上文所述，属于同一个对象的轨迹位于3维簇上。然而，这些簇不是静态的，因为它们是对象运动的函数，而对象的运动随时间发生变化。为了对这些动态簇建模，且避免对每个帧重复求解，本文设计了一种可以通过步进策略进行计算的距离指标。该计算过程必须及时进行且与轨迹长度无关。此外，该指标还需描述空间位置和运动的相似性。直观来说，如果两个轨迹距离较近且运动特点类似，因此更有可能属于同一对象。鉴于此，下面将给出如何通过步进策略计算该指标。

3.2 标签传输

3.2.1 机器学习

本节介绍本文在线对象分割算法使用的机器学习方法。已知图G和权重矩阵W 且是结点i和 j间的链接权重，半监督学习的一种简单思路就是在图中传输标签。设表示被贴标的结点的标签。此外，表示结点标签估计，且和分别对应于被贴标和未被贴标的结点。和基于二进制编码方法进行编码，Y的每个行向量如果元素为1，则表明对应于结点的标签，否则为 0。为了估计标签概率，文献[10]给出的算法对图进行马尔科夫随机游走，从i到j的转换概率为：

然后，算法流程如下：当从结点i开始进行随机游走直至找到标签时，向结点分配到达被贴上正值标签的示例的概率。这一概率可以表示为。可矩阵形式表示为：

可以证明，固定点解为：

3.2.2 基于动态标签传输的簇分离

已知帧 t−1时的轨迹分段情况，本文的目标是获得帧t时的更新标签。为此，需要处理如下几种情形。首先，新轨迹可能被引入到距离矩阵中；其次，当前轨迹的运动信息可能要求我们必须对当前簇进行分割或融合。此外，在前种情况下，新的轨迹可能属于当前对象或者属于新的对象。在本节中，我们描述如何利用本文方法处理这两种情况。

首先，本文研究假设没有新的对象进入场景后，如何利用新的信息更新簇标签。对每个帧，假设扩展后的轨迹具有不同段标签的概率分布。推断标签定义为概率最大的标签。然后，一种方法就是使用这些标签作为有监督标签，再根据利用被标记样本学习而得的分类器确定新轨迹的标签。这种方法有几个问题。首先，没有重访当前标签，因此无法根据标签纠正差错。其次，分类器没有考虑本文已经获得的图结构。

为了解决这些问题，将当前轨迹的标签作为先验知识，然后在考虑图结构的基础上确定由先前帧扩展而来的轨迹及新轨迹的标签。我们向当前帧中的每个结点（轨迹）增添一个与先前帧的轨迹标签相对应的安保结点。设 Puu表示通过相似度矩阵 Wt获得的转换概率，增强后图形的新转换矩阵为：

看上去对每个即将到来的帧再次进行标签传输的做法有些多余，但是其实不然，这主要是因为：首先，通过使用先前标签作为锚点，避免了在谱聚类中的“标签泄露”问题（图 2）。其次，在实践中用迭代方式求解式（4），通过将以前的帧标签作为初始解，可以在少量迭代内实现收敛。

获得了新标签后，需要评估有没有新对象进入场景，原来处于静止状态的对象有没有开始移动。请注意，标签传输只传输当前标签，不引入新的标签。如果有新的对象进入场景，则必有新轨迹的一个相关集合。这些新轨迹必将通过标签传输接收到部分标签，并在相关簇中导致集群内部发生显著变化。类似的，如果有静态对象开始移动，则将降低对象轨迹和同一簇内其他轨迹间的相似性。因此，需要挨个检查簇，确定有没有簇需要分割。具体方法是通过归一化切割来计算最优二元切割，然后评估归一化切割成本。如果成本大于阈值，则保持簇不动。

本文使用如下的方法进行切割。首先，提取与将要评估的簇相对应的子矩阵。然后，求解广义特征值问题。此时，提取与第二最小特征值对应的本征向量，对不同的阈值评估归一化切割成本。归一化切割成本表示为其中y表示阈值本征向量。然后，选择使归一化切割成本最小的向量y作为最优切割。归一化切割成本范围为0到1。在本文方法中，如果切割成本低于阈值，便分割簇。

3.3 初始化

假设在时刻t时的帧，知道时刻t−1时的轨迹标签。本文有两种方法启动系统。首先，可以使用与偏向相机假设无关的离线运动分段算法，以生成初始标签。另一种方法是在开始时为所有轨迹分配一个标签，利用本文簇分割算法确定类别数量。在本文实验中，使用后一种方法，并证明即使不用初始化，也可以检测出场景中的移动对象。簇分割流程如何从单个簇的初始分配开始，进而分割出场景中的两个人，如图3所示：

图3 marple6序列的初始化。

从上至下为第100，160和260帧及其相应的分割结果。在第1个帧中，所有轨迹的标签相同，且场景中几乎没有运动。100帧之后，倚在墙上的男人开始移动，并从背景簇中被自动分割出来。类似地，第160帧之后，靠近摄像机的男人也被检测并从背景中分割出来。

4 仿真实验

本节利用文献[8]中的Berkley数据集评估本文算法，仿真工具为Matlab2012。数据集有26个序列，包括刚性和关节运动。将数据集的真实数据作为189个帧的帧注释。数据集包括一个评估工具。然而，请注意，评估工具只能用于离线算法。例如，它假设整个序列中的每个轨迹均被分配一个标签；如果轨迹在视频序列开始时被分配了一个错误标签，那么即使标签在后续帧中被纠正，轨迹也会受到惩罚。类似地，如果一个对象是静止对象然后运动，那么该方法也会因为当对象处于静止状态时没有分割对象而受到惩罚。这会给本文方法带来不利影响，因为无法在运动出现前实现运动检测。在实际应用中，通过预测流程可以缓解上述问题，此时，算法被允许提前几帧运行以延缓决策。出于一致性考虑，本文使用相同的评估工具衡量误差。

文献[8]的评估工具为每种序列生成5种指标，然后对所有序列求均值。这5种指标是：密度、总体误差、平均误差、过分割误差、以及误差在10%以下的段数（简称为lt10）。密度衡量被标记的轨迹与像素总数量之比。密度越大，表明图像覆盖范围越大。如果算法要求滑动窗口的所有轨迹，则会降低密度。总体误差是正确标记的轨迹数量与被标记的总轨迹之比。评估工具会自动计算簇相对真实数据区域的分配情况，并有可能将多个簇分配给同一个区域。平均簇误差表示每个区域被错误标记的轨迹与轨迹所有数量之比的均值。因为评估工具可能会把多个段分配给同一个真实数据区域，因此评估工具也会给出过分割误差，该误差定义为经过融合以匹配真实数据区域的段的数量。此外，评估工具也会给出误差低于10%的被覆盖区域数量，且鉴于背景因素，每个序列需减去一个区域。

将本文算法与RANSAC[11]、GPCA[12]和LSA[13]等离线算法做比较。如文献[8]所示，当轨迹数量上升时，其他运动分割算法的伸缩性较差。例如，对people1序列的10多个帧，GPCA需要2963秒，LSA需要38614秒，因此，无法基于滑动窗口运行这些窗口。增加窗口大小对密度和分割效果的影响，如图4所示：

图4 增加窗口尺寸后对滑动窗口RANSAC结果的影

虽然增加滑动窗口大小可以提升效果，但是寻找横跨整个窗口的轨迹会更加困难，进而显著降低密度。最右侧图像：cars4序列的第40帧。右面3个图像：滑动窗口值为10、20和30时的分割结果。当滑动窗口大小增加时，横跨整个窗口的轨迹数量变少。

本文方法运行于文献[8]中数据集时获得的定量结果，如表1所示：

表1Berkley数据集的评估结果

本文进行3组实验。首先，针对不包含第1帧的前10帧对本文方法与RANSAC、GPCA和LSA做比较。该实验的目的是定量评估本文算法相对传统的运动分割算法的性能，这些传统的运动分割算法需要横跨整个序列的轨迹集合。在第2组实验中，评估了前200帧的算法性能。为了避免初始化在结果中导致的偏差，从第50帧往后结合真实数据帧展开评估。这组实验的目的是评估算法对长序列的性能。这些序列代表了在线算法的典型应用情景。最后，在第3组实验中，结合整个序列集合和真实数据注释图片进行评估。

当帧数超过 10个时，本文方法的性能优于 GPCA、RANSAC、LSA，且运行结果与文献[8]相当。实际上，如果把范围限定于更长的序列，则本文方法结果优于文献[8]，如第2组实验所示。这表明本文方法的性能优于传统算法，且精度相当。当序列较长时，方法性能与RANSAC算法相当，这一现象表明任何基于滑动窗口的在线算法均存在的一个重要问题。滑动窗口之外的信息无法被记住，因此往往融合已经获知具有不同运动特征的对象。

最后，对整个数据集，实现了在线性能，但是本文方法的性能略低于文献[8]。如果采用预测策略，轨迹决策延迟数个帧，则可进一步降低这些误差。

不同算法对marple1序列前10帧的运行时间，如表2所示：

表2 marple1序列10个以上帧时的计算时间

虽然文献[8]对前10个帧用时19秒，但是将该方法用于滑动窗口时每个帧就需19秒。另一方面，在Matlab2012上未经优化而部署时，每帧需要3秒左右。表3进一步表明，计算时间主要由n n× 距离矩阵的更新和仿射矩阵的计算确定。本文认为，因为这些操作可以基于GPU并行处理，所以实现实时性能的难度不大。

marple1序列单独一个帧时不同阶段的计算时间，如表3所示：

表3 marple1序列单独一个帧时不同阶段的计算时间

各个阶段为：跟踪（track），距离矩阵更新（dist），仿射矩阵(aff)和标签传输（lblprop）。时间以毫秒为单位，轨迹数量为4427。没有包含跟踪时消耗的光流计算。

5 总结

本文给出了如何将运动分割问题转化为簇分离问题。以此为基础，给出了一种在线运动分割算法，该算法不会损失当前最新算法的精度。通过对动态变化的图使用标签传输方法，本文方法既可以维护标签，又可以当更多信息可用时从误差中恢复。本文算法在基准数据集上的运行结果与离线算法相当。

需要在线处理的多种应用场景促使我们研发本文算法。例如，可以通过实时运动分割实现用户设备的在线视频定位。当视频可离线获得时，使用当前离线算法处理2小时左右的视频需要耗时数周。下一步研究工作的重点是基于压缩感知技术来对运动分割中的异常目标进行快速识别。

[1] Unger M, Werlberger M, Pock T, et al. Joint motion estimation and segmentation of complex scenes w ith label costs and occlusion modeling[C]. Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012: 1878-1885.

[2] Zappella L, Lladó X, Provenzi E, et al. Enhanced local subspace affinity for feature-based motion segmentation[J]. Pattern Recognition, 2011, 44(2): 454-470.

[3] Turaga P, Chellappa R, Subrahmanian V S, et al. Machine recognition of human activities: A survey [J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2008, 18(11): 1473-1488.

[4] 蒋鹏, 秦娜, 周艳, 等. 一种基于均值偏移的自动运动分割方法[J]. 计算机科学, 2013, 40(8): 273-276.

[5] 冯林, 刘胜蓝, 王静, 等. 人体运动分割算法: 序列局部弯曲的流形学习[J]. 计算机辅助设计与图形学学报, 2013, 25(4): 460-467.

[6] 童超, 章东平, 陈非予. 基于视频粒子流和 FTLE 场的人群运动分割算法[J]. 计算机应用, 2012, 32(1): 252-255.

[7] 王诗言, 于慧敏. 运动场景下的时空域跟踪模型及原始-对偶算法[J]. 浙江大学学报 (工学版), 2013, 47(4)：521-528

[8] Brox T, Malik J. Object segmentation by long term analysis of point trajectories [M]. Computer Vision–ECCV 2010. Springer Berlin Heidelberg, 2010: 282-295.

[9] Zelnik-Manor L, Machline M, Irani M. Multi-body factorization w ith uncertainty: Revisiting motion consistency [J]. International Journal of Computer Vision, 2012, 68(1): 27-41.

[10] Zhu X, Ghahramani Z, Lafferty J. Sem i-supervised learning using Gaussian fields and harmonic functions[C]. ICML. 2013: 912-919.

[11] Tron R, Vidal R. A benchmark for the comparison of 3-d motion segmentation algorithms[C]. Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, 2007: 1-8.

[12] Vidal R, Hartley R. Motion segmentation w ith m issing data using Power Factorization and GPCA[C]. Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on. IEEE, 2004：310-316

[13] Yan J, Pollefeys M. A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate [M]. Computer Vision–ECCV 2011. Springer Berlin Heidelberg, 2011: 94-106

Research on Online M otion Segmentation A lgorithm Based on Clustering in Video Identification

Xu Xiangyi, Liao Mengyi
(School of Software, Pingdingshan University, Pingdingshan, 467002, China)

Under the affine model, the motion segmentation problem becomes that of subspace separation. Due to this assumption, such methods are mainly off-line and exhibit poor performance when the assumption is not satisfied. In order to solve these problem we propose an approach that achieves online motion segmentation through dynam ic label propagation and cluster splitting. Starting from an initialization computed over a m ixed number of frames, we update the sim ilarity between trajectories in an online fashion. A fter that, we propagate the label information from one frame to the next using dynam ic label propagation, at the same time , evaluate each cluster and measure a normalized cut cost of splitting the cluster for dynamic cluster splitting. The performance of the proposed algorithm is evaluated on a benchmark dataset and achieves competitive performance while being online.

Affine Camera Model; Motion Segmentation; Dynamic Label; Cluster; Trajectories

TP393

A

2014.06.25）

国家自然科学基金（NU1204611）；河南省自然科学基金（132300410278）

徐向艺（1979-），女，河南平顶山人，平顶山学院，软件学院，讲师，硕士，研究方向：智能算法、图像处理，平顶山，467002

廖梦怡（1983-），女，河南南阳人，平顶山学院，软件学院，讲师，硕士，研究方向：云计算、数字媒体技术，平顶山，467002

1007-757X(2014)11-0020-05