




已阅读5页,还剩46页未读, 继续免费阅读
(数学专业论文)非结构网格下曲线演化的水平集方法及其应用.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
国防科学技术大学研究牛院硕十学位论文 摘要 科学技术的发展日新月异,也给数值计算模拟提出了越来越高的要求。随着 图像处理中研究问题规模的扩大,实际应用迫切需要计算数学为其提供准确、高 效和实用的数值计算工具。与此同时,水平集方法作为一种强有力的数学工具, 除了广泛地应用于计算流体力学等领域之外,也逐渐受到图像处理工作者们的重 视,成为求解图像偏微分方程的一种新兴的数值方法。本文考虑曲线演化模型, 特别是非结构网格下曲线演化的水平集解法,结合曲线演化理论和水平集方法, 将半隐式格式引入模型数值求解,从而弥补了传统模型在图像处理问题中存在的 不足,同时提高了计算的效率,做了一些有意义的尝试。 1 、研究曲线演化的水平集模型,包括曲线自然演化模型、改进的曲线沿指定 靶曲线演化的模型、非结构网格的数值计算等。由于非结构网格的几何贴体性和 自适应性,使得本文构造的方法适用于处理复杂曲线的演化,初步的数值结果表 明了方法的可行性。 2 、根据二维情况下曲线的非结构网格表示,通过基于d e l a u n a y 三角化和 v o r o n o i 图的方法,将其推广到三维的曲面重构中。根据给定的满足采样密度的样 本点,生成了分片线性光滑的曲面三角形网格。 3 、将水平集方法与曲线演化理论相结合,应用到具体的图像处理问题:图像 复原与图像分割。其主要思想是以偏微分方程的变分方法为手段,引入曲线的水 平集函数表示,将图像总变分和曲线能量化为水平集方程,即一类曲线演化方程, 在此基础上采用数值算法对模型进行求解。一方面,对于图像复原的总变分模型, 通过添加边缘算子,使得模型能够自适应的去除噪声且较好的保持图像边缘;另 一方面,对于图像分割的经典模型,采用一种半隐式格式对其进行数值求解,提 高了计算的效率。 格式 主题词:曲线演化水平集方法非结构网格图像复原 图像分割半隐式 第i 页 国防科学技术大学研究生院硕十学位论文 a b s t r a c t t h er a p i dd e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g yb r i n g s i n c r e a s i n gi n t e r e s ti n n u m e r i c a lc o m p u t a t i o n a st h em a g n i t u d eo fp r o b l e m ss t u d i e di n i m a g es c i e n c e b e c o m e sl a r g e r ,t h e r ei sa l l u r g e n tr e q u i r e m e n t i n p r a c t i c e t h a t c o m p u t a t i o n a l m a t h e m a t i c ss h o u l dp r o v i d ea c c u r a t e ,e f f i c i e n ta n de a s y u s en u m e r i c a lt o o l st os i m u l a t e a n da n a l y s i si m a g e m e a n w h i l e ,t h el e v e ls e tm e t h o d ,a sa p o w e r f u lm a t h e m a t i c a lt o o l 。 a t t r a c t sm u c hm o r ea t t e n t i o no fr e s e a r c h e r si n i m a g ep r o c e s s i n g i th a sb e c o m ea t h r i v i n gt e c h n i q u ei ns o l v i n gp a r t i a ld i f f e r e n t i a le q u a t i o n sb a s e da p p l i c a t i o n si ni m a g e p r o c e s s i n g i nt h i sp a p e r ,l e v e ls e tm e t h o df o rc u r v ee v o l u t i o n ,e s p e c i a l l yl e v e ls e t m e t a m o r p h o s i sm e t h o do nu n s t r u c t u r e dm e s h e s ,a r ec o n s i d e r e d i ti sw e l lk n o w nt h a t t h em o d e lo fc u r v ee v o l u t i o nh a v ea p p e a r e di nt h ey o u n gf i e l do fi m a g ep r o c e s s i n g m o r er e c e n t l y ,s u c ha si m a g er e s t o r a t i o na n di m a g es e g m e n t a t i o n t h el e v e lc u r v ew i t h s h a r pe d g e sb r i n g sn u m e r i c a ld i f f i c u l t i e st oc l a s s i c a lm a t h e m a t i c s o u rm e t h o di st o c o m b i n et h ec u r v ee v o l u t i o nt h e o r ya n dt h el e v e ls e tm e t h o d ,a n du s eae f f i c i e n t s e m i - i m p l i c i tn u m e r i c a ls c h e m ef o ri t si m p l e m e n t a t i o n o u rm a i nw o r k sa r e : a t h et h e o r yo fc u r v ee v o h t i o n w eu s et h ef i n i t ev o l u m em e t h o do nu n s t r u c t u r e d m e s h e sf o rt h en a t u r a le v o l u t i o nm o d e la n dt h ei m p r o v e dm o d e l d u et ot h ea d v a n c e o fu n s t r u c t u r e dm e s h e si ng e o m e t r i ca d a p t i v i t y ,t h en e ws c h e m e sc a nh a n d l ew i t ht h e c u r v ew i t hc o m p l e xg e o m e t r y f e a s i b i l i t yi sp r o v e db yp r e l i m i n a r yn u m e r i c a lr e s u l t s b b a s e do nt h em e t h o do fc u r v er e c o n s t r u c t i o n u s i n gu n s t r u c t u r e dm e s h e s ,w e r e c o n s t r u c tat r i a n g u l a t e ds u r f a c eu s i n gd e l a u n a yt r i a n g u l a t i o na n dv o r o n o id i a g r a m s t h ec o n s t r u c t e ds u r f a c ei sp i e c e w i s el i n e a r c w em a k ee f f o r t sw h i c hc o m b i n et h el e v e ls e tm e t h o da n dt h ec u r v ee v o l u t i o nt h e o r y t oa c c o m p l i s hs p e c i a lt a s k s ,s u c ha si m a g er e s t o r a t i o na n di m a g es e g m e n t a t i o n w e n o t i c et h a ti ns o m eo ft h ea b o v ea p p l i c a t i o n s ,t h ep d e st h a tg o v e r nt h em o t i o no f t h e i n t e r f a c ec a nb ed e r i v e df r o mav a r i a t i o n a lp r i n c i p l e o nt h eo n e1 1 a n d ,南rt h et o t a l v a r i a t i o n a li m a g er e s t o r a t i o nm o d e l ,w ea d da ne d g eo p e r a t o rw h i c hm a k et h em o d e li s a d a p t a t i v et or e m o v et h en o i s ea n dm a i n t a i nt h ee d g e ;o nt h eo t h e rh a n d ,w eu s eas e m i - i m p l i c i ts c h e m ef o rt h en u m e r i c a lc o m p u t a t i o no ft h ec l a s s i c a lm o d e lo fi m a g e s e g m e n t a t i o n k e yw o r d s :c u r v ee v o l u t i o n l e v e ls e tm e t h o du n s t r u c t u r e dm e s h e si m a g e r e s t o r a t i o n i m a g es e g m e n t a t i o n s e m i i m p l i c i ts c h e m e 第i i 页 国防科学技术大学研究生院硕十学位论文 表 目录 表2 1 非结构网格的节点数和三角形网格数1 8 表3 1 峰值信噪比比较( d b ) 2 9 表4 1 能量变分的水平集形式3 7 表4 2c v 模型的时间对比( 秒) 3 9 表4 3g a c 模型的时间对比( 秒) 一4 0 第1 i i 页 国防科学技术大学研究生院硕十学位论文 图目录 图2 1d i r i c h l e t 棋格l5 图2 2圆曲线的非结构网格生成与加密1 7 图2 3复杂几何外形曲线的非结构网格生成与加密1 7 图2 4 非洲大陆的曲线演化1 8 图2 5 兔子曲线的演化过程1 9 图2 6 茶壶曲线的演化曲线1 9 图2 7 头骨模型曲面重构2 0 图2 8 油井模型曲面重构2 0 图2 9 大象模型曲面重构2 1 图2 1 0 兔子模型曲面重构2 l 图3 1l e n a 图像去噪效果一2 9 图3 2c a m e r a m a n 图像测试效果3 0 图3 3 乘性噪声模型去噪效果3 l 图4 1c v 模型迎风差分方法3 8 图4 2c v 模型半隐式格式3 9 图4 3g a c 模型迎风差分格式一4 0 图4 4g a c 模型半隐式格式一4 0 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含 其他人已经发表和撰写过的研究成果,也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目:韭结捡圆整王些线渲他鲍壅壬篡友洼丞墓应用 学位论文作者签名:百- _ 书 日期:。o7 年f k 月。了日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档,允许论文被查阅和借阅;可以将学位论文的全部或部分内容编入有关数据 库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目: 韭箜掐圆整王些绫渲焦鲍盔垩篡虚洼丞基座周 学位论文作者签名:;堑:益日期:7 年f2 月7 日 作者指导教师签名:! 圣丝塾日期:2 i j f 年f 2 月0 了日 国防科学技术大学研究生院硕+ 学位论文 第一章绪论 1 1问题背景 图像处理和计算机视觉是认知科学与计算机领域中的一个活跃分支,该领域 是2 0 世纪6 0 年代随着计算机的产生和发展形成的新兴的学科,经历了7 0 年代人 们对其兴趣的爆炸性增长之后,在8 0 到9 0 年代逐步走向成熟。在当今的信息社 会( i n f o r m a t i o ns o c i e t y ) 中,图像已成为一种有效的被广泛使用的交流信息的媒介, 同时也成为人们表达现实世界的主要方式之一,图像处理及其应用越来越多的影 响着人们的生活:图像捕捉和数字转换技术使得电视、电影走进了我们的日常生 活;医学成像技术使得人们可以采取更科学的技术手段进行手术和治疗;图像在 仿真与建模的应用使得人工智能有了长足的发展;图像自动监视技术和指纹识别 技术在信息安全方面也扮演着越来越重要的角色自从6 0 年代简单的数字技术 应用于灰度图像处理以来,认知设备的进步带来越来越丰富的可使用的巨大的数 字信息,而计算机的发展则带给人们越来越强的处理海量数据的能力,这些都使 得人们不断探索和发展图像处理和理解的更复杂的数学方法和框架,越来越多的 数学理论成为处理和理解图像的工具,如统计学、图论、调和分析、偏微分方程 方法等等。图像处理的数学模型大致可以分为:基于马尔可夫随机过程理论的概 率统计模型【1j 【2 j ;依赖于分解技术的小波理谢3 】【4 】;基于变分理论的偏微分方程方 法。随着数值分析技术的发展和计算物理在图像处理中的逐步应用,基于变分理 论的偏微分方程方法越来越成为处理图像的重要工具,目前各国都把图像处理的 偏微分方程方法放在非常重要的地位来发展。 图像处理的偏微分方程方法是从大约2 0 世纪9 0 年代开始,并迅速发展起来 的一个新兴交叉学科分支。它继承了偏微分方程已经形成的完整的理论体系和数 值方法,又得益于传统图像处理技术所积累的经验,所以不仅在许多经典的图像 处理课题中,如图像滤波、图像分割和图像复原等,显示出强大的生命力,并且 还提出了一些新的课题,如仿射不变性特征提取和图像纹理分析等。建立合乎处 理要求的偏微分方程的方法1 5 j 主要有: ( 1 ) 通过变分原理将图像处理中涉及一系列未知变量的最优化问题转化为相 应的偏微分方程,进行数值求解。如:测地线活动轮廓模型( g a c ) t 6 j 将分割问题归 结于封闭曲线的能量泛函的最小化问题。 ( 2 ) 将所期望实现的图像变化与某种物理过程进行类比,建立相应的模型。如: p e r o n a 和m a l i k 将图像滤波问题与物理扩散和热传导过程相比较,建立起各向同性 非线性的p m 扩散方程1 7 j 。 第1 页 国防科学技术大学研究生院硕十学位论文 在图像处理方面,与传统的方法相比,偏微分方程方法在理沦和计算方面具 有如下特点: 1 ) 图像偏微分方程方法在连续的区域上进行图像建模,图像像素被表示为连续函 数在网格上的采样点,与图像处理过程相对应的算子直接作用在连续函数上; 2 ) 某像素值在当前时间的变化仅仅依赖于该像素的一个小领域内的像素值,使得 偏微分方程方法具有较强的连续性和局部自适应性; 3 ) 图像的偏微分方程模型易于修改和扩充,易于得到性能更完善或应用更广的模 型,如二维向三维推广,单值图像向矢量图像推广等; 4 ) 借助于偏微分方程的数值分析理论,目前偏微分方程数值求解已经有很多成熟 的算法,粘性解理论提供了用于图像处理的偏微分方程的严格的理论基础。 曲线演化理论利用曲线的法矢量和曲率等几何参数研究曲线随时间的变化, 不仅应用在微分几何领域的极小化曲面问题的理论分析,也用来模拟许多以曲率 运动为模型的自然现象,如晶体增长、火焰燃烧等,近年来,曲线演化理论在图 像处理领域也得到了实际应用,如图像去噪、图像分割等,在实践运用中,这些 模型和方法的核心都归结于界面的演化问题,而水平集方法正是解决这一问题的 最强有力的数学工具! 水平集( l e v e l s e t ) 方法是由s e t h i a n 和o s h e r 于1 9 8 8 年提出 8 1 ,用于解决基于 描述火苗外形的热力学方程,许多科学工程问题都可以归结于追踪运动界面问题, 能够处理复杂的几何拓扑变换和数值计算容易平行向高维推广的优点赋予了水平 集方法强大的生命力,使水平集方法进入了一个快速发展时期,水平集方法现在 已广泛应用于计算流体力学、材料科学、光学设计、图像处理和计算机视觉等领 域。水平集方法处理界面问题的最大的优势是对于运动界面和曲线演化问题,水 平集方法都将其转化为一类偏微分方程:h a m i l t o n - j a c o b i 方程【9 1 。h j 方程来源于 最优控制、微分几何等学科,近年来不断在新的领域得到应用。h j 方程的解的性 质非常复杂,一方面h j 方程的弱解存在但不唯一,另一方面即使初值和h a m i l t o n 函数足够光滑,其解的导数也可能会在某一时刻出现间断,导致解曲面出现尖点 或纽结等现象,因此寻求高分辨、高精度的数值方法也是我们研究的一个很重要 的问题。同时,在数值方法发展的同时,科学家们渐渐的发现网格技术对偏微分 方程的数值解的精确性起着和数值方法同样的决定性作用。对于实际问题,数值 方法精度再高,如果网格条件与问题不匹配,那么得到的数值解也会有很大的误 差,尤其是偏微分方程数值解越来越广泛应用于各种大型的工程问题和军事项目 中,所考虑的实际问题难度越来越大,研究的物理模型越来越复杂,因此网格技 术的研究也渐渐的成为偏微分方程数值解研究的另外一个热点。通常用到的网格 有两种类型,结构网格和非结构网格。结构网格对简单几何区域可直接生成,具 第2 页 国防科学技术人学研究生院硕十学何论文 有正规的网格编号,排列有序,凶此数据结构简单,在结构网格上易于发展数值 算法,算法易于向量化等等。然而,对于较复杂的计算区域,生成几何贴体的结 构网格是非常困难的,而非结构网格有着灵活、易于处理复杂计算区域、易于自 适应等优点,近年来得到广泛的关注。目前对水平集方法的研究,大部分基于结 构网格,采用有限差分方法计算,基于非结构网格的水平集方法的研究还不是很 充分,因此,对基于非结构网格下的水平集方法【lo j 进行研究是很有必要的。水平集 方法与曲线演化理论的结合,极大地推动了其在图像处理领域的发展。 图像处理中的一个重要问题是如何以观测图像为已知数据来恢复反映客观世 界真实场景的原始图像。图像复原就是利用导致图形退化的先验知识,建立图像 退化的数学模型。然后沿着图像退化的逆过程进行恢复,已获得清晰地原始图像, 进而能够使我们能够正确理解图像蕴含的信息,或被其他图像分析方法进行后处 理。图像去模糊和图像去噪是图像复原中的两个主要问题,传统的图像复原方法【l l j 大致可分为逆滤波法、代数方法和空域滤波方法。传统的图像复原算法面临着高 维方程的计算问题,而且缺乏完整的理论基础和统一的设计方法,近年来发展起 来的偏微分方程图像处理技术为图像复原的研究和发展注入了新的活力。在图像 复原中使用偏微分的思想可以追溯到g a b o r 的工作【1 2 j 和j a i n 1 3 j 的研究,随后, k o e n d e r 砒【1 4 】和w i t k i n i l 5 】引入了尺度空间的概念,使得偏微分方程技术的发展得 到了实际性的进展,p e r o n a 和m a l i k 的有关各向异性扩散的文章,对图像处理的偏 微分方程方法做出了重大贡献,并吸引了许多研究者对图像处理偏微分方程方法 进行更深入的研究,在同样的框架下,r u d i n 、o s h e r 和f a t e i n i 【1 6 j 提出了基于全变 分的去噪模型,显示了偏微分方程在图像复原领域中的必要性和重要性。 图像处理中的另一个重要问题是图像分割,其目的是希望将图像中感兴趣的 对象与图像中的其余部分相分离,以便为后续的更高层的图像处理服务,图像分 割的质量的优劣、区域界限定位的精度都将直接影响后续的区域描述以及图像的 分析和理解。目前,有许多图像分割方法,如基于阈值分割方法、基于区域提取 的分割方法、基于边缘检测的分割方法等,基于偏微分方程的图像分割方法是图 像分割领域中的一个重要分支,1 9 9 3 年c a s e l l e s 等人首次将水平集方法应用于图 像处理和计算机视觉【1 7 】,他们用水平集函数来表示轮廓线,将一个平面上的曲线 表示为一个二元函数( 五y ) 的零值集合 矽= 0 ,通过引入变分水平集方法对能量 模型进行极小化,改进了初始s n a k e 模型依赖于曲线几何形状和位置参数的缺点, 进而得到了不依赖于参数的g a c 模型。由于g a c 模型难以分割既没有明显边缘 也缺乏明显纹理特征的图像,c h a n 和v e s e l l 8 】提出了无边缘轮廓( c v ) 模型,在此 基础上m u m f o r m 和s h a h i w j 提出了m s 模型同时实现图像的平滑和分割。 多尺度分析方法近年来成功的运用于许多图像处理领域,如小波分析成功应 第3 页 国防科学技术大学研究生院硕十学位论文 用于图像压缩、多重例格方法应用于图像偏微分方程方法等。由于水半集方法将n 维曲面问题转化为n + i 维的水平集方程的数值求解问题,在更高一维的空间中计 算增加了问题的复杂度,而且在具体实现的过程中,还有一些步骤,如符号距离 函数的重新初始化和初始速度的延拓等问题,都使得计算量大大增加,影响了计 算的效率。2 0 0 3 年w e i n a n 和e n g q u i s t 提出了设计多尺度模型的一类方法 z o l ( h e t e r o g e n e r o u sm u l t i s c a l em e t h o d s ) ,已经在解决复杂流动、扰流、界面问题和 随机问题等方面展现出强大的潜力,一类多尺度水平集方法( h m m 1 e v e ls e tm e t h o d ) 也已经成功应用于界面问题中,其具有的局部化性质使得水平集模型在全局计算 区域得到了很大程度的简化,正如t s a i 和o s h e r 在他们的文章指出【2 i l : “m u l t i s c a l e l e v e ls e tm e t h o dw i l lb eu s e f u li nm o d e l i n gi m a g es e q u e n c e st h a ta r eo b t a i n 丘o mh i g h l yn o i s ym e d i a ” 1 2 本文的主要工作 鉴于以上讨论,我们做了以下工作: 第二章研究了曲线演化的水平集模型,包括曲线自然演化模型、改进的曲线 沿指定靶曲线演化的模型、非结构网格的数值计算等。选择非结构网格的有限体 积法,并将其用于求解模型。由于非结构网格的几何贴体性和自适应性,使得本 文构造的方法适用于处理复杂曲线的演化,初步的数值结果表明了方法的可行性。 根据二维情况下曲线的非结构网格表示, 的方法,将其推广到三维的曲面重构中。 成了分片光滑的曲面三角形网格。 通过基于d e l a u n a y 三角化和v o r o n o i 图 根据给定的满足采样密度的样本点,生 第三章研究了图像复原的总变分模型,对于图像加性噪声模型,通过添加边 缘算子,使得模型能够自适应的去除噪声且较好的保持图像边缘;对于乘性噪声 模型,通过在变分过程中添加约束条件,使得改进的总变分模型能够较好的处理 图像乘性噪声。 第四章将水平集方法与曲线演化理论相结合,研究了图像分割的经典模型, 以曲线能量变分出发,引入曲线的水平集函数表示,将曲线能量变分化为水平集 函数的能量,推导出分割曲线的演化方程,采用一种半隐式格式对其进行数值求 解,提高了计算的效率。 第4 页 国防科学技术人学研究生院硕十学位论文 第二章曲线演化的水平集方法 2 1引言 曲线演化,特别是平面封闭曲线c 的曲率运动,通常被描述为: _ o c :g ( r ) ( 2 1 ) 西 、7、 其中r 和分别是曲线c 的曲率和法向量,意味着吐线上的任意点以曲率函 数g ( 彭) 为速度沿法向运动,这一方程广泛应用于微分几何领域的曲面极小化问 题,同时,也应用于由内在能量驱动的界面运动问题,如火焰外延模拟,溶化问 题和晶体增长等,近年来在图像处理领域也展现了强大的生命力。曲线演化的方 法通常分为参数化方法和无参数方法:参数化方法通过采集曲线上的一些特征点 来表示曲线,将曲线演化问题转化为特征点的对应问题和路径问题,直接用有限 差分方法计算,运算量通常较小,但是,在曲线演化过程中,当曲线形状发生较 大的拓扑变换时,参数化方法需要对曲线重新进行参数化,而且点的路径不唯一 也会导致演化问题的不适定;无参数方法不依赖任何参数,可以灵活处理几何拓 扑变换,其算法的稳定性更容易得到证明,也更容易向高维情形推广,水平集方 法就是典型的一种无参数方法。 水平集方法是一种基于h a m i l t o n - j a c o b i 方程的追踪运动界面的数值方法,它 是处理封闭运动界面随时问演化过程中几何拓扑变化的有效的计算工具,目前已 成为计算流体力学问题、图像处理和计算机视觉的数值计算、数值模拟中的一个 重要方法。为了解决复杂几何拓扑变化的参数化计算的困难,水平集方法通过构 造高一维的水平集函数的零等值面来表示运动界面,通过变分原理得到驱动曲线 演化的水平集函数的偏微分方程,代替参数化的几何拓扑变化,其基本思想是: 对于给定的光滑的封闭曲线,定义光滑的( 至少l i p s c h i t z 连续) 的函数矽( x ,y ,t ) ,将 曲线表示为水平集函数的零值面 矽( x ,y ,f ) = 0 ,初始水平集函数具有符号距离函 数的性质: 矽( x ,y ,) = 这一性质使得封闭曲线由外部到内部的函数值是单调的,有利于数值计算的 稳定性。假设曲线运动的法向速率为,则曲线运动描述为水平集方程: 第5 页 ,厶1 、l 2西 c ;一c = 萑 坛比 协 0 0 r 。 = y y y x x x 矗y矗p 国防科学技术大学研究生院硕十学位论文 型+ v v :0 (23)o 二t + v j 。v 妒。 ( 2 3 ) 此类方程属于h a m i l t o n - j a c o b i 方程,c r a n d a l l 和l i o n s 在1 9 8 3 年对h - j 方程 引入了粘性解概念和粘性上下俐2 2 1 方法,使h - j 方程的研究得到了蓬勃发展,完 备的粘性解理论保证了水平集方程数值解的唯一性和精确性,通过有限体积法离 散可以方便地利用各种类型的网格( 结构网格和非结构网格) ,适用于复杂几何 形状的求解区域。水平集方法的优点是:第一,水平集模型能够自动处理拓扑变 化,容易推广到三维问题中;第二,可以由高维水平集函数性质推出相应的低维 的曲线或曲面的性质;第三,使用曲线的隐式表达,可以简单有效地计算曲线的 几何量如法向量和曲率。现有的水平集方法大多是基于结构网格上求解水平集方 程,通过结构网格点上水平集函数离散值的插值来描述曲线,曲线的几何度量由 曲线两侧的网格点的差分格式计算,这种方法的优点是求解水平集方程的差分格 式易于编程,而且解的收敛性、稳定性在现有的理论框架下都有很强的保证,方 法本身可以达到很高的精度。但是,真实的曲线边界点大部分不会落在网格点上, 所以结构网格下用网格点的插值方法模拟曲线运动以及计算曲线法向速率和曲率 时均会带来很大的误差,大大降低方法整体的精度,而在非结构网格下求解水平 集方法很好的解决了这一问题,由于非结构网格具有很好的几何贴体性质和自适 应性质,其几何贴体性质既保证了网格可以刻画任意复杂边界的曲线,也保证了 曲线边界落在网格点上,大大减少了由边界两侧网格点插值计算带来的误差;同 时,水平集方法主要通过边界附近窄带内的网格点进行计算,而非结构网格的自 适应性质可以通过下分子网格的方法,对边界附近的网格进行加密,计算时只采 用子网格内的网格点,减少了因采用非结构网格带来的计算量。 下一节从曲线的基本性质出发,通过曲线的水平集函数表示,将曲线运动过 程化为水平集函数的数值求解过程,在非结构网格的基础上对方程进行了数值求 解。 2 2曲线演化的水平集模型 2 2 1曲线微分几何性质 本节给出曲线及其几何特征的的定义和性质。 定义2 2 1 ( 曲线) :给定口,b 吼且a o v x q b ( 2 1 9 ) 如( x ) o 其它 过渡中的曲线围成的区域q ,与q b 相交的面积& 。,g : & 嘏= j ( x ) 出 ( 2 2 0 ) 因为符号距离函数:倪2 专吼在q 曰内为正,在q 8 外为负,所以当面积分& 。,q 达 到最大值时: 最= a r g m a x1 7 口。、出(221maxi x ) ) 6 。i7 口 黜 lj 磊 得到q 。= q 8 ,可以证明当源曲线变化到靶曲线时达到稳定状态2 3 1 。下面考虑在出 时间内面积的变化: ,( x ) 出= ,( x ) 出+ ,( x ) ( x ) 出+ ,( x ) r ( x ) - ( x ) 出 ( 2 2 2 ) 其中第一项为t 时刻过渡曲线围成的面积分,第二项为曲线沿法向运动衍时间后 面积分的变化量,第三项为在曲线几何曲率影响下面积分的变化量,:专,2 为 边界点的法向量,r ( x ) 为边界点的曲率。边界位置的变化量为: d s = ( x ) n ( x ) + t s ( x ) 誓( x ) n ( x ) ( 2 2 3 ) 通过求导可以得到边界上点的运动方程: 等= ( ,( ,) ) ( ,( ,) ) + 儿( ,( ,) ) r ( ,( f ) ) ( ,( f ) ) v ,( ,) ( 2 2 4 ) 这个方程描述了在每一个时间步长a c t 内,边界上的每一点在边界法向和曲率 的影响下移动的方向以及在符号距离函数大小控制下移动的距离,水平集模型用 符号距离函数矽的零等值面来表示边界点集,考虑边界上的每个点,( ,) 的运动,得 到水平集方程: 掣删( m 抄) 掣:。 ( 2 2 5 ) 6 t l 、r m 、。 在上式中代入曲线的几何量: = 外批v ( 矽1 ( 2 2 6 ) 得到新的方程: 第9 页 国防科学技术大学研究生院硕十学位论文 考= m 秘( ,) ( 2 2 7 ) 代入式( 2 2 4 ) 得到描述曲线运动的改进水平集模型: 掣:1 w ( x ) 1 ( x ) + ( x ) 酬v 俐 ( 2 2 8 ) 随着曲线在不断演化,初始的水平集函数会偏离符号距离函数的值,所以在 水平集方程的求解过程中,需要周期性的重构水平集函数矽,使其保持符号距离函 数的性质,s u s s m a n , s m c r e k a 和o s h e r 2 4 1 将这一过程转化为重构方程: 破+ s ( 唬) ( 1 v i _ 1 ) = 0 ( 2 2 9 ) 其中s ( 丸) 是符号函数: il ,唬q + s ( 丸) = o ,唬孢 ( 2 3 0 ) l _ 1 ,死q 一 通过数值解求解重构方程,在理论上保证了水平集函数为符号距离函数,但 是数值扰动会一定程度上影响最终的结果。其次,方程( 2 1 5 ) 的速度矿是曲线演化 的速度,即仅仅定义在曲线上,在数值求解水平集方程的过程中,需要每个网格 点的y 都是已知的,所以需要一种有效的速度延拓的方法,通常在曲线演化问题 中,曲线的演化仅取决于曲线的几何性质,而不涉及一般的物理界面的演化问题, 所以一般采用自然延拓的方法,即假定给定的曲线运动方程不仅对嵌入函数的零 水平集成立,而且对于嵌入函数的所有水平集均成立,但从数值计算的时间来看, 这一方法的效率较低,为了克服以上问题,我们提出了非结构网格下的求解曲线 演化的水平集方法。 2 3 非结构网格下求解水平集模型的数值方法 在上节中,通过曲线的水平集表示,将曲线演化过程转化为水平集方程,本 节主要介绍在非结构网格下求解水平集方程的算法,首先简要介绍求解 h a m i l t o n - j a c o b i 方程的粘性解理论和非结构网格的有限体积方法。在此基础上构造 了非结构网格下的数值求解格式 2 3 1 粘性解理论 考虑2 维h j 方程初值问题 v t + h 、( v v ) = 、0 ,旌r 2 b o ( 2 3 1 ) i v ( x ,o ) = v o ( x ) 、 第l o 页 国防科学技术火学研究生院硕士学位论文 粘性解【2 5 】有多种定义,这里给出一种比较简单的定义: 定义3 2 ( 粘性解) : v u ( x ,) c 1 ( r 2 ( 0 ,o o ) ) ,v ( x o ,o ) 1 、若v u 在( ,气) 达到局部极大值,且有 u , ( x o ,f o ) + h ( u ,( x o ,岛) ) 0 2 、若1 ,一u 在( ,) 达到局部极小值,且有 u , ( x o ,岛) + h ( u ,( x o ,t o ) ) 0 则称v ( x ,f ) 为h j 方程的粘性解。 与式( 2 3 1 ) 对应的粘性方程为: i + 1 - i ( v ;) = 吒, i v ( x ,o ) = v o ( x ) 由于方程( 2 3 4 ) 是抛物型方程,其解存在、唯一并存在较好的正则性。 带粘性项方程的解,当占一0 ,粘性方程的解一致收敛到v ( x ,f ) ,即: ( 2 3 2 ) ( 2 3 3 ) ( 2 3 4 ) 设1 l ,5 为下述 v ( x ,) = l i m v 5 ( x ,f ) ( 2 3 5 ) e u 对于一般的h a m i l t o n - j a c o b i 方程,添加粘性项的主要目的是抑制数值振荡, 但是人工粘性过大,会成为影响格式误差的一大因素。由于h j 方程和双曲型守 恒律方程之间有着非常密切的关系:对于一维问题,将守恒律方程积分一次,得 到h j 方程;对于高维问题,h j 方程与弱守恒律方程等价,所以借鉴守恒律方程 的性质和数值格式的构造方法可以得到h j 方程的高阶的数值格式。 2 3 2 结构网格下的数值方法 考虑二维空间中的h a m i l t o n - j a c o b i 方程: 譬+ 日( x ,y ,纯,矽,) = 0 ( 2 3 6 ) 其中h ( x ,y ,t ,苁,) = 0 为h a m i l t o n 函数,吮、力分别是( x ,y ,) 在x 方向和y 方向上的偏导数。为了求解上述方程,先要离散计算区域,将x 方向和y 方向上 的网格宽度分别取为缸和缈,用( 薯,y f ) 来表示节点( i ,j ) 的坐标值,同时取时间 步长为a t ,用饬= 矽( 一,y ,广) 来表示在节点( f ,) 上广时刻矽的函数值,并在x 和 y 方向上引入如下差分算子: 鹤= c t n l , j 妃,圮2 既一啦u ( 2 3 7 ) ;筑= 筑+ 。一纪,;虼= 够一躬一t 方程( 2 ) 的一阶向前e u l e r 时间离散格式为: 第l1 页 国防科学技术大学研究生院硕十学位论文 型筹:一台( _ , ,妃,蟛,x , l , j ,蛾,) ( 2 3 8 ) 其中日( 薯,y j ,蟛,塌,嵫,昵,坛,) 是h a m i l t o n 函数h ( x ,y ,f ,织,丸) = o 的数 值近似,称为数值h a m i l t o n 函数,一般是l i p s c h i t z 连续和单调的,并满足连续性 条件: h ( x ,y ,f ,甜,z ,) = h ( x ,y ,“,v ,)( 2 3 9 ) 通常采用t v dr u n g e k u t t a 方法来提高求解过程中时间的离散精度,t v d r u n g e k u t t a 方法对传统的r u n g e k u t t a 方法进行改造,使其权系数均为正数,以 避免数值解过程中产生多余的振荡,第n 步的二阶t v dr u n g e k u t t a 方法为: ”“= ”+ fh ”+ i = 矽”+ 等 台”+ 台肿1 2 4 。 2 3 3 非结构网格下的数值方法 有限体积方法从控制体的积分形式出发,对求解区域的剖分同有限元方法一 样具有单元特征,能适应复杂的求解区域,离散方法又具有差分方法的灵活性、 间断解的适应性。有限体积法从积分守恒形式出发,采用单元剖分,选择控制原 离散,通过引用以r i e m a n n 问题近似解为基础的数值流通量,可以很好地处理非 线性守恒律问题等。与有限差分、有限元等方法的最大区别就在于,有限体积方 法将求解域内的计算转化到控制体边界上进行计算,而有限差分、有限元均是直 接( 或间接) 在域内计算。正是基于这一点,有限体积方法有着明确的物理涵义, 并可在很大程度上减少计算工作量又能满足计算精度要求,它综合了有限元法和 有限差分方法的优点,具有有限元法几何上的灵活性和有限差分方法在规定离散 流动变量方面的灵活性,可看作是有限元方法和有限差分方法之外的第三类方法。 从有限体积法的离散思想显见它自动满足离散守恒律,因而是守恒律的一种最自 然的离散方法。更重要的是它可以方便地利用各种类型的网格( 结构网格和非结 构网格) ,从而适用于复杂几何形状的求解区域,特别是非结构网格有限体积方 法易于高精度的处理边界条件,易于实现网格的自适应局部加密,虽然编程比较 复杂,计算量较大,但随着计算机软件和硬件性能的的飞速发展,非结构网格有 限体积方法取得了很大发展,目前已成为数值模拟复杂、高速流动的重要方法。 下面利用守恒律方程的数值格式构造方法和非结构网格有限体积方法求解在 上文中建立的曲线演化的水平集模型。我们考虑扩展的水平集模型,即曲线演化 第1 2 页 国防科学技术大学研究生院硕十学位论文 不仪与法向速度有关,与曲线本身的儿伺性质曲翠也自关: 谚+ 网矽= k i v 矽i ( 2 4 1 ) 3 - 程( 2 4 1 ) 为退化的抛物形方程,也可以用粘性解理论求解。将方程重写为: 谚+ 日( v ) = k l v 矽i ( 2 4 2 ) 设封闭曲线围成的区域为q ,我们采取时间与空间分开的处理的方法。 网格剖分:将求解区域q 进行三角网格剖分瓦,记 z i f _ l ,2 ,n 为节点为f 为顶 点的三角形,_ + ! 为沿三角形单元乃与乃+ - 公共边方向向外的单位矢量。 ( 1 ) 空问离散: ( i ) 数值h a m i l t o n 量重构: 通常选用低阶单调流通量形式:l a x f r i e d r i c h s 流通量【2 6 1 : 锄( 华,华h 华h 华丁 亿4 3 , 其中口。= m a x ,( 丸,办) l ,口,= m a x i ( 破,办) i r o e - f i x 流通量【2 7 】: 锄( “卜。( 华h 盟2 亿4 4 , 其柑= m a x l ( 丸槲儿一办) i ,= 鼢务= 协翁 用e n o 方法选择插值模板对单元构造2 阶多项式: p 小叩2 篡x 砂iy i 刚) = f 2 。i + 口4 帆 ( 2 4 5 ) i蠢( p 7 ( i i ) 抛物瓠阿l 臌理当矽黼别睛醐时,虮卸t 尚户1 w i _ 1 可 以得到: 茁i v 矽l = 矽 ( 2 4 6 ) 通过中心差分格式求解。 ( 3 ) 时间离散:用t v d 型r u n g e k u t t
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年急诊急救技术应用专项能力测试(ECMO护理)考核试卷
- 制造业供应链数字化供应商合作模式考核试卷
- 2025年房地产行业工程质量风险防控能力考核试卷
- 2025年度建筑行业市场调控政策考核试卷
- 重难点解析人教版八年级物理上册第4章光现象综合测试试题(解析卷)
- 操盘合同(标准版)
- 浙江省文化产业投资集团招聘考试真题2024
- 泉州市泉港区粮食购销有限公司招聘考试真题2024
- 考点解析-人教版八年级上册物理《物态变化》重点解析练习题(含答案详解)
- 2025煤矿企业主要负责人考试安全生产知识和管理能力自测试题及答案
- 《TCSUS69-2024智慧水务技术标准》
- 2025年医师定期考核临床专业知识考试试题+答案
- 交通银行2025秋招无领导小组面试案例库吉林地区
- 孵化器行业培训课件
- 造纸厂成品库管理细则
- 角膜捐献接受管理办法
- 《宪法是根本法》课件
- 国有企业十五五人力资源规划框架
- 医院护理人文关怀实践规范专家共识
- 2025金融工作会议考试题及答案
- 2025年注册安全工程师考试化工(初级)安全生产实务试卷与参考答案
评论
0/150
提交评论