（应用数学专业论文）基于pde、图割的图像分割模型及算法.pdf

河南人学硕士学位论文 中文摘要 图像分割是进一步进行图像识别、分析和理解的基础，已有许多分割方法但还 没有一种普遍适用于各种图像的有效方法图像分割的研究是目前图像处理中研究 的热点之一因此，本文基于偏微分方程( p d e ) 、图割的图像分割模型、算法研究具 有理论意义和应用价值 首先，本文从图像分割的目的和意义出发，对m u m f o r d s h a h ( m - s ) 模型、c v 模型、 逐段常水平集图像分割模型简单介绍和分析针对m s w d 模型数值计算算法效率 低、稳定性条件难以控制、调节参数难的问题进行研究提出算子分裂图像分割模 型，研究模型的数值计算，利用算子分裂格式给出了m s d m 的a o s ( a d d i t i v eo p e r a t o r s p l i t t i n g ) ，a o s n e w t o n ( a d d i t i v eo p e r a t o rs p l i t t i n g - n e w t o n ) 两种快速算法，从而达到既 快速极小化模型又克服了时间步长难以选择的难题，参数调节范围增大 其次，给出了求解m s d m 的图割算法将求能量函数的最小值转化为求图的最小 割采用高效的最大流算法进行数值计算图割算法避免了其它优化算法局部最小 的缺点，参数调节简单，计算速度快对合成图像及真实图像利用提出的算法实验，验 证该算法的可行有效性 最后，论文对提出的三种算法通过数值实验进行进一步比较 关键词：图像分害- i ；p d e ；a o s ；图割 河南人学硕士学位论文 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 of u r t h e rc a r r yo u ti m a g er e c o g n i t i o n ，a n a l y s i sa n du n d e r - s t a n d i n g t h e r ea r ea n u m b e ro fs e g m e n t a t i o nm e t h o d s b u tt h e r ei sn o tam e t h o dw h i c h i sg e n e r a l l ya p p l i c a b l et oa l lk i n d so fi m a g e t h e r e f o r e ，t h es t u d yo fi m a g es e g m e n t a t i o n i so n eo ft h eh o ts p o t si nt h er e s e a r c ho fi m a g ep r o c e s s i n g t h er e s e a r c ho fi m a g es e g m e n - t a t i o nb a s e do np a r t i a ld i f f e r e n t i a le q u a t i o n s ( p d e ) a n dg r a p hc u ti sm e a n i n g f u lb o t hi n t h e o r ya n dp r a c t i c e f i r s to fa l l ，i nt h i sp a p e r ，s u m m a r i z et h ep u r p o s ea n ds i g n i f i c a n c eo fi m a g es e g m e n - t a t i o n ，i n t r o d u c ea n da n a l y z em u m f o r d s h a hm o d e l ，c h a n - v e s em o d e l ，p i e c e w i s ec o n s t a n t l e v e ls e tm e t h o d t h en u m e r i c a la l g o r i t h mf o rt h em o d e li si n e f f i c i e n ta n dd i f f i c u l tt oc o i l - t r o lt h es t a b i l i t yo fc o n d i t i o n s ，a d j u s t i n gt h ep a r a m e t e r so ft h ep r o b l e md i f f i c u l t t os o l v e t h o s ep r o b l e m s ，w eg i v et h eo p e r a t o rs p l i t t i n gi m a g es e g m e n t a t i o nm o d e l u s i n go fo p e r a t o rs p l i t t i n gs c h e m e ，w eg i v et w of a s ta l g o r i t h m s - - a o s ( a d d i t i v eo p e r a t o rs p l i t t i n g ) ， a o s n e w t o n ( a d d i t i v eo p e r a t o rs p l i t t i n g n e w t o n ) ，s oa st oa c h i e v en o to 出m i n i m i z e e n e r g yf u n c t i o nq u i c k l yb u ta l s oo v e r c o m et h ed i f f i c u l t i e si nc h o o s i n gt h et i m es t e p s t h e p a r a m e t e rc a nb ec h o s e nm o r ee a s i l y s e c o n d l y , u s i n gg r a p hc u t st e c h n o l o g yt os o l v et h eg i v e nm s d m i n s t e a do fm i n i - m i z i n gt h ee n e r g yf u n c t i o n ，w ep r o p o s et os o l v et h er e s u l t i n gm i n i m i z a t i o np r o b l e mb y g r a p hc u t s b yf i n d i n gt h em i n i m u mc u to nas p e c i a lg r a p h ，w eo b t a i nt h es o l u t i o nf o rt h e s e g m e n t a t i o np r o b l e m 。h i g h l ye f f i c i e n tm a x i m u mf l o wa l g o r i t h mc a na v o i dt h es h o r t c o m i n g so fl o c a lm i n i m u m f u r t h e r m o r e ，p a r a m e t e r sc a nb ea d j u s t e ds i m p l ya n dc a l c u l a t e s f a s tw i t ht h en e wm e t h o d t h ea l g o r i t h m sa r ei n t e n s i v e l yt e s t e do ns y n t h e t i ca n dr e a l i m a g e s n u m e r i c a le x p e r i m e n t ss h o wt h a tt h en e wa p p r o a c hi sv a l i d f i n a l l y ，t h et h e s i ss h o w st h ec o m p a r i s o no ft h et h r e eg i v e na l g o r i t h m si nn u m e r i c a l e x p e r i m e n t s k e y w o r d s i m a g es e g m e n t a t i o n ；p a r t i a ld i f f e r e n t i a le q u a t i o n ( p d e ) ；a o sa l g o r i t h m ； g r a p hc u t i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书雨 使用过的材料。与我一同工作的同事对本研究所徽的任何贡献均已在论文中作 了明确的说明并表示了谢意。 )， 门j ，、，忡 学位串请人( 学位论竞作者) 签名：建：l 丝坠 卸d 7 年勿 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学住论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、奎阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学住获得者( 学位论文作者) 釜名： 盔! l 丑：! f 堑 2 0 移0 7 年石月7 目 学位论文指导教师签名：兰幽 2 09 c 7 年么月岁日 第一章绪论 数字图像处理技术在现代信息处理领域中变得越来越重要，医疗图像、遥感图 像、视频图像、特征识别、三维物体或场景的重建、质量检测、指纹分析等都需要图 像处理技术的支持图像处理方法的研究也有很长的历史，最古老的方法来源于一 维信号处理技术，如滤波器理论，频谱分析及概率统计模型目前图像处理的工具主 要分三类：随机模型理论、小波理论、偏微分方程理论随机模型理论主要基于马尔 科夫随机场理论，可以直接处理数字图像外波理论来源于信号处理，并且依赖于分解 技术；自9 0 年代以来，用偏微分方程处理图像的方法也获得较大的发展 1 1数字图像处理 数字图像处理，简称图像处理，指借用数字计算机处理数字图像，这一技术起源 于2 0 世纪2 0 年代，随着信息高速公路、数字地球概念的提出以及i n t e r n e t 的广泛应用， 图像处理技术的需求与日俱增图像处理具有交叉学科的特性，目前图像技术学科 体系可以用图( 1 1 ) 所示的三个层次表述这三个层次的有机结合也称为图像工程 低层处理技术主要有图像滤波、图像增强、图像复原、图像修复、图像编码压缩等 图像分割是介于底层图像处理与中层图像分析之间的一类图像处理过程 踉始阉像 语义符号 特征描述 图1 1 图像技术的三层模型 一幅图像可定义为一个二维函数，( z ，可) ，这里z 和y 是空间坐标，而在任何一对空 间坐标( z ，y ) 上的幅值，称为该点图像的强度或灰度当( z ，秒) 和，幅值为有限的、离 散的数值时，称该图像为数字图像数字图像处理是指借用数字计算机处理数字图 像，数字图像是由有限的元素组成的，每一个元素都有一个特定的位置和幅值，这些 元素称为像素 1 】 河南大学硕士学位论文 1 2 图像分割的定义 图像分割是图像处理中图像分析的关键步骤，在图像处理中占据重要的位置一 方面，它是目标表达的基础，对特征测量有重要的影响另一方面，因为图像分割及其 基于分割的目标表达、特征提取和参数测量等将原始图像转化为更抽象、更紧凑的 形式，使得高层的图像分析和理解成为可能图像分割的过程就是将包含有大量各 式各样景物信息的图像分解成一些具有各种特征的最小成分，这些成分被称为图像 的基元从概念上来说，所谓图像分割就是按照一定的原则将一幅图像或景物分为 若干个部分或子集的过程图像分割也可以理解为将图像中有意义的特征区域或者 需要应用的特征区域提取出来，这些特征区域可以是像素的灰度值、物体轮廓曲线、 纹理特性等，也可以是空间频谱或直方图特征等多年来，人们对图像分割提出了不 同的解释和表达，可借助集合概念用如下比较j 下式的方法定义 9 】： 令集合q 代表整个图像区域，分割可以看作是将q 分成满足以下五个条件的非空 子集( 子区域) q 1 ，q 2 ，q n ： 1 u 墨1q 严q 2 q t 是连通的区域，对t = 1 ，2 ， 3 q in q ，= 仍，对v i ，j ，i j 4 p ( 哦) = t r u e ，对i = 1 ，2 ， 5 p ( f l tu ) = f l a s e ，e v i ，j ，i j 其中p ( f l i ) 是对所有在集合q i 中的元素的逻辑谓词上述条件( 1 ) 指出：分割结果 中全部子区域的总和应能包括图像中所有像素条件( 2 ) 指出：分割结果中同一个子区 域内的像素是连通的条件( 3 ) 指出：分割结果中各个子区域是互不重叠的条件( 4 ) 指 出：分割结果中的像素必须满足的性质( 例如：如果所有q 。内的像素有相同的灰度级， 贝j j p ( f l t ) = t r u e 条件( 5 ) 指出：分割结果中不同的子区域具有不同的特性，没有公共 元素条件( 2 ) 并非必要，因为要分割的对像未必一定是连通的当然，如果把对像不 连通的部分看作是不同的子对像，那么这个条件就是必要的 1 3图像分割的方法 图像分割的方法主要有基于阈值的分割、基于边缘的图像分割、基于区域的图 像分割；基于形态学分水岭的图像分割；基于偏微分方程( p d e ) 的图像分割方法 2 河南大学硕士学位论文 分水岭算法最早由c a y l e y 1o 和m a x w e l l 1 1 提出的分水岭方法在图像分割特别 是视频序列空间域分割方法中，是采用比较多的一种方法 图像处理中采用偏微分方程的思想可以追溯至i j g a b o r 2 和j a l i n f 3 1 的工作但是这 个领域实质性的创始来自于k o e n d e r i n k 4 1 和w i t k i n 5 各自独立的工作他们在图像 处理中引入了尺度空间( s c a l es p a c e ) 的概念，尺度空间把一组图像同时在多个尺度上 表述尺度空问理论是今天图像处理中对偏微分方程研究的基础他们将多尺度图 像表示为g a u s s i a n 滤波器平滑的结果这等同于将原图像经过热传导方程演化，获得 各向同性的扩散流在2 0 世纪8 0 年代后期，h u m m e l 6 1 注意到热扩散流并非产生尺度 空间的唯一抛物方程，提出满足极大值原理的演化方程也能定义一类尺度空间极 大值原理可以视为因果性的数学解释同时k o e n d e r i n k 又创造性地提出在g a u s s i a n 滤 波器处理过程中加入一个阈值运算器随后，o s h e r 等人将其发展成为一种几何偏微 分方程，即著名的曲线演化运动方程 p e r o n a 和m a l i k 7 引入的各项异性扩散方程是这个领域最有影响的工作他们提 出用保边界的具有方向性( 异性) 热扩散方程来代替g a u s s i a n 平滑滤波器他们的研 究开辟了图像处理中偏微分方程理论的应用和很多新的领域随后，o s h e r 和r u d i n 提 出冲击滤波器f 8 1 及r u d i n 提出了总变分下降法，明确提出了图像处理中应用偏微分方 程的必要性和重要性 采用p d e 方法做图像分割一方面得益于p d e 作为基础数学的一个重要分支，已 经形成的理论体系和数值方法；另一方面也得益于传统的图像处理技术所积累的经 验 基于p d e 的图像分割方法基本思想首先是建立一个合乎分割要求的p d e ，即建 立数学模型通常建立“能量 泛函数学模型建立之后，如何求解所得到的p d e 就 成为重要的问题图像函数固有的不连续性，数学模型所得到的p d e 的非线性，以及 图像数据量的庞大等，都给数值求解带来困难因此在p d e 方法图像分割中数值实现 与建立数学模型同样具有挑战性 图像分割的p d e 方法主要有以下优点 第一，由于数学界对于偏微分方程的数值逼近有长期深入的研究，因此可以获得 高度准确性和稳定性的数值解在考虑图像处理和数值解的时候，不可避免地会碰 到非平滑信号的求导问题计算数学中的粘性解提供了处理这类问题严密的数学理 论基于p d e 的方法具有良好的数学基础，可以提供深刻的理论结果，并且算法具有 良好的稳定性在图像处理和计算机视觉中引入偏微分方程理论，不仅有很多现成的 成熟算法，而且提供了丰富的理论结果，例如解的存在性、稳定性和唯一性的证明 第二，一些经典的方法如高斯滤波、中值滤波、膨胀和腐蚀在p d e 的统一框架下 得到了全新的解释从偏微分方程的视角出发处理图像，产生了新的方法，它们比经 3 河南大学硕士学位论文 典的方法包容更多的不变性，如保持结构的滤波、线形增强等 第三，p d e 是连续的模型，与具体的离散网格无关，并且具有旋转不变性 目前，基于p d e 的图像处理已经发展成为一个结合数学形态、变分法、逼近论和 仿设计等数学方法的完整理论体系【1 3 在基于p d e 的图像分割方法中，m s 模型、活 动轮廓模型和基于水平集方法的图像分割模型集中体现- p d e 图像分割方法的优越 性，目前基于p d e 的图像分割是研究的热点 图论诞生于1 8 世纪上半叶到1 9 3 6 年d 柯尼希发表了图论的第一本专著有限 与无限图理论，自此图论的理论及其应用研究得到飞速发展基于图割的图像去 噪算法、基于图割的纹理图像合成、基于图割的图像匹配，将能量函数的最小化问 题，通过构造相应的图，使能量与图割的容量相联系，利用图的理论给出能量函数的最 小化，从而获得图像处理的效果图割算法在优化过程中收敛更快由于用计算机来 计算或验证问题时，首先要建立算法因此图论研究的一个重要问题是建立算法近 年来，随着算法图论、计算组合学、算法组合学的研究，用图论进行图像处理也得到 迅速发展 基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热点 当前图论方法用于图像分割还处于初级阶段，b o y k o v 等人提出了基于图割理论有效 的能量函数优化方法本文将图像映射成带权无向图，利用最小割得到图像的最佳 分割论文对用到的图论基本知识进行简单介绍针对m s w d 模型用图为这一特定 问题建模，进而通过图割算法进行图像分割，在全局上获得能量函数最小，实验结果 表明，所提的算法效率较高，参数调节简单 1 4本文的章节安排 第二章预备知识，主要介绍了p d e 图像处理中常用的两种数学方法：变分法和水 平集方法综述图像分割中的活动轮廓模型，c v 模型，及逐段常水平集模型并利用这 些模型进行数值试验、 第三章详细综述了基于水平集方法的算子分裂思想；本文m s d m 的极小化过 程；推导出算子分裂图像分割模型，同时提a o s ( a d d i t i v eo p e r a t o rs p l i t t i n g ) ，a o s n e w t o n ( a d d i t i v eo p e r a t o rs p l i t t i n gn e w t o n ) 两种算法格式，并进行数值试验 第四章研究m s d m 的g r a p hc u t 算法，导出t m s d m 的离散模型，构造了与该模型 相对应的图结构，并证明了所构造图的最小割与m s d m 离散模型的最小值相对应给 出了基于图割的m s d m 的图像分割算法 第五章对本文提出的三种算法通过数值实验进行进一步比较，j 、结本文创新及 深入研究的展望 4 第二章活动轮廓模型及预备知识 2 1p d e 图像处理中常用的方法 2 1 1 变分法 变分方法是p d e 图像处理中一种常用的有效的数学方法 定义2 1 1 设x ，y 分别是定义在同一数域p 上的赋范线性空间和实数空间，d 是x 的一个子集，若存在某种对应法则t 使得z d ，有唯一确定的剪= t ( x ) = b y 与之 对应，则丁称为泛函数，简称泛函 这里，我们只考虑h i l b e r t 空间中的泛函对泛函求极值的问题称为变分问题，研究变分 问题的学科称为变分法使泛函取得极值的函数称为变分问题的解，也称为极值函 数 h i l b e r t 空间中的线性泛函：映射z ：x _ r ，x 为h i l b e r t 空间，r 为实数域，满足 条件：对任意的z ，y x ，a ，b r 都有l ( a x + b y ) = a f ( z ) + b 2 ( y ) 若存在常数c ，使 得i i ( z ) i c l l x l l ，则称线性泛函2 ( z ) 是有界的对于一个给定的函数z x ，若定义泛 函匕( z ) = ( z ，z ) ，则易见它是一个有界线性泛函对于h i l b e r t 空间中的有界线性泛函有 如下定理 定理2 1 2 设x 是一个h i l b e r t 空间，则对于任意有界线性泛函c ：x _ r ，都存在 一个函数z x ，使得对所有的z x ，l ( x ) = ( z ，z ) 成立 定义2 1 3 令f ：x _ r 是觑f 6 e n 空间x 中的一个泛函，设z x ，若下式 f 7 ( 缈) = 溉坐掣= 丢砟仙m ：。 ( 2 1 ) 的极限存在，则称它为泛函f 在z 处沿方向的方向导数进一步，若f 7 ( z ，) 是关于 的有界线性泛函，则称f 是0 疵e o t 诃微的 根据定理2 1 2 ，由于f 7 ( z ，) 是h i l b e r t 空间中的有界线性泛函，因此存在函数u x ，使 得f 7 ( z ，) = ( u ，) 称u 是f 的0 a t e a u x 导数( 一阶变分) ，并记为u = f ( z ) 若z 是泛 函f ( z ) 的极小值，则对所有的函数x ，都有f 7 ( z + ，) = 0 特别地，f 7 ( z ) = 0 2 1 1 1p d e 图像处理中一类常用的泛函及一阶变分 考虑泛函f ( u ) = 厶l ( x ，u ( z ) ，v u ( x ) ) d x ，其中l ( z ，u ，v u ) 是关于变量z ，u ，v t z 的连 续可微函数，z = ( x l ，x 2 ，z n ) q 且l ( z ，u ，v u ) l 2 ( q ) = ，：矗i f ( x ) 1 2 d x o 和 z ：( z ) 。悭到 矗g23 ( 帕 任一水平集融数d 蚝23 ( b ) 与中水平集相对应的平面 2 2 活动轮廓分割模型 k 孵等人提出的活动轮廓模型在图像处理中，低层信息的正确理解依赖于高层 信息活动轮廓模型能将基于图像本身的底层视觉属性( 边缘、纹理、灰度、色彩等) 和待分割目标的知识和经验，如目标的形状，亮度，色彩等经验知识，以种有机的方 式结合起来，得到待分割目标的完整表达将活动轮廓模型应用到图像分割中，其基本 9 河南大学硕士学位论文 思想可以描述如下：人为的在图像感兴趣的区域( 目标) 上给出初始轮廓曲线，即初 始值( 为一条或多条封闭曲线) ，最小化一个能量函数，使轮廓曲线在图像中运动( 变 形) ，最终逼近该区域( 目标) 边界驱使轮廓运动的机理在于最小化能量函数时，使 得满足一致性的区域扩张到最大( 或收缩到最小) ，即一致性区域的边界 活动轮廓模型的价值在于，它对一系列计算机视觉问题给出了统一地解决方法，已 经被成功的应用于边界提取、图像分割和分类、运动跟踪、三维重建、立体视觉匹 配等计算机视觉领域 2 2 1参数化活动轮廓模型( s n a k e s 模型) k a s s 、w i t l 【i n 、t e r z o p o u l o s 1 6 首次提出了利用活动轮廓模型进行2 d 、3 d 图像 分割，该模型不断发展，逐渐成为最有活力的图像分割技术之一 s n a k e s 模型，简言之，就是表征拟合误差的“能量”为最小化的曲线其原理是设计 拟合目标有一个待选曲线集，定义能量函数与待选集中的每一条曲线相关联肩邑量函 数的设计原则是有利属性能导致能量减小，有利属性包括曲线的连续性和平滑性，与 高梯度区域接近以及其他具体的先验知识这样，活动轮廓在取值范围内移动时就能 在能量函数的指导下收敛到局部边界，且保持曲线自身的连续性和平滑性【1 3 】 s n a k e s 模型的数学表述如下f 1 6 】： 设c 是实平面r 2 上的曲线集，i ：qcr 2 一冗，m 有界) 是图像u 的灰度( 强度) 定 义c = c ： 口，6 1 一q ，cp i e c e w i s e c l ，c ( a ) = c ( b ) 】，则对v c c 定义下面的s n a k e s 能量函 数 厂6广b。，6 e ( c ) = i d ( g ) 1 2 d q + 卢，| c ”( q ) 1 2 由+ 入9 2 ( i v ，( c ( q ) ) 1 ) d q ( 2 1 3 ) j a j o j 8 其中g ： 0 ，+ 。) _ 【0 ，+ o 。) 是边界探测函数，满足：( i ) l i m9 ( s ) = 0 ，( i i ) g 是单调递 减函数第三项为外部能量，吸引轮廓曲线朝图像中目标边界移动前两项称为内部能 量，用来控制轮廓的弹性和光滑性第一项是弹性项，阻碍曲线的拉伸，使曲线具有弹 性第二项是刚性项，阻止曲线弯曲，保证曲线的光滑性p 是强度系数，控制轮廓曲线 沿法线方向朝目标运动的速度，如果p 值很大，轮廓曲线就会变得僵硬而不容易发生 弯曲；如果较小，就会使轮廓曲线发生弯曲可以产生一个角，因此要调整强度系数，使 轮廓线在到达目标边界时夕h 部能量也达到最小值 s n a k e s 模型在内部能量和外部能量的共同作用下使曲线朝能量最小化方向演 化，最终得到目标边界该模型克吸收了解剖结构的先验知识，并具有交互能力，能够 简洁和解析地表达解剖结构形状，精确的分割出目标边界但是，该模型对开始演化的 初始位置很敏感另外一个困难的问题是，对参数化的演化曲线离散点集的选取，因 为这些点集是随着方程的演化不停的更新在这个过程中，很可能会产生一些过于集 1 0 河南大学硕士学位论文 中或者根本无效的区域，最终会导致数值计算后的边界不稳定或者是伪边界，也就是 说在收敛性方面，它有可能收敛到局部的最优点，甚至发散 此外如果图像中有多个目标物体的话，初始曲线无法选取，也就是说该模型无法 处理拓扑改变的情况如果选取的初始曲线包括所有的目标物体，也无法识辨出图像 中的多个物体，而且探测到的边界会产生角点变凸 2 2 2 经典活动轮廓模型 针对s n 8 k 模型的缺点，许多学者进行了改进研究主要集中在模型的收敛性和 稳定性方面c o h e n 提出的b a l l o o ns n a k e 模型18 1 提高了曲线收敛的速度c h e n y a n g x u 提出的基于梯度矢量流( g r a d i e n t v e c t o r f l o w ) 的g v f s n a k e 模型和推广的g v f s n a k e 模 型f 1 纠提高了曲线收敛到目标的速度和扩大了对目标的捕捉范围d k a n g 提出跟踪目 标的稳定s n a k e 模型1 2 叫主动轮廓曲线采用b 样条的s a k 4 型1 2 1 爿 均匀有理b 样条 ( n o n - u n i f u r mr a t i o n a lb - s p l l n es n a k e 模型，即n u r b ss n a k e s 模型 2 2 1 彦数s n a k e 模型 拓扑结构不能变化的局面f i q t e r - z o p o u l v s 的可改变曲线拓扑结构的s 舶i 罐型伫甜得 到解决在模型被改进的同时，模型的复杂程度也在增加c a s e l l e s ，k i m m e l 和s a p i r o 提出的测地主动轮廓线模型( g e o d e s i ca c t i v ec o n m ) 2 4 将图像分割问题等价地转 化为寻找r i e m a n n l a n 空间中的一条测地线这样，基于黎曼空问测地距离最短问题的 测地线活动轮廓模型为图像分割、边界提取提供了一种新的手段 在数学中，曲面上的一条在每一点处的测地曲率均为零的曲线称为测地线参考妇 2 4 的解释a ，b 两点的经典欧氏距离是线段( 虚线) 的长度，但如果a ，b 之间有障碍物 时，则a ，b 两点的距离是曲线( 实线) 的长度可以形象地参考地理中的捌地学，称为测 地距离 曲线的加权欧几里德长度l c 心= 尼。凼= cl d ( q ) i d q 则定义关于函数g ( j ) 的 测地距离为r 9 ( i v j ( c b ) i ) ic ，( q ) i d q b 丘g2 4 旃地匝离 活动轮廓模型的经典方法是用图像u o 的属性来( 如梯度相关的属性函数) 定出目 标的边界，经典的是用一个边界探测函数关于轮廓线c 的泛函为 球) = 小+ a z 6 剐v 叩( 口) m 由 ( 2 1 4 ) 1 1 河南大学硕士学位论文 这里9 是一个边界探测函数g 在内部一致性区域是正的且在边界严格为零这模型不 能处理轮廓的拓扑变换且依赖于曲线的参数表示。针对e ( c ) 不是内蕴的，c a s e l l e s 等 人提出了泛函【2 4 2 5 ： 6 眦) = 2 弧9 ( i v m m l c ，( q ) l d q ( 2 1 5 ) e 2 ( c ) 可以看成是加权欧几里德长度，权重是包含目标边界探测信息的边界探测函 数g ( i v i ( c ( q ) ) 1 ) 也就是说，我们利用了黎曼空间中的黎曼测度寻找测地线这个表述 也确保我们应用非常有效的数值格式经常用到的边界函数 9 ( i v 川2 再丽云研 这里9 是一个正的递减函数，使得1 i mg ( t ) = o ，特别当图像有噪声时，图像首先与高斯 核g 盯( z ，可) ：盯一1 2 e x p 掣卷积应用梯度下降理论计算模型( 2 1 5 ) 的孝及4 、值，设c ( q ) c ，t 0 ，c ( t ，q ) 是曲线族，初始曲线c ( o ，q ) = c o ( q ) 我们通过演化曲线族c ( t ，g ) 来探测图 像的轮廓演化方程为 百o c ：( 一( ，裔) ) 裔(216)ng v g 1 6 甭2 ( 一(，) ) ( 2 其中t 表示轮廓演化的时间，胃表示曲线的单位法线向量，k 表示曲线的曲率，v 表示梯 度算子 ( 2 1 5 ) 式可以通过在右端添加辅助项使得测地轮廓线模型探测非凸目标物体更 容易，加快收敛速度改进的模型为 寒= ( 仡9 一( v g ，奇) + a g ) _ n ( 2 1 7 ) 式中a g 是辅助项，参数q 0 的选取应该足够大使得系数心+ q 的符号保持不变，这样 曲率k 可以不必保持符号不变，从而可以探测到非凸的目标物体 模型( 2 1 7 ) 一般称为几何活动轮廓模型，利用水平集方法，将其表示成水平集函 数西的演化方程为： 筹刮i v 州( 酬嵩m ) l v e t 们坍 ( 2 1 8 ) 在演化过程中初始水平集收缩分裂直到探测出目标边界( 高梯度) 需要注意的是，带 “洞”的目标内部不能分割，当轮廓线不闭合时，探测边界是个难题对于一些边界不 能用梯度表示或者用梯度表示不好的图像，上面经典的测地轮廓线模型就无法很好 的分割 1 2 河南大学硕士学位论文 2 2 3m s 模型 m u m f o r d - s h a h ( m s ) 图像分割模型 2 6 是2 0 世纪8 0 年代由d m u m f o r d 和j s h a h 提出的，在理论上是一种具有体积和低微测度的新的变分问题，通过能量函数优化进 行图像分割m s 数学表达如下 设q 是r g ，n = 2 ，3 上有界开集， 1 t o ( z ) 是定义在区域n 上的原图像，不失一般性，我 们可以设几乎处处z q 0 u o ( z ) 1 ，我们为寻找函数u ：q _ 冗和不连续边界集r ，极小化下面能量泛函： 卜fr f ( u ，r ) = ( u u o ) 2 d x + q i v u l 2 d x + 卢d o ( 2 1 9 ) jjj q a i r r 其中a ，p 是非负常数j r 如是边界的曲线的长度第一项保真度约束( 光滑图像和初始 图像间的差异) ，保真度约束确保分割后的图像u 与原始图像u o 的偏差不至于太大第 二项强调条件翟在区域n r 上光滑度第三项极小化边缘长度，应该尽量光滑 早期的泛函模型是建立在c 1 类函数空间上的，具有很大的局限性，g i o r g i 和a m b r o s i o 等人为此提出了m - s 泛函的弱形式，将原泛函放宽到一类称为特殊有界变分s b v ( q ) 函数空间上但是实际上弱形式m - s 泛函的数值计算较难主要是因为需要对未知的 边缘长度项进行处理若泛函是非凸的找最小解是非常困难的为此许多学者做了 大量的研究 2 7 】用贪婪算法极小化m s 泛函，用区域增长法得到解 2 8 用统计框架计 算m s 泛函2 9 1 中将轮廓c 嵌入一个2 d 的相位场函数中做椭圆逼近 m s 模型是p d e 图像处理中一个经典模型，在图像分割和光滑中是人们研究的一 个热点问题2 0 0 0 年，c h a n 和v e s e 提出了一种简化的m s 模型，称为c v 模型 2 3c - v 变分水平集图像分割模型 活动轮廓模型，或者利用曲线演化理论，先得到一个用拉格朗日方程描述的二维 曲线演化的p d e 方程，再利用水平集方法将其转化为相应的水平集表达形式；或者利 用变分法，极小化一个关于平面参数化曲线的能量函数，得到曲线演化的梯度下降 流，然后再转化为水平集演化的欧拉表达上述两种方式都是分两个步骤得到水平 集函数的演化方程。然而，水平集函数演化的p d e 也可以直接通过极小化关于水平集 函数本身的能量函数而得到由于这是一个基于变分的能量极小化模型，故具有参数 化s n a k e s 模型的优点，而且由于采用水平集函数的表达式，所以又具有水平集方法的 优点，因此是一种非常理想的方法，这种方法称为变分水平集方法【3 0 】【3 1 l 变分水平集 方法的关键是首先建立一个能量函数模型，并且模型中的内，外能量都使用水平集函 数表示，再利用变分法对这个能量函数极小化，便得到水平集演化的p d e 1 3 河南大学硕士学位论文 相对于传统的有纯粹的p d e 驱动的水平集图像分割方法，基于水平集的图像分 割方法可以在能量函数中自然的融入附加约束信息，产生鲁棒性更强的结果 c v 模型是基于m s 分割技术的模型数学描述如下：设活动轮廓线c 将定义在图 像域q 上的图像咖划分为两个部分，若q = q 1uq 2 满足： q 1 = z l v x 在c 的内部) q 2 = z l 比在c 的外部) 则c v 模型的能量函数定义为 f ( o ，c 2 ，c ) = p l e n g t h ( c ) + a r e a ( c ) + 入1 i 札o ( z ，y ) 一c l l 2 d x d y ( 2 2 0 ) - 4 - 入2 i u o ( z ，y ) 一c 2 1 2 d x d y 这里l e n g t h ( c ) 表示边界曲线c 的长度，a r e a ( c ) 表示曲线c 内部区域的面积p20 ，2 0 ，入1 ，入2 o 是固定参数，一般取= 0 ，入1 = 入2 = 1 u ： 口忧7 _ a g e ( u o ) ，妇试ec；(221) u2 l 【a v e r a g e ( u o ) ，o u t s i d ec 7 ( 2 2 0 ) 分割问题可以用变分水平集方法解，为了建立变分水平集模型，c h a n 和v e s e 芒j i a , th e a v i s i d e 数日( z ) 及d i r a c 测度南，于是有 l e n g t h ( 妒= 0 ) = 南( ( z ，剪) ) l v ( z ，y ) l d x d y a r e a ( 0 ) = 日( ( z ，y ) ) d x d y 厶。( 训) 咱1 2 d x d y = f a i u 如，沪c l l 2 日( m ，跏如咖 m o ( z ，) 一c 2 1 2 d x d y = m o ( z ，) 一c 21 2 ( 1 一h ( ，y ) ) ) d x d y ，西 _ 7 6 ， l ( c ，a ) = f ( c ，) + a k ( ) d x + 等k 2 ( ) d z ( 3 7 ) 丽c o l ：o ，瓦o l ：0 ， ( 3 8 ) 一= 一= i - 可童 i 二x l a 西v p g u ” 、“。， 筹= 【u 一( u 。一叫嚣一p 壹i v 两可+ 入丽+ 删7 ( 3 9 ) 要：鬲鬲dz：m-1甜，z：v妒厶i,u0妒一i(u。一okol o u o f o u d u ) m 如 ( 3 1 0 ) 瓦2 厶瓦石妃2 厶抛秽q z 2 厶【u 一( u o u ) j 他如 1 0 ) 1 9 河南大学硕士学位论文 首先由( 3 1 0 ) 式知道( 3 2 ) 关于c 的极小化满足线性方程组a c = 6 ，即 ，n 五善( 蝴) c j d x = f n ( u 0 - - v 触江1 j 2 ， ( 3 1 1 ) 这里a 巧= ( 他，c a l 。( n ) ，b = ( ( u o u ) ，也) l z ( q ) 由以上分析，我们给出m s d m 的增广乘 子( a u g m e n t e dl a g r a n g e ，a l ) 算法，具体如下： 1 ) 赋初值西o ，v 0 2 ) 由( 3 1 1 ) 式迭代母 3 ) 由u = c ；砒( 扩- 1 ) 更新札；用( 3 5 ) 式更新钉 t = 1 4 ) 迭代扩，具体求解见3 3 节 r 5 ) 由u = c ；f k 他( 扩) 更新u ；用( 3 5 ) 式更新 4 = 1 6 ) 由( 3 1 2 ) 式迭代出妒，重复步骤2 ) 一6 ) 直到收敛或达到最大迭代次数为止 对于l ( c ，a ) 只要取足够大的惩罚因子p ，不必趋向无穷大，就可通过极小化l ( c ，入) 求得问题( 3 2 ) 的局部最优解 如果知道最优乘子”，只要取充分大的惩罚因子“，不需要趋向无穷大，就能通过 极小化l ( c ，入+ ) 求出问题( 3 7 ) 的解，但是最优乘子a + 事先不知道，研究怎样确定a ，一 般方法先给定充分大的p 和拉格朗日乘子的初始估计a o ，然后在迭代过程中用( 3 1 2 ) 修 正入，力图使入趋向入+ 入= 妒一1 十矿一1 k ( 扩)( 3 1 2 ) 如果入缸不收敛，或者收敛太慢，则增大参数肛，再进行迭代，收敛快慢用踹来 衡量时间迭代步长丁在梯度迭代过程中依赖于p ，大的p 需要小的丁，大的p 使水平集函 数咖收敛于i 更快选择p 太大将影响保真项，因此要想收敛到真解需要增加迭代次数 3 2 算子分裂 水平集方法是探测交界面问题的有效工具，但是导致了方程求解的数值计算复 杂度增加为了能够提高计算速度，许多学者进行了研究s e t h i a n 提出求解h a m i l t o n - j a c o b i 方程边值问题的快速步进法 4 2 ，d c h o p 提出的窄带法 4 0 ，多重网格方法【4 1 都 是提高数值计算速度及收敛性的方法我们这里重点介绍算子分裂方法 河南大学硕士学位论文 十九世纪五十年代，d o u g l a s ，p e a c e m a n $ 1 j r a c h f o r d 在用差分法求解椭圆方程和抛 物方程时提出了交替方向迭代法后来苏联数学家m a r c h u k 和y a n e n k o 提出了称为局 部一维方向方法t a i t f l n e i t t e m n m a k i 4 3 ，【4