MATLAB的图像分割算法研究Word格式文档下载.doc

1、例如，可以对图像的灰度级设置门限的方法分割。值得提出的是，没有唯一的标准的分割方法。许多不同种类的图像或景物都可作为待分割的图像数据，不同类型的图像，已经有相对应的分割方法对其分割，同时，某些分割方法也只是适合于某些特殊类型的图像分割。分割结果的好坏需要根据具体的场合及要求衡量。图像分割是从图像处理到图像分析的关键步骤，可以说，图像分割结果的好坏直接影响对图像的理解。2.1 图像分割方法的发展和现状分割问题的困难在于图像数据的模糊和噪声的干扰。前面已经提到，到目前为止，还没有一种或者几种完善的分割方法，可以按照人们的意愿准确的分割任何一种图像。实际图像中景物情况各异，具体问题具体分析，需要根据

2、实际情况选择适合的方法。分割结果的好坏或者正确与否，目前还没有一个统一的评价判断准则，分割的好坏必须从分割的效果和实际应用场景来判断。不过在人类研究图像的历史中，还是积累了许多经典的图像分割方法。虽然这些分割方法不适合所有类型的图像分割，但是这些方法却是图像分割方法进一步发展的基础。事实上，现代一些分割算法恰恰是从经典的分割方法衍生出来的。早期的图像研究中，图像的分割方法主要可以分为两大类。一类是边界方法，这种方法的假设是图像分割结果的某个子区域在原来的图像中一定会有边缘存在；一类是区域方法，这种方法的假设是图像分割结果的子区域一定会有相同的性质，而不同区域的像素没有共同的性质。这两种方法都有

3、缺点和优点，有的学者也试图把两者结合起来进行图像分割，随着计算机处理能力的提高，很多方法不断涌现，如基于彩色分量分割、纹理图像分割。所使用的教学工具和实验手段也是不断的扩展，从时域信号到频域信号处理，近来小波变换也应用在图像分割当中。2.1.1 研究背景与意义数字图像目标分割与提取是数字图像处理和计算机视觉领域中一个备受关注的研究分支。因为在目标分割与提取过程中可以利用大量的数字图像处理的方法，加上其在计算机视觉、模式识别等领域中的广泛应用，都吸引了众多研究者的注意。相信对这一问题的深入研究不仅会不断完善对这一问题的解决，而且必将推动模式识别、计算机视觉、人工智能等计算机科学分支的发展。图像分

4、割和边缘检测的问题在近二十年中得到了广泛的关注和长足的发展，国内外很多研究人士提出了很多方法，在不同的领域取得了一定的成果。但是对于寻找一种能够普遍适用于各种复杂情况的准确率很高的分割和检测算法，还有很大的探索空间。边缘提取和分割是图像分析的经典研究课题之一，目前的理论和方法仍存在许多不足之处，仍在不断改进和发展。需要说明的是：边缘与物体间的边界并不等同，边缘指的是图像中像素的值有突变的地方，而物体间的边界指的是现实场景中的存在与物体之间的边界。有可能有边缘的地方并非边界，也有可能边界的地方并无边缘，因为现实中的物体是三维的，而图像只具有二维信息，从三维到二维的投影成像不可避免的会丢失一部分信

5、息；另外成像的过程中的光照和噪声也是不可避免的重要因素。正是因为这些原因，基于边缘的图像分割仍然是当前图像研究中的世界级难题，目前研究者们正在试图在边缘提取中加入高层的语义信息。由于图像的多义性和复杂性，许多分割的工作无法依靠计算机自动完成，而手工分割又存在工作量大，定位不准确的难题，因此，人们提出了一些人工交互和计算机自动定位相结合的方法，利用各自的优势，实现目标轮廓的快速定位。相信这些交互式方法的应用，必将推动图像目标分割与提取这一既具有广阔的应用前景又具有重要的学术价值的课题的进一步研究，也必将成为一个更为独立和活跃的研究领域。2.2 基于图论的图像分割基于图论的图像分割技术是近年来国际

6、上图像分割领域的一个新的研究热点，在此，有必要先介绍一下基于图论分割的一些基本知识。2.2.1 基本知识（1）图的最优划分准则令图G=（V，E），图G被划分为两部分A、B，且有AB=V，AB=，节点之间的边的连接权为（W（M，V），则将图G划分为A，B两部分的代价函数为：cut（A，B）= （1）使得上述剪切值最小的划分（A，B）即为图G的最优二元划分这一划分准则称为最小割集（Minimum cut）准则。（2）图像的最佳分割将一幅图像视为一个带权的无向图G=（ V，E），像素集被看作节点集.边缘集被看作边集E，像素之间的连接权为W（i,j），则将图像二值划分为两个集合（区域）A，B的代价函数

7、为：cut（A, B）= （2）对于一幅图像，使得上述代价函数最小的划分即为图像的最佳分割。（3）权函数权函数一般定义为两个节点之间的相似度。在基于图论的图像分割方法中常见的权函数有如下形式：上式权函数中，对于灰度图像，Fi的值为像素的灰度值，Xi为像素的空间坐标，为灰度高斯函数的标准方差，为空间距离高斯函数的标准方差。r为两像素之间的有效距离。若超过这一距离，则认为两像素之间的相似度为0。此相似度函数认为，两像素之间的灰度值越接近，则两像素之间的相似度越大，两像素之间的距离越近则其相似度也越大。另外，文献16定义了如下两个权函数为：=exp（-） （4）= （5）上述权函数仅考虑了像素之间的

8、灰度关系，没有考虑其空间关系。（4）相似度矩阵、度矩阵及拉普拉斯矩阵图论分割算法常把所定义的最优割集准则转化为求解相似度矩阵或拉普拉斯矩阵的特征值及特征矢量问题。相似度常用W或A表示，有时也称亲和力（affinity）矩阵。将原图像中的像素从左到有单行排列并作为相似度矩阵的行序列及列序列,相似度矩阵中每一个元素的值为使用相似度函数计算所得到的值,因此若一幅图像尺寸为，则其相似度矩阵元素个数将。将相似度矩阵的每行元素相加。即得到该节点的度，以所有度值为对角元素构成的对角矩阵即为度矩阵，度矩阵常用D表示。拉普拉斯矩阵为L=DW，在图论分割算法中拉普拉斯为常用的标准矩阵。（5）势函数、Fiedler

9、矢量及谱势函数为代表某像素划分归属的指示矢量（indicator vector）。其定义为：若最终势函数中某像素对应的值为1则该像素属于集合A，若为0则属于集合B。但实际划分求解得到的结果常为0到1之间的实数值，此时可用k均值聚类等方法进一步决定像素的归属。许多图论分割算法将图划分问题转化为求解下述方程的第二小特征矢量问题： x=x （7）这里的第二小特征矢量为第二个最小特征值对应的特征矢量，它代表了最佳图划分的一个解（即势函数），把这一特征矢量称为Fiedler矢量。与特征矢量（不一定是Fiedler矢量）对应的特征值称为谱。目前，基于图论的图像分割方法的研究主要集中在以下几个方面：（1）最

10、优剪切准则的设计；（2）谱方法用于分割；（3）快速算法的设计；（4）其他图论分割方法。通过对以上图论的研究与比较，我们现在应该找出一种较好的图像分割的方法，或是得到这种方法的途径。3.1 割集准则 由式（2）的最优分割准则及式（3）的相似度函数可知，基于图论的最优分割基本原则就是使划分成的两个子图（区域）内部相似度最大子图之间的相似度最小同时应使得划分的区域尽量避免出现歪斜（即偏向小区域）分割。割集准则的好坏直接影响到分割结果的优劣。常见的割集准则有Minimum cut，Average cut，Normalize cut，Min-maxCut，Ratio cut，Foreground-cut

11、，Bcut，Isoperimetric ratio，Nested cut。表1列出了几种常见的割集准则。其中Norma1ize cut是一种较规范的形式，可以将准则转化为求解矩阵的特征矢量问题 Isoperimetric ratio是一种较新颖的图论分割算法，且运算速度较快，不需要对相似度矩阵进行重构。最优准则的实现有两种方式：一种是将最优准则转化为求解矩阵方程 ，另一种方法是使用所定义的准则直接进行图缩减。前三种准则的较详细的性能对比参见文献17。表1 几种常见准则的比较准则准则形式准则实现方式特点Minimum CutCut（A,B）=树图缩减易倾向于较小的分割Average CutAvc

12、ut（A,B）= +求方程（D-W）x=x易倾向于较大的分割Normalize CutNcut=Assoc（A,V）=求方程（D-W）x=Dx当类间重叠较大时易出现歪斜划分Min-Max CutMcut=求方程（D-W）x=Dx后置处理需要花费大量时间Ratio CutRcut（A,B）=速度较慢，可避免划分向短边偏移Isoperimetric Ratioh=表示区域S的体积,| 为区域S的边界所包含的面积= 速度较快3.2 谱方法谱方法在本质上与图论方法相一致此类算法直接对原图像构造亲和力矩阵（即相似度矩阵）W或拉普拉斯矩阵L，然后求解矩阵的特征矢量并以此为基础直接或进一步构造特征矢量指导分

13、割目前常见的几种谱分割方法见表2。其中文献l8是一种较规范、较常用的谱分割方法。表2 几种常见的谱分割方法所用方程主要求解步骤Wx=求解最大特征值对应的特征矢量用于指导分割，递归运算（D-W）x=求解方程的Fiedler矢量指导分割，递归运算求解前k个特征值对应的特征矢量并合并成矢量V，将V按行归一化等到矢量X，计算，通过Q矩阵指导分割，即=1的象素将被分为一类Nx=,其中特征矢量合并成矩阵V，将V按行矢量归一化得到X，然后使用k均值方法将X的行矢量聚类得到分割结果3.3 快速算法的设计从前面的介绍可以看到，图论分割算法用于求解特征向量的实现方法其运算耗费主要在于相似度矩阵的构造，相似度矩阵的

14、元素个数与像素尺寸有着直接的关系，因此快速算法的设计主要集中在对相似度矩阵的采样构造与稀疏处理。另外，还可以通过改变搜索策略直接进行图缩减以提高算法速度。（1） Nystrom 采样构造相似度矩阵该方法的思想是对原图像进行采样,计算n个采样像素之间的相似度矩阵A,以及n个采样像素与其余N一n个像素之间的相似度矩阵B,并使用A，B对总相似度矩阵W 以及k个特征矢量进行估计。由此原相似度矩阵写为：其中, 分别为前述矩阵,N为图像的总像素个数， 为其余（N-n）个像素之间的相似度矩阵。令A可对角化为，表示W的特征矢量的估计，则有：W的估计为：式（10）中的特征矢量还需进一步正交化才能使用。实验证明，

15、只需对原数据采样1%即可得到较高的估计质量与较好的分割效果。（2）概率采样与SVD估计文献19的方法类似于文献20，但采样方法与该文不同，在计算效率提高了10%的情况下仍得到了较好的分割结果。（3）使相似度矩阵W稀疏这种方法将W 矩阵中大部分元素值赋0，或将W 矩阵中的元素随机赋0。文献21使用4连通图，并将矩阵中的元素进行编码，使相似度矩阵的计算速度大为提高。（4）改变搜索策略前面几种方法都是基于对相似度矩阵的变换。文献22并不对相似度矩阵进行操作，而是直接进行图缩减。传统的MinCutMaxFlow算法当给定的路径长度耗尽时开始一个新的宽度优先搜索构建图像的宽度优先搜索树要耗费大量时间。文

16、献22提出一种递归的三步搜索策略：“生长（growth）”、“增加（augmentation）”、“收养（adoption）”。通过在“增加” 阶段将“tree转化为“forest”等，使得算法运算时间比传统方法大为缩减，甚至可以达到实时运算。4. 基于等周图割的图像分割基于图论的图像分割方法是近年来国际上图像分割领域的一个新的研究热点。该类方法将图像映射为带权无向图，把像素视作节点,利用最小剪切准则得到图像的最佳分割。有学者首先将最小割集准则用于图像分割，很快这个方法就被转化为求Laplacian矩阵的Fieldler矢量问题。此后许多学者提出了不同的最优图划分准则用于图像分割,较典型的有r

17、atio cut准则,等周割集（Isoperimetric cut）准则等。谱图分割提供了一种良好的图像分割方法。我们借助小等周常数划分的思想，将图像分割问题转化为线性系统问题，而不是特征向量问题。利用这种方法旨在获得高质量的图像分割效果，并提高速度和改进稳定性。4.1 等周问题 等周割集准则的提出源自典型的等周问题,即找出一个包含最大面积的最小周长的边界。定义一个集合U的等周常数为: h= （8）S U为集合U中的一个区域,表示区域S的体积,| 为区域S的边界所包含的面积。由上述定义,等周常数h为所有可能的集合S的面积与体积之比的下确界。对一个紧致集合,其体积存在, ,而对非紧致集合有 。我

18、们在这里指出找到一个同时具有最大面积（也就是说，上确值）和最小周长（也就是说, 下确值）的区域，直观的说，就是一个好的图像分割了。早先应用到图像分割上的谱图分割已经产生了成功的算法。一般来说,以前的方法都是依据谱图理论上的最大切/最小割算法。虽然等周准则在直观上是类似于以前的谱图理论，但表面算法上细小的差别还是将图像分割问题转化为线性系统问题，而不是特征向量问题。线性系统问题是合乎需要的， 因为它改进了速度和稳定性。此外，谱图分割还会出现一些“意外情况”。最小割算法易倾向与较小的分割，从而带来问题。而等周算法倾向与大量的分割，从而可以很好的避免这个问题。4.2 等周算法（1）定义一个带权无向图

19、G = （V, E） ,其节点v V,边e E V V,分割节点与的边定义为 ,权值为w （ ） ,节点的度为: = ， E （9）对于一个有限节点的图来讲,等周常数变为:= （10）其中S V, 。集合S的边定义为, = | i S, j , 为S的补集。则集合S的面积为:|= （11）集合S的体积为：=， （12）对有限节点式（10）的下确界应为最小值。定义势函数矢量X （13）以及一个矩阵L （Lap lacian矩阵） ,其元素为： | =LX （15） =d （16）d为节点度矢量。用r表示元素值全为1的列矢量,则在满足约束=d下最大化S的体积可以通过令:d =d （17）来实现。由

20、此式（10）的等周常数可写为:= （18）上式约束最优化可以引入Lagrange乘子并将X松弛到实数,然后最小化如下代价函数实现:Q （X） = LX -（d -d） （19）=2LX-d （20）2LX=d （21）求解X时标量2及可以省去。但由矩阵L的定义看出,L 的行和与列和都是0, 使得（21） 式的求解需要引入新的约束。注意到图G中c个不相连的子图实际上对应于矩阵L的秩为n - c。因此可将某先验节点放入区域,此操作对应于从L中移除第g行第g列得到剩余矩阵,且对应于移除X, d的第g行,得到,。因此求解势函数X可转化为求解:= （22）得到X0 即为指导分割的势函数矢量。得到势函数后

21、,可通过设定阈值或k均值聚类得到最终二值分割结果。（2）物理分析：等式（21）最早出现在电路理论中，当时在确定电流源的无规则电路中解决电势问题。在电路中将一个节点接地（例如，使该节点电势为0），决定保持电势就需要等式13这个解决方案。因此，我们提到节点，我们先设定作为接地点。同样的对于的解决方案来自（22）。在节点，我们可能提到如的电压。有了上面所阐述的符号，3个对接地的基本电路方程式就可以给出了：y=f （23）=y （24）p= （25）对一个电流分支向量y，电流源f和电势差（电压）p。注意在当前公式中没有电压源。以上3个方程可以组合成一个线形系统：C=X=f， （26）即 =L18。我们

22、发现电路和图在这方面有很深的联系。这一事实暗示了在图上对这种算法的分析。电压降计算出的每一个节点都存在这样一种现象：很多可预料的自由电子从节点向地移动。比如说它可能从节点出发去。基于这种理论，等周分割就是将图分割成拥有最小等周比率的图。（3）算法细节1）算法摘要:基于等周图割的图像分割可以用以下步骤来描述：1利用（27）式求所有边的权并构造L矩阵2选择最大度的节点作为领域节点，并通过删除对应的列/行来确定L0和d0。3根据公式=求解出。4在对应最低等周率所确定分割的值的地方设置势能x的阈值5在每个分割上连续迭代，直到子分割的等周率比停止参数大2）找出每条边的权：为了应用等周算法来分割一张图，这

23、幅图的值必须经由每条边的权来编码。 我们使用标准的求权公式： （27）其中代表一个自由参数且代表了节点的参数。注意到可以用这两点之间的几何距离的矢量值表示。4.3 等周割集应用举例（1）等周割集准则用于直方图聚类等周割集准则用于直方图聚类实际上是使用该准则对一维直方图数据进行聚类。由直方图进行二值分割实际上是对直方图数据进行二值聚类,直方图的二值划分灰度即为分割阈值。使用等周割集准则进行直方图聚类的算法步骤如下:1） 由式计算直方图数据的相似度。2） 由式（9）及（14）计算度矩阵d及Laplacian矩阵L 。3） 选择最大的节点,将d及L中与该节点对应的行和列删除,得到新矩阵, 。4） 由

24、式=求解势函数。5） 对 进行二值划分,由式（18） 计算等周比值h ,并判断是否大于给定的终止条件。6） 对直方图数据进一步迭代划分,直到满足终止条件。此时的二值划分点即为分割阈值。其中,对的二值划分通过k均值聚类进行,相似度函数的计算可以使用全连通图（所有直方图数据两两计算相似度） ,也可以使用如4连通、8连通图来进行计算。5. 编程语言的选择 题目的要求是用C+或者是MATLAB来实现这个算法，经过比较，虽然对C+可能要更熟悉一点，但是在对题目的把握上，尤其是考虑到程序的编写上，经过分析与老师的指导，认识到使用MATLAB与C+各自的优缺点后，决定使用MATLAB。5.1 MATLAB简

25、介 MATLAB是一种功能十分强大，运算效率很高的数字工具软件，全称是Matrix Laboratory。起初它是一种专门用于矩阵运算的软件，经过多年的发展，MATLAB已经发展成为一种功能强大的软件，几乎可以解决科学计算中的任何问题。总之，矩阵和数组是MATLAB的核心，因为MATLAB中的所有数据都是以数组的表示和储存的。除了常用的矩阵代数运算值外，MATLAB还提供了非常广泛和灵活的方式处理数据集的数组运算功能。另外，MATLAB除了对矩阵提供了强大的处理能力之外，还具有一种与其他高级语言相似的编程特性。同时它还可以与Fortran和C语言混合编程，进一步扩展了其功能。在图形可视化方面，

26、MATLAB提供了图形用户界面（GUI），使得用户可以进行可视化编程。因此，MATLAB就把数据结构、编程特性以及图形用户界面完美地结合到一起。5.2 MATLAB的主要应用 1数学和计算 2算法开发 3数据获取 4建模、模拟和原型设计 5数据分析、研究和可视化 6科学和工程图形 7应用开发，包括图像用户界面构建基于此，选用MATLAB已经是很明显的了。5.3 MATLAB的优点（1）MATLAB使用方便MATLAB允许用户以数学形式的语言编写程序，用户在命令窗口中输入命令即可直接得出结果，这比C+、Fortran和Basic等等该机语言都要方便的多。而且它是用C语言开发的，其流程控制语句与C

27、语言中的相应语句几乎一致。这给使用上带来了方便，使我能较快的适应与使用MATLAB这门语言。（2）内部函数非常丰富MATLAB的内部函数提供了相当丰富的函数，这些函数解决许多基本问题，如矩阵的输入。在其它语言中（比如C语言中），要输入一个矩阵，先要编写一个矩阵的子函数，而MATLAB语言则提供了一个人机交互的数学系统环境，该系统的基本数据结构是矩阵，在生成矩阵对象时，不要求做明确的维数说明。与利用C语言或 Fortran等等高级语言编写数值计算的程序相比，利用MATLAB可以节省大量的编程时间。这就给用户节省了很多的时间，使用户可以把自己的精力放到创造方面，而把繁琐的问题交给内部函数来解决。除了这些数量巨大的基本内部函数外，MATLAB还有为数不少的工具箱。这些工具箱用于解决某些领域的复杂问题。（3