基于HO算法的NURBS拟合过程中的权重优化

Weight Optimization in NURBS Fitting Process Based on HO Algorithm

摘要: 非均匀有理B样条(NURBS)在复杂形状表达上有很强的适应性，高精度的曲线拟合可以有效提高其在多领域的应用效果。针对NURBS曲线逼近拟合，结合河马优化算法(Hippopotamus optimization, HO)，提出一种针对NURBS曲线逼近拟合中的权重优化方法。首先，将权重引入HO算法中作为种群成员；然后，结合型值点与拟合曲线位置关系建立拟合目标函数；最后，通过HO算法迭代机制，寻找最佳权重，应用最佳权重再次进行NURBS曲线拟合。实验数据表明，通过HO算法对NURBS曲线逼近拟合中的权重进行优化，有效提高了曲线拟合精度。

Abstract: NURBS (Non-Uniform Rational B-Splines) have strong adaptability in expressing complex shapes. High-precision curve fitting can effectively improve their application effects in various fields. Aiming at the NURBS curve approximation fitting, combined with the HO (Hippopotamus Optimization) algorithm, a weight optimization algorithm for NURBS curve approximation fitting is proposed. Firstly, the weights are introduced into the HO algorithm as population members; then, the fitting objective function is established based on the positional relationship between the control points and the fitting curve; finally, through the iterative mechanism in the HO algorithm, the best individual member, that is, the best weight, is found, and the NURBS curve fitting is performed again with the best weight. Experimental data show that optimizing the weights in the NURBS curve approximation fitting process through the HO algorithm effectively improves the curve fitting accuracy.

1. 引言

非均匀有理B样条(Non-Uniform Rational B-Splines, NURBS)因其在数学表达上的普适性、灵活性与控制能力、参数连续性，而被广泛应用在航空航天、工业设计、汽车、船舶[1]-[3]等需要精密建模的行业。如今NURBS已经成为利用计算机处理集合信息时用于形状的表示、设计和数据交换的工业标准。

NURBS曲线拟合过程中涉及许多数学求解及参数信息[4]，为提高NURBS曲线拟合精度，许多学者做出了研究。张蒙等[5]提出基于最小二乘渐进迭代逼近LSPIA (Least-Squares Progressive-Iterative Approximation)的NURBS曲线拟合算法，优化控制顶点、数据点参数等变量，节省运算时间且具保形效果。Lan L等人[6]提出Full-LSPIA方法，联合优化NURBS的控制点、权重与节点，另提递减式全最小二乘渐进迭代逼近Decremental Full-LSPIA (Decremental Full-Least-Squares Progressive-Iterative Approximation)，实验验证其拟合精度更优。张银娟等[7]将遗传算法引入NURBS权重优化，提升曲线拟合精度，试验数据证实效果。盖荣丽等[8]提出特征点提取、最小二乘及粒子群优化的NURBS拟合方法，压缩数据且提升精度。

在实际应用中，晏婷等人[9]为提高齿轮齿廓曲线拟合精度，提出基于NURBS曲线拟合的渐开线圆柱齿轮齿形偏差计算方法。吕鑫、王硕桂[10]提出等离子弧表面处理中NURBS拟合复杂工件曲线的算法，用曲率积分找关键点平移作轨迹点，提升处理质量且简化计算。

以几何距离为核心的拟合误差通常难以获得稳定的解析梯度，使得传统基于梯度的优化方法对初值敏感、容易陷入局部最小，而河马优化算法(Hippopotamus optimization, HO) [11]同时包含全局探索与局部开发两种机制，对目标函数的可微性要求低，敏感参数数量少，可显著降低参数调试成本与工程实现复杂度。本文将权重显式建模为待优化变量，利用HO算法的全局寻优特性，实现对全区域的自适应增强。因此，为提高NURBS曲线的拟合精度，本文主要工作如下：

使用型值点反求曲线控制点，在对离散点进行拟合的过程中引入HO算法，将权重作为寻优目标，以离散点与拟合曲线之间最小距离的平方和作为目标函数，利用HO搜寻最优权重，利用最优权重对曲线进行重新拟合，大幅度提高了拟合精度。

2. 权重对NURBS曲线的影响

NURBS数学表达

p次NURBS曲线的定义为

$C\left(u\right)=\frac{{\displaystyle \sum _{i=0}^n{N}_{i,p}\left(u\right)w_i{P}_i}}{{\displaystyle \sum _{i=0}^n{N}_{i,p}\left(u\right)w_i}},a\le u\le b$ (1)

其中$\left\{C\left(u\right)\right\}$ 为NURBS曲线，$\left\{w_i\right\}$ 是权重，$\left\{P_i\right\}$ 是控制点，$\left\{N_{i,p}\left(u\right)\right\}$ 是定义在非周期(且非均匀)节点矢量$U$ 上的$p$ 次$B$ 样条基函数，其中，$U=\left\{a,\cdot \cdot \cdot ,a,u_{p+1},\cdot \cdot \cdot ,u_{m-p-1},b,\cdot \cdot \cdot b\right\}$ 。

对所有的$i,w_i>0$ ，令

$R_{i,p}\left(u\right)=\frac{N_{i,p}\left(u\right)w_i}{{\displaystyle \sum _{j=0}^n{N}_{j,p}\left(u\right)w_i}}$ (2)

$R_{i,p}\left(u\right)$ 称为有理基函数，权重$w_i$ 并没有修改基函数$N_{i,p}\left(u\right)$ 的表达式，而是定义了一个与基函数和控制点都相关的有理函数，进而(1)式可以改写为

$C\left(u\right)={\displaystyle \sum _{i=0}^n{R}_{i,p}\left(u\right)P_i}$ (3)

在公式定义上，权重$w_i$ 作为系数，与$N_{i,p}\left(u\right)P_i$ 这个整体相结合，它影响的是基函数与控制点共同构成的内容。而在几何体现上，权重改变的是控制点对曲线的影响力。增大权重会使曲线被拉向该控制点，减小权重则使曲线远离控制点。

若$u\notin \left[u_i,u_{i+p+1}\right)$ ，则$R_{i,p}\left(u\right)=0$ 。此外，在任一给定的节点区间内，至多有$p+1$ 个非零的$R_{i,p}\left(u\right)$ 。这体现了NURBS的局部支撑性。进而可知当移动控制点$P_i$ 或改变权重$w_i$ ，仅影响区间$u\in \left[u_i,u_{i+p+1}\right)$ 上

的曲线形状，这则体现了NURBS曲线的局部修改性。根据以上两个性质，我们可以利用移动控制点或改变权重的方式来实现曲线的局部修改，而不改变曲线其他部位的形状，这在交互形状设计中非常重要。

图1说明了如何通过改变权重来实现曲线形状修改。改变权重$w_3$ 和$w_6$ ，分别令其为0.5、1、1.5、3，并绘制NURBS曲线，可以看出权重越大，该段曲线会越靠近控制该段曲线的控制点，反之则会远离控制点。

Figure 1. Local modification of curve shape by changing weights

图1. 通过改变权重来实现曲线形状的局部修改

3. 逼近拟合与插值拟合

对于未知方程的曲线，通过选取曲线上的型值点(Q)反算求出曲线控制点的过程叫做NURBS曲线控制点的反求。利用求得的曲线控制点进行NURBS曲线拟合，可实现对未知方程曲线的表示。

NURBS曲线拟合常用方法有两种，逼近拟合和插值拟合。两者间存在明显的差异。逼近拟合不要求通过所有的型值点，着重在整体趋势和规律上，拟合过程中会过滤细节，且逼近拟合可通过减少参数数量降低计算复杂程度；而插值拟合则严格通过所有的型值点，能够实现数据的精确匹配，参数数量与型值点有直接关系，型值点数量越多计算量越大。通过逼近拟合计算的曲线在满足误差的条件下更为光滑，能够避免过拟合，有较强的泛化能力。以插值拟合方式计算的曲线在已知数据点位置精确无误差，拟合结果唯一确定，这也导致插值拟合易出现过拟合现象，在点与点之间可能存在剧烈震荡。

由于逼近拟合和插值拟合之间的差异，使得NURBS曲线控制点的反求也存在不同情况。而无论哪种方法，第一步都是参数化。常用的参数化方法有以下几种。均匀参数化，其特点是计算简单，但容易导致形状失真；积累弦长参数化，其特点是根据型值点间的累计弦长分配参数，能更好的反映点的分布，也是最常用的方法；向心参数化，适用于型值点急转弯的情况。为保证拟合精度，本文采用的是积累弦长参数化。其节点满足：

$\{\begin{array}{l}{u}_0=u_1=u_2=u_3=0\hfill \\ u_{n+3}=u_{n+4}=u_{n+5}=u_{n+6}=1\left(i=1,2,\cdots ,n-1\right)\hfill \\ u_i=u_{i-1}+\frac{\left|Q_i-Q_{i-1}\right|}{{\displaystyle \sum _{i=1}^n\left|Q_i-Q_{i-1}\right|}}\hfill \end{array}$ (4)

逼近拟合和插值拟合控制点反求过程中最大的不同在于控制点个数。对于一条p次曲线，若其型值点个数为$n+1$ ，在逼近拟合中，控制点数量$c+1$ 由人为决定，但需要满足$c+1<n+1$ 。在插值拟合中控制点数量等于型值点数量$n+1$ 。在上述两种情况下建立控制点反求方程，由逼近拟合建立的是最小二乘优化问题，通过最小二乘的方法求解超定系统，求得的结果就是最佳控制点。而插值拟合中方程数量与未知数数量一致，因此建立的是线性方程组。

通过上述方法对曲线进行拟合，插值拟合的理论误差为0，而逼近拟合由于其本质是优化过程，而不是求解精确解，这就使得逼近拟合存在系统误差。

在常规拟合的过程中，由于无法直接观察或计算某个控制点对曲线段的影响程度，故而通常将权重人为设置为1，这虽是一种实用的简化策略，但牺牲了NURBS的完整有理表达能力，并且在一定程度上增加了拟合误差。为了保证NURBS的完整表达以及尽可能地减小权重设置对曲线拟合带来的误差影响，本文采用HO算法对逼近拟合过程中的权重进行优化。优化目标为型值点到拟合曲线最小距离和，即

$\text{fitness}={\displaystyle \sum _{i=1}^n\left|Q\left(i\right)-C\left(u_i\right)\right|}$ (5)

式中，$\text{fitness}$ 为型值点到拟合曲线最小距离和，$Q\left(i\right)$ 为给定型值点，$C\left(u_i\right)$ 为拟合曲线上的点。

以逼近拟合为优化对象的原因在于，逼近拟合的曲线不会严格经过型值点，可将型值点到拟合曲线之间的最小距离和作为精度参考，而插值拟合的曲线会严格经过所有的型值点，型值点到拟合曲线之间的距离和为0。通过这样的方式，可以在保证拟合曲线平滑度的情况下提升拟合精度。

4. 河马优化算法

HO是一种基于河马群体的优化算法，其探索过程来源于河马种群三种突出的行为模式：位置更新、防御掠食者(探索阶段)、逃离捕食者(开发阶段)。

全局探索阶段河马围绕主导或局部最优位置更新，引入随机向量增加多样性，避免早熟；探索阶段，河马面对掠食者(局部最优陷阱)，根据距离判断威胁，转向探索并利用Levy飞行增强随机性；开发阶段，河马逃离时在当前最优附近生成随机位置，通过步长控制更新更优解，实现局部空间优化。

对于权重优化问题，尤其是当目标函数具有多个局部极值或较强的非线性特性时，HO算法能够更好地跳出局部极值，朝着全局最优解前进。同时由于HO算法对目标函数的可微性要求较低，即使目标函数存在不规则性、非光滑性或计算量大，HO算法依然能够通过启发式搜索找到较为理想的解。

相比于粒子群算法(Particle Swarm Optimization, PSO)这类优化算法，HO算法的参数更少、调参难度低，这一点在面对高维的优化问题时显得尤为重要。与此同时，HO算法通过控制搜索策略和优化过程的复杂度，可以在大规模问题中保持较好的搜索效率。

在HO算法优化过程中，河马是优化问题的候选解，这意味着每个河马在搜索空间中的位置更新代表了决策变量的值，即河马位置更新过程代表着权重的迭代过程，在最终优化结果中河马的位置代表着最佳权重。

常用优化算法如PSO算法对于目标优化也有着不错的效果，但两者初始参数的确定，对于算法优化效果有着很大的影响。

PSO优化的核心思想在于个体通过群体内信息共享协同寻找最优解，但在寻优过程中，尤其在高维问题上，依赖极值跟踪，易陷入局部最优，且对于初始种群十分敏感，敏感参数过多，对于适应度函数值有着十分大的影响。

HO算法凭借其三阶段模型，只需对种群数量进行调整，不需要确定过多敏感参数，这既能保证优化过程的稳定性，又表现出良好的优化效果。

5. 权重优化

分别利用HO、PSO优化算法对几组型值点拟合出的曲线进行权重优化，并确保两者边界条件相同，均为[0.5, 1.3]，最大迭代次数均为500次。通过迭代得到优化后的权重值，再利用新的权重进行曲线拟合，并计算误差函数值。

图2分别为HO、PSO算法对权重进行优化之后得到的多组拟合图形，由图像及数据结果得到，两种方法优化后的拟合曲线比优化前更加贴近型值点，这证明了优化权重的方法可以使得曲线拟合精度得到提升。权重为1时，五角星图形误差值为63.9911，衰减正弦图形误差值为4.6670；利用HO算法优化后的图形误差分别为33.5164、3.8013；利用PSO优化后的误差分别为53.9819、4.2496。由数据结果可知，HO优化效果最佳。PSO优化后的精度虽同样有所提升，但对各项敏感参数的调试需要大量的时间，且精度提升不如HO算法。

针对HO算法对衰减正弦图形的优化情况进行敏感性分析，当迭代次数足够多时，如400次、500次，种群数量对优化精度影响不大，这是因为种群规模的影响被“充分进化”稀释，即使种群规模较小也可通过充足的迭代逼近全局最优；当迭代次数少时，如200次，算法的进化过程未能充分实现，种群规模的缺陷会被放大，导致精度下降，此时大种群规模，可探索解空间范围更广，在一定程度上求解精度会稍好于小种群规模。对不同迭代次数下不同种群规模进行多次求解并计算均值，得到以下结果：迭代次数为500、400、300次，种群规模分别为50、40、30的求解均值稳定在4.06左右；当迭代次数为200次，种群规模为50、40、30的求解均值分别为4.10、4.13、4.14。

图3为利用HO算法对五角星拟合中的权重优化后局部放大图，可以看出优化后的拟合曲线较权重为1时的拟合曲线更加贴近型值点。图4为两种算法对各组曲线优化计算时间对比，可以看出，PSO在计算速度上最快，HO计算时间相对较长。这是因为HO为了维持“探索–开发”的混合机制，会在一代中对同一个个体产生多个候选更新，导致每代评估次数大于1次/个体，而PSO为每个新个体评估1次。

Figure 2. The optimization of the fitting of two types of graphs using HO and PSO respectively

图2. 分别使用HO、PSO对两种图形拟合进行优化

Figure 3. Magnified view of the local area of the five-pointed star shape after optimization by the HO algorithm

图3. HO算法优化五角星图形后的局部放大图

Figure 4. Comparison of calculation time between HO and PSO

图4. HO与PSO计算时间对比

通过HO算法对曲线拟合权重进行调整后，如图5所示，优化后的曲率值图呈现出更规整的峰值分布，大幅降低了极端曲率情况；另一方面，图6所示的曲率梳图中图形曲线、梳齿线、包络线贴合度提升，平滑度改善。这表明优化有效提升曲线拟合精度，让曲线形态更合理、稳定，在曲线拟合质量上成效显著，验证了优化方法的价值与效果。

Figure 5. (a) Curvature before optimization; (b) Curvature after optimization

图5. (a) 优化前曲率；(b) 优化后曲率

Figure 6. (a) Curvature comb before optimization; (b) Curvature comb after optimizations

图6. (a) 优化前曲率梳图；(b) 优化后曲率梳图

6. 结论

利用HO算法对NURBS曲线拟合中的权重进行优化，可以有效规避如PSO等优化方法的参数调试过程，极大地降低了优化难度；同时HO算法对权重的优化效果好于PSO算法。需要注意的是，该目标函数追求的是整体误差最小，因此个别型值点到优化前曲线的距离可能小于其到优化后曲线的距离。对于如何在每个型值点处尽可能地减小其与拟合曲线之间的距离误差，可作为下一步研究内容。

基金项目

甘肃省科技计划项目(2022JR5RA314, 22YF7WA151, 22YF7GA138, 23CXGA0151)。