粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合

doi:10.11772/j.issn.1001-9081.2021050777

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (7): 2177-2183.DOI: 10.11772/j.issn.1001-9081.2021050777

• 多媒体计算与计算机仿真 • 上一篇下一篇

粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合

盖荣丽¹(), 高守传¹, 李明霞²^,³^,⁴

^1.大连大学信息工程学院, 辽宁大连 116622
^2.中国科学院沈阳计算技术研究所, 沈阳 110168
^3.中国科学院大学, 北京 100049
^4.大连工业大学信息科学与工程学院, 辽宁大连 116034

收稿日期:2021-05-13 修回日期:2022-01-14 接受日期:2022-02-18 发布日期:2022-03-08 出版日期:2022-07-10
通讯作者: 盖荣丽
作者简介:高守传（1995—），男，山东滨州人，硕士研究生，CCF会员，主要研究方向：曲线曲面建模、智能控制
李明霞（1980—），女，山东烟台人，硕士，主要研究方向：运动控制。
基金资助:
国家自然科学基金资助项目(61602074);辽宁省自然科学基金指导计划项目(2019?ZD?0309)

Non-uniform rational B spline curve fitting of particle swarm optimization algorithm solving optimal control points

Rongli GAI¹(), Shouchuan GAO¹, Mingxia LI²^,³^,⁴

^1.School of Information Engineering，Dalian University，Dalian Liaoning 116622，China
^2.Shenyang Institute of Computing Technology，Chinese Academy of Sciences，Shenyang Liaoning 110168，China
^3.University of Chinese Academy of Sciences，Beijing 100049，China
^4.School of Information Science and Engineering，Dalian Polytechnic University，Dalian Liaoning 116034，China

Received:2021-05-13 Revised:2022-01-14 Accepted:2022-02-18 Online:2022-03-08 Published:2022-07-10
Contact: Rongli GAI
About author:GAO Shouchuan， born in 1995， M. S. candidate. His research interests include curve and surface modeling， intelligent control.
LI Mingxia， born in 1980， M. S. Her research interests include motion control.
Supported by:
National Natural Science Foundation of China(61602074);Liaoning Provincial Natural Fund Guidance Program(2019-ZD-0309)

摘要/Abstract

摘要：

为使参数曲线拟合在压缩数据量的基础上仍能保持较高的精度，提出了一种基于特征点提取、最小二乘法逼近以及粒子群优化算法求解最优控制点的高精度非均匀有理B样条（NURBS）曲线拟合方法。首先，以反曲点和曲率极值点作为筛选依据从所有离散数据点中提取特征点；然后，将特征点在最小二乘法下逼近，并根据所得线性方程组计算得到初始控制点；最后，以初始控制点的位置坐标构造粒子初始种群，并建立一个衡量离散数据点与拟合曲线误差的适应度函数，且利用粒子群优化算法对初始控制点的位置进行迭代优化，直至达到最大迭代次数为止。在叶片和蝴蝶截面原型上进行的实验验证的结果表明，所提方法使待拟合数据量分别压缩为原来数据量的25/117和120/283，且与以精度高为优势的增加辅助控制点的方法相比，所提方法的拟合精度分别提高了57.1%和22.9%，在已有曲线拟合研究方法中具有较强竞争力。

关键词: 粒子群优化算法, 最优控制点, 最小二乘法, 非均匀有理B样条曲线, 反曲点, 曲率极值点

Abstract:

In order to maintain high precision of parameter curve fitting on the basis of compressed data， a high-precision Non-uniform Rational B Spline （NURBS） curve fitting method was proposed based on feature point extraction， least square approximation and particle swarm optimization algorithm solving optimal control points. Firstly， feature points were extracted from all discrete data points based on the inflection point and curvature extreme points. Then， the characteristic points were approximated by the least square method， and the initial control points were calculated according to the obtained linear system of equations. Finally， the initial population of particles was constructed by the position coordinates of the initial control points， and a fitness function was established to measure the errors between the discrete data point and the fitting curve. The positions of the initial control points were iteratively optimized by the particle swarm optimization algorithm until the maximum number of iterations was reached. The results of experimental verification on blade and butterfly section prototypes show that the amount of data to be fitted is compressed to the 25/117 and 120/283 respectively of the original one by using the proposed method. Compared with the method of adding auxiliary control points with high accuracy as advantage， the proposed method has the fitting accuracy 57.1% and 22.9% higher， indicating strong competitiveness of the method in the existing curve fitting research methods.

Key words: particle swarm optimization algorithm, optimal control point, least square method, Non-Uniform Rational B Spline (NURBS) curve, inflection point, curvature extreme point

中图分类号:

TP391.41

盖荣丽, 高守传, 李明霞. 粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合[J]. 计算机应用, 2022, 42(7): 2177-2183.

Rongli GAI, Shouchuan GAO, Mingxia LI. Non-uniform rational B spline curve fitting of particle swarm optimization algorithm solving optimal control points[J]. Journal of Computer Applications, 2022, 42(7): 2177-2183.

图/表 17

图1 NURBS曲线拟合算法流程

Fig. 1 Flow chart of NURBS curve fitting algorithm

图2 叶片截面原型

Fig. 2 Blade section prototype

图3 叶片特征点

Fig. 3 Blade feature points

图4 叶片初始控制点

Fig. 4 Blade initial control points

图5 叶片最优控制点

Fig. 5 Blade optimal control points

图6 粒子群优化适应度算法迭代1

Fig. 6 Particle swarm optimization fitness algorithm iteration 1

图7 叶片截面NURBS曲线拟合

Fig. 7 NURBS curve fitting of blade section

表1 叶片误差及时间对比

Tab. 1 Blade error and time comparison

方法

最大误差/

平均误差/

均方差/

平均

耗时/s

图8 叶片拟合误差分布

Fig. 8 Blade fitting error distribution

图9 蝴蝶截面原型

Fig. 9 Butterfly section prototype

图10 蝴蝶特征点

Fig. 10 Butterfly feature points

图11 蝴蝶初始控制点

Fig. 11 Butterfly initial control points

图12 蝴蝶最优控制点

Fig. 12 Butterfly optimal control points

图13 粒子群优化适应度算法迭代2

Fig. 13 Particle swarm optimization fitness algorithm iteration 2

图14 蝴蝶截面NURBS曲线拟合

Fig. 14 NURBS curve fitting of butterfly section

表2 蝴蝶误差及时间对比

Tab. 2 Butterfly error and time comparison

方法	最大误差/mm	平均误差/mm	均方差/mm	平均耗时/s
最小二乘法	0.030	0.008 3	0.008 3	1.11
文献［8］方法	0.026	0.003 5	0.003 7	1.96
本文方法	0.010	0.002 7	0.002 6	5.13

图15 蝴蝶拟合误差分布

Fig. 15 Butterfly fitting error distribution

参考文献 21

1	VÁRADY T， MARTIN R R， COX J. Reverse engineering of geometric models — an introduction［J］. Computer-Aided Design， 1997， 29（4）：255-268. 10.1016/s0010-4485(96)00054-1
2	NI H P， YUAN J P， JI S， et al. Feedrate scheduling of NURBS interpolation based on a novel jerk-continuous ACC/DEC algorithm［J］. IEEE Access， 2018， 6： 66403-66417. 10.1109/access.2018.2813334
3	LAUBE P， FRANZ M O， UMLAUF G. Deep learning parametrization for B-spline curve approximation［C］// Proceedings of the 2018 International Conference on 3D Vision. Piscataway： IEEE， 2018： 691-699. 10.1109/3dv.2018.00084
4	凌海雅，赵仕卿，陆利正，等. 空间曲线基于内在几何量的高质量采样和B样条拟合［J］. 计算机辅助设计与图形学学报， 2020， 32（2）：255-261.
	LING H Y， ZHAO S Q， LU L Z， et al. High-quality sampling and B-spline fitting for spatial curves using intrinsic geometric quantities［J］. Journal of Computer-Aided Design and Computer Graphics， 2020， 32（2）：255-261.
5	BI Q Z， HUANG J， LU Y A， et al. A general， fast and robust B-spline fitting scheme for micro-line tool path under chord error constraint［J］. SCIENCE CHINA Technological Sciences， 2019， 62（2）： 321-332. 10.1007/s11431-018-9374-6
6	BUREICK J， ALKHATIB H， NEUMANN I. Fast converging elitist genetic algorithm for knot adjustment in B-spline curve approximation［J］. Journal of Applied Geodesy， 2019， 13（4）： 317-328. 10.1515/jag-2018-0015
7	李莎莎，徐惠霞，邓重阳. 数据点加权最小二乘渐进迭代逼近及其B样条曲线拟合［J］. 计算机辅助设计与图形学学报， 2019， 31（9）：1574-1580.
	LI S S， XU H X， DENG C Y. Data-weighted least square progressive and iterative approximation and related B-spline curve fitting［J］. Journal of Computer-Aided Design and Computer Graphics， 2019， 31（9）：1574-1580.
8	任利娟，张广鹏，王元，等. 基于压缩控制点的B样条曲线重构算法［J］. 西安理工大学学报， 2019， 35（2）：163-171.
	REN L J， ZHANG G P， WANG Y， et al. B-spline curve reconstruction algorithm based on compression control points［J］. Journal of Xi’an University of Technology， 2019， 35（2）：163-171.
9	马淑梅，罗曦，李爱平，等. 船舶工业机器人曲面喷涂喷枪轨迹离线规划［J］. 同济大学学报（自然科学版）， 2017， 45（2）：289-295.
	MA S M， LUO X， LI A P， et al. Offline trajectory planning on curved surface for spray painting robot in shipbuilding industry［J］. Journal of Tongji University （Natural Science）， 2017， 45（2）：289-295.
10	纪小刚，杨艳，薛杰. 基于多分辨技术的任意控制顶点曲面光顺［J］. 机械工程学报， 2015， 51（11）：159-164. 10.3901/jme.2015.11.159
	JI X G， YANG Y， XUE J. Multi-resolution analysis based fairing algorithm to surfaces with any amount of control vertices［J］. Journal of Mechanical Engineering， 2015， 51（11）：159-164. 10.3901/jme.2015.11.159
11	TIAN X Q， KONG L F， KONG D M， et al. An improved method for NURBS surface based on particle swarm optimization BP neural network［J］. IEEE Access， 2020， 8： 184656-184663. 10.1109/access.2020.3029563
12	王允森，盖荣丽，孙一兰，等. 面向高质量加工的NURBS曲线插补算法［J］. 计算机辅助设计与图形学学报， 2013， 25（10）：1549-1556.
	WANG Y S， GAI R L， SUN Y L， et al. NURBS interpolation algorithm for high-quality machining［J］. Journal of Computer-Aided Design and Computer Graphics， 2013， 25（10）：1549-1556.
13	HU D F， GUO J W. Tool path optimization algorithm of spatial cam flank milling based on NURBS surface［J］. Journal of the Brazilian Society of Mechanical Sciences and Engineering， 2018， 40（4）： No.170. 10.1007/s40430-018-1092-x
14	WANG Q， ZHOU W， CHENG Y G， et al. A NURBS-enhanced improved interpolating boundary element-free method for 2D potential problems and accelerated by fast multipole method［J］. Engineering Analysis with Boundary Elements， 2019， 98： 126-136. 10.1016/j.enganabound.2018.10.008
15	杨萍，杨明泰，张阳阳. 高速数控加工中NURBS曲线拟合及插补技术的研究［J］. 中国机械工程， 2015， 26（12）：1630-1634. 10.3969/j.issn.1004-132X.2015.12.013
	YANG P， YANG M T， ZHANG Y Y. Research on technologies of NURBS curve fitting and interpolation in high speed NC machining［J］. China Mechanical Engineering， 2015， 26（12）：1630-1634. 10.3969/j.issn.1004-132X.2015.12.013
16	MAHMOOD M， MATHAVAN S， RAHMAN M. A parameter-free discrete particle swarm algorithm and its application to multi-objective pavement maintenance schemes［J］. Swarm and Evolutionary Computation， 2018， 43： 69-87. 10.1016/j.swevo.2018.03.013
17	WANG B F， LI S， GUO J， et al. Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm［J］. Neurocomputing， 2018， 282： 42-51. 10.1016/j.neucom.2017.12.015
18	SHAFAEI A， KHAYATI G R. A predictive model on size of silver nanoparticles prepared by green synthesis method using hybrid artificial neural network-particle swarm optimization algorithm［J］. Measurement， 2020， 151： No.107199. 10.1016/j.measurement.2019.107199
19	闫涛，刘凤娴，陈斌. 基于量子混沌粒子群优化算法的分数阶超混沌系统参数估计［J］. 电子学报， 2018， 46（2）：333-340. 10.3969/j.issn.0372-2112.2018.02.011
	YAN T， LIU F X， CHEN B. New quantum chaos particle swarm optimization algorithm for estimating the parameter of fractional order hyper chaotic system［J］. Acta Electronica Sinica， 2018， 46（2）：333-340. 10.3969/j.issn.0372-2112.2018.02.011
20	RUI J W， ZHANG H B， ZHANG D L， et al. Total organic carbon content prediction based on support-vector-regression machine with particle swarm optimization［J］. Journal of Petroleum Science and Engineering， 2019， 180： 699-706. 10.1016/j.petrol.2019.06.014
21	张丹丹，罗可. 一种结合粒子群和粗糙集的聚类算法［J］. 小型微型计算机系统， 2016， 37（9）：2040-2045. 10.3969/j.issn.1000-1220.2016.09.028
	ZHANG D D， LUO K. Clustering algorithm based on particle swarm optimization and rough set［J］. Journal of Chinese Computer Systems， 2016， 37（9）：2040-2045. 10.3969/j.issn.1000-1220.2016.09.028

[1]	刘栋, 李晨航, 吴长茂, 茹法鑫, 夏媛媛. 基于可校正强化搜索遗传算法的光学系统自动设计[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2838-2847.
[2]	高培根, 锁斌. 基于加权犹豫模糊集的实验设计与分阶段PSO-Kriging建模[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2144-2150.
[3]	杜晓昕, 周薇, 王浩, 郝田茹, 王振飞, 金梅, 张剑飞. 智能算法的亚群优化策略综述[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 819-830.
[4]	王震, 张珊珊, 邬斌扬, 苏万华. 基于自适应粒子群优化算法的串联复合涡轮储能优化策略[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 611-618.
[5]	梁军, 洪泽泓, 余松森. 基于改进粒子群优化算法和遗传变异的图像分割模型[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1743-1749.
[6]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[7]	于振华, 刘争气, 刘颖, 郭城. 基于自适应混合粒子群优化的软件缺陷预测特征选择方法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1206-1213.
[8]	马学森, 许雪梅, 蒋功辉, 乔焰, 周天保. 混合自适应粒子群工作流调度优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 474-483.
[9]	柳春锋, 李峥, 王居凤. 分布式工厂中微型制造单元多目标优化[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3824-3832.
[10]	高兵, 郑雅, 秦静, 邹启杰, 汪祖民. 基于麻雀搜索算法和改进粒子群优化算法的网络入侵检测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1201-1206.
[11]	聂方鑫, 王宇嘉, 贾欣. 教与学信息交互粒子群优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 874-882.
[12]	张京, 朱爱红. 基于遗传算法和粒子群优化的列车自动驾驶速度曲线优化方法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 599-605.
[13]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[14]	张齐林, 李方伟, 王明月. 基于时间反演的到达时间定位[J]. 计算机应用, 2021, 41(3): 820-824.
[15]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.

粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合

Non-uniform rational B spline curve fitting of particle swarm optimization algorithm solving optimal control points

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 21

相关文章 15

编辑推荐

Metrics