Paper Info
Title
Curve Approximation By Adaptive Neighborhood Simulated Annealing And Piecewise Bezier Curves
Abstract
The curve approximation problem is widely researched in CAD/CAM and geometric modelling. The problem consists in determining an approximating curve from a given sequence of points. The usual approach is the minimization of the discrepancy between the approximating curve and the given sequence of points. However, the minimization of just the discrepancy leads to the overfitting problem, in which the solution is not unique. A new approach is proposed to overcome this problem, in which the length of the approximating curve is used as a regularization increasing the algorithm stability. Another new proposal is the discrepancy determination, in which a method that has the best ratio between accuracy and processing time is proposed. A new simulated annealing (SA) approach is used to minimize the problem, in which the next candidate is determined by a probability distribution controlled by the crystallization factor. The crystallization factor is low for higher temperatures ensuring the exploration of the domain. The crystallization factor is high for lower temperatures, corresponding the refinement phase of the SA. The approximating curve is represented as a piecewise cubic Bezier curve, which is a sequence of several connected cubic Bezier curves. The piecewise Bezier curve supports a new proposed data structure that improves the proposed algorithm. A comparison is also made between the used single-objective SA and the AMOSA multi-objective SA. The results showed that the proposed single-objective SA finds a solution which is not dominated by the Pareto front determined by AMOSA. The results also showed that the regularization stabilized the algorithm, in which the increase in parameters does not lead to the overfitting problem. The proposed algorithm can process even complex curves with self-intersections and higher curvature.
Year
DOI
Venue
2020
10.1007/s00500-020-05114-0
SOFT COMPUTING
Keywords
DocType
Volume
Piecewise Bezier curve, Curve approximation, Adaptive neighborhood simulated annealing, Multi-objective simulated annealing
Journal
24
Issue
ISSN
Citations 
24
1432-7643
1
PageRank 
References 
Authors
0.35
0
6
Name
Order
Citations
PageRank
Edson K. Ueda121.07
André Kubagawa Sato2144.82
Thiago de Castro Martins3186.73
Rogerio Yugo Takimoto442.13
Roberto Silvio Ubertino Rosso521.74
Marcos Sales Guerra Tsuzuki6327.61