时间一致性超像素视频分割方法综述

韩艳茹，尹梦晓,2，杨 锋,2，钟 诚,2

1(广西大学 计算机与电子信息学院，南宁 530004) 2(广西多媒体通信与网络技术重点实验室，南宁 530004)

1 引 言

在图像和视频处理中，基于像素级的图像和视频分析处理计算量较大且耗时，而将图像和视频分割为超像素[1]或提取显著点[2]的预处理能使图像和视频更易于操作，这已成为图像和视频处理的标准方式[3].

Ren等[1]首次提出对共享类似低级特征(如颜色或纹理)的空间相干像素进行像素分组得到超像素，并将得到的超像素作为图像分析和处理的基元.超像素使用更丰富(基于区域)的特征集，大幅减少图像基元的数量，从而有效地提高后续处理步骤的计算效率以及分割质量.超像素广泛应用于各种视觉任务，例如图像分割[4-6]，图像解析[7]，跟踪[8,9]及场景分类[10]等.同样，视频超像素在视频分割[11-14]和显着性检测[15-18]等视频分析和处理任务中也具有很大的应用潜力.

通常，超像素是通过最小化代价函数将图像划分而得到的，这使得每个超像素各自为单个对象而不互相重叠.然而，如果将获取超像素的方法直接独立地应用于视频序列中的每一帧，将导致超像素可能在时间上不具有连续性，这样即使连续帧之间仅有轻微变化，超像素也会出现闪烁.近年来有研究者将超像素从静止图像扩展到视频序列来生成视频超像素[19-40]，根据视频处理时视频的加载方式分为离线方法和流式方法.

离线方法要求提前提供视频数据，需要一次性加载整个视频，然后再进行后续操作.由于加载完整的视频需要较大的计算机运行内存，因此用离线方法处理的视频要尽可能短.相关的离线方法有：基于层次图(GBH)[19]、加权聚合分割(SWA)[20-22]、Nyström标准化切割(NCut)[23,24]、均值漂移[25-27]以及文献[28]的方法.其中SWA和Ncut都将标准化切割准则作为基础代价函数，与Ncut不同的是，SWA分层次地最小化代价函数得到分层分割，基于层次图的GBH同样可以实现分层分割.

流式方法不需要一次性加载整个视频，故能够不受计算机运行内存的限制，处理任意长度的视频.流式方法按照解决时间一致性问题的方式可分为三类：图像超像素直接扩展法[29,30]、超体素方法[31,32]以及时间一致性超像素方法[33-40].图像超像素直接扩展法[29,30]直接扩展图像超像素方法进行视频处理,没考虑视频中对象移动的问题.超体素方法[31,32]主要处理3D体积数据(例如医学影像)，将时间维度按空间维度处理，把视频序列看做3D视频体进行处理.时间一致性超像素[33-40]则是利用光流信息传播运动矢量，将第一帧的超像素分割扩展到视频的后续帧中，以流式方式计算视频超像素.超体素和时间一致性超像素密切相关，他们之间的关系可以描述为：具有时间一致性的超像素按帧堆叠得到超体素；超体素按帧进行切片得到具有时间一致性的超像素.但当按帧切片的超体素横截面分割为非连续段时，以上关系不成立[36].本文主要对时间一致性超像素方法进行梳理和总结，对超体素仅作简单介绍，详细总结请参阅文献[3].

超像素分割在计算机视觉领域得到广泛研究和关注，已有相关综述文献大多是关于图像超像素分割的，如文献[5,9]以图像分割为应用背景对超像素方法进行分析总结.现有的视频超像素的综述文献[3,41]没有区分超体素方法和时间一致性超像素方法.超体素主要处理3D体积数据，而时间一致性超像素针对视频数据[35].本文对现有的时间一致性超像素方法进行总结，对评测指标进行更为完整的归纳,在此基础上给出未来可以研究改进的几点建议.

论文其余部分安排如下：2.1节和2.2节介绍视频超像素方法，2.3节分析评测基准指标，第3节介绍在视频处理领域的应用，最后第4节进行总结展望.

2 视频超像素

视频超像素作为一种有效的视频表示方式，将原始视频分割为视频超像素已经成为许多计算机视觉系统中重要的预处理步骤，受到研究者们的广泛关注，各种用于视频分析和处理的视频超像素提取方法被提出.本文将获取视频超像素的方法分为离线和流式两类方法进行介绍.

2.1 离线方法

本节介绍GBH[19]、SWA[20-22]、Nyström标准化切割NCut[23,24]、均值漂移[25-27]以及文献[28]等几种具有代表性的离线视频超像素方法.

GBH是由Grundmann等[19]提出的一种基于层次图的分层视频分割方法，该方法在基于层次图的图像分割[42]的基础上，将相邻的体素合并成小体素组，并从中得到颜色直方图.计算颜色直方图之间的卡方距离并在区域级迭代，由此将体素组进一步合并到较大的时空区域，再通过跟踪合并得到分层视频分割.

Sharon等[21,20]提出的SWA是一种优化标准切割准则的方法，该方法使用自适应代数多重网格算法[43]选择顶点子集，来递归地粗化初始图，由此生成多层次分割，使得精细级别上的每个顶点都与粗级别上的一个顶点耦合.层次结构中的每个顶点表示一个潜在的分割，且层次结构便于算法捕捉图像的多尺度特征.Akselrod[22]首次将SWA扩展到3D领域解决多发性硬化的分割问题，使用SWA算法对输入的三维多通道和各向异性数据进行分层分割，得到有意义的解剖结构和病变相对应的区域.

Fowlkes等[24]提出一种基于Nyström Normalized cuts[23]的图像和视频超像素分割的谱划分方法.该方法首先使用归一化割集的多特征向量将每个体素嵌入到一个低维欧几里德空间中，然后使用k-means算法对这些数据进行最后的分区.

Mean shift是一种模式搜索算法，最早由Fukunaga等[44]提出.Comaniciu等[25]将Mean shift用于图像分割，每个像素都与一个特征点相关联，把核函数应用到特征点的局部结构中，产生的分割可以看作是用高斯核估计特征点密度的模式[25,26].Paris等[27]基于文献[26]的方法，利用因果时空核估计特征点密度，使超像素跨越空间和时间实现了时间相干性，从而将超像素推广到视频流中.

Veksler 等[28]提出第一种生成超体素的方法，该方法通过构造一个包含图像梯度的能量函数，并使用图切割算法优化该能量函数，以达到对每个体素分配一个标签的目的.该方法用重叠的立方体覆盖视频序列，每个立方体的体积决定了产生的超体素的最大体积，体积较大的立方体对应超体素间更高的时间一致性.

2.2 流式方法

本节将介绍三类流式方法：图像超像素直接扩展法[29,30]，超体素方法[31,32]，时间一致性超像素方法[33-40].

2.2.1 图像超像素直接扩展法

Achanta等[29]通过将视频序列视为3D信号进行k-means优化，通过直接扩展用于2D图像的SLIC算法，沿时间轴连接2D图像获得视频超像素.

Van等[30]对文献[45]中的超像素方法进行扩展，使用颜色直方图来表示超像素，并设置一个目标函数来进行优化，其中如果每个直方图的填充区数最小化，则该函数最大化.在分割过程中，通过将每个超像素中的单个像素或像素块超像素进行重新分配来优化之前的超像素分割效果，如果新的分配可以增加目标函数的值，则接受此次分配的更改.受参数超像素率的影响，该方法会对某些帧执行超像素终止或分裂操作，即为了保持超像素的数量随时间恒定，在对目标函数值的影响最低的情况下，通过从一个超像素中分离出一个部分，来为终止的超像素创建一个新的超像素.

这类方法因为没有考虑对象移动因素，当场景中存在快速移动的对象时可能会失效，不能有效地解决移动对象的时间一致性问题.

2.2.2 超体素方法

针对上文提到的GBH方法在计算过程中需要访问整个视频的问题，Xu等[31]对其进行了扩展，以流媒体的方式来处理任意长的视频同时保持层次分割.该方法将时间马尔可夫假设应用于视频流重叠块的分割，在分割过程中该方法只需要一个子帧，并允许在任何给定时间内将少量帧加载到存储器中.

Yi等[32]提出基于视频流形均匀细分的内容敏感超像素生成方法，并通过扩展内容敏感超像素来处理长视频.该方法将输入视频映射到嵌入R6中的三维流形，利用三维流形的体积元素可以很好地度量视频中的内容密度的优势，通过类劳埃德的分裂合并方案来计算三维流形上的均匀细分，从而生成视频的内容敏感超像素.

2.2.3 时间一致性超像素方法

Alex等[33]首次提出生成时间一致性超像素的方法，该方法基于文献[46]中的TurboPixels超像素方法，使用光流信息传送超像素中心点来初始化后一帧的种子点，进而生成具有时间一致性超像素.文献[46]中提出的TurboPixels超像素算法使用水平集将均匀分布的种子点生长为非重叠的超像素.为了得到时间一致性超像素，文献[33]首先使用TurboPixels算法提取第一帧的超像素，然后利用Lucas-Kanade算法计算连续帧之间每个像素点的运动向量.计算每个超像素包含的所有像素点运动向量的加权平均值，其中越接近超像素中心其权重越大，最后根据计算得到的平均向量将每个超像素中心映射到下一帧，以此来初始化下一帧初始种子点进而生成超像素分割.对视频中所有帧重复上述过程，获得整个视频的时间一致性超像素分割结果.

Liang 等[34]应用了类似文献[33]的传送方法，提出了一种基于部分随机游走算法[47]和时空信息的视频超像素分割方法.该方法首先使用延迟随机游走算法[48]获得第一帧的初始种子点，这些种子点被置于规则的矩形网格上，且由用户指定初始种子点数量，然后基于种子点执行融合了拉普拉斯优化矩阵的PARW分割算法生成初始超像素分割，并通过调整初始种子点的位置使超像素边界与物体边缘更加贴合，最后再次执行PARW分割算法生成最终的超像素分割，并通过光流传播超像素中心以初始化下一帧的种子点.重复此分割-传播-分割过程生成视频的时间一致性超像素分割.

Chang等[35]扩展了SLIC超像素算法，构建时间一致性超像素的生成模型.该模型的每个像素用五维特征建模：三通道颜色和二维位置.这个超像素模型在已知方差的高斯分布下，利用混合模型对单个特征进行聚类来生成超像素.在为第一帧生成超像素后，通过光流信息初始化的高斯过程来模拟帧与帧之间的超像素移动，并基于双边核对运动矢量进行细化.为了解决相邻帧间结构变化的问题，Chang等提出拆分，合并和切换操作，拆分即一个超像素可以分成几部分形成几个标签不同的超像素，合并则是几个不同的超像素合在一起生成一个超像素，切换就是改变超像素的标签.仅当新的分割结果增加联合对数似然函数的值时，才对初始分割执行操作生成新的分割.

Reso等[36,37]介绍了一种混合聚类方法，利用混合聚类策略对多维特征空间执行能量最小化聚类，它将文献[38]的五维特征空间分成全局颜色子空间和多个局部子空间.此外，它引入了基于新轮廓演化的策略以确保生成的超像素具有时间一致性.Reso等采用包括多个连续帧的滑动窗口将帧分组为不可变的过去帧和可变的当前帧以及未来帧，虽然未来帧可以适应视频量的变化，但过去帧是不可变的且试图保留被分配的颜色聚类.滑动窗口方法还可以产生短延迟流并具有处理任意长视频序列的能力.文献[36]通过像素方向的前向光流传播超像素中心标签来完成分割传播，而文献[37]使用像素方向的反向光流查找前一帧中的超像素标签来优化分割.后一种方法产生更稳定的分割结果，因为它同时传播超像素的相对位置和形状以保持超像素的一致性.为了处理视频中的结构变化，两种方法都依赖于像素中包含的像素的数量.前者使用线性假设预测正负增长，而后者设置最小和最大阈值以识别需要终止或分裂的超像素从而控制超像素的大小.

尽管文献[33-37]的时间一致性超像素方法可以基于运动信息跟踪对象，但是需要利用光流算法来估计每个超像素的运动向量.一方面获取所有像素的稠密光流向量需要高的计算复杂度，另一方面上述方法没有给出解决遮挡问题的有效方案，如表1所示.

表1 时间一致性超像素方法

Table 1 Temporal superpixels methods

文献光流时间一致性遮挡方 法Alex[33]稠密√×利用光流将前一帧的每个超像素中心映射到下一帧,作为下一帧的初始种子点进而执行超像素分割Liang[34]稠密√×融合拉普拉斯矩阵来优化PARA算法生成超像素分割,通过光流传播种子点来保持时间一致性Chang[35]稠密√√使用光流信息初始化超像素的运动矢量,然后基于双边核来细化运动矢量Reso[36]稠密√√执行K-means算法来分配超像素标签,在计算每个超像素的平均颜色时采用时间滑动窗口,该窗口包含过去帧,未来帧及当前帧Reso[37]稠密√√基于轮廓构建EM框架对超像素边界处的像素执行优化,并利用光流信息反向传播超像素标签来初始化新帧,同时传播超像素的相对定位和形状Lee[38]稀疏√√从块到像素级别分层次细化每个区域的超像素标签,在每个级别,使用代价函数强制执行轮廓约束Lee[39]稀疏√√通过相邻超像素以及目标超像素的块匹配距离构造邻近加权块匹配,并使用由颜色,空间,轮廓和时间一致性项组成的代价函数来约束边界像素的超像素标签的更新Reso[40]稠密√√使用加权平均光流传播整个超像素来随时间保持超像素分割的形状,同时检测被遮挡的超像素和被遮挡的图像区域

Lee等[38]提出了轮廓约束超像素(CCS)算法，该算法通过使用光流算法传送前一帧的超像素标签来初始化当前帧的超像素标签，因而可以一致地标记连续帧中的相同区域.Lee等首先在规则网格中初始化超像素区域，然后从块级别到像素级别分层次地细化每个区域的超像素标签，在每个级别，使用成本函数来明确地执行轮廓约束，如果在它们之间存在对象轮廓，则两个相邻区域应该属于不同的超像素.为了使超像素边界与对象轮廓兼容，Lee等提出了轮廓模式匹配的概念，并构造了包括轮廓约束的目标函数.此外，Lee等通过扩展CCS算法生成用于视频处理的时间一致性超像素，使用光流传输前一帧中的超像素标签来初始化后续帧中的超像素标签，然后执行时间一致性超像素标记，使超像素在时间上一致，并与对象轮廓兼容.

Lee等[39]提出了一种基于邻近加权块匹配(TS-PPM)的时间一致性超像素算法，该算法通过考虑相邻超像素以及目标超像素的块匹配距离构造邻近加权块匹配(PPM)，来稳健地估计超像素的运动矢量.在每帧中，通过使用PPM运动向量传递前一帧的超像素标签来初始化当前帧的超像素分割，然后基于成本函数更新边界像素的超像素标签，该成本函数由颜色、空间、轮廓和时间一致性项组成.最后执行超像素分割、合并和重新标记操作，以规范超像素尺寸并减少不正确的超像素标签.

尽管文献[38,39]通过稀疏地执行块匹配来估计每个超像素的运动向量降低了计算复杂度，但是没有有效地解决遮挡问题.

Reso等[40]提出了一种处理结构变化的新方法，该方法建立轮廓演化期望最大化框架，利用有效的标签传播方案来促进超像素形状的保持及其随时间的相对定位，从而精确地检测在超像素传播到新帧期间的遮挡并去除遮挡边界.该方法通过将传播的超像素的重叠部分分类为被遮挡或遮挡区域，获知实际遮挡边界所在的位置，这能够终止被遮挡的超像素并创建新出现的超像素.另外，Reso等通过对超像素遮挡区域的进一步优化来提升超像素与视频场景中存在的光流的一致性.

文献[40]有效解决了由对象和自遮挡引起的视频体中的结构变化问题，但其计算稠密光流向量来保持超像素时间一致性的做法增加了计算复杂度.

2.3 评测指标

时间一致性超像素的评价是该领域研究的重要内容之一，目前衡量算法的评价指标可大致分为：3D欠分割错误率指标[41]、3D分割准确度指标[41]、边界召回距离指标[35]、紧凑度指标[49]、时间范围指标[35]、标签一致性指标[35]、解释方差指标[41]、面积方差指标[50].

2.3.1 3D欠分割错误率(3D UE，3D Undersegmentation Error)

该指标首次由文献[41]提出，是用来衡量超像素边界与真值边界贴合的程度，将真值分割(ground truth，通过手工分割得到)的面积和有部分与其重叠的所有超像素的并集进行比较，分割外超像素的面积越大，分割误差就越高.形象地说，它是超像素区域“溢出”真值区域边界的比例.定义如下式所示：

(1)

其中，gm是真值分割，sn是超像素分割结果，N是超像素总数，sn|sn∩gm≠φ表示超像素分割sn与真值分割gm没有重叠，|·|表示分割的数量.

2.3.2 3D分割准确度(3D SA，3D Segmentation Accuracy)

该指标也是由文献[41]提出，表示正确标记的超像素数量占真值分割数量的比例，该指标越高说明超像素分割与真值分割越接近.定义如下式所示：

(2)

其中，M是真值分割的数量，Nm表示超像素标签与真值分割标签一致的集合.

2.3.3 边界召回距离(BRD，Boundary Recall Distance)

文献[35]提出了边界召回距离，它用来衡量真值分割中与下一个边界的平均距离.与2DBR[45]不同，BRD不需要用户选择固定阈值.对于每帧k，计算如下：

(3)

其中，Sb,gr,k和Sb,seg,k分别表示真值分割和超像素分割的边界像素集合.d(i,j)表示两个像素点的欧式距离.

2.3.4 紧凑度(CO，Superpixel Compactness)

文献[49]中提出使用超像素紧凑度作为基准指标，该指标用来衡量超像素的紧密度，它是通过加权超像素n的等周商Qn(如文献[50]中所定义)和相对超像素大小计算的，如下所示：

(4)

2.3.5 时间范围(TEX，Temporal Extent)

该指标在文献[35]中引入，通过计算时空分割的平均持续时间来评估随时间跟踪区域的能力.通过结合3DUE或3DSA来使用此指标，它提供了一个合适的度量来判断超像素分割在视频体中显示的时间一致性的程度.该指标仅描述超像素是否跨越了对象边界(真值分割所定义的).但该指标完全忽略其时间一致性或其在对象边界内的相对位置，为了评测这种类型的时间一致性，需使用文献[35]中提出的标签一致性指标.

2.3.6 标签一致性(Label Consistency)

该指标度量超像素流与原图像移动的一致性，并惩罚超像素形状以及超像素组中的任何时间不一致性.它利用光流信息将分割帧的超像素标签传送到下一帧，并确定传送的标签与算法生成的分割之间的一致像素数.标签一致性表示为一致的像素数与所有帧上平均每帧的像素总数之比.

2.3.7 解释方差(EV，Explained Variation)

文献[51]提出了EV指标来评价超像素分割，它是一种与人无关的度量，不易受到标注者感知变化的影响.它显示过分割作为较低细节的表示方式，它如何来表示原始图像，文献[41]首次将其扩展到视频域，计算方式如下：

(5)

2.3.8 面积方差(VoA，Variance of Area)

文献[35]指出，超像素应是局部的，这样才是有意义的表示方式，随着超像素的增大，会失去代表性.因此，所有帧的超像素大小应该大致相等，为了度量这一性质，文献[50]提出VoA指标.对于第k帧，计算如下：

(6)

3 时间一致性超像素的应用

时间一致性超像素作为新的视频表示方式，使用更丰富(基于区域)的特征集，有效地提高了视频分析和处理任务的后续步骤的计算效率，将视频用时间一致性超像素表示已成为计算机视觉领域许多应用所依赖的预处理步骤.

视频对象分割视频分割技术利用时间一致性超像素来获得时间相干性信息.文献[11]首先使用文献[46]提出的超像素方法将视频帧分割为时间一致性超像素，然后将其作为输入生成视频分割.超像素的使用大大降低了计算复杂度和内存使用，使视频分割算法能够运用到更长的视频.文献[52]提出一种基于超像素的3D时空图形切割方法，该方法将移动对象分割视为对时空域中图像超像素的分组，以此来提取移动前景对象.文献[53]通过使用谱聚类形成超像素分割来代替原始像素数据进行无监督视频分割，分割的超像素具有的时间一致性、时空运动特征、形状相似性等特性，能提高算法运行性能以及分割质量.文献[54]提出基于谱聚类的视频对象分割技术,该技术扩展李等[55]的超像素算法将光流向量包含到特征向量，以得到视频中每一帧超像素之间的时空关系，进而执行视频分割.文献[40]将时间一致性超像素分割作为基础分割进而执行交互式视频分割，时间一致性超像素的准确性以及高效性有利于实现高质量的最终分割结果且可大大减少用户等待时间.文献[13]提出一种基于时间一致性超像素视频表示方式的半监督视频分割方法，该方法利用时间一致性超像素跨时间跟踪同一对象在不同视频帧中的相同部分，以此来为视频中的运动对象构造具有一致的运动模式、相似的外观和紧密的时空关系的超轨迹，进而执行半监督视频分割.

视频显著性检测如果将图像显着性检测技术独立地应用于视频中的每个帧，则所得到的显着性图存在在时间上不兼容的情况，而时间一致性超像素来获得时间上兼容的映射.文献[15]提出一种基于超像素的视频显著性检测时空特征模型，该模型基于视频帧的超像素表示，在超像素级别和帧级别分别提取运动直方图和颜色直方图作为局部特征和全局特征.然后，结合超像素的运动显著性和时间显著性预测及调整方案来度量超像素的时间显著性，并通过评估超像素的全局对比度和空间稀疏性来度量超像素的空间显著性.文献[16]提出基于超像素级别轨迹的时空显著性检测模型，通过输入视频生成的时间一致性超像素来得到超像素级的运动轨迹，并将其作为初始估计进而执行显著性检测.文献[56]针对运动复杂、场景复杂的无约束视频，提出一种时空显著性模型，该模型首先对视频帧的超像素分割结果进行特征提取，得到运动直方图和颜色直方图并将其作为显著性度量的特征，然后构造超像素级图来测量超像素的运动显著性，进而生成时空显著性图.文献[57]提出一种基于交叉帧元胞自动机的视频显著目标检测方法，该方法用超像素来表示给定的视频帧，根据帧内和相邻帧之间的外观相似性和时间相干性来构造显著性传播网络，并通过外观特征和运动特征的融合对其进行初始化，然后利用元胞自动机在超像素之间传播显著性来迭代细化显著性图.文献[18]提出一种视频显著目标检测模型，该模型以时间一致性超像素为基础，提取颜色梯度和运动梯度并以此得到超像素级的时空显著性和时间一致性信息，进而识别视频中的显著区域.

时间一致性超像素还可以应用在其他视频处理任务，Cai等[58]将其应用到视频对象跟踪，通过将目标分割成几个超像素来利用物体的内部几何结构信息进行对象跟踪.Yudistira等[59]通过在运动空间中引入运动超像素并跟踪超像素中心来获得时间信息并将其用于视频分类和识别.Gangapure等[60]提出一种适用于实时监控任务的基于超像素的因果多传感器视频融合算法.

4 结 语

本文介绍了时间一致性超像素的发展现状，对近年来具有代表性的方法进行了着重分析.时间一致性超像素是一种良好的视频表示方式，是视频处理和计算机视觉领域的一个重要预处理工具.但由于分割场景的复杂性，现有的时间一致性超像素还存在一定的局限性，至今尚未出现能兼顾分割质量和效率的时间一致性超像素生成方法.

时间一致性超像素依赖于超像素，超像素分割质量直接影响时间一致性超像素的分割效果；时间一致性超像素通过光流信息来保持时间一致性，而当视频中有遮挡时光流不稳定，且稠密光流比较耗时.综上所述，目前关于时间一致性超像素的研究主要包括以下几个方面：降低提取光流信息的计算复杂度，提高算法效率[38,39]；结合颜色和轮廓信息，提高分割准确率[39]；约束保持超像素形状，检测及去除遮挡[40].未来的研究可以考虑以下几点：

1)改进轮廓特征提取方法.由于轮廓信息用于约束超像素的分割，轮廓信息直接影响分割的准确性，完整且有效的轮廓信息有助于提升分割准确性.

2)优化光流信息.在视频的超像素分割过程中，依靠光流信息来估计像素的运动.将视频看成一个整体，考虑视频的所有帧，生成视频的整体光流图，可以更准确的估计像素运动矢量.

3)完善评测指标.视频超像素的分割结果要兼顾准确性和时间一致性.现有的评测指标大多针对分割准确性，而准确性高的分割，其时间一致性不一定高.进一步研究像素运动矢量，提出更加准确的时间一致性测评指标.

4)扩展视频超像素的应用范围.现有的方法具有各自的优势与不足，可针对特定问题，选择合适方法达到最优效果.