基于SLIC与分水岭算法的彩色图像分割

1 引言

图像分割是将图片中有意义或感兴趣的目标提取出来，用于图像后续处理。由于外界环境的影响以及图像自身存在的问题，使得图像分割成为研究的热点和难点。目前图像分割算法主要有以下几种：基于区域的分割算法、基于边缘的分割算法、基于阈值的分割算法和基于聚类分析的分割算法等。分水岭分割算法是一种典型的基于区域分割算法，具有实现简单以及能够很好提取轮廓的特点，但图像过分割问题较严重。为了解决过分割问题，高丽等人^[1]提出了一种改进的基于标记的分水岭分割算法，该算法一定程度上抑制了过分割现象，但是存在边缘定位不准的问题；卢中宁等人^[2]提出了一种基于形态学梯度修正和区域合并的分水岭分割算法，减少了过分割并使分割后的区域更有意义，但是算法耗时较长，运行效率低；余旺盛等人^[3]提出了一种基于标记分水岭和区域合并的分割算法，较好地解决了图像过分割现象，但数据处理量大。针对以上改进算法存在的不足，并结合Achanta等人^[4]提出的简单线性迭代聚类(simple linear iterative clustering，SLIC)方法，本文提出了一种基于SLIC与分水岭算法的彩色图像分割算法。

通常人眼在观察外界事物时，是根据颜色特征进行划分的，即以相似的像素集合为准，并不是单个像素点。因此，Ren等人提出了“超像素”的概念^[5]。在一幅图像中，相邻像素点特征相似即划分为同一个超像素，特征不相似即划分为不同的超像素。每个超像素都是连续的，并且能够保留图像的颜色、纹理等特征信息。因此，利用超像素替代像素点进行图像分割，已经被越来越多地应用到了图像分割的预处理步骤中。目前，常见的超像素分割方法有，Shi等人^[6]于2000年提出了归一化分割(normalized cut, N-Cut)方法；Felzenszwalb等人^[7]于2004年提出的Graph-based方法；Levinshtein等人^[8]于2009年提出的Turbopixel方法；Achanta等人在文献[4]中提出的简单线性迭代聚类(SLIC)方法等。在上述超像素分割算法中，SLIC算法处理速度快，并且超像素块能够很好贴合目标的边界，以及能够获得形状、大小基本相同的超像素块。另外，SLIC算法能够在预处理阶段消除伪影和噪声的影响，一定程度上能够防止分水岭算法产生过分割现象。由于采用SLIC超像素分割对输入的图像进行预处理，还能够减少算法计算复杂度^[9]，因此本文拟利用SLIC和分水岭算法相结合的方法对图像进行分割，并提出了一种自适应选取阈值的方法减小背景噪声对分割结果的影响^[10]。该算法首先对彩色图像计算图像复杂度，进而计算出预分割的超像素个数K值，对图像进行SLIC超像素分割；之后对超像素分割后的图像求梯度图像，再对梯度图像进行阈值处理，得到具有极小值标记的图像，并对此利用形态学极小值标记提取方法；最后对标记提取后的图像利用分水岭分割算法得到最终分割图像，来抑制过分割问题。通过对Berkeley数据库中的图片进行统计实验分析发现，本文算法具有较理想的分割效果。

2 基本理论 2.1 简单线性迭代聚类算法

2003年，Ren等人在文献[5]提出了超像素的概念，是由一系列相邻并具有相似特征的像素组成的有一定意义的不规则像素块。超像素的提出也有效减少了后续处理中无足轻重的冗余信息，不仅简化了图像的拓扑结构，而且降低了后续处理步骤的复杂度。简单线性迭代聚类(SLIC)方法巧妙地利用K-means算法，以种子点为中心局部聚类，迭代超像素块，是一种基于梯度上升的超像素分割算法。SLIC算法将图像从RGB彩色空间转换到CIELab颜色空间，将每个像素的颜色值和坐标组成一个5维空间向量^[11][l, a, b, x, y]，然后对5维特征向量构造距离度量，这种新的距离度量能够使超像素的形状、大小有规则。SLIC算法根据人为指定预分割的超像素个数K以及图像中所有像素数N，得到每个超像素的大小为N/K，相邻超像素之间的距离为 \( S = \sqrt {{N \mathord{\left/ {\vphantom {N K}} \right. } K}} \) ，由S来选定K个初始聚类中心 \({C_i} = [{l_i},{a_i},{b_i},{x_i},{y_i}]\) 。然后计算从每个聚类中心到2S×2S区域内的像素的距离，距离计算公式^[11]如下：

\({d_{{\rm{color}}}} = \sqrt {({l_j} - {l_i}) + ({a_j} - {a_i}) + ({b_j} - {b_i})} ,\)(1) \({d_{{\rm{space}}}} = \sqrt {({x_j} - {x_i}) + ({y_j} - {y_i})} ,\)(2)

其中： \({d_{{\rm{color}}}}\) 表示颜色距离， \({d_{{\rm{space}}}}\) 表示空间距离。因此，距离度量公式^[11]如下：

\({D_m} = \sqrt {{d_{{\rm{color}}}} + {{({d_{{\rm{space}}}}/S)}^2} \cdot {m^2}} ,\)(3)

其中 \(m\) 表示权衡颜色相似性和空间邻近度之间的重要性。

根据式(1)~式(3)求得每个像素点和周围种子点的距离，并取距离最小值对应的种子点作为该像素点的聚类中心。在利用SLIC算法进行分割时是一个迭代过程，并且通过实验分析发现，执行10次左右可以获得较理想的结果。最后由于进行分割后图像的连通性较弱，因此将少于某一阈值的超像素合并到它邻近的超像素^[12]。该算法得到的超像素分布规则可控制性好且复杂度较低，但不能分割出目标区域，为后续图像处理增加了难度。

2.2 分水岭算法

分水岭(Watershed)算法开始是由Digabel和Lantuejoul^[13]应用到图像的处理中，后来又由Lantuejoul和Beucher^[14]共同探讨研究将分水岭算法运用到灰度图像分割中，给分割提供了一种有用的方法。直到1991年，Vincent等人对分水岭算法计算速度进行改进后，分水岭算法才得到了广泛关注和应用。该算法的基本思想是将图像看作一幅地形图，其中每一像素的灰度值表示该点的海拔高度，此外，算法过程是模拟浸入过程来说明的^[15]。根据分水岭算法原理，分割算法分为两种：一种是自上而下模拟降水算法^[16]，如图 1，一种是自下而上的模拟泛洪算法^[16]，如图 2。

[Image omitted: See PDF]

[Image omitted: See PDF]

近年来，分水岭算法因其在处理图像分割时运行简单和轮廓提取效果好的特点成为了研究热点^[17]，并且在许多领域得到了广泛应用。由于分水岭分割算法对噪声和其他干扰比较敏感，因此直接利用分水岭算法会产生过分割现象，使分割目标不能被分割出来，造成分割结果在后续处理中无意义。如何解决这个问题也一直是研究的热点，目前常见的解决方法主要有两种：一种是利用标记控制方法，对图像的前景和背景进行标记，并通过图像滤波进行标记提取；另一种是通过区域合并的方法，对图像利用分水岭分割算法分割后，再利用合并准则对图像进行区域合并。

3 基于SLIC与分水岭算法的彩色图像分割

为了解决传统分水岭算法产生的过分割导致图像分割信息无法使用的问题，本文提出了一种基于SLIC和分水岭算法的彩色图像分割算法。本文算法对图像进行基于SLIC算法的超像素分割预处理，结合对梯度图像阈值处理和分水岭分割，最终得到较理想的分割结果。由于SLIC算法能够利用图像的冗余信息，通过聚类的思想有效地消除伪影和噪声引起的影响，进而可以抑制分水岭算法过分割的产生。但SLIC算法在进行超像素分割时，需要人工设定预分割的超像素个数K，不利于算法的自适应性。因此本文首先提出了一种自适应选取K值的方法，通过图像复杂度和图像的大小计算K值以提高算法效率；然后针对图像中存在的噪声问题，提出了一种自适应阈值的方法去除图像中背景和边缘处的噪声；最后对处理后的图像利用分水岭分割算法得到分割后的图像。

3.1 图像复杂度计算

图像复杂度(Image complexity)是指在一幅给定图像中发现或提取感兴趣目标的困难程度。广义集合的内部复杂度的计算公式^[18]如下：

\(C = - \sum\nolimits_{i = 1}^k {{n_i} \cdot \log ({n_i}/N)} ,\)(4)

其中： \(C\) 代表复杂度， \(k\) 代表广义集合内不同标志值的个数， \({n_i}\) 代表灰度值为i的像素点个数， \(N\) 代表整幅图像内像素点的个数。

针对图像数据本身特点，引入信息熵，即某种特定信息出现的概率^[19]，熵值越大，则图像越复杂，反之，越简单。信息熵(Ent，用E_Ent表示)的计算式^[18]：

\({E_{{\rm{Ent}}}} = - \sum\nolimits_{i = 1}^k {{{{n_i}} \mathord{\left/ {\vphantom {{{n_i}} {N \cdot \log ({n_i}/N)}}} \right. } {N \cdot \log ({n_i}/N)}}} = C/N。\)(5)

灰度共生矩阵(Gray level co-occurrence matrix，GLCM)是一种通过研究灰度的空间相关特性来描述纹理的方法^[20]。为了能够恰当地衡量图像的复杂度，可以用一些参数来表示灰度共生矩阵的特征。其中具有典型度量特征的参数有：能量(E)、对比度(Con，用C_Con表示)、相关度(Cov，用C_Cov表示)。

由于图像复杂度的大小与图像的信息熵和灰度共生矩阵的特征参数有关，为了更好地计算图像复杂度，引入了权重，并且对信息熵和特征参数进行加权求和，其中信息熵和对比度的权重为1，相关度和能量的权重为-1。从而使得图像复杂度的大小能够客观地反映图像分割的难易程度^[21]。图像复杂度T_k计算式^[21]为

\({T_k} = {E_{{\rm{Ent}}}} + {C_{{\rm{Con}}}} - E - {C_{{\rm{Cov}}}},\)(6) \(其中：\,\,\,E = \sum\limits_{i = 0}^{m - 1} {\sum\limits_{j = 0}^{n - 1} {{Q^2}(i,j,d,\theta )} }, \)(7) \({C_{{\rm{Con}}}} = \sum\limits_{i = 0}^{m - 1} {\sum\limits_{j = 0}^{n - 1} {\left[ {{{(i - j)}^2}Q(i,j,d,\theta )} \right]} } ,\)(8) \({C_{{\rm{Cov}}}} = \sum\limits_{i = 0}^{m - 1} {\sum\limits_{j = 0}^{n - 1} {\frac{{i \times j \times p(i,j,d,\theta ) - {u_1} \times {u_2}}}{{d_1^2d_2^2}}} } ,\)(9)

式中： \(Q(i,j,d,\theta )\) 是通过灰度共生矩阵归一化处理得到；m表示图像在平面内x轴方向上的像素数；n表示图像所在平面内y轴方向上的像素数； \(\theta \) 表示灰度共生矩阵的生成方向，可以取0°、45°、90°、135°；

\({u_1} = \sum\nolimits_{i = 0}^{m - 1} {\sum\nolimits_{j = 0}^{n - 1} {p(i,j,d,\theta )} } \) ； \({u_2} = \sum\nolimits_{j = 0}^{n - 1} j \sum\nolimits_{i = 0}^{m - 1} {p(i,j,d,\theta )} \) ； \(d_1^2 = \sum\limits_{i = 0}^{m - 1} {{{(i - {u_1})}^2}\sum\limits_{j...