图2-2网络的切割示意图
2.2.3源点和汇点同一化处理
在一个一般的s-t网络中，源点集和汇点集可以由多个结点组成，如图2-3所示，{S1、S2}为源点集，{T1、T2}为汇点集。在实际应用过程中一般将多源多汇的网络映射成单源单汇的网络，以便简化问题或降低复杂度。通用的方法是引入两个新的接点SS和TT，用容量为∞的弧把SS 连接到源点集中的每一个结点，用容量为∞的弧把把TT 连接到汇点集中的每一个结点，如图2-3所示。

图2-3  多个源点和汇点的s-t网络（传统方法）

图2-4  源点和汇点的同一化处理
在上述算法中将边的权值设置为∞会影响后继最大流-最小割的远行效率。Ning Xu在文献[39]中给出了既不增加结点也不增加无穷大权值的另一种称为“结点同一化”的映射方法：将源点集、汇点集合并为对应的两个结点SS1和TT1，删除合并产生的自回路边，结点SS1或TT1与任意中间结点的所有边合并为一条边，该边的权值为原两结点间所有边的对应权值累加，以SS1，TT1分别作为新s-t网络N*的源点、汇点，得到图2-5所示新的s-t网络，可见，用该方法映射得到的新s-t网络更为简洁。在本论文中研究采用该方法实现源点和汇点同一化后的网络流图。

  
图2-5 源点和汇点的同一化处理（文献[39]的方法）

2.2.4网络流理论及最大流的求解
赋予G中每个有向边< vi,vj >一个非负数fij，这一组数满足下列两个条件称为网络的流，用f来表示它。
(1)每一条边(vi,vj) ,有fij<cij。
(2)对于既不是源也不是汇的每个顶点vi ,恒有。
(fij为边<vi,vj>的流量)
定义2-1对于源点S和汇点T有:

这个w叫做网络流的流量，而且从S点发出的量等于进入收点T的量。
当fij=cij时，称为边<vi,vj>饱和，或f饱和，表示流f对该边已饱和。最大流问题是求使得从源点S送往汇点T的流量w达到最大的流f。
定义2-2对于路P满足下面两个条件称P是非f饱和路
(1)每条正向边<vi,vj>，fij<cij；
(2)对P中的每条反向边< vi,vj >，fij>0。
否则，称P是f饱和路，非f饱和的ST路称为f的可增广路[27]。     
对于最大流的求解有多种方法，本章采用的是标号法[27]，下面对标号法做简单叙述，在引入该方法之前，先介绍一个定义和两个定理。
定义2-3 设f和C分别为网络G的流和容量，P是网络G中从源S到汇T的f的可增广路，则
 
其中，cij-fij对应于P中的正向边<i,j>，fij对应于P中的反向边。
例：图2-6为网络流图的一个实例， P=v1v2，v1v2的方向为正向，其中c12=10，c23=8，f12=2，f21=2。
则c12-f12=10-2=8，反向边f21=2，Δ= min{ c12-f12, f21}= min{8,2}=2，
得到正向边，反向边。.
 

图2-6 网络流图的实例
定理2-1 设f和C分别为网络G的流和容量，P是网络G中从源S到汇T的f的可增广路，Δ、f*见定义2-2，则f*是网络G的一个流，它的值比流f的值大Δ[27]。
定理2-2 设网络G的源为S汇为T，f和C分别为G的流和容量，则f是最大流当且仅当G中不存在f可增广路[27]。
基于定理2-1、定理2-2将标号法的步骤归纳为：
（1）从一个流开始；
（2）查找f的可增路。如果f的可增路不存在，结束，流是最大流；
（3）沿f的可增路增加流量△，其中△按定义2-3所定义，并转向(2)。
定理2-3在任何网络G中，最大流的值等于最小切割的容量[27]。
根据定理2-3网络的最小割问题可以通过计算其最大流来解决。
2.2.5抠像问题向网络流的的转化
抠像问题向网络流的的转化要解决的关键问题是如何构造一个网络流图来表达待抠取的图像，图2-7(a)到图2-7(b)形像地表达了这一转化关系，图2-7(a)两个顶点S和 T分别代表人工标定的前景对像和背景。图2-7(b)中，图中的顶点一般会有 6条边，其中两条边分别连接代表对像和背景的S和T顶点，其余 4条边连接其上下左右 4个顶点（即本文采用四邻域），位于图中边缘部分的顶点边会有所减少，S和T顶点连接图中的每个像素。
除S , T外，网络中的每个结点来代表图像的像素点。图像中像素对应网络的顶点，像素之间的相似性对应边上的容量，通过以上方式将图像映射到一个s-t 网络。像素结点之间的连接称为 n-连接，像素结点与源点和汇点的连接称为 t-连接。n-连接代表了图像的邻域系统，而 t-连接代表了像素与标记(源点、汇点)的关系。选择合适的能量函数来表示像素之间的相似性。本文算法用前景区域能量对应于任一像素p与T之间t-连接的容量，背景区域能量对应于任一像素p与S之间t-连接的容量，用边界能量对应任一像素p与相邻像素之间的则n-连接容量，该网络的最小割s-t定义了最小化能量的一个分割。根据定理2-3（最大流/最小割）的等价性定理，可以采用求解网络最大流的算法来获得最小割。

图2-7 基于图割理论的图像抠像示意图

2.2.6 基于图割理论进行的图像抠像的基本思路
图割理论的核心思想在于构造一个能量函数，然后运用组合优化技术来最小化该能量函数。图像抠像问题即是一个将像素标为前景/背景的典型二元标号问题。基于图割理论进行的图像抠像的基本思路是通过网络构造、最小化能量函数及网络流理论，把标号问题转换为用最大流-最小割方法来解决。

图2-8基于图割理论进行图像抠像的基本框架

如图2-8所示：首先构造能量函数，把图像抠像问题转化为能量函数最小化问题；然后通过构造s-t网络，使能量与s-t网络的割的容量相对应；最后利用图的网络流理论给出能量函数的最小化解，从而获得抠像问题的解。
2.3基于图割的抠像算法
基于图割的抠像算法用灰度值的数组Z=(z1,z2,zn) (n表示图像总的像素点个数)来表示输入的图像，则图像的抠像问题可以看作是一个给每个像素点zi，其中i∈(1,2,…,n) 赋一个相应透明度的过程。透明度一般用值来表示，抠像的任务就是确定每一个未知像素的i值，即确定i的值为1或0。当i的值为1时，判断为前景，i的值为0时，判断为背景。图像抠像问题可以用（2-1）式来描述 [5]。
                                         (2-1)
式(2-1)中，A为与有关的函数，E(A)为图像切割的总能量，它与前面提到的s-t 网络切割的容量相对应，。
传统的基于图割抠像算法的能量模型用（2-2）式来表示[5]。
                                    
                               (2-2)
式中，i表示图像单个未知区域的像素，V表示未知像素的集合，表示i和j为相邻像素，E表示所有相邻像素的集合，与前面的边集对应，E1(Ai)表示像素i区域能量，它与前面提到的t-连接相对应，E2(Ai ,Aj)表示相邻像素i和j之间能量(传统的算法称为边界能量)，它与前面提到的n-连接相对应，参数用于反映区域能量与边界能量的相对重要性，传统的基于图割的抠像算法将设为一个固定常数。基于图割的抠像算法根据最大流/最小割的等价性定理，采用求解网络最大流的算法来获得最小割。
图G的一个s-t割是边集E的一个子集，通过最大流算法将图G的结点分为两部分，一部分与源点S相连，其余结点与汇点T相连。最后将与前景像素块(源点S)相连的像素标记为1，将与背景像素块(汇点T)相连的像素标记为0。
2.4基于图割中动态权重参数能量模型的抠像算法
本章在研究传统的基于图割的抠像算法的基础上，综合考虑了能量模型中区域能量与边界能量的相对重要性关系、采样信息（人工标定前景和背景），提出了基于图割中动态权重参数能量模型的抠像算法。本章的方法分为以下三个步骤：(1)与传统的基于图割的抠像算法一样，构造能量函数，把图像抠像问题转化为能量函数最小化问题，能量函数的优劣将影响抠像效果的好坏，这是极为关键的一步；(2)通过构造s-t网络，将能量函数值与网络流图中边对应；(3)根据最大流最小割定理，将网络的最小割问题转化为求解网络最大流，进而获得抠像问题的解。
本算法的创新工作在于采用画轮廓线的方法来代替三分图标定前景（源点）和背景（汇点），在图割能量模型中加入了动态权重参数，并对背景像素块的均值和方差实行迭代更新，最后对抠像后的图像进行多次修正。
2.4.1 算法的能量模型
(1)像素块的均值和方差
本章算法用像素之间的相似性来表示能量函数，像素之间的相似性越大表示能量函数值就越大，反之相反，各结点（像素或像素块）的性质用该结点（像素或像素块）均值和方差来描述。
在待抠像图像中，通常采用人工标定方法确定前景(源点)和背景(汇点)。
设某个图像的像素集合为P。把人工标定的前景像素分为m块。设第i块像素集合为Pi，像素个数为NIi，则该块的RGB向量的平均值与协方差分别用(2-3)和(2-4)式计算。
                           (2-3)
                     (2-4)
其中, 为像素p的RGB列向量。同样把人工标定的背景像素分为n块，其均值和协方差分别用(2-5)和(2-6)式计算。
                            (2-5)
                     (2-6)
(2) 前景和背景区域能量
从前面的描述知，图像抠像问题是一个将像素标为前景或背景的问题。判断一个未知像素p属于前景还是背景，首先要考虑这个像素本身的颜色。如果与已标定背景颜色相比，它的颜色与已标定前景的颜色更接近，那么它属于前景的可能性大于属于背景的可能性，反之相反。本文用区域能量E1(Ap)来描述像素的这种属性。设F为前景像素集合，B为背景像素集合，U为未知像素集合。用前景区域能量来描述未知区域像素p与已标定前景颜色块的相似程度，记作E1F(Ap)；用背景区域能量来描述未知区域像素p与已标定背景颜色块的相似程度，记作E1B(Ap)。
图割算法采用直接比较求绝对值方法来判断任一未知像素p与前景颜色和背景色的相似程度和，即，。
前景区域能量E1F(Ap)和背景区域能量E1B(Ap)，分别用式（2-7）、（2-8）来表示。
                                        （2-7）
                                        （2-8）
对于任一未知区域的像素，其颜色与前景的颜色越相似, E1F(Ap)值越小，p越有可能为前景像素；它的颜色与背景的颜色越相似, E1B(Ap)值越小，p越有可能为背景像素。
(3) 边界能量
判断一个未知区域的像素属于前景还是背景，除了考虑是这个像素本身的颜色，还应该考虑它周围的像素属于哪部分，如果它周围的像素都属于背景，那么它也很有可能属于背景，像素p越不可能成为边界像素，反之相反。而且它的颜色跟周围像素的颜色越相似，这个可能性越大。用边界能量来描述这种属性。
                              （2-9）
Cn表示与p相邻的像素RGB列向量。为一个冲击响应函数，当Cp=Cn的时候其值为0，否则为1。
从（2-9）式可以看出，像素p与相邻像素的颜色越接近，的值越小，像素p与相邻像素属同一个区域（前景/背景）的可能性就越大，像素p越不可能成为边界像素。
(4) 能量模型的求解
为获得最优分割，需要最小化全局能量式(2-2)。根据图割理论，可以将全局能量最小化问题转化为图割问题来求解，先对前景像素块和背景像素利用前面提到的方法进行节点同一化处理，然后通过求解最大流来获得前景与背景的切割线。
2.4.2能量模型最小化的迭代和背景样本值的快速更新
传统的基于图割的抠像算法需要人工去指定前景(源点)、背景(汇点)和未知区域，GrabCut使用非完全编号(画一个矩形框)取代了完整三分图，提高了操作的灵活性， 即用户的初始交互只需确定背景区域B（即矩形框的外部）, 并不需要确定前景。在操作过程中临时指定一些未知区域像素为前景像素, 而背景的编号是固定不变的。与GrabCut算法不同的是，本章的算法使用画轮廓线代替画矩形框的办法来标定前景(源点)和背景(汇点)。这种方法不仅操作简单，对于复杂形状的前景也具有很好的适应性。
传统的基于图割的抠像算法能量最小化是一次完成的，即通过求解网络最大流来完成能量最小化，获得前景和背景的切割线，进而完成抠像，这种通过一次求解获得的切割线相当粗糙。GrabCut提出能量模型的迭代求解，即在获得前景和背景的切割线后，从获得的切割线开始重新利用最大流算法来完成能量最小化，即将切割线外部的像素当做背景像素重新迭代，当判断出能量函数值无大幅度衰减时自动终止迭代，此时获得的切割线为最优解。
与GrabCut算法不同的是，本章算法在一次迭代获得前景和背景的切割线后，对人工标定的背景像素块的均值和方差做出快速更新，将更新后的均值和方差用于下一次迭代求解。本算法将一次迭代新增加的背景像素的集合记为Px，Px中所有的像素均用于背景像素块的均值和方差的更新。记px为Px 中的任一像素，将式（2-5）、（2-6）求得的最小概率对应的前景块号记为l，该块的均值和方差分别用式（2-10）、（2-11）更新。
为了说明这种迭代思想的有效性，特选用了一幅图像与GrabCut算法进行对比实验，实验过程中使用同样大小提示图像（标记框）。实验结果如图2-9所示， 其中(a)为原图像，(b)对应GrabCut算法结果图，(c)为采用人工标定的背景像素块的均值和方差更新的结果图，比较的结果可以看出。相对于GrabCut算法，人工标定的背景像素块的均值和方差更新后获得的图像边界更平滑，边界沾染的背景像素更少。
结果对于前景背景差别大图像，一般迭代5~10次能量函数值达到最小，对于前景背景差别小的图像，一般迭代15~20次才会结束。
                         （2-10）
                   （2-11）
其中Pl为第l块像素集合，Il为第l块像素个数。
 
               (a)               (b)              (c)
图2-9 结果比较图
(a) 原图
(b) GrabCut算法的结果图
(c)人工标定的背景像素块的均值和方差更新后的结果图
2.4.3能量模型中的动态权重参数
传统的基于图割的抠像算法用来调整区域能量和边界能量影响的权重参数λ是一个常数，本章算法引入了动态权重。在开始迭代时由于处理的像素离边界较远，抠像结果应该尽可能地展示出光滑的特性。因此，λ应当足够地大使得能量函数由边界能量占据主导地位。随着迭代的进行处理的像素离边界较近，抠像结果应该尽可能地展示出不连续的特性，这时候我们应该让边界能量处于次要地位。
从2.4.2知对于前景背景差别大的图像，一般迭代5~10次能量函数值达到最小，对于前景背景差别小的图像，一般迭代15~20次得到正确的切割线。对前景和背景差别小的图像，随着迭代进行，权重参数λ应当足够小以充分发挥区域能量的影响，以便能更好地获得前景的边界，而且较小的λ也可以抑制边界能量的影响，保持图像的不连续性。因此，我们是根据每一步的迭代动态地确定相应的λ。本文算法引入了动态权重参数，采用迭代法求取最佳的λ值，λ定义如下：
                                     (2-12)
随着迭代的进行，λ逐渐地从一个非常大的值过渡到一个相对较小的值，与前面的分析一致。其中k是能量最小化的次数，β是一个调整常数，通常设为6或7。当前景区域或背景区域是不连续的情形，β被设成一个很小的常数0.5 ，随着迭代次数的增加，λ迅速减小。
为了展示引入动态权重参数的有效性，特选了几幅图像进行与λ为常数时进行对比实验，在实验过程中均对人工标定的背景像素块的均值和方差快速更新（2.4.2节提到的），动态与静态权重参数的比较如图2-10所示，其中(a)为原图像， (b)为提示图像（标记框）， (c)为权重参数设为一个固定常数的抠像结果，(d) 为动态权重参数的抠像结果，比较可以看出，相比于权重参数设为一个固定常数的抠像结果，使用动态权重参数获得的前景图像更加完整。
表2-1罗列了每张图片所对应的迭代次数和操作时间。从比较中可以看出，无论是时间还是抠像精度上，使用动态权重参数获得的结果明显占优。
表2-1动态与静态权重参数的比较
图像 图像尺寸 迭代次数 耗时（s）
  静态 动态 静态 动态
香蕉 480*500 24 15 215 114
马 500*550 26 16 225 120
花朵 550*580 30 19 280 130

      
（a)                           (b)
      
                       (c)                             (d)
图2-10动态与静态权重参数的比较
(a)原图
(b)提示图像（标记框）
(c)权重参数设为一个固定常数的抠像结果
(d)动态权重参数的抠像结果
2.4.4算法流程
全局抠像算法可以方便快捷地抠取出图像的前景，但是对于复杂的图像或是图像的敏感区域（如图2-11(a)红框部分），全局抠像算法得到的抠像结果并不理想(如图2-11(b)所示)。为了解决上述不足，需要对抠取结果不正确区域进行多次交互抠取。
修正方法的具体做法如下：
（1）观察初始抠像结果图，找出没有达到用户要求的区域；
（2）通过人工标定的方法确定源点（前景集）和汇点（背景集）；
（3）采用本文算法进行抠像。
图2-11(c)为目标图像修正后的结果，实验平台为：Windows XP Standard Edition, Matlab 7.1, Microsoft Visual Studio 2005, CPU: Pentium 4/531, RAM: 512MB，修正耗时2.224s，修正算法不仅实时性强，操作简单，而且能很好地抠出难度高的图像，获得的抠像效果较好。
        
           (a)                      (b)                     (c)
图2-11目标图像修正前后的比较
(a)原图像
(b)修正前的目标图像
(c)修正后的目标图像

综上所述，本算法流程如图2-12所示。

图2-12本算法流程

2.5实验结果与分析
本章我们通过一组实验来说明本章算法的优效性，本章所涉及的算法都使用matlab作为平台来实现，与2.4.4一样，所有实验结果都是在同一台配置下完成：Windows XP Standard Edition, Matlab 7.1，Microsoft Visual Studio 2005，CPU: Pentium 4/531，RAM: 512MB。在实验过程中我们借用了文献[5]的部分代码，对于GrabCut算法我们根据其描述重新实现其算法，对于Marker Drawing方法我们借助了原始文献的可执行代码。
图2-9(a)、图2-10(a)、图2-11(a)对应的原始图像前景和背景差别较大，通过前面的比较分析知，用本章算法能获得较好的效果。
为了进一步说明本章算法的有效性，将本文算法与Marker Drawing[24]、GrabCut算法[6]在一些前景和背景差别较小的图像上进行对比实验。图2-13为原图像与提示图像，为了验证本文算法的有效合理性，本章算法与Marker Drawing、GrabCut算法[6]使用的提示图像设为一致，图2-13 (a)“鸟巢图”原始图像，图2-13 (b)为“鸟巢图”提示图像（标记框），图2-13 (c)“鸭子图”原始图像，图2-13 (d)为“鸭子图”提示图像（标记框）。
传统的抠像算法（Poisson抠像算法[4]与贝叶斯抠像算法[3]等）需要人工去指定前景(源点)、背景(汇点)和未知区域，即需要用户在画一些线条来表示一部分区域为前景和背景，通过这种方式制作的三分图相当麻烦。本章的算法中使用画轮廓线代替画矩形框的办法来标定前景(源点)和背景(汇点)不仅简便，而且对于前景和背景差别较小的图像和形状相对复杂的图像具有很好的适应性。
实验结果如图2-14，图2-15所示，其中图2-14(a)、图2-15(a)是Marker Drawing算法所得的结果，尽管Marker Drawing算法对于一般图像抠像效果良好，但是对于复杂的图像所得效果不理想，对这种前景和背景差别较小的图像所得边缘相当粗糙；图2-14(b)、图2-15(b)是GrabCut算法所得的结果，相比于Marker Drawing方法，GrabCut算法虽然在边界处理上有一定的提高，但是对于图像的敏感的区域抠像效果仍不理想；图2-14(c)、图2-15(c)为使用本章算法所得的结果，从实验结果可以看出，采用本章算法后图像的各个部分均得到了较为合理的分离，图2-14“鸟巢图”中使用本章算法很好地分离出了背景区域的地面部分，同时人物身后建筑物也能很好地分离开来。通过与其它几种算法比较可以看出，采用本章算法抠像后的图像边缘更加平滑，能获得更好的视觉效果。
从前面知，本章算法对前景和背景差别较大的图像及前景和背景差别较小的图像能获得较好的抠像效果。
为了进一步验证本章算法的有效性，我们使用几张人造图像来对比实验，因为这种人造图像有着预先设计好的像素的前景透明度，我们将得到的前景透明度与真实的像素的前景透明度之间的误差值进行求和并将其绘制成直方图，如图2-16所示，其中横轴的1、2、3、4分别对应四组比较，纵轴对应的误差值（误差像素的个数），从结果可以看出，相比于其它算法本章算法获得的结果明显占优势。

           (a)                (b)                (c)              (d)
图2-13原图像与提示图像
(a)“鸟巢图”原始图像
(b)“鸟巢图”提示图像（含标记框）
(c)“鸭子图”原始图像
(d)“鸭子图”提示图像（含标记框）

      
               (a)                （b）              (c)            
图2-14 “鸟巢图”各种不同方法抠图效果的对比
(a) Marker Drawing方法所得的结果图
(b)GrabCut算法所得的结果图
(c)本章算法所得的结果图
          
(a)               （b）                (c)            
图2-15“鸭子图”各种不同方法抠图效果的实验对比结果图
(a) Marker Drawing方法所得的结果图；(b)GrabCut算法所得的结果图
(c)本章算法所得的结果图