毕业论文-基于超像素的图像分割技术及其实现

1、 MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 1 h * MERGEFORMAT SEQ MTChap r 2 h * MERGEFORMAT 毕业设计基于超像素的图像分割技术及其实现学生姓名 学 院 专 业 班 级 学 号 指导教师 2016 年 5 月 16 日盐城师范学院毕业设计 页 ，共 17 页引言图像分割技术依据灰度、颜色、纹理和形状等特征，将具有相似特征的像素聚集形成同一个区域，并且使得这些区域间的特征明显不同。以此方法将图像划分形成一些不相互重叠的区域。在计算机视觉领域，图

2、像分割问题也越加显得重要,因为其分割的质量将直接影响到视觉系统的性能。随着计算机技术的精进以及多媒体技术的发展，图像分割技术几乎应用在有关图像处理的所有领域，涉及范围也变得十分广泛。例如：医学、数字图像、军事、体育、智能交通和产品质量检测。因此可见，所需要分割图像的来源也变得更加广阔，数量也急剧增加。那么随之而来的问题也越来越多，比如参数收敛变慢导致的运算规模扩大，以及耗费的处理时间也成倍增加。为了解决这一问题,超像素方法被研究实现。这一概念最早于2003年被Ren等人提出116。超像素的实质就是一些聚集在一起的相邻像素群，特别之处在于这些像素群有着相似的特征。所以从算法运行效率角度考虑，为了

3、提高了算法的运行速度，采用较少数量的超像素替代数量繁多的像素这一方法来减少算法的执行时间；同时,利用超像素方法，即将像素按照相同特征分组，可以获取图像的冗余信息,这也大大地降低了后续处理工作的复杂度。目前，已被研究的超像素算法有很多，但是大致可以划分为两类，一是基于图论的图像分割方法，有Felzenswalb提出的graph-based方法2、Liu等人提出的基于熵率的方法3、Moore等人提出的superpixel lattices方法4和Shi等人提出的Normalized Cuts（Ncut）方法5，16；二是基于梯度下降的方法，有Levinshtein等人提出的Turbopixels方

4、法6、Achanta等人提出的SLIC（Simple linear iterative clustering）方法7、Comaniciu等人提出的MeanShift方法8、Vedaldi等人研究的Quick-Shift方法9以及Vincent等人研究的分水岭（Watersheds）方法10。基于图论的图像分割因能够将像素点转换为无向图，有着其他超像素方法所不能比拟的优势。如：可利用图或者网络图反应图像的特征。基于梯度下降的方法，均涉及聚类思想，但是因为其应用方面有各自特征，所以各自方法也不尽相同，导致优缺点也不同。超像素方法因为方便提取中层图像，通常作为分割算法的预处理步骤，现在已经被成功应用

5、于多种视觉任务，已然成为了视觉领域的一项关键技术，如骨架提取、目标跟踪、图像分割以及目标识别。因此，超像素技术以其巨大的应用价值和发展潜能在计算机视觉应用领域越发备受关注。本文对几种经典的超像素算法进行介绍，着重研究并实现了其中的SLIC超像素算法，并对其实际应用进行介绍。背景在已经被研究的超像素算法中，本文对其中的几种比较典型的算法进行介绍。一种是基于图论的超像素算法：Graph-based算法和Superpixel lattices算法；还有一种基于梯度上升的算法：Turbopixels算法和MeanShift算法。在图模型中，用超像素代替像素点进行构图的方法，降低了图规模，解决了基于像素

6、的图像尺寸增大而导致的计算量急剧上升引发的不可处理问题，得到了广发的应用。而基于梯度的超像素算法，保持了被分割区域良好的边缘特性，减少了后续合并的时间，很大程度上提高了运行速度和分割结果的质量基于图论的方法在解决图像聚类与分割问题中，基于图论的图像分割方法的应用最早可以追溯到1971年Zahn的工作11,他把此问题转换到图论中，用最小生成树的思想来解决问题。虽然基于图论的图像分割技术与方法有很多,但是它们着有共同特征:将图像表示成图论中的网络图,利用图论的相关技术,通过对网络图的一系列操作和计算处理,完成图像的分割。为了便于说明，作出图形来阐述。如图2.1所示，其中V表示整个图B中的所有结点v

7、的集合；E表示图B中所有边的集合，将图像A表示成带权的无向网络图B，图B中的每个结点对应图像A中的每个像素，表示为：。 Original image A Graph B图2.1 图像映射到图论中我们将连接结点和的边表示为,与边相关的数据信息表示为权值 。显然在图论方法中，这些边的权值表示的是像素特征等方面相似度的值。然而在实际运用中，权值可以有各种含义。自1971年，图论被Zahn应用于图像分割以来，目前基于图论的图像分割算法已有多种。本章节介绍两种具有代表性的基于图论的超像素分割方法：Graph-based方法和superpixel lattice方法。Graph-based方法Graph-

8、Based Segmentation 是典型的基于图论的图像分割算法，由Felzenszwalb等人提出2。该方法运用最小生成树的思想来分割图像，实现起来较为简单，并且速度较快，精度较高。不过，在图像分割应用中直接用Graph-Based分割图像的很少，因为用该方法所产生的超像素的大小不同、形状各异。Graph-based方法,先将图像中的像素点映射为带权的无向图,每条边的权值表示所连接的两个结点的差异性,用R、G、B分量的欧式距离来计算。在该方法中，我们将区域差异分为各个区域自身内部的差异和各个区域之间的差异两种,分别定义为、 。其中，表示表示区域内差异，表示区域间差异。若区域间差异小于任何

9、一个区域内差异,即，则将两个不同的区域合并；反之,若，则将作比较的两个区域作为单独的区域处理。Graph-based方法产生的超像素，实际上就是像素点集合形成的最小生成树，通过图上的结点聚类实现。虽然该方法产生超像素的速度快，但是不能自定义生成超像素的数量，更不能控制所产生超像素的紧凑度。Superpixel lattices方法Superpixel lattices算法，简称SL，能够保持图像的拓扑结构，由Moorer等人提出4。该算法用寻找最短路径的方式，只需输入图像的边界图，便能从垂直方向和水平方向，在无监督状态下搜寻最优路径来分割图像，以形成较小的区域，从而得到超像素。相较于Graph

10、-Based 方法，虽然Superpixel lattices算法能够直接控制超像素的数量,且分割效果良好，但是过分依赖于输入的边界图。在使分割图像均匀方面，Superpixel lattices方法还有两个机制：a）路径能否均匀分布会直接被图像带是否分布均匀影响；b）搜寻最小代价路径的方法，有利于搜索相对较直和较短的路劲。所以该算法仍然需要改进。基于梯度下降的方法基于梯度下降的超像素方法产生超像素的基本思路是：先粗聚类，再采用梯度法迭代聚类的结果，直至满足收敛条件。Turbopixels方法Turbopixels方法能够快速产生网格状的超像素，于2009年被Levinshtein等人提出6。

11、该算法的基本思想是先膨胀初始化聚类中心，再参考曲率演化模型，将背景区域骨骼化，即可产生超像素。Turbopixels方法生成的超像素有如下特性12：尺寸均匀。通过设计集合流膨胀初始化均匀分布的聚类中心，使生成的超像素大小几近相同，形状大致一样；连通性。运用水平方向几何扩张的方法，将所有超像素表示为连续的像素点集合，保证Turbopixels方法的连通性；紧凑性。该算法使各个特征均匀的区域在边界外做恒定运动，使得超像素紧凑；平滑并保持边缘。当聚类中心停止增长时，在边界强度弱或者无边界区域，需要几何流公式曲线运动速度变大；而在边界强度较强的地方，需要其曲线速度变慢甚至停止。从而使超像素边界与图像边

12、界吻合，实现图像的分割。超像素不重叠。当具有相同特征的像素点以其聚类中心开始聚类并且区域不断扩大直至要碰撞时，边界停止增长，即每个像素被分配到单一的超像素之中，超像素不会重叠。Turbopixels方法的图像的大小与算法复杂度接近于线性关系，短时间内就可以处理万像素集的图像并且获得密度较高的超像素，运算速度快。该算法产生的超像素能够很好的确保图像的部分边界，并还能限制欠分割。 MeanShift方法MeanShift算法，最早于1975年被提出，是基于核密度梯度估计的迭代式搜索算法。而于1995年，因研究了核函数并且定义了权值系数，使得Mean-Shift方法的应用更加广泛。其基本思想是通过定

13、位密度函数的局部最大，把具有相同特征的像素聚集到一起，从而生成超像素。该算法抗噪性和边缘贴合度较好，但是形成的超像素不规则。随后，经Comaniciu等人改进8，提出了一种能够快速统计的无参迭代算法。该算法仍然基于核密度梯度，并且被证明在满足一定条件下，MeanShift算法通过有限次的迭代，能够收敛到一个最近的稳定点，即模点。这一特征，成功将MeanShift推广到特征空间分析的领域。用MeanShift方法分割图像，就是依照模点的特征进行像素的聚类，以此形成稳定性和抗噪性都较好的超像素，但是执行速度慢，容易过分割。MeanShift方法有一个迭代过程。首先要算出当前像素点的漂移均值，并以该

14、均值所在像素点为新的起点，继续移动，直到符合设定的条件，迭代停止。扩展形式如下： （2-1）其中，是一个常系数，是一个单位核函数； 是采样点， 表示权重，并且 。SLIC超像素SLIC(Simple Linear Iterative Cluster),是一种简单的线性迭代算法,最早由Achanta等人于2010年提出13。相比较基于图论的Graph-based方法、Superpixels方法以及基于梯度上升的Turbopixels方法和MeanShift方法，SLIC方法在边界保持以及边界召回等方面的优势更强9。用SLIC超像素算法生成的超像素紧凑性好、大小和形状均匀且规则。本章节将详细介绍S

15、LIC超像素算法，给出实现SLIC算法的相关关键代码并且加以解释说明。算法介绍SLIC算法根据亮度、颜色的相似性以及空间的相邻性，实现五维空间中的像素聚类。首先将图像从RGB颜色空间转换到CIELAB颜色空间并且记录坐标下的五维特征向量。将每个像素的 颜色值与其对应的坐标组成一个五维向量。其中代表亮度；表示红绿颜色分量，表示从绿色渐变到红色；表示黄蓝颜色分量，表示蓝色渐变到黄色。由它们的向量距离来度量两个像素的相似性，距离大小与相似性成反比，即距离越小，相似性越大。具体步骤如下：首先，初始化聚类中心。依照蒋定的超像素个数，在均匀地在搜索范围内调配聚类中心。我们假定需要分割的图像中共有个像素点，

16、预分割的超像素有个（假设超像素尺寸相同）。那么计算出全部超像素的大小均为，且相邻聚类中心的距离近似为 。在聚类过程中，我们每隔L个像素就选取一个聚类中心，然后以这个聚类中心四周的为其搜索空间，搜寻最为相似的点。为了降低所选聚类中心是边缘或噪声的概率，以每个聚类中心为窗口基准，将聚类中心移动到大小为3*3窗口中梯度最小的区域，并为每个聚类中心分配单独的标签16。其次，对于每一个像素点，都要计算出与之距离最近的聚类中心之间的相似度，直至收敛停止迭代。距离测量因为CIELAB颜色空间对亮度、红绿颜色分量、黄蓝颜色分量的大小有限制，而对图像大小没有限制，如果图像较大，那么空间距离将会对所衡量得向量距离

17、造成很大的影响。所以为了降低空间距离的造成影响度，需要对进行修正。我们将将像素点和的空间距离规范为： (3-1)对于大型超像素，空间距离大，导致颜色看上去不是十分接近，所以我们将将像素点和的颜色差异规范为： (3-2)那么，像素点和的相似度为： (3-3)其中，为聚类中心的间距, 定义为一个平衡参数，目的是为了控制颜色差异和空间距离在相似度衡量中的比重，范围一般是1到20，在本文的算法中设置为10。并且取值越大，说明像素间的相似度越高。与在整张图像中寻找超像素的运算速度相比，对每个聚类中心聚类时，只在以聚类中心为中心的区域内搜索相似像素点的运算速度更快。我们做出示意图来阐述，如图3.1所示。其

18、中图a是在整张图像中搜索，图b是在的区域内搜索。(a)在整张图像中搜索(b) 在区域内搜索图3.1 减少搜索像素的范围后期处理最初，在实验中我们可能会发现一些小的区域r，虽然已经被标记为归属于某一块超像素,但却与其所归属的超像素没有任何衔接。此时，为了降低超像素的残缺程度，我们就需要把区域r重新归类，而所归类的超像素就是与r连接的最大超像素。算法实现章节3.2、3.3详细介绍了SLIC算法，本章介绍SLIC算法的具体实现。具体实现过程如下：（1）SLIC算法中，得出每个超像素的大小为，关键代码如下所示：void SLIC: ForGivenNumberOfSuperpixels ( const

19、 unsigned int* innerbuff, const int Pwidth, const int Pheight, int *&samelabels, int& Anumlabels, const int& K,/用于接收希望得到的超像素的数量 const double& scale) /用于距离转化为颜色空间的比例 istance const int superpixelsize = double(Pwidth*Pheight)/double(K);/每一个超像素的大小 ForGivenSuperpixelSize(innerbuff,Pwidth,Pheight,samelabe

20、ls,Anumlabels,superpixelsize,scale); 上述代码中，我们将图像的像素内指针定义为innerbuff，将用于存储所要分割图像的宽度和高度分别定义为Pwidth和Pheight；samelabels和innerbuff用于返回每个像素聚合后所属于的类（即标签）；Anumlabels返回值为实际聚类之后得到的标签数目；K值用于接收用户输入的、希望得到的聚类的超像素数量；scale表示距离转化为颜色空间的比例。（2）我们首先定义初始化聚类中心，将整个RGB格式的图像转换为LAB颜色空间中，即灰度化色彩空间。再根据我们所设定得进行边缘检测，检测出的边缘用来修整初始化的聚

21、类中心。经此，开始初始化聚类中心。关键代码如下所示：void SLIC: ForGivenSuperpixelSize( for( int s = 0; s szz; s+ ) samelabelss = -1; DoRGBtoLABConversion(innerbuff, s_lvec, s_avec, s_bvec); bool Aperturbseeds(true);/干扰像素点不一定要聚类进一个超像素，可以将此先设置为假 if(Aperturbseeds) DetectLabEdges(s_lvec, s_avec, s_bvec, s_width, s_height, edgema

22、g); /如果是干扰像素，先放置一边，不进行聚类GetLABXYSeeds_ForGivenStepSize(kkseedsl,kkseedsa,kkseedsb,kseedsx,kkseedsy,STEP,Aperturbseeds,edgemag); PerformSuperpixelSLIC(kkseedsl,kkseedsa, kkseedsb, kkseedsx, kkseedsy,sameklabels, STEP, edgemag,scale); /初始化聚类中心 Anumlabels = kkseedsl.size(); int* nlabels = new intszz; E

23、nforceLabelConnectivity(sameklabels,s_width, s_height, nlabels, Anumlabels, double(szz)/double(STEP*STEP); /没有被聚类的点和相邻的类强制聚类 （3）计算最短距离，更新中心点。整个聚类循环n次（参数n可修改）。循环起始位置，先将整个距离初始化为最长距离，然后再计算当中更新最短的距离。根据中心点的起始范围计算聚类的初始位置，接着计算颜色空间和像素位置的欧氏距离，其中位置距离需要进行一个规范，而不是直接使用。关键代码如下所示： Odist =(l-kkseedsln)*(l-kkseedsln

24、)+(a-kkseedsan)*(a-kkseedsan)+(b-kkseedsbn)*(b-kkseedsbn); /算法中的公式计算Odistxy=(x-kkseedsxn)*(x-kkseedsxn)+(y -kkseedsyn)*(y - kkseedsyn);/算法中的公式计算 Odist += Odistxy*invwt; /算法中的公式计算 if( Odist distveci ) distveci = Odist;/颜色空间的距离 samelabelsi = n;/表明属于超像素哪个标签 （4）我们为了提高运算速度，在以聚类中心为中心的区域内搜索相似像素点，关键代码如下所示：

25、if(count 2)/搜索范围为以某一个像素为中心点的2倍范围 for( int cc = 0; c c count; cc+ ) int inds = yveccc*width+xveccc; nlabelsinds = adjlabels;/将相应的label设置为附近的标签 label-; 实验结果与分析通过实验，我们发现，不同的迭代次数以及设置不同的超像素数量，会严重影响实所分割超像素的形状以及分割质量。首先，我们做迭代次数不同的实验。通过实验，观察迭代次数对超像素图像分割的影响，迭代的次数分别为3次、6次、8次、10次、12次、15次。如图4.1所示：图4.1 a 迭代3次 图4.

26、1 b 迭代6次图4.1 c 迭代8次图4.1 d 迭代10次图4.1 e 迭代12次图4.1 f 迭代15次图4.1 迭代不同次数的超像素分割图如上图a、b、c、d、e、f所示，我们发现，随着迭代次数的增加，超像素分割的形状越来越规则、越来越均匀。但是当次数超出于10后，超像素的形状和大小逐渐趋于平稳状态。由此可见，算法中的迭代次数也会影响到超像素图像分割的效果，选择迭代的次数也是实验的一部分。在以下的实验中，迭代次数均取10。第二个实验中，我们研究超像素数量对分割质量的影响。我们发现，在同等条件下，分割成不同超像素数量，其分割的效果不一样。如图4.2所示，a图超像素数量是50个，b图超像素

27、数量为100个，c图超像素数量是200个，d图超像素数量是500个。图4.2 a 超像素数量为50 图4.2 b 超像素数量为100图4.2 c 超像素数量为200 图4.2 d 超像素数量为500图4.2 不同超像素数量的图像分割图如图4.2，我们可以清晰地看出，超像素方法可以将具有几千甚至上万个像素的图像减少为只有几百甚至几十个的超像素图像，并且每个超像素在亮度、颜色等方面具有几乎相同的特征。在a、b、c、d四幅图中，我们观察发现，每个图像分成的超像素规则且均匀，大小形状几乎一致。并且可以明显地对比得出，b图比a图分割更细致，却没有c图准确，而d图比a图、b图、c图更加精细。当超像素数量增

28、加时，分割图像的边缘贴合度越好，分割失误越少；而当超像素数量减少时，贴合度变差，分割失误也越多。超像素的应用在实际生活中，超像素方法也有着一定的协助作用，为生活和工作提供了便利。比如在医学图像处理中有着重要而广泛应用的基于SLIC算法的超像素分割技术14。SLIC方法能够使独立的像素点聚类成分布均匀、边界规则的超像素，并且保持图像的重要边界信息，突出图像细节特点，极大的提高了图像处理的效率。如今，该技术已经应用在医学中的多个领域，为专家诊断提供辅助。比如，在定位人体内出血和癌细胞组织方面，取得了一定的成功。运用已经实现的SLIC超像素图像分割技术，我们对内出血的CT图像和癌变组织的CT图像进行

29、分割，并对分割结果进行研究。（1）内出血定位。内出血，尤其是颅内出血，严重影响病人的生命健康，若不能及时诊治，会造成语言功能障碍、瘫痪甚至威胁生命。通过SLIC超像素分割技术，我们可以快速定位出血的位置以及大小。如图5.1所示，红色圆圈标记处为颅内出血处。图5.1 a 颅内出血CT原图像 图5.1 b 颅内出血超像素分割图像图5.1 颅内出血CT原图与超像素分割图对比（2）癌变组织定位。由于癌变组织的特性与之正常细胞已经发生改变，与周围组织已经发生形状上的显著区别。实验中，基于SLIC技术的超像素算法可以快速将癌变部分聚类，为专家提供癌变组织的具体位置和形状。如图4.2所示，红色圆圈处为癌变组

30、织位置。图5.2 a 癌变组织CT原图 图5.2 b 癌变组织超像素分割图图5.2癌变组织CT原图与超像素分割图对比基于SLIC算法的超像素分割技术在建筑学上也有着一定的应用，可以用于标定户外建筑目标图像15。在已知户外建筑目标图像布局后，运用该技术过滤掉图像中的非目标部分，有针对性地研究目标区域。通过位置、颜色、纹理特征的提取，十分有利于建筑目标的检测和识别工作的进行，极大地提高了工作效率与工作质量。结 束 语目前，图像分割技术已经被成功应用于多种视觉任务，如目标识别、目标跟踪以及骨架提取。因此对分割的要求也越来越高，超像素概念应运而生。现有的、已经被研究的几种超像素算法大致归类为两种，一种

31、是基于图论的图像分割方法，因具有独特的结构，而具有独特的优势。另一种是基于梯度下降的方法，都采用了聚类的基本思想，但是因为其各自实现的具体方法不同，优缺点也略有差别。通过实验，我们分析了SLIC超像素算法的迭代次数以及超像素数量对分割质量的影响，并且将SLIC算法由理论变成实际运用。比如在医学中可以定位颅内出血、癌变组织；在建筑学中可以过滤掉图像中的非目标部分，对目标区域更有针对性地进行研究。超像素技术的应用领域越来越广泛，而其边界良好贴合的特性也使其更具优势，所以对超像素的研究也需要更加深入。参考文献1 REN Xiao-Feng,MALIK J. Learning a classifica

32、tion model for segmentation C/Proc of the 9th IEEE International Conference on Computer Vision. Washington DC: IEEE Computer Society,2003:10-17.2 FELZENSWALB P F,HUTTENLOCHER D P. Efficient graph-based image segmentation J.International Journal of Computer Vision,2004,59(2):167- 181.3 LIU Ming-yu,TU

33、ZEL O,RAMALINGAM S,et al.Entropy rate superpixel segmentationC/Proc of IEEE Conference on Computer Vision and Pattern Recognition. 2011:2097-2104.4 MOORE A,PRINCE S,WARRELL J,et al. Superpixel latticesC/Proc of IEEE Conference on Computer Vision and Pattern Recognition.2008:1-8.5 SHI Jian-Bo,MALIK J

34、.Normalized cuts and image segmentationJ.IEEE Trans on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.6 Levinshtein A,Stere A,Kutulakos K,et al. Turbopixels: fast superpixels using geometric flows J. IEEE Trans on Pattern Analysis and Machine Intelligence, 2009,31(12):2290-2297. 7 Acha

35、nta R,Shaji A,Sith K,et al. SLIC superpixels compared to state-of-the-art superpixel methods J. IEEE Trans on Pattern Analysis and Machine Intellige- nce,2012,34(11):2274-2282. 8 Comaniciu D,Meer P. Mean shift: a robust approach toward feature space anal- ysis J. IEEE Transaction on Pattern Analysis and Machine Intelligence,2002, 24(5):603-619. 9 VEDALDI,SOATTO S. Quick shift and kernel methods for mode seeking M/ Computer Vision. Berlin: Springer-Verlag,2008:705-