1.1选题背景及意义

从组成图像的特征分析出发，结合已有的线性代数和矩阵论的分析方法，学习三种已有的图像超像素分割方法，结合超像素分割算法，分析欠分割与过分割对场景内容理解的影响，利用ROC曲线对分割的场景区域进行描述，最后可视化超像素分割的场景图像。

1.2图像分割与超像素

在计算机视觉领域，图像分割(Segmentation)指的是将数字图像细分为多个图像子区域(像素的集合)(也被称作超像素)的过程。更精确的，图像分割是对图像中的每个像素加标签的一个过程，这一过程使得具有相同标签的像素具有某种共同视觉特性。

基于像素作为处理单元的图像分割方法，不能分割出目标区域的准确边界，只能给出目标区域的大概的位置。因为，图像是由许许多多的像素组合而成的，如果研究学者只对单一的某个像素点研究并没有什么实际意义，因此研究学者就引出了超像素的概念。超像素在计算机视觉领域已受到了广泛关注，其最重要的原因就是超像素可以有效降低图像处理过程中算法的复杂度。

1.3超像素分割算法研究现状

2003年，Ren^[2]等提出了超像素的概念。超像素分割^[3-5]是提取图像中像素的颜色信息、距离信息，并计算这些信息的相似性，借助聚类算法将相似的像素合并成连续的、容易分析的区域。2008 年，Morre A^[6]等提出了在图像的水平、垂直方向上，分别寻找最优路径，获取表征物体细节特征的超像素。此方法可以任意设置超像素分割的数目，但由于分割过程过于依赖边界图质量，从而导致时间复杂度较高。2009 年，Levinshtein^[7]等提出Turbopixel方法，使用基于几何流的水平集，逐渐扩大一组种子位置，将图像分割为网格化的超像素。此方法也可以任意设置超像素分割的数目，但获得的超像素不能很好地贴近边缘。Achanta^[8]等提出 SLIC 算法，此方法在确定初始聚类中心后，不断更新聚类中心与像素的距离函数，达到预定阈值后，采用临近合并策略消除离散的超像素，此方法可以产生贴合度较好的超像素，但会形成较多的、小的孤立点，不利于后续图像处理。

2. 研究的基本内容与方案

目前超像素算法分类标准有两种：一种是基于算法原理对超像素进行分类，可将算法分为基于图论的超像素分割算法和基于梯度下降的超像素分割算法；另外一种是基于分割出的超像素块是否有规整性对超像素进行分类。判断生成的超像素块的规整性也需花费大量的精力，故就按照第一种超像素分类方法，分别详细的介绍基于图论的超像素方法和基于梯度下降的超像素方法^[9]。

2.1基于图论的超像素分割方法

图论方法是将图像元素构成数学上合理的结构或组织，使问题的表述更加灵活，计算更加灵活。通过将一个图划分为若干子图来建模，使得它们中的每一个表示图像中有意义的感兴趣的对象。在所有现有的基于图论分割方法中的方法都涉及使用以下定义：

一个图G=(A,B)是由有限个非空的定点集A和边集B构成，其中A={a₁，a₂….a_n}是对应图像元素的一组顶点，其可以表示像素或区域。B是连接一组相邻顶点而组成的一条边。A中的每对(a_i,a_j)都是一个b_ij的子集，具有相应的重(ai,aj)量，每条边(ai,aj)都有一个权值公式w_ij=w(a_i,a_j)，每一个顶点序列从a₁到a_n都有一条代价最小的路径，图论方法就是根据这个路径来处理分割图像的。路径的代价w为:

图论的图像划分领域应用到图像分割中来，形成了基于图论的图像分割方法该方法是将原图二值化形成一个带权值的映射图。首先给定几个基本定义如图2.1所示，图中的点对应着像素点或区域，权值数的大小表示着两个点之间的相关性，通过权值的总和最小而形成的最小代价路线，这条线使得图像分割得以实现。