图像分割方法研究

2010-11

国防科学技术大学研究生院硕士学位论文

摘 要

图像分割是图像处理中的一项基本而又关键的技术，是目标识别和图像解释的前提，多年来一直受到广泛关注。图像分割问题的典型定义就是如何在图像处理过程中将图像中的一致性区域和感兴趣对象提取出来。本文以图像分割中最常见和最基本的技术——静态图像分割为研究背景，主要研究了Mean Shift图像分割方法和基于图论的图像分割方法。

Mean Shift图像分割方法是一种统计迭代的核密度估计方法。Mean Shift算法以其简单有效而被广泛应用，但该方法在多特征组合方面和数据量较大的图像处理上仍存在不足之处，本文针对这些问题对该算法的结构进行了优化。首先，本文利用图像上下文信息对图像进行了区域合并以此来对输入数据进行了压缩；其次，本文将Dempster-Shafer理论（简称D-S理论）引入到核密度计算来实现特征空间中所有特征量的优化组合；最后，本文对这种改进的Mean Shift图像分割算法的性能进行了比较研究。

基于图论(Graph Theory)的分割是图像分割领域的一类重要方法，本文主要探讨了基于图割值的图像分割方法并对各类基于图论的分割方法进行了对比研究。归一化图割方法（Normalized Cuts）是基于图论的图像分割方法之一，该方法将图像分割问题转化为特征值求解问题。在Normalized Cuts中的一个重要问题就是如何描述图像上下文信息。本文在区域合并的基础上构建了区域邻接图并通过一种相似性度量方法来确定图像的上下文信息且将分割结果应用于建立图像分割树。

本文最后通过将图像分割方法应用于实际系统中来对本文所研究的两种图像分割方法进行比较研究并总结出了这两种方法的特点和应用效果。

关键词：图像分割，Mean Shift，Dempster-Shafer 理论(D-S 理论)，图论，标准化图割，图像分割树

第 i 页

国防科学技术大学研究生院硕士学位论文

ABSTRACT

Image segmentation is very essential and critical to image processing. It is the base of target recognition and image understanding. Image segmentation has been attracting wide attention for decades because of its great importance. In image segmentation problem, the typical goal is to extract continuous regions and interest objects in the case of image processing. Some techniques in segmentation of static images, which is the most common and basic techniques in image segmentation, are concerned in this paper. Two kinds of segmentation approaches are discussed, including segmentation based on Mean Shift algorithm and based on graph theory.

The Mean Shift algorithm for segmentation is a statistical iterative algorithm based on kernel density estimation. Mean Shift algorithm has been widely applied for its simplicity and efficiency. But the algorithm has some deficiencies in feature combination and image processing for large data. According to the deficiencies of the Mean Shift algorithm, this paper optimizes the structure of the algorithm for segmentation. Firstly, this paper introduces a method of data compressing by merging the nearest points with similar properties into consistency regions. Secondly, Dempster-Shafer (D-S) theory is introduced to optimize the combination of features. Lastly, in comparison with other approaches, the efficiency of the improved approach for image segmentation is validated.

Image segmentation based on graph theory is a main kind of segmentation methods. The segmentation based on graph cuts is deeply discussed in this paper, and a comparison is drawn among different kinds of segmentation approaches based on graph theory. Normalized Cuts is one of the most important algorithms in all algorithms based on graph theory and it translates the segmentation problem into eigenvalue solution problem. One important problem in Normalized Cuts is how to describe an image with its context information. Based on region merge application, region adjacency graph is introduced and applied to forming an image segmentation tree by adopting Normalized Cuts.

Finally, the applications of the two approaches for practical systems are implemented. And the results of experiments show the performance with the two segmentation approaches.

Key Words: image segmentation, Mean shift, Dempster-Shafer (D-S) theory, graph theory, Normalized Cuts, image segmentation tree

第 ii 页

国防科学技术大学研究生院硕士学位论文

表 目 录

表 3.1 Mean Shift图像分割信息表 .......................................................................... 25 表 4.1 几种常见的基于图割值的分割方法比较 ....................................................... 28 表 4.2 不同门限值的Normalized Cuts分割的比较 .................................................. 35 表 5.1 飞机目标图像一的检测结果 ........................................................................... 44 表 5.2 飞机目标图像二的检测结果 ........................................................................... 44

第 III 页

国防科学技术大学研究生院硕士学位论文

图 目 录

图 1.1 图像工程 ............................................................................................................. 1 图 2.1 双峰直方图 ......................................................................................................... 6 图 2.2 反向传播网络 ..................................................................................................... 9 图 3.1 Mean Shift算法过程示意图 ............................................................................. 13 图 3.2 Mean Shift算法收敛示意图 ............................................................................. 13 图 3.3 图像相邻区域数据结构图 ............................................................................... 20 图 3.4 Mean Shift分割试验图——桂林 ..................................................................... 24 图 3.5 Mean Shift分割试验图——Italy_Mountain .................................................... 24 图 3.6 Mean Shift分割试验图——Mexico_Sunset .................................................... 24 图 3.7 Mean Shift分割试验图——漓江 ..................................................................... 24 图 3.8 Mean Shift分割试验图——树林 ..................................................................... 25 图 3.9 Mean Shift分割试验图——Water_Bird .......................................................... 25 图 3.10 各种Mean Shift图像分割算法时间对比图 ................................................. 25 图 4.1 不同Ncut门限值的图像分割 ......................................................................... 35 图 4.2 图像分割树的建立过程 ................................................................................... 36 图 4.3 图像区域合并 ................................................................................................... 36 图 4.4 图像分割树对比 ............................................................................................... 37 图 5.1 飞机型号识别流程图 ....................................................................................... 39 图 5.2 卫星图像中飞机目标区域的二值化 ............................................................... 39 图 5.3 轴方向为北的飞机图像 ................................................................................... 40 图 5.4 图像中目标的方向校正 ................................................................................... 42 图 5.5 飞机目标图像一 ............................................................................................... 44 图 5.6 飞机目标图像二 ............................................................................................... 44 图 5.7 邻近图像区域数据权值结构 ........................................................................... 47 图 5.8 海陆分割图一 ................................................................................................... 49 图 5.9 海陆分割图二 ................................................................................................... 50 图 5.10 海陆分割图三 ................................................................................................. 51 图 5.11 海陆分割图四 ................................................................................................. 52

第 IV 页

国防科学技术大学研究生院硕士学位论文

第一章 绪论

1.1 图像分割简介

图像分割是从上世纪60年始被人们所研究的，它是图像分析理解与目标识别的前提，多年来一直被广泛关注。图像分割可定义为将数字图像分割成互不相交（不重叠）区域的过程[2]。在计算机视觉理论中，图像分割、特征提取与目标识别构成了由低层到高层的三大任务。图像分割是一项基础而长久的研究领域，其结果好坏直接影响计算机视觉工程各环节。

图像分割的应用非常广泛，几乎出现在有关图像处理的所有领域并涉及各种类型。图像分割的目的是把图像划分成若干互不相交的区域，使各区域具有一致性，而相邻区域间的属性特征有明显的差别。当人观察景物时，在视觉系统中对景物进行分割的过程是必不可少的。人所观察理解的并不仅仅是一个复杂的景物，而更是由多个内容组成的集合体。但是在由像元阵列构成的数字图像中，不同图像内容占据不同的连通像元集合，图像分割的任务是将整个图像分离成代表不同图像内容的像元集合的过程。尽管图像分割的任务在人类视觉感受中很难找到对照，但在数字图像处理和分析中它却是一个非常重要且艰巨的任务。

图像分割作为前沿学科充满了挑战，吸引了众多学者从事这一领域研究。图像处理技术在航空航天、生物医学工程、工业检测、机器人视觉、司法、军事制导、文化艺术、地理测绘等领域受到广泛重视，并取得了重大的开拓性成就，使图像处理成为一门引人注目、前景远大的新型学科。

图像理解图像工程图像分析图像分割图像处理 图 1.1 图像工程

对于图像分割在图像工程中所处的地位，图1.1给出了很好的诠释。图像工程可分为图像处理、图像分析和图像理解三个层次。图像处理属于低层操作，着重

第 1 页

国防科学技术大学研究生院硕士学位论文

强调在图像之间进行变换以改善图像的视觉效果，主要在图像像素级上进行处理。图像分析则进入了中层，是对图像中感兴趣的目标进行检测和测量以获得它们的客观信息，从而建立对图像的描述。图像理解是高层操作，是在图像分析的基础上，进一步研究图像中各目标的性质和它们之间的相互联系，也可以理解为是对从描述中抽象出来的数据符号进行运算推理。图像分割是从图像处理到图像分析的关键步骤，也是进一步图像理解的基础，所以在图像工程中占据重要地位。

目前，随着图像分割在医学、遥感、电子商务、专利检索和建筑设计等领域的广泛应用，人们不断寻找新的理论和方法来提高图像分割的效果。随着不同学科研究人员对图像分割的日益关注，新的理论和方法会不断应用到更多领域中去。

1.2 图像分割方法研究

图像分割技术研究是图像处理领域中的一项重要内容，至今已有上千种不同类型的方法问世，要把常用的图像分割方法加以分类和介绍并不是一件容易的事情，至今也没有一种统一的为所有学者所接受的分类方法。文献[1]根据图像本身的特点把灰度图像分割和各种特殊图像（例如彩色图像、深度图像，纹理图像等）的分割方法分开来讨论，在灰度图像分割的基本算法中又把传统的分割方法和与特定理论工具结合的方法分开讨论。文献[2]把图像分割算法分成阈值分割、边界检测和区域提取三类。文献[34]把图像分割方法分成度量空间引导的空间聚类、单连接区域生长体系、多连接区域生长体系、质心连接区域生长体系、空间聚类体系和合并体系等六类方法来进行讨论。文献[35]把图像分割算法分成阈值分割、像素分类、深度图像分割、彩色图像分割、边界检测和基于模糊集理论的分割六类方法来讨论。

近年来，随着各学科许多新理论和新方法的提出，人们也提出了许多结合一些特定理论、方法和工具的图像分割技术。由于图像分割技术至今尚无通用的自身理论，所以每当有新的数学工具或方法提出来，人们就尝试着将其用于图像分割，因而提出了不少特殊的算法。在这些算法中，比较典型的有基于数学形态学的图像分割方法、基于模糊理论的图像分割方法、基于神经网络的图像分割方法、基于支持向量机的图像分割方法、基于图论的图像分割方法、基于免疫算法的图像分割方法、基于粒度计算理论的图像分割方法等等。

本文根据各种图像分割方法的统计特性，将图像分割方法分为结构分割方法和非结构分割方法来讨论。结构分割方法是根据图像的局部区域像素的特征来实现图像分割的方法，如灰度阈值、区域生长和纹理结构分析等。这些方法是假定预先知道这些区域的特性，或在处理中能够提取这些特性来研究各类像素群。本

第 2 页

国防科学技术大学研究生院硕士学位论文

文根据这类方法的特点，着重研究了Mean Shift图像分割方法。非结构分割方法是根据图像的二维或线性模型来构造分类的特征矢量进而实现图像分割的方法，如基于水平集的分割方法、基于神经网络的分割方法和基于先验模型的方法等。本文在非结构分割方法中主要讨论了基于图论的分割方法。

1.3 论文的主要工作和结构组织

本文的研究内容是静止图像的分割方法。本文根据图像分割方法的不同结构特性，着重讨论了基于Mean Shift的图像分割方法和基于图论的图像分割方法。

论文主要工作在于：

1、通过分析典型Mean Shift算法的优点和不足，并针对实际应用提出一种快速Mean Shift算法的整改方案。

2、结合矩阵论的知识，运用图的理论来重点分析Normalized Cuts的特性，并针对Normalized Cuts的算法问题所在提出基于Normalized Cuts的图像分割树的实现方案。

3、将Mean Shift图像分割算法应用于飞机型号识别并合理运用目标的统计信息来对卫星图像中飞机目标进行提取与匹配识别。

4、将Normalized Cuts应用于海陆分割并将海陆图的所有特征信息融合于Normalized Cuts的权值函数中来实现一种较好的海陆分割系统。

论文的组织结构如下：

第二章简述图像分割的概念并对各种图像分割方法进行分析和对比研究。 第三章研究自底向上的Mean Shift图像分割算法。 第四章研究基于图论的自顶向下的图像分割算法。

第五章把Mean Shift图像分割方法和基于Normalized Cuts的图像分割方法应用于具体系统当中，并通过实例分析来验证这两种方法的可行性。

第六章对全文工作和主要创新点作了总结，并展望图像分割技术的研究方向和应用前景。

第 3 页

国防科学技术大学研究生院硕士学位论文

第二章 图像分割的基本概念与方法

2.1 图像分割的基本概念

图像分割是将图像中具有特殊意义的不同区域分开来，并使这些区域相互不相交，且每个区域应满足特定区域的一致性条件。这里的区域是像素的连通集[2]。现将连通路径[2]与连通集的定义如下：

定义2.1（连通路径） 像素集合中的一条可在相邻像素间移动的路径，称之为连通路径。

定义2.2（连通集） 在一个像素集合中，任意两个像素之间都存在一条完全由这个集合的元素构成的连通路径，这样像素集合称之为连通集。

连通性的准则一般分为4连通和8连通两种。如果只依据旁侧相邻的像素（上、下、左、右）确定连通，就称为4连通。如果在把旁侧相邻的连通域进行对角相邻（45度相邻点）的扩展，那么就得到8连通。通常8连通的结果与人的感觉更接近。如果把一幅图像中所有像素的集合记作F，有关均匀性或者区域同质性的判别准则记为P。则图像分割的形式化语言定义如下：

定义2.3（图像分割的一般模型） 把一幅图像中所有像素的集合F划分为若干子集{S1,S2,...,Sn}，其中每个子集都构成一个空间连通区域，并且满足：

(1)USj=F;

j=1

n

(2)SiISj=φ,i≠j;(3)P(Sj)=TRUE,∀j;(4)P(SiUSj)=FALSE,i≠j;

(2.1)

式中，φ表示空集，P(•)为集合F的逻辑谓词。这样的划分{S1,S2,...,Sn}称之为图像分割的一般模型。

在以上定义的模型中，同质性判断标准P可以根据图像的灰度、纹理和几何度量结构来得到。

2.2 图像分割的基本方法

图像分割一般根据要解决的问题来将图像细分为感兴趣对象的集合，其分割方法的种类已达上千种。针对各种图像分割的特点，一般可根据分割对象、分割

第 4 页

国防科学技术大学研究生院硕士学位论文

策略以及分割方法的统计特性等来进行具体分类。

根据图像分割的不同对象可分为灰度图像分割和彩色图像分割。根据文献[23]中的讨论，我们一般都能将灰度图像的分割方法扩展到彩色图像分割中去，但彩色图像能够提供更多的信息量，所以在进行彩色图像分割时，可以根据彩色空间的不同通道进行分割，然后再进行融合处理。

根据图像分割的不同策略可将图像分割方法分为基于区域之间的不连续性和基于区域内部的相似性的分割方法[29]。区域之间的不连续性一般用于边界提取，通过先找到点、线（宽度为1）、边（不定宽度），再确定区域的划分。区域内部的相似性一般用于区域分割，通过一定的相似性准则判断图像各像素点的所属区域，最终区域的外轮廓就是对象的边（分界线）。这种分类方法很好的阐述了分割方法的基本策略，但不能够对分割方法进行有效划分，因为很多图像分割方法可以将这两种策略作为不同的图像特征结合到一起来处理，如基于神经网络的图像分割方法。

根据图像分割的不同对象来进行的方法分类不够具体，而根据图像分割的不同策略来进行的方法分类又存在诸多分类不清，本文根据图像分割方法的统计特性将图像分割方法分为基于图像局部特征的图像分割方法和基于模型的图像分割方法。

2.2.1 基于图像局部特征的图像分割方法

基于图像局部特征的图像分割方法是根据图像局部区域中像元的特征来实现图像分割的方法。下面主要介绍下阈值分割法、边缘检测法、区域生长和特征空间聚类法。

2.2.1.1 阈值分割法

阈值分割法是一种传统的图像分割方法，因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。阈值法在不同物体或结构之间有很大的强度对比时，能够得到很好的效果。它计算简单，而且总能用封闭而且连通的边界定义不交叠的区域。当使用阈值规则进行图像分割时，所有灰度值大于或等于某阈值的像素都被判属于物体。所有灰度值小于该阈值的像素被排除在物体之外。于是，边界就成为这样一些内部点的集合，这些点都至少有一个邻点不属于该物体。一般情况下，阈值运算可以看作图像中某点的局部特性（如平均灰度）及该点在图像中位置的检验，其检验函数可记作T(x,y,g(x,y),N(x,y))，其中g(x,y)表示图像中点(x,y)的灰度，N(x,y)表示图像中点(x,y)的局部邻域特性。

第 5 页

国防科学技术大学研究生院硕士学位论文

阈值法从阈值选择范围上分为全局阈值、局部阈值和自适应阈值三种，即 全局阈值 T=T(g(x,y))

（只与点的灰度有关）

局部阈值 T=T(g(x,y),N(x,y)) （与点的灰度和邻域特性有关） 自适应阈值 T=T(x,y,g(x,y),N(x,y)) （与点的位置、灰度和邻域特性有关） 简单阈值选择通常是利用直方图技术[2]。假设一幅灰度图像由两个区域组成，一个区域以亮色为主，另外一个区域以暗色为主，那么直方图有两个峰（一个峰对应于表示物体的灰度值，另一个峰对应于表示背景的灰度值）如图2.1所示。于是在两峰之间的选择一个值就可以作为图像分割的阈值。

图 2.1 双峰直方图

基于阈值分割法虽然简单，但在阈值的选取很大程度上影响图像分割的效果，它只考虑像素本身的灰度值，而不考虑图像的空间分布，这样其分割结果就对噪声很敏感，对从事图像分割的人员的先验知识依赖过强。虽然目前出现了各种甚于阈值分割的改进算法。图像分割的效果有所改进．但在阈值的设置上还是没有很好的解决方法，若将智能遗传算法应用在阈值筛选上，选取能最优分割图像的阈值，这可能是基于阈值的图像分割法的发展趋势。

2.2.1.2 边缘检测法

边缘检测法是基于图像不连续性的分割技术。由于一幅图像的大部分信息存在于不同区域的边缘上，而且人的视觉系统在很大程度上根据边缘差异对图像进行识别分析，所以可以通过检测图像的边缘信息来实现对图像的分割。基于边界检测的分割方法其基本思想是先检测图像中的边界点，再按一定策略连接成轮廓，从而构成分割区域。这类方法有两个主要的技术难点，即边界检测和边界连接。简单的边缘检测可以借助空域微分算子通过卷积完成。常见的边界检测方法包括（如Roberts算子，Sobel算子，Prewitt算子，Canny算子、基于各种边界检测算子[1]

二阶方向导数算子，Laplacian算子，LOG边界检测算子等）的边界检测、多尺度边界检测、基于曲面拟合的边界检测、基于模糊数学的边界检测、基于数学形态

第 6 页

国防科学技术大学研究生院硕士学位论文

学的边界检测、基于神经网络的边界检测、基于统计判决的边界检测等。

基于边界检测的图像分割在边界检测后通常需要把得到的边界连接起来，常见的边界连接方法可以分成两大类，即局部方法和全局方法。局部方法通常是在每个边界点的小邻域内搜索并连接相近的点，而全局方法通常是把图像平面上所有边界点视为一个整体来考虑。常用的全局边界连接方法有基于Hough变换的边界连接方法、基于网络搜索的边界连接方法和基于动态规划的边界连接方法等。

2.2.1.3 区域生长

区域生长[1]是一种已受到人工智能领域中的计算机视觉界十分关注的图像分割方法。这种分割方法的基本思想是把具有相似性质的像素集合起来构成区域。具体实现是在每个分割区域内寻找一个种子像素，根据事先确定的生长或相似准则，在种子周围邻域内寻找与种子像素具有相同或相似性质的像素并将其合并到种子所在的区域。生长准则一般可分为三种：基于区域灰度差准则、基于区域内灰度分布统计性质准则和基于区域形状准则。区域生长技术的关键有三点：一是选择或确定一组能代表所需区域的种子元素；二是确定在生长过程中的相似准则或者生长准则；三是确定生长过程的停止条件。区域生长方法可分为单连接区域生长、多连接区域生长、质心连接区域生长、基于子区域合并的区域生长等。

区域生长是一种典型的串行区域分割方法，其特点是将处理过程分解为多个顺序步骤，其中后续步骤的处理要根据对前面步骤的结果进行判断后确定。采用区域生长法的关键在于种子点的位置选择、生长准则和生长顺序。此方法最简单的形式是先人工给出一个种子点，然后提取出和此种子点具有相同灰度值的所有像素。一般的区域生长法存在的问题是：(1)如何定义区域一致性准则；(2)其分割结果和种子点的选择有很大关系；(3)对噪声很敏感；(4)很容易产生过图像过分割现象。

2.2.1.4 特征空间聚类法

特征空间聚类法是通过聚类的方法对图像特征空间进行相似性划分。用聚类方法做分割应用较为广泛，其基本原理是把图像空间中的元素映射到某个特征空间中，通过将特征空间的点聚集成团，然后再映射回原图像空间以得到分割的结果。

特征聚类方法众多，特征聚类可以是单特征聚类(比如基于颜色特征的K均值聚类[1])，也可以是多特征聚类（比如基于坐标和颜色特征的Mean Shift算法[8]）。特征聚类按照元素与类别之间的隶属关系可分为硬性聚类和模糊聚类；按照各类别之间的关系可分为基于类划分的聚类和分等级的聚类；按照聚类方法所基于的

第 7 页

国防科学技术大学研究生院硕士学位论文

技术又可以分成基于核技术的聚类、基于神经网络技术的聚类、基于图论技术的聚类、基于组合优化技术的聚类、基于向量量化的聚类、基于模糊集技术的聚类等。如果把特征空间简单地认为是灰度值空间，则阈值分割可以看作是聚类分割的一个特例。

聚类法必须解决的两个关键问题就是：一是如何选定样本之间的类似程度；二是如何根据样本之间的类似程度将给定的样本集划分为不同的类群。在特征空间聚类的分割中，图像特征的提取、相似度的计算和正确的聚类方法是算法研究的关键。从目前的研究动向看，能自我学习自我记忆的聚类分析算法将是图像处理中的一个研究热点。

2.2.2 基于模型的图像分割方法

基于模型的图像分割方法是根据图像的二维或线性模型来构造分类的特征矢量进而实现图像分割的方法。下面主要介绍基于偏微分方程的图像分割方法、基于神经网络的图像分割方法和基于图论的图像分割方法。

2.2.1.1 基于偏微分方程的图像分割方法

基于偏微分方程（PDE）的图像分割方法通常是用曲线演化过程来完成分割。分割过程通常从图像平面上一条任意位置的闭合曲线开始。曲线在内力（由曲线的固有属性驱动）和外力（由图像数据驱动）的共同作用下不断演化，最终停止在图像中物体的边界，从而把图像分割成不同的部分（曲线内部和曲线外部）。这一类模型通常是给出包含曲线和图像数据在内的目标函数，然后通过最小化目标函数得到曲线的演化流，即描述曲线演化过程的偏微分方程。最早应用于图像分割的PDE模型称为活动轮廓线模型，即Snake模型[37]。设C(q):[0,1]→R2是参数化的一条平面曲线，μ0:Ω→R+是给定要分割的图像，则Snake模型就是寻找能使下面能量函数最小的曲线:

1

2

1

2

1

2

E(C)=θ∫C'(q)dq+γ∫C\"(q)dq−λ∫∇μ0(C(q))dq (2.2)

0

0

0

其中λ、γ和θ都是正的实数，∇μ0是图像梯度的幅度。

基于PDE的曲线演化通常通过水平集方法[38]来实现。水平集方法的基本思想是先把二维平面上的曲线C表示成三维空间中平滑曲面的零水平集，即

C(x,y,t)={(x,y)|Φ(x,y,t)=0}，然后用曲面Φ的演化来实现曲线的演化。水平集演化的主要优势在于可方便地处理几何拓朴的变化，此外，曲线的一些诸如曲率、法向量等几何特征都可以方便地用曲面的函数表示出来。

2.2.1.2 基于神经网络的图像分割方法

第 8 页

国防科学技术大学研究生院硕士学位论文

神经网络方法将图像分割问题作为一个函数最小化问题来处理，其主要思想是利用已知确定结果的样本模式对网络进行训练，然后利用训练好的网络进行图像的处理或识别。在众多神经网络算法中，反向传播（BP）学习算法是最著名的多层前向反馈式神经网络训练算法之一。BP算法在图像处理和图像识别领域已经取得令人瞩目的成就。BP算法的构造过程如下：假设一个神经网络是由许多相互连接的相同结点构成，并把这些结点称为处理单元（PE）。每一个PE的动作都是比较简单的，一个PE从处于“上游”的几个PE接受输入信号并产生一个标量输出，然后传给处于“下游”的PE，这样我们就建立了一个反向传播网络，其示意图如下：

图 2.2 反向传播网络 基于神经网络的图像分割方法通过使用大量的平行的神经网络来达到对图像进行有效分割的目的。这些网络由模拟生物学习机理的节点或者元素组成，网络中的每个节点能够执行最基本的运算，并通过调整节点之间的权值可以达到网络对生物机理的学习。使用神经网络法的时候，因为网络中有许多相互连接，所以空间信息就能很容易包涵在分类过程中。

由于神经网络是由许多神经处理单元互相连接组成的庞大网络，其巨大的连接结构和分布的处理单元，使得系统具有鲁棒性、并行性及实时性。近年来，人工神经网络技术与模糊技术的结合被应用于图像分割中，该方法使得分割过程既考虑了图像上下文的信息又结合了模糊技术的优点（不完善、不精确知识情况下的决策）和神经网络的优点（实时性、鲁棒性、智能性和抗噪性），因此会显著提高分割效果。

2.2.1.3 基于图论的图像分割方法

在众多的图像分割方法中，基于图（Graph-based）的分割方法显示出强大的优势。它可以有效地结合图像灰度、纹理和色彩等各种信息来达到满意的分割效

第 9 页

国防科学技术大学研究生院硕士学位论文

果。此外，图论（Graph theory）中诸多成熟而完美的经典算法又为这一类图像分割算法提供了有力的计算工具，因此基于图论的分割算法近年来受到广泛关注。常见的基于图的分割方法[11]包括基于最小生成树（Spanning tree）的分割，基于支配集（Dominant set）的分割和基于最小图割值(Graph cut)的分割等，其中以基于图割值的分割方法应用最为广泛。

基于最小图割值分割的工作原理是把图像视为一个无向的权值图，图的顶点对应图像的像素或者区域，权值则反应了两个像素或者区域之间的相似程度，同时定义一个用图像的某种割值来表示的目标函数，并通过求解目标函数的极值来实现分割。各种分割方法的目标函数不同，求解手段也多种多样，使得基于图割值的分割框架下的内容丰富多彩。常见的基于图割值的分割方法[11]包括谱分割、等周分割、最小割值、Normalized Cuts、平均割值、比例割值和均值割值等。本文第四章也将对以上几种基于图割值的方法进行简单的比较并着重讨论了基于Normalized Cuts的图像分割方法。

第 10 页

国防科学技术大学研究生院硕士学位论文

第三章 Mean Shift 图像分割方法研究与改进

3.1 Mean Shift简述

Mean Shift算法是由Fukunaga和Hostetler[4]在1975年提出来的，但开始并未引起人们的兴趣。直到1995年，Cheng[6]通过定义一组核函数来组织Mean Shift算法使得该算法得以广泛应用。Mean Shift算法的基本过程是通过迭代的方法找到特征空间中各类的中心并以此来进行聚类。

Mean Shift算法虽然从提出来到现在已经有几十年，但随着计算机视觉领域的不断发展，该算法一直都被广泛研究和应用着。在图像分割领域，Mean Shift算法以其深刻研究价值展示出很强的生命力。2002年，Comaniciu and Meer[8]通过特征空间分析证明了Mean Shift算法是一种鲁棒性很强的算法。2007年，Miguel A. Carreira-Perpinan[10]证明了高斯Mean Shift算法是一种期望最大化（EM）算法。近些年来，Mean Shift算法被广泛用于目标跟踪与识别、图像滤波和信息融合等领域。然而，Mean Shift算法虽然简洁可靠，但其算法复杂度随着数据的增加呈平方增长。为了提高效率，该领域的专家们做了很多有效的工作。Changjiang Yang[39]引入快速高斯变换来改进该算法，大大提高了该算法的效率。H. Guo[19]通过采用一种新的迭代策略来提高Mean Shift算法的迭代计算速度。Daniel Freedman[9]则采纳随机技术来提高Mean Shift算法的核计算速度。Kai Zhang[13]则采用了以区域代替像素点的数据压缩策略来减少计算量。所有的这些改进都推进了Mean Shift算法的发展。另外，Mean Shift算法在多特征组合上存在一些不足，尤其在多模态复杂场景图像中Mean Shift图像分割的效果不尽人意。本文针对以上问题采用D-S理论对Mean Shift算法的特征空间组织结构进行了优化，并引入一种新的区域合并方法来对核空间的数据进行压缩处理，从而提高了Mean Shift图像分割的质量与效率。

3.2 Mean Shift算法的基本原理

Mean Shift算法是一种统计迭代的算法，其基本思想就是从特征空间中的某点开始沿着滑动窗口中梯度方向移动直到收敛。下面从核密度估计、Mean Shift算法过程、Mean Shift算法收敛性分析以及特征空间分析四部分来具体讨论Mean Shift算法。

第 11 页

国防科学技术大学研究生院硕士学位论文

3.2.1 核密度估计

核密度估计（亦称Parzen窗估计）是对密度函数的一种非参数估计，它是统计模式识别中密度函数估计的重要形式。这种密度估计方法对先验知识要求很少，而且完全依靠训练数据进行估计，可以用于任意形状密度函数的估计，因此核密度估计得到了广泛的应用。

定义3.1（核密度估计） 假设已知d维空间的n个采样点{xi,i=1,2,...,n}，则密度函数f(x)的估计为：

n

fˆ(x)=

∑w(x)K

i

i=1

ni=1

H

(x−xi)

(3.1)

i

∑w(x)

KH(x)=H

−1/2

其中，w(xi)为权系数，KH(x)为核函数，其计算公式如下：

K(H

−1/2

x) (3.2)

这里的H是一d×d的参数矩阵，则通过这种方式得到的密度估计称为核密度估计。

一般情况下，定义3.1中的核函数KH(x)可以表示成x范数的剖面函数，其具体形式如下：

2

K(x)=ck,dk(x) (3.3)

通常核函数可选为Epanechinov核，其剖面函数形式如下：

⎧1−x0≤x≤1

kE(x)=⎨ (3.4)

0x>1⎩

Epanechinov核是通过最优化核密度估计值与实际密度值的均方误差得到的一种核函数形式[8]，但其边界的一阶导数不是连续的。考虑到边界导数的连续性，也可将核函数选为高斯核，其剖面函数形式如下：

1

kN(x)=exp(−x)

2

x≥0 (3.5)

在应用高斯核函数时，为了计算方便，一般采用高斯核函数的截断形式。

另外，如果参数矩阵H是满矩阵（即矩阵H的每个元素都不为零），则核密度估计的计算复杂度会大大增加。因此，在实际应用中，一般将H表示为对角矩阵H=diag[h1,h2,...,hd]或表示成单位比例矩阵H=h

2

2

2

2

I。

考虑公式(3.1)，当w(xi)取常数且H为单位比例矩阵时，核密度估计函数可写为：

第 12 页

国防科学技术大学研究生院硕士学位论文

x−xi

ˆfh,K(x)=d∑k() (3.6)

nhi=1h

这样，根据这种简化的核密度估计函数，我们可以更加有效的进行核密度计算。

3.2.2 Mean Shift算法过程

Mean Shift算法过程是一个迭代收敛的过程，一般包括三部分：一是选择数据窗口来估计特征空间数据点的概率密度；二是计算当前窗口的数据中心；三是将窗口中心移动到数据中心。

下面通过一个简单的图示来说明Mean Shift算法过程中的一步迭代。我们以点代表数据点，圆代表数据窗口，则其示意图如下：

感兴趣数据窗口 该窗口的数据中心 ck,d

n

2

Mean Shift矢量

图 1.1 Mean Shift算法过程示意图

从上图可以很明显的看出，Mean Shift的收敛中心必然满足窗口中心与数据中心重合而且该收敛中心对应于数据密度的峰值。

图 3.2 Mean Shift算法收敛示意图

第 13 页

国防科学技术大学研究生院硕士学位论文

根据一般的梯度下降法，我们考虑公式(3.5)的核密度估计函数，则通过计算其微分可以得到：

x−xi

ˆ(x)=xxk∇f−()'() h,Kid+2∑nhi=1h

定义一个剖面函数g(x)=−k′(x)，该函数所对应的核函数为：

G(x)=cg,dg(x)

ˆ(x)∇fh,K

x−xi

)=d+2∑(xi−x)g(

nhi=1h

2

⎡⎡nx−xi⎤⎤

)⎥⎥⎢⎢∑xig(2nh⎡⎤2ck,dx−xi⎥⎢⎢⎣i=1⎦−x⎥()=dg⎢⎥∑⎢⎡n⎥2

nh+2⎢h⎤1=i−xx⎥⎣⎦⎢i⎥)⎥⎢∑g(

⎢⎢i=1⎥h⎥⎦⎣⎣⎦

2ck,d

n

2

(3.7)

2

(3.8)

这里的cg,d是一个归一化常量，结合公式(3.7)，我们可以得到：

2ck,d

n

2

(3.9)

核函数G(x)的核密度函数为：

x−xi

ˆ(x)=fg() h,Gd∑nhi=1h

这里我们再定义一个Mean Shift矢量，即：

cg,d

n

2

(3.10)

x−xi

xg()∑i

h

mh,G(x)=i=1−x 2n

x−xig()∑hi=1

n

2

(3.11)

由此，我们可以得到Mean Shift矢量的另一种形式，即：

))12cg,d∇fh,K(x)12∇fh,K(x)

)mh,G(x)=h=hc)

2ck,dfh,G(x)2fh,G(x)

(3.12)

上式表明Mean Shift矢量的方向始终指向数据密度梯度的最大下降方向，所以这也就说明了Mean Shift算法过程的收敛点处必有∇f

3.2.3 Mean Shift算法收敛性分析

由于Mean Shift算法是一种统计迭代算法，所以其收敛性非常重要。关于Mean

第 14 页

(x)=0。

国防科学技术大学研究生院硕士学位论文

Shift算法收敛性问题，文献[6]指出其收敛性与剖面函数有关，文献[8]对Mean Shift算法在采用凸的剖面函数来进行核密度估计的情况下的收敛性给予了严格的证明。下面我们通过一个定理来说明Mean Shift的收敛性。

根据公式(3.12)，定义一组数据点{yj},j=1,2,...，其递推过程如下：

∑xg(

i

n

yj−xi

hyj−xi

h

2

2

)

=yj+mh,G(yj) (3.13) )

yj+1=

i=1

∑g(

i=1

n

根据上式引出以下定理：

定理 3.1 如果核K有一个单调递减的剖面凸函数k(x)，则序列yj

{}j=1,2,...

和

{{)

fh,K(yj)

}}j=1,2,...

)

收敛，且fh,K(yj)

{}j=1,2,...

单调递增。

)

证明如下：首先，既然n是一个有限值，而fh,K(yj)是有界的，所以要证明))fh,K(yj)且单调递增，我们只需证明fh,K(yj)是严格递增的，也就等价于：对

j=1,2,...

))

于yj≠yj+1，有fh,K(yj)对于j=1,2,...，并假设yj=0则，根据公式(3.5)，我们可得：

fˆh,K(yj+1)−fˆh,K(yj)=

ck,dnh

d

∑k(

i=1

n

yj+1−xi

h

2

x−i

h

2

)

(3.14)

根据剖面函数k(x)的凸面性，我们可以得到：

k(x2)≥k(x1)+k'(x1)(x2−x1)

(3.15)

又令g(x)=−k'(x)，则∀x2,x1∈[0,∞)且x2≠x1，根据(3.15)可以得到：

k(x2)−k(x1)≥g(x1)(x1−x2)

结合(3.14)与(3.16)，我们可以得到：

(3.16)

fˆh,K(yj+1)−fˆh,K(yj)≥

ck,dnhd+2ck,dnhd+2ck,dnh

d+2

∑

i=1n

n

xg(i

hxg(i

h

n

2

)(xi

2

2

−yj+1−xi)x−yj+1))−yj+1

22

2

==

∑

i=1

)(2y

T

j+1i

2

n

(2yTj+1∑

i=1

x

xig(i

h

∑

i=1

xg(i

h

2

))

第 15 页

国防科学技术大学研究生院硕士学位论文

又根据(3.13)，我们有：

fˆh,K(yj+1)−fˆh,K(yj)≥

由于剖面函数k(x)对于所有的x≥0，∑

i=1n

ck,dnh

d+2

2

yj+1

2

∑

i=1

n

x

g(i

h

2

)

(3.17)

xg(i

h

所以只要yj+1≠yj=0，)是正的，

ˆ(y)>fˆ(y)。公式(3.17)的右边是正的，所以f又∀yj≠0，根据公式(3.17)，h,Kj+1h,Kj

我们可以推导出：

ˆ(y)−fˆ(y)≥fh,Kj+1h,Kj

ck,dnh

d+2

yj+1−yj

2

∑g(

i=1

n

yj−xi

h

2

)

(3.18)

)

ˆˆ同理可得fh,K(yj+1)>fh,K(yj)，因此，序列fh,K(yj)

{}j=1,2,...

单调递增且收敛。

在推导yj

{}j=1,2,...

的收敛性过程中，根据公式(3.18)，我们可以得到：

ˆ(y)≥fˆh,K(yj+m)−fh,Kj

ck,dnh+

d+2

yj+m−yj+m−1yj+1−yj

2

2

∑g(

i=1

n

yj−xi

h

2

2

)+...

ck,dnhd+2

∑g(

i=1

n

yj−xi

h

)

(3.19)

ck,d⎡22

⎤Myyyy...−++−j+mj+m−1j+1jd+2⎢⎥⎦nh⎣

c2

≥kd,d+2yj+m−yjM/2nh≥

其中，M表示在yj的。由于{fh,K(yj)})

{}j=1,2,...

求得∑g(

i=1

n

yj−xi

h

2

)的最小值，一般情况下均是严格正

j=1,2,...

收敛，且为Cauchy序列，根据公式(3.19)，由比较法可知，

{y}j

j=1,2,...

也是收敛的。

3.3 典型的Mean Shift图像分割算法

将Mean Shift算法用于图像分割，一般要解决三个问题：一是如何获取图像的特征数据；二是怎样基于图像的特征数据进行核密度估计；三是如何确定图像数据聚类的策略。下面我们先通过基于图像数据的核密度估计来解决前两个问题，然后通过具体的图像分割算法阐述图像数据聚类的策略，最后我们对典型的Mean Shift图像分割算法进行算法分析。

第 16 页

国防科学技术大学研究生院硕士学位论文

3.3.1 基于图像数据的核密度估计

在典型的Mean Shift图像分割里面，图像特征一般选为颜色特征和坐标特征。对于颜色特征，由于RGB颜色空间模型对人眼视觉作用的效果是非线性的[23]，所以本文采用了LUV颜色空间模型[1]，并以L通道的颜色值作为颜色特征来参与图像数据的核密度估计。而坐标特征则选取横坐标和纵坐标的二维空间数据作为图像的特征数据。

为了进一步说明基于图像数据的核密度估计，我们假设一幅大小为m×n的图像上各像素点的特征数据为一个三维矢量集{xij,i=1,2,...,n,j=1,2,...,m}，且该矢量的各分量分别代表横坐标、纵坐标和L通道颜色值。则根据公式(3.5)，我们可以得到数据空间{xij,i=1,2,...,n,j=1,2,...,m}中的核密度估计为：

fˆh,K(x)=

L

C

ck,dnh

d

∑∑k(

j=1i=1

mn

L

xL−xij

2

hL

)k(

C

xC−xij

2

hC

) (3.20)

其中，x与x分别表示x的L通道颜色值和坐标值，hL与hC表示L通道颜色值和坐标值的核带宽。

3.3.2 典型的Mean Shift图像分割算法

基于Mean Shift的图像分割算法是一种特征空间聚类算法，假设图像数据为

{xij,i=1,2,...,m,j=1,2,...,n}，则结合公式(3.13)和(3.20)，假设{yk},k=1,2,...为

一组图像特征空间上的数据矢量集且y1=xij，我们可以得到图像分割中的Mean Shift算法的迭代过程为：

2

2

∑∑

yk+1=

m

mn

xig(g(

yy

Ck

−xhC−x

Cij

)g(

2

y−xhLy−xhL

Lk

LkLij

)

2

j=1i=1

∑∑

n

CkCij

j=1i=1

hC

)g(

Lij

(3.21)

)

其中g(x)为图像特征空间的核剖面函数的负导数。又假设M为一个区域的最小像素个数。则Mean Shift图像分割算法描述如下：

第一步：选择Epanechinov核作为核函数。

第二步：对于图像上的每个点，根据公式(3.21)计算其收敛点，记为zij； 第三步：在数据集{zij,i=1,2,...,n,j=1,2,...,m}上进行特征聚类，将坐标空间的欧氏距离小于hC且颜色空间距离小于hL的数据点聚为一类，并记所有的特征类集

第 17 页

国防科学技术大学研究生院硕士学位论文

为{Cp}p=1,2,...,q；

第四步： ∀i=1,2,...,n,j=1,2,...,m，图像数据空间的类标记为Lij={p|zij∈Cp}。 第五步：消除元素个数小于M的类。 3.3.3算法分析

Mean Shift图像分割算法是一个特征空间任意形状的聚类方法，为了进一步分析该算法的性能，本文主要从核带宽选择、特征空间分析、收敛性分析以及计算复杂度分析四方面来研究该算法。

3.3.3.1 核带宽选择

带宽矩阵H是Mean Shift算法中的一个重要参数，它决定了算法的计算效率。一般有四种选取带宽矩阵的方法，具体如下：

1）基于全局统计信息的最佳带宽选择方法。该方法的带宽矩阵选择一般是通过衡量估计器的偏差和均方差得到的。

2）基于分割稳定性的带宽选择方法。该方法与图像分解过程的稳定相互关联。 3）人机交互方法。该方法主要是通过人机交互接口根据人工判读来确定带宽矩阵。

4）基于局部信息的最优带宽选择方法。该方法一般处理效果较好，但计算量相对较大。

3.3.3.2 特征空间分析

根据Mean Shift算法过程，我们一般选取一些较容易计算且具有统计信息的特征量。在典型的Mean Shift图像分割算法中，特征空间由坐标特征和颜色特征组成。这两个特征量是实际运用中最常用到得两个图像特征。一般情况下，我们还可以选取纹理特征、梯度特征、边界特征等等。

3.3.3.3 收敛性分析

Mean Shift迭代过程是图像分割中的关键环节，该环节直接决定了算法的效率。在典型的Mean Shift图像分割算法中，根据定理3.1，我们能直接判定该算法是收敛的。

3.3.3.4 计算复杂度分析

根据典型的Mean Shift图像分割算法的特殊性，我们需要通过多次迭代来获得应有的计算精度。假设N为图像中像素点个数，k是算法平均迭代次数，则典型

第 18 页

国防科学技术大学研究生院硕士学位论文

的Mean Shift图像分割算法的总计算复杂度为O(kN2)。

3.4 一种改进的Mean Shift图像分割算法

对一个大数据图像来说，根据上节典型的Mean Shift图像分割算法的分析，设计一个快速Mean Shift算法是非常重要的。为了提高Mean Shift图像分割算法的效率和鲁棒性，我们通过以下改进来开展工作。首先，本文提出一种快速区域合并算法；然后，本文将证据（D-S）理论和基于区域的核密度估计方法进行了有效结合并用于Mean Shift图像分割方法的设计；最后，本文再次通过快速区域合并算法来消除孤立小区域。

3.4.1 基于D-S理论的核密度估计

为了权衡高斯核的计算复杂性和Epanechinov核的边界不连续性，本文采用了一个二次核进行核密度计算，其剖面函数如下：

⎧12

⎪(1−x)0≤x<1

kD(x)=⎨2 (3.22)

⎪x≥1⎩0

该剖面函数的负导数为：

⎧1−x0≤x<1gD(x)=⎨ (3.23)

0x≥1⎩

在进行特征空间融合前，本文假设特征空间的所有特征间都是相互的，对于图像中某点x处某两个特征量所对应的特征剖面函数分别为g1(x)和g2(x)，则根据D-S理论融合后的特征剖面函数为：

g1(x)g2(x)⎧

g1(x)g2(x)≠0⎪

g12(x)=⎨g1(x)+g2(x)-g1(x)g2(x) (3.24)

⎪0g1(x)g2(x)=0⎩

通过公式(3.24)组合的图像特征一般更适合于人眼视觉模型，是特征空间优化的一个可行方案。

3.4.2 基于区域的Mean Shift过程

假设图像数据空间的区域数为m，图像数据{xij|i=1,2,...,n,j=1,2,...,m}被划分为连通区域集{R1,R2,...,Rq}，且各区域大小分别为nk，区域中心分别为

第 19 页

国防科学技术大学研究生院硕士学位论文

1ck=n则我们可以通过基于区域的核密度估计来近似图像数据在特征空∑xij∈Rkxij，k间上的密度，其公式如下：

fˆh,K,R(x)≈

ck,dnh

d

∑

i=1

q

x−ci

nik(

h

2

)

(3.25)

又根据公式(3.11)，我们可以推出Mean Shift迭代过程为：

x-ck

ncg()∑k=1hd+2kk

h

mR(x)=-x (3.26) 2

qx-ck1

∑k=1hd+2nkg(h)

q

1

2

通过这种方式计算得到的mR(x)为基于区域的Mean Shift矢量。

3.4.3 快速区域合并算法设计

为了得到快速的区域分割，本文采用了一种线性扫描的算法来获得若干连续区域。下面，我们首先定义下相似点。

定义3.2（相似点） 假设x1,x2为图像数据空间中的两个点，Lx1,Lx2是其

Luv颜色空间的L通道值，如果这两点满足：

1）x1,x2是相邻的；

2）Lx1−Lx214623578 图 3.3 图像相邻区域数据结构图

如图3.3所示，阴影的格子代表当前数据点x0，格子1到4中的数据点分别表示为x1, x2, x3, x4，假设Gp(·)是返回类的编号的函数，则快速区域合并算法的描述如下：

第一步：依次选择图像数据空间上的每个点作为当前数据点x0；

第 20 页

国防科学技术大学研究生院硕士学位论文

第二步：判断x2与x0的相似性，如果相似，则Gp(x0) = Gp(x2)，把当前数据点移向下一个；否则进行第三步处理；

第三步：判断x3与x0的相似性，如果相似，则Gp(x0) = Gp(x3)，再根据x1，x4与x0的相似性来判断是否需要合并区域，最后把当前数据点移到下一个并返回第二步；否则进行第四步处理；

第四步：判断x4与x0的相似性，如果相似，则Gp(x0) = Gp(x4)，把当前数据点移向下一个并返回第二步；否则进行第五步处理；

第五步：判断x1与x0的相似性，如果相似，则Gp(x0) = Gp(x1)，把当前数据点移向下一个并返回第二步；否则，创建一个新的分类并把该数据点分到该类中去。

第六步：根据类的编号，将图像数据空间中的点进行标记并分类。

一般，通过以上区域合并算法得到的图像区域存在较多的小区域。为了获得更好的区域合并的效果，本文又根据这种快速区域合并算法设计了小区域消除算法，假设数据个数小于M的为小区域，则其算法过程如下：

第一步：计算所有区域的平均特征数据，并把区域数小于M的进行标记； 第二步：对于每个小区域，寻找其相邻的最相似区域，并予以合并； 第三步：合并所有相似区域并重新对分类区域进行编号。 3.4.4 改进的Mean Shift图像分割算法

为了提高Mean Shift图像分割的效率，本文通过D-S理论进行特征空间优化，并通过快速区域合并算法来进行基于区域的Mean Shift图像分割算法设计，其具体步骤如下：

第一步：图像滤波。在这步中，对与当前像素点相邻且相似的像素点进行求均值并将该均值赋予当前像素点；

第二步：区域合并。在这步中，运用快速区域合并算法进行区域合并并设定相对较小的区域门限；

第三步：求Mean Shift迭代收敛点。在这步中，根据公式(3.24)和(3.26)，计算各区域的收敛点；

第四步：区域分类。在这步中，根据各区域的收敛点特征对图像区域进行分类； 第五步：小区域消除。在这步中，通过再次快速区域合并算法并设定相对较大的区域门限。

在以上算法中，图像滤波的作用是为了平滑非边缘区域进而达到突出边缘的效果。在Mean Shift迭代收敛过程中，通过以区域来替代像素点的方法使得特征空间数据大大缩减了，因此，该算法的效果和计算复杂度较典型算法均有所提高。

第 21 页

国防科学技术大学研究生院硕士学位论文

3.4.5算法分析

本文提出的一种改进的Mean Shift图像分割算法是一种鲁棒性较强的算法，该算法在同一图像数据中参数相同的情况下得到的分割结果是相同的。下面主要从核带宽选择、特征空间分析、收敛性分析以及计算复杂度分析四方面来研究该算法。

3.4.5.1 核带宽选择

核带宽的选择与图像的统计信息有关，一般在各种图像分割过程中核带宽的作用不是一致的，因此较难选择。本文采用了半自动的核带宽选择方法，即根据

图像的统计信息给出参考带宽，然后由人工判读并根据图像分割的效果进行微调。

3.4.5.2 特征空间分析

在改进的Mean Shift图像分割算法中，为了与典型的图像分割的效果进行比较，本文还采用了坐标特征和颜色特征来作为图像特征空间数据。本文根据各个特征的不同作用，采用了各特征的归一化处理，并结合D-S理论进行了特征空间优化。

3.4.5.3 收敛性分析

本文在3.2节中已经给出了Mean Shift算法过程收敛性的证明。现在只需证明在用D-S理论进行特征融合后的Mean Shift过程仍是收敛的。根据前面的证明，这里仅需证在用D-S理论进行特征融合后的核函数K 仍具有凸的剖面函数。

定理 3.2 假设核K具有形如公式(3.22)的剖面函数，核G 为K的导数核；又假设核K具有一个凸的剖面函数k(x)，数据点 x由特征x1和x2组成。令g0(x1,x2) 为g(x1) 和g(x2) 进行D-S融合后的组合特征，则与g0(x1,x2) 对应的核K的剖面函数k0(x1,x2) 为凸函数。

证明过程如下: 如果x1,x2∈[0,1)且k0(x1,x2) 的二阶导数存在，根据公式

(3.24)可得：

g0(x)=

1−x1−x2+x1x2>0

1−x1x2

∂k0(x)∂k0(x)

==g0(x1,x2)>0.∂x∂x1∂x2

对上式再进行求导，可得：

第 22 页

国防科学技术大学研究生院硕士学位论文

∂k0(x1,x2)∂g0(x1,x2)

= 2

∂x∂x1∂x2

故可得：

1−x1−x2+x1x2

∂k0(x1,x2)1−x1x2

=2

∂x∂x1∂x2

2

⎛1−x2⎞∂⎜⎟

−xx112⎠=−⎝

∂x2

2(1−x1)(1−x2)=>0.3

(1−x1x2)

∂

当x1∈(−∞,0)∪[1,+∞) 或 x2∈(−∞,0)∪[1,+∞)时，根据二次核的剖面函数定

2

义可求得g0(x)=0。又假设当k0(x)的二阶导数不存在时，均有∇k0(x)=0，则可2

得到对于所有的x均有∇k0(x)=0。由此可以得出结论∇k0(x)在定义域内非负，

2

所以k0(x)为凸函数。

3.4.5.4 计算复杂度分析

计算复杂度是衡量一个算法优劣的重要指标。基于Mean Shift的图像分割算法的计算复杂度不但与图像大小有关，而且与图像的内容有关。为了更好的计算这里假设 N 为图像数据总本文提出的改进的Mean Shift图像分割算法的复杂度，

数，m为第一次区域合并后的区域数，M为区域大小的最小门限值，则该算法的计算复杂度可由四部分组成：①图像滤波的计算复杂度为O(N)；②快速区域合并算法的计算复杂度为O(N)；③Mean Shift迭代收敛过程的计算复杂度为O(m2)；④小区域消除的计算复杂度为O(mM2)。假设M 远远小于m，则总的计算复杂度为：

222

T(n,m)=O(N+N+mM+m)=O(N+m) (3.27)

由此可见，当N足够大时，本文所提算法相对于图像大小是渐近线性的。

3.5 Mean Shift图像分割实验与分析

基于Mean Shift的图像分割在实际中应用广泛，现在用到Mean Shift的系统有很多，本文选取Comaniciu和Meer[8]设计的EDISON系统来做实验效果比较和

第 23 页

国防科学技术大学研究生院硕士学位论文

性能对比。在实验前，本文先把所有Mean Shift过程的颜色特征空间L通道值设定为6，区域合并过程中区域的最小像素个数设定为20。进行实验的电脑配置为

Inter(R) Pentium(R) D CPU 2.80GHz。

(a)

(b)

(c)

图 3.4 桂林

(d)

(a)

(b)

(c)

图 3.5 Italy_Mountain

(d)

(a)

(b)

(c)

(d)

图 3.6 Mexico_Sunset

(a)

(b)

(c)

(d)

图 3.7 漓江

第 24 页

国防科学技术大学研究生院硕士学位论文

(a)

(b)

(c)

(d)

图 3.8 树林

(a)

(b)

(c)

(d)

图 3.9 Water_Bird

图3.4~图3.9中，图(a) 表示初始图像，图(b)表示EDISON系统的分割结果，图(c) 表示典型的Mean Shift图像分割算法的分割结果，图(d) 为改进算法的分割结果。

上面各图的具体分割信息如下：

表 3.1 Mean Shift图像分割信息表

图像名称 桂林 Italy

Mountain Mexico Sunset 漓江 树林 Water Bird

图像大小

时间(b)

时间(c)

时间(d)

区域数(b)1044 768 1341 405 1339 4252

区域数(c) 区域数(d)970 733 1282 385 1288 4319

417 453 581 328 350 698

772×571 13.82s 48.84s 5.75s 68×576 23.65s 93.67s 7.42s 768×576 28.67s 87.s 6.11s 696×0 12.36s 50.60s 4.47s 768×576 19.14s 78.34s 7.92s 768×576

22.34s

49.81s

9.73s

根据表3.1，可以得到以上各图的算法的时间对比如下：

1009080706050403020100

1

2

3

4

5

6

Time(b)Time(c)Time(d)

图 3.10 各种Mean Shift图像分割算法时间对比图

第 25 页

国防科学技术大学研究生院硕士学位论文

根据表3.1和图3.10，我们可以得出结论：改进的Mean Shift图像分割算法的时间消耗大概是典型算法的15% ，是EDISON系统的40%。另外，本文算法的分割结果均为连通的区域集并且有效地将大面积区域细分和很好地剔除小区域。

现在我们来分析下上面实验的图像分割质量。在图3.4~图3.9中，典型的Mean

Shift图像分割效果与EDISON系统的分割效果差不多。对照原始图像，我们可以发现本文分割效果较EDISON系统的分割效果有以下几点优势：一是本文算法在对边界模糊区域进行分割时分割得相对比较具体如图3.3、图3.4和图3.7；二是

EDISON系统在实现图像分割时比本文分割算法更容易出现分割遗漏，如图3.5和图3.8；三是本文算法在处理小区域问题上一般更能够接近人的视觉分割并能较好的对一些相对过细的区域进行合并，如图3.9。

3.6 本章小结

本章主要研究了Mean Shift算法的基本原理，着重研究了Mean Shift的迭代过程和收敛性以及特征空间的结构。通过Mean Shift结构分析，本章提出了一种快速区域合并算法并将其应用于改进的Mean Shift图像分割算法。在改进的Mean

Shift图像分割算法中，本章首先利用图像上下文信息对图像进行了区域合并以此来对输入数据进行了压缩；然后将D-S理论引入到核密度计算来实现特征空间中所有特征量的优化组合；最后对这种改进的Mean Shift图像分割算法的性能进行了比较研究。

第 26 页

国防科学技术大学研究生院硕士学位论文

第四章 基于图论的图像分割方法研究

4.1 图论相关知识

图论是一新的数学分支，也是一门很有实用价值的学科，其应用领域非常广泛。近年来，图论发展极为迅速。下面介绍下图的一些基本概念。

定义4 .1（图） 图（Graph）是由顶点集V和边集合E⊆V×V组成的二元组，记作G=(V,E)。如果边是有序的顶点对，则图G称为有向图（Directed graph），否则称为无向图（Undirected graph）。

定义4.2（权值图） 对于图G=(V,E)，如果建立映射f:E→R,即图中的每一条边都被指定一个实数,或者说被赋予一个权值，那么G称为权值图（Weighted

graph），用G=(V,E,W)表示，W=[wij]n×n是权值矩阵，对于(i,j)∈E,wij就是边

(i,j)对应的权值，n=V表示V的顶点个数。

定义4.3（顶点的度） 对于权值图G=(V,E,W)，假设节点i∈V，节点i的度（Degree）定义为di=

j∈V(i,j)∈E

∑

wij。

定义4.4（体积） 对于权值图G=(V,E,W)，点集A⊆V的体积（Volumn）定义为Vol(A)=

∑d

i∈A

i

，其中di是节点i的度。

定义4.5（割值） 对于权值图G=(V,E,W)，假设点集A∈V和B∈V满足

A∪B=V,A∩B=φ，则A，B之间的割值（Cut）定义为Cut(A,B)=

i∈A,j∈B(i,j)∈E

∑

wij。

定义4.6（图的Laplacian矩阵） 对于无向权值图G=(V,E,W)，假设没有自环（Self-loop）(即边的两端是同一个顶点)，则它Laplacian矩阵（Laplacian Matrix）

Δ

L定义为L=D−W，其中D=diag(d1,d2,...,dn)，di是节点i的度。

定义4.7（图的Fiedler值和Fiedler向量） 无向权值图G=(V,E,W)的Laplacian矩阵的第二个最小特征值称为Fiedler值（FiedlerValue），与之对应的特征向量称为Fiedler向量（FiedlerVector）。

图的Laplacian矩阵是图论中一个重要概念，它是实对称、半正定阵，它的行和和列和都为0，最小特征值为0，对应的最小特征向量是1向量。图的Fiedler值和Fiedler向量在基于图的谱分析占据重要位置，其中图割方法中的经典算法

Normalized Cuts[3]就是通过计算图的Fiedler值和Fiedler向量来完成图像分割的。

第 27 页

国防科学技术大学研究生院硕士学位论文

4.2 基本图割方法

在众多的图像分割方法中．基于图（Graph-based）的分割方法显示出强大的优势，它可以有效地结合图像灰度、纹理和色彩等各种信息达到满意的分割效果，此外图论中诸多成熟而完美的经典算法又为这一类图像分割算法提供了有力的计算工具，因此基于图的分割算法近年来受到广泛关注。

表 4.1 几种常见的基于图割值的分割方法比较

名称 谱分割(Spectral Partitioning) 等周分割(Isoperimetric Partitioning) 文献 [21]优化准则 没有明确的优化准则 目标函数 最终转化的问题 特征值问题，其解需要离散化 线性方程组求解问题，其解需要离散化 图的割值等价树的构造问题 广义特征值问题，其解需要离散化 minx⊥rx'Lx，r为全1向量，约x'xx'Lx，d=[di]n×1约束x'd条件为：束条件为：xi∈{−1,+1} [22]Cut(A,A)，约束条minAVol(A)1件为Vol(A)≤Vol(V)2minCut(A,A) Aminx最小割值(Min Cut) 归一化割值(Normalized Cut) [25]10国防科学技术大学研究生院硕士学位论文

作原理是把图像视为一个无向的权值图，图的顶点对应图像的像素或者区域，边的权值则反应了两个像素或者区域之间的相似程度。定义一个采用图像某种割值来表示的目标函数，通过求解目标函数的极值实现分割。各种分割方法的目标函数不同，求解手段也多种多样，使得基于图割值的分割框架下的内容丰富多彩。表4.1列出了几种经典的基于图割值的图像分割方法。其中最小割值（Min Cut）是提出较早的优化准则，对于某些图像可以取得较好的分割效果，然而该准则有分割出孤立点或者小区域的倾向。这是因为基础割值Cut(A,A)会随着A与A之间连接边数增加而增大。此后提出的各个准则都针对这一缺点做了改进，从不同角度对割值做了平均，包括对A的体积取平均（等周分割、归一化割值），对A的势取平均(平均割值)等。

这些经典的割值分割方法通常转化成三类问题来求解：一类仍是图论中的经典问题，例如割值等价树，最小完全匹配问题等，这些问题的求解通常借助于图论中成熟的算法，通常时间复杂度较高。在这类问题的求解过程中保持了标号向量x的离散属性，求解的结果直接可以作为分割的结果。第二类是矩阵的特征值问题，大的稀疏矩阵特征值问题在矩阵理论中也有许多成熟的理论和算法。求解特征值的过程是在连续域内进行。求得的向量x的元素都是实数，还要通过某种方式把x离散成二值向量。这类方法同求解第一类问题相比时间复杂度有所降低。第三类是新近提出的用求解线性方程组的方法来解决最小割值的问题，同求解特征值问题一样，也是先在连续域内求解然后在进行离散化，尽管时间复杂度与特征值问题同阶，但实验结果表明运行时间比求解特征值问题有明显降低[22]。

4.3 基于Normalized Cuts的图像分割

基于Normalized Cuts的图像分割是基于图割值的图像分割方法中的最重要的方法之一。相对于最小割值方法，该方法通过归一化割值来解决割值随着数据的增加而增加这一问题的。

4.3.1 Normalized Cuts方法介绍

任意特征空间的点集均可表示为一个带权值的无向图G=(V,E,W)，图上的节点即为特征空间的点，每两个节点之间由一条边连接起来，边的权值为wij，wij表示节点i和节点j的相似程度。如果将图G=(V,E,W)进行划分，假设分为m个互不相交的子集V1,V2,...,Vm，划分后保证每个子集Vi内的相似程度较高，不同的集合

Vi和Vj之间的相似程度较低，那么就必须确定一个最佳划分的准则。

第 29 页

国防科学技术大学研究生院硕士学位论文

考虑图的二值划分，假定将图G=(V,E,W)划分为两个不相交的子集A和B，则A∪B=V,A∩B=φ,即B=A。如果不断地移去连接这两个子集的边，那么两个子集的不相似程度可描述为移去的所有边的权值之和。可描述如下：

Cut(A,B)=

i∈A,j∈B

(i,j)∈E

∑

wij (4.1)

一个图的最佳二值划分就是Cut(A,B)为最小值时的划分。这种最小划分的准则比较适合划分图中的孤立点，即孤立点的划分值较小。很显然，公式(4.1)定义的划分值是随着连接两个划分的边的数量的增加而增大的。假设边的权值与两点间的距离成反比，那么孤立点的划分值将很小。Normalized Cuts方法克服了这种情况，提出一种规格化的划分准则，其形式如下：

11

Ncut(A,A)=Cut(A,A)(+)

Vol(A)Vol(A)

公式(4.2)可写为：

(4.2)

假设x为n=V维图像特征矢量，如果节点i在A中，则xi=1；否则xi=−1。则

Ncut(A,A)=

令k=

∑

xi>0,xj<0

i

−wijxixj

∑x>0di

+

∑

xi<0,xj>0

i

−wijxixj

(4.3)

∑x<0di

∑∑xi>0

di

di

， b=

k

，y=(1+x)−b(1−x)，则根据文献[3]并结合1−k

定义4.6，可得：

yTLy

minxNcut(x)=minyT

yDy

T

(4.4)

上式约束条件为yi∈{1,−b}且yD1=0。公式(4.4)符合Reyleigh商的形式，因此Normalized Cuts的规则就转化为求解广义特征值：

Ly=λDy (4.5)

上式的一个解就是问题的一个实值解，显然，最小特征值肯定是0，而与此对应的特征向量为全1矢量，即表示不分割。因此，图的Fiedler值和Fiedler向量就是最优解。将公式(4.5)标准化的一个简单方法就是令z

-121212=Dy，由此可得：

DLDz=λz (4.6)

由此，Normalized Cuts的最优准则就转化成了广义特征值求解的问题。

第 30 页

国防科学技术大学研究生院硕士学位论文

4.3.2 Normalized Cuts的权值矩阵

在 Normalized Cuts方法中，一般还需考虑权值函数。对于一个权值图

G=(V,E,W)，权值wij∈W必须反映两节点间的相似性，以图像颜色特征值和坐标

特征值为例，一般可以定义权值函数为：

−

F(i)−F(j)

22

wij=e

σI2

⎧−X(i)−X(j)2

2⎪eσX*⎨⎪0⎩

2

ifX(i)−X(j)

其他

2

(4.7)

其中，F(i),X(i)分别表示图像的颜色信息和坐标信息。公式(4.7)所表示的权值越大，两节点越相似。

4.3.3 基于Normalized Cuts的图像分割

本文所描述的基于Normalized Cuts的图像分割算法是一种重复二分法。具体算法描述如下：

第一步：构建权值图G=(V,E,W)并计算D=diag(d1,d2,...,dn)，其中di表示节点i的度；

第二步：解线性方程组(D−W)x=λDx的Fiedler值和Fiedler向量； 第三步：根据Fiedler向量将图G分成两个子图；

第四步：判断各子图的最小Ncut值是否小于门限NT，若是则继续二分。 第五步：重复执行上一步直至所有子图的最小Ncut值都大于NT。

该方法所分割的区域个数由Ncut值的门限值NT直接决定。这里的分割只是将图像或局部图像不断二分，有时为了简化计算量，可直接用K分（K大于等于3）代替二分或结合最小的若干个图的特征向量来进行分割。

4.3.4 算法分析

在基于Normalized Cuts的图像分割中，其主要计算量在于解线性方程组

(D−W)x=λDx的Fiedler值和Fiedler向量。本文结合Lanczos压缩迭代法和

QR分解进行特征值的求解。令n=V为图像中像素点的个数，m为Lanczos压缩迭代法的迭代次数，则Lanczos算法的计算复杂度为O(nm)，QR分解的计算复杂度为O(m2)。一般权值矩阵为稀疏矩阵，所以Lanczos方法的压缩比可以很高，即

n远远大于m。因此，基于Normalized Cuts的图像分割的总的计算复杂度近似为O(nm)。

第 31 页

国防科学技术大学研究生院硕士学位论文

基于Normalized Cuts的图像分割树中一个重要参数是调节分割粒度的参数——门限值NT，主要在于能够影响图像分割的尺度，即图像分割结果的区域数。在计算图像割值Ncut时，本文采用公式(4.2)的计算方法来获得区域的一致性标准并用于门限判断。

4.4 基于Normalized Cuts的图像分割树

通过树结构的图像表达被认为是一种重要的基于区域的图像分析方法。在图像分析中，为了便于从图像中提取一般观察者感兴趣的对象，有必要通过图像分割来获得一系列不同尺度的区域分割结果，并从中选择合适尺度的分割结果来进行对象提取。一般来说，分割尺度的粗细与分割结果中的区域数目直接相关，分割区域数目越多，则表示分割尺度越细。下面就从图像分割树的概念、建立和应用来描述基于Normalized Cuts的图像分割树。

4.4.1 图像分割树概念

图像分割树就是通过树结构的形式来描述图像在不同尺度的区域分割结果以及这些区域间的相互关系。一般最常用的图像分割树是二叉划分树[40]（Binary

partition tree，BPT）。本文前面介绍的基于Normalized Cuts的图像分割算法本身就提供了一个BPT的实现方案。BPT为图像的多尺度分割提供了一种有效的表示工具，它可以系统地记录基于图像的过分割结果进行的区域合并过程。在BPT中，每个叶子结点表示一个初始分割区域；每个非叶子结点则表示在区域合并过程中新生成的区域，它的2个子结点表示被合并的2个邻接区域；根结点则表示整个图像区域。

传统的BPT算法由图像树节点表达、合并相似树节点以及构建二叉树三部分组成。这是一个自底向上的算法，在图像树节点表达过程中，一般是把图像的一个细分割（比如基于分水岭算法的图像分割）的每个区域看做一个节点并建立节点间的相似性度量准则；在合并相似树节点过程中，遍历图像各个小区域，并将它们各自与最相似的区域进行合并；在构建二叉树过程中，首先根据合并相似树节点的方法进行树节点递归合并，然后对一些意义不大的树节点进行剔除，最后把所有区域表示成二叉树中的一个节点。由于BPT算法中的合并过程总是把两个最相似的节点进行合并，所以该算法不需要人工交互。

本文在Normalized Cuts的图像分割算法基础上提出了一种自顶向下的图像分割树的构建方法。基于Normalized Cuts的分割采用了递归地一分为二的方法把图像分成多个区域，而这种分割方式会出现尽管每次分割目标函数都是最优但多次

第 32 页

国防科学技术大学研究生院硕士学位论文

分割以后的目标函数总和并非最优的问题。另外，基于Normalized Cuts的分割有一个调节分割粒度的参数——门限值NT。在分割的不同阶段可能需要不同的参数才可以达到好的分割效果，在实现中却很难自适应地调节该参数。

针对以上两问题，本文提出了在过分割的图像区域上进行区域合并的处理方法。该方法首先根据快速区域合并算法获得一系列小区域；其次在这些小区域集上设置较小的门限值并应用Normalized Cuts算法不断进行二分；然后根据二分结果再进行树枝上的部分小区域合并；最后构建图像的BPT。

4.4.2 图像分割树的建立

在构建图像分割树之前，先确定两区域间相似性度量函数。一般初始区域划分的结果是通过区域邻接图（Region adjacency graph，RAG）来表示的。RAG的每个结点表示每个分割区域，而连接两个结点的边的权重则表示两个邻接区域的相似性度量。在定义相似性度量时，本文综合考虑了邻接区域的颜色差异、连接紧密程度以及区域面积的影响，即颜色相似而且连接紧密（有较高的共用边界比例）的邻接区域通常可以合并成一个更有意义的区域；面积较小的区域应该更早地合并成面积较大的有意义区域。因此，两区域Vi和Vj间的相似性度量函数可表示如下：

RAG(i,j)=μ (4.8)

(1+aici−cm+ajcj−cm)

其中ci和cj分别表示Vi和Vj的颜色均值，cm表示将这2个邻接区域合并成一个区域后的颜色均值，ai和aj分别表示Vi和Vj的面积，μ为Vi和Vj的共用边界比例，其定义如下：

μ=

pij

min(pi,pj)

(4.9)

其中pi和pj分别表示Vi和Vj的周长，pij表示Vi和Vj共有的边界长度。RAG(i,j)越大，区域i和区域j越相似。

根据以上相似性度量函数并将其用于计算区域间的权值函数，则基于

Normalized Cuts的图像分割树的算法描述如下：

第一步：根据本文所设计的快速区域合并算法将图像分割成若干小区域

V1,V2,...,Vm，并对小区域的总体特征和区域编号进行标记；

第二步：把区域集{V1,V2,...,Vm}的每个小区域看作顶点，用边Eij(i,j=1,2,...,m)连接表示区域集中两区域间；wij(i,j=1,2,...,m)表示两区域间的相似性，构建区域

第 33 页

国防科学技术大学研究生院硕士学位论文

权值图G=(V,E,W)；

第三步：运用Normalized Cuts算法对权值图G进行不断二分并设置相对偏小的分割门限值以产生分割二叉树T；

第四步：检测二叉树T的各树枝节点之间的相似性，并将相似性度量值满足一定门限的树枝节点进行合并且将合并结果作用于上层树结构；

第五步：遍历所有树节点并构建图像二叉分割树。 4.4.3 图像分割树的算法分析

上一小节阐述了本文图像分割树算法的步骤，该算法采用了BPT的树结构。一般的BPT算法在进行部分小树枝消除的过程中会由于不同根节点的树枝间的合并而产生环的结构。本文在解决这个问题时考虑到图像区域的一致性将不同根节点的枝节点间的合并结果进行区域的类判别并把判别结果更新到整个树结构中。本文在构建图像分割树的过程中，其主要计算复杂度在于用Normalized Cuts进行图像分割，所以构建分割树的算法复杂度近似为O(nm)，n为快速区域合并后的图像区域数，m为Normalized Cuts分割后的图像区域数。

在建立基于Normalized图像分割树的过程中，分割门限值NT是调节分割树的叶节点个数的重要参数，较小的NT值会得到较多分类树节点个数，从而对图像的表达也就越详尽，但计算复杂度也相应增加，所以选择合理的分割门限值NT对图像分割树的建立起着重要作用。一般在综合考虑分割树的信息完整性和计算复杂度基础上可选取NT值的范围为0.0001~0. 1。

4.5 图割实验及分析

根据前面的方法研究，以下实验主要对以下两方面内容进行了实验验证：一是不同Ncut门限值的分割效果验证，二是基于Normalized Cuts的图像分割树与传统的BPT的对比实验。进行实验的电脑配置为Inter(R) Pentium(R) D CPU 2.80GHz。

4.5.1 基于Normalized Cuts算法的不同门限值的图像分割

不同的分割门限对基于Normalized Cuts的图像分割方法的影响主要在于分割结果的区域数，下面通过具体的实验来验证不同分割值对图像分割结果的影响。

第 34 页

国防科学技术大学研究生院硕士学位论文

(a)

(b)

(c)

(d)

图 4.1 不同Ncut门限值的图像分割。(a)为大小256×256的原图，(b)门限值为0. 01的分割结

果，(c)门限值为0.005的分割结果，(d)门限值为0.001的分割结果

图4.1的分割结果信息如表4.2所示：

表 4.2 不同门限值的Normalized Cuts分割的比较 门限值NT 区域数 时间

图(b)

图(c)

图(d)

0.01 0.005 0.001 29 72 110 6.8s 10.67s 17.s 根据图4.1和表4.2，我们可以得出：分割门限越小，则分割结果中的区域数越多，图像信息的表达越完整，计算时间也越长。

第 35 页

国防防科学技术大大学研究生院院硕士学位论论文 4.5.2 基于于Normalizzed Cuts的图像分割树的树与传统的的BPT的对对比研究 图像分割树树是对图像像信息的一种种简单有效效的表达方式，本文在在进行图像像分割树的的对比实验方方面，着重重研究了图像像分割树的的建立和不同方法的图图像分割树树结构对比比。 4.5.2.1图像像分割树的的建立过程9817462(a) (b) 35 (c) 图 4.2 图像分割割树的建立过过程。(a)表示示原图，(b)表示区域分割表割结果，(c)表表示区域分割割树 在上图中，根据本文文的特征提取取方法，背背景区域3与区域1之之间的相似似性最小，而区域1、2、4、5之间相似度之度为0，故图图割的过程程为首先划分分开区域1，然后依依次是4、2和5，从而而建立了如图(c)所示的的图像分割割树。 4.5.2.2 图像像分割树的的对比实验本文试验中中，BPT算法和基于算Normalizedd Cuts的算算法都是基于于区域的分分类算法，对待分割图图像的第一一步处理都是是将图像进进行区域合并并。 (a) (b) 图 4.3 图像像区域合并。(a)表示原图图，(b)表示区区域分割结果果 第 36 页国防科学技术大学研究生院硕士学位论文

在图4.3中，由于图像是渐变的，而本文所采用的区域合并算法是基于颜色相似的，所以其结果是呈条状的。基于BPT的图像分割树和基于Normalized Cuts 的图像分割树分别如下：

613141162021222312161952117113107(a)

(b) 图 4.4 图像分割树对比。(a)表示BPT的结果，(b)表示Normalized Cuts图像分割树

由上图可以显然看出BPT的图像分割树是自底向上的，而基于Normalized

Cuts的图像分割树是自顶向下的。考察图4.3的各个分割树根节点的两子节点，图(a)中这两节点的区域集合所代表的二类划分不能够突出中间的渐变圆，而图(b)中两节点的区域集合所代表的二类划分较明显突出了图像中间的渐变圆。

4.6 本章小结

本章的研究内容包括两个方面：一是研究了基于图论的图像分割方法及对比；二是研究了基于Normalized Cuts的图像分割及图像分割树的建立。在研究基于图论的图像分割方法时，本章就图像分割方法的相关准则、问题描述和解决方案进行了对比分类。在研究如何构建基于Normalized Cuts的图像分割树时，本章还给出了相应的相似性度量函数，并与传统的BPT构建方法进行了实验对比。最后实验验证了本文所提基于Normalized Cuts的图像分割算法是一种性能较好的分割算法。

结合第三章的研究内容来看，本章研究的基于Normalized Cuts的图像分割算法是一种自顶而下的分割方法，该方法能够较好的表达图像分割的层次关系；而

Mean Shift图像分割方法是一种自底而上的分割方法，该方法是从图像的像素级描述来进行聚类得到区域级的描述，较Normalized Cuts简单快速但缺乏层次描述。

第 37 页

国防科学技术大学研究生院硕士学位论文

第五章 图像分割应用研究

5.1 图像分割的应用简述

随着图像分割技术研究的深入，其应用日趋广泛。凡属需要对图像目标进行提取、测量的工作都离不开图像分割。目前，图像分割已在交通、医学、遥感、通信、军事和工业自动化等诸多领域得到广泛应用。

在智能交通领域，图像分割已广泛应用于车牌的定位和生产。在医学领域，图像分割已应用于脑图像、心脏图像、胸部图像和细胞图像等的分割。在遥感领域，利用遥感数据进行海洋监测、海事救援、海洋污染监控等应用时，都需要通过图像分割来对海岸线进行提取。目前，随着图像分割在医学、遥感、电子商务、专利检索和建筑设计等领域得到了广泛应用，图像分割的方法也在不断更新并融入越来越多的新理论和新方法。

5.2 基于Mean Shift的飞机型号检测

对飞机目标的类型进行识别是现代自动化防空武器系统指挥决策的重要环节。在现代高技术条件下的防空作战中，快速准确地判断飞机的类型，及时准确地判断出敌方目标对我方的威胁程度，并根据我方战术意图和武器系统防空作战能力，进行科学的目标分配和火力分配，是提高防空作战制胜能力的关键，也是当代军事领域研究热点。为了快速有效的识别图像中的飞机目标，本文在已检测到飞机目标的基础上，提出了基于Mean Shift的飞机型号检测算法。

5.2.1 飞机型号检测的研究背景和方法

在高技术条件下的局部战争中，飞机发挥着十分重要的作用。高效快速地识别飞机目标有利于作战指挥员实时把握敌方动态，进行决策分析并迅速做出反应，赢得战争的胜利。通过遥感卫星或侦察飞机等运载工具采用光学摄像可以获取机场的高分辨率图像，对这些图像进行分析能够提取出机场中的飞机目标。

飞机型号检测一般分为三个部分：一是建立飞机样本库；二是飞机图像的特征描述；三是飞机型号匹配识别。建立飞机样本库是根据需要识别的飞机种类并采集标准的飞机样本图来建立的；飞机图像的特征描述是识别飞机特征的关键，对飞机特征的描述是否精确和有效直接影响最终的识别效果；飞机型号匹配识别是根据匹配算法或模型进行的筛选过程，一般的飞机型号匹配识别流程如下：

第 38 页

国防防科学技术大大学研究生院院硕士学位论论文 图像数据 预处理图像像特征提提取飞机型型号识别别结果结输输出图 5.1 飞机型号识别飞别流程图 在上述流程程中，图像像特征提取决决定着飞机机型号识别的方法。如如果图像特特征为检测测区域的统计计特征，例例如图像特征征矩、灰度度、纹理等，则飞机型型号识别是是一种基于于图像特征数数值的匹配配识别方法。如果图像像特征为归一化的图像像二值数据据，则飞机机型号识别是是基于模板板匹配的识别别方法。 5.2.2 基于于Mean Shhift的飞机型型号检测系系统的实现本文针对飞飞机图像目标的特征，将飞机型型号检测系统统分为基于于Mean Shiift的图像像去噪与二值值化、飞机机方向检测和和标准化、飞机目标特征提取以以及飞机类类型匹配识识别四个步骤骤来实现。 5.2.2.1 基于于Mean Shhift的图像像去噪与二值值化 飞机目标图图像中一般般都存在较强强的噪声，本文在图像去噪和二二值化方面面，引入了了Mean Shifft来实现高高效的二值化化，其具体体算法如下： 第第一步：图图像低通滤波波。通过滤滤波来削弱图图像中比较较尖锐的噪噪声的影响；； 第第二步：用用Mean Shihift对图像进进行图像聚聚类分割；第第三步：检检测图像边缘缘并进行描描边； 第第四步：统统计图像中各各区域的面面积和灰度信信息，并根根据统计结果果把所提取取目标以外外的区域当成成背景，所所提目标当作作前景； 第第五步：前前景空洞剔除除。在这步步中，本文采采用形态学学中的腐蚀和和膨胀操作作来实现目目标中的空洞洞剔除。 (a) (b) 二值值化方法的分分割图 (cc) 图 5..2 卫星图像中飞机目标区区域的二值化化。(a)为原图图，(b)为自适适应阈值的分分割图，(c)为本文为图5.2分别别显示了基于于Mean Shift的二值化化算法和自适应阈值法法对卫星图图像的第 39 页国防防科学技术大大学研究生院院硕士学位论论文 二值值分割效果。。从分割结结果看，自适适应阈值的的分割结果容易把背景景区域划到到目标区域域当中去且较较难分辨出出前景和背景景，而本文文提出的算法则能够更更好的提取取出飞机目标。 5.2.2.2 飞机机方向检测测和标准化一般在飞机机目标图中中，飞机的方方向一般是是不固定的。为了更加加精确地识识别飞机类类型，一般需需要把图像像中飞机目标标规范到同同一方向上去。本文采采用了基于于目标对称称性的方向校校正。 实际中的飞飞机为了在在飞行过程中能够平衡衡机身，其结构都是在在飞行方向向上呈两边边对称的。即即使飞机目目标受噪声所所影响或其其机翼长短不一，在飞飞机目标图图像中其结结构还是对称称的。因此此，本文根据据这种对称称性来统一飞飞机目标的的方向。 假设用Φ(R)来表示飞飞机目标R的对称性，，如果θaxis是飞机R的的轴线方向向，则Φ(R)满足： θaxis=argmaxΦ(Rθ) 0<θ<π (5.1) 其中中，Rθ是R旋转角度θ后的飞机机目标。在这这个方程里里，相差π的的两个目标标方向被认认为相同方向向。为了得得到Φ(R)，本文首先计计算R在水水平方向上的的投影： HR(j)=0≤idZM(Q,F)=5.2.2.4 飞机类型匹配识别

0dH(T,M)=H(T)

H(M) (5.11)

其中，H(⋅)表示目标机长，如果dH(T,M)>1，则dH(T,M)=1d(T,M)。

H

dW(T,M)=W(T)

W(M)

(5.12)

其中，W(⋅)表示目标翼展，如果dW(T,M)>1，则dW(T,M)=1d(T,M)。

W

dS(T,M)=S(T)

S(M)

(5.13)

其中，S(⋅)表示目标三角面积，如果dS(T,M)>1，则dS(T,M)=1d(T,M)。

S

飞机目标与数据库中飞机模型的总的相似度函数为：

dT=wd1H+wd2W+wd3S+wd4ZM

(5.14)

其中，w1、w2、w3和w4为权值系数。根据以上相似度函数，我们只需寻找飞机模型库中与飞机目标最相似的飞机模型类型，就可以判定待识别飞机目标为该类型。

5.2.3 实验与分析

在实验之前，本文针对各种飞机类型进行了统计和模板设计，本文数据库中

F22，F111， SU30，SU33， B52， Tu22等等。dH、dW、dS和dZM飞机类型包括：

的权值系数w1、w2、w3和w4分别设定为0.2、0.2、0.3和0.3。为了更好的测试基于Mean Shift的飞机型号检测系统的性能，本文选取了两幅亮度不同的背景和两架不同型号的飞机作为检测对象。进行实验的电脑配置为Inter(R) Pentium(R) D

CPU 2.80GHz。

第 43 页

国防科学技术大学研究生院硕士学位论文

(a) (b)

图 5.5 飞机目标图像一。图(a)为原图，图(b)为检测区域局部的放大图

对图5.5进行飞机类型检测，结果中相似度大于0.5的机型输出如下表：

表 5.1 飞机目标图像一的检测结果

机型 相似度 检测结果

F15 0.8650

F111 0.9305

F22 0.9112 F111

苏30 苏33

0.5846 0.19

(a) (b)

图 5.6 飞机目标图像二。图(a)为原图，图(b)为检测区域局部的放大图

对图5.6进行飞机类型检测，结果中相似度大于0.5的机型输出如下表：

表 5.2 飞机目标图像二的检测结果

机型 相似度 检测结果

Tu95 0.9175

C130 0.6234

B52 0.9466 B52

B1 0.7417

B2 0.6387

第 44 页

国防科学技术大学研究生院硕士学位论文

以上实验结果显示，基于Mean Shift的飞机型号检测系统在噪声较少的卫星图像中能够较准确地检测出飞机的类型。在实验中，特征系数w1、w2、w3和w4是根据多次实验统计出的较为合理的预定值，飞机类型检测性能这些系数之间的比例的改变而改变。另外，由于该系统中用到的四个特征并不能表达图像的所有信息，所以该系统的应用还存在一些局限性，尤其在信噪比较弱的卫星图像中，其检测性能和结果还有待提高。

5.3 基于Normalized Cuts的海陆分割

利用遥感图像进行海上目标检测、监视的关键技术是实现海陆分离，从而为目标检测、监视减少不必要的处理工作。海陆分割工作的目的是将海洋遥感图像中的陆地区域进行遮蔽或移除，使得检测器仅仅作用于海洋区域而忽略陆地区域。本文根据SAR图像的海陆特征，并结合基于Normalized Cuts的分割算法来进行海陆分割。

5.3.1 海陆分割的研究背景和方法

由于遥感图像具有监控范围广、时效快等优点，近年来在海洋监测，海事救援，污染监控等方面得到越来越广泛的应用，特别是海上目标检测、监视。通过对遥感数据，包括光学图像和SAR图像的处理得到达成上述任务所需的信息得到广泛的关注和深入的研究。由于遥感图像中海面相对于陆地较为简单，而所关心的区域也是海面。提高海域图像处理的效率和准确性以降低虚警、漏检的关键是屏蔽陆地区域。

海陆分割是图像分割的一种，目前已有很多的海陆分割方法，从分割策略上讲，可以分为基于阈值分割的算法、基于区域生长的方法和基于边界检测的方法。

基于阈值分割的算法海陆分割的主要算法，其一般步骤是选取一个（或多个）阈值分割图像，对分割后的二值化的图像进行形态滤波，区分内陆孤立区域和海面孤立区域，再分别连通和去除孤立区域，得到海岸线。但是这类方法存在如下几个问题：一是阈值的选取带有较大的随意性和经验性，不容易实现自动的阈值选取，阈值选取的好坏直接影响分割效果，已有的自动阈值选取算法是基于图像灰度直方图双峰分布或近似双峰分布，有局限性。虽然也出现了各种自适应的阈值选取方法，但是这些算法的针对性比较强，要求图像的灰度级对比较为明显。通常情况下海域图像较暗陆地区域较亮，这是阈值分割的一个前提基础，但是当图像没有经过辐射校正，图像灰度级较暗或者陆地与海面灰度级相差不大时利用

第 45 页

国防科学技术大学研究生院硕士学位论文

阈值分割并不能很好地将陆地与海域分开，阈值的自动选取也得不到准确的结果。即使不存在上述问题，由于陆地上存在散射特性较暗的区域，对应的在图像上也会存在亮度较暗的区域，这样也会导致误分割。二是对于利用阈值分割，只考虑了灰度信息，而没有考虑梯度信息，通常图像的陆地区域灰度层次较为丰富，这是陆地与海域的一个显著区别，对于海陆分割是一个可利用的资源。三是外海孤立区域和内陆孤立区域的判定需要通过计算区域距离和最小路径来判断，无疑增加了许多计算量，对于数据量较大的遥感图像这是影响算法性能的一个重要因素。

区域生长算法是基于这样的假设：海陆区域的像素分别具有某种不同的特性，比如灰度、纹理。该算法的基本思想是：先从海区域中找一个种子点，然后按一定规则，将周围的像素与之合并，将合并的像素作为新的种子像素继续向外扩展，直到找不到满足条件的像素为止则分割结束。

边界检测方法是人们研究的较多的一种方法，它试图通过检测海陆的边缘来解决图像分割问题。由于海陆边缘上像素灰度值的变化比较剧烈，一般利用图像一阶导数或二阶导数的过零点信息来提供判断边缘点的基本依据，边缘检测的缺点在于边缘检测和边缘的连接相互，边缘检测的错误无法在边缘连接的过程中得到更正。

虽然海陆分割方法很多，但至今还没有找到对所有图像都很有效的分割算法。要使海陆分割算法效果好，就必须充分利用SAR图像的成像特点，本文将卫星图像的显著性特征导入到Normalized Cuts算法当中并通过Normalized Cuts来获得海陆的二值分割。

5.3.2 基于Normalized Cuts海陆分割系统的实现

基于Normalized Cuts海陆分割系统主要由图像去噪、特征提取、海陆分割以及小区域消除四部分组成。

5.3.2.1 图像去噪

在遥感图像的特征提取与目标识别方面，国内外学者已做了很多工作，早期工作主要集中在噪声抑制等预处理方面。遥感图像一般包括SAR遥感图像和光学遥感图像。本文海陆分割对象为光学遥感图像。在光学遥感图像中，由于传感器噪声和配准噪声等使得图像变得模糊不清。另外，在光学遥感图像中，云层的干扰对遥感图像的影响很大。因此，在对光学遥感图像进行自动检测之前必须进行去噪处理。一般光学遥感图像的去噪方法是通过抑制噪声来提高信噪比。本文采用同态滤波器来对一些海面薄云进行剔除，而对大片高密度云层，由于云层里的目标无法识别而将其判断为陆地。同态滤波把频率过滤作为图像处理的核心，其

第 46 页

国防科学技术大学研究生院硕士学位论文

基本方法是取图像值的对数对图像数据进行求频域操作，然后在频域上进行滤波，最后通过指数运算将图像数据变换到时域。

本文针对光学遥感图像来进行去噪，所采用图像去噪方法分三个步骤：首先，对图像进行中值滤波；然后，利用同态滤波器对图像进行噪声抑制；最后，对图像相似区域进行平滑，在平滑过程中对每一个像素点的相邻且相似的九个像素点进行求均值并将均值赋予该像素点。

5.3.2.2 特征提取

利用遥感图像的识别特征来分析和提取目标是遥感图像中目标检测和识别的重要方法，而在遥感图像的特征提取中应用纹理特征和线特征等特征的研究较多。本文在特征提取方面利用了图像的灰度特征、梯度特征和纹理特征。

图像的灰度特征就是图像的颜色值信息，本文根据以图像统计均值C为参考，以分段函数的形式给出了图像的灰度特征，其形式如下：

⎧1

⎪⎪⎪⎪

dC(x,y)=⎨

⎪(f(x,y)−80)/40⎪(f(x,y)+20−C)/40⎪⎪⎩0其中，f(x,y)为图像的灰度值。

C≥120,f(x,y)≥120或40≤C<120,f(x,y)≥C+20或C<40,f(x,y)≥C+10

C≥120,80≤f(x,y)<120

40≤C<120,C−20≤f(x,y)(5.15)

在图像梯度特征提取方面，本文分别对图像水平方向和垂直方向求梯度，并将两个梯度的均值作为图像的梯度特征，其计算公式为：

dG(x,y)=

其中，G(x,y)为梯度均值。

1232123432G(x,y)

(5.17)

maxG(x,y)

34234123214332 图 5.7 邻近图像区域数据权值结构

在图像纹理特征提取方面，本文设计了一种针对SAR图像的简单纹理特征提

第 47 页

国防科学技术大学研究生院硕士学位论文

取方法。其提取算法如下：

第一步：对于图像中的每个点，取其邻近的24个像素点（如图5.7所示）； 第二步，在上述24个点中，与当前像素点的灰度差绝对值小于20的点的权值系数为图5.7中相应位置的数值，其余点的权值系数为0；

第三步，计算每个像素点邻域数据的权值和，并将其作为该点的纹理特征值，记为T(x,y)；

第四步，归一化纹理特征值，即TN(x,y)=T(x,y)/60。 5.3.2.3 海陆分割

本文在设计图像海陆分割算法时，综合考虑了图像灰度、梯度和纹理三个特征。海面图像一般起伏不大而陆地图像一般有较大起伏。另外，由于海陆交界处的纹理起伏也较明显，本文可先把这些区域都判为陆地，然后进行两次图像腐蚀，即可得到较为准确地海陆分割图。海陆分割算法具体如下：

第一步：计算图像灰度、梯度和纹理三个特征的值； 第二步：计算图像中每个像素的总特征值，其公式如下：

FT=w1dC(x,y)+w2TN(x,y)+w3dG(x,y)

其中，dG(x,y)为梯度特征，w1、w2和w3是权值系数。

第三步：根据图像像素的总特征进行快速区域合并；

(5.16)

第四步：计算各区域的平均灰度、梯度和纹理并得到区域的总特征值； 第五步：根据各区域的总体特征来计算区域间的相似性并设定Normalized Cuts的门限值NTF，然后根据NTF将图像进行二分；

第四步：对二值图像进行两次腐蚀操作。 5.3.2.4 小区域消除

在海陆二值图中，一些海上目标或噪声都可能会被划入陆地区域。本文在滤除这些小区域的过程中分三步进行：

第一步：通过形态学滤波消除部分小区域；

第二步：根据一般海岛的大小确定小区域的门限ThR； 第三步：以面积为参数根据ThR进行小区域剔除。 5.3.3 实验与分析

0.3实验之前，先对实验参数进行设置：特征权值系数w1、w2和w3分别为0.3、和0.4，总的特征门限ThF为0.4，小区域门限ThR为50。本文选取不同噪声环境背

第 48 页

国防防科学技术大大学研究生院院硕士学位论论文 景的的遥感图像作作为分割对对象。实验电电脑配置为Inter(R) PenIntium(R) DD CPU 2.80GGHz。 (a) (b) (c) 图 5.8 海陆分割图一。。(a)为原图，，(b)阈值法的的分割结果(c)(本文方法的的分割结果 在图5.8中，图中(b)和(c)均得到较好的分割割效果，但图(b)存在很很多小区域域且海洋里里的一些舰船船目标均被被判为陆地。。 第 49 页国防防科学技术大大学研究生院院硕士学位论论文 (a) (b) (c) 图 5.9 海陆分割图二。。(a)为原图，，(b)阈值法的的分割结果(c)(本文方法的的分割结果 在图5.9中，图中(b)和图和(c)均能能消除陆地上上云层的干干扰，但在处处理云层的的阴影和陆陆地上较暗区区域时，图图(b)的方法更更容易将这这些区域判断断为海域。 (a) (b) 第 50 页国防防科学技术大大学研究生院院硕士学位论论文 (c) 图 5.10 海陆分割图三海三。(a)为原图，(b)阈值法法的分割结果(c)本文方法的分割结果 在图5.10中，图(b)对海面薄云对云不能有效去去除海域薄薄云的影响，图(c)在处处理海域中中比较亮的和和纹理比较较复杂的云层层时均将其其判为陆地，对比较平平缓的云层层能够有效效去除。 (a) (b) 第 51 页国防科学技术大学研究生院硕士学位论文

(c)

图 5.11 海陆分割图四。(a)为原图，(b)阈值法的分割结果(c)本文方法的分割结果

在图5.11中，图(b)对港口区域的边缘不能够有效判别且会由于噪声较多而出现较大面积的判断错误，图(c)在处理港口区域的海陆分割时，基本能够分割出海陆框架，但边缘地区的判断还不够精确。

通过以上实验，我们可以看出，本文所设计的基于 Normalized Cuts海陆分割系统在处理光学遥感图像中各类区域时均能达到较好的分割效果。另外，由于遥感图像种类繁多，在处理不同类型遥感图像时，还需结合各种传感器的特性来进行特征提取并根据具体情况进行特征组合来实现海陆图的有效分割。

5.4 本章小节

本章研究了图像分割的相关应用并通过结合Mean Shift图像分割方法和

Normalized Cuts图像分割方法来对图像分割进行了具体应用研究。在基于Mean Shift的飞机型号检测中，根据飞机目标图像的特点和飞机识别的需要合理设计了飞机模板的特征描述并取得了较好的检测效果。在基于Normalized Cuts的海陆分割中，充分利用光学遥感图像的特点进行了合理的特征描述并将其纳入到

Normalized Cuts算法的权值函数中去，实验结果显示了较好的海陆分割效果。

第 52 页

国防科学技术大学研究生院硕士学位论文

总结与展望

6.1 工作总结

本文主要研究了基于Mean Shift的图像分割和基于图论的图像分割，现将工作总结如下：

第二章阐述了图像分割的概念并把图像分割方法分为结构性图像分割方法和非结构性图像分割方法两种。在结构性图像分割方法中介绍了阈值分割法、边缘检测法、区域生长和特征空间聚类法；在非结构性图像分割方法中介绍了基于偏微分方程的图像分割方法、基于神经网络的图像分割方法和基于图论的图像分割方法。

第三章研究了Mean Shift图像分割算法。本文对Mean Shift算法的特征空间和收敛过程进行了详细分析，并针对实际应用提出一种快速Mean Shift算法的整改方案。

第四章研究了基于图论的图像分割算法。本文结合矩阵论的知识对比分析了各种基于图割值的图像分割算法并重点研究了基于Normalized Cuts图像分割。本文分析了多尺度图像分割的必要性并提出了基于Normalized Cuts的图像分割树的实现方案。

第五章把Mean Shift图像分割方法和基于Normalized Cuts的图像分割方法应用于简单的系统当中，并通过实例分析验证了这两种方法的可行性。

总体而言，本文研究和讨论的是图像分割中最基础的技术，而图像分割作为一种应用性很强的技术只有与具体的分割相结合才能有旺盛的生命力。本文虽然结合了一些实际的应用背景讨论了图像分割的应用，但其研究深度和广度还有待进一步扩展。

6.2 主要创新

本文创新性工作包括：

1、提出了一种改进的Mean Shift图像分割算法。该算法引入D-S理论来进行特征空间优化，并采取了一种快速区域合并方法来提高Mean Shift图像分割算法的效率。

2、提出了一种基于Normalized Cuts的图像分割树构建方法。该算法在快速区域合并的基础上采用一种区域间的相似度度量函数来构建权值图，并以此提出一种二叉划分树的建立方法。

第 53 页

国防科学技术大学研究生院硕士学位论文

3、提出了一种基于Mean Shift的飞机型号识别算法。该算法提出了一种运用Mean Shift基本原理和目标的统计信息来对卫星图像中飞机目标进行提取的方法，然后根据目标提取结果进行二值化，最后与数据库中各模板进行匹配识别；

4、提出了一种基于Normalized Cuts的海陆分割算法。该算法利用了卫星图像中的海陆信息并将海陆图的所有特征信息融合于Normalized Cuts的权值函数中，从而实现了较好的海陆分割效果。

6.3 前景展望

本文研究和讨论的是静态图像的分割方法，是图像分割中最基础的技术。这些基础技术只有与新的理论工具或者实际的应用环境结合起来才会有旺盛的生命力。本文认为：图像分割未来的发展方向应该是基于特定应用背景的图像分割和基于特定理论工具的图像分割，此外对于图像分割评价方法的研究也是具有潜力的发展方向。一般不存在适用于所有图像并且在各种性能上都占据优势的分割方法，只有结合了具体的应用背景才能正确选择出合适的分割算法，对算法的改进也应该结合具体问题、具体分割任务有针对性地进行。例如，如果图像分割的任务是为了完成视频序列中的目标跟踪，那么对分割的实时性就提出了较高的要求；如果分割的任务是为了检测医学图像中的异常部位，那么就要求分割很准确，而且宁可虚报而不能漏报。另一方面，不同的应用环境提供了不同的先验知识，这些先验知识可以指导我们设计和选择合适的模型，所以只有针对具体的问题和任务进行研究和改进才能有好的发展前景。

图像分割是一种应用型技术，与各种理论工具的结合给图像分割技术注入了新的活力。迄今为止，已经有多种理论工具和方法结合到图像分割技术中，例如数学形态学、偏微分方程、图论、人工神经网络、模糊理论和逻辑、小波分析、信息论和遗传算法等。目前还不断有新的方法和技术涌现，并且被应用到图像分割中来，例如人工免疫方法、核技术等。与这些新的理论、方法和工具的结合使用是未来图像分割技术的一个发展方向。

图像分割技术发展至今，主要的研究还是集中在图像分割技术本身，而对于分割技术评价方法的研究相比之下就少得多了。事实上，分割结果的评价对许多图像技术都是很重要的，因为分割评价通过对分割算法性能的研究以达到优化分割的目的，不仅可以提高现有算法的性能。而且对研究新的分割技术也具有指导意义。更高层次地，对评价方法本身的评价也是很重要的，它可以指导如何选取合适的评价方法来更好地评价分割算法，不过目前这方面的研究还几乎是空白。随着图像分割技术的发展，图像分割的评价也越来越受到重视，最近又有很多新

第 页

国防科学技术大学研究生院硕士学位论文

的评价方法问世，对评价方法的研究必将促进图像分割技术向更高的层次发展。

图像分割作为图像分析中的重要环节，是进一步进行目标表达、描述、跟踪、识别和分类的基础。随着图像分析及其相关学科理论和技术的不断进步，图像分割技术也必将得到长足的发展。

第 55 页

国防科学技术大学研究生院硕士学位论文

致谢

回首攻读硕士的日子，感触良多，虽然并没有取得让人满意的成绩，却也学到了很多，进步了很多。在此谨向曾经给予我无私帮助与鼓励的老师和同学们表达最诚挚的谢意。

首先衷心感谢张权老师。他以渊博的知识激励我进步，以高尚的个人魅力鼓舞我奋进，以宽广的胸襟给予我宽容和理解。然后特别感谢教授，他一丝不苟的治学态度和对科学事业孜孜不倦的追求为我树立了榜样，同时他还以身作则，在实践中教导我如何做人与做学问，他对我的帮助和指导我永远铭记在心。还有非常感谢朱长仁老师，他在各方面都能为人师表，在指导我学习的一段时间里认真负责，让我受益良多。另外感谢实验室的刘方、王程、张鹏和钟平老师，感谢他们对我的无私帮助和殷切关怀。最后感谢王威、张志、程环环、、叶鹏、郭军、孙皓、汪汉云、陈扬钛、任、井沛良，无论是学习上的讨论还是球场上的切磋都令人难忘。这个大家共同营造的和谐的实验室氛围让我在紧张的学习之余倍感快乐和温馨。

第 56 页

国防科学技术大学研究生院硕士学位论文

参考文献

[1] 章毓晋，图像分割[M]．科学出版社，北京东黄城根北街16号100717，2001． [2] Kenneth R.Castleman，数字图像处理[M]．电子工业出版社，北京市海淀区万寿

路173信箱100036，2006．

[3] Jianbo Shi and Jitendra Malik, Normalized Cuts and Image Segmentation[J]. IEEE

Trans. PAMI, 2000.

[4] Fukunaga K, Hostetler L D, The estimation of the gradient of a density function with

applications in pattern recognition[J]. IEEE Trans. Information Theory ,1975.

[5] VISTA NICTA and RSISE ANU1st Semester, Image Segmentation, Normalized

Cuts[J]. Computer Vision and Image Understanding:Theories and Research, 2007. [6] Cheng Y Z, Mean shift,mode seeking,and clustering[J]. IEEE Trans. PAMI, 1995. [7] Hui Zhang, Jason E. Fritts and Sally A. Goldman, Image segmentation evaluation: A

survey of unsupervised methods[J]. Computer Vision and Image Understanding, 2007.

[8] Comaniciu D, Meer P, Mean shift: A robust approach toward feature space

analysis[J]. IEEE Trans. PAMI, 2002, 24(5): 603-619.

[9] Daniel Freedman and Pavel Kisilev, Fast Mean Shift: Technical report[C].

Hewlett-Packard Laboratories, 2009. 图像分析[M]．科学出版社，北京东黄城根北街16号100717，2005． [10] 孙即祥，

[11] 俞璐，灰度图像分割技术研究：学位论文．东南大学信号与信息处理专业，

2007．

[12] S. Paris and F. Durand. A topological approach to hierarchical segmentation using

mean shift[C]. CVPR, 2007.

[13] Kai Zhang, Ming Tang and James T.Kwok, Applying Neighborhood Consistency

for Fast Clustering and Kernel Density Estimation[C], CVPR, 2005.

[14] Y.Y. Wong, P.C. Yuen, and C.S. Tong, Segmented Snake for Contour Detection[J].

Pattern Recognition, 1998, 31(11):1669-1679.

[15] D. Comaniciu and V. Ramesh, Mean shift and optimal prediction for efficient

object tracking[C]. In Proceedings of the International Conference on Image Processing, 2000. [16] Georgescu B,ShimshoniⅠand Meer P, Mean shift based clustering in high dimensions: A texture classification example[C]. ICCV, 2003.

[17] D. Barash and D. Comaniciu, A common framework for nonlinear diffusion,

adaptive smoothing, bilateral filtering and mean shift[J]. Image and Vision Computing, 2004, 22(1):73–81.

[18] D. Comaniciu, An Algorithm for Data-Driven Bandwidth Selection[J]. IEEE Trans.

第 57 页

国防科学技术大学研究生院硕士学位论文

PAMI, 2003

[19] H. Guo, P. Guo and H. Lu, A Fast Mean Shift Procedure with New Iteration

Strategy and Re-sampling[C]. In IEEE International Conference on Systems, Man and Cybernetics, 2006.

[20] Liao, S.X., and Pawlak, M.: ‘On the accuracy of Zernike moments for image

analysis’, IEEE Trans. PAMI, 1998, 20,(12), pp. 1358–13.

[21] Pothen A, Simon H D, Liu K F P, Partitioning sparse matrices with eigenvectors of

graphs[J]. SIAM Journal on Matrix Analysis Applications, 1990, 11(3)；430~452. [22] Grady L, Schwartz, Isoperimetric graph partitioning for image segmentation[J].

IEEE Trans. PAMI, 2006, 28(3)：469—475．

[23] Cheng H D，Jiang X H，Sun Y，et a1．Color image segmentation:advances and

prospects[J]．Pattern Recognition，2001，34：2259-2281．

[24] Xiaotong Yuan, Stan Z. Li, Half Quadratic Analysis for Mean Shift: with

Extension to A Sequential Data Mode-Seeking Method[J]. IEEE Transactions on Image Processing, 2007. [25] Wu Z, Leahy R, An optimal graph theoretic approach to data clustering：Theory and its applicaton to image segmentation[J]. IEEE Trans. on PAMI, 1993, 15(11):1101-1113.

[26] Zhang Yu, Shi Zhong-ke, and Wang Run-quan, Fast Mean Shift Based Traffic

Image Filtering Algorithm[J]. IEEE Transactions on Image Processing, 2009.

[27] Maurizio Filipponea, Francesco Camastra, Francesco Masulli and Stefano Rovetta,

A survey of kernel and spectral methods for clustering[J]. Pattern Recognition, 2007.

[28] Miguel A. Carreira-Perpinan, Gaussian Mean-Shift Is an EM Algorithm[J], IEEE

Trans, PAMI, 2007.

[29] Sarkar S, Soundararajan P, Supervised learning of large perceptual organization:

Graph spectral partitioning and learning automata[J]. IEEE Trans. on PAMI, 2000, 22(5):504-525.

[30] Wang S, Siskind J M, Image segmentation with ratio cut[J], IEEE Trans. on PAMI,

2003, 25(6):675-690.

[31] Wang S, Siskind J M, Image segmentation with minimum mean cut[C].

Proceedings of IEEE International Conference on Computer vision, 2001, V01.1:517-524. 田捷，诸葛婴等．图像分割方法综述[J]．模式识别与人工智能，1999，[32] 罗希平，

12(3)：300～312．

[33] Fu K S, MeiJ K, A survey On image segmentation[J]. Pattern Recognition, 1981,

13: 3-16．

[34] Haralick R M, Shapiro L G, Image segmentation techniques[J]. Computer

第 58 页

国防科学技术大学研究生院硕士学位论文

vision,graphic and image processing, 1985,29: 100-132.

[35] Pal N R，Pal S K, A review On image segmentation techniques[J]. Pattern Recognition, 1993, 26(9); 1277-1294.

[36] Zhiming Qian, Changren Zhu and Runsheng Wang, An Improved Fast Mean Shift

Algorithm for Segmentation[C]. International Conference on Computer Analysis and System Modulating, 2010.

[37] Kass M, Witkin A, Terzopoulos D, Snakes: active contour models[J]. International

Journal of Computer Vision, 1988,1: 321-332.

[38] Sussman M, Smemka P, Osher S, A level set approach for computing solutions to

incompressible two-phase flow[J]. Journal of Computing Physics, 1994, 114: 146-159.

[39] Changjiang Yang, Ramani Duraiswami, Nail A. Gumerov and Larry Davis,

Improved Fast Gauss Transform and Efficient Kernel Density Estimation[C]. ICCV, 2003.

[40] Salembier P.Garrido L, Binary partition tree as an efficient representation for

image processing[J]. Segmentation,and Information Retrieval, 2000.

[41] J.-W. Hsieh, J.-M. Chen, C.-H. Chuang and K.-C. Fan, Aircraft type recognition in

satellite images, Image Signal Process, 2005. [42] 许新征，丁世飞等，图像分割的新理论和新方法[J]．电子学报，2010． [43] 汤凌，郑肇葆，虞欣，一种基于人工免疫的图像分割算法[J]．武汉大学学报(信

息科学版)，2007 (1)：67-70．

[44] 丛琳，沙字恒，焦李成，基于免疫克隆选择算法的图像分割[J]．武汉大学学

报(信息科学版)，2006，28(7)：1169-1173．

[45] Martinez A M, Mittrapiyanurnk P, Kak A C, On combining graph-parition with

nonparametric clustering for image segmentation[J]. Computer Vision and Image Understanding, 2004,95:72-85. [46] Merigot A．Revisting image splittlnglA]．in：Proceedings of IEEE Internationat

Conference on Computer Vision[C]. 2001,Vol.1:517-524.

[47] Wu X．Adaptive Split-and-Merge segmentation based On piecewise least-square

approxirnation[J]. IEEE Transactions On Pattern Analysis and Machine Intelligence, 1993, 15(8): 808-815.

[48] 肖亮，吴慧中，韦志辉等，图像分割中分段光滑mumford-shah模型的水平集

算法[J]．计算机研究与发展，2004，41：129_135．

[49] 林开颜，吴军辉，徐立鸿，彩色图像分割方法综述[J]．中国图象图形学报，

2005，10(1)：1-8．

王蕾，图像分割的阌值法综述[J]．系统工程与电子技术，2002，24(6)：[50] 韩恩奇，

92-94．

第 59 页

国防科学技术大学研究生院硕士学位论文

作者在学期间发表的学术论文

[1]Zhiming Qian, Changren Zhu, Runsheng Wang, An Improved Fast Mean Shift Algorithm for Segmentation, International Conference on Computer Application and System Modeling, 2010.

第 60 页