陈秋凤，申群太

（1. 福建农林大学 计算机与信息学院，福建 福州 350002; 2. 中南大学 信息科学与工程学院，湖南 长沙410083）

抠图是按照不透明度将感兴趣物体，从图像或视频序列中精确分离出来的一种图像处理技术[1-2]。抠图是一个高病态问题，需要用户提供一定的标注信息进行求解。目前的单帧抠图算法都要求用户输入的标注信息完全正确，并采用大数值的输入控制参数，以迫使输出值与用户标注值严格相同[3-12]。然而过强的输入约束，使得信息传播只与标注区域的边界相关，传播距离有限；在多层抠图算法中[13]，通过超像素来构建不同层级的图像，虽能够提高算法运算速度，但受超像素预分割精度的影响，高层计算出的结果在向下层传递标注时也会造成错误的初始值。而视频抠图是单帧抠图在图像序列流上的扩展[14-18]，帧间标注信息的传递尤为重要。目前视频抠图多数采用半自动标注的方式，通过帧间传播策略将关键帧上的标注信息依次向后续帧传递。虽有学者[15,18]利用光流信息提高了帧间连续性，但依然采用的是硬约束的方式，因此要求传播产生的三分图对前景边界有良好的包围性并严格正确，这使得后续帧的三分图产生过程复杂，影响了算法的可扩充性和快速性。针对三分图标注的产生方法，不少学者也作了进一步的研究，但仍然是建立在初始标注完全正确的基础上[19-20]。

综上可知，传统算法采用的硬约束方式使得抠图效果严重依赖于所采用标记的准确性，对用户输入要求高。为此，本文在随机游走算法基础上，提出了软约束随机游走算法(soft-constrained random walk, SCRW)，使得输入控制矩阵能够根据图像颜色分布特性进行自适应调整。

1 随机游走分割算法

随机游走是一种具有马尔科夫链性质的特殊布朗运动，在给定的图和一个出发点上，信息以一定的概率随机地移动到邻居节点上。借助电势理论，Grady[21]指出图像分割过程实际上是求解带边界条件的Dirichlet问题。首先建立一张自然图像对应的无向图模型，节点表示图像中的像素点，表示连接两个节点的边，为相似度矩阵，表示节点 i 与节点的相∑似度，定义节点的度矩阵，其对角元素为。给定有个像素的数据集，图像分割的目标是将数据集分成类。设为用户预先指定的种子点集(每一类至少有一个已标注的种子[点)，]为未标注点集，则原数据集可表示为。从每个未标注点出发，分别计算该未知点到类标注点的首达概率，并根据最大概率将该点划分到相应的类别，从而实现图像的分割。记图的拉普拉斯矩阵为 L=D-W，则

由文献[21]知，随机游走分割算法的Dirichlet问题也可写成两顶点概率差值的加权和形式：

2 带输入控制的随机游走抠图算法

2.1 目标函数规则化约束与输入控制

在传统双层抠图中，其求解的目标函数不但要求两近邻像素点间的值最大程度地符合建立的图模型，保持局部相似性，也要求输出值与原始给定值相一致[3-12]。因而其目标函数通常包含有平滑项和数据项两个部分：

结合原始的随机游走算法，将传统双层抠图算法扩展为多图层抠图，像素点到类种子的首达概率定义为第个图层的不透明度，并与式(3)的相区别，此处为每个点取不同的输入控制参数，将抠图目标函数转化成带规则化输入信息约束的扩展Dirichlet问题，则

1)标注信息从已知区域向未知区域扩散时，未知区域只能接受已标注区域的边界信息，扩散过程只依赖于局部相似关系建立的图模型，而与已知区域内部的其他信息无关。尤其是标注信息不足时，局部模型的小窗口特性限制了输入信息的传播距离。

2.2 输入控制参数 取小值时转移概率分析

将式(4)写成矩阵形式，则有

由文献[22]可知，式(8)、式(9)正是部分吸收随机游走算法(partial absorption random walk,PARW)的基本形式，故为吸收概率矩阵，表示信息在节点 i 的自吸收概率，表示节点 i 的信息被近邻节点吸收的概率。根据式(8)、式(9)的分析，可得到结论1和结论2。

由于本文所提带软性约束条件的随机游走SCRW与部分吸收式随机游走算法PARW本质上是相同的，此时图中节点 i 到节点的转移概率为

3 输入控制矩阵设计

3.1 信息流扩散与图像局部模型

在非归一化图模型中，若各点的输入控制参数取为相同的值，即(为常量)时，图像点i 的自转移概率为，随单调递减。由于在图像边界内部像素点间相似度高，节点在边界内的值比边界处大，导致在边界内的吸收概率低于边界，当信息流到边界处时将会被节点高概率地吸收，从而防止标注信息的扩散超过边界。非归一化矩阵之所以能保持信息大部分在边界内被吸收，主要得益于图结构上各节点度的差异性。

根据图像特性[23]，在围绕图像点 i 的窗口中，可将前景颜色和背景颜色的关系分为4种模型：

2)点-线模型：前景或是背景其中之一退化为点模型，在窗口内取值为常数，不妨设前(景为)常量，背景呈线性，则、，代入线性组合公式得

3.2 局部自适应输入控制矩阵设计

式中：t 为预先设定的阈值，参考文献[23]取值为0.002 5。式(12)表示转换空间中方差大于阈值t的维数。

4 单帧图片抠图

为了提高算法的快速性，单帧抠图采用双层的形式。首先对图像进行SLIC超像素[24]分割，构建基于超像素的图模型，对初始的用户输入进行信息扩散得到高层抠图结果，接着将高层结果作为低层抠图的输入标注信息，在基于像素的图模型上进行扩散，求得细化后的结果。本文在高层和低层都采用具有软约束的随机游走算法SCRW，二者的区别在于图模型的构造和控制矩阵H的设计上。

在低层中，图模型按照传统的CF算法[10]建立，相似度函数为

5 视频抠图

由于视频抠图处理数据量大，一般无法对每帧图像进行标注，但图像序列间具有连续性与相似性，充分利用图像的帧间信息可以获得单张图像不具备的特征。本文在单帧双层SCRW算法的基础上，采用软硬两种约束相结合的方式进行视频抠图。图1为视频抠图的示意图：左侧为输入的第帧、第 i 帧图像及相应的三分图区域(背景B，前景F，未知区域U)。连续两帧图像间的信息传导有两种：光流映射与流形最近邻映射。

首先计算图像的前向与后向运动向量[26-27]流映射到当前帧，并对其进行形态学操作去除部分杂点，确保新产生的三分图的准确性。而后对图像进行超像素划分进行高层SCRW运算，将已知区域向未知区域扩散得到初步抠图结果。与式(13)不同，此时具有边连接的两超像素相似度的计算中包含了前向、后向光流场向量：

式中：Fk为颜色特征；Fl为运动向量特征，取值为

上述FLANN搜索特征中未加入光流向量是因为不同帧间的光流特征不具有可比性。与传统视频抠图要求三分图密实围绕前景物体、宽度较窄不同，本文只需要勾画前景与背景的大致区域，即只需要前背景的稀疏输入，因而未知区域的范围较宽。然而未知区域通常包含复杂的图像细节，如毛发、孔洞等，且由于图像运动造成的前景物体遮挡、新增前景等原因，当前帧未知区域中的点与前一帧的流形匹配点有可能差别较大，置信度低。设为当前帧中的点与其前帧最优匹配点间的欧式距离，对向量取阈值，丢弃距离大于的点则得到流形约束图。此时除了式(11)的两种输入控制参数外，流形约束对应的输入控制矩阵设计为

1)用光流法计算(视频序列)中每一帧的前向、后向光流运动向量；

7)判断视频是否处理完毕或到预定处理帧数，否则转到2)。

6 实验结果

实验的运行环境为：Intel Core i3双核3.3 GHz CPU，编程环境为Matlab 2016。对比算法有CF[10]、LB[11]、KNN[12]抠图算法。由于 CF 算法在层数大于5时，程序无法正常运行，因此取层数level=1及level=5两种水平下的结果与本文算法进行对比，文中超像素数取1 000。实验中定量分析图片源于抠图标准网站http://www.alphamatting.com[28]。

6.1 单帧抠图实验结果与分析

图2 全局输入控制参数、 的影响Fig. 2 Influence of global input control parameters,

2)容错性

图3是不完全正确标注情况下，传统CF算法和本文所提SCRW算法的容错性比较。在图3(b)中，白色画线为前景标注，黑色画线为背景标注，中间圆圈区域内，用户错误地将中间背景布标注为前景。图3(c)的传统CF抠图算法，因为采用为大值的硬性约束，输出严格遵从输入，最终结果仍然将中间的背景布抠选了出来；而在图3(d)中，因为SCRW采用为小值的软性约束，各节点局部自适应的设计使得输入信息能够根据图像特征进行自适应扩散，可对一些非正确的输入进行校正，使其符合图像内容，因此本文算法的容错性更强。

图3 容错性比较Fig. 3 Comparison of fault tolerances

3)定量比较

在图4(a)中，三分图1是原始三分图，三分图2～三分图5是原三分图的未知区域向外扩展10、15、20、25个像素点而得，笔画式标注则是手动标注(白色前景，黑色背景)，图4(a)的用户标注信息从左至右依次减少。图4(b)、(c)为各算法在不同的用户标注下的MSE误差及运算时间。由图4(b)知，在三分图比较紧凑的情况下，未知区域中的点距离已知区域近，不需远距离的信息传播就能获得引导信息，CF、LB算法的MSE误差反而比较小；但随着用户标注区域的减少，CF、LB算法由于缺乏远距传播，未知区域中的部分点得不到引导信息，产生了较大的误差，虽然CF算法随着降采样水平的增高，也具有一定的远距传播能力，但其过强的输入控制使高层中不够准确的结果在低层中产生误扩散，故其MSE误差在高level的情况下反而更大；KNN算法虽采用非局部近邻，但其流形近邻的搜索特征包含空间信息，传播距离也有限；而本文算法的高层远距离传播及低层细节恢复能力使得算法的整体误差最小，尤其是在用户输入信息不够充分的情况下能够取得更好的结果。在图4(c)中，CF算法在level=5时的运算时间最短，但其相应的误差最大，是以牺牲准确度来降低运算时间；除此之外，随着未知区域的增加，各算法的运算时间出现不同程度的增加，但本文算法的增量最小，运算时间基本在10 s左右。

图4 不同用户输入下各算法准确率及运算时间对比Fig. 4 Comparison of algorithm accuracy and operation time with different user inputs

6.2 视频抠图实验结果与分析

如图5所示，是Amira视频第79帧到第82帧的各算法运行结果。图5(b) 的三分图为前帧通过光流匹配得到的，图5(a)前背景边界线与图5(b)中的三分图对应。由图5(a)知，随着前景图像的运动，匹配的三分图虽然大致划分了前景背景区域，但并没有很好地贴近前景边界，虽然图5(d)中的高层软约束SCRW能够增加输入信息的远距传播能力，但因前景物体与背景的颜色存在一定的相似度，因此Amira图像的灰色外套及眼部没有完全地被抠选出来(图中箭头所示)。在图5(e)中，由于CF算法的局部窗口作用会使得算法在确定的前景和背景间平滑过渡，未知区域中的前景物体出现了半透明的抠图结果。本文所提出的带流形匹配的SCRW算法由于存在三分图和前帧值传递的软约束，能在较大未知区域中提供引导信息，因此能够取得时空更加一致的抠图结果。

图5 Amira视频序列抠图结果Fig. 5 Matting results of Amira video sequence

7 结束语

本文针对抠图算法标注准确性问题，根据带约束随机游走算法信息流的传播特性，提出了一种带软性约束的随机游走算法，并将其应用到单帧图像抠图和视频抠图中。实验结果表明，输入控制参数对标注信息的扩散距离具有直接的影响，软性约束下随机游走具有更加优良的容错特性，所提算法避免了视频抠图中获取三分图标注的繁杂计算，为提高抠图算法的精度提供了新的思考方向。但本文算法在大尺寸图像和视频上运行缓慢，对边界模糊图像的处理效果不够理想，如何进一步提高算法的快速性和复杂图像的处理能力仍将是未来努力的方向。