非结构网格下曲线演化的水平集方法及其应用
|
摘要
科学技术的发展日新月异,也给数值计算模拟提出了越来越高的要求。随着图像处理中研究问题规模的扩大,实际应用迫切需要计算数学为其提供准确、高效和实用的数值计算工具。与此同时,水平集方法作为一种强有力的数学工具,除了广泛地应用于计算流体力学等领域之外,也逐渐受到图像处理工作者们的重视,成为求解图像偏微分方程的一种新兴的数值方法。本文考虑曲线演化模型,特别是非结构网格下曲线演化的水平集解法,结合曲线演化理论和水平集方法,将半隐式格式引入模型数值求解,从而弥补了传统模型在图像处理问题中存在的不足,同时提高了计算的效率,做了一些有意义的尝试。
1、研究曲线演化的水平集模型,包括曲线自然演化模型、改进的曲线沿指定靶曲线演化的模型、非结构网格的数值计算等。由于非结构网格的几何贴体性和自适应性,使得本文构造的方法适用于处理复杂曲线的演化,初步的数值结果表明了方法的可行性。
2、根据二维情况下曲线的非结构网格表示,通过基于Delaunay三角化和Voronoi图的方法,将其推广到三维的曲面重构中。根据给定的满足采样密度的样本点,生成了分片线性光滑的曲面三角形网格。
3、将水平集方法与曲线演化理论相结合,应用到具体的图像处理问题:图像复原与图像分割。其主要思想是以偏微分方程的变分方法为手段,引入曲线的水平集函数表示,将图像总变分和曲线能量化为水平集方程,即一类曲线演化方程,在此基础上采用数值算法对模型进行求解。一方面,对于图像复原的总变分模型,通过添加边缘算子,使得模型能够自适应的去除噪声且较好的保持图像边缘;另一方面,对于图像分割的经典模型,采用一种半隐式格式对其进行数值求解,提高了计算的效率。
The rapid development of science and technology brings increasing interest in numerical computation.As the magnitude of problems studied in image science becomes larger , there is an urgent requirement in practice that computational mathematics should provide accurate,efficient and easy-use numerical tools to simulate and analysis image.Meanwhile,the level set method,as a powerful mathematical tool, attracts much more attention of researchers in image processing.It has become a thriving technique in solving partial differential equations based applications in image processing.In this paper,level set method for curve evolution,especially level Set metamorphosis method on unstructured meshes,are considered.It is well known that the model of curve evolution have appeared in the young field of image processing more recently,such as image restoration and image segmentation.The level curve with sharp edges brings numerical difficulties to classical mathematics.Our method is to combine the curve evolution theory and the level set method,and use a efficient semi-implicit numerical scheme for its implementation.Our main works are:
a.The theory of curve evolution.We use the finite volume method on unstructured meshes for the natural evolution model and the improved model.Due to the advance of Unstructured Meshes in geometric adaptivity,the new schemes can handle with the curve with complex geometry.Feasibility is proved by preliminary numerical results.
b.Based on the method of curve reconstruction using unstructured meshes,we reconstruct a triangulated surface using Delaunay triangulation and Voronoi diagrams. The constructed surface is piecewise linear.
c.We make efforts which combine the level set method and the curve evolution theory to accomplish special tasks,such as image restoration and image segmentation.We notice that in some of the above applications,the PDEs that govern the motion of the interface can be derived from a variational principle.On the one hand,for the total variational image restoration model,we add an edge operator which make the model is adaptative to remove the noise and maintain the edge;on the other hand,we use a semi - implicit scheme for the numerical computation of the classical model of image segmentation.
1、研究曲线演化的水平集模型,包括曲线自然演化模型、改进的曲线沿指定靶曲线演化的模型、非结构网格的数值计算等。由于非结构网格的几何贴体性和自适应性,使得本文构造的方法适用于处理复杂曲线的演化,初步的数值结果表明了方法的可行性。
2、根据二维情况下曲线的非结构网格表示,通过基于Delaunay三角化和Voronoi图的方法,将其推广到三维的曲面重构中。根据给定的满足采样密度的样本点,生成了分片线性光滑的曲面三角形网格。
3、将水平集方法与曲线演化理论相结合,应用到具体的图像处理问题:图像复原与图像分割。其主要思想是以偏微分方程的变分方法为手段,引入曲线的水平集函数表示,将图像总变分和曲线能量化为水平集方程,即一类曲线演化方程,在此基础上采用数值算法对模型进行求解。一方面,对于图像复原的总变分模型,通过添加边缘算子,使得模型能够自适应的去除噪声且较好的保持图像边缘;另一方面,对于图像分割的经典模型,采用一种半隐式格式对其进行数值求解,提高了计算的效率。
The rapid development of science and technology brings increasing interest in numerical computation.As the magnitude of problems studied in image science becomes larger , there is an urgent requirement in practice that computational mathematics should provide accurate,efficient and easy-use numerical tools to simulate and analysis image.Meanwhile,the level set method,as a powerful mathematical tool, attracts much more attention of researchers in image processing.It has become a thriving technique in solving partial differential equations based applications in image processing.In this paper,level set method for curve evolution,especially level Set metamorphosis method on unstructured meshes,are considered.It is well known that the model of curve evolution have appeared in the young field of image processing more recently,such as image restoration and image segmentation.The level curve with sharp edges brings numerical difficulties to classical mathematics.Our method is to combine the curve evolution theory and the level set method,and use a efficient semi-implicit numerical scheme for its implementation.Our main works are:
a.The theory of curve evolution.We use the finite volume method on unstructured meshes for the natural evolution model and the improved model.Due to the advance of Unstructured Meshes in geometric adaptivity,the new schemes can handle with the curve with complex geometry.Feasibility is proved by preliminary numerical results.
b.Based on the method of curve reconstruction using unstructured meshes,we reconstruct a triangulated surface using Delaunay triangulation and Voronoi diagrams. The constructed surface is piecewise linear.
c.We make efforts which combine the level set method and the curve evolution theory to accomplish special tasks,such as image restoration and image segmentation.We notice that in some of the above applications,the PDEs that govern the motion of the interface can be derived from a variational principle.On the one hand,for the total variational image restoration model,we add an edge operator which make the model is adaptative to remove the noise and maintain the edge;on the other hand,we use a semi - implicit scheme for the numerical computation of the classical model of image segmentation.
引文
[1] S Z Li.Markov Random Field Modeling in Computer Vision[M].London: Springer-Verlag,1995:15-16
[2] S Geman,D Geman.Stochastic relaxation, Gibbs distributions, and the Bayesian res- -toration of images[J].IEEE Transactions on Pattern Anaalysis and Machine Intelli- -gence ,1984,6(6):721-741
[3] S Mallat.A Wavelet Tour of Signal Processing[M].Academic Press,1998:12-14
[4] A Chambolle,R A DeVore,N Y Lee,B J Lucier.Nonliner wavelet image processing variational problems,compression and noise removal through wavelet shrinkage[J]. IEEE Transaction on Image Processing,1998,7(3):319-334
[5]王大凯,侯榆青,彭进业.图像处理的偏微分方程方法[M].北京:科学出版社,2008
[6] Caselles V,Morel J M,Sapiro G.Geodesic active contours[J].Int.Journal of Comput- -ational Vision, 1997,22:61-79
[7] Perona P,Malik J.Scale space and edge detection using anisotropicdiffusion[J].IEEE PAMI,1990,12:629-639
[8] Osher S,Sethian J A.Fronts propagating with curvature-dependent speed:algorithms based on Hamilton-Jacobi formulations[J].Journal of Computational Physics, 1988, 79:12-49
[9] Crandall M,Lions P.Viscosity solutions of Hamilton-Jacobi equations[J].Trans. Am er.Math. Sec 1983,277:1-42
[10]张军,赵宁,谭俊杰,任登凤,王莎.Level set方法在非结构网格上的应用[J].自然科学进展,2007,17:29-33
[11]吴斌,吴亚东,张红英.基于变分偏微分方程的图像复原技术[M].北京:北京大学出版社,2008:15-20
[12] Gabor D.Information theory in electron microscopy Laboratory Investigation[R]. 1965,14:801-807
[13] Jain A K.Partial differential equations and finite-difference methods in image processing,partI:image representation[J].Optimization theory and Applications 1977,23:65-91
[14] Koenderink J J.The structure of images Biological Cybernetics[R].1984,50:363-370
[15] Witkin A P.Scale-space filtering[C].In Proceedings 8th International Joint Conference on Artifical Intelligence,1983,2:1019-1021
[16] L Rudin,S Osher,E Fatemi.Nonlinear Total Variation Based Noise Removal[J]. Physica D,1992,60:259-268
[17] Caselles V,Catte F,Coll T, Dibos F.A Geometric Model for Active Contour in Image Processing[J].Numerische Mathematik ,1993,66:1-31
[18] Chan T F.Active contours without edges[C].CAM Report UCLA,1998:98-53
[19] Morse B S,Schwartzwald D.Image magnification using level-set reconstruction[C]. Computer Vision and Pattern Recognition,2001:11-14
[20] Weinan E ,Bjorn Engquist.The heterogeneous multi-scale methods[C].UCLA CAM Report02(15),2002
[21] Richard Tsai ,Stanley Osher.Level set method and their applications in Image Scie- nce[M].London:Springer,2003
[22] Crandall M ,Lions P.Viscosity solutions of Hamilton-Jacobi equations[J].Trans Am er.Math,1983,277:1-42
[23] Breen D E,Whitaker R T.A level-set approach for the metamorphosis of solid mod- els[J].IEEE Transactions on Visualization and Computer Graphics,2001,7(2): 173- 192
[24] Sussman M,Smereka P ,Osher S.An Level Set Approach for Computing Solutions to Incompressible Two-Phase Flow[J].Journal of Computational Physics,1994,114: 146-159
[25] Crandall M ,Lions P L.Two Approximations of Solutions of Hamilton-Jacobi Equa- tions[J].Math,Soc,1983,277:1-42
[26] Oshe S ,Shu C W.High Order Essentially Non-Oscillatory Schemes for Hamilton-J- acobi Equations[J].SIAM.J.Mumer.Anal,1991,28:902-921
[27] Harten A,Engquist B,Osher S ,Chakravarthy S.Uniformly High-Order Accurate Es- sentially Non-Oscillatory Schemes III[J].Journal of Computational Physics, 1987, 71:231-303
[28] Shu C W,Osher S.Efficient Implementation of Essentially Non-Oscillatory Shock Comput Schemes[J].Journal of Computational Physics,1988,77:439-471
[29] Nina Amenta,Marshall Bern.Surface reconstruction by Voronoi filtering[C].To appear in 14th ACM Symposium on Computation Geometry,1998
[30] H Hoppe,T DeRose,T Duchamp,J McDonald ,W Stuetzle.Surface Reconstruction from Unorganized Points[C].In SIGGRAPH Proceedings,1992: 71-78
[31]徐国良.计算几何中的偏微分方程方法[M].北京:科学出版社,2008:291-294
[32] L Rudin,S Osher,E Fatemi.Nonlinear Total Variation Based Noise Removal [J]. Physica D,1992,60:259-268
[33] E Cole.The Removal of Unknown Image Blurs by Homomorphic Filtering[C], Te- chnical Report .Department of Electrical Engineering.University of Toroto.1973
[34] Kass M,Witkin A,Terzopolos D.Snake:active contour models[J].Journal of Comp- utational Vision,1988,(1):321-331
[35] Chan T F,Vese L.Active contours without edges[C]CAM Report,1998:98-53
[36] Morse B S,Schwartzwald D.Image magnification using level-set reconstruction[C]. Computer Vison and Pattern Recognition,2001:21:24
[37] Caselles V,Catte F,Coll T, Dibos F.A geometric model for active contours[J]. Numer Math,1993:14-16
[38] Osher S,Fedkiw R.Level Set Methods and Dynamic Implicit Surfaces[M].New York:Springer,2003
[2] S Geman,D Geman.Stochastic relaxation, Gibbs distributions, and the Bayesian res- -toration of images[J].IEEE Transactions on Pattern Anaalysis and Machine Intelli- -gence ,1984,6(6):721-741
[3] S Mallat.A Wavelet Tour of Signal Processing[M].Academic Press,1998:12-14
[4] A Chambolle,R A DeVore,N Y Lee,B J Lucier.Nonliner wavelet image processing variational problems,compression and noise removal through wavelet shrinkage[J]. IEEE Transaction on Image Processing,1998,7(3):319-334
[5]王大凯,侯榆青,彭进业.图像处理的偏微分方程方法[M].北京:科学出版社,2008
[6] Caselles V,Morel J M,Sapiro G.Geodesic active contours[J].Int.Journal of Comput- -ational Vision, 1997,22:61-79
[7] Perona P,Malik J.Scale space and edge detection using anisotropicdiffusion[J].IEEE PAMI,1990,12:629-639
[8] Osher S,Sethian J A.Fronts propagating with curvature-dependent speed:algorithms based on Hamilton-Jacobi formulations[J].Journal of Computational Physics, 1988, 79:12-49
[9] Crandall M,Lions P.Viscosity solutions of Hamilton-Jacobi equations[J].Trans. Am er.Math. Sec 1983,277:1-42
[10]张军,赵宁,谭俊杰,任登凤,王莎.Level set方法在非结构网格上的应用[J].自然科学进展,2007,17:29-33
[11]吴斌,吴亚东,张红英.基于变分偏微分方程的图像复原技术[M].北京:北京大学出版社,2008:15-20
[12] Gabor D.Information theory in electron microscopy Laboratory Investigation[R]. 1965,14:801-807
[13] Jain A K.Partial differential equations and finite-difference methods in image processing,partI:image representation[J].Optimization theory and Applications 1977,23:65-91
[14] Koenderink J J.The structure of images Biological Cybernetics[R].1984,50:363-370
[15] Witkin A P.Scale-space filtering[C].In Proceedings 8th International Joint Conference on Artifical Intelligence,1983,2:1019-1021
[16] L Rudin,S Osher,E Fatemi.Nonlinear Total Variation Based Noise Removal[J]. Physica D,1992,60:259-268
[17] Caselles V,Catte F,Coll T, Dibos F.A Geometric Model for Active Contour in Image Processing[J].Numerische Mathematik ,1993,66:1-31
[18] Chan T F.Active contours without edges[C].CAM Report UCLA,1998:98-53
[19] Morse B S,Schwartzwald D.Image magnification using level-set reconstruction[C]. Computer Vision and Pattern Recognition,2001:11-14
[20] Weinan E ,Bjorn Engquist.The heterogeneous multi-scale methods[C].UCLA CAM Report02(15),2002
[21] Richard Tsai ,Stanley Osher.Level set method and their applications in Image Scie- nce[M].London:Springer,2003
[22] Crandall M ,Lions P.Viscosity solutions of Hamilton-Jacobi equations[J].Trans Am er.Math,1983,277:1-42
[23] Breen D E,Whitaker R T.A level-set approach for the metamorphosis of solid mod- els[J].IEEE Transactions on Visualization and Computer Graphics,2001,7(2): 173- 192
[24] Sussman M,Smereka P ,Osher S.An Level Set Approach for Computing Solutions to Incompressible Two-Phase Flow[J].Journal of Computational Physics,1994,114: 146-159
[25] Crandall M ,Lions P L.Two Approximations of Solutions of Hamilton-Jacobi Equa- tions[J].Math,Soc,1983,277:1-42
[26] Oshe S ,Shu C W.High Order Essentially Non-Oscillatory Schemes for Hamilton-J- acobi Equations[J].SIAM.J.Mumer.Anal,1991,28:902-921
[27] Harten A,Engquist B,Osher S ,Chakravarthy S.Uniformly High-Order Accurate Es- sentially Non-Oscillatory Schemes III[J].Journal of Computational Physics, 1987, 71:231-303
[28] Shu C W,Osher S.Efficient Implementation of Essentially Non-Oscillatory Shock Comput Schemes[J].Journal of Computational Physics,1988,77:439-471
[29] Nina Amenta,Marshall Bern.Surface reconstruction by Voronoi filtering[C].To appear in 14th ACM Symposium on Computation Geometry,1998
[30] H Hoppe,T DeRose,T Duchamp,J McDonald ,W Stuetzle.Surface Reconstruction from Unorganized Points[C].In SIGGRAPH Proceedings,1992: 71-78
[31]徐国良.计算几何中的偏微分方程方法[M].北京:科学出版社,2008:291-294
[32] L Rudin,S Osher,E Fatemi.Nonlinear Total Variation Based Noise Removal [J]. Physica D,1992,60:259-268
[33] E Cole.The Removal of Unknown Image Blurs by Homomorphic Filtering[C], Te- chnical Report .Department of Electrical Engineering.University of Toroto.1973
[34] Kass M,Witkin A,Terzopolos D.Snake:active contour models[J].Journal of Comp- utational Vision,1988,(1):321-331
[35] Chan T F,Vese L.Active contours without edges[C]CAM Report,1998:98-53
[36] Morse B S,Schwartzwald D.Image magnification using level-set reconstruction[C]. Computer Vison and Pattern Recognition,2001:21:24
[37] Caselles V,Catte F,Coll T, Dibos F.A geometric model for active contours[J]. Numer Math,1993:14-16
[38] Osher S,Fedkiw R.Level Set Methods and Dynamic Implicit Surfaces[M].New York:Springer,2003