0 引言
Graph Cuts（GC）<sup>[1]</sup>是一种广泛应用的的优化算法，在目标提取领域中该算法通过简单地交互标记出部分前景和背景区域，该方法就可以将目标从复杂的背景中分离出来。由于人工交互的存在，该类算法获得了比较可靠的先验知识，随后的自动分割又使得整个过程不需要太多的人工干预就能获得较好的分割结果，因此算法获得了广泛的应用并吸引了很多学者研究并改进[2-4]。
GC算法基于图论，将图像分割问题与图的最小割（min cuts）联系起来，在给定的图像中求解一个最优分割位置。从图像到图论，再到最优分割，各种复杂的概念夹杂在一起，使得算法实现过程中有很多细节问题需要解决。本文详细叙述了GC算法实现细节，为进一步研究GC及其相关方法奠定基础。
1 优化模型建立
模型建立是GC算法的重要部分，该算法建立了类似MAP-MRF的估计方程，既考虑节点集合P，也包含每个节点邻域中的边缘{p，q}。先定义一个分割A=（A<sub>1</sub>，…，Ap，…，A|P|），A是一个二值向量，其中每个元素属于前景或背景。然后可以通过A的代价方程E（A）表示区域和边缘的约束特性：
E（A）=λ×R（A）+B（A）（1）
其中，R（A）是区域特性，B（A）是边缘特性。λ是一个大于0的值，它调节了R（A）和B（A）在整个表达式中的重要性。
R（A）=∑p∈NRp（Ap）
（2）
它表示了区域项R（A）是每一个节点属性的总和。一般在目标提取任务中，Rp（·）可以认为是节点p和前景、背景联系的紧密程度，此时Rp（·）包含了两个值。
B（A）=∑{p，q}∈NB{p，q}·δ（Ap，aq）（3）
其中，N是邻域系统，如四邻域。
δ（Ap，Aq）=1 if A”p≠Aq
0 otherwize
（4）
即：如果Ap和Aq分类相同则忽略它们之间的边缘，它的直观理解是相同性质的节点应该处于相同区域。边缘项B（A）是所有边性质B{p，q}的总和。B{p，q}是一个大于零的项，它惩罚了节点p和q的不连续性。
2 从图像到图的转换
假设待分割的图像为G=（V，E），其中V为顶点集合，一个像素为一个顶点，E为边的集合，相邻两个像素之间有一条边。图1（a）表示的是一个图像，其中椭圆代表顶点，实线代表边。图像中一般只看到像素，边是一个隐含的关系，图1（a）中的边是节点和其四邻域中点之间的关系。
图1 图像到图的转换
GC算法将图像转换为图时保留了所有的节点和边，另外还添加了两个节点T和S。T表示背景，而S表示前景。这两个节点和原来所有节点之间都有联系，表示原来的节点和这两节点的相似程度。
因此，将图像转变成图有这样几个部分：①保留原有的像素节点;②所有节点与其相邻节点（如四邻域）之间为边，文献中将这种边称为n-link。值得注意的是，n-link的边是无向的，若转变为有向图则可以添加双向相同的边;③添加背景节点T和前景节点S，并与原有的像素节点建立边，文献中将这种边称为t-link。
图1（b）表示的是由一个3×3的图像转化而成的图。
3 优化模型的具体函数实现
图建立好后，就可以将图和式（1）建立的优化模型联系起来，最后通过优化算法求解图1（b）中标记为“cut”的“最小割”（min cut），将前景和背景分开。下面是优化模型式（1）中具体使用的函数，这一步能够将理论和实际联系起来。
3.1 区域项
设“obj”表示前景，“bkg”表示背景，则Rp（·）可以表示为一种对数形式：
Rp（”obj”）=-lnPr（Ip|obj）（5）
Rp（”bkg”）=-lnPr（Ip|bkj）（6）
Pr（·）表示概率，式（5）和（6）分别表示的是节点属于前景、背景的概率，并取对数后再取反。当一个节点属于前景的概率大于背景概率时，Pr（Ip|obj）>Pr（Ip|bkg），相应地Rp（”obj”） 另外GC算法需要人工交互，交互中获得的前景节点直接设Rp（”obj”）为一个较大的值，Rp（”bkg”）为0，而背景节点的Rp（”obj”）为0，Rp（”bkg”）为一个较大的值。
3.2 边缘项
B{p，q}使用两个节点间的差异建模：
B{p，q}∝exp（-（）Ip-Iq）22σ2）
（7）
当两个节点的值（如灰度值）相差不多时，B{p，q}比较大（接近1），当两个节点相差较大时，B{p，q}较小（接近0）。由于式（1）中只统计前景和背景边界处的边，因此B{p，q}小能够减小式（1）的总值。B{p，q}对应于图1（b）中相邻节点的边，此时可以理解为相邻两个节点的边相差越大，则处于不同区域的可能性越高。
模型建立好后就可以用最大流（max flow）方法来解决最小割问题，该方法有很多实现方式，并且还处于发展中。
4 结语
GC算法是一个优秀的目标提取算法，是基于图论图像分割方法的基础算法之一。在研究该类图像分割算法时，GC算法是必须研究清楚，并且实现出来的算法之一。本文分析了GC算法的实现过程，给出了每个步骤详细的解释，为进一步研究基于图论的图像分割算法打下了坚实基础。
参考文献：
＼[1＼] YURI Y BOYKOV，M P JOLLY.Interactive graph cuts for optimal boundary & region segmentation of objects in ND images[C].International Conference on Computer Vision，2001：105-112.
[2] YUNQIANG LIU，VICENT CASELLES.Exemplar-based image inpainting using multiscale graph cuts[J].IEEE Transactions on Image Processing，2013，22（5）： 1699-1711.
.Medical image analysis，2013，17（1）： 62-77.
.Pattern Recognition，2013，46（6）： 1719-1733.
