基于图论的分割方法

此类方法基于图论的方法利用图论领域的理论和方法，将图像映射为带权无向图，把像素视作节点，将图像分割问题看作是图的顶点划分问题，利用最小剪切准则得到图像的最佳分割。此类方法把图像分割问题与图的最小割（MIN-CUT）问题相关联，通常做法是将待分割的图像映射为带权无向图G=(V，E)，其中，是顶点的集合，E为边的集合。图中每个节点N∈V对应于图像中的每个像素，每条边∈E连接着一对相邻的像素，边的权值其中表示了相邻像素之间在灰度、颜色或纹理方面的非负相似度。而对图像的一个分割S就是对图的一个剪切，被分割的每个区域C∈S对应着图中的一个子图

分割的原则就是使划分后的子图在内部保持相似度最大，而子图之间的相似度保持最小。我们以一个两类的分割为例，把G = (V,E) 分成两个子集A,B,另： ，CUT(A,B) = , 其中 , 是权重(weight), 最小割就是让上式的值最小的分割