基于区域合并的纹理图像分割—MSRM算法的MATLAB实现

基于区域合并的纹理图像分

题目：割一MSRM算法的MATLAB实现

摘要

图像分割是图像分析及计算机视觉系统中的重要环节，是图像处理研究中的一个基 本难题。图像分割是山图像处理到图像分析的关键步骤，只有在图像分割的基础上才能 对u标进行特征提取、参数测量和识别，使得更高层的图像分析和理解成为可能，图像 分割质量的好坏直接影响后续图像处理的效果。因此，可以说图像分割是图像处理中最 为重要的环节。

基于区域的图像分割方法，将图像按内容划分成许多区域。虽然存在过分割，但是 可以通过研究改进算法减少过分割或选择有效的后处理算法得到有用的结果。例如，在 Mean Shift和Watershed这两种图像分割算法中，一方面可以研究各种减少过分割的改 进算法。另一方面，也可以釆用有效的预处理，去除噪音，使图像适宜于Watershed或 Mean Shift算法分割。

MSRM是基于最大相似度的区域合并算法，该算法简单有效，不需要设定区域合并的 阈值,且对单U标和多U标图像都能正确分割。本设计在提取了图像的颜色特征和纹理特 征之后，计算相邻区域的相似度，在人工交互信息的指导下，基于最大相似度准则逐步 对初始过分割区域进行合并，分离出图像中的目标和背景。

关键i司：MSRM：区域合并；交互式图像分割：算法；纹理图像

Abstract

Image segmentation is the important elements of image analysis and computer vision systems , and it is a fundamentalproblem in image processingo Image segmentation is a key step that from image processing to the image analysis o Only on the basis of image segmentation to object feature extraction, parameter measurement and recognition, which make it possible to analysis and understanding of the higher-level image, and the quality of image segmentation directly affects the effect ofsubsequent image processing. Therefore, we conclude that image segmentation is the most important part of image processing・

Region-based image segmentation method is divided into many regions according to the contents of the imageo Although there is over-segmentation, studing improved algorithm can reduce the over-segmentation or choosing an effective post-processing algorithms are useful results. For example, in both Mean Shiftt and Watershed image segmentation algorithm. One can study a variety of improved algorithm to reduce over-segmentation, On the other hand, effective pretreatment can also be used to remove noise, and make the image suitable for Mean Shiftt and Watershed segmentation algorithm.

MSRM is a algorithm which based on the maximum similarity of the region merging, the proposed algorithm is efficient and effective, it does not require a preset threshold and can successfully extract the single objective and multi-target image from complex scenes . In this design, calculate the similarity of adjacent regions afte the extration of image color features and texture features, under the guidance of interaction information ,a maximal similarity based region merging mechanism was proposed to gradually merged the initial over-segmentation of regions. Then separated the target and background from image・

Keywords： MSRM: Region merging; Interactive Image Segmentation; Algorithm;

Texture image

1绪论 ........................................................................ 1

1.1研究的背景和意义 ....................................................... 1 1.2 内容与组织结构 ......................................................... 2 2图像分割技术研究综述 ........................................................ 3

2. 1引言 .................................................................. 3 2.2图像分割的概念和分类 ................................................... 3 2.3基于阈值的图像分割 ..................................................... 4 2.4基于间断检测的图像分割 ................................................. 4 2.5基于区域的分割 ......................................................... 4

2.5.1基于区域生长的分割 ................................................ 5 2.5.1基于合并的分割 ................................................ 6 2. 5. 1基于聚类的分割 ................................ 错误!未定义书签。 2. 5. 1基于形态学的分割 .............................. 错误!未定义书签。 2. 6本章小结 .............................................................. 7 3基于最大相似度的交互式区域合并算法的研究 .................................... 8

3. 1引言 .................................................................. 8 3. 2区域表示和相似性度量 .................................................. 9 3.3目标和背景标记 ......................................................... 9 3.4基于最大相似度的区域合并机制 ........................................... 9 3.5区域合并算法 ......................................... 错误!未定义书签。 3.6收敛性分析 ........................................... 错误!未定义书签。 3. 7本章小结 .............................................................. 7 4图像分割系统设计及实验结果 ................................................. 15

4. 1引言 ................................................................. 15 4. 2 图像分割系统 ....................................................... 15 4. 3实验结果与分析 ....................................................... 15

4. 3. 1 实验结果 ........................................................ 15 4. 3. 2 鲁棒性分析 .................................................... 16 4. 3. 3 分割效率分析 .................................................. 19 4. 3.4

结论 .......................................................... 20

结束语 ....................................................................... 21 参考文献 ..................................................................... 22 致谢 ......................................................................... 24

1绪论

1.1研究的背景和意义

计算机视觉是通过计算机模拟人类视觉行为的一门学科，其任务为对输入的图像（序 列）数据自动进行分析和解释。根据数据的组织形式，计算机视觉可划分为四个层次。 最底层是原始的L1标或场景，通过信号处理和数字化，得到对应图像的数字化表示形 式；中间层则借助各种各样的算法，提取图像的各种特征，在各层之间建立联系；最后 顶层通过模式识别方法，进行图像理解。

视觉处理方法可分为两类：低级的图像处理方法和高层的图像理解方法。前者不需 要预先知道图像的内容，通常包括图像圧缩、图像恢复、图像分割、边界检测等方法， 为高层的图像理解提供支持。而后者是根据L1标的相关知识及一些实现方法，基于低级 阶段获取的图像特征来模拟人的视觉和做决策的过程，通常包括LI标识别、图像理解、 3D视觉和目标运动分析等。

随着信息时代的来临，越来越多的各种信息充斥着人们的生活，人们渴望利用计算 机来处理繁多的信息。而科学研究表明，人类获取的信息中有75%左右来自于自身的 视觉，即大部分信息为图像图形信息。图像信息相对于其他类型的信息来说，最大的优 势在于信息量大、直观、形象、易于理解等特点。因此，数字图像分割技术为越来越多 学者所重视，正逐渐成为网络信息时代一个新的研究热点【讥

图像分割创3】是图像分析及视觉系统中的重要环节，是图像处理研究中的一个基 本难题。图像分割是山图像处理到图像分析的关键步骤，只有在图像分割的基础上才能 对LI标进行特征提取、参数测量和识别，使得更高层的图像分析和理解成为可能，图像 分割质量的好坏直接影响后续图像处理的效果。因此，可以说图像分割是图像处理中最 为重要的环节。

纹理是图像的一个重要特征。以纹理特性为主导的图像称为纹理图像【出，纹理图像 是图像的重要组成部分，通常运用各种观测系统获得的图像大多是纹理型的，在航空航 天遥测领域中，各种航空、卫星遥感图像是对地面宏观大范圉的考察，这类图像大多是 纹理型的，通过对这些图像的分析可获得地质状况、土地利用、植被长势等一系列信息。 纹理分析在材料科学的微结构定量分析、海洋学研究及石油勘探中都有广泛的应用，因 此基于纹理的图像分割具有重要的理论意义和广阔的应用前景。

直到今天，纹理图像分割是图像分割中的一个经典难题。尽管人们在纹理图像分割 方面已取得了大量的研究成果，但山于纹理图像的复杂性和缺乏一个统一的图像分割理 论框架，LI前尚无提出通用的分割理论，现已提出的算法大都是针对具体问题。纹理分 割问题仍然是图像处理和机器视觉领域中一个非常艰巨的和富有挑战的课题。

综上所述，釆用自适应的方法将进一步推动纹理图像分割技术的发展，提高纹理图 像的分割质量和效率。本文选择基于区域合并的纹理图像分割算法一MSRM算法作为研 究课题，对于改进图像分割技术，丰富图像分割方案，提高数字图像分割系统的性能具 有一定的理论价值和现实意义。

1.2内容与组织结构

第一章介绍了数字图像分割技术起源、发展，给出了其描述性定义；指明了纹理图 像分割技术是图像处理和图像分析关键所在，是本文的研究重点；最后概述了本文的主 要内容及结构。

第二章对数字图像分割技术重要基础性概念及相关的研究进行了综述，分类介绍了 阈值分割、间断检测分割、区域分割等图像分割技术，重点介绍了与本文研究相关的区 域分割算法。

第三章首先描述了基于最大相似度的区域合并算法一MSRM算法的背景和山来，接 着进一步详细阐述该算法，并指明MSRM算法以Mean Shift算法的分割结果作为基础； 验证了图像分割算法的收敛性。

第四章根据提出的MSRM算法，设计出一个自适应图像分割系统，运用Matlab7.10 工具，通过实验和仿真验证的该解决方案具有自适应和高效的特点。

2图像分割技术研究综述

2.1引言

虽然图像分割技术是隶属于图像处理领域的一个分支学科，但是山于图像分割技术 涉及的学科领域比较广泛，更应该将其视为一个交叉性学科。因此学者们看待该问题的 硏究角度和出发点各不相同，也就给出了较多的模型和相关的概念。这一章，将按照图 像分割技术的技术特点和原理，对三种主要类型图像分割技术的相关概念和典型的解决 方案进行详细的评述。

2.2图像分割的概念和分类

图像分割是图像处理技术的经典难题之一，也是图像分析和模式识别等高级图像 处理操作的流程中的关键步骤，图像的分割结果直接决定了后期图像处理的效果和质 量。所谓图像分割是指将图像中具有特殊含义的区域分割开，且这些区域互相不重叠， 同时每个区域都满足特定的区域一致性条件。从工程实现的角度，图像分割乂可以定 义为将图像划分成互不相交(不重叠)区域的过程。从集合论的角度出发，文献山给出 了 一种较通用的图像分割描述性定义。

定义1令R表示整个待分割图像区域，从而可以将图像分割看作将R划分为n个满 足以下条件的子区域RI, R2,巴的过程：

⑴ g = R， 且R,是连通的；

/-I

(2) 对所有的i和j,且iHj,有RQR,=0； (3) 对于/ =

P(RJ = TRUE；

(4) 对于iHj,有P(R,UR,.) = FALSEo

其中，P(RJ是定义在区域R「内所有点上的逻辑谓词,0表示空集。

条件(1)说明分割必须是完全的(即每个像素必须属于一个子区域)，且子区域自身 必须是连通的；条件(2)说明各个分割区域之间相互不重叠；条件(3)说明同一个分割区 域中的像素具有相同的属性(如具有相同的灰度值)：条件(4)说明不同分割区域和

Rj对于谓词P是不同的。

由于图像分割技术应用广泛且与其他学科(如光学、统计学、生物学等)联系紧密, 所以

图像分割的解决方案和思路呈现出多样化的趋势，并激发了越来越多学者的研究兴 趣，使得对图像分割技术的研究在图像处理领域始终保持着热点地位。在大量关于图 像分割技术的科技文献中，己经提出了相当丰富的分割方法和系统的解决方案，尤其是 近20年来出现的图像分割方法，不仅包括对原有方法的继承和改进，还涌现出一些新思 路、新方法，如基于马尔科夫随机场模型的图像分割⑸⑹、小波分形的图像分割⑺、模 糊聚类创9】、基于人工神经网络的图像分割方法【口等。图像分割方法一般是基于局部像 素点的两个基本特性：不连续性和相似性。按照该特性可以将这些已有的图像分割方法 归为三类：基于阈值的分割方法、基于间断检测的分割方法、基于区域的分割方法。

此外，还有一些比较特殊的图像分割方法，比如混合儿种基本分割方法的复合图像 分割方案，引入待分割图像先验知识的智能图像分割方案，用于视频特征提取的时域图 像分割方案等等。接下来，本章将按照以上的分类方法对图像分割技术进行综述。山于 本文着重于基于区域合并的纹理图像分割，故将重点介绍基于区域合并的图像分割，以 便为下一步的硏究工作提供指导。

2.3基于阈值的图像分割

阈值图像分割乂称为门限图像分割，其原理简单、易于实现，是一类被广泛应用的 图像分割方法，其历史可以追溯到上个世纪60年代。早期的阈值分割方法，主要是围 绕灰度图像展开研究的，后来被部分学者推广到彩色图像分割技术中，如文献山】提出的 一种用于彩色图像分割的直方图阈值方法。近年来，更多的学者倾向于将阈值分割 方法与其他的图像分割方法结合起来使用。如文献M2】中运用模糊理论确定最优阈值，文 献21将神经网络方法与传统的阈值分割技术结合起来，获得最优阈值，解决了免疫组织 化学中的细胞分割问题，等等。

2.4基于间断检测的图像分割

大部分情况下，对于自然界中的图像而言，其U标与背景之间边界部分的色彩、灰 度都是不连续分布的，即边界两边像素的灰度级存在明显的跳变。这就是基于间断检测 的图像分割技术的前提假设，基于这种不连续性的假设所考察对象的不同，可将该类 分割技术分为三个主要类型：基于点的检测、基于线的检测、基于边缘的检测。

2.5基于区域的图像分割

无论是图像阈值分割方法还是间断检测分割方法，都没有考虑□标或背景内部像素 间的信息关联性，而这一特性在机器视觉中却是尤为重要的。基于区域的图像分割方法 正是从LI标和背景内部的像素间相似度角度出发，面向像素对图像进行分割的，具有前 两大类方法无法比拟的优势。文献a】对数字图像像素的概念及特性进行了全面的分析。 按照处理图像的

方向性，基于区域的分割算法可以分为区域生长和合并两种类型。 此外，还有一些对这两类分割方法的推广和改进，如形态学分割方法、聚类分割方法等。

2.5.1基于区域生长的分割

区域生长分割算法的基本思想：将图像中具有相似性质的像素整合在一起构成一个 区域。在生成每个区域的过程中都要设定一个用于生长的种子像素，根据不同类型的图 像给定生长准则，来判断种子周围的像素点是否与种子像素之间具有相似性，即是否可 生长。如果可生长，则把该像素加入到区域中，并置其为新的种子像素，进行迭代。

具体步骤如下：

(1) 对每个需要分割的区域找一个种子像素作为生长的起点。

(2) 将种子像素周围邻域中与种子像素具有相同或相似性质的像素合并到这一区域 中。 (3) 将这些新像素当作新的种子像素继续进行上面的过程，直到再没有满足条件的像 素被包括进来。

在实际应用区域生长法时需要解决三个问题： (1) 选择或确定一组能正确代表所需区域的种子像素。 (2) 确定在生长过程中能将相邻像素包括进来的准则。 (3) 制定让生长过程停止的条件或规则。

种子像素的选取常可借助具体问题的特点进行，利用迭代的方法从大到小逐步收缩 是一种典型的方法。生长准则的选取不仅依赖于具体问题本身，也和所用图像数据的种 类有关。一般生长过程在进行到再没有满足生长准则需要的像素时停止。

山于相似性通常是用统讣的方法确定的，所以基于区域生长的分割算法对噪声不敬 感。但是，区域生长分割算法的问题在于：种子像素点需要山操作人员按照分割需求来 设定，对于复杂图像的处理，区域生长分割算法的效率会大大降低；而且分割效果依赖 于种子点的选择及生长顺序。对此 文献问提出了一种通过计•算种子点附近邻域统计•信 息，自适应改变生长标准参数的算法。导致基于区域生长的分割算法效率较低的另一个 原因是算法的串行性。对此，文献【⑹研究并提出了并行性区域生长分割算法。

2.5.2基于合并的分割

合并算法的基本思想：对整个图像得到所有的分割区域，然后按照一定的 规则对这些区域进行合并。该方法的重点是指定、合并的准则，并考虑处理的精度。 通常的作法是用网格简单地对原图像进行操作，网格的多少取决于希望获得的分割 精度；通过比较各个区域的灰度值均值和方差等统讣量，来确定区域的一致 性。

整个合并的过程如下：

(1) 对谓词P，如果P(R,) = FALSE,就把区域出 成4个象限子区域； (2) 如果相邻区域匕和R*满足P(R』Rj = TRUE,则对这两个区域进行合并； (3) 如果无法进行或合并操作时，结束。

基于合并的分割算法同样是基于统计学方法的，所以对噪声也不敏感。但是区 域技术的固有缺点是可能会使边界被破坏，且算法在精度与时间复杂度上存在冲 突，需要找到一个均衡点，但这往往是很难的。

2.5.3基于聚类的分割

图像的分割问题可看成是像素分类问题，所以可以通过使用特征空间聚类算法实 现。特征空间聚类分割将图像的所有像素都一一映射在特征空间的每个点上，对特征空 间进行分割，最后再次通过映射关系将分割结果定位在原始图像上，从而实现了图像 LI标的分割。该过程不需要训练样本，是一种无监督、迭代式的统计分割过程。在基于 特征空间聚类的算法中，K-均值聚类\"1、模糊C-均值聚类(FCM)等算法是最常用的聚类 算法。

K-均值聚类算法先选取K个初始类均值，然后将每个像素归入均值离它最近的类， 并计算新的类均值，迭代执行前面的步骤直到新旧类均值之差小于某一阈值。

模糊聚类的思想Dimn首先提出，是对K-均值聚类算法的推广。其基本的思路为 将 由n个维数为P的样本组成的数据集X = {.V2，...,X”}WR\"XP分为c类,则模糊隶属度矩 阵U = {n*}eR” “表示，并满足以下条件：

(1)怂 w[O,l],V讥： ⑵工“em：

k (3) 0 v 工心 i

那么，模糊c -均值聚类就可以通过最小化关于隶属度矩阵u和聚类中心集合v的LI 标函数并繁复迭代来实现。但是，该方法没有考虑图像各个像素之间的空间儿何分布特 征，对噪声和不均匀灰度敬感。

2.5.4基于形态学的分割

近年来，数学形态学已发展为一种新型的数字图像处理方法和理论，在边缘检测和 图像分割中得到了广泛的研究和应用。它的基本思想是用具有一定形态的结构元素去量 度和提取

图像中的对应形状以达到对图像分析和识别的□的。利用膨胀、腐蚀、开启和 闭合四个基本运算进行推导和组合，可以产生各种形态学实用算法，其中结构元素的选 取很重要。腐蚀和膨胀对于灰度变化较明显的边缘作用很大，可用来构造基本的形态学 边缘检测算子（形态学梯度）【岡。

2.6本章小结

比较分析上述各种类型的图像分割技术，可以发现：

阈值图像分割技术是最简单的一类分割方案，其计算量小、易于实现，但是在对非 理想边缘以及复朵灰度分布图像的分割时不能得到有效的分割结果，其至会导致错误分 割。

基于间断检测的分割技术比较适用于对纹理图像的分割，但是需要根据不同的图像 设置不同的检测模板，且该类算法普遍对噪声敬感。尽管采用LoG, Wavelets等多尺 度方法对其进行改进，降低对噪声的敬感程度，但却导致系统的计算复杂度大大增加。 而且 山于边缘检测分割的结果是非闭合的，还需额外考虑多尺度分割结果的融合问题。

基于区域的分割方案，考虑到了图像像素之间的相似性和连通性，这正是前两类图 像分割方案所不具备的。所以，在图像信息向着高清晰度发展的趋势下，选MSRM分割 算法对图像进行分割处理是非常适合的。而且，MSRM算法的另一个重要特性就是易于 并行实现，这一特点也是非常复合现今对图像分割技术的实时性、高效性要求的。

3基于区域合并的纹理图像分割算法的研究

3.1引言

基于区域的图像分割方法，将图像按内容划分成许多区域。虽然存在过分割，但是 可以通过研究改进算法减少过分割或选择有效的后处理算法得到有用的结果。例如，在 Mean Shift\"】和Watershed^20'这两种图像分割算法中，一方面可以研究各种减少过分割的 改进算法。另一方面，也可以采用有效的预处理，去除噪音，使图像适宜于Watershed 或Mean Shift算法分割。

虽然有很多图像分割方法致力于解决图像分割问题，它们在一些特定的对象中能取 得较好的结果。但是，总的来说，图像，特别是彩色图像包含着复杂的纹理和颜色特征， 使得全自动图像分割儿乎成为不可能的任务。

因此，一些结合用户输入或先验信息的半自动图像分割方法，即交互式图像处理 [2H,成为近年来研究的热点。如经典的ACM方法，实际上也是一种半自动图像分割算 法，适当地选择初始曲线，是得到好的分割结果的必要条件；基于标记驱动的Watershed 图像分割方法QI,它结合用户的输入信息，提高分割结果；在Graph Cut方法中，用户 的交互式信息也是影响算法的分割结果至关重要的因素。这些交互式图像分割算法通常 是以像素为处理单位，但是，它们的一些基本思想显然也适用于基于区域的处理，从而 能够改进分割结果。

虽然，Mean Shift和Watershed等算法通常存在着过分割，但是它们得到了一个较好 的初始分割结果，即每个区域都包含着U标或背景的一些特征，为后续区域合并处理提 供了一个基础。但是，因为U标和背景通常呈现复杂的特征，传统的基于固定阈值的合 并方法很难得到有效的结果，因此需要研究新的算法解决复朵条件下的区域合并。

本章的研究对象是彩色（自然）图像的分割问题。将以Mean Shilt算法的分割结果作 为基础，提出一种新的交互式区域台并算法，来提取自然图像中的口标。本文所使用 Mean Shift分割软件是EDISON System123'它是个开放的Mean Shift分割软件，界面友 好，功能完善，是硏究Mean Shift算法很好的平台。

图3.1展示了分割软件的一个实例。其中（a）为原始图像，（b）为EDISON System分割 后得到的包含很多小区域的结果。

图3.1 EDISON System分割的例子

3.2区域的表示和相似性度量

Mean Shift算法一般将图像分割成一些区域，每个区域具有一定的特征。本文采用 RGB颜色空间表示每个区域，当然，其它颜色空间，如HsI和Lab等，也可用于对区 域建模。将RGB颜色空间量化为16x16x16=4096箱格，然后计算每个区域的规范化直 方图。为了度量区域之间的相似性.选择Bhatlacha系数测量区域R和Q的相似度：

4096

P（^0）=Z7HistR-HistQ

U = 1

3.1

式中，His蜷和His$分别表示区域R和Q的直方图。上标I】表示直方图的第I】个箱 格。

3.3目标和背景的标记

在交互式图像分割，用户需要指定LI标和背景的概念。用户可以在图像上通过绘制 标记，如直线，曲线和笔划等来输入上互动信息。含有LI标标记像素的区域因此被称为 LI标标记区域，而含有背景标记像素的区域被称为背景标记区域。图3.2 (b)显示了用 简单的线条标记LI标和背景的例子。我们用绿色标记来标示U标而使用红色标记来表示 对象的背景。请注意，通常只有一小部分的U标区域和背景区域会被用户标记。实际上, 用户的必要输入越少，交互式算法就越方便越强大。

图3.2 (a)初始分割。(b) 111用户交互式的信息输入。绿线是目标标记和红线是背景 标

记。(c)区域分割的结果。

目标标记完后，每个区域将被标记为三种类型的地区之一：日标标记区域，背景标 记区域和未标记的区域。要完全提取物体轮廓，我们需要将每个未标记的区域自动正确 的标记为

目标区域或背景区域。为了方便的后续讨论，我们分别用M。和MR表示目标 标记区域集和背景标记区域集，用N表示未标记区域集。

3.4

基于最大相似度的区域合并机制

经过U标/背景的标记后，准确地从背景中提的U标轮廓仍然是一个具有挑战性的问 题，

因为用户只指示了一小部分H标/背景的特征。传统的方法中，只有邻近区域的相 似性超过预设的阈值【2引才将两个区域合并。这些方法在自适应阈值选取上存在困难。一 个过大的阈值将导致LI标的区域的不完全合并，而过小的阈值可以很容易造成过合并， 即一些H标区域被合并为背景区域。此外，也很难判断何时该停止区域合并进程。

LI标和背景的标记分别提供了对象和背景一些关键特征。在于基于标记控制的分水 岭分割算法中，标记是算法的种子和出发点。类似的，提出的区域合并方法也将从初始 标记区域开始，然后所有未标记区域将逐渐标识为LI标区域或背景区域。这个懒怖的方 法提出了对齐抠出方法［⑼，它结合了基于分水岭初始分割的图形切割，这实际上是一 个采用最大流算法的区域合并方法。在本论文中，我们提出了一种自适应地基于极大的 相似性的合并机制，以辨别在目标和背景标记指导下所有未标记区域。

设Q表示R的一个相邻区域，S0={S^}.=n 表示Q的所有相邻区域的集合。所以 Q与它所有邻域相似性表示为Q(Q,S,)i = 1,2，…,q，显然ReSQo如果R和Q的相似性为 中Q(Q,S,)最大的，我们就将R和Q合并。合并规则定义如下：

若Q(R,Q)「晋x/(Q，S,)，则合并 R 与Q。

3.2

合并规则(2)非常简单，但它确立了该区域合并进程的基础。(2) —个重要的优 点是它避免了合并控制中相似性阈值的预置。虽然最值运算操作对异常值敏感，但我 们经验发现算法工作良好。这主要是因为，直方图是对本地区全局描述，它具有很强 的噪音和很小的变化。

但是，标记区域仅覆盖一部分的LI标和背景，那些U标和背景中的非标记区域也应 当被自动识别并正确标记。总的来说，标记区域包含了相应的主要特征，因此，未标记 的LI标区域与LI标标记区域，以及未标记的背景区域与背景标记区域有着更高的自相似 度。所以通常惜况下，非标记的目标区域不会与背景区域相合并。类似地，未标记的背 景区域同样不会与目标区域相合并。

3.5区域合并算法

基于最大相似度的区域合并算法(Maximal Similarity based Region Merging,简称 MSRM),分为两个迭代地执行的阶段，直到没有新的区域合并发生。合并策略是尽可 能合并背景区域，而保持前景区域不被合并。一旦合并完所有的背景区域，等价于提取 了目标。

对每一个区域BeMB,确定其邻域集合= {Aj.=12「。对每一个A：,如果A^MB, 求其相应的邻域集合SA,={A^}I=I, k，显然BeSA.o然后计算A,和MA.中的每一个区域 的相似度。如果B

和满足下式：

那么B和A「合并成一个区域，新的区域将和B有相同的标记，即： B = Bu A】

否则，B和A’将不台并。

以上的过程迭代进行。在每一次迭代中，集合MR和N将被更新.其中，Ng膨胀、 N收缩。当所有背景标记MR找不到新的合并对象时，迭代结束。经过第一阶段，部分 属于背景的区域互相合并。但是，仍有一些背景区域因为彼此间具有更大的相似度.因 此它们不能和背景标记区域合并。第一阶段的合并结果如图3.3 （a）所示。可以看出， 经过第一阶段后，大多数属于背景的区域己被合并，但仍有一些未标记的背景区域未和 背景标记区域合并。

为了完成LI标提取，第二阶段将以第一阶段剩下的未标记区域N为处理对象，其中 包含部分口标特征，同时也包含部分背景特征。未标记区域在最大相似度规则的指导下 互相融合，即目标部分互相融合，背景部分互相融合。

经过第一阶段台并之后，对每一个未标记区域（属于目标或背景）PeN,构成它的 邻域集合SP={H,}I=I2昇-接着，对每一个如果其满足H,gMB和HjEM。，构成 它的邻域集台S„. ={A»-}.in 那么P e SH1 O计算H,和秽中每一个区域的相似度 p（H,,S**l）o如果P和H\"满足下式:

°但訂）=噩乎何理） 那么将P与H,合并成一个区域 P = PkjH,

否则，它们不能合并。

以上过程迭代至未标记区域N中不再发生合并为止。图3.3 （b）表明，经过第二阶 段的合并之后，一些未标记口标区域和未标记背景区域分别互相融合。接着，重复地执 行第一阶段和第二阶段，直到没有新的合并发生。最后，每个区域被标记成两类：LI标 或背景，图3.3 （d）显示了最终提取的目标。在绝大部分实验中，算法将在2-3个回合 结束。

图3.3区域合并过程（a）第一回合第一阶段（b）第一回合第二阶段（c）第二回合第一阶段 （d）第二回合第二阶段 MSRM算法

输入：初始均值漂移分割结果。 输出：最后的分割图。 当处于最后循环的区域合并中，

第1阶段。将未标记区域N与背景标记区域MB合并。

输入：初始分割结果或第二个阶段的合并结果。 （1-1）对于每个区域BeMB,构成其邻域集合SB={A,}.=I2 ro （1-2）对于每个'且A^MB,构成其邻域集合弘二八

（1-3）计算p（A,,Sf-）,如果/9（Ai,B）=晋x/（），那么 B = B合并。

（1-4）更新MB和N。

（1-5）如果MB的地区无法找到新的合并对象，笫一阶段合并结束。否则，返回到（l-l）o 第2阶段。自适应地合并未标记区域N。

输入：第一阶段合并的结果。

（2-1）对于每个区域PeN,构成其邻域集Sp={Hi}.=12 pO

（2-2）对于每个HieMB且H工M。，构成其邻域集合弘二{A畀十『显然卩丘弘。 （2-3）计算°（耳,申）。如果p（Hj,P）=［晋x/（Hi，S『），那么P二PuHj,否则，P与H’ 不再合并。 (2-4)更新 N。

(2-5)如果在区域N无法找到新的区域合并，第二阶段停止。否则返回到(2-1)。 结束

3.6收敛性分析

该MSRM算法是一个迭代的方法。它逐步将未标记背景区域N分配到21叮然后把 所有剩下的区域分配到M。。可以很容易地看出该方法收敛。我们有以下定理。

定理1 2. 4节中的MSRM算法收敛，即所有的N区域经过若干迭代会被标记为 目标或着背景。证明如下：

如果在第一个阶段，一个未标记区域PwN在其邻域中有最大相似度区域 B(BSMB),那么P与B合并，即B二PuB。如果和P有最大相似度的区域B在标标 记区域中，那么P将保留。如果P和另一个未标记区域P' (P' WN)有最大相似度，那 么P与P'将在第二阶段合并.即P二P' u P。。根据以上分析，在迭代的下一个回合, P将与MB或其与另一个未标记区域P'合并，或仍保持不变。如果在某次选代后.任一 个未标记区域P在MB或N中找不到相应的合并对象，算法将停止。

从上面过程可以看出，随着合并的进行，来标记区域中的一部分与日标标记区域合 并，一部分将与背景标记区域台并，因此未标记区域N的个数将会逐渐减少。一旦N 停止减少，整个算法将停止，N中所有剩下的区域将被标记为因此，N中所有的 区域全部被标记，算法收敛。 3.7 本章小结

本章首先提出对彩色图像进行分割的算法，将以Mean Shift算法的分割结果作为基 础，提出一种新的交互式区域台并算法，来提取自然图像中的LI标。接着对MSRM算 法的背景知识做了介绍，即区域的表示和相似度的度量，以及标记的划分等。然后详细 描述基于最大相似度的区域合并算法，MSRM分为两个迭代地执行的阶段，直到没有新 的区域合并发生。合并策略是尽可能合并背景区域，而保持前景区域不被合并。一旦合 并完所有的背景区域，等价于提取了 LI标。最后本章指出了算法的收敛性，并进行了证 明。

4系统设计及实验结果

4.1引言

MATLAB是矩阵实验室(Matrix Laboratory)的简称，是美国MathWorks公司出品 的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计•算的高级技术汁算 语言和交互式环境，主要包括MATLAB和Simulink两大部分。本文采用MATLA7.10 完成系统设计。

4.2图像分割系统

为了验证本文的算法，本文设计了一个自适应图像分割系统，该系统由3个模块组 成，预处理模块、标记模块、和区域合并模块。该系统的总体框架如图所示，

图4.1图像分割系统框架

预处理模块的功能是：将原始的图片进行初始分割，这里采用的Mean Shift算法， 初始分割后保存的文件名为,imagenanie_IiiiSeg.png'。山于本文着重于区域合并算法，这 里采用EDISON System^23',它基于边缘信息对Mean Shift方法进行了扩展，区域性更好, 可以识别微弱边缘。

标记模块的功能是：根据用户鼠标动作所完成的输入，在初始分割后的图像上做好 相关的标记。其中目标标记为绿色，背景标记为红色。

区域合并模块是本文的核心部分，其功能是：根据LI标和背景的标记结果和初始分 割得到的小区域，按最大相似度规则进行合并，最后提取目标的轮廓。

4.3实验结果与分析

通过一些有代表性的例子测试提出的算法，然后进行鲁棒性分析以及介绍可能失败 的情况，最后分析了提出算法的局限性。

431实验结果

MSRM算法本质上是一个自适应区域合并方法。当用户输入交互式信息之后，算法 将自动地进行区域合并，将区域标记为U标或背景区域。图4.2显示了从天空背景中提 取飞机的例子。图4.2 (a)表示Mean Shift分割结果及交互式信息，其中绿色的标记表 示訂标，红色的表示背景，标记区域仅覆盖了 U标和背景的一部分。算法效率很高，只 需很少的标记，经过两阶段的区域合并之后，图4.2 (d)显示，目标被成功地提取。

图4.3为从复杂背景中提取一双鞋子。图4.3 (a)显示，Mean Shift分割存在严重的 过分割。LI标相对位于图像的，但是背景区域的颜色差异很大，而且LI标和背景有 混叠。。图4.3 (b)显示，MSRM算法仍成功地从背景中提取目标。

该算法方法可容易推广到多目标提取，图4.3显示了一个例子。在图4.3中，目标是 提取草原场景中的若干只幼狮。儿只狮子的体色和背景类似，，该算法仍然能使用儿个 简单的标记，成功地将它们与背景分离。

图4.2区域合并过程(a)到(d)显示了图像分割的过程

图4.3从复杂背景中提取一双鞋子

图4.4 一个多U标提取例子

4.3.2鲁棒性分析和失败情况

MSRM算法是一种交互式的图像分割方法，需要由用户输入标记。因此用户输入 的标记一定程度上会影响分割结果。根据大量的实验，发现只要标记能够覆盖U标的主 要特征，MSRM通常能够可靠地提取目标。

图4.5的第七行图像是从复杂的背景中提取一只天鹅,MSRM算法执行效果非常好。 图4.5 (b)显示，用更少的标记，仍可以提取天鹅的基本轮廓。图4.5用两种不同的标 记提取目标•得到了相同的结果。

但是，当阴影出现、LI标和背景间存在着模糊区域或对比度较低时，MSRM算法分 割性能会有所下降。例如，在图4.6中，人物U标和鲜艳的背景比较相似，在一些区域,

提出算法的分割结果将U标的一部分划分为背景。

其次，提出的算法以Mean Shift算法的分割结果作为基础，因此，如果Mean Shift 分割不能提供一个好的初始分割结果，MSRM算法或许会失败，图4.7显示了山于对企 鹅的初始分割效果不理想，无法成功提取忖标。当然，近年来，随着有关Mean Shift图 像分割算法的研究仍不断，将会降低提出算法对Mean Shift分割的依赖性。

图4・5a、b两组不同标记提取背景中的天鹅

图4.6人物分割失败例子

图4.7山于初始分割效果不理想而分割失败的例子

4.3.3分割效率分析

图4.2—图4.6的分割运行时间如表4.1。图4.2飞机、图4.4狮子、图4.5天鹅的用 时较短，平均用时为&45s,它们都具有口标和背景的对比度较高的特点，此时MSRM 算法的分割效率非常高。虽然图4.4狮子的是提取多LI标，但其用时最短，表明MSRM 算法的效率与訂标个数并无很大相关性。图4.3雪地鞋和图4.6人的用时分别为前三图 平均时间的3.2倍、6倍。其中图4.3雪地鞋存在很多的过分割，而且背景复杂，虽然得 到较好的分割结果，但是效率不如前三者，表明MSRM算法效率的非常依赖于初始分 割的结果。图4.6人的LI标和背景的的色彩都比较艳丽，对比度较低，且存在一定的过 分割，结果LI标没有完全提取出来，而且分割的效率大大降低。表明MSRM算法的效 率不仅依赖于初始分割结果，算法的有效性与LI标和背景的区分度有很大关系。 表4.1图像分割运行时间

图像 图4.2飞机 图4.3雪地鞋 图4.4狮子 图4.5天鹅 图4.6人 运行时间⑸ 9.49 26.91 7.01 8.86 51.31 4.3.4结论

提出了一种基于区域合并的交互式图像分割算法MSRM,它用Mean Shift算法对图 像作初步分割，分割结果的区域作为算法处理的基本单位。然后，用户输入交互式信息, 指定LI标和背景的大致位置和特征信息，提出的算法将自动从各种背景中分割LI标。提 出的方案在訂标标记和背景标记的指导下，基于最大相似度机制进行区域合并，井提取 □标。提出的算法简单有效，它对图像内容自适应理解。多个有代表性的实验结果验证 了本文提出算法的有效性。但是.当初始分割结集的区域数比较多时，提出的算法的实 时性将受到一定的影啊。

提出的方法提供了一种通用的区域合并框架，它本身并不依赖于Mean Shift分割， 其它算法(如Watershed【\"\"Level set|26L SuperPixel1271)的分割结果同样可适用于这个框架。

随着网络及多媒体时代的到来，人们对图像与视频分割技术提出了新的需求一一优 秀的数字图像及视频分割不但要具有精确的分割线，还应具备高自动化程度、实时性、 易于操作等重要特性。但在现有的图像与视频分割系统中，往往不能满足这样的需求。 所以针对数字图像分割系统的自动化程度及实时性的改进正逐渐成为学者们关注的热 点问题，尤其是在视频特征提取、机器视觉等应用上，更加侧重于对图像分割技术实时 性、自动化的需求。图像分割技术在整个图像处理技术领域起到了不可替代的基础性作 用，是后期分析图像、处理视频等操作的性能得以提高和效果得以改进的关键所在。

本文对数字图像分割技术进行了较为全面的研究，重点分析了 MSRM算法在图像分 割中的应用，实现了高效和便捷的自适应图像分割，本文所做的主要工作如下：

（1） 总结了图像与视频分割技术的发展历程，重点比较分析了各种类型图像与视频 分割技术的特点，侧重阈值分割、间断检测、区域分割三大类分割技术，深度挖掘了不 同类型分割技术的优势和需要改进之处。明确了图像预分割处理在图像与视频提取技 术中起到的制约作用。

（2） 对基于区域合并的纹理图像分割算法进行一些研究，交待了区域的表示和相似 性度量，阐述了基于最大相似度的区域合并机制，重点分析了区域合并过程，最后对合 并算法的收敛性进行了证明。

（3） 根据本文的改进思想，设计出了一套自动化图像分割系统，并验证了该系统具 有较好的实时性和较高的自动化程度。同时，结合通过Matlab7.10图像处理工具箱得 到的仿真结果，验证了本文改进思想的可行性，有效性。

参考文献

[1] Gonzalez R C, Richard E W. Digital image processing・ 2nd ed・ Beijing： Publishing House

of Electronics Industry, 2003, 460-521 ・ [2] 章毓晋.图象分割.北京科学出版社，2001.

[3] 边肇祺，张学工等.模式识别(第二版).北京：清华大学出版社，2000.

[4] K. Karu, A. K・ Jain, R・ M. Bolle・ Is there any texture in the images・ Pattern Recognition,

1996, 29(9)： 1437—1446

[5] Fabien S, Wojciech P・ Parameter estimation in hidden fuzzy Markov random fields and

image segmentation. Graphical Models and Image Processing, 1997, 59(4)： 205-220 [6] Zhang Y Y, Stephen S, Michael B. Segmentation of brain MR images using Markov random

field ・ In: Proceedings of Medical Image Understanding and Analysis, 1999, 65-68 [7] 叶俊勇，汪同庆，彭健等.基于小波分形的图像分割算法.计算机科学，2002, 29(12)：

157-159, 149

[8] Sang H P, Dong Y, Sang U L・ Color image segmentation based on 3-D clustering:

morphological approach・ Pattern Recognition, 1998, 31(8)： 1061-1076

[9] Philippe S ・ Segmentation of digitized dermatoscopic images by two-dimensional color

clustering・ IEEE Transaction On Medical Imaging, 1999, 18(2)： 1-171 [lOJEnno L, Helge R・ Adaptive color segmentation-a comparison of neural and statistical

methods. IEEE Transaction On Neural Networks, 1997, 8(1)： 175-185

[1 l]Kurugollu F, Sankur B, Harmanci A E・ Color image segmentation using histogram

multithresholding and fusion・ Image and Vision Computing, 2001, 19(13)： 915-928 [12] Wong F ,

Nagarajan R , Yaacob S . Fuzzy image segmentation via

thresholding ・ Journal of the Institution of Engineer (india) Electronics and Telecommunication Engineering Division, 2006, 86： 68-72

[13] Mao K Z, Peng Z, Tan P H・ Supervised learning-based cell image segmentation for immuno-histochemistry. IEEE Transactions on Biomedical Engineering, 2006, 53(6)： 1153-1163 [14] Blinn J F. What is a pixel・ IEEE Computer Graphics & Applications, 2005, 25(5)： 82-87 [15] 陆剑锋，林海，潘志庚.自适应区域生长算法在医学图像分割中的应用.计算机辅 助设

计与图形学学报，

[16] 张发存，赵晓红，王忠等.区域生长法图像分割的数据并行方法研究.计算机工程, 2004,

30(17)： 14-16

[17] Carevic D , Caelli T • Region-based coding of color image using Karhunen-Loeve transform•

Graphics Models and Image Processing, 1997, 59( 1): 27-38

[18] 杨晖，曲秀杰.图像分割方法综述.电脑开发与应用，2005, 18(3)： 21-23

[19] Comaniciu. V・ Ramesh and P ・ Meer ・ Real-time tracking of non-rigid objects using mean

shift・ In Proc・ IEEE Conf, on Computer Vision and Pattern Recognition> Hilton Head. SC, olume II, June, 2000o PP. 1 42—1 49.

[20] S・ Chien・ Y・ Huang and L・ Chen・ Predictive watershed： a fast watershed algorithm

for video segmentation • IEEE Transactions on circuit and systems for video technology. 2003, 13(5)： 453-461 ・

[21] Levin and A. Rav. Acha and D・ Lischinski- Spectral matting. In Proceedings of die IEEE

onfefence on Computer Vision and Pattern Recognition, 2007.

[22] Meyer and S・ Beucher・ Morphological segmentation ・ Journal of Visual Communication

and Image Representation・ 1990, 1(1)： 21-46•

[23] EDISON图像分割软件• http： //www.caip.njtgers.edu/riul/research/code.htrnl

[24] M ・ Sonka, V・ Hlavac, R・ Boyle, Image Processing, Analysis and Computer

Vision,Thomson, 2007.

[25] Y. Li, J. Sun, C. Tang, H. Shum, Lazy snapping, SIGGRAPH 23 (2004) 303-308.

[26] 朱付平,田捷,林瑶，葛行飞.基于Level Set方法的医学图像分割.软件学报.2002, (9)：

1866-1872.

[27] Pen, J・ Malik, Learning a classification model for segmentation, ICCV03, vOl. 1, pp. 10. 17,

Nice, 2003.

本论文是在我的导师郑庆庆的悉心指导和大力支持下完成的。自撰写论文以来，郑 老师细致而具体指导我们每一个同学，并且指导性的提出许多宝贵的意见与建议。郑庆 庆导师是位学识渊博、亲切和蔼的一名教师，在她这里我们不仅掌握了此次论文的相关 技能和知识，而且从她身上学到了很多做人的道理。

同时，我还要感谢我的同学郑凯、徐海洲等在毕业设计期间给予我的大力支持与帮 助。他们的睿智与热心，给了我许多的启发和帮助，对我的论文的顺利完成作了许多的 贡献。在此，我表示诚挚的谢意。

特别真挚的感谢我的父母，他们的养育和教导之恩是我立身行事的根本。感谢他们 一直以来无私地支持我、鼓励我，使我能够安心地学习，学业得以顺利完成。家人的支 持和理解，永远是我前进的动力。

最后感谢我的母校武汉科技大学，感谢四年来的培养，让我各方面都有了提高！