B 样条曲线逼近偏差的精确求解算法*

江本赤 韩 江 夏 链

(合肥工业大学CIMS 研究所，安徽 合肥 230009)

B 样条是计算机辅助设计中的重要研究方向，已被确定为描述工业产品几何形状的数学标准［1-2］。在逆向工程等应用中，常需要用B 样条曲线逼近实测的有序数据点列［3-4］。国内外学者就此类问题开展大量的研究［3-7］，并取得了重要成果。Park 等人［5］提出了基于自适应误差控制的逼近算法，该方法无需事先指定控制顶点数目;徐进等人［6］提出了可自动识别特征点的B 样条曲线逼近技术，该方法可有效控制曲线的形状细节;Yoshimoto 等人［7］提出了一种适用于平面离散数据点拟合的遗传算法，该方法对光滑数据的拟合效果较好。

偏差反映了曲线与离散点之间的逼近程度，是衡量逼近质量的重要指标。上述文献中的算法都包含了基于偏差控制的迭代运算，而偏差计算的结果将决定迭代的次数，并影响相关参数的调整方向。从理论上讲，偏差值应为以数据点为圆心并与曲线相切的圆弧半径，但此法太过复杂，显然不可取。目前最常见的偏差计算方法，主要是先对数据点参数化，然后求出各参数值在曲线上的对应点，并将数据点与对应点之间的距离作为该点处的逼近偏差。事实上，该方法的可靠性较差，在绝大多数情况下所求得的对应点不是最近点，其计算值存在较大误差，甚至可能是实际偏差值的数倍，容易因为“误判”而增加多余的迭代次数，严重影响了算法的效率。因此，对于B 样条曲线逼近偏差计算方法的研究很有必要。

基于上述考虑，在对常用参数化方法进行分析比较的基础上，本文提出一种曲线对应点邻域搜索比较的偏差求解方法。对于某具体的数据点，在使用常规方法求出曲线上的对应点之后，再将其领域内的曲线离散成若干个细分点，并分别求出该数据点与各细分点间的距离，最后将最小距离值作为曲线与该点之间的偏差。该方法显著改善了偏差计算结果的可靠性和准确性，可更真实地反映B 样条曲线的逼近精度。

1 B 样条曲线逼近

1.1 B 样条曲线定义

B 样条曲线的方程为［8］

式中:p 为次数;Pi为曲线的控制顶点;Ni，p(u)为B 样条基函数，是定义在节点矢量U 上的p 次分段多项式，其数值由公式(2)和(3)求出。

节点矢量U 中a 和b 的重复度都为p+1，除非特别声明，通常取a=0，b=1。

1.2 B 样条曲线逼近

与插值不同的是，B 样条逼近不要求曲线严格通过而是最接近给定数据点，以捕获给定数据的形状，且每点处的偏差都小于误差界限。图1 所示的是一条B样条曲线逼近离散点的情形。

2 逼近偏差计算方法

先来看B 样条曲线逼近中最小二乘法的偏差控制与计算方法。对于给定m+1 个数据点Qk(k=0，1，…，m)，先确定参数值{u'k}，使包含n+1 个控制顶点的曲线满足下面两个条件:

(1)曲线通过首尾点，即Q0=C(0)，Q1=C(1);

(2)其余数据点Qk在最小二乘的意义下被逼近，即

关于n+1 个变量Pi达到最小值。

其中的C(u'k)是数据点Qk在曲线上的对应点，为曲线在该点的逼近偏差，而C(u'k)与数据点参数值u'k的获取方法有关。下面对几种最常见参数化方法进行分析比较。

2.1 常见参数化方法的对比与分析

最常见参数化方法有3 种，即均匀参数化、弦长参数化和向心参数化。其中，均匀参数化计算最为简单，即弦长参数化方法如下:

当数据点均匀分布时均匀参数化与弦长参数化的结果相同。而向心参数化方法如下:

现在用上述3 种参数化方法，分别求解图1 所示的B 样条曲线偏差情况。图2 所示的是对应点C(u'k)分布，图3 所示的是各自的偏差分布情况。

为了进一步说明不同参数化方法的使用效果，下面再分别计算另一组数据点的逼近偏差，图4 所示的是数据点在曲线上对应点，其偏差数值的分布情况见图5。

通过图3 和图5 可以看出，在相同条件下，弦长参数化所求出的偏差数值最小，这是由于它在分配参数时考虑了相邻数据点的距离大小;向心参数化对相邻数据点的距离值进行了开方处理，弱化了原始数据信息的影响(在曲线插值中处理数据点急转弯变化时，它可以得到比弦长参数化更好的效果);而均匀参数化对应的偏差值最大，则是由于它在分配参数时没有参考任何数据点的原始信息。因此，在求解B 样条曲线逼近偏差的过程中，用弦长参数化方法分配原始数据点的参数最为合理。

通过图2 和图4 可以看出，无论采用哪一种参数化方法，所求出对应点C(u'k)都不同程度地偏离了其应有位置。即使落在曲线上、理论偏差为零的数据点，其求出的偏差数值也可能很大，即实际曲线早已达到逼近精度要求，而不必要的迭代计算仍需继续进行。最极端的情况是，仅仅由于对应点严重偏离应有位置，导致求出的偏差值永远达不到预定精度要求。

鉴于此，下面提出一种计算数据点在曲线上对应点的改进方法，适用于B 样条曲线逼近中的偏差计算。

2.2 邻域搜索比较法

为了改善逼近偏差计算结果的可靠性，对于所有原始数据点，先用常规方法求出其在曲线上的对应点C(u'k)，再在C(u'k)的邻域内将曲线离散成若干细分点，并分别计算细分点与原始数据点的距离。记Qk点的参数为u'k，求解曲线在第k 个数据点Qk处逼近偏差的具体操作步骤如下:

(1)求出各细分点对应的参数。在u'k左右各取出w 个对称的参数值，即

u"j=(u'k-wΔu")+jΔu"，j=0，1，…，2w

(2)分别计算数据点Qk与各细分点间的距离Lj。Lj=Qk-C(u"j)，j=0，1，…，2w。

(3)求出Lj的最小值Lk。Lk=min(Lj)，作为曲线在Qk点处的逼近偏差。

此处需要指出的是，由于Δu"=Δu'2w 且Δu'=t(u'k+1-u'k-1)，t∈(0，1］，故C(u'k)点的邻域大小被限制在前后两原始数据点C(u'k-1)与C(u'k+1)之间，并可以通过系数t 来调节2w+1 个细分点的疏密程度。在w 取较大值的同时，t 的取值越小，细分点越集中，所求逼近偏差值的可靠性越高。图6 所示的分别是取w=2，t=0.4 和w=3，t=0.2 时所得的细分离散点的情况。

3 实例验证

为了验证上述方法的可行性和有效性，下面仍以图1 所示的数据为例，取w=3，t=0.2，结合均匀参数化、弦长参数化和向心参数化方法，将改进前后的效果进行对比，比较的结果如图7、图8 和图9 所示。

通过比较不难看出，本文所提方法显著提高了逼近偏差计算结果的准确性。

4 结语

本文分析了现有B 样条曲线逼近偏差的计算方法存在的问题，并在此基础上探索出了一种基于邻域搜索比较的精确偏差求解方法，得出了如下结论:

(1)逼近偏差的计算精度问题，不仅影响对曲线逼近效果的评价，同时也直接影响曲线逼近的算法效率。

(2)适当扩大在曲线上搜索和比较的范围，可显著改善偏差计算结果的可靠性。

(3)通过调整邻域搜索法中的分辨率参数，可以有效控制曲线上细分点的范围和密度，进而实现对逼近偏差计算精度的调节。

［1］Park H，Lee J H.B-spline curve fitting based on adaptive curve refinement using dominant points［J］.Computer-Aided Design，2007，39(6):439-451.

［2］程仙国，刘伟军，张鸣.特征点的B 样条曲线逼近技术［J］.计算机辅助设计与图形学学报，2011，23(10):1714-1718.

［3］Piecl L A，Tiller W.Least-square B-spline curve approximation with arbitrary end derivatives［J］.Engineering with Computers，2000，16(2):109-116.

［4］赵世田，赵东标，付莹莹.测量数据点的高精度B 样条曲线拟合算法［J］.计算机集成制造系统，2010，16(8):1708-1713.

［5］Park H，Kim K，Lee S C.A method for approximate NURBS curve compatibility based on multiple curves refitting［J］.Computer-Aided Design，2000，32(4):237-252.

［6］徐进，柯映林，曲巍崴.基于特征点自动识别的B 样条曲线逼近技术［J］.机械工程学报，2009，45(11):212-217.

［7］Yoshimoto F，Harada T，Yoshimoto Y.Data fitting with a spline using a real-coded genetic algorithm［J］.Computer-Aided Design，2003，35(8):751-760.

［8］Les Piegl，Wayne Tiller.非均匀有理B 样条［M］.2 版.北京:清华大学出版社，2010.