基于散乱数据的曲面插值与逼近若干方法研究
|
摘要
基于大规模散乱数据的插值或拟合方法,在很多领域都有重要的应用。所以长期以
来,都有很多学者从事这方面的研究,并且发展和形成了许多方法。本文主要是针对其
中的若干常用方法,提出一些改进办法。同时结合实例比较,证明改进后的算法在计算
复杂度或拟合质量等方面较原来的方法有了较大的提高。
第一章主要改进了Shepard插值方法。对于常用的Shepard方法,一般地认为,其权
函数的光滑性和衰减性越好,曲面的拟合效果就越好。该章结合截断多项式、B样条基
函数和指数函数来构造其权函数,使新的权函数具有更高的光滑度和更好的衰减性,并
且其光滑性和衰减性可以根据实际需要自由调节。从而提高了曲面的拟合质量。通过大
量的实例表明,运用改进的方法得到的曲面确实比用原先的算法得到的曲面无论从光滑
性和光顺性上都有了较大的提高。同时该方法还可用于修正的Shepard方法等。
第二章主要给出了一个基于径向基(非局部支集)的局部插值方法。用径向基(非
局部支集)插值,随着型值点数量的增加,其系数矩阵的阶数以及条件数也迅速增大,
从而给计算带来不便。在本章中,结合多元样条的思想,给出了一个使径向基插值局部
化的算法。该算法较好地继承了径向基插值曲面的性质,从而保证了拟合曲面具有好地
光顺性和拟合精度。曲面片之间的光滑性可以灵活选择。算法构造简单,计算方便,具
有较强的实用性。文中数值实例也表明运用分片局部化算法,在计算效率上有了很大的
提高,尤其是在型值点数量较大的情况下。而曲面拟合质量与直接用径向基插值得到的
曲面具有可比性。
第三章主要用参数曲面-NURBS拟合散乱数据。该章首先推广了文献的结果,
将文献中关于B样条曲线曲面拟合数据点的迭代算法推广至有理形式,给出了无需
求解方程组反求控制点即可得到拟合NURBS曲线曲面的迭代方法。该算法和文献的
算法本质上是统一的,而后者恰是前者的一种退化形式。同时本章还给出了收敛性证明
以及一些定性分析。另外结合前两章的内容,对文献提出的用NURBS曲面拟合散乱
数据的抽样网格方法作了适当的改进,提高了算法运算效率,并对曲面拟合质量也有一
定的提高。同时还提出一种基于散乱数据的均匀网格抽样方法。由于均匀网格适宜参数
化,所以更便于NURBS拟合。
本文运用了大量实例来验证算法,都收到了比较好的效果。
The problem of constructing approximations based upon scattered data are encountered in many areas of scientific applications, like meteorological information, such as the amount of rainfall, or geological information, such as depth of underground formmations. This is done using interpolation techniques that estimate value on unexplored points of a region considering the values sampled on it. The main work of this thesis is to improve some approximation methods that are often used in practice. With the numerical examples, we prove the improved methods .are more convenient to compute or have more approximate quality.In chapter 1, with regard to the Shepard method, we use the truncated polynomials, the B-spline basis functions and exponential functions to construct the weight functions. They are of better properties of smoothness and decay, which can be adjusted freely. And so the surface can be fitted better by the improved method. It also can be applied in modified Shepard Mehthod[5].In practice, interpolation methods of radial basis functions are often required for approximation with very large number of data, in which the interpolation matrix is usually ill-conditioned. In order to solve this problem, we construct a localized method for interpolation with radial basis functions (global supported) based on the idea of multivariate spline. Moreover, we verify that this method is feasible through theoretic analysis and numerical experiments. These methods perform almost as good as the global supported radial basis functions interpolation methods do.In chapter 3, we use NURBS to approximate the scattered data. Paper[20]gave out the iterative algorithm of B-spline interpolation and approximation. In this chapter,we generalize this result and present an iterative algorithm of NURBS interpolation and approximation. Using this algorithm, we can get the approximat NURBS curve or surface directly without solving a linear system to compute the weights and control points. This algorithm is consistent with the algorithm in paper [20] and the latter is just the degenerate form of the former in essence.Furthermore, using the new methods introduced in former chapters, we improve the NURBS approximation method given out in paper[21], and then the computing is simpler. We also present an approach for scattered sampling and uniform mesh generation. Since the uniform mesh is easy to be parameterized.this approach is more convenient to be used. .The numerical examples in this thesis show us these methods are feasible, and the results are satisfying.
来,都有很多学者从事这方面的研究,并且发展和形成了许多方法。本文主要是针对其
中的若干常用方法,提出一些改进办法。同时结合实例比较,证明改进后的算法在计算
复杂度或拟合质量等方面较原来的方法有了较大的提高。
第一章主要改进了Shepard插值方法。对于常用的Shepard方法,一般地认为,其权
函数的光滑性和衰减性越好,曲面的拟合效果就越好。该章结合截断多项式、B样条基
函数和指数函数来构造其权函数,使新的权函数具有更高的光滑度和更好的衰减性,并
且其光滑性和衰减性可以根据实际需要自由调节。从而提高了曲面的拟合质量。通过大
量的实例表明,运用改进的方法得到的曲面确实比用原先的算法得到的曲面无论从光滑
性和光顺性上都有了较大的提高。同时该方法还可用于修正的Shepard方法等。
第二章主要给出了一个基于径向基(非局部支集)的局部插值方法。用径向基(非
局部支集)插值,随着型值点数量的增加,其系数矩阵的阶数以及条件数也迅速增大,
从而给计算带来不便。在本章中,结合多元样条的思想,给出了一个使径向基插值局部
化的算法。该算法较好地继承了径向基插值曲面的性质,从而保证了拟合曲面具有好地
光顺性和拟合精度。曲面片之间的光滑性可以灵活选择。算法构造简单,计算方便,具
有较强的实用性。文中数值实例也表明运用分片局部化算法,在计算效率上有了很大的
提高,尤其是在型值点数量较大的情况下。而曲面拟合质量与直接用径向基插值得到的
曲面具有可比性。
第三章主要用参数曲面-NURBS拟合散乱数据。该章首先推广了文献的结果,
将文献中关于B样条曲线曲面拟合数据点的迭代算法推广至有理形式,给出了无需
求解方程组反求控制点即可得到拟合NURBS曲线曲面的迭代方法。该算法和文献的
算法本质上是统一的,而后者恰是前者的一种退化形式。同时本章还给出了收敛性证明
以及一些定性分析。另外结合前两章的内容,对文献提出的用NURBS曲面拟合散乱
数据的抽样网格方法作了适当的改进,提高了算法运算效率,并对曲面拟合质量也有一
定的提高。同时还提出一种基于散乱数据的均匀网格抽样方法。由于均匀网格适宜参数
化,所以更便于NURBS拟合。
本文运用了大量实例来验证算法,都收到了比较好的效果。
The problem of constructing approximations based upon scattered data are encountered in many areas of scientific applications, like meteorological information, such as the amount of rainfall, or geological information, such as depth of underground formmations. This is done using interpolation techniques that estimate value on unexplored points of a region considering the values sampled on it. The main work of this thesis is to improve some approximation methods that are often used in practice. With the numerical examples, we prove the improved methods .are more convenient to compute or have more approximate quality.In chapter 1, with regard to the Shepard method, we use the truncated polynomials, the B-spline basis functions and exponential functions to construct the weight functions. They are of better properties of smoothness and decay, which can be adjusted freely. And so the surface can be fitted better by the improved method. It also can be applied in modified Shepard Mehthod[5].In practice, interpolation methods of radial basis functions are often required for approximation with very large number of data, in which the interpolation matrix is usually ill-conditioned. In order to solve this problem, we construct a localized method for interpolation with radial basis functions (global supported) based on the idea of multivariate spline. Moreover, we verify that this method is feasible through theoretic analysis and numerical experiments. These methods perform almost as good as the global supported radial basis functions interpolation methods do.In chapter 3, we use NURBS to approximate the scattered data. Paper[20]gave out the iterative algorithm of B-spline interpolation and approximation. In this chapter,we generalize this result and present an iterative algorithm of NURBS interpolation and approximation. Using this algorithm, we can get the approximat NURBS curve or surface directly without solving a linear system to compute the weights and control points. This algorithm is consistent with the algorithm in paper [20] and the latter is just the degenerate form of the former in essence.Furthermore, using the new methods introduced in former chapters, we improve the NURBS approximation method given out in paper[21], and then the computing is simpler. We also present an approach for scattered sampling and uniform mesh generation. Since the uniform mesh is easy to be parameterized.this approach is more convenient to be used. .The numerical examples in this thesis show us these methods are feasible, and the results are satisfying.
引文
[1] Richard Franke. Scattered data interpolation: Tests of some methods. Mathematic of Computation, 1982, 38(157) : 181-200.
[2] 黄友谦.曲线曲面的数值表示和逼近.上海:上海科学技术出版社,1984.
[3] Nie Hui, Zeng Long, Luo Xiao-nan, A partial approximation Shepard Method based on cardinal spline about messy data. Journal of Mathematical Research and Exposition, 2003, 23(2) : 237-240.
[4] Richard Franke, Greg Nielson. Smooth interpolation of large sets of scattered data. International Journal for Numerical Methods In Engineering, 1980, 15: 1691-1704.
[5] Karen Basso, Paulo Ricardo De Avila Zingano, Carla Maria Dal Sasso Freitas. Interpolation of scattered data: Investigating alternatives for the Modified Shepard Method. Ⅻ Brazilian Symposium on Computer Graphics and Image Processing, 1999, 10: 17-20.
[6] 王仁宏.数值逼近.北京:高等教育出版社,1999.
[7] 吴宗敏.径向基函数、散乱数据拟合与无网格偏微分方程数值解.工程数学学报,2002, 19(2) :1-12.
[8] 吴宗敏.函数的径向基表示.数学进展,1998,27(3) :202-208.
[9] 王仁宏.多元样条函数及其应用.北京:高等教育出版社,1994.
[10] H.Wendland. Piecewise polynomial positive definite and compactly supported radial basis functions of minimal degree[J]. Adv.Comput.Math.,1995, 4: 389-396.
[11] Z.M.Wu. Compactly supported positive definite radial function[J]. Adv.Comput. Math., 1995, 4: 283-292.
[12] Robert Schaback, z.Wu. Operaters on radial functions. Jounal of Computational and Applied Mathematics, 1996, 73: 257-270.
[13] Damiana Lazzaro, Laura B. Montefusco, Radial basis function for the multivatiate interpolation of large scattered data sets. Jounal of Computational and Applied Mathematics, 2002, 140: 521-536.
[14] G.A.Anastassion, S.G.Gal. Partial shape preserving approximations by bivariate shep ard operators. Computer and Mathematics Application. 2001, 42: 47-56.
[15] Charles A.Micchelli. Interpolation of sacttered data:distance matrics and conditionally positive definite functions. Constructive Approximation, 1986, 2:11-22.
[16] Aurelian Bejiancu, Jr. Local accuracy for radial basis function interpolation on finite uniform grids. Journal of Approximation Theory, 1999, 99: 242-257.
[17] Colin Bradley, Geoffrey W Vickers, etal.Free-form surface reconstruction for machine vision rapid prototyping.Optical Engineering, 1993, 32(9) : 2191-2200.
[18] M.D.Buhmann, Radial Basis Functions: Theory and Implementations. Cambridge University PRESS, 2003.
[19] Francis J.Narcowich, Joseph D.Ward. Norms of inverses and condition numbers for matrices associated with scattered data. Journal of Approximation theory, 1991, 64: 69-94.
[20] 蔺宏伟,王国瑾,董辰世.用迭代非均匀B-spline曲线曲面拟合给定点集.中国科学 (E辑),2003,33(10) :912-923.
[21] 来新民,黄田,曾子平,林忠钦.基于NURBS的散乱数据点自由曲面重构.计算机辅助 设计与图形学学报,1999,11(5) :433-436.
[22] Li S Z. Adaptive sampling and mesh generation. Computer Aided Design, 1995, 27(3) : 235-240.
[23] Weiyin Ma, J P Kruth. Parameterization of randomly measured points for least squares fitting of B-spline curves and surface. Computer-Aided Design, 1995, 27(9) : 663-675.
[24] L.A.Piegl, W.Tiller. Parametrization for surface fitting in reverse engineering. Computer Aided Design, 2001, 33: 593-603.
[25] 施法中.计算机辅助几何设计与非均匀有理B样条.北京:北京航空航天大学出版社, 1993.
[26] L.A.Piegl, W.Tiller. The NURBS Book. New York: Springer, 1997.
[27] 齐东旭,田自贤,张玉心等.曲线拟合的数值磨光方法.数学学报,1975,18(3) :173-184.
[28] 齐东旭.关于计算机辅助几何造型中数学方法的若干注记.北方工业大学学报,1991, 3(1) :1-8.
[29] de Boor. How does agree's smoothing method work. In:Proceedings of the 1979 Army Numerical Analysis and Conmputers Conference, ARO Report 79-3, Army Research Office, 1979, 199-320.
[30] de Boor C. A Practical Guide to Splines. New York: Springer-Verlag, 1978.
[31] de Boor C. Total positicity of the spline collocation matrix. Indiana University Mathematics Journal, 1976, 25(6) : 541-551.
[32] Loe K F. α-β-spline: A linear singular blending B-spline.The Visual Computer,1996, 12:18-25.
[33] 陈景良,陈向晖.特殊矩阵.北京:清华大学出版社,2001,370-371;429-430.
[34] Piegl, L. On NURBS: A Survey, IEEE CG&A, 1991, 1: 55-71.
[35] Rolland L. Hardy, Dr.-Ing. Research results in the application of Multiquadric equation to surveying and mapping problem. Surveying and Mapping, 1975, 35: 321-332
[36] 彭群生,胡国飞.三角网格参数化.计算机辅助设计与图形学学报,2004,16(6) :732-739.
[37] Floater M S. Parametrization and smooth approximation of the face triangulations [J]. Computer Aided Geometric Design, 1997, 14(3) : 231-250.
[38] Floater M S, Reimers M. Meshless parametrization and surface reconstruction [J]. Computer Aided Geometric Design, 2001, 18(2) : 77-92.
[39] 陈志杨,李江雄,柯映林.反求工程中的曲面重建技术.汽车工程,2000,22(157) : 365-367.
[40] Hugues Hoppe, Tony DeRose, Tom Duchamp. Surface reconstruction from unorgnized points. Computer Graphics (SIGGRAPH'92 Proceedings) 1992, 26(2) :71-78.
[41] 周海,周来水,王占东等.散乱数据点的细分曲面重建算法实现.计算机辅助设计与图 形学学报,2003,15(10) :1287-1292.
[42] Suzuki H, Takeuchi S, Kanai T. Subdivision surafce fitting to a range of points[A]. In: Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, Seoul, Korea, 1999, 365-367.
[43] Loop C. Smooth subdivision surfaces based on triangles[D].Utah:University of Utah, 1987.
[44] Luiz Velho, Denis Zorin. 4-8 Subdivision. Computer Aided Geometric Design, 2001, 18: 397-427.
[45] J Warren. Subdivision methods for geometric design[D]. Rice university, 1995.
[46] Ma, W., Zhao N. Catmull-Clark surface fitting for reverse engineering applications. Geometric Modeling and Processing 2000, Theory and Applications. Proceedings, 2000, 274-283.
[47] 韩力文,周蕴时.曲线与曲面的细分算法.计算技术与自动化,2002,21(3) :20-22.
[2] 黄友谦.曲线曲面的数值表示和逼近.上海:上海科学技术出版社,1984.
[3] Nie Hui, Zeng Long, Luo Xiao-nan, A partial approximation Shepard Method based on cardinal spline about messy data. Journal of Mathematical Research and Exposition, 2003, 23(2) : 237-240.
[4] Richard Franke, Greg Nielson. Smooth interpolation of large sets of scattered data. International Journal for Numerical Methods In Engineering, 1980, 15: 1691-1704.
[5] Karen Basso, Paulo Ricardo De Avila Zingano, Carla Maria Dal Sasso Freitas. Interpolation of scattered data: Investigating alternatives for the Modified Shepard Method. Ⅻ Brazilian Symposium on Computer Graphics and Image Processing, 1999, 10: 17-20.
[6] 王仁宏.数值逼近.北京:高等教育出版社,1999.
[7] 吴宗敏.径向基函数、散乱数据拟合与无网格偏微分方程数值解.工程数学学报,2002, 19(2) :1-12.
[8] 吴宗敏.函数的径向基表示.数学进展,1998,27(3) :202-208.
[9] 王仁宏.多元样条函数及其应用.北京:高等教育出版社,1994.
[10] H.Wendland. Piecewise polynomial positive definite and compactly supported radial basis functions of minimal degree[J]. Adv.Comput.Math.,1995, 4: 389-396.
[11] Z.M.Wu. Compactly supported positive definite radial function[J]. Adv.Comput. Math., 1995, 4: 283-292.
[12] Robert Schaback, z.Wu. Operaters on radial functions. Jounal of Computational and Applied Mathematics, 1996, 73: 257-270.
[13] Damiana Lazzaro, Laura B. Montefusco, Radial basis function for the multivatiate interpolation of large scattered data sets. Jounal of Computational and Applied Mathematics, 2002, 140: 521-536.
[14] G.A.Anastassion, S.G.Gal. Partial shape preserving approximations by bivariate shep ard operators. Computer and Mathematics Application. 2001, 42: 47-56.
[15] Charles A.Micchelli. Interpolation of sacttered data:distance matrics and conditionally positive definite functions. Constructive Approximation, 1986, 2:11-22.
[16] Aurelian Bejiancu, Jr. Local accuracy for radial basis function interpolation on finite uniform grids. Journal of Approximation Theory, 1999, 99: 242-257.
[17] Colin Bradley, Geoffrey W Vickers, etal.Free-form surface reconstruction for machine vision rapid prototyping.Optical Engineering, 1993, 32(9) : 2191-2200.
[18] M.D.Buhmann, Radial Basis Functions: Theory and Implementations. Cambridge University PRESS, 2003.
[19] Francis J.Narcowich, Joseph D.Ward. Norms of inverses and condition numbers for matrices associated with scattered data. Journal of Approximation theory, 1991, 64: 69-94.
[20] 蔺宏伟,王国瑾,董辰世.用迭代非均匀B-spline曲线曲面拟合给定点集.中国科学 (E辑),2003,33(10) :912-923.
[21] 来新民,黄田,曾子平,林忠钦.基于NURBS的散乱数据点自由曲面重构.计算机辅助 设计与图形学学报,1999,11(5) :433-436.
[22] Li S Z. Adaptive sampling and mesh generation. Computer Aided Design, 1995, 27(3) : 235-240.
[23] Weiyin Ma, J P Kruth. Parameterization of randomly measured points for least squares fitting of B-spline curves and surface. Computer-Aided Design, 1995, 27(9) : 663-675.
[24] L.A.Piegl, W.Tiller. Parametrization for surface fitting in reverse engineering. Computer Aided Design, 2001, 33: 593-603.
[25] 施法中.计算机辅助几何设计与非均匀有理B样条.北京:北京航空航天大学出版社, 1993.
[26] L.A.Piegl, W.Tiller. The NURBS Book. New York: Springer, 1997.
[27] 齐东旭,田自贤,张玉心等.曲线拟合的数值磨光方法.数学学报,1975,18(3) :173-184.
[28] 齐东旭.关于计算机辅助几何造型中数学方法的若干注记.北方工业大学学报,1991, 3(1) :1-8.
[29] de Boor. How does agree's smoothing method work. In:Proceedings of the 1979 Army Numerical Analysis and Conmputers Conference, ARO Report 79-3, Army Research Office, 1979, 199-320.
[30] de Boor C. A Practical Guide to Splines. New York: Springer-Verlag, 1978.
[31] de Boor C. Total positicity of the spline collocation matrix. Indiana University Mathematics Journal, 1976, 25(6) : 541-551.
[32] Loe K F. α-β-spline: A linear singular blending B-spline.The Visual Computer,1996, 12:18-25.
[33] 陈景良,陈向晖.特殊矩阵.北京:清华大学出版社,2001,370-371;429-430.
[34] Piegl, L. On NURBS: A Survey, IEEE CG&A, 1991, 1: 55-71.
[35] Rolland L. Hardy, Dr.-Ing. Research results in the application of Multiquadric equation to surveying and mapping problem. Surveying and Mapping, 1975, 35: 321-332
[36] 彭群生,胡国飞.三角网格参数化.计算机辅助设计与图形学学报,2004,16(6) :732-739.
[37] Floater M S. Parametrization and smooth approximation of the face triangulations [J]. Computer Aided Geometric Design, 1997, 14(3) : 231-250.
[38] Floater M S, Reimers M. Meshless parametrization and surface reconstruction [J]. Computer Aided Geometric Design, 2001, 18(2) : 77-92.
[39] 陈志杨,李江雄,柯映林.反求工程中的曲面重建技术.汽车工程,2000,22(157) : 365-367.
[40] Hugues Hoppe, Tony DeRose, Tom Duchamp. Surface reconstruction from unorgnized points. Computer Graphics (SIGGRAPH'92 Proceedings) 1992, 26(2) :71-78.
[41] 周海,周来水,王占东等.散乱数据点的细分曲面重建算法实现.计算机辅助设计与图 形学学报,2003,15(10) :1287-1292.
[42] Suzuki H, Takeuchi S, Kanai T. Subdivision surafce fitting to a range of points[A]. In: Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, Seoul, Korea, 1999, 365-367.
[43] Loop C. Smooth subdivision surfaces based on triangles[D].Utah:University of Utah, 1987.
[44] Luiz Velho, Denis Zorin. 4-8 Subdivision. Computer Aided Geometric Design, 2001, 18: 397-427.
[45] J Warren. Subdivision methods for geometric design[D]. Rice university, 1995.
[46] Ma, W., Zhao N. Catmull-Clark surface fitting for reverse engineering applications. Geometric Modeling and Processing 2000, Theory and Applications. Proceedings, 2000, 274-283.
[47] 韩力文,周蕴时.曲线与曲面的细分算法.计算技术与自动化,2002,21(3) :20-22.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |