基于平衡熵切片的视频流分割算法的研究

刘芸 许华宇 刘衍

在均衡的熵切片技术的基础上提出了基于流的均衡的熵切片技术。通过UCF运动数据集来评估该方法的有效性。大量实验结果表明这种方法能以在线工作的方式获取更高质量的分割结果，同时花费的时间和内存更少。

视频分割 均衡的熵切片 流处理 超体元

1 引言

随着远程监控系统、无人驾驶系统的大量实际应用，视频分割将在生活中扮演十分重要的角色，如场景的识别感知[1]，阴影/照明的估测[2]，机器人学[3]中已经大量使用到了视频分割技术。在前期的没有长度限制的视频处理中，视频分割技术似乎已经有了一种可靠的方法，它们不像早期的视频分割方法[4]那样需要做一个基于静态的背景假设[4]。视频分割最新的研究成果是产生时空的关联性，如文献[5]、文献[6]、文献[7]可以获得十分出色的视频分割结果。有一些方法甚至可以做到在线的流处理，但是在实际应用中还有很多工作要做。

2 背景介绍

为了详细地说明视频分割的复杂性，本文在总结前人研究成果的基础上提出了以下3个主要挑战：

（1）时间相干性：在不考虑时间相干性的情况下，视频可以被一帧一帧地分割。在这种情况下，作为一个连续的方法是不能展现出帧与帧之间很小的变化，但是却能实时地处理视频。如果使用一个树结构去重构整个视频，将会需要占用很大的内存和硬件资源。在一些监控和交互应用中[8]，不可能把整个视频都放到内存中去处理。所以有些学者就提出了基于流的层分割方法的近似框架[9]，每个帧只会被处理一次并且不会改变前面的帧的分割结果。它可以展现出帧与帧之间很小的变化但是效果却没有使用树结构去重构整个视频的好并且仍然具有算法延迟的特性。

（2）自动处理：随着时间去追踪区域对分割动态场景中感知相似的区域有很大的影响。与追踪相反，去追踪哪一块区域是很难判断哪些帧有这些区域或者追踪的时间方向（向前或者向后）。

（3）可扩展性：如果给出一个视频中的大量的像素点或者特征，视频分割方法将趋向于变慢并且需要很大的内存。最好的方法就是把视频分割成多级的区域，每个区域涉及到时间和空间，并且每个区域也能代表一个物体。

视频的层分割方法表现地很好，归因于相似的多尺度区域被作为产生的层被再评估，但是却没有被广泛采用。结果层包含了丰富的视频多尺度信息，但不能片面地取一层，这样做会丢失一些信息。

基于上述三个方面的挑战，本文提出了一种新的方法去满足这些问题。此方法在获取了足够的帧后，会开始构建一个基于层结构的树。为了获取一个最优的树切片，就会使用特征标准并且使用一个标准的解决方案（IBM CPLEX）去获取树切片。在完成这些之后，系统会输出结果并保存一些信息，然后开始下一次的处理，并将一直循环处理，直到所有的帧都被处理完。

3 基于超体元的视频分割方法

视频分割问题在概念上可以想象成一个聚类的问题，就是通过扫描物体移动时通过的空间和时间，把许多超体元聚集成可以展现的更大单元。从另一方面说，本文所描述的超体元都是聚集成时空体的，如果这个时空体改变了，比如物体从场景中消失，就可以视为一个分割。如果有其他的新物体进入到视频的场景中，这将会使问题变得更加复杂。

一开始视频分割是尝试去把一个视频分割成时间相干的场景。由于视频的信息量是十分庞大的，如果在像素点或者体像素的级别上去分割视频的话也算是时空等价的。因此，大多数研究者倾向于基于超像素或者超体元的研究。他们是把一些相似或相关的像素聚集在一起形成的，而且都是比像素点和体像素都大的实体，现在的很多视频分割方法不是基于超像素的就是基于体像素的。超像素的本质是空间对象，因为需要考虑物体间时空上的关联，所以无论如何都要把从运动或者颜色对比线索获取的像素点的时间方面考虑进去。动作线索可以考虑成一个像素流，简单地说，就是使用光流算法去计算帧与帧之间像素点的移动。其中光流算法是连接两个视频帧之间相同像素的向量，这是一个可以把运动线索合并到视频中的方法。在本文中，只考虑使用超体元去进行视频分割。

3.1 均衡的熵切片技术

Felzenszwalb和Huttenlocher提出了一种基于图的图片分割算法[10]，他们的算法被Grundmann扩展成了基于图的视频分割算法（Graph-based Hierarchy Video Segmentation，GBH）[11]。然而GBH在低层会过分割，在高层会欠分割，因此在高层的时候会包含太少的分割域，在低层的时候会包含太多的分割域。所以，需要在这么多层的分割结果中，找到一个平衡，而这是一个十分复杂的过程。因为需要去平衡不同层之间的信息分布，而一个基于熵概念的均衡的熵切片方法[12]可以解决这个问题。

均衡的熵切片技术包含一个模型（均衡的熵切片模型）和一个能通过一个二进制规划解决这个问题的公式。它只考虑树形的超体元层，比如每一个节点有且仅有一个父节点（除了根节点）而且每一个节点至少有一个子节点（除了叶节点）。GBH可以产生这样的一个树。

均衡熵切片技术需要一个树切片在已经选择的超体元中去帮助它平衡大量的信息，基于一个给出的特征标准，这个特征标准可以是颜色直方图。这个树切片是很多个从根节点到叶节点路径所组成的节点集，图1显示了一个分割树上的树切片。

假设每一个切片都能提供一个扁平的层次结构，比如把结合了切片上所有的节点的树形层次结构平铺在同一层上，就可以从原始视频的超体元层级结构中获得一个新的分割组成。本文之所以会平铺层级结构是因为在不同的层级上对不同的物体进行分割是不可能的。但是一旦平铺了树的层级结构，所有的物体都会被聚集在同一层上，这些物体就会更加适合被分析。所有的树形切片集都包含有用的和无用的节点选择信息，有用的意思是可以使视频的分割结果趋向于精确，无用的意思是使视频的分割结果趋向于模糊。

在树形结构T中，本文用一个二进制的变量xs去表示每个节点Vs。如果节点Vs是切片的一部分，则xs的值就取为1；如果不是，就取为0。本文的方法是用x去表示整个树。任何x的实例都会影响树形结构T中节点的选择，但并不是所有的x实例都是可用的。在一个有效的切片中，在分割树T中，每一条根到叶的路径有且仅有一个节点会被选中。图1从另一方面说，如果是一个有效的路径，那么这条路径只包含一个节点，并以图1指出的方式把那个节点选择出来并以线性约束的方式进行表达。

首先让P表示一个p×N的二进制矩阵。p=|V1|是树T的叶子的节点数，而且N=|T|是树T中所有的节点数。矩阵P的每一行通过设定相应路径上节点的列值（不是1就是0）来编码一条根到叶节点的路径。这样的一个矩阵就列举了树T中所有可能的根到叶路径。更多的细节可以在图2中看到。

为了确保一个树切片是有效的，本文用了下面这个约束：

公式中1ρ是所有1组成的一个长度为ρ的向量。这个线性约束能确保每一条根到叶路径有且只有一个节点在切片x上。如果有多于一个的节点在Pi中被选择，那么Pix>1。如果没有节点在Pi中被选择，那么Pix=0。有效的选择x就被称之为一个树切片。这就是前面说收集包含有用和无用节点的原因。有用的信息就是组成根到叶有效的路径节点，无用的信息就是在约束条件下没有在根到叶有效的路径上。

在一个有效的路径上，在分割树的每条根到叶路径上有且仅有一条路径会被选择，所以就会有很多条路径在切片上。均衡的熵切片技术可以在一个层级中找到最好的切片，这个切片可以包含最大的信息量。通过包含的信息量选择大的或者小的超体元，如果信息量少，本文的方法就选择大的超体元；反之，就会选择小的超体元。

特征标准对一个节点的信息量有很大的影响。层级结构中每个节点的信息量可以通过计算确定的动作或者人为线索的特征去获取熵。假设有一个特征标准F（·）映射一个节点Vs到一个离散特征变量分布，就可以得到：

随着二维离散特征变量的变化而变化，如果希望切片主要关注视频背景是静止的区域，就可以使用一个无人监督的动作特征标准，比如说：光流。

为了去寻找一个树切片，这个树切片不仅可以平衡所有被选择节点所包含的信息量，而且可以同时考虑节点的信息量，于是本文提出了均衡的熵切片技术。它通过最小化被选择节点不同的熵来寻找一个有效的树切片，而且最小化的过程是通过所有有效树切片得到的：

直接最小化式（3）太复杂了，因为它要求枚举出所有有效的切片和包含一个只选择了根节点退化了的最小值。此时就可以使用二进制规划的方法，，即均衡的熵切片技术：

虽然树的高层节点的熵比低层节点的熵要大，但是高层节点的数量要比低层节点的数量少很多。通过添加体积因素，向下去选择层级结构直到获取一个均衡的熵。

在获取了第一次视频块的分割信息后，就尝试着去把这些标记信息传递下去，以此来达到连续分割视频的效果。

3.2 基于流的均衡的熵切片技术

把第一次分割视频的结果信息传递到以后的视频分割过程中，综合考虑了前面提出的问题后，本文提出了一种新方法并把它命名为基于流的均衡的熵切片技术，可以用下面的步骤去描述：

在步骤（1）中，获取一个视频的层级结构是很重要的，GBH就可以获取一个这样的结果。本文提出的方法只能处理树形的超体元层级结构。步骤（2）到步骤（6）会一直持续下去直到所有的视频帧被处理完。在步骤（3）中，使用了一个创新的方法去构建一个树形结构。一开始先把帧的RGB值改为索引值，通过矩阵变换，就可以从层与层之间获取一个相互有关联的层级数据结构的值。这些数据可以用来构建树形结构，具体如图3所示。

在步骤（4）中，使用光流方法去计算视频中每一帧的特征，它的核心思想是使用共轭梯度替代赛德尔或者逐次超松驰方法，使大的线性系统的解决方案变得十分简单。如果有一个很大的线性方程式Ax=b，其中x是流域，它需要在每个内部步骤中被计算出来，而且还需要找到一个可以被分解为筛选和权重的串联矩阵A。这样它就不需要在使用共轭梯度解决方法过程中去记录矩阵A，但是需要去写一个由筛选和权重构成的方程去应用到A得到x的值。在这一步中也会构建一元和二元的项。

因为视频在本文所提出方法的处理过程中是用一个树形结构去展现的，所以就很难保持每一次处理视频过程中颜色的连续性，树的结构信息很难被传送到下一次视频分割中。为了解决这个问题，首先用一个颜色池，在每一次的视频块的处理中，在得到了CPLEX结果后，把从每一层选取的结果画到同一层上。

在这个过程中，从颜色池中选择颜色，因为CPLEX的结果是不可控的，它不会在每一次视频块的处理过程中选择同一块区域。比如人的手在第一次视频块处理中是蓝色的，在第二次视频块处理中，人的手就会从其他层去选择，所以就会变成其他颜色。在第一次处理过程中储存了颜色和其相对应的位置信息（CPLEX的结果），当其他视频块开始把结果画出来的时候，先对比储存的信息，当找到对应的颜色信息后，就会使用第一次视频块处理过程的位置信息，以此来保持颜色的连续性。这个方法可以总结为一个伪代码，具体如下面的算法所示：

4 实验结果与分析

本文提出的算法中，线性和二次项的变量十分重要。实际上可以观察到，层级之间有关联的超体元的选择对σ的变化不是很敏感。正则化这些可以影响视频分割结果的项并通过大量实验结果的对比，最终确定把σ设为10为最优，也就是说本文所提出的方法获取的结果更加倾向于二次项而不是线性的。

本文使用了M.Rodriguez提供的UCF运动数据集[15]来评估本文提出的方法。这个数据集包含了各种各样的运动场地而且具有代表性，所收集的150个视频序列的分辨率都是720×480的，是一个拥有广泛的场景和视角的自然运动特征视频库。

图4到图6展示了相关结果，可以显示出对今后做视频分析很有用的许多细节，并且可以很好地处理本文选择的数据集。

图4中滑滑板的男孩和女孩的外形可以很清楚地显示出来，他们的手臂位置的变化速度超过了他们的身体，但是仍能很好地展现出手臂的变化。

图5的上半部分是一个沿着直线滑行的男孩，所以就很难进行分割，但仍然可以看出男孩的每个动作。在这幅图的底部，有一个女孩坐着不动，有一个男孩向她移动，其他的几个男孩在附近玩耍，结果很清晰地显示了这些。

图6展示了背景是静止的和快速变化的分割结果。上半部分展示的背景是静止的，有人骑着马向前走，人和马的轮廓可以很容易地分辨出来。下半部分是一个人骑着马快速地向前跑，所以背景的变化就很快。在结果中，背景的颜色改变了，但是人和马的颜色依旧保持了一致。

5 结束语

本文的方法不但可以以流的方式不间断地工作，而且可以找到一个树切片，这个树切片不仅可以平衡所有被选择节点所包含的信息量，而且可以同时考虑节点的信息量。通过包含的信息量选择大的或者小的超体元，如果信息量少，就选择大的超体元；反之，就会选择小的超体元。光流被用来作为一个后置的特征标准去驱动信息的选择，它跟原始的超体元处理无关。实验结果表明这种方法不但能以流的方式工作，而且可以获取更高质量的分割结果，同时在时间和内存方面的花费更少。

参考文献：

[1] Criminisi A， Cross G， Blake A， et al. Bilayer Segmentation of Live Video[J]. Proc IEEE Computer Vision & Pattern Recognition， 2006（1）： 53-60.

[2] Liu C. Beyond Pixels： Exploring New Representations and Applications for Motion Analysis[J]. Massachusetts Institute of Technology， 2009.

[3] Alexandros P， Chaohui W， Dimitris S， et al. Simultaneous Cast Shadows， Illumination and Geometry Inference Using Hypergraphs[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2013，35（2）： 437-449.

[4] Vijay B， Ignas B， Roberto C. Semi-supervised video segmentation using tree structured graphical models[J]. IEEE Transactions on Software Engineering， 2013，35（11）： 2751-2764.

[5] Grundmann M， Kwatra V， Han M， et al. Efficient Hierarchical Graph-Based Video Segmentation[J]. Georgia Institute of Technology， 2010，26（2）： 2141-2148.

[6] Drucker F， Maccormick J. Fast superpixels for video analysis[A]. Motion and Video Computing， 2009： 1-8.

[7] Corso J J， Sharon E， Dube S， et al. Efficient Multilevel Brain Tumor Segmentation With Integrated Bayesian Model Classification[J]. Medical Imaging IEEE Transactions on， 2008，27（5）： 629-640.

[8] Liu M Y， Tuzel O， Ramalingam S， et al. Entropy rate superpixel segmentation[A]. IEEE Conference on Computer Vision & Pattern Recognition， 2011： 2097-2104.

[9] Xu C， Xiong C， Corso J J. Streaming Hierarchical Video Segmentation[A]. Proceedings of the 12th European conference on Computer Vision-Volume Part VI， Springer-Verlag， 2012： 626-639.

[10] Felzenszwalb P F， Huttenlocher D P. Efficient Graph-Based Image Segmentation[J]. International Journal of Computer Vision， 2004，59（2）： 167-181.

[11] Grundmann M， Kwatra V， Han M， et al. Efficient Hierarchical Graph-Based Video Segmentation[J]. Georgia Institute of Technology， 2010，26（2）： 2141-2148.

[12] Xu C， Whitt S， Corso J J. Flattening Supervoxel Hierarchies by the Uniform Entropy Slice[A]. Computer Vision （ICCV）， 2013 IEEE International Conference on IEEE， 2013： 2240-2247.

[13] Guo R， Hoiem D. Beyond the Line of Sight： Labeling the Underlying Surfaces[J]. Springer Berlin Heidelberg， 2012（1）： 761-774.

[14] Liu C. Beyond Pixels： Exploring New Representations and Applications for Motion Analysis[J]. Massachusetts Institute of Technology， 2009.

[15] Rodriguez M D， Ahmed J， Shah M. Action MACH a spatio-temporal Maximum Average Correlation Height filter for action recognition[A]. IEEE Conference on Computer Vision & Pattern Recognition， 2008： 1-8.