Research On Curve And Surface Approximating Methods Based On Non-uniform B-splines

In reverse engineering,the key technique of reconstructing data models is to approximate large-scale scattered data points based on B-spline curves and surfaces.In the problem of data points approximation,the most challenging task is how to determine the knots and control points of B-spline curves and surfaces in a most effective way.The number of control points is directly proportional to the approximate accuracy,but it is inversely proportional to the computational efficiency.Therefore,the approximate accuracy of data points and computation efficiency of algorithm can not be improved at the same time.In order to alleviate the contradiction between approximation accuracy and computational efficiency,in this paper,the differential evolution algorithm(DE)and the extended progressive-iteration approximation(EPIA)are improved to enhance the approximation effect of data points.The main research work and innovations of this paper are described as follows.First,an enhanced differential evolution algorithm combined with chaotic local search(DE-CS)is presented in this paper.Due to the existence of a large number of local extremes in the least square approximation problem of B spline curves and surfaces,a chaotic mutation operator is designed in this paper,which is used to execute local search for the best individual,which can avoid falling into local optimum.This operator adaptively adjusts the search range around the best individual with a chaotic mutation coefficient,which enables the algorithm to jump out of the local optimum in the earlier evolution phase,and can improve the optimization accuracy of the algorithm in the later stage of evolution.At the same time,the combination of mutation strategy DE/current-to-best/ and crossover strategy with random walk can balance the exploration and exploitation capabilities of the algorithm.Simulations show that the new algorithm improves the approximation accuracy without reducing the computational efficiency.Compared with GA,PSO,AIS and standard DE algorithm,the approximation error of the new algorithm is smaller.Second,an extended progressive-iteration approximation algorithm with different weights(DWEPIA)is proposed in this paper.In this algorithm,a new iterative approximation format is obtained by adding different weights to the process of updating the control points,which not only increases the flexibility of operation,but also accelerates the convergence speed of the algorithm.By analyzing in theory,we prove that the iterative approximation formate of DWEPIA is convergent.For the sake of improving the approximation accuracy of the algorithm,this paper improves the rule of selecting the main feature points.By calculating the local differential curvature of the data points,the initial control points which can fully reflect the geometric features of the data points and uniformly distributed on the curve are selected.Therefore,the approximation accuracy of the data point is guaranteed.The conditions for inserting knots are improved in this paper,compared with the original EPIA algorithm,each iteration no longer just inserting one point but inserting multiple knots,which also accelerates the convergence of the algorithm.Simulation results show that compared with EPIA algorithm,the algorithm proposed in this paper has higher efficiency and better approximation effect.