CN117666471A - Micro-line segment global smoothing method and system based on improved particle swarm genetic algorithm - Google Patents

Abstract

The invention belongs to the technical field of numerical control in mechanical manufacturing engineering, and discloses a micro-segment global fairing method and system based on an improved particle swarm genetic algorithm. The method comprises the steps of screening an inflection point and a curvature extreme point from given discrete data points to serve as main characteristic points, acquiring bow-height characteristic points according to the acquired main characteristic points, adding the bow-height characteristic points into a main characteristic point set, and compressing data quantity by replacing original data points with the main characteristic points; adopting a least square method to approach the main feature points to calculate and obtain initial control points, constructing an initial population of particles by using position coordinates of the initial control points, and establishing an adaptability function for measuring fitting errors; iteration is performed using the modified particle swarm genetic algorithm. The invention compresses the data volume on the basis of ensuring the fitting precision and improves the fitting efficiency. Meanwhile, an improved particle swarm genetic algorithm with self-adaption is adopted, so that fitting accuracy is improved.

Description

Micro-segment global smoothing method and system based on improved particle swarm genetic algorithm

Technical Field

The invention belongs to the technical field of numerical control in mechanical manufacturing engineering, and in particular relates to a micro-segment global smoothing method and system based on an improved particle swarm genetic algorithm.

Background Art

With the development of science and technology and society, the industrial field has put forward higher requirements for processing quality and efficiency. Free curves and surfaces are widely used in modern industrial products, such as aerospace, automobiles, electrical or electronic products, household items and other fields. However, when processing complex curves and surfaces, traditional processing methods usually discretize the curve trajectory to be processed into a series of small line segments connected end to end according to the accuracy requirements to approximate the trajectory of the original tool. With the development of modern industrial technology, higher requirements are put forward for the processing speed and efficiency of CNC machine tools, but the curve trajectory described by the small line segments will have a sudden change in tangent direction and discontinuous curvature at the corners of adjacent line segments, which leads to speed fluctuations and acceleration mutations when the tool passes through the corners, thereby causing vibration and impact of the process system. A large number of studies have shown that smoothing the continuous small line segment path is an effective means to solve the above problems.

Through the above analysis, the problems and defects of the existing technology are as follows: the existing technology does not use the method of extracting the inflection points, curvature extreme points and bow height feature points that best reflect the trajectory shape as the main feature points instead of the original discrete data points, which makes the amount of data to be processed in mechanical processing large, the fitting efficiency is low, and the processing efficiency is affected. The existing particle swarm algorithm and genetic algorithm have their own shortcomings.

Summary of the invention

In order to overcome the problems existing in the related art, the disclosed embodiments of the present invention provide a micro-segment global smoothing method and system based on an improved particle swarm genetic algorithm.

The technical solution is as follows: a micro-segment global smoothing method based on an improved particle swarm genetic algorithm, comprising:

S1, select the inflection points and curvature extreme value points from the given discrete data points as the main feature points, obtain the bow height feature points according to the obtained main feature points, and add the bow height feature points to the main feature point set, and replace the original data points with the main feature points to compress the data volume;

S2, the initial control points are calculated by using the least squares method to approximate the main feature points, the initial particle population is constructed based on the position coordinates of the initial control points, and a fitness function is established to measure the fitting error;

S3, using the improved particle swarm genetic algorithm to iterate until the given number of iterations is reached.

In step S1, the main feature points are selected by the following steps:

Step 1.1, extraction of inflection points;

Step 1.2, extraction of curvature extreme points;

Step 1.3, extraction of bow height feature points.

In step 1.1, the extraction of inflection points includes:

For discrete data points on a two-dimensional plane, when the angle between the normal vectors of the coordinates of two adjacent data points is π, the concavity and convexity change, otherwise the concavity and convexity are consistent. Among four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , the normal vectors V _j , V _j+1 of the four consecutive data points are calculated, and the formula is as follows:

Wherein, V _j is the j normal vectors calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , Q _j-1 is the previous data point of the j-th data point, Q _j is the j-th data point, Q _j+1 is the first consecutive point of the j-th data point, Q _j+2 is the second consecutive point of the j-th data point, V _j+1 is the j+1 normal vector calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , θ is the normal vector angle threshold, |V _j | is the j absolute normal vectors calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , and |V _j+1 | is the j+1 absolute normal vector calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 ;

By setting a threshold value θ _max , it is determined whether the normal vector angle of the desired point exceeds the threshold value, and whether the desired point is an inflection point.

In step 1.2, the extraction of the extreme points of curvature includes:

Traverse all discrete data points and calculate the curvature k _i , average curvature k _avg and maximum curvature km _{a x} of each point; set a curvature threshold k _a between the average curvature and the maximum curvature; if the curvature of a point is greater than the set curvature threshold, the point is considered to be a curvature extreme point; if the curvature of a point is between the average curvature and the curvature threshold, and the curvature of the point is greater than the curvature before and after the point, the point is a curvature extreme point; the calculation formula for the curvature extreme point is as follows:

In the formula, k _i is the curvature, _ka is the curvature threshold, k _avg is the average curvature, k _i is the curvature, k _i-1 is the curvature of the point before the i-th point, and k _i+1 is the curvature of the point after the i-th point.

In step 1.3, the extraction of bow height feature points includes:

The point distance criterion is used to obtain the bow height feature points in the discrete data points, so that the obtained main feature points reflect the geometric characteristics of the original trajectory; after the curvature extreme values of the inflection points M _j and M _j+1 are extracted, the two adjacent main feature points are calculated in turn, and the maximum distance d _k from other data points between the two adjacent main feature points to the line segments M _j , M _j+1 is calculated, and the threshold is set to d _max . If d _k > d _max , Q _k is the bow height feature point and is added to the main feature point set. Subsequently, recursive calculation is performed between M _j Q _k and Q _k M _j+1 to obtain all the bow height feature points in turn, and the bow height feature points are added to the main feature point set.

In step S2, the initial control points are calculated by using the least squares method to approximate the main feature points, including:

Step 2.1, the definition of NURBS curve is:

Where, C(u) is the basis function of the NURBS curve; ω _i is the weight factor corresponding to the control point, the first and last weight factors are ω ₀ , ω _n > 0, and the rest are ω _i ≥ 0; _Pi is the n+1 control point, i = 0, 1, 2…n; Ni _,p (u) is the p-order NURBS curve basis function, and u is the independent variable;

Ni _,p (u) is calculated by De Boor recursion relation:

Wherein, _ui is the independent variable of the i-th point, ui ₊₁ is the independent variable of the i+1-th point, ui _+p is the independent variable of the i-th point p-time recursion, _up is the independent variable of the p-time recursion, _ui+p+1 is the independent variable of the i-th point p+1-time recursion, Ni _+1,p-1 (u) is the NURBS curve basis function of the i+1-th point p-1-time recursion;

Step 2.2, calculation of initial control points; parameterize the main feature points using the accumulated chord length method, and configure the node vector using the integer method; for the initial fitting data point sequence M = {M _k | k = 1, 2, 3, ... s}, the first and last control points are consistent with the feature points, that is, P ₀ = M ₀ = C(0), P _n = _Ms = C(1), and the other data points are approximated under the least squares method, and the approximation error square sum equation f is established to minimize the approximation error square sum equation f. The calculation formula is as follows:

Wherein, _Mk is the initial fitting data point sequence of the kth node, C( _uk ) is the initial fitting data point sequence of the final control point under the u _k independent variable, _Rk is the difference of the fitting data point sequence of the kth node, and _Ni,p ( _uk ) is the basis function of the p-th NURBS curve under the u _k independent variable;

R _k =M _k -N _0,p ( _uk )M ₀ -N _n,p ( _uk )M _s ,k=1,...,s-1

Wherein, N0 _,p ( _uk ) is the p-order NURBS curve basis function of the initial node under the u _k independent variable, _M0 is the initial fitting data point sequence of the initial node, _Nn,p ( _uk ) is the p-order NURBS curve basis function of the n-th node under the u _k independent variable, and _Ms is the initial fitting data point sequence of the s-th node;

In order to minimize the value of the error square sum equation f, let the partial derivative of equation f with respect to the control point _Pi be 0, and we get:

Where N _{t, p} ( _uk ) is the basis function of the p-th NURBS curve at the t-th node under the u _k independent variable;

We get a system of linear equations with n-1 unknowns:

(N ^T N)P＝R

in:

In the formula, ^NT is the T-order NURBS curve basis function, N is the NURBS curve basis function point sequence, P is the control point sequence, R is the fitting data point sequence difference point sequence, _N1,p ( _u1 ) is the p-order NURBS curve basis function of the 1st node under the _u1 independent variable, _Nn-1,p (u _s-1 ) is the p-order NURBS curve basis function of the n-1th node under the u _s-1 independent variable, _P1 is the 1st control point, _Pn-1 is the n-1th control point, _N1,p ( _u1 ) _R1 is the 1st fitting data point sequence difference of the p-order NURBS curve basis function of the 1st node under the _u1 independent variable, and _Nn-1,p (u _s-1 )Rs _-1 is the s-1th fitting data point sequence difference of the p-order NURBS curve basis function of the n-1th node under the u _s-1 independent variable.

In step S2, the initial particle population is constructed with the position coordinates of the initial control points, and a fitness function for measuring the fitting error is established, including:

Gaussian elimination method is used to solve P, the first and last control points are added, the initial control point set is obtained, and the fitting of the initial NURBS curve is completed.

In step S3, an improved particle swarm genetic algorithm is used for iteration, including:

Set the parameters of the particle swarm genetic algorithm, construct the initial particle swarm population by randomly adding the coordinates of the initial control points obtained by the least squares method to a random value in the interval [-1, 1], and set the initial velocity component of each individual to a random value of [-5, 5]; establish a suitable fitness function to determine the size of the fitting error, and introduce a linear decreasing inertia factor. Calculate the initial fitness value of each particle by the fitness function equation, compare and analyze the fitness value of each particle, and update the individual optimal position and global optimal position of the particle;

In each iteration, the inertia factor is updated, and the particle's velocity and position are updated at the same time. The calculation formula is as follows:

v _id (t+1)＝ωv _id (t)+c ₁ r ₁ [P _best (t)-x _id (t)]+c ₂ r ₂ [P _gbest (t)-x _id (t)];

x _id (t+1)=x _id (t)+v _id (t+1);

In the formula, ω is the inertia factor, v _id is the current speed of particle i in dimension d, c ₁ and c ₂ are learning factors, r ₁ and r ₂ are random numbers between [0, 1], P _best (t) is the individual optimal solution position of particle i in dimension d, x _id is the current position of particle i in dimension d, P _gbest is the global optimal solution position of the entire particle swarm in dimension d, ω _e is the inertia factor value at the termination of iteration, ω _s is the inertia factor value at the initial iteration, t is the number of iterations, v _id (t+1) is the speed of particle i in dimension d at the t+1th iteration, x _id (t+1) is the position of particle i in dimension d at the t+1th iteration, t _max is the maximum number of iterations, and ω(t) is the inertia factor of the tth iteration.

Furthermore, the fitness value of each particle is calculated according to the fitness function, and the fitness values of each particle are compared. The individuals and groups that need to be crossed are selected according to the adaptive crossover probability formula to complete the individual optimal crossover and group optimal crossover operations; the particles are mutated according to the adaptive mutation probability formula to generate new particles; the crossover adopts the random crossover method, and the mutation adopts the Gaussian mutation method; the calculation formula is as follows:

Where: _Pc and _Pm represent the particle crossover probability and mutation probability respectively, _Pcmax represents the maximum crossover probability, _Pmmax represents the maximum mutation probability, _favg represents the average fitness of the particle swarm, f′ represents the fitness value of the particle to be crossed, and f represents the fitness value of the particle to be mutated.

Another object of the present invention is to provide a micro-segment global smoothing system based on an improved particle swarm genetic algorithm, which is implemented by the micro-segment global smoothing method based on the improved particle swarm genetic algorithm, and the system comprises:

The main feature point extraction module is used to select inflection points and curvature extreme value points from given discrete data points as main feature points, obtain bow height feature points based on the obtained main feature points, and add the bow height feature points to the main feature point set. The main feature points are used to replace the original data points so that the data volume is compressed;

The initial control point calculation module is used to calculate the initial control points by using the least squares method to approximate the main feature points, construct the initial particle population with the position coordinates of the initial control points, and establish a fitness function to measure the fitting error;

The initial control point optimization module is used to iterate using the improved particle swarm genetic algorithm until a given number of iterations is reached.

Combining all the above technical solutions, the advantages and positive effects of the present invention are as follows: the present invention adopts cubic NURBS curve to fit continuous micro-segment trajectory. First, the inflection points and curvature extreme points are selected from the given discrete data points as the main feature points, and the bow height feature points are obtained according to the obtained main feature points, and added to the main feature point set. The main feature points are used to replace the original data points so that the data volume is compressed. Then, the least squares method is used to approximate the main feature points to calculate the initial control points, and the initial particle population is constructed with the position coordinates of the initial control points, and a fitness function that measures the fitting error is established, and then the improved particle swarm genetic algorithm is used to iterate until a given number of iterations is reached. The present invention ensures a high fitting accuracy while compressing the data volume.

The present invention adopts the method of extracting the inflection points, curvature extreme points and bow height feature points that can best reflect the trajectory shape as the main feature points to replace the original discrete data points, thereby compressing the data volume and improving the fitting efficiency on the basis of ensuring the fitting accuracy; on the basis of the standard particle swarm algorithm and genetic algorithm, a dynamic adaptive hybrid algorithm is designed by introducing a dynamic adaptive adjustment strategy to improve the evolution speed and convergence accuracy of the algorithm.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings herein are incorporated in and constitute a part of the specification, illustrate embodiments consistent with the present disclosure, and together with the description, serve to explain the principles of the present disclosure;

1 is a flow chart of a micro-segment global smoothing method based on an improved particle swarm genetic algorithm provided by an embodiment of the present invention;

2 is a schematic diagram of a micro-segment global smoothing method based on an improved particle swarm genetic algorithm provided by an embodiment of the present invention;

FIG3 is a schematic diagram of a method for calculating normal vectors V _j and V _j+1 according to an embodiment of the present invention;

FIG. 4 is a schematic diagram showing the principle of extracting bow height feature points provided by an embodiment of the present invention.

DETAILED DESCRIPTION

In order to make the above-mentioned objects, features and advantages of the present invention more obvious and easy to understand, the specific embodiments of the present invention are described in detail below in conjunction with the accompanying drawings. In the following description, many specific details are set forth to facilitate a full understanding of the present invention. However, the present invention can be implemented in many other ways different from those described herein, and those skilled in the art can make similar improvements without violating the connotation of the present invention, so the present invention is not limited by the specific implementation disclosed below.

The micro-line segment global smoothing method and system based on the improved particle swarm genetic algorithm provided by the embodiment of the present invention are innovative in that: the method selects inflection points and curvature extreme value points from given discrete data points as main feature points, obtains bow height feature points based on the obtained main feature points, and adds the bow height feature points to the main feature point set, and replaces the original data points with the main feature points to compress the data volume; the least squares method is used to approximate the main feature points to calculate the initial control points, and the initial particle population is constructed with the position coordinates of the initial control points, and a fitness function that measures the fitting error is established; and the improved particle swarm genetic algorithm is used for iteration. The present invention uses the method of extracting the inflection points, curvature extreme value points and bow height feature points that best reflect the shape of the trajectory as the main feature points to replace the original discrete data points, compressing the data volume on the basis of ensuring the fitting accuracy and improving the fitting efficiency. At the same time, the improved particle swarm genetic algorithm with self-adaptation is used to improve the fitting accuracy.

Embodiment 1, as shown in FIG1 , the micro-segment global smoothing method based on the improved particle swarm genetic algorithm provided by the embodiment of the present invention adopts a cubic NURBS curve to fit the continuous micro-segment trajectory, specifically comprising:

S1, select the inflection points and the curvature extreme value points from the given discrete data points as the main feature points, obtain the bow height feature points according to the obtained main feature points, and add the bow height feature points to the main feature point set, so that the data volume is compressed by replacing the original data points with the main feature points;

S2, the initial control points are calculated by using the least squares method to approximate the main feature points, the initial particle population is constructed based on the position coordinates of the initial control points, and a fitness function is established to measure the fitting error;

S3, using the improved particle swarm genetic algorithm to iterate until the given number of iterations is reached.

In step S1 of the embodiment of the present invention, the selection of main feature points includes:

The inflection points and curvature extreme points are extracted as the main feature points, and then the bow height feature points are extracted based on the inflection points and curvature extreme points, and added to the main feature point set. At the same time, in order to maintain the integrity of the shape, it is necessary to ensure that the discrete data points at both ends are not filtered out, so the first and last discrete data points need to be divided into main feature points.

In step S2 of the embodiment of the present invention, using the least squares method to perform NURBS curve fitting to obtain initial control points includes:

Before approximating the data points, we first need to determine the relevant parameters of the fitting curve, mainly the degree p of the fitting curve, the weight factor ω _i and the node vector U. Since the cubic NURBS curve achieves C ² continuity in continuity and meets the modeling requirements of engineering applications, the degree of the fitting curve is determined to be 3, the weight factor is set to 1, and the number of control points is n+1. The main feature points are parameterized by the method of accumulating chord lengths, and then the node vector is configured by the integer method.

In step S3 of the embodiment of the present invention, an improved particle swarm genetic algorithm is used to optimize the control points:

Set the parameters of the particle swarm genetic algorithm, namely the population size and the maximum number of iterations. Construct the initial particle swarm population by randomly adding a random value in the interval [-1, 1] to the coordinates of the initial control point obtained by the least squares method, and set the initial velocity component of each individual to a random value of [-5, 5]. Establish a suitable fitness function, and introduce a linearly decreasing inertia factor to ensure that the particles have a strong global search ability in the early stage and a strong local search ability in the later stage. Calculate the fitness value of each initial particle by the fitness function equation, and compare and analyze the fitness value of each particle to update the individual optimal position and the global optimal position of the particle. In each iteration, update the inertia factor, update the speed and position of the particle at the same time, calculate the fitness value of each particle according to the fitness function, compare the current fitness value of each particle with the fitness value of the individual optimal solution before the iteration, if it is less than, update the individual optimal solution, otherwise do not update. Compare the current fitness value of each particle with the fitness value of the global optimal solution, if it is less than, update the global optimal solution, otherwise do not update. Calculate the fitness value of each particle according to the fitness function, compare the fitness values of each particle, select the individuals and groups that need to cross according to the adaptive crossover probability formula, and complete the individual optimal crossover and group optimal crossover operations. Perform mutation operations on particles according to the adaptive mutation probability formula to generate new particles. Calculate the fitness value of the new particle by the fitness function equation, and compare the fitness value to update the individual optimal position and global optimal position of the particle. Determine whether the algorithm meets the termination condition. If so, end the iteration and output the result; otherwise, repeat the iteration until the maximum number of iterations is reached.

In the embodiment of the present invention, FIG. 2 provides the principle of a micro-segment global smoothing method based on an improved particle swarm genetic algorithm.

It can be seen from the above embodiments that the existing particle swarm algorithm and genetic algorithm have their own shortcomings. The particle swarm algorithm is easy to fall into the local optimal solution, and the genetic algorithm converges slowly. Therefore, an improved particle swarm genetic algorithm with self-adaptation is used to ensure that the optimal solution is obtained faster.

Furthermore, the present invention combines the particle swarm and the genetic algorithm to improve the shortcomings of the original methods while ensuring their respective advantages. At the same time, the particle swarm algorithm adopts an adaptive inertia factor, which can ensure that the algorithm has a strong global search capability in the early stage and a strong local search capability in the later stage, thereby preventing the algorithm from falling into the local optimal solution too early. The genetic algorithm proposed by the present invention adopts an adaptive crossover mutation probability, which can ensure that excellent individuals are not destroyed, thereby improving the accuracy of the optimal solution.

Example 2, as another detailed implementation of the present invention, the micro-segment global smoothing method based on the improved particle swarm genetic algorithm provided in the embodiment of the present invention includes:

Step 1, selection of main feature points:

For the discrete data point set, selecting the inflection point, curvature extreme point and bow height feature point as the main feature point can generally reflect the basic shape of the original curve trajectory. The inflection point and curvature extreme point can respectively reflect the concavity and convexity changes and smoothness changes of the original trajectory, while the bow height feature point can describe the geometric characteristics of the original trajectory. In order to maintain the integrity of the shape, it is necessary to ensure that the discrete data points at both ends are not filtered out, so it is necessary to divide the first and last discrete data points into main feature points. By selecting the main feature points to replace the discrete data point set, not only can the trajectory shape be fully represented, but also the amount of data can be greatly compressed. The method for extracting the main feature points of discrete data points is as follows.

Step 1.1, extraction of inflection points:

For discrete data points on a two-dimensional plane, when the angle between the normal vectors of the coordinates of two adjacent data points is π, it is considered that the concavity and convexity have changed, otherwise it is considered that the concavity and convexity are consistent. Taking four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 as an example, as shown in Figure 3, their normal vectors V _j and V _j+1 can be calculated. The calculation formula is as follows:

Wherein, V _j is the j normal vectors calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , Q _j-1 is the previous data point of the j-th data point, Q _j is the j-th data point, Q _j+1 is the first consecutive point of the j-th data point, Q _j+2 is the second consecutive point of the j-th data point, V _j+1 is the j+1 normal vector calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , θ is the normal vector angle threshold, |V _j | is the j absolute normal vectors calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 , and |V _j+1 | is the j+1 absolute normal vector calculated from four consecutive data points Q _j-1 , Q _j , Q _j+1 , Q _j+2 ;

You can set a threshold value θ _max yourself, and determine whether the point is an inflection point by judging whether the normal vector angle of the point exceeds the threshold.

Step 1.2, extraction of curvature extreme points:

Traverse all discrete data points and calculate the curvature k _i , average curvature k _avg and maximum curvature km _{a x} of each point. In order to prevent interference factors such as noise from affecting the extraction of curvature extreme points, a curvature threshold k _a between the average curvature and the maximum curvature is set. If the curvature of a point is greater than the set curvature threshold, the point can be considered as a curvature extreme point; if the curvature of a point is between the average curvature and the curvature threshold, and the curvature of the point is greater than the curvature before and after the point, the point is also considered as a curvature extreme point. The calculation formula for the curvature extreme point is as follows:

In the formula, k _i is the curvature, _ka is the curvature threshold, k _avg is the average curvature, k _i is the curvature, k _i-1 is the curvature of the point before the i-th point, and k _i+1 is the curvature of the point after the i-th point.

Step 1.3, extraction of bow height feature points, as shown in Figure 4;

The point distance criterion is used to obtain the bow height feature points in the discrete data points, so that the obtained main feature points can better reflect the geometric characteristics of the original trajectory. After the curvature extreme value of the inflection point _{M j} and _{M j+1} is extracted, the maximum distance d _k from other data points between the two adjacent main feature points to the line segment M _j M _j+1 is calculated in turn, and the threshold is set to d _max . If d _k > d _max , Q _k is the bow height feature point, and it is added to the main feature point set. Then, recursive calculation is performed between M _j Q _k and Q _k M _j+1 to obtain all the bow height feature points in turn and add them to the main feature point set.

Step 2: Use the least squares method to fit the NURBS curve to obtain the initial control points:

Step 2.1, definition of NURBS curve;

NURBS is a non-uniform rational B-spline curve, which is defined as:

Where: C(u) is the NURBS curve basis function, u is the independent variable; _Pi (i=0, 1, 2, ..., n) represents n+1 control points; _ωi is the weight factor corresponding to the control point, the first and last weight factors _ω0 , _ωn >0, and the rest _ωi≥0 ; Ni _,p (u) is the p-order NURBS curve basis function, and Ni _,p (u) can be calculated by the De Boor recursive relationship:

Wherein, _ui is the independent variable of the i-th point, ui ₊₁ is the independent variable of the i+1-th point, ui _+p is the independent variable of the i-th point p-time recursion, _up is the independent variable of the p-time recursion, _ui+p+1 is the independent variable of the i-th point p+1-time recursion, Ni _+1,p-1 (u) is the NURBS curve basis function of the i+1-th point p-1-time recursion;

Step 2.2, calculation of initial control points;

First, the main feature points are parameterized using the accumulated chord length method, and then the node vectors are configured using the integer method. For the initial fitting data point sequence M = {M _k | k = 1, 2, 3, ... s}, in order to prevent uncontrollable and nonlinear problems at the first and last positions, the first and last control points must be consistent with the feature points, that is, P ₀ = M ₀ = C(0), P _n = _Ms = C(1), and other data points are approximated under the least squares method, and the approximation error square sum equation f is established to minimize the approximation error square sum f. The calculation formula is as follows:

Wherein, _Mk is the initial fitting data point sequence of the kth node, C( _uk ) is the initial fitting data point sequence of the final control point under the u _k independent variable, _Rk is the difference of the fitting data point sequence of the kth node, and _Ni,p ( _uk ) is the basis function of the p-th NURBS curve under the u _k independent variable;

R _k =M _k -N _0,p ( _uk )M ₀ -N _n,p ( _uk )M _s ,k=1,...,s-1

Wherein, N0 _,p ( _uk ) is the p-order NURBS curve basis function of the initial node under the u _k independent variable, _M0 is the initial fitting data point sequence of the initial node, _Nn,p ( _uk ) is the p-order NURBS curve basis function of the n-th node under the u _k independent variable, and _Ms is the initial fitting data point sequence of the s-th node;

In order to minimize the value of the sum of squared errors f, let the partial derivative of f with respect to the control point _Pi be 0, and then we get:

Where N _{t, p} ( _uk ) is the basis function of the p-th NURBS curve at the t-th node under the u _k independent variable;

We can further obtain a linear equation system containing n-1 unknown quantities:

(N ^T N)P = R;

in:

In the formula, ^NT is the T-order NURBS curve basis function, N is the NURBS curve basis function point sequence, P is the control point sequence, R is the fitting data point sequence difference point sequence, N1 _,p (u1) is the p-order NURBS curve basis function of the 1st node under the _u1 independent variable, _Nn-1,p (u _s-1 ) is the p-order NURBS curve basis function of the n-1th node under the u _s-1 independent variable, _P1 is the 1st control point, _Pn-1 is the n-1th control point, _N1,p (u ₁ ) _R1 is the 1st fitting data point sequence difference of the p-order NURBS curve basis function of the 1st node under the _u1 independent variable, and _Nn-1,p (u _s-1 )Rs _-1 is the s-1th fitting data point sequence difference of the p-order NURBS curve basis function of the n-1th node under the u _s- independent variable.

Gaussian elimination method is used to solve P, and then the first and last control points are added to obtain the initial control point set, completing the fitting of the initial NURBS curve.

Step 3: Use improved particle swarm genetic algorithm to optimize the control points:

Set the parameters of the particle swarm genetic algorithm, namely the population size and the maximum number of iterations. Construct the initial particle swarm population by randomly adding a random value in the interval [-1, 1] to the coordinates of the initial control point obtained by the least squares method, and set the initial velocity component of each individual to a random value of [-5, 5]. Establish a suitable fitness function to determine the size of the fitting error, and introduce a linear decreasing inertia factor to ensure that the particles have a strong global search ability in the early stage and a strong local search ability in the later stage to prevent the population from falling into the local optimal solution too early. Calculate the initial fitness value of each particle by the fitness function equation, and compare and analyze the fitness value of each particle to update the individual optimal position and global optimal position of the particle.

In each iteration, the inertia factor is updated, and the particle's velocity and position are updated at the same time. The calculation formula is as follows:

v _id (t+1)＝ωv _id (t)+c ₁ r ₁ [P _best (t)-x _id (t)]+c ₂ r ₂ [P _gbest (t)-x _id (t)];

x _id (t+1)=x _id (t)+v _id (t+1);

In the formula, ω is the inertia factor, v _id is the current speed of particle i in dimension d, c ₁ and c ₂ are learning factors, r ₁ and r ₂ are random numbers between [0, 1], P _best (t) is the individual optimal solution position of particle i in dimension d, x _id is the current position of particle i in dimension d, P _gbest is the global optimal solution position of the entire particle swarm in dimension d, ω _e is the inertia factor value at the termination of iteration, ω _s is the inertia factor value at the initial iteration, t is the number of iterations, v _id (t+1) is the speed of particle i in dimension d at the t+1th iteration, x _id (t+1) is the position of particle i in dimension d at the t+1th iteration, t _max is the maximum number of iterations, and ω(t) is the inertia factor of the tth iteration.

Calculate the fitness value of each particle according to the fitness function, compare the current fitness value of each particle with the fitness value of the individual optimal solution before the iteration, if it is less than, update the individual optimal solution, otherwise do not update. Compare the current fitness value of each particle with the fitness value of the global optimal solution, if it is less than, update the global optimal solution, otherwise do not update. Calculate the fitness value of each particle according to the fitness function, compare the fitness value of each particle, select the individuals and groups that need to cross according to the adaptive crossover probability formula, and complete the individual optimal crossover and group optimal crossover operations. Perform mutation operations on the particles according to the adaptive mutation probability formula to generate new particles. The crossover adopts the random crossover method, and the mutation adopts the Gaussian mutation method. The calculation formula is as follows:

Among them: P _c and P _m represent the probability of particle crossover and mutation respectively, P _cmax represents the maximum probability of crossover, P _mmax represents the maximum probability of mutation, f _avg represents the average fitness of the particle group, f′ represents the fitness value of the particle to be crossed, and f represents the fitness value of the particle to be mutated. The adaptive crossover and mutation probability can prevent the destruction of the optimal individual, thereby improving the fitting accuracy.

The fitness function equation is used to calculate the fitness value of the new particle, and the fitness value is compared to update the individual optimal position and the global optimal position of the particle. Determine whether the algorithm meets the termination condition. If it does, the iteration ends and the result is output; otherwise, the iteration is repeated until the maximum number of iterations is reached.

Embodiment 2: The embodiment of the present invention further provides a micro-segment global smoothing system based on an improved particle swarm genetic algorithm, the system comprising:

The main feature point extraction module is used to select inflection points and curvature extreme value points from given discrete data points as main feature points, obtain bow height feature points based on the obtained main feature points, and add the bow height feature points to the main feature point set. The main feature points are used to replace the original data points so that the data volume is compressed;

The initial control point calculation module is used to calculate the initial control points by using the least squares method to approximate the main feature points, construct the initial particle population with the position coordinates of the initial control points, and establish a fitness function to measure the fitting error;

The initial control point optimization module is used to iterate using the improved particle swarm genetic algorithm until a given number of iterations is reached.

In the above embodiments, the description of each embodiment has its own emphasis. For parts that are not described or recorded in detail in a certain embodiment, reference can be made to the relevant descriptions of other embodiments.

Since the information interaction, execution process, etc. between the above-mentioned devices/units are based on the same concept as the method embodiment of the present invention, their specific functions and technical effects can be found in the method embodiment part and will not be repeated here.

Those skilled in the art can clearly understand that for the convenience and simplicity of description, only the division of the above-mentioned functional units and modules is used as an example for illustration. In practical applications, the above-mentioned function allocation can be completed by different functional units and modules as needed, that is, the internal structure of the device can be divided into different functional units or modules to complete all or part of the functions described above. The functional units and modules in the embodiments can be integrated in one processing unit, or each unit can exist physically separately, or two or more units can be integrated in one unit. The above-mentioned integrated unit can be implemented in the form of hardware or in the form of software functional units. In addition, the specific names of the functional units and modules are only for the convenience of distinguishing each other, and are not used to limit the scope of protection of the present invention. The specific working process of the units and modules in the above-mentioned system can refer to the corresponding process in the aforementioned method embodiment.

An embodiment of the present invention further provides a computer device, which includes: at least one processor, a memory, and a computer program stored in the memory and executable on the at least one processor, wherein the processor implements the steps of any of the above-mentioned method embodiments when executing the computer program.

An embodiment of the present invention further provides a computer-readable storage medium, wherein the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, the steps in the above-mentioned method embodiments can be implemented.

An embodiment of the present invention further provides an information data processing terminal, which, when executed on an electronic device, provides a user input interface to implement the steps in the above method embodiments. The information data processing terminal is not limited to mobile phones, computers, and switches.

An embodiment of the present invention further provides a server, which is used to provide a user input interface to implement the steps in the above method embodiments when executed on an electronic device.

An embodiment of the present invention provides a computer program product. When the computer program product runs on an electronic device, the electronic device can implement the steps in the above-mentioned method embodiments when executing the computer program product.

If the integrated unit is implemented in the form of a software functional unit and sold or used as an independent product, it can be stored in a computer-readable storage medium. Based on this understanding, the present application implements all or part of the processes in the above-mentioned embodiment method, which can be completed by instructing the relevant hardware through a computer program. The computer program can be stored in a computer-readable storage medium, and the computer program can implement the steps of the above-mentioned various method embodiments when executed by the processor. Among them, the computer program includes computer program code, and the computer program code can be in source code form, object code form, executable file or some intermediate form. The computer-readable medium may at least include: any entity or device that can carry the computer program code to the camera/terminal device, a recording medium, a computer memory, a read-only memory (ROM), a random access memory (RAM), an electrical carrier signal, a telecommunication signal, and a software distribution medium. For example, a USB flash drive, a mobile hard disk, a disk or an optical disk.

The above description is only a preferred specific implementation manner of the present invention, but the protection scope of the present invention is not limited thereto. Any modifications, equivalent substitutions and improvements made by any technician familiar with the technical field within the technical scope disclosed by the present invention and within the spirit and principles of the present invention should be covered within the protection scope of the present invention.

Claims (10)

1. A micro-segment global fairing method based on an improved particle swarm genetic algorithm, comprising:

s1, screening an inverse curve point and a curvature extreme point from given discrete data points to serve as main characteristic points, acquiring a bow-height characteristic point according to the acquired main characteristic points, adding the bow-height characteristic point into a main characteristic point set, and replacing original data points by the main characteristic points to compress data volume;

s2, approximating the main feature points by a least square method to calculate to obtain initial control points, constructing an initial population of particles according to position coordinates of the initial control points, and establishing an adaptability function for measuring fitting errors;

and S3, iterating by using the improved particle swarm genetic algorithm until the given iteration times are reached.

2. The method of claim 1, wherein in step S1, the principal feature points are selected by:

step 1.1, extracting the inflection points;

step 1.2, extracting curvature extreme points;

and 1.3, extracting bow height characteristic points.

3. The method of claim 2, wherein in step 1.1, the extraction of the inflection point comprises:

for discrete data points of a two-dimensional plane, when the included angle of normal vectors of coordinates of two adjacent data points is pi, the concave-convex property changes, otherwise, the concave-convex property is consistent, and the two data points are continuously four data points Q _j-1 ,Q _j ,Q _j+1 ,Q _j+2 In the method, four continuous data point normal vectors V are calculated _j ,V _j+1 The formula is as follows:

wherein V is _j For four consecutive data points Q _j-1 ,Q _j ,Q _j+1 ,Q _j+2 Calculated j normal vectors, Q _j-1 For the data point immediately preceding the jth data point, Q _j For the jth data point, Q _j+1 Continuous 1 st point, Q, for the jth data point _j+2 A 2 nd point, V, which is a succession of the jth data point _j+1 For four consecutive data points Q _j-1 ,Q _j ,Q _j+1 ,Q _j+2 J+1 normal vectors are calculated, θ is the normal vector included angle threshold, |V _j I is four consecutive data points Q _j-1 ,Q _j ,Q _j+1 ,Q _j+2 Calculated j absolute normal vectors, |V _j+1 I is four consecutive data points Q _j-1 ,Q _j ,Q _j+1 ,Q _j+2 J+1 absolute normal vectors calculated;

by setting a threshold value theta _max Judging whether the normal vector included angle of the required point exceeds a threshold value or not, and judging whether the required point is an inflection point or not.

4. The method of claim 2, wherein in step 1.2, the extraction of curvature extremum point comprises:

traversing all discrete data points and calculating curvature k of each point _i Average curvature k _avg And maximum curvature k _max The method comprises the steps of carrying out a first treatment on the surface of the Setting a curvature threshold k between the average curvature and the maximum curvature _a The method comprises the steps of carrying out a first treatment on the surface of the If the curvature of a certain point is larger than the set curvature threshold value, the certain point is considered as a curvature extreme point; if the curvature of a certain point is between the average curvature and the curvature threshold value and the curvature of the point is larger than the front-back curvature of the point, the point is a curvature extreme point; the calculation formula of curvature extreme points is as follows:

wherein k is _i Is of curvature, k _a Is the curvature threshold, k _avg For average curvature, k _i Is of curvature, k _i-1 The curvature of the point before the ith point, k _i+1 Is the curvature of the point following the i-th point.

5. The method of global fairing of micro-segments based on improved particle swarm genetic algorithm according to claim 2, wherein in step 1.3, the extracting of bow-height feature points comprises:

obtaining bow height characteristic points in discrete data points by utilizing a point distance criterion, so that the obtained main characteristic points embody the geometric characteristics of the original track; m is M _j And M _j+1 Two adjacent main feature points after the curvature extremum extraction of the anti-curvature points is completed, and sequentially calculating other data points between the two adjacent main feature points to a line segment M _j ,M _j+1 Is greater than the maximum distance d _k Setting the threshold value as d _max If d _k >d _max Q is then _k For bow high feature points, adding a main feature point set, and then at M _j Q _k And Q _k M _j+1 And (3) recursively calculating, sequentially obtaining all bow height characteristic points, and adding the bow height characteristic points into a main characteristic point set.

6. The method of claim 1, wherein in step S2, the initial control point is calculated by approximating the principal feature point by a least squares method, and the method comprises:

step 2.1, definition of nurbs curve is:

wherein, C (u) is NURBS curve basis function; omega _i For the weight factor corresponding to the control point, the first and last weight factors are omega ₀ ，ω _n >0, the rest omega _i ≥0；P _i For n+1 control points, i=0, 1,2 … n; n (N) _i,p (u) is the NURBS curve basis function p times, u being the argument;

N _i,p (u) is calculated from the De Boor recurrence relation:

wherein u is _i As an argument of the ith point, u _i+1 As an argument of the (i+1) th point, u _i+p The argument for the p-th recursion of the ith point, u _p For p recursively independent variables, u _i+p+1 The argument for the p+1st recurrence for the i-th point, N _i+1,p-1 (u) is the NURBS curve basis function of the i+1st point p-1 th recurrence;

step 2.2, calculating an initial control point; parameterizing main characteristic points by adopting an accumulation chord length method, and configuring node vectors by adopting a rounding method; for the initial fitting data point column m= { M _k I k=1, 2,3, … s }, the first and last control points are consistent with the feature points, i.e. P ₀ ＝M ₀ ＝C(0)，P _n ＝M _s =c (1), other data points are approximated by the least square method, and an approximation error sum of squares equation f is established, so that the approximation error sum of squares equation f is minimum, and the calculation formula is as follows:

wherein M is _k Initial fitting of data point columns for kth node, C (u _k ) To u is _k Initial fitting of final control point under independent variable to data point column, R _k Fitting data point column difference values for kth node, N _i,p (u _k ) To u is _k An independent variable p times NURBS curve basis function;

R _k ＝M _k -N _0,p (u _k )M ₀ -N _n,p (u _k )M _s ，k＝1,…,s-1

wherein N is _0,p (u _k ) U is the initial node _k The basis function of the NURBS curve, M, p times under the independent variable ₀ Initial fitting of data point columns for initial nodes, N _u,p (u _k ) At u for the nth node _k The basis function of the NURBS curve, M, p times under the independent variable _s Initially fitting a data point column for the s-th node;

to minimize the value of the sum of squares error equation f, equation f is made relative to control point P _i The partial derivative is 0, and the following is obtained:

wherein N is _t,p (u _k ) At u for the t-th node _k An independent variable p times NURBS curve basis function;

a linear system of equations is obtained containing n-1 unknowns:

(N ^T N)P＝R

wherein:

wherein N is ^T For the T-order NURBS curve base function, N is the NURBS curve base function point array, P is the control point array, R is the fitting data point array difference point array, N _1,p (u ₁ ) At node 1 u ₁ The basis function of the NURBS curve under the independent variable p times, N _n-1,p (u _s-1 ) At u for the n-1 node _s-1 The basis function of the NURBS curve, P, under the independent variable, P times ₁ For control point 1, P _n-1 N is the N-1 th control point, N _1,p (u ₁ )R ₁ At node 1 u ₁ 1 st fit data point column difference, N of p times NURBS curve basis function under independent variable _n-1,p (u _s-1 )R _s-1 At u for the n-1 node _s-1 The s-1 th fit of the NURBS curve basis function at the argument is the data point column difference.

7. The method of claim 1, wherein in step S2, constructing an initial population of particles with position coordinates of initial control points and establishing a fitness function that measures fitting errors, comprises:

and solving P by adopting a Gaussian elimination method, adding the first control point and the last control point to obtain an initial control point set, and completing the fitting of an initial NURBS curve.

8. The method of claim 1, wherein in step S3, the iteration is performed using the modified particle swarm genetic algorithm, comprising:

setting parameters of a particle swarm genetic algorithm, constructing an initial particle swarm population by randomly adding random values in an [ -1,1] interval to the coordinates of an initial control point obtained by a least square method, and setting the initial velocity component of each individual to be the random value of [ -5,5 ]; establishing a proper fitness function to judge the fitted error, introducing a linear decreasing inertia factor, calculating an initial fitness value of each particle according to a fitness function equation, comparing and analyzing the fitness value of each particle, and updating the individual optimal position and the global optimal position of the particle;

in each iteration, the inertia factor is updated, and meanwhile, the speed and the position of the particles are updated, and the calculation formula is as follows:

v _id (t+1)＝ωv _id (t)+c ₁ r ₁ [P _best (t)-x _id (t)]+c ₂ r ₂ [P _gbest (t)-x _id (t)]；

x _id (t+1)＝x _id (t)+v _id (t+1)；

wherein ω is an inertial factor, v _id For the current velocity of particle i in d dimension, c ₁ ,c ₂ Are learning factors, r ₁ ,r ₂ Is [0,1]Random number, P between _best (t) is the individual optimal solution position of particle i in d dimension, x _id For the current position of particle i in d-dimension, P _gbest For the global optimal solution position of the current whole particle swarm in d dimension, omega _e To terminate the value of the inertia factor, ω, at the time of iteration _s The value of the inertia factor in initial iteration is t, the iteration times is v _id (t+1) is the speed of the t+1st iteration of the particle i in d-dimension, x _id (t+1) is the position of particle i in the t+1st iteration of the d-dimension, t _max For the maximum number of iterations, ω (t) is the inertia factor of the t-th time.

9. The micro-segment global fairing method based on the improved particle swarm genetic algorithm according to claim 8, wherein the fitness values of all particles are calculated according to a fitness function, the fitness values of all particles are compared, and individuals and groups needing to be crossed are selected according to a self-adaptive cross probability formula to complete the optimal crossing operation of the individuals and the optimal crossing operation of the groups; performing mutation operation on the particles according to the self-adaptive mutation probability formula to generate new particles; wherein the cross adopts a random cross mode, and the mutation adopts a Gaussian mutation mode; the calculation formula is as follows:

wherein: p (P) _c And P _m Respectively represent the particle cross probability and the variation probability, P _cmax Represents the maximum crossover probability, P _mmax Represents the maximum mutation probability, f _avg Represents the average fitness of the population of particles,f' represents the fitness value of the particles to be crossed, and f represents the fitness value of the particles to be mutated.

10. A micro-segment global fairing system based on an improved particle swarm genetic algorithm, the system being implemented by the micro-segment global fairing method based on an improved particle swarm genetic algorithm according to any of claims 1-9, the system comprising:

the main feature point extraction module is used for screening out a sigmoid point and a curvature extreme point from given discrete data points to serve as main feature points, acquiring bow-height feature points according to the acquired main feature points, adding the bow-height feature points into a main feature point set, and compressing data quantity by replacing original data points with the main feature points;

the initial control point calculation module is used for approximating the main characteristic points by adopting a least square method to calculate to obtain initial control points, constructing an initial population of particles by using position coordinates of the initial control points, and establishing an adaptability function for measuring fitting errors;

and the initial control point optimization module is used for iterating by utilizing the improved particle swarm genetic algorithm until the given iteration times are reached.