第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·