本文要介绍的基于图模型的图像分割算法就是一种基于区域相似性的串行算法，即属于串行区域类。在1.4中将介绍与该分割算法紧密相关的一些概念，包括图模型、区域合并技术以及聚类。

1.4 图模型的建立

图模型（graph models）,即由点和线组成用以描述系统的图形，属于结构模型，以图论作为工具，用于描述大量事物和事物之间的关系。而基于图的分割技术的基础是，一般我们会将问题呈现为G=(V,E)；其中每个结点 对应图中的像素点，E为特定相邻像素点之间的连线。每条边附有权值W(Vi,Vj)，权值大小以两端结点的特征性质（比如灰度值）作为基础的非负值。在我们的分割算法中，权值取决于相连两结点对应像素间的差异性。以此，一个图像就可以建立起与其相对应的一个图模型用于描述我们需要的图像结构。

在基于图模型的分割方法中，分割方法S将V划分成不同部分，不同部分 对应于图像中不同区域 ，其中 。对于结果我们有不同的方法来评价分割质量，主观上，我们希望的结果是同一区域内的元素是相似的，不同区域间的元素是有较大差异的，同时，不同区域的结点间有较高的边权值，以此作为其边界特征。

1.5 聚类和区域合并技术

聚类就是把具有相似性质的事物区分开加以分类，严格上讲，就是将物理或抽象对象的集合分成由类似的对象组成的多个类。基于聚类的分割算法在图像分割领域有极其广泛的应用，其思想来源于模式识别领域，适用于灰度图像、彩色图像、纹理图像等各类图像的分割。

例如，比较经典的聚类算法，动态均值法-K均值法的算法如下：

1. 随机选取K个样本，以它们的值代表每一类的均值u0, u1, …, u(k-1).

2. 按最近距离将数据分类。

3. 每次分类后计算均值u0，u1，…，u（k-1）。若与上次相等则分类结束，否则转2.

对于一个图像，基于聚类的方法要求我们在图像对应的特征空间寻找紧密的聚类结构，这些方法一般假设图像是分段线性恒定的，因为某一特征特征空间搜索聚集在一起的像素点毫无疑问具有相同之处（比如，相近的颜色）。

区域合并技术是指首先将图像分割为初始区域，然后合并相似区域，最后将图像合并为最少的均匀区域为止。通常在一个分割算法中，当相似性或一致性条件定义较为严格，或者由于噪声干扰等因素的影响，同一类别的像素可能会被分割到不同的区域，因此造成的分割区域大于期望区域数，称为过分割。对于过分割问题就可以通过相应准则下的区域合并技术进行优化，目前比较成熟的方法有基于分水岭变换法，通过提取图像中区域极小值对应的分水线，实现过分割区域合并。

1.6 本文主要内容安排

本论文的组织结主要分为以下章节：

第一章介绍本课题的选题依据及价值，简述了图像分割的基本概念和分类，说明了基于图模型的图像分割的基本构想，并介绍了和本文算法密切相关的聚类和区域合并技术。

第二章将会对基于图模型的图像分割进行详细的描述，包括目标，成对区域对比法的介绍，以及算法和其特点，重点是关于算法的实现，并对其时间复杂的进行了分析。

第三章将通过对两幅图像的分割考察算法特点和预期目标的实现，并分析了参数的取值对分割结果的影响。

第四章利用该分割算法对比较典型的道路场景进行分割和对结果进行了分析，提出一定的构想和改进方法。