图像分割算法_基于图的图像分割算法
1.算法目标
在计算机视觉中，图像分割是一个非常基础的问题，它是通过一些方法将图像分割为若干个区域。在目标检测中，这是一个非常重要的算法，在用Two-stage算法进行目标检测时，第一步就是执行图像分割，给出待检测的候选区域(Region Proposal)，然后用卷积神经网络(CNN)进行分类和识别。基于图的图像分割算法，是一个比较优秀的图像分割算法，它是选择性搜索算法(Selective Search Algorithm )的基础。
图像分割的效果(左边是分割前的图像，右边是分割后的图像)
2.算法原理
2.1 算法思想
图像分割的任务看起来像是一个聚类的过程，根据相似性规则将图像中相似性高的像素点聚集在一起构成一个个区域(集合)，所以也有很多通过聚类算法进行图像分割的，如：利用K-Means聚类算法进行图像分割。但基于图的图像分割算法与聚类算法不同，它本质上是基于最小生成树的一个图像分割算法，它的运行效率就要比一般的聚类算法快。
介绍几个关于图和树的概念(补了一下数据结构)：
n 图是由顶点集合V和边集合E组成的非线性的数据结构，记为G(V,E)。
n 图又分为有向图和无向图，无向图的边不具有方向性，有向图的边具有方向性。
n 树是一种特殊的图，任意两个顶点都有路径相连但不构成回路。
n 最小生成树(MST)是给定图可以生成的树中边权值之和最小的那个。
基于图的图像分割算法的思想是：将图像中的每个像素点看作图的一个顶点，然后根据相似性规则计算出每个像素点4邻域或者8邻域的不相似度，将这些个不相似度当作相应边的权值。然后根据最小生成树算法进行像素点的合并，最终会得到若干个最小生成树，此时图像就被分为若干个区域了。
2.2 相似性度量
相似性到底该如何度量呢？一种最简单的思想就是直接利用像素点间的欧式距离来度量相似度。
(1)
其中S表示不相似度，r，g，b分别代表彩色图像的R，G，B三个分量的值。
2.3 合并原则
定义区域的内部差异函数Int(C)：
(2)
直观的理解就是内部差异的值等于最小生成树边的最大值。
定义区域间差异函数Dif(C1，C2)：
(3)
这个公式表示两个区域的差异是两个区域边界上的点所连成边的权重最小值。
定义最小区域内差异函数MInt(C1，C2)：
(4)
其中：
(5)
定义合并原则：
(6)
这个合并原则可以直观的理解为：当区域间的差异值大于最小区域内差异值时，不能将两个区域合并，否则两个区域就可以合并。
在(5)中有一可调整参数K，当K较大时，就表示两个区域的最小区域内差异很大，比较不容易合并，于是算法就倾向于将图像分成很多个小的区域，而选择较小的K时，算法会将图像分割为几个大区域。
3.算法流程
Step1：计算每个像素点的不相似度(4邻域或者8邻域);
Step2：将边按照不相似度排序得到边集E={e1,e2,…,en} ;
Step3: 初始化区域集合C为空集，初始化点集C1为空集
Step4: 从e1开始，将e1的两个顶点加入C1，并将区域子集C1加入C中 ;
Step5: 对当前的边e 进行合并判断，e的两个顶点为(Vi，Vj);
如果满足合并条件：(1)Vi与Vj不属于同一区域
(2)D(Ci,Cj)==false
将e的两个顶点加入Ci中，将Ci加入C中 ;
否则：创建新的点集Ci+1 将这条边加入到Ci+1 中，将Ci+1 加入到C中
Strp6：边集E是否为空集？空则结束，非空进行Step5 ;
算法运行结束后，会得到一个区域集合C，C中有若干个点集Ci，此时图像就被分成了若干个区域了。
**参考文献：**Efficient Graph-Based Image Segmentation