基于Normalized cut的彩色图像分割方法

摘要

本发明公开了一种基于Normalized cut的彩色图像分割方法，首先对图像处理得到初始分割区域，然后利用降维将初始分割区域信息重新构建成新的图像数据，最后再利用Normalized cut直接对所得区域进行聚类。同时针对Normalized cut的权值函数计算只考虑像素颜色信息这一特点，设计了新的考虑像素趋向性关系的权值函数。可以证明，本发明方法的分割效果良好且时间复杂度相对于Normalized cut大大降低。

说明书

技术领域

本发明涉及图像处理时的分割方法，尤其涉及利用图论进行图像分割的方法，具体是一种基于Normalized cut的彩色图像分割方法，属于图像处理领域中的图像分割子领域。

背景技术

Normalized cut算法首先提出了相比于最小割准则更准确地割集准则，既考虑了集合间相似性最小同时又要考虑集合内部的相似性最大化。它很好地避免了最小割容易出现孤立点的问题，而且该准则是相对于全局优化的准则，即将一幅图像看作整体进行切割，而不是只着眼于像素级别的细节。并将求最优割集问题经数学推演转换为了求特征值系统问题，在理论上具有良好的可行性。但是它也有缺点，要生成的相似度矩阵难以处理。一幅100×100的图像最终会生成10000×10000的矩阵，虽然它是一个稀疏矩阵，大部分为0，但对它的任何操作，如求特征值和特征向量的时间仍然十分可观。

就实际分割结果来看，Normalized cut在某些时候会出现过分割或欠分割的情况。过分割表现为从图像特征上明显属于同一区域或目标物的区域被分割，而欠分割表现为一些较大区域中可能包含其他明显的细节特征需要进一步分割。

发明内容

发明目的：针对现有技术中Normalized cut算法存在的问题，本发明提供一种基于Normalized cut的彩色图像分割方法。

技术方案：一种基于Normalized cut的彩色图像分割方法，包括以下步骤：

1）将图像数据映射为图结构，并利用图论中的方法分割图像。

2）利用并查集，通过设置阈值函数将分割后的图像合并像素，得到初始分割区域。

3）将初始分割区域视作新图像中的“像素”，通过对区域的相关特征（均值，方差，面积）进行处理，得到该区域在新图像中像素的值和方位坐标。

4）利用新图像中像素的值和方位坐标，使用Normalized cut算法对区域直接进行聚类。

5）针对聚类结果，对于面积较小的区域直接与邻近的大区域合并，得到分割后的图像。

本发明的另一方面为对于传统Normalized cut算法中生成权值矩阵的权值函数的改进，包括：设计权值函数的时候，不仅考虑颜色信息，还要考虑相邻像素点之间的像素值跃变所传递的方向信息。对于一个像素来说，同属于一个集合的其他像素应该对它有正向趋向性，反之其他集合中的像素对它应该有逆向趋向性，而不在边缘附近的像素点，应该没有明显的趋向性。因此我们对于每个像素，定义了一个变量来表示该像素对周围相邻像素的趋向性(orientation)，它可以取1，-1，0三个值，1表示正趋向，-1表示逆趋向，0表示无趋向。该变量通过对图像数据进行边缘检测及正交滤波，获得每个像素点的强度变化，强度值大于0则趋向性为1，小于0为-1。

有益效果：与现有技术相比，本发明具有如下优点：

（1）本方法在Normalized cut处理图像之前，首先对像素进行初始分割，之后对初始分割的区域进行聚类，降低了Normalized cut所耗费的时间和代价，提高分割速度、且有效提高了分割效果。

（2）同时针对Normalized cut的权值函数仅考虑颜色信息的缺点，提出了考虑像素间方向趋向性的改进函数。可以有效解决图像过分割的问题。

附图说明

图1为本发明实施例的方法流程图；

图2为本发明实施例的像素趋向性示意图。

具体实施方式

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

如图1所述，基于Normalized cut的彩色图像分割方法：

首先利用并查集对图像进行初始分割，分割完成后，属于同一区域的像素点有相同的父节点。利用如下参数来描述区域信息：

1.该区域包含的像素数目，一般认为可以等价于区域面积；

2.该区域像素的像素值的平均值，同一区域的像素通常颜色相近；

3.该区域像素的像素值的方差，同一区域的像素值虽然相近，但也有必要记下其变化程度，方差正好合适；

4.该区域像素的父节点坐标，用来在Normalized cut处理时表示该区域的方位信息；

本发明方法处理的是彩色图像，而彩色空间通常有三个值，例如RGB空间有R，G，B三色，HLS空间有亮度，明度，饱和度，因此平均值和方差均有三个值。

此时得到分割后的一个个区域，每个区域由一系列参数来唯一表示。但Normalized cut需要像素的值来构建矩阵，也就是说Normalized cut需要一个个的单个值，而不是一个包含几个参数的向量。因此我们需要一个处理机制来减少参数数量，更精确的说，我们只需要一个“综合变量”来表示一个区域的所有信息，如式1所示：

Info_zone＝a*num_zone+b*mean_zone+c*variance_zone   (1)

其中Info是zone区域的综合变量，num是zone区域的像素数，mean是zone区域像素的平均值，variance是zone区域像素的方差。通过线性回归进行参数估计得到a,b,c三个参数。通过求取区域信息所构成的相关矩阵的最大特征值所对应的特征向量。其中r_ij是原来变量x_i和x_j的相关系数，R是相关矩阵。

接下来我们只要对系统求取特征值λ_i(i＝1,2,…,p)，并使其按降序排列，即可得到对应特征向量此时就是最大特征值所对应的特征向量，即而a,b,c参数分别对应特征向量的各分量。

得到分割好的区域信息，在这里将分割好的区域称之为“超像素”，而“超像素”的像素值该区域的综合信息，“超像素”的方位信息我们用这个区域父节点的坐标来表示。

因为Normalized cut算法处理的是图像数据，而图像数据是二维矩阵存储的，现在有的只是一维的一系列的“超像素”像素值，所以需要构建一张“超图”。从数学上来说就是需要将一维数据转换为二维数据。

现在假设原来图像宽W高H，初始生成“超像素”的数目是g个，u_i(x_i,y_i)是第i个“超像素”的像素值，其中x_i,y_j是这个“超像素”区域的父节点的坐标。首先为简便起见依然构建大小的矩阵，并定义

$>\left(\begin{array}{c}{x}_i^{\text{'}}=\frac{x_i}{W/\sqrt{g}+1}\\ y_i^{\text{'}}=\frac{y_i}{H/\sqrt{g}+1}\end{array}\right)---\left(3\right)$>

其中（x′_iy′_i）是新的矩阵中的坐标位置。这样就得到了全新的“超图”，里面的像素就是“超像素”。

Normalized cut中用到的权值函数都仅仅考虑了像素的颜色信息。我们在设计权值函数的时候，不仅考虑颜色信息，还考虑了相邻像素点之间的像素值跃变所传递的方向信息。

对于像素v_i来说，同属于集合A的其他像素应该对它有正向趋向性，反之集合B中的像素对它应该有逆向趋向性，而不在边缘附近的像素点，应该没有明显的趋向性。

因此对于每个像素p_i，定义了一个变量o_i来表示该像素对周围相邻像素的趋向性(orientation)，它可以取1，-1，0三个值，1表示正趋向，-1表示逆趋向，0表示无趋向，如图2所示。该变量是通过对图像数据进行边缘检测及正交滤波，获得每个像素点的强度变化，强度值大于0则趋向性为1，小于0为-1。

此时权值w_ij表示的就不单是像素i和像素j的关系了，还要考虑像素j的邻域像素的权值影响。因此可以得出新的权值函数：

其中是求取·的欧几里德范数的算符。通过全新的权值函数，可以构建新的相似度矩阵，之后利用Normalized cut完成图像分割。