第1章 绪 论
1.1 论文背景和意义
1.1.1 选题的背景
视觉感官在人类所有感官中占据重要地位，计算机视觉：要求计算机模拟人的视觉机理来获取和处理信息，正逐渐成为热门研究领域。随着科学技术的迅速发展，各种数码产品不断更新，数码相机、手机的摄像和拍照功能越来越强大，智能电视的画面越来越清晰，这些数码产品的图像达到几百万甚至上千万的像素分辨率，还有一些专门用于超清摄影的设备。由于图像的分辨率不断增大，许多基于像素级的传统分割算法花费的时间越来越长，如何才能减少分割的数据运算量成为图像分割的难题之一。人类视觉感知到的图像信息并不是从某一个孤立的像素点得到的，只有许多像素点组合在一起才对人类的视觉感知有意义。像素并不是视觉感知的着重点，这种需求下，产生了“超像素”的概念。
1.1.2 研究此课题的意义
超像素分割是图像分割重要的一个分支，是一种图像信息强有力的预处理技术，为图像分割与图像处理提供了有力的帮助和支持。超像素技术也是广泛的应用于社会生产的各行各业各领域。超像素的结果对图像处理都带来很大的便利，目前超像素分割技术也逐渐应用于医学图像诊断、军事精确打击、数字图像处理、目标跟踪、模式识别、虚拟现实场景、3D 重建、建筑物定位布局、大气图像分析等领域，而且取得了显著地成果。尽管图像分割和超像素分割得到了广泛重视、研究和应用，国际上也有许多分割技术的学术会议，有关图像分割研究的文章早已数以万计，但是至今我们国内这方面的研究比较国外来说有一定的落后，本文对常用的几种超像素分割算法进行深入比较分析验证，希望能够给超像素技术提供一点支持。
1.2 国内外研究状况
图像分割是图像处理中的一个基本问题，同时也是模式识别、目标追踪、
1
场景分析等计算机视觉问题的基础，超像素概念最早由国外学者提出使用的，由于图像分割理论较为成熟，因此超像素分割发展也较为迅速，相应的算法和应用都比较多：
国外:（1）Ren和Malik最早提出使用Normalized Cuts（N-Cuts）来完成超像素分割，而且对超像素做了定义，得到相似大小和紧凑的块应用于各个领域，但是它的计算开销太大。（2）Levinshtein等人提出了一个叫做Turbo-Pixel方法有效代替超像素完成相似区域的规则分割，基于图像中设置的均匀种子点得到物体边缘曲线，从而完成图像超像素的分割。（3）Felzenszwalb和Huttenlocher提出了一种新方法―FH‖将图像分成一些区域，找到两个区域的边界将图像分割。算法运行时间对于图像边的数量是线性的，计算非常之快。（4）A.Moor等人提出了―Lattice-Cut‖（格形分割）的超像素分割技术，用规则的格形方法来分割，保持像素之间的相对位置和关系，保持了图像的拓扑结构，有利于图像的后续处理。（5）Comaniciu等人提出了Mean-Shift方法，来分析一个复杂的多模态的特征空间，采用聚类的方法把相似的特征聚到一起，形成不同的区域块，有很好的性能。（6)Veksler等人以图割问题为基础构建了一个超像素分割的方法，采用一种密集的块重叠技术，将图像分为均匀大小的有重叠的块，再根据相关特征融合这些块，使它们互不重叠的分布在图片上达到超像素分割的效果，其分割后的超像素大小上近似且非常规则，而且作者从图像到视频，将超像素延伸到超体素，同样收到良好的效果。（ 7）Achanta等人提出了简单线性迭代聚类（SLIC，Simple Linear Iterative Clustering）的方法，只需设定目标超像素的数量即可，且运行速度较快，只需要线性的运行时间和存储空间。（8）Liu等人提出了基于熵率的超像素分割技术，信息熵有着非常好的性质，将准确的分析图中的相似性关系，其效果的准确率最高。
基于分类：超像素生成算法大致可分为基于图论的方法和基于梯度下降的方法两类。（1）基于图论:Felzenswalb 等人提出的graph-based方法、Shi等人提出的Ncut(normalized cuts)方法、Moore等人的superpixellat-tice方法和Liu等人提出的基于熵率方法。Ncut算法利用轮廓特征和纹理特征来全局最小化代价函数，它能生成规则的超像素，但是图像边界的保持效果不好、计算量较大，处理大图片时速度很慢。Graph-based方法使用最小生成树的思想来分割图像，它能较好地保持图像边界，速度较快，但是得到的超像素大小和形状都不规则。Superpixel lattice方法保持了图像的拓扑结构信息，但性
2
能严重依赖于预先提取的图像的边界。熵率法提出了包括图像随机游走熵率和平衡项的目标函数,通过最大化目标函数以实现分割，它产生的超像素比较规则和均匀。（2)基于梯度下降法:Vincent等人的分水岭(watersheds)方法、Comaniciu等人的MeanShift方法、Vedaldi等人的Quick-shift方法、Levinshtein等人的Tur-bopixels方法和Achanta等人的SLIC(simple linear itera-tive clustering)。它们都采用了聚类的基本思想,Turbopixels是基于几何流的水平集方法，对初始的种子点逐步进行碰撞，最终将超像素近似均匀地分布到图像平面上。Mean-Shift是一个迭代模态搜索的过程，它能产生形状规则的超像素，但速度慢，并且不能控制超像素的数量、大小和紧凑度。Watersheds是一种基于拓扑理论的数学形态学分割方法，该方法速度快，但是不能控制超像素的个数和紧凑度。SLIC算法是基于颜色和距离相似性进行超像素分割，该方法思想简单，可以生产大小均匀、形状规则的超像素。由于超像素能够提取中层图像特征，它通常作为分割算法的预处理步骤，已经成为视觉领域的一项关键技术。
国内:由于计算机视觉研究领域技术进入国内较晚，相对超像素分割方面 的技术起步也较晚，集中出现在最近五年，以超像素的应用为主，对这方面的理论研究较少，研究现状：
（1） 苏金玲等人利用超像素分割技术和Graph-Cut，提出一种快速的显著对 象自动分割方法，把颜色和亮度等特征显著地区域分割出来。（2)刘陈等人的研究是应用超像素分割的结果，把超像素当作像素来处理问题，保留了绝大多数边界特征且大大优化了算法的复杂度，是基于Mean-Shift算法实现的。（3)刘靖等人通过应用超像素分割提出了一种提取户外建筑目标图像中布局信息的方法，效果较好。（4)袁淑娟等人把超像素技术应用于虚拟现实场景构建，先把图像分为超像素，再增加类别标志把图像分成不同的集群，利用三维技术输出三维场景，就可以高效地构建出虚拟现实场景。（5)张微等人用Mean-Shift算法将图片分为超像素，以超像素为节点建立图模型，用于CRF（条件随机场）的参数估计和推导，超像素技术不但使其极大缩短了时间，而且提高了分类的准确率。（6)韩守东等人通过使用高斯超像素技术来构建Graph Cuts模型以实现图割算法的加速，提出了一种交互式的快速图像分割方法。
超像素生成算法将图像划分成同质小区域，同一区域内的像素点具有相似的亮度、颜色、纹理等性质，因此它们的聚集结果便可以方便地以整体特征代表整个区域中的所有像素点，而一个这样的同质小区域就是一个超像素。用超
3
像素代替像素点作为图像处理的基本单位，可以降低信息冗余，减少分类器所需样本点或简化拓扑结构，具有更高的视觉等级和更丰富的意义，可提升后续图像处理算法的效率，实质性地提升着我们的工作质量。以往基于图论的图像分割算法只能分割分辨率较低的图像，当对分辨率较高的图像进行处理时，需要先对图像进行降低分辨率的处理，而超像素分割算法克服了这个缺点。
1.3 本文的主要工作
现在超像素越来越被广泛地应用于计算机视觉领域中，并且作为图像分割和模式识别的初始阶段，最根本的原因是：一方面是使用了超像素后可以有效地减少图像局部信息的冗余，使图像处理的复杂度和运算量大大降低；另一方面是基于像素级的传统的图像处理方法，也不能准确的定位目标区域的边界，只能给出一个大概的位置。所以超像素分割的效果和标准的人工分割还有一定的差距，而且超像素分割算法的分割结果进行合并处理后，仍然不能完全避免过分割现象，仍然需要进一步对过分割现象进行改进。
虽然近年来新的研究成果越来越多，但由于图像分割本身所具有的难度，使研究没有大的突破性的进展，仍然存在的问题主要有两个：其一是没有一种普遍使用的分割算法；其二是没有一个好的通用的分割评价标准。
综述国内外各种有关超像素分割算法模型、算法实现步骤;对比分割效果分析不同留在理解各种算法模型实现的基础上，搜集相关模型实际的应用效果;分析不同模型图像处理效果在不同指标精度的限制下，编写相关程序对图片预处理，比较结果结合实际给出恰当的评判标准。
4
第2章 基本理论
2.1 算法的模型
2.1.1 基于图论的分割方法
所2003年Ren和Malik提出超像素，认为像素不是自然实体，是图像离散化的表示，是中等程度分辨率的图片，有很多的像素个数，在像素层面上对图像进行优化很困难，为解决这个问题提出超像素的概念，即指具有相似纹理、颜色、亮度等特征的相邻像素构成的图像块。图像块保留了进一步分割的大多有效信息，一般不会破坏图像中物体的边缘信息，用超像素代替像素点作为图像分割的目标能够减少图像分割的规模，大大提高计算效率。
图论作为一种数学方法和理论，主要研究具有特殊性质个体间的关系，被广泛应用到生物，信息，物理等领域。20世纪80年代才在图像处理方面得到应用。在研究出的许多基于图论的分割和聚类方法的中心思想是形成加权图。将图像先映射为加权无向图G，图G的每一个顶点V对应于图像的像素或者区域，G的每一条边E都被进行了加权，利用对应的分割准则得到最好分割。以下介绍图论在图像分割领域中的研究情况。
给定图像I，构建图G=（V,E,W），V：每个像素作为图的一个节点，E：一定范围内的连接边界，像素i和像素j间的差异或相似度为权重w(i,j)，公式：
wij?e?F(i)?F(j)22?12??X(i)?X(j)?e2*??x??0；其他22;当X(i)-X(j)2?r
X(i)—像素点i的空间坐标；
?I —高斯函数(guassian)的标准方差；
?x —空间距离的高斯函数(guassian)标准方差；
r —两个像素的距离，在这个距离之外时，两像素的权重为 0； F(i)—像素点i基于亮度、颜色或纹理信息的特征向量，分割点集时F(i)=1，分割对象为灰度图像时，F(i)=I(i)，对于分割色彩图像时，F(i) =[v,v·s·sin(h)
5