基于图论的阈值化图像分割方法与研究

基于图论的阈值化图像分割方法与研究内容摘要：

以归并的点为止。 如此往复，直到再没有像素点可以被合并，这样一个区域就形成了。 和区域生长算法不同的是，区域分裂合并法则不需要先找指定的种子像素点，它按照某种一致性准则直接进行分裂或合并区域，当相邻的区域相似性一致时，通过合并运算合并为一个大的区域，相反的，当一个区域内不满足一致性原则就分裂成几个小的区域。 因此区域分裂合并算法的研究重点是对分裂和合并的准则设计。 基于区域的分割方法的优点为：由于阈值化分割方法很少或没有考虑到空间关系，使得在多阈值选择上受到诸多的限制，而基于区域的分割算法则完全可以弥补这种不足。 基于区域的分割方法在图像的空间关系上，不仅考虑到像素的相似性，而且还考虑到空间区域上的邻接性，因此可以有效地消除噪声的4干扰，在算法上有很强的鲁棒性。 无论是合并运算还是分裂运算，都可以很好的将分割深入到像素级，因此在图像分割的精度上有较高的保障。 基于区域的方法的缺点则是：由于物体的轮廓线经常是任意形状的，因此在分割的速度上都较慢。 （4） 基于聚类的分割基于聚类分割就是按照样本之间的相似性原则把集合划分成若干个互不相交的子集，划分的结果应满足某种表示聚类准则质量最大化。 如果用距离表示两个样本间的相似性时，就会把特征空间划分成若干个区域，这样每一个区域相当一个类别。 一些常用的距离度量准则都可以作为相似性的度量标准。 聚类分割中典型的算法有模糊C均值算法 [10] 、K均值算法 [11]、分层聚类方法 [12] 和期望最大化等。 虽然聚类算法不需要训练集，但对初始分割时需要提供一个初始参数，同时初始参数的选定的恰当与否对最终分类结果有很大的影响，因此对于聚类分割，初始参数的选取成为该方法的一个技术难点。 （5） 结合其他特定理论的分割方法近年来，大量学者致力于将新方法、新概念应用于图像分割中，在图像分割方面，结合特定理论的图像分割方法已取得了较好的应用效果。 图论、小波分析和小波变换、模糊理、神经网络、遗传算法、粗糙集理论、数学形态学 [1315]等以近年来发展迅速的灰色系统理论等数学工具的利用，为图像分割提供了更多的选择，并且针对不同的图像有效地改善了分割效果。 基于图论的图像分割技术是近年来国内外在图像分割领域的一个新的研究热点。 该方法基本思想是将图像映射为带权无向图, 把图像的像素点视作节点, 利用最小剪切准则得到图像的一个最佳分割。 该方法在本质上把图像分割问题转化为图的最优化问题, 是一种点对聚类方法, 因此在数据聚类也会有很好的应用前景。 但由于该方法涉及的理论知识较多, 应用研究也还处在初级阶段, 因此该法将会成为图像分割领域中一个具有挑战性的研究热点。 图像分割的发展现状及趋势图像分割方法的重要性以及国内外学者的高度关注，使得图像分割技术得到了很好的发展，到目前为止，已经形成了很多种图像的分割方法，但是由于图像本身的特性，使得每种图像分割方法都是针对某一类图像的，即每种图像分割算法只能针对特定的图像取得较好的分割结果，而不能对所有种类的图像都得到较好的分割结果。 算法本身具有一定的针对性，而没有不具有算法的通用性。 这就使得人们在进行图像分割时，只能针对某类图像进行分割，没不能对所有的图像进行分割。 造成这种局面的主要原因，主要是因为以下三个方面[16]：（1）由于现实生活中，图像的种类复杂，使得人们在研究对图像进行分割5时，在对算法进行设计时，都有时针对某类图像的，而没有考虑其他的图像。 即在算法的本身就具有一定的针对性。 （2）人们在对图像进行分割时，尤其在设计图像的分割算法时，不仅需要数学理论的支持，还需要对心理学的借助，这是因为人们在处理图像时，视觉心里的反映是一个很重要的方面，不能被忽视。 而目前大多数的图像分割算法，由于各种原因，而没有很好的考虑到这一点，因此很难取得较好的图像分割效果。 因此，应该借助各种新的理论和工具来弥补这种不足。 同时，在面对数量庞大，各式各样的图像库，我们还要主要图像算法的实时性，因此对图像分割算法的研究，仍然有一定的挑战性。 （3）人类视觉系统是一个复杂的系统，它涉及到很多领域的知识和理论。 到目前为止，我们还没有一个标准化、系统化的认识，同时也缺乏对这要知识的认识和了解。 所以，设计一个适用性很好的图像分割算法仍然是一个很有挑战性的事情。 纵观图像分割技术的发展历程，虽然在图像分割技术上来说，很难得到一个非常理想的图像分割方法。 但对新知识新理论的借助，对这要技术上的克服不是没有一定的可能的，而且这也是图像分割方法的发展的一个必然趋势。 目前主要的研究思路包括以下几个方面：（1） 神经网络 [16]、模糊算法 [17]、遗传算法 [18]、图论算法 [19]、粗糙集理论、小波分析 [20] 、形态学等新的方法和概念应用到图像分割领域。 这些新的理论知识和工具的引入，为图像分割方法开辟了新的思路，也为图像分割方法的研究注入了新鲜的动力和活力。 同时这些新理论和新工具的借鉴，避免了单一算法的不足，提高了图像分割算法的有效性。 （2） 对 多 种 图 像 分 割 算 法 的 结 合 时 图 像 分 割 方 法 的 另 一 个 新 的 研 究 思路，也受到人们越来越高度的重视。 目前的图像分割方法都中对多种图像分割方法的结合。 这种结合后的图像分割方法具有一定的优势。 因为单一的图像分割算法都具有一定的针对性和局限性。 而两种或者两种以上的方法的结合，往往可以避免这种单一算法的不足，起到扬长避短，各显其优的特性。 当然这种结合的优势，要在有效的结合下才能显示，仅仅把两种算法放在一起是无法发挥这样优势的。 （3） 对特定邻域的知识的注入和对特殊问题的解决也是图像分割方法研究中的一个热点和重点。 人们对图像分割方法的研究不再局限于图像分割处理技术的方面，与其他领域的图像处理的结合将会成为图像分割技术的另一个研究热点。 课题的提出与研究的意义在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣。 这些6部分常称为目标或前景(其他部分称为背景).它们一般对应图像中特定的、具有独特性质的区域。 为了辨识和分析目标，才有可能对目标进一步利用。 图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。 这里特性可以是像素的灰度、颜色、纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 图像分割技术不仅是一种重要的图像处理技术，而且还在人类的生产和生活中得到广泛的应用，因此受到了越来越多人的关注，吸引了越来越多专家和学者的重视和研究。 由于图像分割的广泛应用，因此图像在不同领域也有着其不同的应用名称，比如在在目标检测领域中的目标轮廓技术，图像求差和图像区分技术等，以及在图像识别技术中的目标识别和目标跟踪等等。 无论图像分割技术的名称如何变化和改变，但其本身的核心仍然不会偏离图像分割技术的。 图像处理中，图像分割是最为基础和重要的领域之一，也是低级计算机视觉中最基本最重要的研究内容，是成功进行图像分析、理解与描述的关键技术，因为图像分割结果的质量直接影响以后进行的分析、识别和解释的质量。 从上世纪 50 年代，人们就可以研究图像的分割方法，随着研究的深入和计算机科学技术的发展，以及与新理论和新工具的借鉴和结合，到目前为止，专家学者们以及提出了上千种各种类型图像分割方法，而且这方面的研究仍在积极进行。 因此对这方面的研究有着极其重要的理论意义和现实意义。 基于图论的图像分割方法是近年来一个研究热点，该方法把图像看作是一个带权图，图中的节点对应着图像的像素，权值的大小表示两点间的相关性。 通过对能量函数进行组合优化来实现对像素的合理分类。 这种运用图划分的理论来实现对图像中目标图像的分割方法，相对于其他的图像分割方法，在某些方面取得了较好的图像分割效果，因此受到越来越多国内外学者和专家的关注。 虽然基于图论的图像分割方法具有一定的优势，但是这类方法一般都有较高的复杂性，使得算法实时性较差，同时在区分像素点间的相似性时，也存在这一些问题。 因此有必要把基于图论的图像分割方法与其他的有关图像处理的理论和知识进行有效的结合，以便取得更好的图像分割效果。 研究内容及论文的组织结构论文首先对图像分割的方法进行了研究，同时深入的研究了基于图分割理论的图像优化组合分割算法。 通过对基于图论的组合优化算法的研究和改进，提出了一种改进的基于图论的 Normalized Cut 准则的组合优化算法，并应用到阈值图像的分割中，该算法的实时性上和分割的效果上都取得了很好的成效，同时还具有较好的抑制噪声的能力。 其次，提出了一种改进的基于图论的MinMax Cut 准则的组合优化算法，该算法把传统的基于 MinMax Cut 准则图像分割方法，应用到阈值图像分割中，大大节约了算法的实现时间和空间，同7时也取得了较好的分割效果。 本论文的结构安排如下:第一章 在阅读大量的国内外文献基础上，研究了有关图像分割的基本理论，深入地探讨了有关图像分割的方法，总结了图像分割的含义，分类及发展现状和今后的趋势。 第二章 介绍了图的基本概念以及图划分的理论、图与图像间的相互对应关系，从而引出了基于图论的图像分割方法中的一些基本方法、常用的割集准则，以及基于图论的图像分割方法的研究进展、特点和存在的不足，为下文的基于图论的图像分割方法的改进提供了理论基础。 第三章 介绍和分析了基于图论的图像分割方法中常用的运用NormalizeCut准则割集作为分割准则的图像分割方法，并在把这种方法运用到阈值化的图像分割的基础上，分析了在该种方法中像素点间的相关性权值的计算公式的不足，提出了一种具有抗噪性的基于归一化准则的图像分割方法，通过实验结果，验证了该种图像分割方法的优势和实用性。 第四章 针对基于图论的图像分割方法中通用性的不足，提出了一种基于MinMax Cut的阈值化图像分割方法。 该方法采用MinMax Cut划分测度作为区分目标和背景的阈值化分割准则。 在描述图像各像素间的相似性关系权值矩时，把基于图像像素的权值矩阵换成基于灰度级的权值矩阵，大大节约了算法实现的复杂度和算法所需要的存储空间度。 并用类似于基因势函数的计算公式作为图权公式，该公式以统计学的形式更为全面的反映了两像素点间的相似性，同时又避免了通过手动的形式来设置控制像素点间相似性因素的差异敏感程度参数的不足，提高了算法的通用性。 通过实验结果，验证了本章算法的实用性。 第五章 总结了论文的研究课题和所做的工作，并对下一步的研究计划和研究前景进行了展望。 本章小结本章对图像分割进行了概述，主要介绍了图像分割的数学定义，需要满足的条件，以及国内为学者对图像分割方法的大致分类，并对常用的图像分割方法进行了简单的介绍，同时也对进行图像分割方法的发展状况以及今后的发展趋势进行了综述。 在此基础上提出了本课题的研究意义。 并对本论文的主要内容和结构安排进行了介绍。 8第二章 图论的基本理论知识 图的基本概念及理论在数学领域，图是离散数学的一个分支，有关图的理论是一门实用价值很高的学科。 在计算机科学领域，图是一种特殊的数据结构，它有着自己独特的定义形式，也从不同的理论出发点划分出不同种类的图。 而有关图的划分的理论是基于图论的图像分割方法的理论基础，为图像分割提供了一种新的理论方法。 图的含义及表示图是关系的一种数学表示。 图是由若干顶点和连接这些顶点的边构成 [21]。 一般情况下，若用 G 表示一个图的话，那么可以用非空顶点集合Vag = {v1, v2 , v3 ⋅ ⋅ ⋅ vn} 和非空边集合 Eag = {E1, E2 , E3 ⋅ ⋅ ⋅ Em}组成。 其中，集合 Vex 中的元素个数，即图的顶点数，是由图 G 的构成来决定，称为图 G 的阶。 而边集合 Eag 中元素的个数也是由图 G 的构成决定的，称为图 G 的规模。 边集合 Eag中的每个元素，即图的边都是由图中的两个不同的顶点组成，可以表示为Ex ∈VV j ，因此图中边就是连接顶点 i 和顶点 j 的弧，也可以用 VV j 来表示。 图的分类由于出发点和目的不同，可以把图分为不同的种类。 一般情况下，人们依据连接两顶点间的边是否具有方向，把图分为无向图和有向图。 通常情况下，人们在运用图时常常给图中的边赋予一定的数值，这种图为加权图。 这些数值表示为两顶点间的联系。 数值的大小可以表示为这种联系的紧密程度。 通常情况下这些数值又称为图中边的权值。 （ 1）无向图在图 G 中，如果连接两个顶点间的边是没有方向的，那么图 G 就称为无向图。 也就是说，连接两个顶点 i 和 j 的边是无方向的，先后顺序是无关的，即：VV j 和 V jVi 表示的是同一条连接两个顶点 i 和 j 的边，因此也可以认为组成边的顶点偶对是无序的。 在图 G 中每个顶点都有一个度。 对于无向图来说，顶点 VX的度是指与 VX 相连接的边的数目，一般记为 deg(VX )。 可以把图 中的无向图表 示 为 如 下 形 式 ， G = G(Vex, Eag ) ，Vex = {v1, v2 , v3 , v4 , v5 , v6} ，Vag = {v1v2 , v1v4 , v1v6 , v2v3 , v2v4 , v3v4 , v4v5 , v5v6}。 （ 2）有向图在图 G 中，如果连接两个顶点间的边是有方向的，那么图 G 就称为有向图。 也就是说，连接两个顶点 i 和。