GraphCut

Graphcuts是基于Markov随机场理论和最大流最小割定理（maxflow/min
cuttheory）的图像分割算法，这个maxflow是图论经典的算法，网上很多人有讲解的，咳咳，就不抄了。。。Graphcuts代码啥的也蛮多，放一个我在ubuntu14.04LTS64位系统下调试通过的吧：http://download.csdn.net/detail/terry_o0o/8493811这个其实是运用graph
cuts应用于立体视觉的代码，实现了三种方法。。。其中maxflow的实现代码也包含在里面了，可以对照原理和代码看。

Graphcuts将图像映射成网络图,并在此网络图上构建一个能量函数,然后用最小割算法求解图的最小割集,也就得到了能量函数的最小解。具体说就是把图像中的像素看作是网络图中的顶点,把像素间的相似程度看作是顶点间边的权值大小。大体步骤为:

1.首先将研究的问题转换成有关图像的某种性质(如像素的亮度)的标号问题。

2.建立与此标号相关的一个能量函数。

3.对应于这个能量函数将图像构建成一个网络图。

4.在得到的网络图上求解最小割。得到的最小割的值即为待研究问题的一个最优解。

GraphCuts方法中的能量函数来源于Markov随机场理论,简单理解就是将一幅图像的像素点看作一个网络图的顶点,将图像对应成一个网络图,然后正确设置边的权值使得网络图最小割所对应的弧正好出现在图像中物体的边界处。这样求得最小割位置的同时也找到了目标物的边界。

建立网络图，要从一个图像建立网络图，我们将图像中所有的像素一般分成三部分。指定的目标区域种子点(一般作为源点集),指定的背景区域种子点(一般作为汇点集)和没有被指定的待分割像素点。

网络图一般被构建为单源单汇网络图,因此在构建网络图的过程中还会添加两个额外的终端点,一个源点终端点S,一个汇点终端点t,图像中的所有像素点作为网络图中的普通顶点。其中全部目标区域种子点连接到S,以S作为弧的起点。全部背景区域种子点连接到t,以t作为弧的终端点。同时在所有相邻的像素点所对应的顶点之间建立连接弧。在计算时一般会在每对顶点间建立两条对称的有向弧,分别以两个顶点作为起点。弧的权值与两个顶点对应的像素的亮度差成反比。而连接到S或t的弧的权值一般设为固定值,其值比普通弧的最大值要大即可。

GraphCuts方法其实是求解一个能量函数的最小化的过程,而在图像分割中该能量函数被定义为E(L)=aR(L)+B(L),其中，R(L)为区域项（regionalterm），B(L)为边界项（boundaryterm），而a就是区域项和边界项之间的重要因子，决定它们对能量的影响大小。如果a为0，那么就只考虑边界因素，不考虑区域因素。E(L)表示的是权值，即损失函数，也叫能量函数，图割的目标就是优化能量函数使其值达到最小.

而我们刚刚构建的网络图其实相当于只有能量函数中的B(L))项,此时a=0。这样构建的网络图虽然能够完成图像的分割,但是求出的最小割是一种全局最小割或者说是一种全局最优解。因此要在前面的网络图基础上再添加一项区域条件(即R(L))项),以完善网络图的构建。即对于每个非种子点的普通像素点再增加两条分别连接终端点S和t的弧。弧的权值与该像素点属于目标或背景的概率成正比(称这种弧为t.1inks,而将前一种弧称为n-links)。这样构建的网络图将不在是一个平面结构,而更类似与立体结构。求得的最小割也不再由相邻顶点间的弧值决定,而由相邻顶点问的弧值与顶点和终端点间的弧值共同决定。

Graphcut的3x3图像分割示意图：我们取两个种子点（就是人为的指定分别属于目标和背景的两个像素点），然后我们建立一个图，图中边的粗细表示对应权值的大小，然后找到权值和最小的边的组合，也就是（c）中的cut，即完成了图像分割的功能。

图盗自zouxy09大神，一般人我不告诉他。。