彩色图像超像素分割方法论文(共26页)

1、中国石油大学（华东）本科毕业设计(论文)本 科 毕 业 设 计（论文(lnwn)）题 目：彩色(cis)图像(t xin)超像素分割方法副标题学生姓名：窦长红学 号：11072203专业班级：软件工程11-2班指导教师：李宗民2015年 6月14日中国石油大学（华东）本科毕业设计(论文)彩色(cis)图像(t xin)超像素分割(fng)方法副标题摘 要在进行图像处理任务时，往往会需要大量的复杂计算，若是以像素为单位会造成时间上和空间上的极大消耗。超像素的提出，很好的解决了这一问题，在后续的图像处理任务中以超像素为单位将会大大降低算法的复杂度。本文主要分析和研究了两种比较好的分割算法，即SLI

2、C算法和SEEDS算法，并对它们进行了编码实现和分析比较。SLIC算法通过将搜索范围限制在一个小范围内，来提高运行速度，但是这样会造成过分割的问题，本文针对这一问题对算法进行了改进。最后，本文利用超像素分割的评判标准对SLIC算法和改进的SLIC算法进行了客观比较。实验结果表明，改进后的算法达到了更好的效果。关键词：超像素；聚类；K-means；SLIC；SEEDSSuperpixels segmentation methods of color imageAbstractIn the image processing tasks, it requires massive calculatio

3、n frequently, and will cause a great lot of consumption on time and space if dealt by pixels. The arising of superpixels, has nicely resolved this problem, it can greatly reduce the complexity of the calculation in the subsequent image processing tasks. This paper puts focus on introducing two bette

4、r superpixels segmentation algorithms SLIC and SEEDS. SLIC algorithm can achieve linear complexity by reducing the superpixel search regions. But this will cause the over-segmentation. So this paper puts forward the improvement for this problem. Finally, in this paper, the different segmentation alg

5、orithms have compared objectively.Keywords：Superpixels；Clustering；K-means；SLIC；SEEDS目 录目录 TOC o 1-3 h z u HYPERLINK l _Toc435018663 目 录 PAGEREF _Toc435018663 h 4 HYPERLINK l _Toc435018664 第1章 引言 PAGEREF _Toc435018664 h 1 HYPERLINK l _Toc435018665 第2章 超像素的应用 PAGEREF _Toc435018665 h 2 HYPERLINK l _Toc

6、435018666 2.1 目标识别 PAGEREF _Toc435018666 h 2 HYPERLINK l _Toc435018667 2.2 遥感图像分类 PAGEREF _Toc435018667 h 2 HYPERLINK l _Toc435018668 2.3 医学影像 PAGEREF _Toc435018668 h 2 HYPERLINK l _Toc435018669 第3章 超像素方法综述 PAGEREF _Toc435018669 h 4 HYPERLINK l _Toc435018670 3.1 基于图论的算法 PAGEREF _Toc435018670 h 4 HYP

7、ERLINK l _Toc435018671 3.1.1 Normalized Cuts算法 PAGEREF _Toc435018671 h 4 HYPERLINK l _Toc435018672 3.1.2 Superpixel Lattice算法 PAGEREF _Toc435018672 h 4 HYPERLINK l _Toc435018673 3.1.3 Graph-based算法 PAGEREF _Toc435018673 h 4 HYPERLINK l _Toc435018674 3.2 基于梯度上升的算法 PAGEREF _Toc435018674 h 4 HYPERLINK

8、l _Toc435018675 3.2.1 Mean-shift算法 PAGEREF _Toc435018675 h 5 HYPERLINK l _Toc435018676 3.2.2 Turbopixels算法 PAGEREF _Toc435018676 h 5 HYPERLINK l _Toc435018677 3.2.3 SEEDS算法 PAGEREF _Toc435018677 h 5 HYPERLINK l _Toc435018678 3.3 超像素算法比较 PAGEREF _Toc435018678 h 7 HYPERLINK l _Toc435018679 3.3.1 计算复杂度

9、 PAGEREF _Toc435018679 h 7 HYPERLINK l _Toc435018680 3.3.2 分割效果 PAGEREF _Toc435018680 h 7 HYPERLINK l _Toc435018681 第4章 SLIC分割算法 PAGEREF _Toc435018681 h 9 HYPERLINK l _Toc435018682 4.1 SLIC算法基本原理 PAGEREF _Toc435018682 h 9 HYPERLINK l _Toc435018683 4.2 SLIC算法步骤 PAGEREF _Toc435018683 h 9 HYPERLINK l _

10、Toc435018684 4.3 SLIC距离计算 PAGEREF _Toc435018684 h 11 HYPERLINK l _Toc435018685 4.4 孤立点处理 PAGEREF _Toc435018685 h 11 HYPERLINK l _Toc435018686 4.5 SLIC算法优缺点 PAGEREF _Toc435018686 h 12 HYPERLINK l _Toc435018687 4.6 SLIC算法改进 PAGEREF _Toc435018687 h 12 HYPERLINK l _Toc435018688 4.6.1 改进原理 PAGEREF _Toc43

11、5018688 h 12 HYPERLINK l _Toc435018689 4.6.2 改进结果 PAGEREF _Toc435018689 h 13 HYPERLINK l _Toc435018690 第5章 实验结果与分析 PAGEREF _Toc435018690 h 14 HYPERLINK l _Toc435018691 5.1 实验环境 PAGEREF _Toc435018691 h 14 HYPERLINK l _Toc435018692 5.2 SLIC算法与SEEDS算法的比较 PAGEREF _Toc435018692 h 14 HYPERLINK l _Toc43501

12、8693 5.3 改进SLIC算法运行结果 PAGEREF _Toc435018693 h 15 HYPERLINK l _Toc435018694 第6章 结论 PAGEREF _Toc435018694 h 18第1章 引言第1章 引言(ynyn)图像分割基于像素的强度、颜色、纹理等特征的相似度把图像分割为多个子区域（超像素）。超像素算法把图像中的像素分割为有感知意义的原子区域，从而替代传统像素网格的刚性结构。超像素可以(ky)获取大量的图像冗余信息，从而极大地减小接下来图像处理任务的复杂度，是后续图像分析任务的预处理步骤1。现今，超像素已经成为了许多计算机视觉任务的关键一步(y b)，在

13、身体模型估计、目标定位、深度估计等领域应用十分广泛。在2003年，任和马利克提出了超像素的概念2，他们定义超像素是按照经典完全形态理论组合像素，从而对图像进行过分割的结果。现今有很多超像素算法，它们都各有各的优、缺点，因此他们的适用领域都不尽相同。如果边缘保持度是最重要的需求，那么基于图论的方法也许是最好的选择。对于所有的需求而言，很难说对哪个算法效果是最好的，但理想中的超像素算法通常具有以下优势：1)超像素应该与图像边缘相吻合。2)当作为一个减小计算复杂度的预处理步骤时，超像素算法必须要计算迅速、节省内存、便于使用。3)当用于分割时，超像素算法既要运行迅速又要有高质量的分割效果。一个具有较高

14、使用价值的超像素算法，必须要效果好、运算速度快且简单易用。然而，现今的超像素算法很少能完全满足这些需求，存在分割质量差、内存消耗大、需要多重难调参数等多种问题。本文第三章对当前主要的算法做了简单的分析和比较，评估了他们的速度、边界保持度以及对分割效果的影响。经过比较，可以发现SLIC算法是比较好的一个算法。SLIC算法采用改进后的K均值聚类算法来更高效地产生超像素。SLIC算法复杂度只有O(N)。SLIC算法不仅非常的简单易用，而且在伯克利数据集上运行时，SLIC边界保持度仍然达到了当前最好算法的水平。当在PASCAL和MSRC数据集上运行时，SLIC算法的分割效果超过了当前的所有算法。本文主

15、要研究实现了彩色图像超像素分割算法中的SLIC算法，将其与其他先进算法进行比较。第2章 超像素的应用第2章 超像素(xin s)的应用 超像素(xin s)分割是一种越来越流行的图像与处理步骤，在计算机视觉领域得到了广泛的应用，比如图像分割，图像分析，3D重建和目标跟踪等领域(ln y)。与基于像素点相比较，基于超像素的方法跟符合人类的认知，并且消除了巨大的冗余信息。人们普遍认为，超像素分割需要具备一下特点：首先，超像素应该具有很好的边界保持度，并且每个超像素都不应该与多个目标有交集。其次，超像素分割作为一个预处理步骤，必须要有足够小的算法复杂度，也就是说运行时间要足够短。最后，对人类视觉认知

16、比较重要的图像全局信息也要被适当的考虑在内。 基于超像素而非像素点进行图像分析与处理，能极大提高处理的速度，在某些情况下甚至可以提高效果。比如，一些基于图的算法采用超像素时能使速度加快2到3倍。 随着硬件的不断发展，通过计算机来进行图像处理与分析变得越来越重要，比如在医学影像、数码摄像、监控、遥感等领域得到了广泛应用。进行图像分析与处理时，超像素分割是基本的与处理步骤。在实际应用时，超像素分割需要有好的分割效果和快的分割速度。下面介绍超像素在几个典型的视觉任务中的应用，包括目标识别、遥感图像分类和医学影像分割。在进行任务时，超像素能够提升算法的性能，并且能减少计算成本。就本文考虑到的应用而言，

17、SLIC算法总体要好于其它的先进的超像素方法。2.1 目标识别目标识别是指从其它目标中区分出特殊目标的过程。目标识别技术已普遍应用于空间技术、国民经济和国防等范畴。它包括两个方面：两个非常相似目标的识别、一种类型的目标和其他类型目标的识别。合理的进行超像素分割，是目标识别面对的首要任务。比如，在按下智能数码摄像机的快门时，要求能够在较短的时间内完成目标识别，并按照识别结果进行参数调节，从而实现智能拍摄。因此，就要求超像素分割算法务必是极快的。2.2 遥感图像分类只要是纪录了各种地物 HYPERLINK /view/1015.htm t _blank 电磁波大小的胶片（或相片），都称为遥感影像，

18、在遥感中主要是指 HYPERLINK /view/1314412.htm t _blank 航空像片和 HYPERLINK /view/967228.htm t _blank 卫星相片。随着遥感技术的不断发展，高分辨率的遥感影像广泛应用于各种领域，并发挥着重要的作用比如环境、测绘等。传统的遥感图像分类是基于像素点的，这种方法计算量大，并且对于高分辨率的图像分割效果比较差。因此，要对高分辨率遥感图像进行场景分类，分类最小单元不能再取像素点而要选用超像素。这样消除了基于像素点带来的噪声和边界误判现象。为了充分利用高分辨率遥感影像的信息，从而更加准确的对目标进行分类，因此深入研究基于超像素的遥感图像

19、分类方法有很重要的意义。2.3 医学影像医学影像是指以非侵入性的方式获得人体内部组织图像的技术，以便为医疗(ylio)或医学研究服务。它通常(tngchng)包含两个研究方向：医学(yxu)成像系统和医学图像处理3。医学影像经过计算机的处理后，能够将人的身体结构数字化，实现对人体结构细节的精确模拟，为病情的诊断提供更精确的信息，从而提高诊断的准确性。如图2-1(a)肝CT肿瘤图，通过计算机的算法进行定量分析，准确的将肿瘤边界定位3。肿瘤影像进行图像分割处理后，能够得到肿瘤直观清晰的三维影像信息，以便进行进一步的诊断和治疗3，如图2-1(b)所示。再如图2-1(c)，利用图像分割技术可将大脑小脑

20、的脑白质、脑灰质、脑干、脑汁等分割开来，经过计算机图像处理呈现图2-1(d)所示的三维立体影像，大脑，小脑等清晰可见，为医学领域很多脑分析、脑治疗等提供直观的三维影像信息3。(a)肝CT肿瘤图 (b)肝CT肿瘤三维影像 (c)脑MR图 (d)脑MR三维图医学影像分割是指采用数字化仪器和计算机，对影像中发生病变的部位进行科学、精确的分析，提取出影像中感兴趣的特殊目标或组织，从而实现三维模型重建。医学影像分割的关键是怎样完成对影像数据的精确、迅速分割。三维重建模型的精确性将会受到影像分割效果的直接影响。所以，如何为不同的人体部位和器官，找到合适的分割方法是非常重要的。现今，很多研究人员都提出了许多

21、很好的图像分割方法。第3章 超像素方法综述第3章 超像素(xin s)方法综述(zngsh)超像素(xin s)分割算法大体上可以分为两类：基于图论的算法和基于梯度下降的算法。3.1 基于图论的算法基于图论的算法，将图像看作带权的无向图G=V，E，W，其中V为图的结点集，也就是图像的像素集，E为两两结点间的边集，而W代表了两结点之间的权重值，权重值一般通过像素颜色、亮度、纹理等特征来决定4。Normalized Cuts5、Superpixels Lattices6、Graph-based7方法等都属于这种类型。3.1.1 Normalized Cuts算法Normalized Cuts算法也

22、称为归一化割算法，该算法通过估计图像的纹理和轮廓，迭代的对图像进行分割。归一化割算法将图像分为几个区域，不同区域之间的相似度用cuts来表示。石和马利克8提出了一个规范化的标准来衡量和计算分割效果，并且计算出NCuts值来作为衡量标准。Normalized Cuts算法生成的超像素大小一致、整齐紧凑，但是复杂度很高，该算法复杂度为O（N3/2），其中N为像素的个数。具体算法步骤：1. 给定一幅图像，映射为一个加权无向图，为每一条边构造一个权值函数，以便来衡量节点之间的相似性。2. 利用最小特征值求出对应的特征向量3. 找出具有最小特征值的特征向量y，利用特征向量y 将图一分为二，在向量y 中选

23、择一个分割数值，将特征向量y中大于该数据的节点存放在B中，其余的放在A中。这样就可以将图像分割成两部分了。4. 接下来判断分割后的结果是否需要再进行分割，如果需要继续分割，则利用递归的方式进行再分割。3.1.2 Superpixel Lattice算法Superpixel lattice 算法需要输入的参数是图像边界图，寻找图像的最小权重路径，在边界代价图最小处分割图像。Superpixel Lattice算法通过寻找最佳垂直或水平分割路径，不断地把图像从垂直和水平方向进行二分形成一个超像素网格（一个规则的超像素点阵）。该算法虽然可以产生大小近似相等、整齐紧密的超像素，但是超像素质量和生成速度

24、很大程度上取决于先前估计的边界图。Superpixel Lattice算法的复杂度为O(N2logN)。3.1.3 Graph-based算法Graph-based算法采用最小生成树的方法来产生超像素，算法复杂度为O(NlogN)，比Normalized Cuts算法要快很多，但是生成的超像素大小不一致、形状不紧凑。算法步骤：1. 对输入彩色图像的每个颜色通道进行平滑，平滑的目的是使聚类中的像素点更紧密地连接在一起。2. 将图像映射为图G = (V，E)。3. 分割：将图像分割成很多的小项，要使同一小项中的元素相似度较高。4. 对图中所有边按非递减的顺序进行排序。5. 对排序后每条边，按非递减

25、的顺序找到其连接的两个节点所属的小项。利用最小生成树迭代分割图像。6. 后续对较小的小项进一步处理。7. 对每个小项挑选一种随机颜色用来表示用于区分。3.2 基于(jy)梯度上升的算法基于(jy)梯度上升的算法，首先(shuxin)要初始化一个大体的、不精确的聚类，在当前迭代中利用梯度上升的方法，精炼上一次迭代产生的聚类，直至达到收敛。Mean-shift9、Turbopixels10以及seeds11等方法都属于这一类。3.2.1 Mean-shift算法Mean-shift算法又称均值漂移算法，通过把特征空间中的所有数据点迭代地移动到核质心，执行梯度上升算法来高效地产生超像素。均值漂移算法

26、不能对超像素的个数和紧密程度进行直接地控制，随着输入参数的不同生成的超像素大小会发生改变。该算法复杂度为O(N2)。执行均值漂移算法，数据集中的所有点都可以作为初始点，分别执行均值漂移算法，能够收敛到同一个点的分为一类，它能对任何分布、任何维度的采样行进行聚类12。均值漂移算法属于统计聚类方法，在分割时，第一步是将图像中的像素转换为特征空间的采样点。对于彩色图像，需要结合图像的空间和色彩信息，则由2 维的位置空间和3 维的色度空间组成特征空间，像素就转换成一个5 维特征空间采样点，然后对采样点进行均值漂移聚类12。3.2.2 Turbopixels算法Turbopixels算法采用几何流水平集

27、的方法，不断扩大图像平面上的种子点数量，从而产生超像素。该算法的复杂度为线性复杂度O(N)，产生的超像素整齐紧密、大小统一、边界吻合度高，总体来说分割质量较好。基本步骤：1.指定要分割的超像素个数K，将图像均分为K 个网格，每个网格中放置一个初始种子点。2.由于图像并不是均匀分布的，所以初始种子点可能会落在图像上的边界处，为了解决这个问题，可将种子点的位置打乱，使其远离梯度值较高的区域。3.迭代以下步骤，直至不再有进一步的演化：a）第T 次演化边界b）估计未分配区域的骨架c）更新边界上像素点的速度和在边界附近未分配像素点的速度。3.2.3 SEEDS算法Bergh等人提出了SEEDS 算法，通

28、过一个能量函数来调节颜色柱状图和边界规则性，利用爬山算法来进行能量最优化。SEEDS开始于一个规则的网格，这也就是初始化的超像素。该算法并不需要为了迭代生长超像素来分担瓶颈。超像素生长就意味着，在每次迭代中都要计算超像素和周围所有像素的距离，这可能会产生极大的花费。SEEDS算法通过移动边界来交换像素，从而避免了超像素生长方法。SEEDS具体步骤：初始化超像素：首先将图片划分为规则的网格，不断合并相邻的网格使网格变大，最终获得初始的超像素。如图3-1所示。下面插入图3-1超像素初始化过程.(a)最小网格(wn ) (b)中等大小(dxio)网格 (c)最大网格(wn ) (d)初始化超像素生成

29、超像素：定义一个颜色项和边界项的能量函数，使该能量函数最大化，利用爬山算法完成超像素分割。在图像上选择不同大小的块， 首先以最大的块为交换单位，随着不断地迭代也不断的减小块的大小，最终减小到以像素为交换单位。如图3-2所示。下面插入图3-2超像素分割过程(a)初始化超像素 (b)最大单元 (c)中等单元 (d)最小单元 (e)像素点交换能量函数是有色彩项和边界项组成的评判标准，由公式(3-1)给出：Es=H(s)+Gs (3-1)其中H(s)为色彩项，用来估计超像素的颜色分布。G(s)为边界项，用来评估超像素的边界。纬是调节两者权重的系数。颜色项由公式(3-2)给出：Hs=khj(cAk(j)

30、2 (3-2)其中Ak(j)为属于超像素k的像素j，hj为色彩空间的封闭子集，cAkj为属于Ak的一系列像素的色彩柱状图。边界项由公式(3-3)给出：G(s)=ik(bNi(k)2 (3-3)其中Ni为像素i与周边像素组成的小块，bNi(k)表示超像素内有效像素所占比重。下面插入图3-3本文(bnwn)提倡(tchng)的SLIC算法(sun f)是基于梯度上升的算法，不仅操作简单，而且还可以生成高质量的、紧密的、大小一致的超像素。该算法把像素映射成CIELAB色彩空间上l，a，b值和空间坐标上x，y值构成的五维特征向量，并且提出了一种全新的距离计算方法，使得产生的超像素更加整齐紧凑。同时，S

31、LIC唯一需要输入的参数是超像素个数，这使得该算法非常的简单易用。该算法的复杂度为O(N)，说明运行速度很快。SLIC算法分割的超像素整齐紧密、大小统一而且边界保持度很高。表3-1为两类方法的比较结果，图3-3为SLIC算法的分割效果，可以看出基于梯度上升的算法要比基于图论的算法实用性更好，而基于梯度上升的算法中SLIC算法又是最好的。此处插入(ch r)表3-1 基于图论的算法(sun f)和基于超像素算法的性能比较表3-1 基于图论(t ln)的算法和基于超像素算法的性能比较基于图论的算法基于梯度上升的算法比较参数NCUTSLGBMSTPSLIC超像素个数控制YESYESNONOYESYE

32、S紧凑程度控制YESYESNONOYESYES输入参数个数132311算法复杂度O(.)N3/2N2logNNlogNN2NNdC=（lk-ki）2+（ak-ai）2+（bk-bi）2(4-2)dS=(xk-xi)2+(yk-yi)2 (4-3)D=dCm2+dSS2 (4-4)3.3 超像素算法比较这一部分，主要介绍当前最先进的超像素算法之间的对比，因为在第四章做了SLIC与SEEDS算法的比较，在这一部分将不再对SEEDS进行分析。本章主要对SLIC算法与Normalized Cuts、Graph-based、Turbopixels、quick-shift等算法作比较。为了能够更客观公正的

33、对多个超像素算法进行比较，在这里把分割误差和边界召回作为比较参数。3.3.1 计算复杂度对图像进行超像素分割时，SLIC算法的运行速度是Turbopixels算法的10倍，是Normalized Cuts算法的500倍。这是因为SLIC算法复杂度只有O(N)。Graph-based算法需要5N的空间来存储边权重和阀值，而 SLIC算法仅仅只需要1N的空间来存储。计算速度：超像素用来替换像素进行图像处理，以加快速度。因此，能快速的生成超像素是首要的。在考虑到的算法中，SLIC算法是最快的超像素方法，并且随着图像的增加而增大，速度优势更加明显。Graph-based算法也比较快，其他的算法在运行速

34、度方面与这两种算法有很明显的差距。内存效率：在处理大图像时，超像素算法节约内存也是很重要的。SLIC是最节约内存的方法，只需要N个浮点用来存储每个像素点到他最近的聚类中心的距离。其他方法对内存要求相对较高，Graph-based算法要求5N个浮点用于存储边的权值和四联通的阈值。3.3.2 分割(fng)效果超像素通常是分割算法的预处理步骤。作为一个优秀的超像素算法应该能提高分割算法的分割效果。超像素算法的质量也应该考虑到其他的因素。其中一个就是使用的简单性。有很多难以调节的参数的超像素方法可能会造成时间的浪费和性能的降低。另外能力是指定超像素个数，并不是所有算法都可以这样。当然，对超像素的整齐

35、紧密程度的控制能力也是尤为重要的。紧致，规则的超像素通常是我们想要的，因为它们有限制的体积，相邻邻居比较少能够形成更加容易(rngy)判断理解的图，能够提取更加局部相关的特征。然而要得到紧致的超像素，就要牺牲边缘的吻合度，能够控制两者之间的取舍将会非常有用。接下来，我们通过几个方面(fngmin)来回顾一下每个超像素分割方法的效果，包括边界吻合度，速度，内存效率，分割质量，参数调节，控制超像素个数的能力和控制紧致度的能力。Turbopixels算法产生最精致和体积连续的超像素，但它在所有方法中的边界响应和欠分割误差。Turbopixels算法运行也很慢，分割效果也比较差。Turbopixels

36、算法是最慢的超像素算法，分割一幅2048*1536的图片比SLIC几乎慢100倍，需要花费800秒。但是，Turbopixels算法只需要调节一个参数，可以直接调节超像素的个数。Normalized Cuts算法：Normalized Cuts算法只比Turbopixels算法有一点的提高。Normalized Cuts算法产生的超像素甚至比Turbopixels算法的更加紧致，所以更适合于基于图的应用。该算法边界保持度很差，但是分割质量很高。Normalized Cuts算法的运行时间很慢，不能分割2048*1536大小的图像，会耗光内存出错。Quick-shift算法边界保持度很好，但是该

37、算法分割效果比较差，还有其他的一些局限使得它成为一个不那么理想的方法。Quickshift算法运行很慢，需要调节多个不直观的参数，并且不能控制超像素的个数和紧凑程度。而且，不能保证超像素是完全连续的，这会给下一步的处理带来麻烦。Graph-based算法生成的超像素很不规则，但是对图像的边缘吻合程度很好。该算法运行也比较快，仅次于SLIC算法，分割一幅2048*1536的图像用时18.19秒。但是Graph-based算法分割效果不是很好，需要输入三个参数，但是不能控制超像素的个数和紧凑程度。在所有考虑到的超像素方法中，SLIC是总体表现最好的。它是最快的方法，分割一幅2048*1536的图像

38、只需14.94秒，更加节约内存，边界保持度很好。SLIC使用简单，唯一的一个参数就是想要得到的超像素个数，也是少有的几个能够用于生成超体素的超像素分割方法之一。最后，在现有的方法之中，SLIC可以通过调节参数m来权衡超像素紧凑程度和边界保持度，这一点是其他算法所没有的。第4章 SLIC分割算法第4章 SLIC分割(fng)算法4.1 SLIC算法(sun f)基本原理SLIC13称为(chn wi)简单线性迭代聚类，从名字也可以看出该算法的优点：思想简单、运算迅速以及使用方便等。SLIC算法将一幅图像转化为CIELAB 颜色空间和平面坐标下的5 维特征向量l a b x y，然后为该征向量构建

39、度量标准，利用K均值算法对图像迭代进行聚类。l a b是指CIELAB色彩空间中的颜色向量，x y指像素的位置坐标。SLIC算法的主要特点为：把搜索空间限制成和超像素大小成比例的区域，来减少距离计算的次数，从而使复杂度减小到和像素个数N呈线性比例的水平，且和超像素的个数k无关；通过定义一个全新的加权距离把颜色相似度和空间接近程度结合起来，从而提高分割质量。4.2 SLIC算法步骤SLIC算法，需要输入的唯一参数就是超像素的个数K。算法的具体步骤为：1)初始化聚类中心(种子点)。假设图像内有N个像素点，则超像素的大小为N/K，聚类中心间的距离为S=N/K，生成的超像素大小近似为S2。设超像素的聚

40、类中心为Ck=lk,ak,bk,xk,ykT，其中k的范围为1到K。为了避免噪点成为聚类中心，对后续的聚类过程造成干扰，需要将聚类中心移动到以它为中心的N N 区域内梯度值最小的地方，同时为聚类中心分配一个单独的标签。计算图像梯度由公式(4-1)给出：Gx,y=Ix+1,y-Ix-1,y2+Ix,y+1-I(x,y-1)2 (4-1)其中，I(x,y)为l a b向量对应于x y向量，|.|是L2 norm也就是欧几里德距离。这样就同时考虑了颜色和强度信息。 (a)传统k-means算法搜索 (b)SLIC算法搜索区域限制图4-1限制搜索范围2)迭代聚类。每一次迭代中，在包含聚类中心的2S*2

41、S区域内搜素，使所有像素都和一个最邻近(min(Ds)的聚类中心联系在一起，如图(4-1)所示。限制搜索区域的大小显著地减少了距离计算的次数，和传统的K-means算法相比，速度得到了显著提高，因为传统的k-measns方法中每个点要和所有的聚类中心进行比较。当所有像素都和最近的聚类中心建立了联系，接下来更新聚类中心，新的聚类中心为所有属于这一聚类中心的像素的向量l,a,b,x,yT的均值，记当前聚类中心和之前聚类中心之间的残留偏差为E，重复迭代至偏差收敛，一般迭代10次就足够了。3)后续(hux)处理(chl)。通过该过程把不连续的孤立点和最邻近的超像素(xin s)联系起来，保证连通性。S

42、LIC分割算法的总结如表4-1所示。表4-1 SLIC的核心算法算法 1 SLIC1:在间隔为S的规则网格上进行取样，来初始化聚类中心Ck=lk,ak,bk,xk,ykT2: 将聚类中心移动到3*3区域中梯度值最低的位3: repeat4: for 每个聚类中心Ck do5: 根据计算出的距离Ds，在聚类中心周边2S*2S区域进行搜索，关联像素和聚类中心6: end for7: 计算出新的聚类中心，以及参与偏差E8: 直到 E阈值9:加强联通SLIC核心代码：for( int itr = 0; itr 10; itr+ )/10次迭代distvec.assign(sz, DBL_MAX);/循

43、环起始位置先将距离初始化为最大距离int * inter1=interMat.ptr(itr)for( int n = 0; n numk; n+ )/对每个聚类中心k，在2S*2S区域内进行聚类 int offset= STEP; y1 = max(0.0,kseedsyn-offset); y2 = min(double)m_height,kseedsyn+offset); x1 = max(0.0,kseedsxn-offset); x2 = min(double)m_width,kseedsxn+offset);for( int y = y1; y y2; y+ )/跨度为2STEP*

44、2STEP内for( int x = x1; x x2; x+ )int i = y*m_width + x;l = m_lveci;a = m_aveci;b = m_bveci;/计算颜色空间和位置的欧氏距离 dist =(l - kseedsln)*(l - kseedsln) +(a - kseedsan)*(a - kseedsan) +(b - kseedsbn)*(b - kseedsbn); distxy =(x - kseedsxn)*(x - kseedsxn) +(y - kseedsyn)*(y - kseedsyn);dist += distxy*invwt;if(

45、dist distveci )distveci = dist;klabelsi = n;inter1i=klabelsi;4.3 SLIC距离(jl)计算(j sun)在CIELAB色彩空间(kngjin)中，欧氏距离比较适合感知较小的距离，简单的定义DS为五维欧氏距离将会造成不同体积的超像素聚类时的不连续，超像素不再遵循区域边界线，只是在平面上邻近。对于大的超像素空间距离比颜色相似度占的权重要大，使空间距离的重要性比颜色相似度更大。这样产生的超像素不能很到的吻合边缘。对于小的超像素，情况恰恰相反。为了把这两种距离合并为一个度量量，根据颜色近似度和空间相似度在一个聚类中的相对最小距离将他们归一

46、化是很有必要的。因此，要采用一种全新的距离测量方法DS。DS是像素i和聚类中心k之间xy位置坐标距离和lab颜色距离的加权距离。坐标距离、颜色距离和加权距离分别由公式(4-2)、(4-3)和(4-4)给出：下面插入这三个公式其中，NS是最大空间距离，NC是最大颜色距离。最大空间距离应该和聚类中心的间距相关，则令NS=S，而最大颜色距离中NC是不能直接决定的，所以可以将其设置为一个常量m。公式(4-4)化为：D=dCm2+(dSS)2 (4-5)将公式(4-5)化简为：Ds=dC2+m2(dSS)2 (4-6)DS=dc+ mSdS (4-7)也可以用更简单的公式(4-7)替代公式(4-6)，但

47、是用公式(4-6)更精确。这种全新的距离计算方法，通过m可以调节空间邻近度和颜色相似性的权重。当m很大的时候，空间邻近度的权重更大，得到的超像素更加的规则紧密；当m很小的时候，得到的超像素边界保持度更高，但并不规则。在CIELA颜色空间中，m的取值范围是1,40。4.4 孤立点处理在迭代聚类结束时，并不能保证一个聚类里的像素点来自于一个连通分量，也就是说会存在极少数的像素点是孤立的。为了解决这一问题，我们可以在算法的最后一步加强联通性，使用联通元素算法使这些孤立的像素与邻近的聚类中心关联。如果有多个符合条件的聚类中心，则选取五维特征空间中距离最邻近的那个中心与孤立点关联。4.5 SLIC算法(

48、sun f)优缺点SLIC算法有两大特点：限制搜索范围和全新距离(jl)测量DS。优点包括(boku)参数简单，只需要一个参数K(超像素的个数)，生成的超像素大小一致，整齐紧凑，分割效果较高。缺点有超像素个数要人为确定，很大程度上依赖于经验值，会直接影响到分割效果。 4.6 SLIC算法改进4.6.1 改进原理SLIC算法有一大特点：把搜索空间限制在和超像素体积成比例的区域中，在本文中取该区域大小为2S*2S，从而使优化算法中距离计算的次数极大地减少，这样就把算法复杂度降到了O(N)，和像素个数N呈线性的水平，并且和超像素的个数k无关。这样做虽然极大地提高了速度，但也会造成一个问题，那就是过分

49、割。比如图像中一个大于2S*2S子区域里所有像素的颜色纹理等特征都相同，在进行SLIC超像素分割后，这个子区域也会被分割为不同的超像素。实际应用SLIC算法时，对于颜色种类相对较少，颜色分布比较简单的图像，我们可能希望生成的超像素能够更加具有自适应性。既不再简单地将搜索范围限制在2S*2S区域内，而是根据颜色的分布情况适当的扩大（缩小）这个范围。改进的原理是，取超像素附近的一个较大邻域，求出该范围内像素梯度值的最大值和最小值，并且计算出相应超像素中心的梯度值，求出这三个梯度值的相应距离，距离大的说明要扩大搜索范围，距离小的说明要缩小搜索范围。利用归一化方法将距离映射到一个较小的范围，更有利于比

50、较。归一化公式由公式(4-8)给出：Dy=(Dx-MinVal)/(MaxVal-MinVal) (4-8)其中Dy，Dx是超像素中心的梯度值，MinVal是领域内的最小梯度值，MaxVal是领域内的最大梯度值。核心代码：int x = (int)(kseedsxn);/original xint y = (int)(kseedsyn);/original yint i=y*width + x;double maxedges=edgesi,minedges=edgesi,gg=edgesi,sum=edgesi;din=1;int ymin = max(0,y-2*STEP);int ymax

51、 = min(height,y+2*STEP);int xmin = max(0,x-2*STEP);int xmax = min(width,x+2*STEP);for(int y1=ymin;yymax;y1+)for(int x1=xmin;x=maxedges)maxedges=edgesj;if(edgesj!=0)if(edgesj=minedges)minedges=edgesj;normal=(edgesi-minedges)/(maxedges-minedges);4.6.2 改进(gijn)结果(ji gu)从图4-2可以看出，改进后的算法(sun f)比原来的算法的分割质

52、量更高，效果更好。比如红框中标出的部分。图4-2 从左到右依次为待分割图像、SLICS分割效果和改进SLIC分割效果第5章 实验结果与分析第5章 实验(shyn)结果(ji gu)与分析(fnx)5.1 实验环境 本文的主要实现环境是VS2010和OpenCV，以及在测试算法时用到的matlab软件。 HYPERLINK /view/28727.htm t _blank Visual Studio是微软公司推出的开发环境，是目前最流行的 HYPERLINK /view/4821.htm t _blank Windows平台应用程序开发环境。OpenCV的全称是：Open Source Comp

53、uter Vision Library。OpenCV是一个基于（开源）发行的跨平台计算机视觉库，可以运行在Linux、Windows和Mac OS操作系统上。它由一系列C函数和少量C+ 类构成，同时提供了Python、Ruby、MATLAB等语言的接口，实现了 HYPERLINK /view/14662.htm t _blank 图像处理和计算机视觉方面的很多通用算法。OpenCV用C+语言编写，它的主要接口也是C+语言，但是依然保留了大量的C语言接口。MATLAB是美国 HYPERLINK /view/1855191.htm t _blank MathWorks公司出品的商业 HYPERLI

54、NK /view/1658637.htm t _blank 数学软件，用于算法开发、数据可视化、数据分析以及 HYPERLINK /view/920695.htm t _blank 数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。在图形图像处理领域，matlab的使用非常广泛，但是使用matlab编码有时会使运行速度变得很慢。论文中使用的测试数据库是Berkeley分割数据集，该数据集是一个包含大量自然图片的标准数据库。在本部分测试比较算法质量时，需要将算法代码添加到超像素分割的benchmark上。Benchmark就是评价算法标准的实现代码，在此用到

55、的评价标准是分割误差和边界召回。5.2 SLIC算法与SEEDS算法的比较 这一部分主要展示SLIC算法和SEEDS算法在suerpixel benchmark上的测试结果。SLIC和 SEEDS算法的分割效果，如图(5-3)所示。从效果图可以直观地看出SLIC算法产生的超像素要好于SEEDS算法。 图5-1 SLIC与SEEDS的分割误差图5-2 SLIC与SEEDS的边界(binji)召回由图5-1可以看出，对于分割误差这个比较(bjio)参数，SLIC算法(sun f)要明显低于SEEDS算法，说明SLIC算法要好于SEEDS算法。在图5-2中，SLIC算法的边界召回要大于SEEDS算法

56、，这也说明SLIC算法生成的超像素质量高于SEEDS算法。 图5-3 SEEDS（上）与SLIC（下）分割效果比较5.3 改进SLIC算法运行结果论文中，利用VS2010创建了MFC工程，则运行结果会有一个Dialog窗口，如图5-4。图5-4中的CreatIntersuperpixels按钮的功能是，展现十次迭代的中间结果。在第四章提到，SLIC算法采用的是迭代收敛的思想，一般迭代十次就可以满足需求。通过展示改进后的SLIC算法十次迭代结果的渐变过程，能够更直观的展现分割的过程，如图5-5。分割的最终结果可以在图4-2中看到。通过图5-5，我们可以更直观地看到图像分割的具体过程和变化，更有利

57、于理解分割算法的思想。图5-4 VS2010程序运行结果(ji gu) 图5-5 改进(gijn)后的SLIC算法分割结果(ji gu)，按照箭头的顺序依次为第一次迭代(di di)到第九次迭代的迭代结果第6章 结论第6章 结论(jiln)现今(xinjn)，对图像(t xin)的预处理大部分都是基于像素点来完成的，但像素点只是将图像数字化的一种表示，它并不是实际存在的实体。而超像素是通过对像素点进行感知然后分组的结果。一个超像素所携带的信息量远高于一个像素点，而且相对于矩形图像块来说，它能很好的保持图像块边缘。由此对于处理大规模图像来说，超像素能极大地提高图像预处理的速度。超像素的优势有：具

58、有更高的计算效率：将图像中成千上万的像素点进行有意义的合并，聚集成几十到几百个超像素点；分割更具有意义：相对于网格的只能两两影响，超像素可以实现远距离的模型交互；每个超像素都是有意义的：每一个超像素都是一群相同像素的组合，它们有着相同的颜色或者纹理等。本文通过直观的超像素分割结果和在Berkeley数据库上的测试结果对比发现，在本文所考虑到的超像素分割算法中，SLIC算法是分割效果较好的一个算法。SLIC算法的优势包括参数简单，只需要一个参数K(超像素的个数)，分割后所得到的超像素大小一致，整齐紧凑，分割效果好。但该算法也存在一定的缺点，比如不能实现自适应聚类，需要人为确定超像素个数和初始化聚

59、类。中国石油大学（华东）本科毕业设计(论文)致 谢弹指一挥间，四年大学(dxu)生活已接近(jijn)尾声。感谢(gnxi)培养了我四年的母校，让我拥有这美好的四年大学时光。在这四年里，我收获了很多，学到了很多，提高了很多。当然这与一直给我帮助的人是分不开的，感谢辅导员老师对我的关心和教导，感谢班主任和各位授课老师给我的帮助，感谢室友们在我迷茫时给我的鼓励和温暖。我在此，对在这四年里和我一起走过的老师同学朋友，表示衷心的感谢。李宗民教授严谨认真的治学态度和精益求精的科研精神给我留下了深刻的印象。在李老师的细心指导下我完成了该论文，李老师对我的毕设工作提出了很多宝贵的建议。在此我衷心地感谢李宗民老师在毕设过程中对我的关心和指导。李宗民老师在我的毕设实践过程当中给我提供了大量的帮助，为我理清了算法的重点与难点，对我的课题提出了有效的改进方案。再次对刘老师表示衷心的感谢。在实验室完成论文工作期间，宫延河师兄和张洲凯师兄对我的工作给予了很大的帮助，在此感谢他们对我的悉心指导。最后，感谢我的父母给了我无私的爱，感谢他们在家乡给我的关心与温暖，感谢他们对我求学之路的默默支持和奉献，让我能有更美好的未来。参考文献1 王春瑶,陈俊周,李炜. HYPERLINK /kcms/detail/detail.aspx?file