·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] 知，随机游走分割算法的 Dirich￾let 问题也可写成两顶点概率差值的加权和形式： 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 卷