第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sept.2019 D0:10.11992/tis.201809014 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20181227.1144.004html 局部自适应输入控制的随机游走抠图 陈秋凤2，申群太2 (1.福建农林大学计算机与信息学院，福建福州350002；2.中南大学信息科学与工程学院，湖南长沙 410083) 摘要：针对传统性抠图算法中，非完全正确用户标注及不精确超像素分割造成的信息误扩散，以随机游走算 法为基础，提出带软性约束的抠图算法。通过对扩展Dirichlet问题的推导，指出带软约束的随机游走与部分自 吸收随机游走概率的关联性。以吸收概率为指导，在传统相似扩散所构建的图模型上，根据局部窗口内特征矩 阵的秩与方差设计了输入控制矩阵，使得信息扩散的过程能够跟随图像的局部特征进行自适应扩散。最后将 软约束随机游走应用到单帧双层抠图及视频抠图中。实验表明，所提算法具有信息远距传播能力和良好的容 错性能，尤其在用户标注不够充分的情况下能够取得更加优良的抠图结果。 关键词：抠图：视频抠图：随机游走；软性约束；吸收概率；局部模型；输入控制：自适应 中图分类号：TP391文献标志码：A文章编号：1673-4785(2019)05-1007-10 中文引用格式：陈秋凤，申群太.局部自适应输入控制的随机游走抠图.智能系统学报，2019,14(5)：1007-1016. 英文引用格式：CHEN Qiufeng,SHEN Quntai..Random-walk matting with local adaptive input control[J.CAAI transactions on intelligent systems,2019,14(5):1007-1016. Random-walk matting with local adaptive input control CHEN Qiufeng 2,SHEN Quntai? (1.College of Computer and Information Sciences,Fujian Agriculture and Forestry University,Fuzhou 350002,China;2.School of Information Science and Engineering,Central South University,Changsha 410083,China) Abstract:In traditional image-matting algorithms,incomplete user labeling and inaccurate super-pixel segmentation lead to the incorrect propagation of information.To solve this problem,we propose the use of soft constrained matting based on a random-walk algorithm.Through the derivation of the extended Dirichlet problem,we identify the relation- ship between a random walk with soft constraint and the probability of a partial self-absorption random walk.Guided by the absorption probability,an input control matrix is designed according to the rank and variance of the feature matrix in the local window.This is performed via a graph model that was constructed using traditional similarity diffusion such that the process of information diffusion could follow the local image features to realize adaptive diffusion.Finally,we applied the soft constrained random walk to single-frame two-layer image and video matting.The experimental results reveal that the proposed algorithm can transmit information over long distances and has good fault tolerance.In addition, it can achieve better image matting results,particularly in cases wherein user labeling is insufficient. Keywords:matting;video matting;random walk;soft constrained;absorption probability;local model;input control; adaptive control 抠图是按照不透明度将感兴趣物体，从图像 术。抠图是一个高病态问题，需要用户提供一 或视频序列中精确分离出来的一种图像处理技 定的标注信息进行求解。目前的单帧抠图算法都 要求用户输入的标注信息完全正确，并采用大数 收稿日期：2018-09-11.网络出版日期：2018-12-27. 基金项目：国家自然科学基金项目(61473318,60974048). 值的输入控制参数，以迫使输出值与用户标注值 通信作者：陈秋凤.E-mail:chengiufeng0204@l26.com. 严格相同。然而过强的输入约束，使得信息传
DOI: 10.11992/tis.201809014 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20181227.1144.004.html 局部自适应输入控制的随机游走抠图 陈秋凤1,2，申群太2 （1. 福建农林大学 计算机与信息学院，福建 福州 350002; 2. 中南大学 信息科学与工程学院，湖南 长沙 410083） 摘 要：针对传统性抠图算法中，非完全正确用户标注及不精确超像素分割造成的信息误扩散，以随机游走算 法为基础，提出带软性约束的抠图算法。通过对扩展 Dirichlet 问题的推导，指出带软约束的随机游走与部分自 吸收随机游走概率的关联性。以吸收概率为指导，在传统相似扩散所构建的图模型上，根据局部窗口内特征矩 阵的秩与方差设计了输入控制矩阵，使得信息扩散的过程能够跟随图像的局部特征进行自适应扩散。最后将 软约束随机游走应用到单帧双层抠图及视频抠图中。实验表明，所提算法具有信息远距传播能力和良好的容 错性能，尤其在用户标注不够充分的情况下能够取得更加优良的抠图结果。 关键词：抠图；视频抠图；随机游走；软性约束；吸收概率；局部模型；输入控制；自适应 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2019)05−1007−10 中文引用格式：陈秋凤, 申群太. 局部自适应输入控制的随机游走抠图 [J]. 智能系统学报, 2019, 14(5): 1007–1016. 英文引用格式：CHEN Qiufeng, SHEN Quntai. Random-walk matting with local adaptive input control[J]. CAAI transactions on intelligent systems, 2019, 14(5): 1007–1016. Random-walk matting with local adaptive input control CHEN Qiufeng1,2 ，SHEN Quntai2 (1. College of Computer and Information Sciences, Fujian Agriculture and Forestry University, Fuzhou 350002, China; 2. School of Information Science and Engineering, Central South University, Changsha 410083, China) Abstract: In traditional image-matting algorithms, incomplete user labeling and inaccurate super-pixel segmentation lead to the incorrect propagation of information. To solve this problem, we propose the use of soft constrained matting based on a random-walk algorithm. Through the derivation of the extended Dirichlet problem, we identify the relationship between a random walk with soft constraint and the probability of a partial self-absorption random walk. Guided by the absorption probability, an input control matrix is designed according to the rank and variance of the feature matrix in the local window. This is performed via a graph model that was constructed using traditional similarity diffusion such that the process of information diffusion could follow the local image features to realize adaptive diffusion. Finally, we applied the soft constrained random walk to single-frame two-layer image and video matting. The experimental results reveal that the proposed algorithm can transmit information over long distances and has good fault tolerance. In addition, it can achieve better image matting results, particularly in cases wherein user labeling is insufficient. Keywords: matting; video matting; random walk; soft constrained; absorption probability; local model; input control; adaptive control 抠图是按照不透明度将感兴趣物体，从图像 或视频序列中精确分离出来的一种图像处理技 术 [1-2]。抠图是一个高病态问题，需要用户提供一 定的标注信息进行求解。目前的单帧抠图算法都 要求用户输入的标注信息完全正确，并采用大数 值的输入控制参数，以迫使输出值与用户标注值 严格相同[3-12]。然而过强的输入约束，使得信息传 收稿日期：2018−09−11. 网络出版日期：2018−12−27. 基金项目：国家自然科学基金项目 (61473318, 60974048). 通信作者：陈秋凤. E-mail：chenqiufeng0204@126.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sept. 2019
·1008· 智能系统学报 第14卷 播只与标注区域的边界相关，传播距离有限：在 广=[店…肉表示数据集对第k个类别的首 多层抠图算法中)，通过超像素来构建不同层级 达概率，并将广改写为广=)（吃）门，为已 的图像，虽能够提高算法运算速度，但受超像素 标注的种子点概率，取值为 预分割精度的影响，高层计算出的结果在向下层 店= ∫1，x属于第k类 传递标注时也会造成错误的初始值。而视频抠图 10,其他 是单帧抠图在图像序列流上的扩展41，帧间标 由文献[21]知，随机游走分割算法的Dirich- 注信息的传递尤为重要。目前视频抠图多数采用 let问题也可写成两顶，点概率差值的加权和形式： 半自动标注的方式，通过帧间传播策略将关键帧 (1) 上的标注信息依次向后续帧传递。虽有学者s1 p]-∑- 利用光流信息提高了帧间连续性，但依然采用的 求解可得未标注点的首达概率，即 是硬约束的方式，因此要求传播产生的三分图对 p吃=-LBpM (2) 前景边界有良好的包围性并严格正确，这使得后 续帧的三分图产生过程复杂，影响了算法的可扩 2带输入控制的随机游走抠图算法 充性和快速性。针对三分图标注的产生方法，不 2.1 目标函数规则化约束与输入控制 少学者也作了进一步的研究，但仍然是建立在初 在传统双层抠图中，其求解的目标函数不但 始标注完全正确的基础上920。 要求两近邻像素点间的α值最大程度地符合建立 综上可知，传统算法采用的硬约束方式使得 的图模型，保持局部相似性，也要求输出α值与 抠图效果严重依赖于所采用标记的准确性，对用 原始给定值相一致B。因而其目标函数通常包 户输入要求高。为此，本文在随机游走算法基础 含有平滑项和数据项两个部分： 上，提出了软约束随机游走算法(soft-constrained J=min (3) random walk,.SCRW),使得输入控制矩阵能够根 据图像颜色分布特性进行自适应调整。 式中：为点i的不透明度；d为待求不透明度的 1随机游走分割算法 输入初始值；S为约束集合；入为输入控制参数， 其值越大表示所求α值与原输入的一致性越高。 随机游走是一种具有马尔科夫链性质的特殊 式(3)等号左边第2项可看作针对输入信息的规 布朗运动，在给定的图和一个出发点上，信息以 则化项，入为规则化因子。 一定的概率随机地移动到邻居节点上。借助电势 结合原始的随机游走算法，将传统双层抠图 理论，Grady山指出图像分割过程实际上是求解 算法扩展为多图层抠图，像素点到k类种子的首 带边界条件的Dirichlet问题。首先建立一张自然 达概率定义为第k个图层的不透明度，并与式 图像对应的无向图模型G=(VE),节点V表示图 (3)的λ相区别，此处为每个点取不同的输入控制 像中的像素点，E表示连接两个节点的边， 参数h,将抠图目标函数转化成带规则化输入信 W=[wlna为相似度矩阵，w表示节点i与节点j 息约束的扩展Dirichlet问题.则 的相似度，定义节点的度矩阵D,其对角元素为 d=∑w。给定有n个像素的数据集 -22,-f+2- 12 X={,2,…,x山，图像分割的目标是将数据集X分 式中：a、a表示点i、j在第k个图层的不透明度 成k类。设X,为用户预先指定的种子点集（每一 值；为用户输入的信息或初始值；h:为第i个像 类至少有一个已标注的种子点)，X为未标注点 素点的输入控制参数，其数值的大小与信息的传 集，则原数据集可表示为X=KX⑦从每个未 播距离相关。当k>2时，式(4)为多层抠图；当 标注点出发，分别计算该未知点到k类标注点的 k=2时，式(4)为单纯的前景提取。若将式(1)中 首达概率，并根据最大概率将该点划分到相应的 的首达概率广定义为不透明度a,再与式(4)进 类别，从而实现图像的分割。记图的拉普拉斯矩 行对比，不难发现式(1)的传统随机游走算法少 阵为L=D-W则 了规则化约束项。实际上随机游走分割是将种子 i=j 点看作理想电源，内阻为无限小，即假设入为无 Lii i≠，je2 穷大，从而才能对拉普拉斯矩阵进行拆分，将数 0 其他 据集分成已标注和未标注两个部分求解。而式 式中2表示像素点i的空间近邻集合。令 (3)的传统抠图算法的目标函数也都是将输入控
播只与标注区域的边界相关，传播距离有限；在 多层抠图算法中[13] ，通过超像素来构建不同层级 的图像，虽能够提高算法运算速度，但受超像素 预分割精度的影响，高层计算出的结果在向下层 传递标注时也会造成错误的初始值。而视频抠图 是单帧抠图在图像序列流上的扩展[14-18] ，帧间标 注信息的传递尤为重要。目前视频抠图多数采用 半自动标注的方式，通过帧间传播策略将关键帧 上的标注信息依次向后续帧传递。虽有学者[15, 18] 利用光流信息提高了帧间连续性，但依然采用的 是硬约束的方式，因此要求传播产生的三分图对 前景边界有良好的包围性并严格正确，这使得后 续帧的三分图产生过程复杂，影响了算法的可扩 充性和快速性。针对三分图标注的产生方法，不 少学者也作了进一步的研究，但仍然是建立在初 始标注完全正确的基础上[19-20]。 综上可知，传统算法采用的硬约束方式使得 抠图效果严重依赖于所采用标记的准确性，对用 户输入要求高。为此，本文在随机游走算法基础 上，提出了软约束随机游走算法 (soft-constrained random walk, SCRW)，使得输入控制矩阵能够根 据图像颜色分布特性进行自适应调整。 1 随机游走分割算法 G = (V,E) V E W= [wi j]n×n wi j i j D di = ∑ jwi j n χ = {x1, x2,··· , xn} χ k χM χU χ = [ χ T M χ T U ] k 随机游走是一种具有马尔科夫链性质的特殊 布朗运动，在给定的图和一个出发点上，信息以 一定的概率随机地移动到邻居节点上。借助电势 理论，Grady[21] 指出图像分割过程实际上是求解 带边界条件的 Dirichlet 问题。首先建立一张自然 图像对应的无向图模型 ，节点 表示图 像中的像素点， 表示连接两个节点的边， 为相似度矩阵， 表示节点 与节点 的相似度，定义节点的度矩阵 ，其对角元素为 。给定有 个像素的数据集 ，图像分割的目标是将数据集 分 成 类。设 为用户预先指定的种子点集 (每一 类至少有一个已标注的种子点)， 为未标注点 集，则原数据集可表示为 。从每个未 标注点出发，分别计算该未知点到 类标注点的 首达概率，并根据最大概率将该点划分到相应的 类别，从而实现图像的分割。记图的拉普拉斯矩 阵为 L=D−W，则 Li j = ∑ j wi j, i = j −wi j, i , j, j ∈ Ωi 0, 其他 Ωi 式 中 表示像素点 i 的空间近邻集合。令 p k = [ p k 1 p k 2 ··· p k n ]T k p k p k = [( p k M )T ( p k U )T ] p k M 表示数据集对第 个类别的首 达概率，并将 改写为 ， 为已 标注的种子点概率，取值为 p k i = { 1, xi属于第k类 0, 其他 由文献 [21] 知，随机游走分割算法的 Dirichlet 问题也可写成两顶点概率差值的加权和形式： D [ p k ] = 1 2 ∑ ei j∈E wi j( p k i − p k j )2 (1) p k 求解可得未标注点的首达概率 U ，即 p k U = −L −1 U B T p k M (2) 2 带输入控制的随机游走抠图算法 2.1 目标函数规则化约束与输入控制 α α 在传统双层抠图中，其求解的目标函数不但 要求两近邻像素点间的 值最大程度地符合建立 的图模型，保持局部相似性，也要求输出 值与 原始给定值相一致[3-12]。因而其目标函数通常包 含有平滑项和数据项两个部分： J = min 1 2 ∑n i=1 ∑ j∈Ωi wi j( αi −αj )2 +λ ∑ i∈S (αi −α˜i) 2 (3) αi i α˜i S λ α λ 式中： 为点 的不透明度； 为待求不透明度的 输入初始值； 为约束集合； 为输入控制参数， 其值越大表示所求 值与原输入的一致性越高。 式 (3) 等号左边第 2 项可看作针对输入信息的规 则化项， 为规则化因子。 k k λ hi 结合原始的随机游走算法，将传统双层抠图 算法扩展为多图层抠图，像素点到 类种子的首 达概率定义为第 个图层的不透明度，并与式 (3) 的 相区别，此处为每个点取不同的输入控制 参数 ，将抠图目标函数转化成带规则化输入信 息约束的扩展 Dirichlet 问题，则 D [ α k ] = 1 2 ∑n i=1 ∑ j∈Ωi wi j( α k i −α k j )2 + ∑ i∈S hi ( α k i −α˜ k i )2 (4) α k i α k j i j k α˜ k i hi i k > 2 k = 2 p k α k λ 式中： 、 表示点 、 在第 个图层的不透明度 值； 为用户输入的信息或初始值； 为第 个像 素点的输入控制参数，其数值的大小与信息的传 播距离相关。当 时，式 (4) 为多层抠图；当 时，式 (4) 为单纯的前景提取。若将式 (1) 中 的首达概率 定义为不透明度 ，再与式 (4) 进 行对比，不难发现式 (1) 的传统随机游走算法少 了规则化约束项。实际上随机游走分割是将种子 点看作理想电源，内阻为无限小，即假设 为无 穷大，从而才能对拉普拉斯矩阵进行拆分，将数 据集分成已标注和未标注两个部分求解。而式 (3) 的传统抠图算法的目标函数也都是将输入控 ·1008· 智 能 系 统 学 报 第 14 卷
第5期 陈秋凤，等：局部自适应输入控制的随机游走抠图 ·1009· 制参数1取为大值四，并且每个点的输入控制参 将该式拆开、并写成单个元素的形式为 数值相等。若忽略各算法所构建图模型的差异 du= x1+∑ (8) hi+di 性(，看成相同)，当各抠图算法的输入控制参数 分h+d A→∞时，很容易得知各抠图算法与随机游走分 (9) 割算法具有等价性。 2644 入值是否越大越好？其实不然。因A值取为 由文献[22]可知，式(8)、式(9)正是部分吸收 大值存在以下问题： 随机游走算法(partial absorption random walk, 1)标注信息从已知区域向未知区域扩散时， PARW)的基本形式，故A为吸收概率矩阵，ai表 未知区域只能接受已标注区域的边界信息，扩散 示信息在节点i的自吸收概率，a表示节点i的 过程只依赖于局部相似关系建立的图模型，而与 信息被近邻节点j吸收的概率。根据式(8)、式 已知区域内部的其他信息无关。尤其是标注信息 (9)的分析，可得到结论1和结论2。 不足时，局部模型的小窗口特性限制了输入信息 结论1由于吸收概率矩阵A中的元素在0、 的传播距离。 1之间，且各行加和为1，因此输入信息在图模 2)为了使目标函数值最小，传统算法会迫使 型上的扩散有稳定解，所提供的信息将被图完 α的取值在已知区域和未知区域之间平滑过渡。 全吸收。 当输入的信息不完全正确时，过大的A值也会将 结论2自吸收概率a的大小与输入信息的 错误传递给其他像素，且无法进行自修正。 局部相似扩散距离有关，自吸收概率a:越小，传 针对入取大值存在的问题，以下对输入控制 播距离越远，反之距离越近。 参数h:取小值时的特性进行分析。 由于本文所提带软性约束条件的随机游走 2.2输入控制参数h,取小值时转移概率分析 SCRW与部分吸收式随机游走算法PARW本质 将式(4)写成矩阵形式，则有 上是相同的，此时图中节点ⅰ到节点j的转移概 D[=a'L(a)+(d-y'H(a-) 率为 h h:+d' i=j eeg (5) Pu (10) i≠j -41卧- （h:+d’ 式(10)表明，初始信息有h,/(h+d)的概率停 式中：对角矩阵H=diag(h1,h2,…,hn;a表示第k 留在原节点上，而由w/h+d)概率转移到相邻 个图层的不透明度值；为给定的初值，并将其 节点j,转移到相邻节点的总概率为d,/(h+d)。 分为已知和未知两部分用下标、1表示。矩阵H 3输入控制矩阵设计 对角元素：的大小表明了对原始输入值的遵从 程度。为了达到更远的传播距离和避免不准确输 3.1信息流扩散与图像局部模型 入信息对输出结果的不良影响，本文输人控制参 由上可知，节点的自吸收概率与d、h相关， 数的取值较小，相比于传统抠图算法硬约束下的 在不同类型的图G=(VE)中，信息流的扩散也不 λ值取大值，式（⑤）可以看成一种带软约束的随机 相同。以下将图G=(VE)分为非归一化图模型 游走算法。将式（⑤）求微分得到优化的输出结果为 和归一化图模型两种进行讨论。 a=(L+H)(-Bai+Hd= (6) 在非归一化图模型中，若各点的输入控制参 (La+H)'（-Ba)+(Lu+H)H.a的 数取为相同的值，即H=y(y为常量)时，图像点 当H.取小数值时，(Ln+H)1≈L,式(6)第 i的自转移概率为pa=yy+d),pa随d单调递 一项与式(2)的无约束随机游走一致；第二项与 减。由于在图像边界内部像素点间相似度高，节 输入初始信息心相关，令变换矩阵A=(Lm+H)H 点在边界内的d,值比边界处大，导致p:在边界内 则有 的吸收概率低于边界，当信息流到边界处时将会 A=(Lm+H)广H.= 被节点高概率地吸收，从而防止标注信息的扩散 (L.+)(D.+)(D.+)H= (D.+H,)(D-W+H)'(D.+H)H=() 超过边界。非归一化矩阵H=yl之所以能保持 信息大部分在边界内被吸收，主要得益于图结构 (I-(D.+)W.(D.+)H. 上各节点度d:的差异性。 式(7)等价于A-(Du+H)WnA=(D.+H)H., 而在归一化图模型中，各点的度都为d,信息
λ wi j λ → ∞ 制参数 取为大值[3-12] ，并且每个点的输入控制参 数值相等。若忽略各算法所构建图模型的差异 性 ( 看成相同)，当各抠图算法的输入控制参数 时，很容易得知各抠图算法与随机游走分 割算法具有等价性。 λ 值是否越大越好?其实不然。因 λ 值取为 大值存在以下问题： 1) 标注信息从已知区域向未知区域扩散时， 未知区域只能接受已标注区域的边界信息，扩散 过程只依赖于局部相似关系建立的图模型，而与 已知区域内部的其他信息无关。尤其是标注信息 不足时，局部模型的小窗口特性限制了输入信息 的传播距离。 α λ 2) 为了使目标函数值最小，传统算法会迫使 的取值在已知区域和未知区域之间平滑过渡。 当输入的信息不完全正确时，过大的 值也会将 错误传递给其他像素，且无法进行自修正。 λ hi 针对 取大值存在的问题，以下对输入控制 参数 取小值时的特性进行分析。 2.2 输入控制参数 hi 取小值时转移概率分析 将式 (4) 写成矩阵形式，则有 D [ α k ] = 1 2 (( α k )T L ( α k ) + ( α k −α˜ k )T H ( α k −α˜ k ) ) = 1 2 ([( α k l )T( α k u )T ] [ Ll B B T Lu ] [α k l α k u ] + ··· + ([α k l α k u ] − [ α˜ k l α˜ k u ])T [ Hl 0 0 T Hu ] ([α k l α k u ] − [ α˜ k l α˜ k u ]) (5) H = diag{h1,h2,··· ,hn} α k k α˜ k u l H hi λ 式中：对角矩阵 ； 表示第 个图层的不透明度值； 为给定的初值，并将其 分为已知和未知两部分用下标 、 表示。矩阵 对角元素 的大小表明了对原始输入值的遵从 程度。为了达到更远的传播距离和避免不准确输 入信息对输出结果的不良影响，本文输入控制参 数的取值较小，相比于传统抠图算法硬约束下的 值取大值，式 (5) 可以看成一种带软约束的随机 游走算法。将式 (5) 求微分得到优化的输出结果为 α k u = (Lu + Hu) −1 ( −B Tα k l + Huα˜ k u ) = (Lu + Hu) −1 ( −B Tα k l ) +(Lu + Hu) −1Huα˜ k u (6) Hu (Lu + Hu) −1 ≈ L −1 u α˜ k u A = (Lu + Hu) −1Hu 当 取小数值时， ，式 (6) 第 一项与式 (2) 的无约束随机游走一致；第二项与 输入初始信息 相关，令变换矩阵 ， 则有 A = (Lu + Hu) −1Hu = (Lu + Hu) −1 (Du + Hu) (Du + Hu) −1Hu = ( (Du + Hu) −1 (Du −Wu + Hu) )−1 (Du + Hu) −1Hu = ( I−(Du + Hu) −1Wu )−1 (Du + Hu) −1Hu (7) A−(Du + Hu) −1WuA = (Du + Hu) −1 式 ( 7 ) 等价于 Hu ， 将该式拆开，并写成单个元素的形式为 aii = hi hi +di ×1+ ∑ j,i wi j hi +di ai j (8) ai j = ∑ j,k wk j hi +di ajk, i , j (9) A aii i ai j i j 由文献 [22] 可知，式 (8)、式 (9) 正是部分吸收 随机游走算法 (partial absorption random walk, PARW) 的基本形式，故 为吸收概率矩阵， 表 示信息在节点 的自吸收概率， 表示节点 的 信息被近邻节点 吸收的概率。根据式 (8)、式 (9) 的分析，可得到结论 1 和结论 2。 A α˜ k u α˜ k u 结论 1 由于吸收概率矩阵 中的元素在 0、 1 之间，且各行加和为 1，因此输入信息 在图模 型上的扩散有稳定解， 所提供的信息将被图完 全吸收。 aii aii 结论 2 自吸收概率 的大小与输入信息的 局部相似扩散距离有关，自吸收概率 越小，传 播距离越远，反之距离越近。 i j 由于本文所提带软性约束条件的随机游走 SCRW 与部分吸收式随机游走算法 PARW 本质 上是相同的，此时图中节点 到节点 的转移概 率为 pi j = hi hi +di , i = j wi j hi +di , i , j (10) hi/ (hi +di) wi j/ (hi +di) j di/ (hi +di) 式 (10) 表明，初始信息有 的概率停 留在原节点上，而由 概率转移到相邻 节点 ，转移到相邻节点的总概率为 。 3 输入控制矩阵设计 3.1 信息流扩散与图像局部模型 di hi G = (V,E) G = (V,E) 由上可知，节点的自吸收概率与 、 相关， 在不同类型的图 中，信息流的扩散也不 相同。以下将图 分为非归一化图模型 和归一化图模型两种进行讨论。 H = γI γ i pii = γ/(γ+di) pii di di pii H = γI di 在非归一化图模型中，若各点的输入控制参 数取为相同的值，即 ( 为常量) 时，图像点 的自转移概率为 ， 随 单调递 减。由于在图像边界内部像素点间相似度高，节 点在边界内的 值比边界处大，导致 在边界内 的吸收概率低于边界，当信息流到边界处时将会 被节点高概率地吸收，从而防止标注信息的扩散 超过边界。非归一化矩阵 之所以能保持 信息大部分在边界内被吸收，主要得益于图结构 上各节点度 的差异性。 而在归一化图模型中，各点的度都为 d0，信息 第 5 期 陈秋凤，等：局部自适应输入控制的随机游走抠图 ·1009·
·1010· 智能系统学报 第14卷 流的自转移概率为h:/(h:+do,若各点的输入控制 4)单点模型：前景和背景取为相同常数，即 参数也取为相同的值，则各节点间的自转移概率 I=F=B,为任意常量，这种特殊情况下，自由 都相同。在传统的C℉抠图O算法中，基于像素 度为1，窗口内各点颜色值相同，一般是在图像的 的节点连接度为wc(I,-)(-4)/(+),若窗 连续平滑区域。 口半径为r,经过运算可知各节点的度相等，即 3.2局部自适应输入控制矩阵设计 d=d=(2r+1)2。从w的计算公式可以看出， 记局部窗口内的特征矩阵为G=号1儿 CF算法相当于对原数据进行了0均值的归一化 当前背景颜色取线-线、点-线、点-点及单点模型 操作，归一化丢失了图像各窗口间颜色变化的差 时，由3.1节知颜色特征到α值变换的自由度为 异性，因此若将输入控制矩阵H取为yl,则自转 4、3、2、1,因而相应模型下特征矩阵的秩也为4、 移概率P:为常数，边界内和边界外的节点对信息 3、2、1。矩阵的秩越低，表示特征向量间的相关 流具有相同的吸收概率，信息流由于没有边界吸 性越大，窗口内像素点间具有高的相似度，这使 收特性，将出现误扩散。 得隐含的未归一化前的节点度值山：更大，若图模 因此，在节点度d:相同的归一化图模型中， 型未进行归一化，则不同的d:能够使信息流根据 设计具有边界吸收特性的转移概率，则要求各节 图像特征进行扩散，因而输入控制参数可取为相 点的输入控制参数h:能够根据图像的局部分布 同的值；若图模型进行了归一化，当窗口内的方 特征而变化。以下探讨局部窗口内前背景颜色模 差较小时，局部区域颜色变化平滑，则希望有较 型的分布特征，及相应模型下α值相似变换的自 小的来使得当前节点的自吸收概率低，从而信 由度；并以此为基础来确定h:值。 息流有更大的流动性，反之则，取较大的值。总 根据图像特性)，在围绕图像点i的窗口中， 之，参数：设计的目标是使信息流根据图像的局 可将前景颜色和背景颜色的关系分为4种模型： 部特征得到合适的扩散，即在模型简单颜色平滑 1)线-线模型：前景和背景都是线性变化，则存 区域的扩散程度高，复杂区域的扩散程度低。综 在颜色常量(F1,F2,B1,B2),使窗口中点j的前景和背 上所述.本文采用的：计算公式为 景为F=F1+(1-)F2、B=B1+1-)B2,将F y,G=(V,E)是非归一化图 B,带入抠图前背景耦合公式I,=a,F+(1-a)B,则 hi= h×rank(G)xG=(WE)是归一化图 L=e时F+(1-)F2+(1-B1+(1-)B (11) 由于图像RGB3通道分别符合线性关系，记3×3 式中：、？为全局输入控制常数，为避免过强输 矩阵Q的对应取值为[F+B,F-F,B-B, 入限制作用，一般将其取为小值；rank(G)为特征 则L,与Q的关系改写为 矩阵的秩；：为窗口内颜色方差，整张图像的平 i =I-B2 均方差为云=，∑（σ）}/n。当建立的是非归一的 (1-a1 图模型时，各节点的输人控制参数取相同的 式中1，=，取4ad为Q的第1行， 值，P=y/y1+d),各节点度d,的差异性使得在 则存在4个自由度的相似变换： 未归一化图上的扩散自然具有边界吸收特性：当 aj=a+a++b 建立的是规则化的图模型时，节点度d:取相同的 2)点-线模型：前景或是背景其中之一退化为 值d。对应的自吸收概率为 Pa=hil(hi+di)= 点模型，在窗口内取值为常数，不妨设前景为常 y2×rank(G,)×o:/(y2×rank(G,)×o:+d×) 量，背景呈线性，则F;=F、B,=B+(1-)B, 由于特征矩阵秩rank(G,)的4种取值分别对 代入线性组合公式得 应窗口内颜色的4种分布模型，此时图像上各点 I=a,F+(1-a,)B1+(1-)B2)= 的P:取值实质上是按照线-线、点-线、点-点及 a,(F-B2)+(1-a(B1-B2)+B2 单点4种颜色模型先进行粗略地分段，而后再用 推导可知存在自由度为3的变换： σ：/厅进一步细化而得，这样信息流将会根据图像 aj=alj+a+ar 的局部特性进行自适应地扩散。 3)点-点模型：前景和背景都取值为常数的点 c,与rank(G,)计算方法为：首先对矩阵G:进 模型，即F,=F、B,=B,此时L,=aF+(1-a)B= 行奇异值分解得G:=U∑VT,得到对角线上的奇异 (F-B)α：+B,则自由度为2的变换为 值为[ca2ao,且1>2>>4，则转换 ,=a+a 后的方差为c:=√(c+ca+oa+4)/4,rank(G)的
hi/ (hi +d0) wi j ∝ (Ii −µk) ( Ij −µk ) / ( σ 2 k +ε ) r di = d0 = (2r +1)2 wi j H γI pii 流的自转移概率为 ，若各点的输入控制 参数也取为相同的值，则各节点间的自转移概率 都相同。在传统的 CF 抠图[10] 算法中，基于像素 的节点连接度为 ，若窗 口半径为 ，经过运算可知各节点的度相等，即 。 从 的计算公式可以看出， CF 算法相当于对原数据进行了 0 均值的归一化 操作，归一化丢失了图像各窗口间颜色变化的差 异性，因此若将输入控制矩阵 取为 ，则自转 移概率 为常数，边界内和边界外的节点对信息 流具有相同的吸收概率，信息流由于没有边界吸 收特性，将出现误扩散。 di hi α hi 因此，在节点度 相同的归一化图模型中， 设计具有边界吸收特性的转移概率，则要求各节 点的输入控制参数 能够根据图像的局部分布 特征而变化。以下探讨局部窗口内前背景颜色模 型的分布特征，及相应模型下 值相似变换的自 由度；并以此为基础来确定 值。 根据图像特性 i [23] ，在围绕图像点 的窗口中， 可将前景颜色和背景颜色的关系分为 4 种模型： (F1,F2,B1,B2) j Fj =β F j F1+ ( 1−β F j ) F2 Bj =β B j B1+ ( 1−β B j ) B2 Fj Bj Ij = αjFj +(1−αj)Bj Ij = αj [ β F j F1 + ( 1−β F j ) F2 ] +(1−αj) [ β B j B1 + ( 1−β B j ) B2 ] 1) 线−线模型：前景和背景都是线性变化，则存 在颜色常量 ，使窗口中点 的前景和背 景为 、 ，将 、 带入抠图前背景耦合公式 ，则 。 Q [ F2+B2 F1−F2 B1−B2 ] 由于图像 RGB 3 通道分别符合线性关系，记 3×3 矩阵 的对应取值为 ， 则 Ij 与 Q 的关系改写为 Q αj αjβ F j (1−αj)β B j = Ij − B2 Ij = [ I r j I g j I b j ]T a r i a g i a b i Q 式中 −1 ，取 为 的第 1 行 ， 则存在 4 个自由度的相似变换： αj = a r i I r j +a g i I g j +a b i I b j +bi Fj = F Bj = β B j B1 + ( 1−β B j ) B2 2) 点−线模型：前景或是背景其中之一退化为 点模型，在窗口内取值为常数，不妨设前景为常 量，背景呈线性，则 、 ， 代入线性组合公式得 Ij = αjF+(1−αj) ( β B j B1 + ( 1−β B j ) B2 ) = αj(F− B2)+(1−αj)β B j (B1 − B2)+ B2 推导可知存在自由度为 3 的变换： αj = a r i I r j +a g i I g j +a b i I b j Fj = F Bj = B Ij = αjF+(1−αj)B = (F− B)αj + B 3) 点−点模型：前景和背景都取值为常数的点 模型，即 、 ，此时 ，则自由度为 2 的变换为 αj = a 1 i ˜I 1 j +a 2 i ˜I 2 j Ij = F = B αj 4) 单点模型：前景和背景取为相同常数，即 ， 为任意常量，这种特殊情况下，自由 度为 1，窗口内各点颜色值相同，一般是在图像的 连续平滑区域。 3.2 局部自适应输入控制矩阵设计 Gi = [ I r j I g j I b j 1 ] j∈|Ωi| α di di hi hi hi hi 记局部窗口内的特征矩阵为 ， 当前背景颜色取线-线、点-线、点-点及单点模型 时，由 3.1 节知颜色特征到 值变换的自由度为 4、3、2、1，因而相应模型下特征矩阵的秩也为 4、 3、2、1。矩阵的秩越低，表示特征向量间的相关 性越大，窗口内像素点间具有高的相似度，这使 得隐含的未归一化前的节点度值 更大，若图模 型未进行归一化，则不同的 能够使信息流根据 图像特征进行扩散，因而输入控制参数可取为相 同的值；若图模型进行了归一化，当窗口内的方 差较小时，局部区域颜色变化平滑，则希望有较 小的 来使得当前节点的自吸收概率低，从而信 息流有更大的流动性，反之则 取较大的值。总 之，参数 设计的目标是使信息流根据图像的局 部特征得到合适的扩散，即在模型简单颜色平滑 区域的扩散程度高，复杂区域的扩散程度低。综 上所述，本文采用的 计算公式为 hi = γ1, G = (V,E)是非归一化图 γ2 ×rank(Gi)× σi σ , G = (V,E)是归一化图 (11) γ1 γ2 rank(Gi) σi σ = √∑ i (σi) 2 /n hi pii = γ1/(γ1 +di) di di d0 式中： 、 为全局输入控制常数，为避免过强输 入限制作用，一般将其取为小值； 为特征 矩阵的秩； 为窗口内颜色方差，整张图像的平 均方差为 。当建立的是非归一的 图模型时，各节点的输入控制参数 取相同的 值， ，各节点度 的差异性使得在 未归一化图上的扩散自然具有边界吸收特性；当 建立的是规则化的图模型时，节点度 取相同的 值 。对应的自吸收概率为 pii = hi/(hi +di) = γ2 ×rank(Gi)×σi/(γ2 ×rank(Gi)×σi +d0 ×σ) rank(Gi) pii σi/σ 由于特征矩阵秩 的 4 种取值分别对 应窗口内颜色的 4 种分布模型，此时图像上各点 的 取值实质上是按照线−线、点−线、点−点及 单点 4 种颜色模型先进行粗略地分段，而后再用 进一步细化而得，这样信息流将会根据图像 的局部特性进行自适应地扩散。 σi rank(Gi) Gi Gi = UΣV T [σi1 σi2 σi3 σi4] σi1 > σi2 > σi3 > σi4 σi = √( σ 2 i1+σ 2 i2+σ 2 i3+σ 2 i4 ) /4 rank(Gi) 与 计算方法为：首先对矩阵 进 行奇异值分解得 ，得到对角线上的奇异 值为 ，且 ，则转换 后的方差为 ， 的 ·1010· 智 能 系 统 学 报 第 14 卷
第5期 陈秋凤，等：局部自适应输入控制的随机游走抠图 ·1011· 取值为 得到各节点对应的输入控制参数。低层的种子点 rmk=as>】 12) 包含原始用户输入的标注与高层计算中新增加的 种子点，新增前背景种子点的阈值取为 式中：t为预先设定的阈值，参考文献[23]取值为 t=mean(c)+1.2x max(.) 0.0025。式(12)表示转换空间中方差大于阈值1 2 tb=0.5×mean(a) 的维数。 式中心，为高层基于超像素计算出来的α值。当 4单帧图片抠图 a>tr时，则点i取为新的前景种子点：当<t6 时，则点i取为新的背景种子点；其他点则将高层 为了提高算法的快速性，单帧抠图采用双层 传递下来的α值作为软约束条件，引导随机游走 的形式。首先对图像进行SLIC超像素24分割， 的相似扩散过程，从而得到低层的抠图结果。通 构建基于超像素的图模型G,对初始的用户输入 过新增加前景和背景种子点，在低层的SCRW抠 进行信息扩散得到高层抠图结果，接着将高层结 图中，未知点的数目减少，因而算法的运行时间降低。 果作为低层抠图的输入标注信息，在基于像素的 图模型G,上进行扩散，求得细化后的结果。本文 5视频抠图 在高层和低层都采用具有软约束的随机游走算 由于视频抠图处理数据量大，一般无法对每 法SCRW,二者的区别在于图模型的构造和控制 帧图像进行标注，但图像序列间具有连续性与相 矩阵H的设计上。 似性，充分利用图像的帧间信息可以获得单张图 在高层中，图模型G1=(V1,E)中的连接边有 像不具备的特征。本文在单帧双层SCRW算法 3种：空间上相毗连的两个超像素点间：共享一个 的基础上，采用软硬两种约束相结合的方式进行 边的超像素点间；在颜色空间中用FLANN算法 视频抠图。图1为视频抠图的示意图：左侧为输 寻找到的m:个最相似的超像素点间。连接两节 入的第i-1帧、第i帧图像及相应的三分图区域 点的相似度计算公式为 (背景B,前景F,未知区域U)。连续两帧图像间 lic-cl Wir exp (13) 的信息传导有两种：光流映射与流形最近邻映射。 62 三分图匹配 a值匹配 式中：cw、c,为超像素节点W、v的平均CIELAB颜 - 色值；6为控制相似度计算的常数，文中62=0.1。 第一1 由于在全局图像的相似度计算中采用相同的6， 光流映射 流形最近邻映射 SCRW低层抠图 因此高层建立的图模型G1=(V,E)是未归一化 的，根据式(11)各节点的控制参数取相同的y, 第i邮 矩阵H=yI。记某超像素s内的总像素数为n, 软约束 用户标注的前景像素数为m,背景像素数为， 硬约束 、女软约束 中SCRW高层抠图 当/m,=1、m心/m,=1时，该超像素被定为前景、背 景种子点；当m/m<1、n/m,<1时，该超像素是不 完全标注，取m/m,、/m分别作为前景、背景的 图1 SCRW视频抠图示意 初始软约束条件，运用软约束随机游走算法来计 Fig.1 Schematic of SCRW video matting process 算超像素属于前景和背景的概率，从而得到高层 抠图结果。 首先计算图像的前向与后向运动向量262列 在低层中，图模型按照传统的C℉算法©建 [%4y小，将前一帧的三分图T-1按照前向光 流映射到当前帧，并对其进行形态学操作去除部 立，相似度函数为 分杂点，确保新产生的三分图T:的准确性。而后 之回+-w+-四 对图像进行超像素划分进行高层SCRW运算，将 已知区域向未知区域扩散得到初步抠图结果 式中：2，为围绕像素点q的3×3窗口；4，、∑，为 h。与式(13)不同，此时具有边连接的两超像素 窗口内颜色的均值和方差；2为窗口像素数；ε 相似度的计算中包含了前向、后向光流场向量： 为规则化因子，取10。由以上分析可知，此时建 F-F Wu exp- 立的是归一化图模型。根据式(12)计算各节点窗 62 口内的颜色特征向量的秩与方差，再代入式(11) 式中：F,为颜色特征；F,为运动向量特征，取值为
取值为 rank(Gi) = arg max k∈{1,2,3,4} [ σik σi > t ] (12) t t 式中： 为预先设定的阈值，参考文献 [23] 取值为 0.002 5。式 (12) 表示转换空间中方差大于阈值 的维数。 4 单帧图片抠图 G1 G2 为了提高算法的快速性，单帧抠图采用双层 的形式。首先对图像进行 SLIC 超像素[24] 分割， 构建基于超像素的图模型 ，对初始的用户输入 进行信息扩散得到高层抠图结果，接着将高层结 果作为低层抠图的输入标注信息，在基于像素的 图模型 上进行扩散，求得细化后的结果。本文 在高层和低层都采用具有软约束的随机游走算 法 SCRW，二者的区别在于图模型的构造和控制 矩阵 H 的设计上。 G1 = (V1,E1) nk 在高层中，图模型 中的连接边有 3 种：空间上相毗连的两个超像素点间；共享一个 边的超像素点间；在颜色空间中用 FLANN 算法[25] 寻找到的 个最相似的超像素点间。连接两节 点的相似度计算公式为 wuv = exp( − ∥cu −cv∥ δ 2 ) (13) cu cv u v δ δ 2 = 0.1 δ G1 = (V1,E1) γ1 H = γ1 I s ns n f s n b s n f s /ns = 1 n b s /ns = 1 n f s /ns < 1 n b s /ns < 1 n f s /ns n b s /ns 式中： 、 为超像素节点 、 的平均 CIELAB 颜 色值； 为控制相似度计算的常数，文中 。 由于在全局图像的相似度计算中采用相同的 ， 因此高层建立的图模型 是未归一化 的，根据式 (11) 各节点的控制参数取相同的 ， 矩阵 。记某超像素 内的总像素数为 ， 用户标注的前景像素数为 ，背景像素数为 ， 当 、 时，该超像素被定为前景、背 景种子点；当 、 时，该超像素是不 完全标注，取 、 分别作为前景、背景的 初始软约束条件，运用软约束随机游走算法来计 算超像素属于前景和背景的概率，从而得到高层 抠图结果。 在低层中，图模型按照传统的 CF 算法[10] 建 立，相似度函数为 wi, j = ∑ q| (i, j)∈Ωq 1 Ωq 1+(Ii −µq) T ( ∑ q + ε Ωq Λ3) −1 (Ij −µq) Ωq q 3×3 µq ∑ q Ωq ε 10−5 式中： 为围绕像素点 的 窗口； 、 为 窗口内颜色的均值和方差； 为窗口像素数； 为规则化因子，取 。由以上分析可知，此时建 立的是归一化图模型。根据式 (12) 计算各节点窗 口内的颜色特征向量的秩与方差，再代入式 (11) 得到各节点对应的输入控制参数。低层的种子点 包含原始用户输入的标注与高层计算中新增加的 种子点，新增前背景种子点的阈值取为 tf = mean(αs)+1.2×max(αs) 2 tb = 0.5×mean(αs) αs α αi > tf i αi < tb i α 式中 为高层基于超像素计算出来的 值。当 时，则点 取为新的前景种子点；当 时，则点 取为新的背景种子点；其他点则将高层 传递下来的 值作为软约束条件，引导随机游走 的相似扩散过程，从而得到低层的抠图结果。通 过新增加前景和背景种子点，在低层的 SCRW 抠 图中，未知点的数目减少，因而算法的运行时间降低。 5 视频抠图 i−1 i 由于视频抠图处理数据量大，一般无法对每 帧图像进行标注，但图像序列间具有连续性与相 似性，充分利用图像的帧间信息可以获得单张图 像不具备的特征。本文在单帧双层 SCRW 算法 的基础上，采用软硬两种约束相结合的方式进行 视频抠图。图 1 为视频抠图的示意图：左侧为输 入的第 帧、第 帧图像及相应的三分图区域 (背景 B，前景 F，未知区域 U)。连续两帧图像间 的信息传导有两种：光流映射与流形最近邻映射。 第 i−1 帧 第 i 帧 三分图匹配 Ti−1 α 值匹配 Ti F B U F B U 光流映射 流形最近邻映射 F U B F U B SCRW 高层抠图 SCRW 低层抠图 硬约束 软约束 软约束 αi−1 αi ⊕ 图 1 SCRW 视频抠图示意 Fig. 1 Schematic of SCRW video matting process [ ub vb uf vf ] Ti−1 Ti αh 首先计算图像的前向与后向运动向量[26-27] ，将前一帧的三分图 按照前向光 流映射到当前帧，并对其进行形态学操作去除部 分杂点，确保新产生的三分图 的准确性。而后 对图像进行超像素划分进行高层 SCRW 运算，将 已知区域向未知区域扩散得到初步抠图结果 。与式 (13) 不同，此时具有边连接的两超像素 相似度的计算中包含了前向、后向光流场向量： wkl = exp( − ∥Fk − Fl∥ δ 2 ) 式中：Fk 为颜色特征；Fl 为运动向量特征，取值为 第 5 期 陈秋凤，等：局部自适应输入控制的随机游走抠图 ·1011·