Search

This paper introduces a new memetic optimization algorithm called MeSA (Memetic Simulated Annealing) to address the data fitting problem with local-support free-form curves. The proposed method hybridizes simulated annealing with the COBYLA local search optimization method. This approach is further combined with the centripetal parameterization and the Bayesian information criterion to compute all free variables of the curve reconstruction problem with B-splines. The performance of our approach is evaluated by its application to four different shapes with local deformations and different degrees of noise and density of data points. The MeSA method has also been compared to the non-memetic version of SA. Our results show that MeSA is able to reconstruct the underlying shape of data even in the presence of noise and low density point clouds. It also outperforms SA for all the examples in this paper. [ABSTRACT FROM AUTHOR]

Abstract: Free-form parametric surfaces are common tools nowadays in many applied fields, such as Computer-Aided Design & Manu- facturing (CAD/CAM), virtual reality, medical imaging, and many others. A typical problem in this setting is to fit surfaces to 3D noisy data points obtained through either laser scanning or other digitizing methods, so that the real data from a physical object are transformed back into a fully usable digital model. In this context, the present paper describes an immunological- based approach to perform this process accurately by using the classical free-form Bézier surfaces. Our method applies a powerful bio-inspired paradigm called Artificial Immune Systems (AIS), which is receiving increasing attention from the sci- entific community during the last few years because of its appealing computational features. The AIS can be understood as a computational methodology based upon metaphors of the biological immune system of humans and other mammals. As such, there is not one but several AIS algorithms. In this chapter we focus on the clonal selection algorithm (CSA), which explicitly takes into account the affinity maturation of the immune response. The paper describes how the CSA algorithm can be effectively applied to the accurate fitting of 3D noisy data points with Bézier surfaces. To this aim, the problem to be solved as well as the main steps of our solving method are described in detail. Some simple yet illustrative examples show the good performance of our approach. Our method is conceptually simple to understand, easy to implement, and very general, since no assumption is made on the set of data points or on the underlying function beyond its continuity. As a consequence, it can be successfully applied even under challenging situations, such as the absence of any kind of information regarding the underlying function of data. [Copyright &y& Elsevier]

Abstract: Data fitting through -splines improves dramatically if the knots are treated as free variables. However, in that case the approximation problem becomes a very difficult continuous multimodal and multivariate nonlinear optimization problem. In a previous paper, Yoshimoto et al. (2003) solved this problem for explicit curves by using a real-code genetic algorithm. However, the method does not really deal with true multiple knots, so the cases of data with underlying functions having discontinuities and cusps are not fully addressed. In this paper, we present a new method to overcome such a limitation. The method applies the particle swarm optimization (PSO) paradigm to compute an appropriate location of knots automatically. Our scheme yields very accurate results even for curves with singularities and/or cusps. Several experiments show that our proposal is very efficient and improves previous results (including those by Yoshimoto et al. (2003) in ) significantly in terms of data points error, AIC and BIC criteria. Furthermore, the important case of true multiple knots is now satisfactorily solved. [Copyright &y& Elsevier]