基于超像素的谱聚类图像分割算法

1、小组学习汇报小组学习汇报报告人报告人: :周静波周静波2011年年5月月27日日报告提纲基于超像素的谱聚类图像分割算法基于超像素的谱聚类图像分割算法显著性方法显著性方法问题的提出 谱聚类算法属于图论的范畴，因此不可避免地会存在图论分割算法的缺点，即随着图中节点数的增大，问题的求解将变得异常费时。由于谱聚类算法将图像的每一个像素点看做图中的一个节点，图像越大，节点越多，求解越困难。另外，谱聚类包含对成对相似矩阵进行特征分解，对一幅像素点总数为n的图像来说，成对相似矩阵的维数为n*n。图像较大时，一般计算机无法存储谱聚类算法需要的成对相似矩阵。因此，谱聚类算法不适合对较大的图像进行分割，限制了谱聚

2、类算法在图像分割中广泛应用。降低图像的分辨率可以减少图的节点数和相似矩阵的维数，但是同时也会导致图像信息的丢失，降低了分割的精度。相关工作 Shi从图论的角度提出了标准分割（Normalized Cut）方法，该算法最先将谱聚类算法应用到图像分割当中。标准分割算法先降低图像的分辨率，然后利用谱聚类算法进行分割。 Chang等人结合鲁棒的统计方法提出了基于通道的谱聚类图像分割算法，该方法提出一种新的度量方法来计算像素点之间的相似性，提高谱聚类算法在图像分割中的分割精度。 Fowlkes在标准分割框架下通过利用Nystrm估计来解决计算机存储问题。该方法在图像像素的子集与整个图像之间计算成对相似性

3、来对图像进行分割，虽然一定程度上缓解了计算机存储问题，但是分割的精度比较差。 Lihi等提出在谱聚类算法中利用局部尺度来计算像素点之间的相似性，减少谱聚类算法的参数个数。相关工作 Frederick Tung提出将图像分割成32*32的子图像，每个子图像之间存在一定的重叠。在每一个子图像上面采用谱聚类对像素点进行分割，然后通过随机整体一致算法对子图像进行合并得到初始分割，最后采用谱聚类算法对初始分割进行聚类。这种方法有效的解决了计算机存储问题，算法的空间复杂度为 。 缺点：该方法需要对每一块子图像作一次谱聚类，并且采用随机整体一致算法对有重叠的子图像进行合并，因此增加了整体算法的时间复杂度，降

4、低了该方法的实用性。 )(),(max2dOnO本文算法 本文利用超像素算法先对图像进行初始分割，将图像分割成许多超像素。对相邻的两个超像素之间的规范化颜色直方图计算Bhattacharyya系数，并将Bhattacharyya系数作为图中对应结点的边的权值。通过谱聚类算法对图进行分解，得到分割结果，最后对结果进行合并处理。超像素 采用Alex Levinshtein提出的图像超像素描述方法 给定超像素个数为K，我们先选择K个像素点作为种子像素点分布在整个图像中，种子之间的距离近似等于 ，其中N表示图像的总像素数。种子像素点周围相距1个像素点的所有像素点作为初始边界。初始边界向外距离4个像素的

5、区域作为曲线演变的范围。为避免种子像素点刚好落在图像梯度较大的区域，影响最终的曲线演化结果，我们计算种子节点周围的图像梯度，对梯度变化较大的节点进行扰动。 定义平滑连续函数 ，超像素边界的演化满足如下的水平集基本方程： KN /22), 0:St超像素tSSnBInn1其他界处于两个超像素点的边, 1),(, 0),(yxyxSB),(*),(),(),(1 ),(yxyxyxyxyxSI),(yx为局部相似函数 / ),(),(yxEeyx1*),(IGIyxE232222)(2yxxyyxyyxyxx/超像素 当超像素边界的颜色梯度变化较小时， 较大，超像素边界向外扩张的速度越快；反之，扩

6、张速度越慢；当两个近邻的超像素边界相遇时，超像素边界会停止演化；如果超像素边界越过颜色梯度最强的区域时，超像素边界会向内收缩。 对曲线演变范围内所有的点计算（2），将 的所有点归入到相应的超像素，然后将得到的超像素的边界作为新的初始边界，初始边界外相距4个像素的所有像素点作为新的曲线演变范围，如此反复迭代直到超像素边界停止演变为止。 超像素算法需要设置超像素个数，超像素个数越多，使得生成的图的节点数越大，谱聚类算法中的拉普拉斯矩阵维数越大。相反，如果超像素个数较少，则容易形成弱分割，最终影响分割效果。IS0),(1yxn超像素超像素相似性计算本文通过RGB颜色空间来计算颜色直方图。首先，将R、

7、G、B三个颜色通道都分成16个等级，每个超像素都在 维空间中计算直方图。对直方图进行规范化后，我们采用Bhattacharyya系数来度量它们的相似性。假设 是两个规范化的直方图，那么它们的Bhattacharyya系数为：当然，利用颜色直方图计算超像素之间的相似性也会存在问题。两个不相似的超像素可能具有相似的颜色直方图。为降低这种情况的发生概率 4096161616qp,muuuqpqp1),(其他相邻, 0,jiWijij谱聚类谱聚类时需要确定类别数，当 时，产生过分割现象；当 时产生弱分割现象 我们先选择 ，对任意的 ，计算选择阈值 ，如果 ，合并trueCc trueCc ),(jic

8、c),(jiccjicc ,trueCc ) 1 , 0(jicc ,算法复杂度分析算法复杂度分析 本文提出先将图像表示成超像素，然后对超像素进行谱聚类，因此算法的时间复杂度主要包括两个方面：计算超像素时间复杂度为 ，N为图像像素点个数；而谱聚类算法的时间复杂度为 ，其中e为谱聚类算法中K均值迭代次数，M为超像素个数。由于 ，所以整个算法的时间复杂度近似等于 。 本文算法的空间复杂度只与图像的原始大小和超像素个数有关。)(NO)(eMONM )(NO实验结果实验结果(a)(b)(c)(d)(a)(b)(c)(d)实验结果实验结果(b)(d)(a)(c)(a)(b)(c)(d)(a)(b)(c)

9、(d)(b)(d)(a)(c)实验结果实验结果结论 本文利用超像素算法先对图像进行初始分割，将图像表示为超像素，每一个超像素代表一个区域。然后采用颜色直方图描述超像素，利用Bhattacharyya系数计算超像素之间的相似性。最后，采用谱聚类算法将超像素合并成有意义的区域。通过上述方法来降低图像大小对谱聚类算法的影响，从而扩大谱聚类算法在图像分割中的应用。通过实验证明本文算法不仅可以得到较好的分割结果，而且在处理彩色图像时具有明显的优越性 。显著性F. Liu, M. Gleicher, Region enhanced scale-invariant saliency detection, in: Proceedings of IEEE International Conference on Multimedia & Expo (ICME), 2006。 文章做法： 利用MEANSHIFT算法对图像进行分割，形成许多区域； 对图像做显著性分析； 将每个区域中显著性值在整个区域中做平均； 问题： 显著性结果严重依赖于MEANSHIFT分割结果 显著性目标的边界不够清晰显著性 我的想法： 先对图像做显著性分析，并进行二值化； 初