1. 研究目的与意义（文献综述）
1.1 研究目的及意义 图像处理是指将图像信号转换成数字信号并利用计算机对其进行处理的过程。图像处理最早出现于二十世纪五十年代，数字图像处理作为单独的一门学科的形成大约在二十世纪六十年代初期，数字图像处理技术是一个跨学科的领域，尽管它的发展历史不是很长，但是却引起了各方面人士的广泛关注。 图像分割是一种重要的图像处理技术，在理论研究和实际应用中都得到了人们的广泛关注。图像分割是图像处理中的一个前期处理阶段，它在图像处理中占有重要的地位，因为图像分割质量的好坏直接影响到对图像后期的分析、理解及处理等，比如对图像的特征提取等等。图像分割在不同的领域中有着不同的称谓，一般认为，它是将一幅图像分成各具特性的区域，把目标区域从背景中提取出来的技术和过程。 图像分割的形式多种多样，有时需要将一幅图像分割成一个个可识别的目标，类似于人对图像的感觉一样，而有时需要将它划分成若干具有某种一致性的区域，如色彩的一致性，纹理的一致性等，作为底层视觉处理的一部分。实际对图像分割时，图像的哪些部分重要，人们又对哪些部分感兴趣，需要根据具体的应用而定。 至今提出的分割算法有上千种，而新的算法还在不断被提出。虽然这些算法的实现方法不同，但对于灰度图像来说其分割技术大都基于像素灰度值的两个性质：相似性和不连续性，即在同一个区域内像素灰度值比较接近，而在相邻两区域交界处的像素灰度有跳跃。 从图像分割实际应用的角度，图像分割可以分为阈值分割、边缘检测、区域分割、运动目标分割等。（1）阈值分割是指通过找到一个或多个最优阈值把图像分割为若干目标和背景的分割方法，适用于目标和背景有较强对比的图像分割。（2）边缘检测是通过检测图像特性（灰度）发生变化的位置（边缘）来进行图像分割，边缘是灰度值不连续的结果，这种不连续可利用求导数而检测，适用于边缘灰度值过渡比较尖锐且噪声较小的图像分割。（3）区域分割是一类应用区域生长、区域分裂与区域合并技术的图像分割方法，它利用图像的空间性质，根据某个相似性准则（例如灰度、纹理、形状等、将图像分割成不同的区域）采用小的区域而不用像素，优点是降低了对噪声的灵敏度。但是区域生长技术的运算复杂、用时较长、不适合于实时图像处理。只有当阈值分割或边缘提取技术无法产生满意的结果时，才考虑应用区域生长方法。（4）运动目标分割的研究对象是图像序列，图像序列由不同时刻采集的多帧图像构成，包含了相机与景物之间的相对运动信息。运动目标分割就是通过分析图像序列，获取景物的运动参数及各种感兴趣信息。 到目前为止，虽然已有很多种图像分割方法，但是还没有一种普遍适用于各种图像的有效方法。图论方法在聚类优化问题中应用研究开始于20世纪60年代前后，该方法在图像处理与分析方面的应用开始于20世纪80年代以后。 图论是离散数学的一个分支，它起源于数学，其应用相当的广泛，遍及系统工程、交通运输、生产管理、电工学、城市规划、通信、经济等各个领域。它的发展可以追溯到二十世纪五十年代，图论是研究具有特殊的特性的个体之间的关系的数学理论与方法。图论的研究对象是节点和边。用图论的方法来研究分析讨论所研究的对象的指导思想是：运用图论的相关概念及理论方法，把所讨论的问题归结成图，然后对图进行相应的分析研究以及相关的运算。 基于图论的图像分割方法在对图像进行分割时即考虑到了图像的局部信息也兼顾到了图像的全局信息，在两者之间得到了一种平衡，该方法的重要意义是它把图论网络和目标函数功能涂层的作用结合到了一起；此外，基于图论的图像分割结合了计算机视觉空间变量的概念，是一种智能化的分割；而且，该方法的适用性很强，不只在工业图像、医学图像等分割中可以得到好的结果，还在视频图像、三维图像处理中都得到很好的应用。图论里面已经有很多比较成熟的算法和思想，所以可以很方便的利用图论工作者已有的研究成果来应用于图像处理中。 现今，图像分割已成为图像处理技术发展的一个瓶颈，由于图像分割结果的判断是由人眼来进行的，所以在研究图像分割算法时，应该充分考虑人的视觉特性和图像自身的特点。除此之外，像素周围的灰度值在视觉上也影响了我们的判断，并且空间位置关系在很大程度上影响了图像分割效果。而图论理论具有解决该缺陷的能力，所以可以将图论理论与原有的一些图像分割算法相结合，使基于图论理论的图像分割方法能更好地适用于普遍的图像分割并且达到更好的分割效果。1.2 国内外研究现状 图论在数据聚类和图像分割中的应用可以追朔到1971年Zahn的工作，他利用图论的最小生成树（Minimum spanning tree）进行聚类与图像分割，即将图像聚类与分割问题，转化为图论中的最小生成树问题。在聚类中，生成树中结点间的权表示结点间的距离，在对图像分割中，结点间的权表示的是结点间灰度值的差异。尽管Zahn的图像分割方法基于简单的权值计算与阈值设置，在某些场合的应用中会出现较大的误差，但Zahn的基于图论的处理方法在计算机视觉中受到欢迎，到目前为止，已具有多种基于图论的图像分割技术与方法。 基于图论的图像分割技术是近几十年来国际上图像分割领域的一个新的研究热点。基于图论的图像分割准则实际上是将图像分割问题转化为求解最优化问题，是一种点对聚类的方法。 把图分割用于图像分割主要有两个重要的方法，取决于节点上的“指引函数”是否有限制于实线或二进制/整形的值。二进制约束的一个优点是一个计算的指标函数决定一个分割，而缺点则是二进制约束对于很多泛函的最小化来说，组合优化通常是很难的或者是完全不可行的。 有些算法放宽了指示函数中二进制的约束，并基于问题中的函数或所选的规则化的方法，得到了产生一个割的不同的分割方法。放宽指示函数的二进制约束的主要的缺点是：求解最优化问题必须转化为一个“硬的”分割。然而，这样做的最大的优点是使得许多优化问题变的易于处理。以这种形式为指导的最成功的分割方法有归一化算法和文献中等的一些相关的方法。这些算法都是和一幅图像的图的光谱图相关的，并且算法的最终都需要解特征向量问题。 目前，基于图论的图像分割方法的研究主要集中在以下几个方面：一、最优剪切准则的设计；二、谱方法用于分割；三、快速算法的设计；四、其它图论方法，如显性集理论和计划理论。其中，谱方法是直接对原图像构造相似度矩阵或拉布拉斯矩阵，然后通过求解矩阵的特征矢量直接进行分割或以此为基础进一步构造特征矢量来指导分割。而快速算法的设计则主要是对相似度矩阵的采样构造和稀疏处理，或者改变搜索策略直接进行图缩减来提高算法速度。 最近一二十年出现的一种基于图论的图像分割方法是基于直接寻找图中的最小割的最优化方法，该方法对图的分割的原则就是使所得到的子图之间的相似度最低。Wu和 Leahy通过寻找很多对的水源/水槽和寻找具有最小割的分组把这种应用用于图像自动分割方面。正如大家所指出的，这种函数的最小化将导致趋于分割单个顶点或着小簇，即会出现分割出一个很大的图和一个很小的图的情况。Shi 和 Malik针对该问题，提出了一种归一化割（Normalized Cut，Ncut）算法，该方法很好的解决了Wu等的方法存在的缺陷。该方法考虑到了图像中所分子区域内部的自相似性，且采用归一化的方法，所以分割效果得到了很大的提高。但是归一化割的问题是一个NP完全问题，计算复杂度相当高。所以该算法的实用性受到了很大的限制。基于等周算法的图像分割方法是由Leo Grady等提出来的。该方法通过寻找最小等周率问题来实现图像的分割。相对于归一化割方法，在速度和分割的稳定性方面均有提高。 虽然基于图论的图像分割技术研究还处于初级阶段，但是基于图模型的图像分割已被认为是目前最为成功的分割方法之一。
2. 研究的基本内容与方案
2.1 研究（设计）的基本内容、目标 学习并掌握三种基本分割方法：(1)基于阈值图像分割；(2)基于边缘检测及算子分割；(3)基于区域特性的图像分割。 研究基于graph-based算法的图像分割算法及相关技术。 仿真基于graph-based算法的图像分割算法并比较其他分割方法以及分析不同结果。2.2 研究（设计）的技术方案及措施 在众多的图像分割方法中。基于图（graph-based）的分割方法显示出强大的优势，它可以有效地结合图像灰度、纹理和色彩等各种信息达到满意的分割效果，此外图论中诸多成熟而完美的经典算法又为这一类图像分割算法提供了有力的计算工具。 纵观历年文献，可以发现这些基于图论的图像分割技术与方法具有相同的过程，即基本的框架，就是将图像分割问题基于图论中的图或网络进行转换，进而对转换后的问题求解或优化。 求解或优化问题包括两个步骤：在图像分割空间定义合适的目标函数或代价函数，以及求解这个函数。如图一所示的基于图论的图像分割技术的基本框架，将图像映射为网络图，基于网络图将图像分割问题转化为对图的不同操作，并设计分割准则，然后根据不同的分割准则形成不同的目标函数，通过对目标函数的求解，实现对图像的分割。
图一 基于图论的图像分割技术的基本框架 本文研究内容主要包括三个方面： 第一个方面是系统性的研究。针对基于图论的图像分割技术及应用，基于图论的图像分割发展至今，出现了多种技术与方法，但对这些技术与方法缺乏系统性的介绍。为了更好的认识基于图论的图像分割，本文对主要的技术从特性与应用等方面进行分析与研究。
3. 研究计划与安排
第1－3周：查阅相关文献资料，明确研究内容，了解研究所需理论基础。确定方案，完成开题报告。第4－5周：熟悉掌握基本理论，完成英文资料的翻译，熟悉开发环境。第6－9周：编程实现各算法，并进行仿真调试。第10－12周：针对具体的实验数据，完成整个系统的仿真，实现功能。第13－15周：完成并修改毕业论文。第16周：准备论文答辩。
4. 参考文献（12篇以上）
[1] 刘建龙.基于图论的图像分割算法研究[D].学位论文.南京理工大学.2006[2] 廖武忠.基于图论理论的图像分割算法的研究[D].学位论文.华南理工大学.2012[3] 樊雷茅.图像分割算法研究.学位论文[D].华南理工大学.2010[4] 田沙沙.基于图论的图像分割算法研究[D].学位论文.重庆大学.2011[5] 张乾，王林.一种基于图论的图像分割算法[D].学位论文.四川大学.2012[6] 管慧娟.基于区域的图像分割算法[D].学位论文.哈尔滨工业大学.2005[7] 冯阿睿.图像归一化算法研究.学位论文.重庆大学.2014[8] 冈萨雷斯RC.数字图像处理.阮宇智译(第二版)[M] .北京：电子工业出版社，2003[9] 陈桂明，张明照，戚红雨.应用matlab语言处理数字信号与数字图像[M].科学出版社， 2000[10] 景晓军等编著．图像处理技术及其应用[M].北京：国防工业出版社，2005[11]Qu Shaojun，Qiao liang. The human image segmentation algorithm based on face detection and biased normalized cuts[J].Production PlanningControl,2012,23(2-3):83-104[12]Yang Dandan. Rock particle image segmentation on multi-scale and normalized cut.Proceedings of the the IEEE,2014,99(1):80-93[13] Yu Wen Ting. An improved Normalized Cut image segmentation algorithm with k-Means cluster. Applied Mechanics and Materials ,2014,25(2-5):50-55[14] P.Felzenszwalb. D. Huttenlocher. Efficient Graph-Based Image Segmentation[J].International Journal of Computer Vision,2004,59(2):167-181.[15]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.
