3.9　基于图论的图像分割方法

基于图论的图像分割法是图像分割领域的一个新热点。下面将对该方法的基本理论作简要介绍。

3.9.1　图的最优划分准则

令图G=（V，E），图G被划分为A和B两部分，且有A∪B=V，A∩B=Φ。节点之间的边的连接权为w（u，v），则将图G划分为A和B两部分的代价函数（Cut Size），有

使得上述剪切值最小的划分（A，B）即为图G的最优二元划分，这种划分准则称为最小割集（Minimum Cut）准则。

3.9.2　图像的最佳分割

将一幅图像视为一个带权的无向图G=（V，E），像素集被看作节点集V，边缘集被看作边集E，像素之间的连接权为w（i，j），则将图像二值划分为两个集合（区域）A和B的代价函数，有

对于一幅图像来说，使上述代价函数最小的划分即为图像的最佳分割。

3.9.3　权函数

权函数一般定义为两个节点之间的相似度。在基于图论的图像分割法中，常见的权函数有如下形式：

式中，对于灰度图像，F_i的值为像素的灰度值，X_i为像素的空间坐标，为灰度高斯函数的标准方差，为空间距离高斯函数的标准方差，r为两像素之间的有效距离，超过这一距离则认为两像素之间的相似度为0。根据相似度函数，两像素之间的灰度值越接近，则两像素之间的相似度越大；两像素之间的距离越近，则其相似度也越大。

另外，文献定义了如下两个权函数为

及

上述权函数仅考虑了像素之间的灰度关系，没有考虑其空间关系。

3.9.4　最新研究方向

目前，基于图论的图像分割方法的研究主要集中在以下几个方面：（1）最优割集准则的设计；（2）谱方法用于分割；（3）快速算法的设计；（4）其他图论的分割方法。