如何将Bézier曲线拟合到一组数据？

Question

我有一组数据点（可以稀疏），需要用Bézier曲线进行拟合。我需要的是速度而不是精度，但是拟合结果应该足够好以便识别。另外，我正在寻找一种算法，可以使用得较少库（特别是NumPy）。

我已经阅读了几篇研究论文，但没有一篇提供足够详细的细节来完全实现。是否有任何开源示例？

- user791684

Answer 1

我有类似的问题，并且我在《图形宝典》（1990年）中找到了关于贝塞尔曲线拟合的“自动拟合数字化曲线的算法”。此外，我还找到了该文章的源代码。

不幸的是，它是用C语言编写的，而我对C语言并不很熟悉。而且，这个算法对我来说相当难以理解。我正在尝试将其翻译成C#代码。如果我成功了，我会尝试分享出来。

文件GGVecLib.c与FitCurves.c在同一个文件夹中，包含基本的向量操作函数。

我还找到了一个类似的Stack Overflow问题，如何平滑手绘曲线。被认可的答案提供了一个来自图形宝典的曲线拟合算法的C#代码。

- Archibald

---

这看起来很复杂。有人可以验证一下这段代码是否有效吗？ - user791684

@MichaelScheper的文章已被删除，看起来他们仍在销售这些书籍，因此这篇文章有点不可靠。在亚马逊上购买《图形宝典》只需花费约10美元。 - Archibald

我将这个算法逐行移植到了Javascript中，并且可以确认它是有效的。我使用了一份纸质版的书，但是通过在线搜索找到了C代码。 - Steve Hanov

我找到了一个使用numpy的Python实现，提到了这篇相同的文章：https://github.com/soswow/fit-curves/blob/master/python/fitCurves.py - saschwarz

@saschwarz，您的链接已失效。新链接可能是https://github.com/volkerp/fitCurves。 - Waruyama

Answer 2

很多答案中都没有提到的是，您可能不想将单个三次贝塞尔曲线拟合到您的数据中。更一般地说，您希望将一系列三次贝塞尔曲线（即分段三次贝塞尔拟合）拟合到任意数据集上。

有一篇非常好的论文可以完成这项工作，发布于1995年，并附有MATLAB代码。

% Lane, Edward J. Fitting Data Using Piecewise G1 Cubic Bezier Curves.
% Thesis, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, 1995

http://www.dtic.mil/dtic/tr/fulltext/u2/a298091.pdf

要使用此功能，您必须至少指定节点数，即优化程序将用于拟合的数据点数。可选地，您可以指定节点本身，这将增加拟合的可靠性。论文展示了一些相当棘手的例子。请注意，Lane的方法保证了三次贝塞尔曲线段之间的G1连续性（相邻切向量的方向相同），即平滑接合处。但是，曲率中可能存在不连续性（二阶导数方向的变化）。

我已重新实现了代码，将其更新为现代MATLAB（R2015b）。如果需要，请与我联系。

以下是一个示例，仅使用三个节点（由代码自动选择），将两个三次贝塞尔曲线段适应到Lissajous图形中。

- Biofloat

---

如果您能够将代码重新实现为MATLAB R2015b版本并在GitHub gist上发布并在此处链接，我将不胜感激。谢谢！ - Michael Currie

这是在GitLab上的代码：https://gitlab.com/erehm/PiecewiseG1BezierFit - Biofloat

Answer 3

如果大部分数据符合模型，可以尝试使用RANSAC。很容易在随机选取的4个点上拟合贝塞尔曲线。我不确定从头部估算曲线相对于所有其他点的成本有多高（RANSAC算法的一部分）。但这将是一个线性解决方案，而且编写RANSAC非常容易（可能有开源算法可用）。

- Pace

---

每次RANSAC迭代都需要评估曲线并找到所有点的距离。如果这是在1D中，则很简单，在2D或3D中则变得困难，因为您需要找到曲线上最近的点并计算该点的误差（欧几里得距离）。这将至少每次迭代需要O(n)的时间。迭代次数由内点和模型大小的比率给出。因此，如果您要拟合单个4点弧，那么可能是可行的。弧中的点越多，正确获取点的机会就会指数级下降。 - the swine

因此，对于单个弧线的简单情况，这种方法可以奏效，但对于更长的样条曲线，这种方法会变得极其缓慢。更重要的是，请注意，在贝塞尔曲线中，曲线并不通过点，因此即使您选择了正确的点，它也会给出错误的曲线。使用可以通过控制点的 Catmull-Rom 样条曲线更好。 - the swine

然而，这并不意味着不能将Bezier曲线拟合到一组点上。它意味着该曲线的至少一些控制点不会与数据点重合。但是，如果使用最小二乘等技术，这几乎没有关系。 - the swine

Answer 4

我对这个问题有一个MATLAB解决方案。 我遇到了同样的问题，但我的代码是用MATLAB编写的。 我希望把它翻译成Python不会太难。

您可以通过这段代码FindBezierControlPointsND.m找到控制点。 由于某种原因，在其存档中没有函数“ChordLengthNormND”， 但在第45行调用了它。

我用以下代码替换了它：

[arclen,seglen] = arclength(p(:,1),p(:,2),'sp');
t = zeros(size(p,1),1);
sums = seglen(1);
for i = 2:size(p,1)-1
    t(i) = sums / arclen;
    sums = sums + seglen(i);
end
t(end) = 1;

arclength的MATLAB代码可以在这里获取。

之后，我们有了Bezier曲线的控制点，网上有很多实现通过控制点构建Bezier曲线的方法。

- lintseju

Answer 5

首先，请确保您所请求的是您真正想要的。将点配合到Bezier曲线中会将它们放置在这些点的凸壳中。使用样条曲线可以确保您的曲线通过所有点。

话虽如此，创建绘制任何一种曲线的函数并不复杂。维基百科有一篇很好的文章，可以解释基本概念，贝塞尔曲线。

- Pedery

---

因为这个回答根本没有解答问题，所以被投票降低了。在维基百科上链接贝塞尔曲线只是陈述显而易见的事实，此外维基百科文章也没有涉及曲线拟合。 - Ben Hutchison