第1期 慕生鹏，等：三维离散曲线曲率挠率的微中心差分算法 ·203· 。一B样条曲线拟合法 0.05 ·B样条曲线拟合法 ◆一多项式曲线拟合法 ◆一多项式曲线拟合法 ◆一投影法 ◆一 投影法 ◆一单侧差分法 0.04 单侧差分法 ·一离散几何法 ·高散几何法 。一微中心差分法 过 。微中心差分法 0.01 一+ 100 200300 400 500 200 400 600 点数n 点数n (c)挠率MRE对比 (d)挠率RMSE对比 图7环面螺线误差对比实验 Fig.7 Error comparison experiment of toroidal spiral curve 图2~7反映了随着点的密度增加，曲率和挠 速度最快，本文提出的微中心差分法处于中间 率的误差的收敛性和稳定性。下面针对固定的点 位置。 密度，比较一下各个方法的精度。实验中我们 表26种算法的平均运行时间比较 根据上述的密度实验，取采样点数量适中误差 Table 2 Comparison of average running time of the 比较稳定的点密度，即n=200的时候进行6条 six algorithms 曲线的曲率和挠率估计精度的比较，结果如表1 算法 BSCF PCF Proj OSD DG MCD 所示。 时间56.655963.69350.05380.00090.00700.0120 表16条曲线的平均误差比较(F200) Table 1 Comparison of average error(n=200) 23噪声数据实验 算法BSCF 为了测试每个算法的抗噪声鲁棒性，在采样 PCF Proj OSD DG MCD 点数n为200时，设置噪声水平为0.00010.1，噪 曲率0.01290.00590.03930.02530.00140.0004 声为均值为零、标准差为离散曲线上邻近的两离 挠率0.00530.00120.03300.03020.00080.0003 散点之间的平均距离与噪声水平的乘积的高斯噪 从表1可以看出，本文提出的MCD方法计算 声。实验用Clelia曲线生成了不同噪声水平的离 的曲率和挠率平均误差分别为0.0004和0.0003， 散曲线。 比另5种算法中效果最佳的DG算法的曲率和挠 6种算法计算的曲率最大相对误差和曲率均 率平均误差（分别为0.0014和0.0008），分别降低 方根误差分别如图8(a)、(b)所示，从图中可以看 了69.74%和55.36%。可见，总体来看，本文提出 出：噪声水平越高，算法的误差变化越大；各算法 的算法无论是曲率估计还是挠率估计，精度都是 在噪声水平不大于0.01时，均能较准确地计算离 最高的。 散曲线的曲率值；噪声水平大于0.01时，其误差 关于运行效率，从算法原理可以看出，所有算 明显变大，尤其是单侧差分法和投影法，而本文 的方法误差变化浮动相对较小。 法时间复杂度都是线性级的，即O(),因此给出 6种算法计算的挠率最大相对误差和均方根 平均实验时间便可以说明计算的时间效率。用 误差分别如图8(c)、(d)所示，从图中可以看出：含 6种算法分别计算6条曲线的曲率和挠率，对每 噪声的离散曲线在计算挠率时变得更加敏感，当 条离散曲线的不同采样密度进行50次实验，总 噪声水平大于0.001时，6种算法得到的挠率值与 的平均运行时间如表2所示。从表2可以看 真实值就已有了明显的偏差，并且随着噪声水平 出，离散结构法(Proj、OSD、DG、MCD)相比曲 变大，挠率的最大相对误差和均方根误差相比曲 线拟合法(BSCF、PCF),计算效率大幅提高；在 率也会更快地增大。与其他5种算法相比，本文 离散结构法中，单侧差分算法(OSD)平均运行 的方法误差变化浮动相对较小。图 2～7 反映了随着点的密度增加，曲率和挠 率的误差的收敛性和稳定性。下面针对固定的点 密度，比较一下各个方法的精度。实验中我们 根据上述的密度实验，取采样点数量适中误差 比较稳定的点密度，即 n=200 的时候进行 6 条 曲线的曲率和挠率估计精度的比较，结果如表 1 所示。 从表 1 可以看出，本文提出的 MCD 方法计算 的曲率和挠率平均误差分别为 0.000 4 和 0.000 3， 比另 5 种算法中效果最佳的 DG 算法的曲率和挠 率平均误差 (分别为 0.001 4 和 0.000 8)，分别降低 了 69.74% 和 55.36%。可见，总体来看，本文提出 的算法无论是曲率估计还是挠率估计，精度都是 最高的。 关于运行效率，从算法原理可以看出，所有算 法时间复杂度都是线性级的，即 O(n)，因此给出 平均实验时间便可以说明计算的时间效率。用 6 种算法分别计算 6 条曲线的曲率和挠率，对每 条离散曲线的不同采样密度进行 50 次实验，总 的平均运行时间如 表 2 所示。从 表 2 可以看 出，离散结构法 (Proj、OSD、DG、MCD) 相比曲 线拟合法 (BSCF、PCF)，计算效率大幅提高；在 离散结构法中，单侧差分算法 (OSD) 平均运行 速度最快，本文提出的微中心差分法处于中间 位置。 2.3 噪声数据实验 n 为了测试每个算法的抗噪声鲁棒性，在采样 点数 为 200 时，设置噪声水平为 0.000 1~0.1，噪 声为均值为零、标准差为离散曲线上邻近的两离 散点之间的平均距离与噪声水平的乘积的高斯噪 声。实验用 Clelia 曲线生成了不同噪声水平的离 散曲线。 6 种算法计算的曲率最大相对误差和曲率均 方根误差分别如图 8(a)、(b) 所示，从图中可以看 出：噪声水平越高，算法的误差变化越大；各算法 在噪声水平不大于 0.01 时，均能较准确地计算离 散曲线的曲率值；噪声水平大于 0.01 时，其误差 明显变大，尤其是单侧差分法和投影法，而本文 的方法误差变化浮动相对较小。 6 种算法计算的挠率最大相对误差和均方根 误差分别如图 8(c)、(d) 所示，从图中可以看出：含 噪声的离散曲线在计算挠率时变得更加敏感，当 噪声水平大于 0.001 时，6 种算法得到的挠率值与 真实值就已有了明显的偏差，并且随着噪声水平 变大，挠率的最大相对误差和均方根误差相比曲 率也会更快地增大。与其他 5 种算法相比，本文 的方法误差变化浮动相对较小。 (d) 挠率RMSE对比 挠率均方根误差值 点数n 200 400 600 0.05 0.04 0.03 0.02 0.01 0 B样条曲线拟合法 多项式曲线拟合法 投影法 单侧差分法 离散几何法 微中心差分法 (c) 挠率MRE对比 200 400 500 点数n 102 101 0 挠率最大相对误差值 100 100 300 B样条曲线拟合法 多项式曲线拟合法 投影法 单侧差分法 离散几何法 微中心差分法 图 7 环面螺线误差对比实验 Fig. 7 Error comparison experiment of toroidal spiral curve 表 1 6 条曲线的平均误差比较 (n=200) Table 1 Comparison of average error (n = 200) 算法 BSCF PCF Proj OSD DG MCD 曲率 0.012 9 0.005 9 0.039 3 0.025 3 0.001 4 0.000 4 挠率 0.005 3 0.001 2 0.033 0 0.030 2 0.000 8 0.000 3 表 2 6 种算法的平均运行时间比较 Table 2 Comparison of average running time of the six algorithms s 算法 BSCF PCF Proj OSD DG MCD 时间 56.655 9 63.693 5 0.053 8 0.000 9 0.007 0 0.012 0 第 1 期 慕生鹏，等：三维离散曲线曲率挠率的微中心差分算法 ·203·