2 基于图模型的图像分割

2.1 目标

本算法的主要目标在于，在基于传统的图模型的分割构想下实现对图像实现有效并时间上可接受的分割。具体体现在：

1. 分割结果在主观上是可靠的，即所得区域可以反映图像整体特征。

2. 算法是高效的，运行时间与图像的像素数目呈线性关系。

基于这一目标，为了能够对分割结果做出更加准确的评判，这里给出关于过分割和分割不足的具体定义。

定义1 如果有一对区域 ,但之间并没有边界依据，则S为过分割。

定义2 如果分割结果S的一个适当提纯不是过分割时，则S分割不足。其中分割提纯的概念是指，对于同一个图像的分割结果S1和S2，当S1中每一区域都包含于（或等于）S2中区域，称S1为S2的提纯。特别，当S1不等于S2，则称S1为S2文献综述

的适当提纯。

由以上定义，我们算法的目标可具体描述为，在高效的时间内得到对一幅图像既不是分割不足也不是过分割的分割结果。

为此，将在2.2中介绍一种基于成对区域对比法的准则作为我们如上定义中的边界依据。

2.2 成对区域对比法

准则D用于作为边界依据，那么它应当适用于图像的局部特征，可以反映出不同区域的差异在区域边界像素点上的表现。

可以定义类内差异为这部分最小生成树 中最大的权值：

 ，其中 。

    定义C1和C2的类内差异为两区域相连边上的最小权值：

 ，其中 ，并规定若C1，C2间无相连的边，则可令 。

由以上定义我们确立分割准则为： ，

其中，最小类间差异定义为： 

定义阈值函数T的目的在于，若 ，此时 ，为控制类间差异比类内差异大的程度，我们就必须引入阈值函数T，通常可将阈值函数定义为和区域大小相关的，如：

 这样，对于小的区域就会有了比较严格的的边界依据，而对于大的区域，k的影响则会减弱。同时，较大的k值意着分割结果倾向于形成较大的区域。

任何仅单独区域相关的非负函数都可以用于T的定义，甚至可以通过其实现对特定形状的分割方法。就此意义而言，T实质上是和最终分割结果所关注的各个区域的独自特征紧密相连。