基于多结点样条磨光函数的几何迭代法
|
摘要
几何迭代法在计算机辅助几何设计(CAGD)中有广泛地应用,为了提高传统的B-样条曲线插值在几何迭代中的收敛速度和迭代精度,提出了基于多结点样条磨光函数的几何迭代法,引入多结点样条磨光函数,在曲线拟合时把多结点样条磨光方法和几何迭代方法结合,经过磨光和迭代,在L-BFGS迭代算法的最优解下构造具有高逼近性的曲线拟合方法。实验结果表明,在相同精度下,该方法不仅减少了迭代次数,且提高了迭代速度,可以用于飞机、汽车等外形设计上,亦可用于文物、房屋等外形重构和重建,以及卫星图形图像的处理中。
Geometric iteration method has been widely used in computer aided geometric design(CAGD). In order to improve the convergence speed and iterative accuracy of the traditional B-spline curve interpolation in geometric iterations, this study proposes the geometric iteration method based on many-knot spline polishing functions, which introduces many-knot spline polishing functions, and combines many-knot spline polishing functions method and geometric iteration method in curve fitting. After polishing operator and iterating, the curve fitting method with high approximation under the optimal solution of L-BFGS iterative algorithm is constructed. Experimental results show that the proposed method not only reduces the times of iterations, but also improves the iterative speed under the same accuracy. The proposed geometric iteration method can be used in the shape design of airplanes, automobiles, etc. It can also be used to reconstruct and rebuild the shape of cultural relic houses and satellite image processing.
Geometric iteration method has been widely used in computer aided geometric design(CAGD). In order to improve the convergence speed and iterative accuracy of the traditional B-spline curve interpolation in geometric iterations, this study proposes the geometric iteration method based on many-knot spline polishing functions, which introduces many-knot spline polishing functions, and combines many-knot spline polishing functions method and geometric iteration method in curve fitting. After polishing operator and iterating, the curve fitting method with high approximation under the optimal solution of L-BFGS iterative algorithm is constructed. Experimental results show that the proposed method not only reduces the times of iterations, but also improves the iterative speed under the same accuracy. The proposed geometric iteration method can be used in the shape design of airplanes, automobiles, etc. It can also be used to reconstruct and rebuild the shape of cultural relic houses and satellite image processing.
引文
[1]OKANIWA S,NASRI A,LIN H,et al.Uniform B-spline curve interpolation with prescribed tangent and curvature vectors[J].IEEE transactions on visualization and computer graphics,2012,18(9):1474-1487.
[2]LIN H,MAEKAWA T,DENG C.Survey on geometric iterative methods and their applications[J].Computer-Aided Design,2018,95:40-51.
[3]LIN H,ZHANG Z.An efficient method for fitting large data sets using T-splines[J].SIAM Journal on Scientific Computing,2013,35(6):A3052-A3068.
[4]齐东旭,田自贤,张玉心,等.曲线拟合的数值磨光方法[J].数学学报,1975,18(3):173-184.
[5]齐东旭,梁振珊.多结点样条磨光(Ⅰ)[J].高等学校计算数学学报,1979,(2):196-209.
[6]齐东旭,梁振珊.多结点样条磨光(Ⅱ)[J].高等学校计算数学学报,1981,(1):68-81.
[7]DE BOOR C.How does Agee’s smoothing method work?[R].Washington D C:Army Research Office79-3,1979:299-302.
[8]LIN H W,WANG G J,DONG C S.Constructing iterative non-uniform B-spline curve and surface to fit data points[J].Science in China:Series F,2004,47(3):315-331.
[9]LIN H W,BAO H J,WANG G J.Totally positive bases and progressive iteration approximation[J].Computers and Mathematics with Applications,2005,50(3-4):575-586.
[10]LIN H,WANG G,DONG C.Constructing iterative non-uniform B-spline curve and surface to fit data points[J].Science in China Series:Information Sciences,2004,47(3):315-331.
[11]邓少辉,汪国昭.渐进迭代逼近方法的数值分析[J].计算辅助设计与图形学学报,2012,24(7):879-884.
[12]LIU M,LI B,GUO Q,et al.Progressive iterative approximation for regularized least square bivariate B-spline surface fitting[J].Journal of Computational and Applied Mathematics,2018,327:175-187.
[13]DENG C Y,LIN H W.Progressive and iterative approximation for least squares B-spline curve and surface fitting[J].Computer-Aided Design,2014,47:32-44.
[14]DELGADO J,PE?A J M.Progressive iterative approximation and bases with the fastest convergence rates[J].Computer Aided Geometric Design,2007,24(1):10-18.
[15]MAEKAWA T,MATSUMOTO Y,NAMIKI K.Interpolation by geometric algorithm[J].Computer-Aided Design,2007,39(4):313-323.
[16]LIN H.The convergence of the geometric interpolation algorithm[J].Computer-Aided Design,2010,42(6):505-508.
[17]XIONG Y,LI G,MAO A.Convergence analysis for B-spline geometric interpolation[J].Computers&Graphics,2012,36(7):884-891.
[18]齐东旭.关于计算机辅助几何造型数学方法的若干注记[J].北方工业大学学报,1991,3(1):1-8.
[19]李岳生,齐东旭.样条函数方法[M].北京:科学出版社,1979:148-176.
[20]CAI Z C,LAN T,ZHENG C.Hierarchical MK splines:Algorithm and applications to data fitting[J].IEEETransactions on Multimedia,2017,19(5):921-934.
[21]LIU D C,NOCEDAL J.On the limited memory BFGSmethod for large scale optimization[J].Mathematical Programming,1989,45(1):503-528.
[22]QIN Z W.The relationships between CG,BFGS,and two limited-memory algorithms[J].Furman University Electronic Journal of Undergraduate Mathematics,2016,12(1):5-20.
[23]NASH S G,NOCEDAL J.A numerical study of the limited memory BFGS method and the truncatednewton method for large scale optimization[J].SIAMJournal on Optimization,1991,1(3):358-372.
[24]SHANNO D F.On the convergence of a new conjugate gradient algorithm[J].SIAM Journal on Numerical Analysis,1978,15(6):1247-1257.
[25]LIU Y,WANG W P,LéVY B,et al.On centroidal voronoi tessellation-energy smoothness and fast computation[J].ACM Transactions on Graphics,2009,28(4):1-17.
[26]WANG Y C,DONG L,XUE X,et al.On the design of constant modulus sequences with low correlation sidelobes levels[J].IEEE Communications Letters,2012,16(4):462-465.
[27]WANG Y C,WANG X,LIU H,et al.On the design of constant modulus probing signals for MIMO radar[J].IEEE Transactions on Signal Processing,2012,60(8):4432-4438.
[28]刘超,辛士庆,舒振宇,等.几何迭代法的加速[J].计算机辅助设计与图形学学报,2016,28(11):1838-1843.
[2]LIN H,MAEKAWA T,DENG C.Survey on geometric iterative methods and their applications[J].Computer-Aided Design,2018,95:40-51.
[3]LIN H,ZHANG Z.An efficient method for fitting large data sets using T-splines[J].SIAM Journal on Scientific Computing,2013,35(6):A3052-A3068.
[4]齐东旭,田自贤,张玉心,等.曲线拟合的数值磨光方法[J].数学学报,1975,18(3):173-184.
[5]齐东旭,梁振珊.多结点样条磨光(Ⅰ)[J].高等学校计算数学学报,1979,(2):196-209.
[6]齐东旭,梁振珊.多结点样条磨光(Ⅱ)[J].高等学校计算数学学报,1981,(1):68-81.
[7]DE BOOR C.How does Agee’s smoothing method work?[R].Washington D C:Army Research Office79-3,1979:299-302.
[8]LIN H W,WANG G J,DONG C S.Constructing iterative non-uniform B-spline curve and surface to fit data points[J].Science in China:Series F,2004,47(3):315-331.
[9]LIN H W,BAO H J,WANG G J.Totally positive bases and progressive iteration approximation[J].Computers and Mathematics with Applications,2005,50(3-4):575-586.
[10]LIN H,WANG G,DONG C.Constructing iterative non-uniform B-spline curve and surface to fit data points[J].Science in China Series:Information Sciences,2004,47(3):315-331.
[11]邓少辉,汪国昭.渐进迭代逼近方法的数值分析[J].计算辅助设计与图形学学报,2012,24(7):879-884.
[12]LIU M,LI B,GUO Q,et al.Progressive iterative approximation for regularized least square bivariate B-spline surface fitting[J].Journal of Computational and Applied Mathematics,2018,327:175-187.
[13]DENG C Y,LIN H W.Progressive and iterative approximation for least squares B-spline curve and surface fitting[J].Computer-Aided Design,2014,47:32-44.
[14]DELGADO J,PE?A J M.Progressive iterative approximation and bases with the fastest convergence rates[J].Computer Aided Geometric Design,2007,24(1):10-18.
[15]MAEKAWA T,MATSUMOTO Y,NAMIKI K.Interpolation by geometric algorithm[J].Computer-Aided Design,2007,39(4):313-323.
[16]LIN H.The convergence of the geometric interpolation algorithm[J].Computer-Aided Design,2010,42(6):505-508.
[17]XIONG Y,LI G,MAO A.Convergence analysis for B-spline geometric interpolation[J].Computers&Graphics,2012,36(7):884-891.
[18]齐东旭.关于计算机辅助几何造型数学方法的若干注记[J].北方工业大学学报,1991,3(1):1-8.
[19]李岳生,齐东旭.样条函数方法[M].北京:科学出版社,1979:148-176.
[20]CAI Z C,LAN T,ZHENG C.Hierarchical MK splines:Algorithm and applications to data fitting[J].IEEETransactions on Multimedia,2017,19(5):921-934.
[21]LIU D C,NOCEDAL J.On the limited memory BFGSmethod for large scale optimization[J].Mathematical Programming,1989,45(1):503-528.
[22]QIN Z W.The relationships between CG,BFGS,and two limited-memory algorithms[J].Furman University Electronic Journal of Undergraduate Mathematics,2016,12(1):5-20.
[23]NASH S G,NOCEDAL J.A numerical study of the limited memory BFGS method and the truncatednewton method for large scale optimization[J].SIAMJournal on Optimization,1991,1(3):358-372.
[24]SHANNO D F.On the convergence of a new conjugate gradient algorithm[J].SIAM Journal on Numerical Analysis,1978,15(6):1247-1257.
[25]LIU Y,WANG W P,LéVY B,et al.On centroidal voronoi tessellation-energy smoothness and fast computation[J].ACM Transactions on Graphics,2009,28(4):1-17.
[26]WANG Y C,DONG L,XUE X,et al.On the design of constant modulus sequences with low correlation sidelobes levels[J].IEEE Communications Letters,2012,16(4):462-465.
[27]WANG Y C,WANG X,LIU H,et al.On the design of constant modulus probing signals for MIMO radar[J].IEEE Transactions on Signal Processing,2012,60(8):4432-4438.
[28]刘超,辛士庆,舒振宇,等.几何迭代法的加速[J].计算机辅助设计与图形学学报,2016,28(11):1838-1843.