（数学专业论文）基于水平集方法的图像分割研究.pdf

围防科学技术大学研究乍院硕十学位论文 摘要 图像分割在图像工程中占据着重要的位置，它是由图像处理到图像分析的关 键步骤，已被广泛应用到实际当中。在过去的二十多年罩，图像分割方法层出不 穷，分割效果日渐提高，尤其是水平集方法的诞生，更加推动了图像分割方法的 研究进度。c v 模型是水平集方法在图像分割应用中的经典之作，给后来的工作 起到了启发作用。但是由于图像的复杂性和c v 模型自身存在的缺陷，c v 模型 并不能对所有的图像进行正确完整的分割。立足于这一点，本文的主要目的是研 究并提出适用于更广范围的图像分割方法。 本文主要研究基于水平集方法的图像分割。首先，从符号距离函数入手，提 出了一种扫描生成符号表和扫描生成距离函数的方法，从理论和实验两个角度可 以看出，这种方法是行之有效、简单省时的；其次，提出了一种只考虑演化曲线 外部信息的背景减除模型，运用变分法相关原理对其进行极小化，进而得到背景 减除模型的水平集方程。应用该方程，给出了几个实验结果，并且将其与c v 模 型做对比，得知该模型结构简单、迭代省时、分割效果明显、具有抗噪性。另外， 背景减除模型的水平集方程在演化过程中无需对符号距离函数重新初始化；紧接 着针对背景减除模型的不足之处，提出了一种串行双水平集方法。通过实验结果 可以看出，该模型解决了背景减除模型的遗留问题，高效可行；最后，通过观察 背景减除模型的水平集方程迭代若干步后的水平集函数示意图，并应用理论分析 给出了该模型演化后水平集函数的特点。然后，以演化恰当步后的水平集函数为 对象，提出了一种只用求解其几个特定的水平集就能达到较好分割效果的方法， 实验结果印证了这一点。 关键词：图像分割；水平集方法；符号距离函数；变分法；欧拉一拉格朗日方 程；c - v 模型 第i 页 国防科学技术大学研究生院硕+ 学位论文 a b s t r a c t i m a g es e g m e n t a t i o np l a y sa ni m p o r t a n tr o l ei nt h ei m a g ep r o j e c t ，w h i c hi s t h ek e ys t e pf r o mt h ei m a g ep r o c e s s i n gt oi m a g ea n a l y s i sa n dh a sb e e nw i d e l y u s e di np r a c t i c e 1 nt h ep a s tt w od e c a d e s 。ag r e a tm a n yo fm e t h o d sf o ri m a g e s e g m e n t a t i o nh a v eb e e nd e v e l o p e d p a r t i c u l a r l y t h ea p p e a r a n c eo ft h ei e v e is e t m e t h o dh a sg r e a t l yi m p r o v e dt h ee f f e c to fi m a g es e g m e n t a t i o n c - vm o d e li sa c l a s s i c a la p p l i c a t i o no ft h el e v e ls e ti ni m a g es e g m e n t a t i o n i th a sp l a y e da n i n s p i r i n gr o l et ot h es u b s e q u e n tw o r k h o w e v e r ，d u et ot h ec o m p l e x i t yo ft h e i m a g ea n dt h ei n h e r e n td e f e c to fc - vm o d e l 。i tc a n ts e g m e n ta l li m a g e s a c c u r a t e l ya n dc o m p l e t e l y b a s e do nt h i sp o i n t ，t h em a i np u r p o s eo ft h i st h e s i si s t os t u d ya n dp r o p o s eai m a g es e g m e n t a t i o nm e t h o dw h i c hh a saw i d e rr a n g eo f a p p l i c a t i o n f i r s to fa l l ，b ys t u d y i n gs i g n e dd i s t a n c ef u n c t i o n ( s d f ) ，t h i st h e s i sp r e s e n t s am e t h o du s e dt og e n e r a t es y m b o lt a b l ea n dd i s t a n c ef u n c t i o nb yg r i d ss c a n n i n g t h i sm e t h o di se f f e c t i v e s i m p l ea n dt i m e - s a v i n gf r o mb o t ht h et h e o r e t i c a la n d e x p e r i m e n t a la s p e c t s s e c o n d t h i sp a p e ri n t r o d u c e sab a c k g r o u n ds u b t r a c t i o n m o d e lw h i c ho n l yc o n s i d e r st h ee x t e r n a li n f o r m a t i o no ft h ee v o l u t i o nc u r v e b y t h em i n i m i z a t i o np r i n c i p l eo fv a r i a t i o n a lm e t h o d ，w eg e tt h el e v e ls e tf u n c t i o no f t h eb a c k g r o u n ds u b t r a c t i o nm o d e l a p p l y i n gt h i sf u n c t i o n ，s e v e r a le x p e r i m e n t a l r e s u t t sa r ep r e s e n t e d a n db yc o m p a r i s o nw i t ht h ec - vm o d e l ，w ec o n c l u d et h a t o u rm o d e lh a ss i m p l e rs t r u c t u r e ，m o r eo b v i o u ss e g m e n t a t i o nr e s u l t s ，t h e p r o p e r t yo fa n t i n o i s ea n dl e s st i m es p e n d i n go ni t e r a t i o n i na d d i t i o n ，t h el e v e l s e tf u n c t i o no ft h eb a c k g r o u n ds u b t r a c t i o nm o d e ld o e s n tn e e dt or e i n i t i a l i z et h e s d fa ta 1 1 t h i sp a p e ra l s oi n t r o d u c e sas e r i a it w o 1 e v e is e t sm e t h o dt om a k eu p f o rt h ei n a d e q u a c i e so ft h eb a c k g r o u n ds u b t r a c t i o nm o d e l f r o me x p e r i m e n t s r e s u l t s ，i tc a nb es e e nt h a tt h i sm o d e li sv e r ye f f e c t i v ei nd e a l i n gw i t ht h e r e m a i n i n gp r o b l e m so ft h eb a c k g r o u n ds u b t r a c t i o nm o d e l f i n a l l y ，b yo b s e r v i n g s k e t c hm a po ft h eb a c k g r o u n ds u b t r a c t i o nm o d e l sl e v e is e tf u n c t i o nw h i c h i t e r a t e san u m b e ro fs t e p s t h ec h a r a c t e r i s t i c so ft h i si e v e is e tf u n c t i o na f t e rt h e e v o l u t i o ni sg i v e n t h e n 。u s i n gt h ei e v e ls e tf u n c t i o na f t e ra p p r o p r i a t es t e p s e v o l u t i o n ，w ep r o p o s eam e t h o dw h i c hc a na c h i e v eb e t 【e rs e g m e n t a t i o no n l y w i t haf e ws p e c i f i ci e v e is e t s e x p e r i m e n t a ir e s u l t sp r o v et h i sp o i n t k e yw o r d s ：i m a g es e g m e n t a t i o n ；l e v e ls e tm e t h o d ；s i g n e dd i s t a n c e f u n c t i o n ；v a r i a t i o n a lm e t h o d ；e u l e r - l a g r a n g ee q u a t i o n ；c - vm o d e l 第i i 页 国防科学技术大学研究生院硕十学位论文 图目录 图1 1图像工程3 层次示意图：2 图2 1曲线演化过程与水平集函数演化过程关系示意图8 图2 2 符号距离函数符号取值示意图9 图2 3闭合曲线的符号表构造示意图ll 图2 4 曲线网格点上下连通情况示意图1 2 图2 5 含有封闭内部边界的闭合曲线符号表构造。1 2 图2 6 本文方法扫描计算含有内部边界闭合曲线的过程示意图1 5 图2 7 直接法和本文方法生成距离函数的对比图1 6 图3 1 简单图像的分类示意图2 0 图3 2 模糊边界单背景多目标图像2 0 图3 3正则的h e a v i s i d e 函数和d i r a c 函数示意图。2 2 图3 4 模糊边界的c v 模型分割结果2 4 图3 5 含有噪声图像的c v 模型分割结果2 4 图3 6 单背景双目标图像c v 模型分割结果2 5 图3 7曲线与待分割目标的关系图2 7 图3 8单背景三目标图像分割结果3 0 图3 9 含噪声多目标图像分割结果对比图3 1 图3 1 0 本文方法分割m r i 图像的效果图3 1 图4 1双背景图像分割结果对比图3 3 图4 2 本文和文献f 3 5 】罩两个水平集函数0 水平集位置比较示意图3 6 图4 3灰度递增图像的分割结果比较示意图3 7 图4 4 髋切面图像分割结果3 7 图4 5 人工合成图像的分割结果3 8 图4 6 不同参数下的分割结果3 9 图4 7 灰度递增图像分割结果示意图4 0 图4 8大脑c t 图像的分割结果对比示意图4 l 图4 9 人工合成多目标多背景图像的分割结果对比示意图4 2 第1 i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题昏基王壅壬篡左洼鲍图像金割叠究 学位论文作者签名：羔臣l 日期： 一7 年穆月夕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期：叩年，2 月矽日 日期：m 年i z - p 7 日 | 国防科学技术大学研究生院硕十学位论文 第一章绪论 1 1 图像与计算机图像处理 图像是自然界景物的客观反映，是用各种观测系统以不同形式和手段观测客 观世界而获得的，可以直接或间接作用于人眼并进而产生视知觉的实体。图像中 包含了它所表达物体的丰富描述信息，具有直观、形象、易懂和信息量大等特点。 据统计，通过视觉获取的信息占人们获取所有信息的7 5 左右，因此图像是人类 日常生活、生产中重要的信息源泉。 视觉使人类得以感知和理解周边的世界，视觉所感受到的图像可看做是三维 光辐射场对人眼的影响i l 】。图像最终需要由人或机器来观察、识别和理解。人的视 觉系统可看成是一种神奇的、高度自动化的生物图像处理系统，但是，面对当今 科学技术飞速发展的形势，人的视觉系统还存在主观性、局限性、缺乏持久性和 模糊性等不足之处，所以迫切需要一种能够模拟人的视觉功能而又能超越它的性 能的图像处理系统。数字图像处理，简称图像处理，即利用计算机对图像进行分 析和处理，这一技术是随着计算机技术的发展而逐渐发展起来的一个新的应用领 域，汇聚了光学、电子学、数学、摄影技术和计算机技术等学科的众多方面。 随着人类社会的进步，科学技术的发展，人们对信息处理和信息交流的要求 越来越高。近年来，图像处理已经得到了很大程度的发展，但随着对图像处理的 要求不断提高，应用领域的不断扩大，图像理论必须不断提高、补充和发展。图 像的处理已经从可见光谱扩展到光谱中各个阶段，从静止图像发展到运动图像， 从物体的外部延伸到物体的内部，以及进行人工智能化的图像处理等。 在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣。这些部 分常称为目标和前景( 其它部分称为背景) ，它们一般对应图像中特定的、具有独特 性质的区域。为了辨识和分析图像中的目标，需要将它们从图像中分离提取出来， 在此基础上才有可能进一步对目标进行利用。图像分割就是指把图像分成各具特 性互不重叠的区域并提取出感兴趣目标的技术和过程。 1 2 图像分割的目的和意义 广义上，图像技术是各种与图像相关的技术总称。目前，人们主要讨论的是 数字图像，即主要应用的是计算机图像技术。这包括利用计算机和其他电子设备 进行和完成的一系列工作。图像技术种类很多，跨度很大，但可以将它们归在一 个整体框架图像工程之下【2 l 。图像工程是一个对整个图像领域进行研究应用的 第l 页 国防科学技术大学研究生院硕十学位论文 新学科，它的内容非常丰富，根据抽象程度和研究方法等的不i 司町分为三个各有 特点的层次：图像处理、图像分割和图像理解。它们的关系如图1 1 【3 】所示： 高i 一： 小 抽 象 程 度 符号 目标 蓁 像素 数 据 量 低 l 一： 大 图1 1图像一r 程3 层次示意图 其中，图像处理强调的是图像之间进行的信息交换；图像分析则主要是对图 像中感兴趣的部分进行检测和测量，从而获得它们的客观信息进而建立对图像的 描述；图像理解是在图像分析的基础上，进一步研究图像当中各自不同对象的不 同性质和它们之间的相互联系，并得出对图像内容含义的理解以及对原客观场景 的解释，从而指导和规划行动。 图像分割在图像工程中占据重要的位置，它是由图像处理到图像分析的关键 步骤。一方面，它是目标表达的基础，对目标特征测量有重要的影响；另一方面， 图像分割及其基于分割的目标表达、特征提取和参数测量等将原始图像转化为更 抽象更紧凑的形式，使得进行高层的图像分析和理解成为可能。 图像分割在实际中已得到广泛的应用，例如在遥感和生物医学图像分析、文 档图像处理、保安监视、工业自动化、生产过程控制，以及军事、体育、农业工 程等方面。总的来说，在各种与图像相关的应用中，只要需对图像目标进行提取、 测量时，都离不开图像分割。自2 0 世纪7 0 年代起，图像分割技术就一直受到人 们的高度重视，虽然经历了较长时问的发展，但由于图像种类的多样性，很难用 一个精确的数学公式来表征图像分割的过程。因此，尽管分割的方法很多，还没 有一种适合于所有图像的通用的分割方法。一般来说，对图像分割方法的选择， 都应依据图像和目标而异。能否找到一个统一的方法来用于所有图像的分割是现 在许多学者研究的方向。所以，至今为止，图像分割仍然是图像技术中的研究热 点。因此，从基础原理、应用以及应用效果等方面来深入研究图像分割技术，对 于提高图像分析、图像理解和图像处理技术的实际应用水平，都具有十分重要的 意义。 1 3 图像分割方法概述 第2 页 层 层 层 高 中 低 厂j、l 语 义 国防科学技术大学研究生院硕十学佗论文 多年米，人们对图像分割提出了许多1 i 川的解释定义，不同的定义对分割效 果有不同的影响。借助集合知识，对图像分割作如下比较正式的定义 4 1 ： 令集合尺代表整个图像区域，对r 的分割可看做是将尺分成个满足以下五 个条件的非空子集( 子区域) 蜀，尺：，氐： i ) r 是连通的区域，f _ 1 ，2 ，n ； i i ) 对任意的f ，rnr ，= 彩； v i i i ) ij r =；i r 、， i = l i v ) h ( r ) = t r u e ，汪1 ，2 ，n ； v ) 日( 尺，ur ，) = f a l s e ，f ，r 与尺，相邻。 其中h ( r ) 是评价区域r 中元素灰度一致性的逻辑谓词。图像分割后所产生的 区域必须是一致的和最大的，其中“最大”是指一致性准则在合并任意两个相邻 区域后就不再是真的了。 在过去的几十年里，已经有数以千计的图像分割方法被提出。按照年代界限， 可以把图像分割方法划分为：传统图像分割方法和基于模型的分割方法。 1 3 1传统图像分割方法 在图像分割技术发展的最初2 0 年里，人们主要研究的分割方法综称为传统图 像分割方法。它主要分为以下三种：阈值分割方法、边缘检测方法和区域提取方 法【4 1 。 灰度级阈值分割方法是最古老、最简单的分割算法，适用于物体间彼此不接 触且物体灰度与背景灰度明显不同的图像。很多物体或图像区域表征为不变的反 射率或其表面光的吸收率，可以根据先验知识或整幅图像的灰度信息确定一个亮 度常量，即阈值，然后将图像中各个像素的灰度值都与这个阈值相比较，并根据 比较结果将对应的像素划为两类：像素的灰度值大于阈值的归为一类；像素的灰 度值小于阈值的归为另一类( 灰度值等于阈值的像素可归于这两类之一) 。选择正确 的阈值是阈值分割方法成功的关键所在。 边缘检测方法代表了一大类基于图像边缘信息的方法，它是最早的分割方法 之一，且现在仍然是非常重要的。基于边缘的分割依赖于由边缘检测子找到的图 像边缘，这些边缘标示出了图像在灰度、色彩、纹理等方面不连续的位置。在基 于边缘检测的分割方法发展中，人们提出了各种各样的检测算子，如梯度算子、 方向算子、拉普拉斯算子、马尔算子、综合正交算子、坎尼算子等。但是，边缘 检测得到的图像结果并不能用作分割结果，往往要进行一些后续的处理将边缘合 第3 页 国防科学技术大学研究生院硕十学位论文 并为边缘链，使它与图像中的边界对应得更好。基于边缘分割的最常见的问题是 在没有边界的地方出现了边缘以及在实际存在边界的地方没有出现边缘，这是由 图像噪声或图像中的不当信息造成的。 前面两种方法均是找到区域间的边界，进而达到分割的效果，而区域提取方 法则是直接构造区域，也称它为区域增长方法。它的主要思想是把图像中每一个 像素都划归到一类属性的物体或区域中。简单的区域增长方法有区域归并、区域 分裂和分裂与归并。使用区域增长方法分割后的图像，时常由于参数设置的非最 优化，造成了不是含有太多区域就是含有太少区域的情况。为了改进分类效果， 区域增长方法需要做适度的后处理，简单的后处理是小图像区域消解法，就是给 定预先选择的尺寸，把小于该尺寸的图像区域归并到与之相似的临近区域中。 1 3 2 基于模型的图像分割方法 基于模型的分割方法就是根据某种条件，建立分割模型方程，然后根据方程 的演变找到分割的最终结果1 5 j ，一般意义上分为两种：一是参数活动轮廓模型分割 方法；二是几何活动轮廓模型分割方法【6 】【7 1 。相比于传统的图像分割方法，基于模 型的图像分割方法具有以下显著的优点： 由于模型是在连续状态下实现的，所以最终得到的图像边缘表示可以达到 更高的精度，这一点对于医学图像分割和应用具有非常重要的意义； 通过限定被提取物体的边缘是光滑的，并且融入了其它关于物体形状的先 验信息( 比如曲线长度、区域面积等) ，在方程演化中直接处理了图像的梯度、 曲率等几何特征。所以，基于模型的图像分割方法具有较强的鲁棒性； 使用光滑的闭合曲线表示物体的边缘，避免了传统图像分割方法中的预处 理和后处理过程，如阈值确定、边缘连接等，而且对于物体的形状分析和识别都 具有重要的作用。 参数活动轮廓模型是一种基于变分方法的图像分割模型，该模型首先提出目 标能量函数，然后通过求解其最小值，从而达到对图像分割的目的。一般地，通 过变分法对能量函数进行极小化，得到模型演化的偏微分方程。1 9 8 7 年k a s s ， w i t k i n 和t e r z o p o u l o s 提出了s n a k e 模型【8 】，该模型首次引进了变分法。首先给定 图像和初始曲线，然后使曲线沿法线的方向演化，当运动到物体边界处时，目标 能量函数达到最小值，停止演化，即已检测到图像中物体的边缘。其中物体的判 别仍要依赖传统的基于图像梯度的边缘探测器。通过该模型能得到正确的边界， 并且还能保持边界的光滑性。然而当s n a k e 模型中的初始曲线离物体边界比较远 时，会使演化陷入局部极值点，不能j 下确地对图像进行分割，导致出现错误的分 割结果。针对该缺陷，c o h e n 在s n a k e 模型中引入球形力【9 】来使轮廓沿着法向方向 第4 页 国防科学技术大学研究生院硕十学何论文 向内或向外演化，i r d 时最大化光滑边界所围区域的面积。球形力使轮廓线跨过假 的、孤立的图像边缘，用以抵消曲线收敛趋势。随后，c o h e n 等又提出了距离有势 力模型【1 0 l ，虽然极大拓展了主动轮廓捕获边界的范围，但该模型只适用于二值图 像分割。改进的s n a k e 模型虽然降低了对曲线初始位置和图像噪声的敏感性，但 仍然需要人工决定充气还是放气，而且也不能自然地处理曲线拓扑结构变化。另 外，s n a k e 模型中的能量泛函只依赖曲线参数的选择，跟物体几何形状无关。 而另外一种重要的活动轮廓模型称为几何活动轮廓模型。几何活动轮廓模型 由c a s e l l o s 和m a l l a d i 等人【】【1 2 】分别独立提出，可以认为是s n a k e 模型的扩展，不 同于s n a k e 模型之处在于这种模型的轮廓曲线运动过程是基于轮廓曲线的几何度 量参数。这样，轮廓曲线运动过程就独立于轮廓曲线的参数，因此可以自动处理 拓扑结构的变化。几何活动轮廓模型中应用较多的是由c a s e l l o s 和k i m m e l 等人提 出的测地活动轮廓模型【1 3 】，然而该方法的主要缺点是一旦特征边界出现缝隙，曲 线就会越过目标边界发生“泄露”现象，而且再也无法返回到正确的位置。 随着水平集方法的提出，几何活动轮廓模型与水平集方法相结合的曲线演化 方法成为了图像分割方法的主流。该方法利用轮廓曲线的几何特性，建立轮廓曲 线演化的目标能量函数，然后运用变分法最小化这个能量函数，最终使轮廓曲线 演化至目标的边界，达到分割的目的。其间，利用水平集函数将曲线的演化方程 化成为求解偏微分方程的问题。m u m f o r d s h a h 模型【1 4 】是较早的基于区域的几何活 动轮廓模型，它适用于模糊边界或不连续边界等场合，并且对初始曲线位置不敏 感。t s a i 考虑到区域i 、日j 像素的差异性【l5 1 ，提出最大化区域间平均灰度值之差的平 方建立能量函数。在此基础之上，c h a n 和v e s e 提出了经典的区域最优划分图像分 割模型( c v 模型) 1 6 】，它是一种简化的m s 模型，是一种基于水平集方法的几 何活动轮廓分割模型，该模型充分利用了图像的全局灰度信息，取得了不错的分 割结果。但是由于该模型仅利用了图像的区域灰度信息，使得在某些图像的分割 中，图像边缘定位精确度不高，分割效果不理想。构造不同的目标能量函数，获 得精确度较高的分割模型，是当前几何活动轮廓模型与水平集方法相结合的分割 方法研究中的热点和难点【l 7 。 1 4 本文的主要工作 鉴于以上的讨论分析，我们做了如下的工作： 第二章对水平集方法做了简介，提出了扫描生成符号表的方法和扫描生成距 离函数的方法，给出了两个实验结果。从理论和实验两个角度出发，将其与直接 法做对比，说明我们的方法行之有效，并且简单省时。 第i 章首先介绍了经典的c v 模型，指明了它的优缺点；其次本文从c v 模 第5 页 国防科学技术大学研究生院硕十学位论文 型的缺点出发，只考虑曲线外部信息，提出了背景减除模型，并运 j 变分法对模 型进行极小化得到最终的水平集演化方程：最后给出了几个实验结果，并且将之 与c v 模型分割结果做对比，分析指出了背景减除模型的优点。 第四章首先针对第三章背景减除模型存在的不足之处，分别考虑曲线内外信 息，提出了串行双水平集方法，并给出了数个实验结果，客观地对比和评价了我 们模型的优缺点；最后分析背景减除模型迭代若干步后的符号距离函数图，提出 了根据适当步迭代后的符号距离函数示意图，后验确定水平集的方法，从实验结 果可以看出这种方法是高效可行的。 第6 页 国防科学技术大学研究生院硕十学位论文 第二章水平集方法与符号距离函数 水平集方法( l e v e ls e tm e t h o d s ) 是由s e t h i a n 和o s h e r ! 1 8 】【1 9 j 于19 8 8 年提出， 最近二十年得到广泛的推广与应用。最初水平集方法被用于解决遵循热力学方程 下火苗外形的变化过程，由于燃烧中的火苗外形的拓扑结构变化非常复杂，且具 有随意性，所以用参数化的曲线或曲面描述火苗外形的变化过程就显得相当笨拙、 不现实。水平集方法，以一种隐含的方式来表达平面闭合曲线或立体闭合曲面， 有效的解决了在拓扑结构发生变化时，曲线参数化方法无能为力的问题，将一些 复杂拓扑结构变化问题简单化、可行化。 2 1 水平集方法概述 水平集方法是一种有效处理曲线变化问题的工具，简单地说，水平集方法就 是把低维的计算问题上升到更高一维，即把维的描述看成是+ l 维描述的一个 水平特例f 2 0 1 。以二维曲线演化为例，平面曲线c 被隐含地表达为三维连续函数曲 面矽( x ，y ，f ) 的一个具有相同数值的等值曲线，通常取。等值线，即 矽= 0 ，称为零 水平集，矽( x ，y ，) 称为水平集函数。在处理曲线的变化问题时，根据曲线变化的条 件推导出水平集函数演化的外力，进而不断更新水平集函数，再求出零水平集所 在，便得到了曲线在对应时刻演化后的形状。下面我们给出这种演化的数学表达。 假设矽( x ，y ，f ) ：r 2 o ，t ) 专r 为l i p s c h i t z 连续的水平集函数，为时间参数， 闭合曲线族c ( x ，y ，) 表示f 时刻与( x ，y ，) 对应的零水平集，即： c ( x ，y ，r ) = ( x ，y ) i 矽( x ，y ，) = 0 ，v f 【o ，t ) 由上式可以得到如下的关系式： 矽( c ( 吐f ) = 0 ，v t 0 ，丁) ( 2 1 ) 应用链式法则，对式( 2 1 ) 两边关于r 求全微分，得到水平集方程： 痧+ v 痧坐：0 ( 2 2 ) 一 耐 式中v 矽表示水平集函数矽的梯度，等表示的是曲线c ( x ，y ，) 的变化率，它可以分 研 解为法向( n ) 和切向( t ) 两个方向的分量，即： o c ，：k 丙+ 杉于 ( 2 3 ) 倒 根据水平集函数的定义，可知曲线c 在( x ，y ) 的切方向丁与v 矽垂直，故： v 西t = 0( 2 4 ) 篼7 页 国防科学技术大学研究生院硕十学位论文 将式( 2 3 ) 和( 2 4 ) 代凹( 2 2 ) 中得到新的水半集方程： 谚+ v 矽圪= 0 ( 2 5 ) 更舻步，水平集的内向单位法向量为砧一尚，那么上式可继续更新为： 谚= 圪l v i ( 2 6 这样方程( 2 6 ) 所求出的便满足等式( 2 1 ) ，它是一种h a m i l t o n j a c o b i 方 程【2 ，其中k 称为速度函数。其中曲线c 的曲率可由以下公式求出： 拈咖2 气黼笋 以二维为例，水平集方法的可以形象地表示为图2 1 。虚线以上表示的是二维 的曲线变化，红线以下表示的是三维( 比二维高一维) 水平集函数的演化，其中 曲线变化的虚线表示这个过程没有直接进行，是通过水平集函数演化这个过程表 现出来的。 初始曲线 - t 时刻曲线 提 取 嵌 f 乍 苓 永一 入 亚 1r 集 初始水平集t 时刻水平集 图2 1 曲线演化过程与水平集函数演化过程关系示意图 在实现活动轮廓线演化上，水平集方法相比于参数化方法有以下几个优点【2 2 】： 只要速度函数圪是平滑的，则水平集函数( x ，) ，r ) 始终保持为一个函数，那 么曲线在低维时的拓扑变化( 合并、分裂等) 在高维中便可以很自然的得到处理； 低维曲线在演过程中需要不断地重新参数化，而高维的水平集函数则不需 要； 高维中( x ，y ，) 的计算已经有许多成熟的算法，并且在这方面已有非常成熟 的分析工具，比如偏微分方程的理论及其数值化等。因此，高维中就可以很容易 实现数值近似算法，计算更精确、更具鲁棒性。这也是非常重要的一点； 水平集方法可以非常容易的推广到更高维的应用当中。 虽然水平集方法具有这么多的优点，但是，随着从低维到高维的上升，水平 集方法也有一些缺点和难以处理的问题： 第8 页 国防科学技术人学研究生院硕十学何论文 水、f ，集方法把| 、u j 题上升了一维，计算量有了明显的增加，这就要求有精度 更高、计算更方便省时算法的产生； 水平集函数矽( x ，y ，f ) 的选择。通常选用的是符号距离函数( s i g n e dd i s t a n c e f u n c t 4 b n ) ，简记为s d f ，这将在第二节做讨论； 速度函数k 的扩展。因为水平集方程( 2 6 ) 是由零水平集推导而来，所以 速度函数k 只在零水平集上有定义，其它水平集上没有定义，因此，在水平集函 数矽( x ，y ，f ) 的演化过程中，需要有一种方法来将k 由零水平集处扩展到全值域，变 为全域的速度函数。如何选择合适的方法进行扩展，是实现水平集方法时需要仔 细考虑的问题。 2 2 符号距离函数 水平集函数( x ，y ，f ) 初始化对其演化有重要的影响，通常意义上我们选择的由 初始闭合曲线生成的符号距离函数( s i g n e dd i s t a n c ef u n c t i o n ) ，简记为s d f 。 设初始闭合曲线为c ( t = o ) ，它围成的部分记为q ，矽( ；，f = 0 ) ，；r 2 是初始的 s d f ，定义其取值为： i 矽( x ，f = o ) l = d ( x ) 其中d ( ；) 表示的是点x 到初始曲线c ( t = 0 ) 的距离。 o u t s i d e c o 叠 0 n o u t s i d e c o 一 西 0 、 l 一一乞”、 0， 一一r 一 一 o u t s i d e c o i 0 n 图2 2 符号距离函数符号取值不意图 矽( ；，f = o ) 的取值如图2 2 所示。在曲线内部时，( ；，= o ) 取为正距离；在曲 线外部时，矽( ；，t = 0 ) 取为负距离。这里需要指出的是，( ；，= 0 ) 在曲线内外的正 负关系是相互对立的，但具体是取内讵外负还是外正内负对计算完全没有影响。 符号距离函数具有一个非常显明的特性，就是： i v 矽l = 1 ( 2 7 ) 一般地，在初始s d f 时，我们选用的曲线是正规曲线，比如圆周、正多边形 等。这样做的好处是s d f 的计算过程简单省时，这样做的缺点是初始曲线有可能 第9 页 国防科学技术大学研究牛院硕十学位论文 落在距离需要分割的目标较远的位置，不利j 二j 卜确及时分割出全部需要的目标。 鉴于此，我们经常根据需要，选择一些不规则的曲线作为初始零水平集。因此， 如何快速准确地计算符号距离函数便成为首要的问题。另外，水平集函数演化若 干时间步长以后，其零水平集很有可能变为非规则曲线，需要将它重新初始化为 符号距离函数。所以我们把符号距离函数重构的问题归入到非规则曲线作为零水 平集来初始计算符号距离函数的问题之中，但是它们不完全相同，符号距离函数 的重构过程相对简单，因为它可以根据计算得到的矽直接提取符号，而且符号距离 函数的重构可以根据( 2 7 ) 式进行迭代计算得出，比符号距离函数的初始化多了 偏微分方程数值求解的方法。 符号距离函数的初始化可以分为三个步骤： 符号表的构造。记初始闭合曲线为g ，s 为图像中每个像素点p 的符号。 记c 0 的内部( i n s i d e ( c o ) ) 为正，其外部( o u t s i d e ( c o ) ) 为负，即 s ( p ) ： 1 p c i n ? ? ，如图2 2 所示； l l p o u r s t a e c o 距离函数的计算。计算图像中每个像素点p 到初始曲线的最短距离d ( p ) ； 构造符号距离函数。符号距离函数矽( p ) = s ( p ) d ( p ) 。 符号距离函数重构是水平集方法中一个非常耗时的步骤，减少这一步骤的时 间和提高距离值的精确度将有助于提高曲线演化的效率。在过去的十几年里，符 号距离函数的计算得到了很大程度的关注，也取得了不可忽视的成绩【2 3 1 。 2 2 1 符号表的构造 符号表的构造相对于距离函数的生成简单一些，但它对于j 下确省时地构造出 符号距离函数同样重要。在以往符号距离函数构造的文章中，讨论距离函数构造 的文章居多，而讨论符号表构造的文章很少。在这一小节中，我们从像素点之间 的位置关系入手，提出了一种新的构造符号表的方法，各像素点的符号只需判断 它左边点的信息就可以了，无需计算。 从符号距离函数的定义可以知道，一个连通区域内各点的符号应该相同。本 着这一点，我们编程实现的步骤如下： 1 ) 对图像进行二值化处理，得n - - 值矩阵u 。 图像中像素值小于1 2 8 的像素点，它的u 值记为0 ，否则记为l 。因为2 5 5 表 示的是黑色，所以活动轮廓曲线上点的u 值均为0 。同时用和u 相同大小的单位矩 阵v 表示初始的符号表，给定这样的初值方式就是假设所有的像素点在同一个连 通区域内； 第1 0 页 国防科学技术九学研究生院硕十学位论文 2 ) 扫描生成符号表的过程。 一般的活动轮廓曲线不会衍，士到图像的边框上，网此我们不妨假设图像每行 的第一个点的符号值为1 扫描从第一列丌始，过程如下其中m ，n 表示图像的 行，列大小： f o ry = 2 ：n f o r x - 2 ：m 更新点( x ，处的符号值v e n d e n d 点( x ，y ) 处符号更新的准则如f ： 如果g ( x ，力x u ( x ，y 一1 ) = l ，表明点( x ，y ) 与其左邻点均小是活动轮廓线 的 点，故它们在同一个连通区域内，因此在这种情况f 符号表v 不做变化： 如果u ( x ，y ) = o ，u ( x ，y 一1 ) o ，那么点( x ，y ) 在活动轮廓线上，此时可理解 为扫描正在进入两个连通区域的交界处，叫以视其右边为另外一个连通区域， 凶此把此行后面的所有符号值变号，印v c , x ，y ：”) = 一v ( x ，y ：月) ，如果只完成这 步就不再进行f 面的扫描判断则会出现图2 3 第二副图的错误； 如果u ( x ，y ) o ，u ( x ，y i ) = 0 ，耶么它左邻点在活动轮窿线l ，此时可理解 为扫描正在越过两个连通区域的交界处，凼为在中已经做了反号的变化 此时不能简单的做反号，不然会造成符号表生成的错误，如下图2 3 第三副幽 所示，原因是只把边界点归为了一个连通区域。需要判断扫描是否真下进入 了下一个连通区域。 霪鍪i 嗯 判断标准，主要判断点( r ，y ) 前一点( x ，y 1 ) 上下点的“值： a 如果u ( x l ，y 一2 ) u ( x l ，y 一1 ) “o l ，y ) = 1 ，那么点( j ，y 1 ) 上面三个点 连通，且与点( x ，y ) 的u 值相同，如图2 4 庄圈所示，那么该四点连通，将点 k y ) 后面所有点的符号值设成与它们相川的值，即v ( x ，y ：h ) = v ( x - l ，y - i ) ； b 如果u ( x + l ，y 一2 ) x u ( x + l ，y 一1 ) u ( x + l ，y ) = 1 ，那么点( t y - 1 ) 下面三个点 连通，且与点f x y ) 的u 值相同，如图2 4 右圈所示，耶么陵叫点连通，将点 第l i 页 砥一 闭防科学拄术人学研究生院硕。1 ：学位论文 上连通情况r 连通情况 剀2 4 曲线网格点上r 连通情况币意图 c 其余情况时认为点( z ，y ) 末跨出点( ，y 一1 ) 所在的连通匣域，符号值不做变 化。 经过上i f 【i j 步的扫描后，v 值为l 的区域表示的是曲线外部v 为一1 的区域 表示的是曲线内部。从图2 3 第四副图可以看出程序足j e 确的。其中图像大小 1 2 5 x 1 2 5 ，曲线上刚格点个数9 7 5 ，扫描生成符号袁用时00 1 7 4 0 s 。另外，我们的 程序也能处理含有封闭内部边界的情况，如图25 所示。这说明我们的方法对于复 杂背景罔像分割的符号表构造仍然适用。 舍有封闭内部边界的刚台曲线本文方法枷遗的符号表 嘲2 5 古有封刚内部边界的闭台曲线符号袭构造 222 距离函数的生成 距离函数的生成本质上是计算点与点的距离，图像分割中距离函数的生成问 题，可以理解为把区域简单抽蒙为若干规则整齐的网格点，同样把曲线理解为网 格点，距离函数就足求区域的每个网格点剑曲线所有刚格点e u c l i d 距离的蛙小值。 我们可以这么定义： 定义2 1 设q c 豫2 是一个紧致的连续区域，f n 是一条封闭的曲线，p c f 是r 上的一些离散点集，对于v x q ，x 到曲线r 的距离可以记为： d ( x ) = d i s t ( x ，f ) = m 酬r 一硎a 如果将n 理解为一些网格点集，将r 理解成为蝗删格点p ，那么对于 v x n ，j 到r 的距离便可记为： 第1 2 页 国防科学技术人学研究牛院硕十学何论文 d ( x ) = d i s t ( x ，f ) = m i l l x p 0 ( 2 8 ) ，e o 利用公式( 2 8 ) 计算符号距离函数的方法称为直接法，这种方法的计算复杂 度为o ( m n ) ，其中m 是区域q 网格点数目，是曲线上网格点数目。它的优点是 方法直观，易于理解，计算精确；缺点是当曲线网格点的数目较多时，计算耗时， 并且不利于推广到三维或更高维。 在这一小节，我们提出了