基于图的最小割算法
论文：Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images
是YYB这个牛人在2000年提出的一种经典的基于的图的最小割算法，现在被广泛使用，现在在这里发表个人拙见，欢迎大家提意见。
算法的核心其实就是这个图：
构造一个图，可以把所有node理解为pix，还有两个额外的terminal node：source and sink（分别代表前景和背景吧）
edge分为两种，一种t-link：连接source and sink；另一种n-link：连接相邻node；
node weight可以理解为两个node间的相似度（与source的相似度越高，与sink的相似度就越低，都用权重表示）
min-cut就是找到一种cut使sum of cut edge weight 最小；
怎样找到一个全局最优的Cut方式（用最大流方式Max-Flow）：
1.找到一条路径；
2.flow+=这条路径的最大容量
3.计算剩余图：n-link减最大容量，反向相加；t-link只减不加；
……
4.直到找不到路径
5.得到全局最优解
6.Min-Cut problem dual to Max-Flow problem
Oxford关于图分割的全套PPt点此下载（包括Max-Flow; Min-Cut; Markov;Random Field）