曲线拟合与绘制

2017-07-27

  在学习图形学课程中,一个很重要的部分就是绘制曲线、曲面。其实,这部分需要的基础课程有“最优化”、“数值分析”,其实,想要完全弄清楚,还是有一定难度的。但是,曲线、曲面的绘制是分为两部分的,一部分是数学,一部分是绘制。
一,拟合
    简单来讲,问题的定义是:我们通常会获取到一些离散的点,二维的、三维的, 比如在CAD软件开发需求中,我们经常获取到的数据可能是手工测量的,可能是手绘的,可能是从文件中保存离散点,我们想要知道穿过这些点的曲线的函数,方便后续更加精密的加工。又或者我们已经有曲线方程。此后,我们需要把曲线绘制出来。

1.1,拟合简单函数
  当我们知道这些点表示的图形大概是什么曲线。比如说知道它是二次曲线,就想办法求出来 f(x) = ax2 + bx +c , 如果是三次曲线,就求出来方程 f(x) = ax3 + bx2 + cx + d。对于更曲折的曲线,需要使用更高次的函数来拟合数据。
  scipy.optimize.curve_fit() 可以用来拟合线性、非线性方程,这个算法是利用 least squares实现的。至于least squares方法计算的时候,针对求解的问题,误差和参数还有不同的算法,如无约束问题采用“levenberg-marquardt方法”;如果提供了边界值,则采用Trust Region Reflective 算法。我们需要特别注意“最小二乘”,它的重要性是如此之高,是一定要掌握的。上面的例子及代码演示了我们知道函数是什么形式的,但是,有些时候,我们并不知道曲线的方程形式,或者曲线过于曲折。 样条曲线一般由多项式分段定义表示。在插值问题中,样条插值通常比多项式插值好用。多项式分段时,每一条曲线都用低阶的 多项式表示,我们可以用多段曲线连接成一条曲线。

1.2,拟合高次曲线
  我们一般不会愿意处理高次函数的,一者计算量大,二者计算误差大。 所以,我们会使用多段的低次曲线连接起来,来拟合复杂曲线。 spline 有很多种,我们常见的有Bezier Spline,B-Spline,NURBS,Hermitian Spline, Catmull-Rom Spline等等,算法都是不一样的。
  

  在矢量作图软件中,多段三次Bezier曲线用的较多,在CAD中,Bezier Spline有所不足,每改变一个控制点,就会改变曲线的整体样式。可谓牵一发而动全身。B-Spline,NURBS使用较多,工业上实际的标准是NURBS,像一些简单的场合,想我们团队在做的制衣CAD软件里,只用B-Spline就足够了。B-Spline分为均匀与非均匀的,当节点等距,称B样条为均匀(uniform)否则为非均匀(non-uniform)。但是NURBS并不是后面一个,它的全称是”非均匀有理B样条“。

  scipy.interpolate.UnivariateSpline() 的参数中,k,整型,可选值,默认为5,最高为5。为什么呢?由于龙格现象会导致数值不稳定,得出来的曲线,可能并不是我们想要的。UnivariateSpline 这个函数调用了 fitpack2模块的  splev(x, tck, der=0, ext=0) 函数,这里写着”Evaluate a B-spline or its derivatives“,所以,我们可以看到scipy lib中使用B-Spline来做曲线拟合的。对于n次 B-Spline来讲,它是有多条<n 次的曲线连接而成的,所以,这些曲线对应的多项式次数最高为4。就如同上图,蓝色的曲线看似是一条并连续,但实际上,是由多条曲线连接起来的,连接处两边的曲线导数相同,这样才能让整体曲线足够光滑。
  至于NURBS,一般是用来拟合三维曲面的,更少用到,所以我们一般不谈。
  我们在wiki中会看到least squares问题都是以matrix表示和计算的,但是,我们要明白,矩阵的概念在1840年才提出来, least squares在 1800年左右提出,和矩阵没有必然的联系。

二,绘制
  一般需要绘制曲线的,都是CAD软件的开发工作,基本上用C/C++、OpenGL来实现。其实没有必要,这里就使用最常见的python就能够学习相关的算法了。python2.7之后pip变得越来越好了,常见lib都能够处理了。对于windows上的python lib,建议参考链接2,不用自己编译或者安装exe,可使用第三方已经做好的whl包。
  对于计算机而言,一切都是离散的。所以,所谓的无限连续的曲线,展示的时候,也是一段段的小的直线段连接起来的。主流的显示屏幕分辨率1920×1080,展现出来的曲线,也只是离散的点连接起来的而已。

 

  1. https://en.wikipedia.org/wiki/Curve_fitting
  2. http://www.lfd.uci.edu/~gohlke/pythonlibs/#numpy   
  3. https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.curve_fit.html
  4. https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.UnivariateSpline.html
  5. https://en.wikipedia.org/wiki/Spline_(mathematics)
  6. https://www.zhihu.com/question/29565629
  7. https://en.wikipedia.org/wiki/B-spline
  8. http://zh.numberempire.com/graphingcalculator.php
如果有任何意见,欢迎留言讨论。


[ 主页 ]
COMMENTS
POST A COMMENT

(optional)



(optional)