Automatic knot adjustment using an artificial immune system for B-spline curve approximation

Reverse engineering transforms real parts into engineering concepts or models. First, sampled points are mapped from the object’s surface by using tools such as laser scanners or cameras. Then, the sampled points are fitted to a free-form surface or a standard shape by using one of the geometric modeling techniques. The curves on the surface have to be modeled before surface modeling. In order to obtain a good B-spline curve model from large data, the knots are usually respected as variables. A curve is then modeled as a continuous, nonlinear and multivariate optimization problem with many local optima. For this reason it is very difficult to reach a global optimum. In this paper, we convert the original problem into a discrete combinatorial optimization problem like in Yoshimoto et al. [F. Yoshimoto, M. Moriyama, T. Harada, Automatic knot placement by a genetic algorithm for data fitting with a spline, in: Proceedings of the International Conference on Shape Modeling and Applications, IEEE Computer Society Press, 1999, pp. 162–169] and Sarfraz et al. [M. Sarfraz, S.A. Raza, Capturing outline of fonts using genetic algorithm and splines, in: Fifth International Conference on Information Visualisation (IV’01), 2001, pp. 738–743]. Then, we suggest a new method that solves the converted problem by artificial immune systems. We think the candidates of the locations of knots as antibodies. We define the affinity measure benefit from Akaike’s Information Criterion (AIC). The proposed method determines the appropriate location of knots automatically and simultaneously. Furthermore, we do not need any subjective parameter or good population of initial location of knots for a good iterative search. Some examples are also given to demonstrate the efficiency and effectiveness of our method.