毕业论文超像素分割技术研究 - 图文

学科分类号 110

黑龙江大学

本科学生毕业论文

题 目 超像素分割技术研究 The Research of Superpixel segmentation 姓 名 李绵绵 学 号 2011027048 院 （系） 理学院 专业、年级 数学与应用数学11-1班 指导教师 张太发 2015年6月12日

摘 要

超像素分割是计算机视觉中的热点问题，超像素的使用能有效地减少图像局部信息的冗余，大大降低了图像处理的复杂度和运算量，而且还保留了对图像进行进一步处理的有效信息，超像素技术越来越广泛地应用于许多领域。

本文对常用的几种超像素分割算法进行深入比较分析验证，采用过分割方法得到的超像素作为图像目标识别的基本单元,对现有的超像素分割方法进行研究学习，了解各个方法所要阐述算法的基本思想，以及分割步骤，找出不同算法模型分割效果的优缺点，取长补短，综述不同算法的适用情况。依据超像素分割算法模型的实现步骤对其进行预处理，得到预处理的图片。选用经过比较分析后的方法分割图像，根据实验结果，结合实际优化模型分割。

关键词 超像素 图像分割 区域合并

I

Abstract

The superpixel segmentation is the hot problem in computer vision. The usage of superpixel can reduce the redundancy of the local information in image efficiently and decrease the complexity of image processing largely. It keeps the information, which is usage in the next step image processing. More and more fields apply this technology.

The paper analysis some classical and commonly kind of algorithm in superpixel segmentation. We research some existing superpixel segmentation algorithm, whose basis pixel is based on the superpixel coming from over-superpixel segmentation. The basis idea and the segmental process are introduced in the paper and look for advantages and disadvantages among kinds of methods. We analysis the appropriate conditions in different methods. The preprocessing image is gotten by the model of superpixel segmentation. The simulation is shown by the method which is compared in the paper. Then the result is combined with the real optimal model.

Keywords superpixel; image segmentation; regions merging

II

目 录

摘 要 ........................................................................................................................................... II Abstract ...........................................................................................................................................I

第1章 绪 论 ........................................................................................................................... 1

1.1 论文背景和意义 ............................................................................................................. 1

1.1.1 选题的背景 .......................................................................................................... 1 1.1.2 研究此课题的意义 .............................................................................................. 1 1.2 国内外研究状况 ............................................................................................................ 1 1.3 本文的主要工作 ............................................................................................................ 4 第2章 基本理论 ................................................................................................................... 5

2.1 算法的模型 .................................................................................................................... 5

2.1.1 基于图论的分割方法 .......................................................................................... 5 2.1.2 基于梯度的分割方法...........................................................................................8

2.2 几种常见的算法 ............................................................................................................ 9 2.2.1 Graph-based 方法 .............................................................................................. 9 2.2.2 Superpixel lattice 方法.................................................................................10 12.2.3

基

于

熵

率

的

方

法..................................................................................................12

2.2.4 Turbopixels 方法.............................................................................................13 2.2.5 SLIC 方法...........................................................................................................14 2.2.6 Quick Shift .......................................................................................................15 第3章 实例分析 ..................................................................................................................... 16

3.1 数据的收集与处理 ...................................................................................................... 16

3.1.1 数据集获取 ..................................................................................................... 16 3.2 图像处理效果的对比分析 ........................................................................................... 17 3.2.1 分割结果比较....................................................................................................17

3.3 提出合适的评判准则 ................................................................................................... 19

3.3.1 分割存在的问题 ............................................................................................ 20 3.3.2 超像素合并策略 ............................................................................................ 20

第4章 总结与展望 .................................................................................................................... 25

结 论 .......................................................................................................................................... 26 致 谢 .......................................................................................................................................... 27 参考文献 ...................................................................................................................................... 28

Contents

Abstra .................................................................................................. 错误！未定义书签。 Abstract ............................................................................................... 错误！未定义书签。

Chapter 1 Introduction ........................................................................................................ 1

1.1 The concept of visualization in scientific computing ........................................... 1 1.1.1 Background .................................................................................................... 1 1.1.2 significance ..................................................................................................... 1 1.2 research status ........................................................................................................ 1 1.3 main contribution ................................................................................................. 4 Chapter 2 basic theory ...................................................................................................... 5

2.1 Algorithm .................................................................................................................. 5

2.1.1 the superpixel segmentation based on graph theory .................................... 5 2.1.2 superpixel segmentation based on gradient................................................8

2.2 some classical Algorithm ........................................................................................ 9 2.2.1 Graph-based method .................................................................................... 9 2.2.2 Superpixel lattice method .............................................................................10 12.2.3the

method

based

on

entropy.........................................................................12

2.2.4 Turbopixels method .....................................................................................13 2.2.5 SLIC method .................................................................................................14 2.2.6 Quick Shift ....................................................................................................15 Chapter 3 Chapter experiments .................................................................................. 16

3.1 the collecting and preprocessing ............................................................................. 16

3.1.1 data collectin ................................................................................................ 16 3.2 contrastive analysis................................................................................................... 17 3.2.1 comparison......................................................................................................17

3.3 criteria standard ....................................................................................................... 19

3.3.1 Disadvantages ............................................................................................. 19

3.3.2 merge strategy..............................................................................................20

Chapter 4 Implementation of algorithm ........................................................................... 25

Conclusions ......................................................................................................................... 26 Acknowledgements ............................................................................................................. 27 References ........................................................................................................................... 28

第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

,v·s·cos(h)](i)，其中，h，s，v 为图像在彩色空间（HSV）的值，对于纹理图像分割F(i)=[I*f1,......,I*fn(i)]，其中fi是DOOG滤波器的输出。

Normalized cut，Ncut (归一化割分割方法)是由Shi等人提出的，测量图G所有连接节点的总边界权重为分割成本通过下式（广义特征值系统的特征值及其对应的特征向量）：

?D?W?y?yDy （2-2）

D — 对角线上为d的M×M的对角矩阵；

Ｗ— w(i,j)＝wij的M×M矩阵；

向量ｙ满足：y(i)?{1,?b},yTD1?0,１为单位向量。Ncut分割的真实解是广义特征值系统的第二个最小特征向量。

在不同的空间分离半径rij下，W性质不同，Shi等人对其进行了改进，提出了有偏差的归一化分割，相较于传统的Ncut算法，它存在两个优势：a)允许使用top-down先验证信息来寻求解决方法；b)给定未约束问题的谱方法，约束问题的解决方案可以在很短时间内计算，且允许算法以交互的模式来运行。Ｒen 等人提出了学习一个分类器来进行图像分割的方法。首先用Ncut算法将图像映射为超像素图，它认为好的分割应从相似性、邻近性和连续性等方面来评判，因此采用了经典的 Gestalt 准则来衡量分割质量的好坏，包括区域内和区域间的纹理相似性、亮度相似性、轮廓能量和曲线连续性四方面的特征。最后，归一化这些特征，并训练相应的分类器来对分割后的结果进行分类。它是一种严格的图论分割，能约束产生 许多小的、紧凑的、近似均匀区域。

基于图论的图像分割是一种自上而下的全局分割方法，其主要思想是把整幅图像看做一幅带权无向图，图像中每一个像素对应图中的一个节点，像素之间的相邻关系对应图的边，像素特征之间的差异或相似性对应边上的权重。然后在所建立的图上利用各种分割准则来对图中的节点进行划分，进而完成 对图像的分割。在基于图论的超像素计算方法中，每个像素点被视作是图里面的节点，像素之间的相邻关系对应图中的边，边的权重设置为与两节点间相似度成比例的对应值。运用图论的研究成果，根据图像中各个局部之间的关系和相似性，将图像分割成各具特性的子图的方法。它考虑的是图像全局的性质分布，相对于一些传统的分割方法具有自己的独特优势。首先，图论算法很好的体现了局部和全局之间的结合关系。由初始图像构造图时，图中连接各个顶点的边的权值体现了像素之间的局部联系，这种联系既可以是像素的灰度、颜色、纹理的相似性，也可以是这些性质的组合，或者可以有更

6

为复杂的规则。而将图分割成一个个的子图则体现了图像特征的全局分布特性。基于图论方法的这种局部和全局的结合特性，与人类视觉也有着惊人的相似。其次，引入图论做图像处理的一个很重要的优势就是可以利用大量现有的图论研究成果。

Ncut 方法是利用边缘和纹理信息递归地将图像进行分割得到结果的，综合考虑了全局和局部的信息特点获得全局最优化处理，因此，可以取得在图中所定义的能量函数的全局最小值。 将图 G = ( V，E) 分割为两个不相交的集合 A、 B，且存在 A∪B = V，A∩B = ?。评价分割质量好坏的最小割标准为

cut(A,B)??w(u,v) ( 1)

u?A,v?B使用图论中的最优化分割理论就可以获得 cut(A,B)的最小化解 Min-cut，但是这种方法存在一个严重的缺点就是偏向于割开单个节点或者小数节点集，如图

图1 最小化解 Min-cut 偏向于割开单个节点

早期的Ncut方法由Shi等人于1997年提出，并于2000年作了相应的改进。Ncut 对最小割算法进行改进，采用新颖的归一化割标准，同时度量了区域间的差异和区域内的相似性，很好地避免了最小割准则存在的缺陷。Ncut 准则定义如下:

cu(tA,B)cu(t,A)B?B? Ncu(t,A) （2） asso(c,A)Vas(so,c)BV其中: assoc( A，V) 是指子集 A 中所有节点到图中所有节点的边连接权重总

和，assoc( B，V) 也是类似的定义。这样定义两个区域之间的不相关性，使单个顶点分割的结果不再满足Ncut 值最小，因此不会偏向分割单个孤立的顶点。

Ncut( A，B) 值越低表示相似度高的顶点分配到一个子图中，相似度低的

7

顶点分配到不同子图中，是一种较理想的评价 分割质量的标准。但由于Ncut 被证明是 NP-hard 问题，且随着图中节点数目的增加，问题的求解变得异常复杂。在实际应用中，常把Ncut 准则转换为矩阵计算的形式，并求解方程的特 征值和特征向量。通常选择第二个最小特征值所对应的特征向量，它代表了图划分的最优解，并取一个合适的分裂点，将特征向量离散化为两个值，根据离散化后的值将图分割为两部分。如需要再细分，可以迭代地调用该算法进行二分。 Ncut 算法分割结果的特点是可以控制超像素的数量，且形状比较规整和紧凑。但是 Ncut 算法速度较慢，尤其对于尺寸比较大的图片，计算量很大。

Maji 等人在 Ncut 算法的基础上进行修改，提出了有偏差的归一化分割。相比于传统的 Ncut 算法，它存在两个优势: a) 允许使用 top-down 先验信息来寻求解决方法; b) 给定了未约束问题的谱方法，约束问题的解决方案可以在很短的时间内计算，且允许算法以交互的模式来运行。

2.1.2 基于梯度的分割方法

对于基于梯度的方法，由初始的粗聚类开始，通过梯度方法不断地更新聚类，直到收敛为止。

1）分水岭方法：

分水岭方法用拓扑地形图来描述一幅图像，当应用于图像分割时，图像中每个像素的灰度值表示该点的海拔高度，每个局部极小值及其影响区域为集水盆，而集水盆的边界就形成了分水岭，大致模型可用图2描述。分水岭分割算法借鉴了数学形态学的理论知识，最初由 Digabel 等人将分水岭算法引入到了二值黑白图像的分析 过程中; 随后，Beucher 等人进行了深入的探讨，建立了较为完 善的分水岭理论体系。比较经典的计算方法是 Vincent 等人提出的，采用了浸没算法的实现方案，将分水岭计算分为排序过程和浸没过程。目前三种经典的分水岭分割算法是基于梯度的分水岭分割、基于距离变换的分水岭分割和基于标记的分水岭分割。分水岭算法的优点是简洁、复杂度低、运行时间短，且提取出的物体边缘轮廓线是封闭的，能准确定位目标物体。但是它也存在一定的缺点，分水岭分割会得到成千上万的集水盆，结果很细致，导致图像出现非常严重的过分割现象。 2）基于 Mean-shift 方法

Mean-shift 算法最早在 1975 年由 Fukunaga 等人提出，1995年Cheng

8

发表的文献定义了核函数和权值系数，使 Mean-shift 算法得到了广泛应用。 Comaniciu 等人提出了一种无参数的、基于核密度梯度估计的快速统计迭代算法。其基本思想是在核窗口依次计算所有特征空间数据点的 Mean-shift 矢量，沿着 Mean-shift 梯度上升方向移动，直到收敛到密度最大处，如图3所示。通过有限次迭代计算，能够快速找到数据分布的稳定点，即模点。利用Mean-shift 做图像分割，就是把具有相同模点的像素聚类到同一超像素中的过程。该方法在实际应用中具有较好的稳定性和抗噪性，但速度慢，且由于分割时缺少图像语义信息，分割效果不够理想，存在过分割问题。

图2 分水岭示例 图3 Mean-shift 示意图

Vedaldi 等人提出 Quick-shift 分割算法类似于 Mean- shift 策略的模式搜索，但是速度更快。它不断促使像素特征空间中的每一个数据点，向着能使 Parzen 密度估计增大的最近的像素移动来实现图像的分割。该算法是非迭代的，不能明确地控制超像素的大小和数量。Wang等人提出了各向异性核 Mean-shift 方法，而不是传统的径向对称核来估计局部密度，该方法在性能上优于传统均值漂移的方法，分割后的超像素更光滑、视觉上更符合人类感知系统。Tao等人提出一种Mean-shift 与Ncut相结合的新方法，先利用 Mean-shift 算法对输入目标图像进行预处理生成超像素，再用Ncut方法进行图像分割，把每个超像素看做图的节点，解决了谱聚类在图像分割时计算量大的问题，提高了算法分割效率，但分割效果并不是很理想。

2.2 几种常见的算法

2.2.1 Graph-based 方法

Felzenszwalb 等人提出的基于图论分割方法采用了最小生成树的思想，目的是使同一区域内的元素尽可能相似，不同区域的元素尽可能不相似。该方法的思想是将一幅图像映射为无向图时，为每条边 e 定义了权值 w( e) ，它

9

用来表示边 e 所连接的两个顶点 vi 和vj的差异性。V 是图中所有顶点的集 合，一个分割S就是将V分成不同区域的一种划分，每个小区域 C∈S 对应于图G' = ( V，E') 的一个连通子图，其中 E'是E的非空子集。对于子集C?V 的内部差异就是该区域最小生成树MST ( C， E) 上的最大权值，计算公式为：

int(C)?maxw(e) (3)

e?MST(C,E)两部分子集 C1， C2 ?V 的区域间差异为连接这两部分的最小权值边，即：

minw((vi,vj)) （4） dif(C1,C2)?vi?C1,vj?C2,(vi,vj)?E如果两个部分间的区域差异 dif( C1，C2) 大于 C1、C2 中至 少一个部

分的内部差异 int( C1) 或 int( C2) ，则说明这两部分不 能合为一体，否则就可以合并，用下面公式来说明:

?trueifdif(C1,C2)?MInt(C1,C2) D(C1,C2)?? (5)

otherwise?false MInt(C1,C2)?min(int(C1)??(C1),int(C2)??(C2))

其中: 函数 τ( C) = k/ |C|， k 是常数， |C|是区域 C 的尺寸大小。 函数τ( C)用来控制两个区域 C1、C2 差异性的程度，使得区域 间的差异值必须大于它们的区域内差异。Graph-based 方法通过将图上的节点进行聚类来实现，且生成的超像素就是像素集合的最小生成树。它的运行速度很快，但不能控制超像素的数量和紧凑度。Hoiem 等人将 Graph-baased 用于深度估计中。 2.2.2 Superpixel lattice 方法

对于目前的一些超像素分割算法，存在丢失原始图像重要 的拓扑结构信息这一缺陷，Moorer 等人提出了一种 super- pixel lattice 无监督的过分割算法。该方法描述了一种能保持 图像拓扑结构的贪心算法，虽然增加了拓扑信息约束条件，但 是它在速度和分割精度上保持了良好的性能。 Superpixel lattice 算法输入的是图像的边界图，目的是搜 寻穿过图像的最小权重路径，在边界代价图最小处分割图像。 通过在垂直和水平条带两个方向搜索最优路径，不断地将图像 从垂直和水平方向进行二分来得到常规网格超像素。( a) 是将图像从左到右、从上到下依次分割图像，每条路径 将图像分为两部分，就可以得到四个区域，且在预先设定的带 条中搜索最优路径; ( b) 是不断在水平和垂直方向增加路径， 使图像被分割为九个区域。

10

（a） (b)

图3 超像素网格的形成过程

在搜索最优路径的策略上，Moore 等人采用了两种方案: s-t最小割方法和动态规划方法，前者产生任意拓扑路径，后者则产生无回归路径。其中，最优路径需要满足三个条件: a) 每条垂直和水平路径只交叉一次; b) 任意两条垂直路径不交 叉; c) 任意两条水平路径不交叉。 虽然 superpixel lattice 算法已取得良好的分割效果，但其分 割质量仍然依赖于图像边界图，且隐含地规定了图像均匀分割 需要两个机制: a) 图像带的分布均匀直接影响了路径的均匀分布; b) 最小代价路径策略有利于形成图像上相对较直和较短的路径。因此，Moore 等人.于2009 年在该算法的基础上加入先 验信息，提出了基于场景形状先验的超像素分割。利用概率密度模型来描述图像物体边界的空间密度，采用一种过分割算法，使得超像素间的密度大致相等的同时适应了局部目标边界。随后，Moore 等人又提出了 lattice-cut方法，它是一种无监督的分割，采用交替选择最优策略，用单一图像割交替地在水平或者垂直方向更新超像素边界，同时考虑了图像边界和超像素区域内的一致性。整个超像素产生过程可以用来自图 4描述。图中，( a) 首先将图像分割为均匀间距的网格超像素，且属于同个超像素中的像素点具有相同的标签;( b) ～ ( d) 建立马尔可夫随机场模型，不断交替地在水平和垂直方法更新超像素晶格边界，即改变相关像素点的标签;( e) ( f) 对于垂直或水平方向更新，像素的标签决定了该像素属于哪个垂直或水平带条。Lattice-cut 方法优于现有的计算超像素网格算法，它的性能与某些没有网格限制的分割算法具有可比性。

（c）SLIC 超像素结果及其局部放大 （d）LAttices 超像素结果及其局部放大 图4 原始图像和3种超像素结果及其局部放大比较

11

2.2.3 基于熵率的方法

Liu 等人提出的基于熵率的超像素分割算法，描述了一种基于图拓扑的能量函数。他们采用了一种新型的目标函数， 包括图像随机游走熵率和平衡项两部分。其中，熵率有利于形成结构紧凑、均匀的集群，促使获得的超像素仅覆盖图中的单一目标对象。平衡项促使集群有相似的尺寸，降低不平衡超像素的个数。该目标函数可以表示为:

(??)BA( maxH'A (6)

A其中: A 是选择的边集 A∈E， H'( A) 表示图像随机游走熵率，B ( A) 表示平

衡项，λ≥0 是一个权重值。通过最大化上述目标函数，就可以将图像进行分割。a) 熵率是用来衡量一个随机过程 X = { Xt |t∈T} 的不确定性，对于离散的随机过程，熵率可以用如下公式来表示:

H'(X)?limH(XtXt?1,Xt?2,?,Xt) (7)

t??对于图像随机游走熵率，它作为衡量集群的紧凑度和均匀程度的标准，图 G = ( V， A) 上的随机游走熵率可以表示为:

H'(X)???ui?pi,j(A)log(pi,j(A)) ( 8)

ij其中: μi = wi /wT，且 wi 是图中与节点i相连的边的权重之和，Wt是图中所有边权重的总和。Wi，j是节点i 到节点j的转移概率，Pi, j是随机游走的转移概率，其定义如下:

?wi,j?wi? p(A)??0?i,j??1??j:ei,j?Awi,j?wi?ifi?jandei,j?Aifi?jandei,j?A (9)

ifi?j虽然添加集合A中的任意边能增加熵率的值，但是选择涨幅更大的边有助于形

成紧凑和均匀的集群。如图5所示，集群( a)的紧凑度较高，且它的熵率值大于集群( b)的熵率值;集群( c) 的结构相对较均匀，且它的熵率值大于集群( b) 的熵率值。

12

（a）熵率=0.81 （b）熵率=0.43 （c）熵率=0.64 （d）熵率=0.61

图5 熵率对集群紧凑度和均匀性的作用

b) 平衡项用于促成集群具有相同的尺寸，用如下的公式表示: B(A)?H(zA)?NA???pzA(i)log(pzA(i))?NA （10）

i其中: NA是图中连通分支的个数，ZA是集群成员的分布，若边集A的图分割是S??S1,S2,?,SNA?，那么ZA的分布如式( 11) 所示: pzA(i)?SiVi??1,?,NA? (11)

图 6 展示了平衡值在获得近似尺寸集群时所起的作用。细线和粗线条连接的连通区域代表了不同的集群，( a)中集群的平衡值大于( b)中集群的平均值，且可以看出( a) 中集群分布更均匀。

(a)平衡值=-1.00 (b)平衡值=-1.19 图6 熵率对集群相似尺度的作用

2.2.4 Turbopixels 方法

Levinshtein 等人描述了一种基于几何流的水平集方法，能快速地产生超像素。他们通过膨胀初始化种子点，并结合曲率演化模型和背景区域的骨架

13

化过程，将图像分割为网格状的超像素。 Turbopixels 生成的超像素需要符合五个基本原则: a) 均匀尺寸，算法应把图像分为尺寸和形状大致相同的超像素，可以通过设计几何流来膨胀初始均匀分布的种子达到此目的; b) 连通性，每个超像素应该表示一个简单连通的像素集合，采用结合水平集的几何流扩张方法能确保此约束总是满足; c) 紧凑性，为了使超像素最大限度地紧凑，需要使强度均匀的区域在法线向外方向产生恒定的运动; d) 平滑和边缘保持，当种子增长停止时，超像素边界应该和图像边界相吻合，这需要几何流公式在边界强度弱或者没有边界的地方，曲线运动速度大，而边界强度较强的地方，曲线速度慢甚至停止，从而实现图像的分割; e) 超像素不重叠，算法应该把每个像素分配到单一超像素中。因此,当两个不同的种子膨胀到即将碰撞时，应该停止边界增长。整个算法步骤如图8所示，包括: a) 初始化等间距的种子点。b) 迭代以下步骤，直至不再有进一步的演化。( a) 第 T 次演化边界; ( b) 估计未分配区域的骨架; ( c) 更新边界上像素点的速度和在边界附近未分配像素点的速度。

（a）放置种子点 (b) 第T次化 （c）更新骨架 （d) 更新速度 （e）速度扩展 图8 Turbopixels算法步骤

该方法生成的超像素不仅保持了图像的局部边界，还通过一个紧凑度约束条件限制了欠分割。它的运算速度很快，算法复杂度与图像的尺寸成近似线性关系，并且对于万像素级图像，在几分钟内就可以获得高密度的超像素。Xiang 等人提出从待分割的图像中构建多维特征图像的方法，应用于 Turbopixel 框架超像素分割中。Cigla 等人介绍了一种快速的 Turbopixel 高效图论分割方法，先采用快速Turbopixel算法把图像分割为超像素，再建立加权图，用Ncut算法得到图的最终分割结果。

2.2.5 SLIC 方法

Achanta 等人提出了一种思想简单、实现方便的算法，将彩色图像转换为 CIELAB 颜色空间和 XY 坐标下的 5 维特征向量，然后对5 维特征向量构造度量标准，对图像像素

14

进 行局部聚类的过程。该算法速度较快，能生成紧凑、近似均匀的超像素，具体步骤为: a) 初始化种子点。假设图像有N个像素点，预分割为K个相同尺寸的超像素，那么每个超像素的大小为 N/K，且每个 种子点的距离近似为 S =

N/K。为了避免种子点处在图像

的边缘位置，以及对后续的聚类过程造成干扰，需要将种子点在 以它为中心的 3 ×3 的窗口内移动到梯度值最小的位置，同时 为每个种子分配一个单独的标签。 b) 相似度衡量。对于每个像素点，分别计算与之距离最近的种子点之间的相似程度，将最相似种子点的标签赋给该像素。通过不断迭代该过程，直到收敛，则相似度的衡量关系如下:

dlab?(lk?li)2?(ak?ai)2?(bk?bi)2 （12） dxy?(xk?xi)2?(yk?yi)2mDi?dlab?dxyS其中: dlab为像素点间的颜色差异，dxy为像素点间的空间距离，Di为两个像素的相

似度; S为种子点的间距，m为平衡参数，用来衡量颜色值与空间信息在相似度衡量中的比重。Di 取值越大，说明两个像素越相似，为了提高算法的运算速度，对每个种子点聚类时，只在以种子点为中心的 2S × 2S 区域内搜索相似像素点，而不是在整张图像中寻找（如图 9 所示）。

（a）在整张图新中的搜索 （b）SLIC在限定区域内的搜索 图9 减少像素的搜索范围

Ｒen 等人使用GPU和 NVIDIA CUDA 框架实现 SLIC 算法，能将速度提高 10 ～ 20 倍，促使 SLIC 能应用于实时系统。 Lucchi 等人利用SLIC分割算法作预处理，然后以超像素为节点、空间相邻节点以边连接建立了图模型，给出相应的条件随机场定义，提出了使用核心化特征的结构图像分割。

15

结 论

本文采用超像素作为图像目标识别的基本单元,在目标多样!背景复杂的图像中,通过对图像中每个超像素类别标签的判定,定位所要找的特定类别目标的位置,并将其与背景分割开来,最终得到目标的分割图像\

利用超像素颜色均值图对超像素邻域合并进行修正,从而使边界处的超像素尽可能与同类超像素合并,使识别结果的到较为清晰的目标边缘,最后,本文利用基于超像素的Graphcuts图论模型对目标识别结果进行分割,以超像素分类的置信值结果为数据项,以相邻超像素之间的颜色相似性和公共边界的长度为平滑项,建立GraphCuts能量函数\最小化该能量函数,从而得到本文目标识别结果的分割图,我们在具有较大挑战性的Graz一02数据集上验证了本文的算法,得到了较好的识别,率和边界较为清晰的目标识别结果分割图\通过这些工作,我们发现,在计算机实现全自动化的图像目标识别的过程中.基于局部学习的超像素级图像目标识别特征,如颜色特征,纹理特征等,来增强超像素的表现力和判别力,以提高超像素分类的准确性

超像素级的图像目标识别是一种基于部分的图像内容识别方法,以后的工作中,我们可以引入目标类型的整体模型与我们的方法相结合,使目标的部分模型与整体模型相互促进,增强图像目标识别的效果。

26

致 谢

在我的论文完成之际，首先我要感谢张太发老师，是他为我创造了良好学习的机会和环境，并给了我悉心指导和孜孜不倦的教诲，使我能在工作和学习上克服困难，取得进步。

在此要感谢我生活学习了四年的母校,母校给了我一个宽阔的学习平台,让我不断吸取新知,充实自己。需要特别感谢的是我的父母。父母的养育之恩无以为报,他们是我十多年求学路上的坚强后盾,在我面临人生选择的迷茫之际,为我排忧解难,他们对我无私的爱与照顾是我不断前进的动力。 再次感谢所有关心帮助我的亲人、老师和朋友,祝福你们!

27

参考文献

[1]王猛，李玉良，王庆飞图像处理在矿井瓦斯监控中的应用研究[J].工矿自动化，1671 -251X(2011)07 -0061 -04 .

[2]田丽军.煤矿监控中火灾图像分割方法研究[J].煤炭技术，1008-8725（2011）07-0083-03. [3]李忠杰，胡文涛，胡宁.图像分割技术在煤矿生产中的应用[J].价值工程，1006-4311（2012）11-0151-02.

[4]于淼，戚正伟．NewBluePill 深入理解硬件虚拟机[M]京: 清华 大学出版社，2011:55． [5]王春瑶，陈俊，李炜 超像素分割算法研究综述 计算机应用研究[J] 01-3695(2014) 01-0006-07 .

[6] LiuGC,Lin Z C,Yan S C,etal.Robust Recovery of Subspace Structures by Low-rank Representation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013, 35(1):171-184.

[7]ACHANTA R，SHAJI A，SMITH K,t al.LIC superpixels compared to state-of-the-art superpixel methods［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2012，34 (11) :2274-2282．

[8]LEVINSHTEIN A，SMINCHISESCH C，DICKINSON S.Multiscale symmetric part detection and grouping ［J］.International Journal of Computer Vision，2013,104(2) :117-134． [9]LUCCHI A，SMITH K，ACHANTA R,etal.Supervoxel-based segmentation of mitochondria in EM image stacks with learned shape features［J］.IEEE Trans on Medical Imaging，2012，31(2) : 474-486．

[10]WANG Shu，LU Hu-chuan，YANG Fan,et al.Superpixel tracking［C］Proc of IEEE International Conference on Computer Vision.2011:1323-1330．

[11]ZHOU Xue，LI Xi，CHIN T J，etal .uperpixel-driven level set tracking［C］Proc of the 19th IEEE International Conference on Image Processing.2012:409-412．

[12]LIU Li-wei，XING Jun-liang，AI Hai-zhou，etal．Semantic super- pixel based vehicle tracking［C］Proc of the 21st International Conference on Pattern Recognition.Berlin: Springer-Verlag，2012: 2222-2225．

[13]WANG Wei-jun，NEVATIA R.Robust object tracking using constel- lation model with superpixel［C］Proc of the 11th Asian Conference on Computer Vision.erlin: Springer-Verlag， 2012:191-204．

[14]MAJI S，VISHNOI N K，MALIK J.iased normalized cuts［C］Proc of IEEE Conference on

28

Computer Vision and Pattern Recognition，Washington DC: IEEE Computer Society,2011:2057-2064．

[15]GU Guang-hua，LI Fengcai，ZHAO Y，etal．Scene classification based on spatial pyramid representation by superpixel lattices and contextual visual features［J］.Optical Engineering，2012，51(1) :017201-1-017201-8．

[16] X.Yang, G.Zhang, J.Lu, J.Ma. A kernel fuzzy c-means clustering-based fuzzy support vector machine algorithm for classification problems with outliers or noises. 2011, 19(1): 105-115. [17] X.Zhou, D.Chen, S.Yuan. Medical brain MRI images segmentation by improved fuzzy c-means clustering analysis. Journal of Jilin University (Engineering and Technology Edition). 2009, 2(39): 381-385.

[18] I.Despotovic, E.Vansteenkiste, W.Philips. Spatially coherent fuzzy clustering for accurate and noise-robust image segmentation. IEEE Signal Processing Letters. 2013, 20(4): 295-298. [19] A.Joulin, F.Bach, J.Ponce. Discriminative clustering for image co-segmentation. IEEE Conference on Computer Vision and Pattern Recognition. 2010, 1943-1950.

[20] P.Mehrani, O.Veksler. Saliency segmentation based on learning and graph cut renement. British Machine Vision Conference. 2010.

[21]Gan L,Wu Y,Liu M,et al. Triplet Markov fields with edge location for fastunsupervised multiclass segmentation of synthetic aperture radar images [J], IET Image Processing, 6(7): 831-838,2012.

[22] Zhang L, Ji Q. Image Segmentation with a Unified Graphical Model[J], IEEE Transactions on Patten Analysis and Machine Intelligence, 32(8): 1406-1425,2010.

[23] Zhou X,Li X, Chin T J, et al. Superpixel-driven level set tracking[C]. IEEE International Conference on Image Processing, 2012: 409-412, 2012.

[24] Gong X, Liu J. Rock detection via superpixel graph cuts[C]. IEEE International Conf. on Image Processing, 2012: 2149-2152,2012.

[25] Jiang H. Linear Solution to Scale Invariant Global Figure Ground Separation[C].IEEE Conference on Computer Vision and Pattern Recognition, 2012: 678-685,2012.

[26] Li Z, Wu X M, Chang S F. Segmentation Using Superpixels: A Bipartite Graph Partitioning Approach[C]. IEEE Conference on Computer Vision and Pattern Recognition, 2012: 789-796,2012.

[27] Achanta R,Shaji A,Smith K,et al. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(11): 2274-2281,2012.

29

[28] Van den Bergh M,Boix X, Roig Q etal. SEEDS: Superpixels Extracted via Energy-Driven Sampling[M]. In European Conference on Computer Vision, 2012:13-26, 2012.

[29] Liu M Y, Tuzel O, Ramalingam S,et al. Entropy Rate Superpixel Segmentation[C].IEEE Conference on Computer Vision and Pattern Recognition, 2011: 2097-2104,2011.

[30] Zhang Y,Hartley R,Mashford J,et al. Superpixels via Pseudo-Boolean Optimization[C]. IEEE International Conference on Computer Vision, 2011:'1387-1394,2011.

30

本文来源：https://www.bwwdw.com/article/zfp2.html