（应用数学专业论文）改进的模糊连通度图像分割算法.pdf

中文摘要 摘要 图像分割是数字图像处理过程中的重要环节，分割的效果对其后的目标识别、 图像分析、图像理解等高级处理阶段产生着直接的影响。模糊连通图像分割算法 是一个重要的图像分割方法，隶属于区域分割的范畴。它的基本思想是：利用在 图像空域上定义的一种模糊关系模糊连通度，从全局的角度来描述两个像素 点的相关性和区域的连通性；应用动态规划算法，计算图像中某一种子像素点到 其它所有像素点的模糊连通度；通过特定阈值对模糊连通度做出判决，得到目标 区域，从而得到整幅图像关于背景区域的连通目标图。 模糊连通度图像分割算法的关键步骤之一，是计算所有像素间的模糊连通度， 通常应用动态规划算法来实施，其效率直接影响着分割算法的复杂程度。针对这 一问题，本文提出了一种改进的模糊连通度图像分割算法。该算法首先对像素问 的相似关系进行阈值处理，然后应用图论中的可达矩阵和生成树方法求出连通区 域，在保证分割质量的前提下，有效地降低了算法的复杂度，提高了算法的运行 速度。 作为新算法的扩展，本文又将该算法由单目标区域分割推广到了多目标区域 分割，并且针对多目标区域分割存在的问题提出了一种自动选择种子点的方法。 其主要思想是：用枚举法顺次找出种子点，并应用新算法分割出目标区域。由于 枚举法的复杂性比较高，我们通过建立禁忌列表的方式，把每次分割出的目标区 域中的点放在列表中，以便减少下一步迭代的工作量，从而大大降低了算法复杂 性。实验证明，该算法能够从复杂背景下精确分割出多目标区域。 关键词：模糊连通度：图像分割；可达矩阵；生成树；禁忌搜索 英文摘要 i m p r o v e df u z z yc o n n e c t e di m a g es e g m e n t a t i o na l g o r i t h m a b s t r a c t i m a g es e g m e n t a t i o ni st h ep r o b l e m o ff i n d i n gt h eh o m o g e n e o u sr e g i o n s ( s e g m e n t s ) i na ni m a g e ，i ti si m p o r t a n ti ni m a g ep r o c e s s i n g t h en o t i o no ff u z z ye o n n e c t e d n e s s c a p t u r e st h ei d e ao f ”h a n g i n g t o g e t h e r n e s s ”o fi m a g ee l e m e n t si na f to b j e c tb ya s s i g n i n g as t r e n g t ho fe o n n e c t e d n e s st oe v e r yp o s s i b l ep a t hb e t w e e ne v e r yp o s s i b l ep a i ro fi m a g e e l e m e n t s t h i sc o n c e p tl e a d st op o w e r f u l i m a g es e g m e n t a t i o na l g o r i t h m sb a s e do n d y n a m i cp r o g r a m m i n gw h o s ee f f e c t i v e n e s sh a sb e e nd e m o n s t r a t e do nt h o u s a n d so f i m a g e s b a s e do ni t ，t h i sp a p e rp r e s e n t st w on e wa l g o r i t h m sw h i c ha l eb o t hs i m p l e ra n d f a s t e rt h a ni t t h em a i ni d e a so ft h ea l g o r i t h m sa l et ou s et h ep r e p r o c e s s o ra n dt h e n c o m p n t et h ec o n n e c t i v eo b j e c t s h e r et h ep r e p r o c e s s o rb yu s i n gt h et h r e s h o l dj u d g et h e a f f i n i t i e sa n dd i s c o n n e c tt h ea f f i n i t i e sw h i c hl o w e rt h a nt h r e s h o l d t h e nu s e st h e r e a c h a b i l i t ym a t r i xa l g o r i t h mo rs p a n n i n gt r e ea l g o r i t h m ( h e r et h el a t t e ri sb e t t e rt h a n t h ef o r m e ra l g o r i t h m ) t of i n dt h ec o n n e c t i v er e g i o n t h e yh a v eb e e nt e s t e di nm a n y m e d i c a lg r a yi m a g e s ，a l le x p e r i m e n t sw e r eq u a l i t a t i v e l yd e m o n s t r a t e dt h ee f f e c t i v e n e s s o ft h e s em e t h o d s i nr e c e n ty e a r s ，h o wt of i n dt h er e f e r e n c es e e d sa u t o m a t i c a l l yf o rm u l t i p l eo b j e c t s i m a g es e g m e n t a t i o n a n ds p e e du pt h ep r o c e s so f l a r g ei m a g e ss e g m e n t a t i o na s i m p o r t a n ti s s u e st ou s i nt h i sw o r kw ep r e s e n tan o v e lt a b u s e a r c h b a s e da p p r o a c ht o c h o o s et h er e f e r e n c es e e d sa d a p t i v e l ya n du s eas p a n n i n gt r e em e t h o df o rf u z z yo b j e c t e x t r a c t i o ni ni m a g es e g m e n t a t i o n t h i sp r o p o s e da l g o r i t h mw o u l db em o r ep r a c t i c a la n d w i t hal o w e rc o m p u t a t i o n a lc o m p l e x i t yt h a nr e l a t i v ef u z z yc o n n e c t e d n e s sm u l t i p l e i m a g es e g m e n t a t i o n t h er e s u l t so b t a i n e di nr e a li m a g e sc o n f i r mt h ev a l i d i t yo ft h e p r o p o s e da p p r o a c h k e yw o r d s ：f u z z yc o n n e c t e d n e s s ；i m a g es e g m e n t a t i o n ：r e a c h a b i l i t ym a t r i x ； s p a n n i n gt r e e ；t a b us e a r c h 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：馥进鲍搓塑适适廑图傻坌割簋洼：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：獗畸乙矗fj 纠年弓月扭日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于： 保密口 不保密口( 请在以上方框内打“”) 论文作者签名：碾帕i i 新签名：稚经 f 1 期：0 7 年3 月0 s 日 改进的模糊连通度图像分割算法 引言 在图像处理过程中，人们往往对图像中的某个部分感兴趣。图像分割就是把图 像分成各具特性的区域，并提取出感兴趣目标的技术。它是由图像处理到图像分 析的关键步骤，也是一种基本的计算机视觉技术。迄今为止，人们已经提出了大 量的图像分割算法，大致可分为三类：阈值分割；边缘检测；区域提取。区域提 取是基于区域特性的分割技术，最具代表性的是区域增长算法。这个算法利用图 像的整体连通性对图像进行分割，在应用中需要解决三个问题：( 1 ) 选择或确定一 组能j 下确代表所选区域的种子像素；( 2 ) 确定在生长过程中能将相邻像素包括进来 的准则；f 3 ) $ 1 j 定生长停止的条件或规则。 由于传统的区域增长算法难以确定停止条件，因而人们提出了一种新的区域增 长算法基于模糊连通度的图像分割算法。模糊连通度是定义在图像空域上的 一种模糊关系，其大小由局部模糊连通紧密程度来决定，它可以从全局的角度来 描述像素点之间的相关性和区域的连通性。在进行图像分割时，应用动态规划算 法来计算图像中某一种子点到其它所有像素点的模糊连通度，利用分割判决式作 为算法的终止条件，从而得到整幅图像关于目标背景的连通度图。 模糊连通度图像分割算法，目的是要分割出连通的目标区域，并且要求这个 区域里的像素的模糊连通度满足一定的要求。由模糊连通度的定义，路径的连通 度为路径上相邻元素的相似关系的最小值，模糊连通度为像素间所有路径连通度 的最大值。本文提出的改进算法，主要思想是：首先对图像进行预处理，采用分 割判决式把不满足条件的像素的相似关系切断：然后对像素的关系矩阵应用图论 中求连通分支的方法得到所要分割的连通的目标区域。这里求连通分支的方法有 两种，一种是应用逐次平方的方法求可达矩阵；另一种是应用生成树方法，由种 子点丌始用广度优先遍历的方法生成一个连通图，从而得到目标区域。通过理论 分析可知，这两种方法都可以使模糊连通度图像分割算法的时问复杂度大大降低。 同时实验过程证明了该算法在保持分割精度的i j 提下提高了分割速度。 引言 在图像处理过程中，不仅简单的从背景区域分割出一个目标区域，通常还会 要求从背景区域分割出多个目标区域，这样仅用模糊连通度图像分割算法就难以 解决问题。为此，p u n a mk 和j a y a r a mku d u p a 等人继模糊连通度图像分割算法 后，又提出了相对模糊连通度图像分割算法，并应用于多目标区域分割，实现了 复杂背景下多目标的图像分割。然而相对模糊连通度多目标区域分割算法存在一 个固有的缺陷，就是在选择种子点时要依赖于人工或是外置设备，这对算法的分 割范围和精确性有着一定的影响。针对这一问题，本文又提出了一种新算法，一 方面通过建立禁忌列表实现自动选取种子点，一方面应用生成树方法生成目标区 域。这样不仅解决了选点问题，而且还减少了算法的时l 日j 复杂性，提高了运行速 度。 改进的模糊迎通度图像分割算法 第1 章图像分割概述 1 1 图像分割研究现状及发展 在对图像的研究和应用中，人们往往只对图像中的某些部分感兴趣。这些部 分称之为目标或者前景，其它部分称之为背景。目标般对应于图像中特定的， 具有某种独特性质的区域。为了辨识和分析目标，就需要将有关区域提取出来， 在此基础上才能对目标进一步处理，如特征提取，识别等【1 - ：3 1 。 图像分割是把图像中互不相交，具有特殊涵义的区域区分离出来。每个区域 内像素的属性满足一定的一致性，如灰度值1 4 ，5 】相近或纹理【5 罐】特征相似。图像分割 是图像分析的关键步骤，是一种低层次的计算机视觉技术。计算机视觉中的图像 理解包括目标检测，特征提取和模式识另4 等，都依赖于图像分割的质量。尽管已 经有了许多分割方法，但是到目前为止还不存在一种通用的方法，同时也没有一 个判断分割质量的标准，因为它与人的主观认识有密切联系，被认为是计算机视 觉处理中的一个瓶颈。 分析图像分害0 的过程，我们可以将图像分割划为两个子过程：( 1 ) 目标的识别 定位过程；( 2 ) 目标的提取过程。两部分缺一不可。图像分割一般有三种方式i9 ”l ： 一是阈值分割方法，它借助于图像的整体信息，如直方图1 1 6 - 2 0 l 来决定闽值的选取； 二是边缘提取方法，它主要借助于各种边界算子对图像进行处理来得到边界，进 而获得用户感兴趣的区域，关键是如何从得到的分散的边界组成闭合的边界，从 而得到待分割的区域；三是区域增长方法，最简单的形式是从一个种子点出发， 通过寻找与输入种子点相似属性的像素来得到一块区域。 1 2 传统的区域增长算法 正如它的名字所暗示的，区域增长算法1 2 1 御是一种根据事前定义的准则将像素 或子区域聚合成更大区域的过程，基本方法是以一组“种子”点开始将与种子性 质相似( 诸如灰度级或颜色的特定范围) 的相邻像素点附加到生长区域的每个种子 e 。 第1 章图像分害0 概述 通常根据所解决问题的性质而选择一个或多个起点。当一个先验信息有效时， 这一过程将对每个像素计算相同的特性集，最终，这个特性集在生长过程中将像 素归属某个区域。如果这些计算的结果呈现了不同簇的值，则那些由于自身的性 质而处在这些簇中心附近的像素可以作为种子。 相似性准则的选择不仅取决于面对的问题，还取决于有效图像数据的类型。例 如，对地观测卫星成像非常依赖颜色的使用。如果没有彩色图像本身固有的可用 信息，这个问题会变的非常棘手，甚至无法解决。如果图像是单色的，必须用一 组基于狄度级和空间性质的描绘( 如矩或纹理) 对区域进行分析。 如果有关连通性和相邻性的信息没有用于区域生长过程，则单个的描绘会产生 错误的结果。例如，仅用3 个不同的灰度级值将任意一个范围内的像素可视化。 具有相同灰度级的像素组成一个“区域”，而不考虑它们的连通性，则会生成一 个对于我们讨论的内容来讲毫无意义的分割结果。 区域生长的另一个问题是用公式描述一个终止规则。基本上，在没有像素满足 加入某个区域的条件时，区域生长会停止。但常用的灰度级，纹理和颜色等准则 都是局部性质，没有考虑到区域增长的“历史”。为增强区域生长算法的处理能 力，其准则需利用待选像素和已加入生长区的像素问的大小，相似性等概念( 比如 待选像素的灰度级和生长区域的平均灰度级之间的比较) ，以及生长区域的形状等 全局性质。在这种情况下，常需对分割结果建立一定的模型或辅以一定的先验知 识。 1 3 模糊信息在图像分割中的应用 信息，从广义来说是事务运动的状态和存在方式的反映，通过一定的物质和 能量的形式表现出来，它可被人类的感官直接或借助于工具而感知。s h a n n o n 曾指 出，信息的本质在于消除或减少不确定性。但由于s h a n n o n 信息论取得的巨大成 就的影响，过去人们往往把不确定性看成单纯的随机性。诚然，随机性是重要的 一种不确定性，但不是唯一的不确定性。在随机不确定性中，研究的集合一般具 有明确的外延，也就是说一个对象是否符合某一个概念，必须是非此即彼，不确 改进的模糊连通度图像分割算法 定性仅表现在这些对象代表的事件是否发生这一问题上，这里主要起作用的是随 机性，可用概率论，随机过程和数理统计工具进行研究。但是，在很多问题中， 所研究的集合之间往往还存在外延不明确性，即集合之闻具有“亦此亦彼”的中 介过渡性质，这样就导致了对对象划分的不确定性。特别是概念用人的自然语言 表达时，更是如此。这种不确定性是与随机性不同的一种不确定性，称为模糊不 确定性。1 9 6 5 年，著名控制论专家l a z a d e h 首先提出了模糊集的概念例，创立 了模糊数学，进而提供了一套严格的数学方法，来描述这种带有模糊不确定性的 现象和事物。 模糊信息处理就是利用模糊数学这一工具，来处理带有模糊不确定性的信息。 研究对象之所以带有模糊性，一般是由如下原因造成的： ( 1 ) 在我们日常生活中，很多对象本身就具有模糊性，即具有一系列中h j 过渡 状态。这些对象用经典的明晰集合来刻画是不适合的，只能用模糊集合来刻画。 经典的集合论中隐含有一个假设，即一个研究对象( 元素) ，或者完全具有某种性质， 或者完全不具有某种性质，既或者完全属于某个集合，或者完全不属于某个集合。 这样就忽略了对象在量上具有这种性质的程度。例如自然界中存在的元素有金属 与非金属两大类，但是有些元素既具有金属的一部分特征，又具有非金属的一部 分特征，这就造成了模糊性。 ( 2 ) 人们在认识事物时，由于现阶段技术能力和手段有限，或受环境条件及各 种因素的影响，造成人们对研究对象的认识不充分，获取的信息不足而对事物认 识产生模糊性。某些信息处理问题，特别是智能信息处理问题，由于研究的对象 过于复杂，用现有的精确数学方法处理起来很困难。 在图像分割这样一个视觉任务中，上述两种模糊性皆存在i 刎目标在投影成图 像过程中，由于各种因素的影响，造成了目标物的像与干扰( 或其他物的像) 具有某 种程度相似性。另外，由于成像期间空间分辨率及各种光照条件的影响，使目标 物的像的边界与背景之间像素灰度具有中问过渡的性质，使目标物的边界具有模 糊性，这种模糊性有时可以强到使目标像的某一个部分与背景之| 日j 几乎融为一体 的程度。另一方面，图像分割是一个信息不足的不适定问题，要解决这类问题， 第1 章图像分割概述 需要有一定的先验知识，由于问题的复杂性，不可能完全搞清楚造成这种信息不 足的全部原因，因此，对图像具有的这种先验知识在很多情况下是无法用经典的 精确数学语言来描述的，但却往往很容易用人的自然语言总结，描述出来。而人 类的自然语言往往是不精确的和带有模糊性的。 综上对图像分割这样一个重要的视觉任务，研究用模糊信息处理技术来解决问 题有内在的必然性和合理性。模糊信息处理技术，由于其自身的灵活，高效和稳 健性，以及处理问题的简洁性，对于特征和知识表示都有很重要的作用。对人的 思维机制的研究表明，“人脑的语言不是数学语言”，大量运用模糊概念乃是人 类思维过程的重要特点。因此，在视觉研究中，特别是在图像分割中引入模糊信 息处理技术，对于提高计算机视觉系统的实时性，自动化，智能化水平都将有很 大的促进作用。 改进的模糊连通度崮像分割算法 第2 章基于模糊连通度图像分割概述 2 1 基于模糊连通度图像分割 自从z a d e h 于1 9 6 5 年提出模糊集概念后，在1 9 7 9 年r o s e n f e l d 等人首次把模 糊连通度引入到图像处理中。1 9 9 6 年由u d u p a 等人提出了一种新的区域增长算法 基于模糊连通度图像分割算法，该算法通过比较图像中所有点与目标和背景 种子点的连通度大小来进行目标和背景的判决。近些年很多学者致力于该领域的 研究1 2 8 。o l ，并取得了大量的成果，使得这个领域有了更好的发展。 2 1 1 模糊连通度图像分割的基本知识 1 模糊子集，关系函数，模糊关系 首先来了解模糊子集的定义【3 l l 。肋任意的一个参考集，一个模糊子集，4 是x 中 有序对定义为 爿= 0 ，脚o ) ) k 册，“：j ：一【o ，1 1( 2 1 ) 其中砌是x 中爿的隶属函数。 肚的二元模糊关系定义为 p = ( g ，y ) ，脚缸，y ) ) l x ，y 研，铀：z x 【o 1 1 ( 2 2 ) 对任意的x 上模糊关系p ，有： 反射条件，v x 五，础，z ) = 1( 2 3 ) 对称条件，v x ，) ，墨眦，y ) = 胁，功 ( 2 4 ) 传递条件，坛，z 墨，似，z ) = m a xy e x 【m i n z a ( x ，y ) ，础，z ) 】 ( 2 5 ) p 称为相似关系，如果它满足反射条件、对称条件。 2 模糊邻接和模糊数字空间 是一个t 维欧氏空间，用忍个互相垂赢的或平行的超平面族把分成一些 单位超立方体。在每个超立方体的中心都有一个整数坐标系。这个超立方体称为 像素空问( 是空间元素的简称) 。当n = 2 时称为像素，n = 3 时称为体素。设这些超立 方体的中心坐标为1 元的整数，则它对应于z ，中的一个点。若矽上的模糊关系口 是自反的，对称的，则称为模糊宅f b j 元素的邻近关系【3 2 l 。它描述了两个空间元素 第2 章基丁模糊连通度图像分割概述 的位置邻近关系。一般要求隶属函数地( c ，d ) 是一个非增函数，其中i k 一训是c ，d 的距离，i | | l 表示硝中的任意的l 2 范数。这里用, u a 来表示邻接函数。对任意的空 间元素c ，d ： 在二维空间， 蹦删) 一仨嚣“彘是四邻接 ( 2 - 6 ) 在三维空间， 小一仨巍扣以豌川是六邻接 ( 2 7 ) ( 矿，口) 称为模糊数字空间1 3 2 】。 3 场和隶属场 设s = ( c ，) 是数字空日j ( 矿，口) 上的场【3 2 1 ，这里c = c i 也= q = 白，6 z ： ，z ：是 正的整数元组集，是一个函数，其定义域为c ，值域是整数集陋，明。该函数反映 了空问元素的某种属性，如图像上像素点的亮度值或纹理结构属性。 如果，的值域是【o ，1 1 ，则称s 为( 才，d ) 上的隶属度场。 4 模糊空间元素相似关系： 令s = ( c 厂) 是( 罗，口) 上的一个隶属度场。c 中任意的模糊关系k 如果是自反，对 称的，则称为s 上模糊空间元素的相似度 3 3 - 3 5 】。实际上，一般取k 的隶属函数鲰( c ， 力与弛) ，柳，c ，d 本身有关。因此c ，d 相似关系强度与空间远近，亮度相似程 度，以及场域的实际位置有关。我们通常用以下形式来表示肌： 肌( c ，印= w 喀l 皈c ) ，) + w 塔2 皈c ) ，艄)( 2 8 ) 这里舶，职是高斯函数分别用掣，掣表示，w 。，耽是非负 权值。9 1 是一个高斯函数，表示亮度的均值和变化与定义的目标区域亮度的均值 和变化有关，即c ，d 的亮度与区域期望的亮度值越相近时，它们的相似程度越大。 9 2 是0 均值，表示c ，d 亮度均一性程度，即c ，d 所属的区域的亮度越均匀，它们 改进的模糊连通度图像分割算法 的成分的相似程度越大。一般相似关系应该由均匀相似，目标特征相似组成，这 里用g l ，9 2 分别表示这两个关系。 目标特征相似没有把握住均匀路径的概念。具体来说，考虑在同一个目标区域 但是距离很远的两个空间元素c ，d 。假设有一个背景亮度缓慢变化的结构，例如 m r 图像决定的磁力场的不均匀性，这样空间元素c ，d 虽然在同一个目标区域但 是它们可能有着不同的亮度。然而，我们能够在这个场域中找到一条从c 到d 的 路径( 是邻接元素的序列) 并且在这条路径中每对元素( c - ，d 1 ) 的亮度都很相似。同 样，均匀相似也不能充分的把握整体一致的目杯区域亮度特征。假设从c 到d 的 路径亮度变化的很缓慢，然而路径可能通过多个目标区域。因此，讨论般的模 糊空问元素相似关系应该同时考虑均匀相似和目标特征相似。通常用下面的形式 来表示m p 。( c ，d ) 一。( c ，d ) 占( 如( c ，d ) ，肛( c ，d ) ) ( 2 9 ) 这里脚和阿分别为图像中感兴趣物体的均匀分量和特征分量。和，是c 上 的模糊关系。下面讨论g ，脚，所的函数形式。 1 ，g 的值域是【o ，1 】。 2 ，g 对于已给定的p “或是聍) ，当膨( 或是d 增加时肌是单调非增的。 下面给出了一些满足条件的g 的倪子。 触= = “y ( 2 1 0 ) ，“= ，l 南( 2 1 1 ) 脓：加一， ( 2 1 2 ) 肚2 心( 坳+ 一) 彬办 ( 2 1 3 ) 以一心( ( 1 一m i n ( 心，三一) ) 一+ m i n ( 如，三一) 心) ( 2 1 4 ) 对于均匀相似，假设场s 上的两个空间元素c ，d 间的均匀性( 相当非均匀) 用瞰) ，( 回l 表示。h 名应该满足如下要求： ( 1 ) h 0 的值域是【o ，1 】，且h “0 ) = 1 ； 第2 章基丁模糊连通度图像分割概述 ( 2 ) 当图像场不同时，不同的目标区域应有不同程度的均匀性。例如，在高均 匀性的图像中，目标区域上有相邻的像素c 和d ；而在低均匀性的图像中，目标区 域上有相邻的像素u 和v ；如果非均匀性描述= i f ) ，( 回i = l t ( u ) - ，( v ) l ，那么w g f ) ， 艄) 应比矸0 ( ) ，m ) ) 的值小； ( 3 ) 矸0 是单调非增函数。 在模糊集理论中，有很多隶属函数能够表示模糊假设并非常小。我们已经 测试过了三个比较典型的矸0 函数。如图2 1 所示。其中t 沪机+ 0 ，m v 和s y 分别 为石的均值和方差，本文所有下标l f ，的参数都表示与均匀分量有关，相应的下标 为，表示与特征分量有关的参数。各个参数可通过在目标区域上选择- d , 块具有 代表性的区域来计算得到。 改进的模糊连通度图像分割算法 f 1 ， = 【o ：= 0 x 玉， 膏 l 0 工a h + 等。口v s j 口坤+ - - a l - , 。 仉 工 4 w - h 0 0 ) = f2 2 。k v o 图2 1 耽的函数形式 f i g2 1t h ef u c t i o no fh 0 第2 章基丁模糊连通度图像分割概述 i + 孙知卅 仅) ； 工1 兰 o 工 m p a 。， i 。 m 。一棵- 蔓 蔓m 。+ 拉。 0 ， 用。- i - a 。 置 o j 0 ( 2 2 2 ) 第2 章基于模糊连通度图像分割概述 g 上的每个像素c 都有一个值，表示c 与它相邻像素的相似关系的平均值，这里 的相邻像素点是由2 6 定义的。事实上，在对不同关系函数k 的交互式实验中，我 们发现只是针对- d , 部分的s 会方便去定义k 相似关系图像场。对应前面定义的 邻接关系a ，徘) 表示c 与它直接的邻居下边或是右边( 假设正坐标方向是指从上到 下和从左到右) 相似关系的平均值。在实际分割中，相似关系是定义在与n 维图像 场所有邻节点上的。 选择参数的另一个方法就是通过实践。在执行过程中，首先对所给的图像场 的一部分，用画笔刻画出目标区域和背景区域。其中所画的目标区域和背景区域 的亮度均值( m o ，慨) 和标准方差o o ，s 6 ) 是可计算的。相似的，对于不均匀目标区域 通过计算算出所有可能的像素对( c ，力的不同的亮度i 触) ，i 的均值( “) 和方差 o ) ，其中c d ，并且胁( c ，力 0 。这罩用脚，纷，矽，膨，这些参数的值来估计参 数，公式如下： 心：- m + f 吼，a 坤置0 ，a 坤- m + f 盯，置m + t a h ( 2 2 3 ) ，：m o 暑m 矿a 。i t 卯，a 抽io ，a 2 。l f l ，k o 暑f ( l ( 2 2 4 ) m b m 6 ，a 一f i 吒，a ”一0 ；a 2 6 一f ( 矗，k b f i 这里，t 是一个介于2 和3 中的一个数。( 它的基本上是满足正态分布) 。 2 1 2 基于模糊连通度图像分割算法 基于模糊连通度的图像分割算法 4 0 , 4 1 1 ，简称为k f o e 。其算法步骤为： ( 1 ) 选定一幅图像i ，由用户制定图像中目标0 和背景b 的种子点岛和s b ，并 估计各个参数的值： ( 2 ) 通过动态规划的方法计算目标0 和背景b 的连通度图，采用式( 2 2 0 ) 做出 分割的判决： ( 3 ) 输出所得的目标区域o 。 如果计算图像中每个像素点的模糊连通度的全局最优值，则计算量太大，为 简化运算，一般采用基于动态规划的方法，即可得到满意的结果。算法结构如下： 改进的模糊连通度图像分割算法 输入：图像场，模糊相似关系k ，j 中目标d 和背景且的种子点品和s b ，判决 函数，7 。 输出：，中的目标区域d 。 辅助数据结构：，中以s o 为种子点的目标模糊连通度图像场c 。= 以，k ) ；以s b 为种子点的背景模糊连通度图像场c 矗= 以历) ；包含待处理像素的队列q 。 b e g i n 1 o r x d ，6 d 0 2 ，o ra l l c e l ，i f c = x ，使丘( c ) - 1 ；e l s e 丘( c ) = oa 3 将所有满足条件：础，c ) o 且o ，c ) k c z 2 的像素存入0 4 w h i l e ( q ! = n u l l ) s 从q 中移走一个像素c ； 6 找5 m a x ( c ，妒, v m m i n ( 允p ) ，肿，d ) ) ) ； 1 毽 硝e 蛾t h e n 8 使丘_ ，眦x ； 9 将满足以( c ，e 卜丘0 ) 的8 点添入q ，其中( c ，e ) e n m ； e n d i f ； e n d w h i l e ； e n d f o r ； 1 0 ，d ra l lc ，d o 1 1 f , k c ) ot h e n 判断c q ； 1 2 p 厶p 判断c e b ； e n d f o r ； 1 3 输出目标区域d ； 2 2 基于尺度的模糊连通度图像分割算法 本节沿用2 1 1 节中介绍的模糊集理论来定义模糊连通关系，对于模糊数字 空间( z 2 ，口) 上的图像场，中任意两点且和翩间的模糊连通度仍用式( 2 1 9 ) 来定义， 第2 章基丁模糊连通度图像分割概述 局部模糊连通关系胁仍可由式( 2 8 ) 来定义。为了提高算法的抗噪性和稳定性，我 们引入“尺度”的概念【2 5 1 。从而对儿的均匀性分量和特征分量采取与2 1 1 节中 略有不同的策略来度量。本节采用基于一定尺度范围内的特征来定义这两个分量。 假设图像场，中任意两像素p ，扔之问的第k 条路径上的两相邻像素训，p k t + 1 ) 坼c z 2 。首先，定义以c i 以。和d = 别“为中心，半径为r ( ) 的圆风水) 和风脚， 其中，最“c ) = p ，i | c - e h = m i n r ( c ) ，( 纠 ，( ) 可使用某种自适应的方法来计算。 然后，通过圆面积范围内像素的梯度和强度特征来定义这两个分量。 均匀性的分量表达式为： ，( c ，d ) i1一id：+：(：c,：d=：)：-i丽d-(c,d)l ( 2 2 5 ) 2 衄。“) 咿叫 其中， d + ( c 。募 1 一( 配f ) ) k ( h i ) ( 2 2 6 ： 暨g ! ， d 一( c ，d ) 。未 1 一( 芘) ) 虬扯p d ( 2 2 7 ) ： 恕g ! ， 并有， 讹小舻八以嚣 。一，f ( e ) 一厂0 ) ， 如果 吼，卜b 其它 ，一( e p 0 ， f ( e ) - ，0 co ， 为了简化运算，一般采用基于动态规划的搜索方法，可得到满意的分割结果。 该基于尺度的相对模糊连通算法与2 1 2 节中的基于相对模糊连通度的分割算法 的算法步骤、结构均相同。基于尺度的相对模糊连通图像交互式分割算法在抗噪 声性能方面优于非尺度的算法，而在速度方面却有明显的劣势。 改进的模糊连通度图像分割算法 第3 章改进的模糊连通度图像分割方法 前面给出了模糊连通度图像分割算法，并详细的描述了其过程。在算法中对 于给定的一个特殊的阈值0 ，分割的目标区域是由每对元素问的模糊连通度都大于 0 的像素点组成的。在这一过程中需要计算每对元素的模糊连通度，这个组合问题 非常的复杂。针对这一问题，本文提出了一种改进的算法，能够快速分割出所要 求的图像。 算法主要分为两部分，首先是对待分割的图像场进行预处理，主要是应用 ( 2 1 2 ) 中提到的模糊局目杯区域的定义，由定理2 3 ，所分割出的目标区域满足 u k ( o ，c ) = 口，所以这里只需求出所有像素点的模糊相似关系k ，应用阈值法切断那些 不满足闽值的模糊相似关系。然后对处理过的图像场应用图论中求连通分支的方 法求出与种子点连通的那些像素点。这里求连通分支的方法有两种，一种是应用 可达矩阵，另一种是应用生成树，通过这两种方法都能求出连通区域并达到分割 的目的，后者更优于前者。这样就得到了一个连通的区域，并且该区域中的模糊 相似关系满足模糊硒目标区域的定义。通过算法复杂度理论分析，这两种方法相 对于k f o e 算法大大降低了算法复杂度，并通过实验也证明了它们的有效性。 3 1 应用可达矩阵改进的模糊连通度图像分割方法 3 1 1 可达矩阵基础知识 1 可达矩阵定义【4 2 j 定义3 1 设g = 是一有向图，其中p ! h ，i 2 ，圪 ，并假定已经有 了从到圪的次序。定义了一个1 1x n 的矩阵4 - - ( a h 。，当 e e 时，a o ，= 1 1 当 岳e 时，a o = 0 ，称矩阵a 是图g 的邻接矩阵。一个图的邻接矩阵完整地 刻划了图中各结点间的邻接关系，同时还可以通过对矩阵元素的一些运算来获得 对应图的某些数量特征。 第3 章改进的模糊连通度幽像分割方法 定理3 1 设a 是图g 的邻接矩阵，则a x 的( f ，d 元素a o ( k ) 等于g 中从k 到嵋 的长度为k 的通路数目。若口。= 0 ，则表示没有长度为k 的通路，若4 u - o ，则 a q 仲给出了从k 发出的长度为k 的回路数目。 有向 图g 中从k 到k 的可达性问题，可以通过邻接矩阵运算而得到。 令 j = ( r u k 。，而；，唾+ 4 2 + + 爿4( 3 1 ) 其中r q 给出了从k 到 的所有长度为1 到n 的通路数目之和。具有玎个结点的有 向图中，基本通路及基本回路的长度不超过n ，故若r i j = o 则表示从k 到m 是不 可达的；若r q - o 则表示从k 到巧是可达的；若r u = 0 则表示从k 出发没有回路； 若 f o 则表示从e 出发有回路，这样的点称为递归点。因关心的仅仅是从k 到