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

doi:10.11772/j.issn.1001-9081.2021050777

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (7): 2177-2183.DOI: 10.11772/j.issn.1001-9081.2021050777

• Multimedia computing and computer simulation • Previous Articles Next Articles

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)

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

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

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

通讯作者: 盖荣丽
作者简介:高守传（1995—），男，山东滨州人，硕士研究生，CCF会员，主要研究方向：曲线曲面建模、智能控制
李明霞（1980—），女，山东烟台人，硕士，主要研究方向：运动控制。
基金资助:
国家自然科学基金资助项目(61602074);辽宁省自然科学基金指导计划项目(2019?ZD?0309)

Abstract

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

摘要：

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

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

CLC Number:

TP391.41

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.

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

Figures/Tables 17

Fig. 1 Flow chart of NURBS curve fitting algorithm

Fig. 2 Blade section prototype

Fig. 3 Blade feature points

Fig. 4 Blade initial control points

Fig. 5 Blade optimal control points

Fig. 6 Particle swarm optimization fitness algorithm iteration 1

Fig. 7 NURBS curve fitting of blade section

Tab. 1 Blade error and time comparison

方法

最大误差/

平均误差/

均方差/

平均

耗时/s

Fig. 8 Blade fitting error distribution

Fig. 9 Butterfly section prototype

Fig. 10 Butterfly feature points

Fig. 11 Butterfly initial control points

Fig. 12 Butterfly optimal control points

Fig. 13 Particle swarm optimization fitness algorithm iteration 2

Fig. 14 NURBS curve fitting of butterfly section

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

Fig. 15 Butterfly fitting error distribution

References 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]	Dong LIU, Chenhang LI, Changmao WU, Faxin RU, Yuanyuan XIA. Automatic design of optical systems based on correctable reinforced search genetic algorithm [J]. Journal of Computer Applications, 2024, 44(9): 2838-2847.
[2]	ZENG Minghua, QUAN Ke. Improved hybrid cuckoo search-based quantum-behaved particle swarm optimization algorithm for bi-level programming [J]. Journal of Computer Applications, 2020, 40(7): 1908-1912.
[3]	ZHANG Qing, ZHENG Yan. Civil aviation engine module maintenance level decision-making and cost optimization based on annealing frog leaping particle swarm algorithm [J]. Journal of Computer Applications, 2020, 40(12): 3541-3549.
[4]	WU Xuchen, PIAO Chunhui, JIANG Xuehong. Siting model of electric taxi charging station based on GPU parallel computing [J]. Journal of Computer Applications, 2019, 39(10): 3071-3078.
[5]	ZHANG Xin, ZOU Dexuan, SHEN Xin. Hybrid two-norm particle swarm optimization algorithm with crossover term [J]. Journal of Computer Applications, 2018, 38(8): 2148-2156.
[6]	WANG Yue, FAN Xianxing, LIU Jincheng, PANG Zhenying. Lane line recognition using region division on structured roads [J]. Journal of Computer Applications, 2015, 35(9): 2687-2691.
[7]	LIU Jianlei, LIU Xiaoliang. Visibility estimation algorithm for fog weather based on inflection point line [J]. Journal of Computer Applications, 2015, 35(2): 528-530.
[8]	QIAO Yinqi, XIAO Jianhua, HUANG Yinhe, YIN Kuiying. Randomized Hough transform straight line detection based on least square correction [J]. Journal of Computer Applications, 2015, 35(11): 3312-3315.
[9]	HUANG Huiqun SUN Hong. Network intrusion detection based on particle swarm optimization algorithm and information gain [J]. Journal of Computer Applications, 2014, 34(6): 1686-1688.
[10]	WANG Gang SHI Shoudong LIN Yibing. Pitch measurement methed of twisted-pair wire based on image detection [J]. Journal of Computer Applications, 2014, 34(10): 3014-3019.
[11]	LIU Xu WU Ling CHEN Niannian FAN Yong DUAN Jingjing REN Xinyu XIA Jingjing. Tilt correction algorithm based on aggregation of grating projection sequences [J]. Journal of Computer Applications, 2013, 33(11): 3209-3212.
[12]	. Sub-pixel edge detection algorithm based on Gauss fitting [J]. Journal of Computer Applications, 2011, 31(01): 179-181.
[13]	. Color image segmentation of normalized cut and particle swarm optimization algorithm [J]. Journal of Computer Applications, 2010, 30(12): 3258-3261.
[14]	. Multi-objective PSO based on infeasibility degree and principle of endocrine [J]. Journal of Computer Applications, 2010, 30(07): 1885-1888.
[15]	. Optimal operation of reservoir based on dynamic programming and particle swarm optimization [J]. Journal of Computer Applications, 2010, 30(06): 1550-1551.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 17

References 21

Related Articles 15

Recommended Articles

Metrics