图像分割理论之GraphCut
Fast approximate energy minimization via graph cuts
图割文献阅读笔记以及几个疑惑的解答Graphcut
这篇文章属于Graph cut应用于能量函数最小化较早的文献，文章中介绍了图结构如何构造以及权重如何设计，并且通过这样的设计证明了能量函数的最小值便是通过一次图割优化得到的结果。
Note：
Energy Minimization in Early vision
这章主要介绍了能量函数的构造，即为数据项，平滑项等，在此在重新复习一遍：
数据项：每个像素对其所附标签的代价，这个主要是通过其大小判断标签的合理性。
平滑想：每个像素与其邻域内的像素的距离，主要目的是使得像素与其邻域的像素尽可能平滑。
在本文中的能量函数定义如下：
此公式的形式对后面理解其算法的证明有着重要的作用，其中f代表一个标签集，N为邻域 此后文章主要介绍了目前的一些对能量函数的优化算法，例如模拟退火算法等，此类算法的缺点是求解时间过长，并且也容易陷入局部极小值中。 再者本章也介绍了一个重要的条件（metric）： 此条件主要是针对平滑项所做出的限制，若满足前两项成为semimetric，全部满足即称为metric条件，第三项条件可以看做三角形条件，相当于两边之和大于第三边这样。 同时作者为了比较其算法的不同及优越性，也介绍了一种叫做 Standard move的算法，其算法较为简单，也就是在图像分割时的改变标签的阶段，每次只能将一个像素点改变，这样不仅效率低，也不易找到更好的最优值。
alpha expansion 与alpha-beta-swaps 算法：
在第一次看文献时，错误的理解了这两个算法的本质，认为这是独立于graph cut之外的算法，实际上这个理解不太对，作者的目的是将graph cuts优化后将图像分为两部分标签，并且证明了 graph cuts后的能量函数取到了最小值（至少是local minimal），而无论是alpha expansion或者是 alpha-beta-swaps均为对图结构进行cut后导致标签移动的结果,下面我将试图根据文章中的定理以及定义解释并证明这种算法：
首先列出文献中给出的算法流程：
图1 算法流程
由于这两种算法多少有些相似，因此首先介绍αβ交换算法，alpha-expansion 将在交换算法的条件上增强即可得到。
在图1中可以看到其中3.1步为最重要的步骤，如何通过一次交换得到能量函数的最小值呢？那么就要通过对图结构巧妙地设计以及利用graph cuts进行求解了！
为了得到这个结论先将作者举出的例子，以及一些lemma列出:
为了便于推论以及演示，作者采用了一维结构的图结构，其结构如下：
图2 图结构
可以看到这个包含着cut的图应当还存在一种cut的情况作者没有画出，但奇怪的是作者在后面证明的时候采用了这个没有列出的情况……
图中包含的权值t-link与n-link，作者也给出其设计模式，如下表：
表1 图的权值设定
可以看到，对于t-link其不仅包含了数据项，还包含了顶点对于一些不属于任何类的像素的距离，这点是我之前没想到的。
此公式主要介绍了标签，起初我认为这个标签对于像素p的设置是相反的，这点可以对照图2中发现，但实际上，这个标签并不是想反应像素p究竟属于哪个类别，它的意义在于将cut与图结构联系起来：
我们知道对于每一像素p来说，其会存在两个t-link，分别连接两个不同属性的极点，当cut切断其中一个t-link时，那么这个像素p将会属于另一个类别，而此标签反应的为cut究竟切断了像素p与那个极点的t-link，以此反映在能量函数里。
这个性质简单，就是反映了cut和n-link之间的关系，根据图2便可很快的理解，此处值得注意的是其描述为 for ANY cut c and for ANY n-link,此处作者强调了any，因为此处是满足semimetric条件的，因此其条件较弱，对于任何割与n-link都成立，在后面的alpha-expansion算法中便对此性质进行了加强。
在列完了一些性质以及设定条件后，开始证明部分：
首先先证明一个较简单的
个性质即为对于任意cut，其和n-link之间的关系均可以表示为平滑项之间的关系：
注意此处的证明便是用到了我上文提到的图2中未列出的那种情况，不过我后面又重新思考下，这个作者应当是故意模糊的，因为首先这个图结构V是满足semimetric条件的，即满足这个：
这说明了什么呢？也就是说在平滑项中，其值的大小与像素的标签没有关系，在图2中无论是情况3还是未列举出的那种情况其不同仅仅是像素p，q所属特征不同而已。那么也就更好的说明了，平滑项的设计主要目的是在于将相似的像素更多的聚在一起，而对标签这个因子是忽略的，使其能够更好的将图像分割成功！
此图便为文章中关于算法的证明，首先我们知道一次cut的值为其与n-link，t-link相交的边的权值的和，其表达式如图中（7）式，根据前面对于标签以及权值设置的解释，可以很简单的推导出（7）式中两项的具体表达式，因此最终可以推导出：
即割的最小值即为能量函数的最小值，那么也就揭示了为了通过图割可以找到能量函数最小值！ 总结：首先交换算法中的交换的意义，便是通过图割的割进行分割后根据其属于不同标签的阵营进行交换，其交换的规则取决于graph cut的最优值。同时对于今后算法的应用上，应当按照一定的条件进行权值设置，如果盲目的进行设计，那么其不一定是最优的交换. 关于alpha-expansion算法，其证明的原理类似，但是其条件变为metric，同时其也增加了辅助点的引入，并且满足这个三角形条件可以防止形成孤立的点，虽然其与交换算法有些相似，但其中的一部分仍然需要进一步的思考与梳理。
p.s 这里面在建立图结构时，其t-link的权值赋值时相反的，例如像素p与s点相似度，会被分配到p-t的连接上，这样 进行最小割时才能正确分割，后面的文章中我会提到这个
参考文献： [1] Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2001, 23(11): 1222-1239. [2] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms[M]. Cambridge: MIT press, 2001.