B-Spline Eğri Uydurmada Optimum Serbest Düğüm Noktalarının Seçilmesi için Guguk Kuşu Arama Algoritması

Abstract

Genellikle eğriyi yeniden oluşturmak olarak bilinen eğrilere veri noktaları uydurma, bilgisayar destekli tasarım / imalat alanında (CAD / CAM) önemli bir problemdir. 3D lazer tarama ile elde edilen genellikle yüksek boyutlu ve gürültülü bir diziden oluşan veri noktalarının serbest forma sahip bir parametrik eğriye (tipik olarak bir B-spline) uydurulması gereken tersine mühendislik alanında bu problemle sıklıkla karşılaşılmaktadır. Bu problemin üstesinden gelebilmek için çok sayıda yöntem mevcut olmasına rağmen, şu ana kadar problemin tatmin edici genel bir çözümü elde edilebilmiş değildir. Bu çalışmada, eğri uydurma problemini çözmek için, doğadaki diğer evcil kuşların yuvalarına yumurtalarını bırakan guguk kuşlarından esinlenilerek geliştirilmiş optimizasyon yöntemlerinden biri olan Guguk kuşu arama algoritması (CS) kullanılmıştır. Veri noktalarından eğri elde etmek için ise tersine mühendislik kullanılmıştır. Ayrıca, düğüm yerleri ve düğüm sayısı eğri tahmininde serbest bırakılmış olup, CS yöntemi ile bu parametreler arama uzayında rastgele seçilmiştir. Bu şekilde en küçük hata oranına sahip eğri tahmininin elde edilmesi amaçlanmıştır. Deneysel çalışmalarda eğri uydurma için, literatürde sıklıkla kullanılan beş farklı fonksiyon tercih edilmiştir. Deneysel sonuçlarda, her bir fonksiyon için orijinal eğri ve tahmin edilen eğri karşılaştırmalı olarak sunulmuş olup, elde edilen sonuçlar çoğu fonksiyon için CS yöntemi ile tahmin edilen eğrilerin orijinal eğrilere çok benzer sonuçlar ürettiğini göstermiştir.

Keywords

• B-spline Eğri Uydurma,Guguk kuşu Arama algoritması (CS),Serbest düğüm yerleştirme,Optimizasyon

Cuckoo Search Algorithm for Optimal Choice of Free Knots in B-spline Data Fitting

Abstract

Fitting data points to curves commonly known as curve reconstruction a significant problem in computer aided design/manufacturing (CAD/CAM). This problem is frequently encountered in the field of reverse engineering where a free-form parametric curve (typically a B-spline) with a set of (usually a high-dimensional and noisy) data points, obtained by 3D laser scanning, has to be fitted. Although there are a number of methods to come up with this problem, until now there has not been a satisfactory general solution to the problem. In this study, the cuckoo search algorithm (CS), one of the optimization methods inspired by a bird species named cuckoo that leave their eggs in the nest of other host birds, is used to solve the problem of curve fitting. Reverse engineering is used to obtain the curve from the data points. In addition, the knot positions and number of knot are free variables of the problem in the estimation of the curve, and these parameters are randomly selected in the search space by the CS method. In this way, the curve estimate with the smallest error rate is aimed to obtain in this study. Five different functions frequently used in the literature for curve fitting are preferred in the experimental studies. In the experimental results, the original curve and the predicted curve for each function are presented comparatively, and the results obtained show that for most functions, the curves predicted by the CS method produce very similar results to the original curve.

Keywords

• B-spline Curve Fitting,Cuckoo Search algorithm (CS),Free knot placement,Optimization

References

1. Akaike, H. (1973). Information theory and an extension of the maximum likelihood principle. Second international symposium on information theory, Budapest, Akademiai Kiado.
2. Akaike, H. (1974). A new look at the statistical model identification. . IEEE Transactions on Automatic Control 19(16):716–723.
3. Barnhill, R. E. (1992). Geometry processing for design and manufacturing, SIAM.
4. Burchard, H. G. (1974). "Splines (with optimal knots) are better." Applicable Analysis 3(4): 309-319.
5. Cox, M. G. (1972). "The numerical evaluation of B-splines." Journal of Mathematic Application 10: 134-149.
6. De Boor, C. (1972). "On calculating with B-splines." Journal of Aproximate Theory 10: 50-62.
7. De Boor, C. (2001). A Practical Guide to Splines (Applied Mathematical Sciences Vol. 27), Springer-Verlag, New York.
8. De Boor, C. R., J. R. (1968). "Least Squares Cubic Spline Approximation Variable Knots." Computer Science Technical Reports, Purdue University.

9. De Boor, D., J. Rice, C. de Boor and J. Rice (1968). "Least squares cubic spline approximation: 1. Fixed knots. CSD Tr. 20." Computer Science Department" Purdue University, Lafayette, Indiana.
10. Dierckx, P. (1995). Curve and surface fitting with splines, Oxford University Press.
11. Farin, G. E. (2002). Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann.
12. Farin, G. E., J. Hoschek and M.-S. Kim (2002). Handbook of computer aided geometric design, Elsevier.
13. Gálvez, A. and A. Iglesias (2011). "Efficient particle swarm optimization approach for data fitting with free knot B-splines." Computer-Aided Design 43(12): 1683-1692.
14. Gálvez, A. and A. Iglesias (2012). "Particle swarm optimization for non-uniform rational B-spline surface reconstruction from clouds of 3D data points." Information Sciences 192: 174-192.
15. GáLvez, A. and A. Iglesias (2013). "A new iterative mutually coupled hybrid GA–PSO approach for curve fitting in manufacturing." Applied Soft Computing 13(3): 1491-1504.
16. Gálvez, A., A. Iglesias, A. Avila, C. Otero, R. Arias and C. Manchado (2015). "Elitist clonal selection algorithm for optimal choice of free knots in B-spline data fitting." Applied Soft Computing 26: 90-106.
17. Gálvez, A., A. Iglesias and J. Puig-Pey (2012). "Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction." Information Sciences 182(1): 56-76.
18. Hoschek, J., D. Lasser and L. L. Schumaker (1993). Fundamentals of computer aided geometric design, AK Peters, Ltd.
19. Jupp, D. L. B. (1978). "Approximation to Data by Splines with Free Knots." SIAM Journal on Numerical Analysis: 328-343
20. Jupp, D. L. B. (1978). "Approximation to data by splines with free knots." SIAM Journal on Numerical Analysis 15(2): 328-343.
21. Lee, E. T. Y. (1989). "Choosing Nodes in Parametric Curve Interpolation." Computer-Aided Design 21(6): 363-370.
22. Ma, W. and J.-P. Kruth (1995). "Parameterization of randomly measured points for least squares fitting of B-spline curves and surfaces." Computer-Aided Design 27(9): 663-675.
23. Ma, W. and J.-P. Kruth (1998). "NURBS curve and surface fitting for reverse engineering." The International Journal of Advanced Manufacturing Technology 14(12): 918-927.
24. Molinari, N., J.-F. Durand and R. Sabatier (2004). "Bounded optimal knots for regression splines." Computational statistics & data analysis 45(2): 159-178.
25. Patrikalakis, N. M. and T. Maekawa (2009). Shape interrogation for computer aided design and manufacturing, Springer Science & Business Media.
26. Piegl, L. and W. Tiller (2012). The NURBS book, Springer Science & Business Media.
27. Pottmann, H., S. Leopoldseder, M. Hofer, T. Steiner and W. Wang (2005). "Industrial geometry: recent advances and applications in CAD." Computer-Aided Design 37(7): 751-766.
28. Precioso, F., M. Barlaud, T. Blu and M. Unser (2003). Smoothing B-spline active contour for fast and robust image and video segmentation. Image Processing, 2003. ICIP 2003. Proceedings. 2003 International Conference on, IEEE.
29. Rice, J. R. and M. Saloin (1969). The approximation of functions, Addison-Wesley Reading, Mass.
30. Sarfraz, M. and S. A. Raza (2001). Capturing outline of fonts using genetic algorithm and splines. Information Visualisation, 2001. Proceedings. Fifth International Conference on, IEEE.
31. Schwarz, G. (1978). "Estimating the dimension of a model." Annals of Statistics 6(2): 461-464.
32. Schwetlick, H. and T. Schutze (1995). "Least-Squares Approximation by Splines with Free Knots." Bit 35(3): 361-384.
33. Unser, M., A. Aldroubi and M. Eden (1993). "B-spline signal processing. II. Efficiency design and applications." IEEE transactions on signal processing 41(2): 834-848.
34. Ülker, E. and A. Arslan (2009). "Automatic knot adjustment using an artificial immune system for B-spline curve approximation." Information Sciences 179(10): 1483-1494.
35. Valenzuela, O., M. Pasadas, I. Rojas, A. Guillen and H. Pomares (2013). "Automatic Knot Adjustment For B-Spline Smoothing Approximation Using Improved Clustering Algorithm." 2013 Ieee International Conference on Fuzzy Systems (Fuzz - Ieee 2013).
36. Varady, T., R. R. Martin and J. Cox (1997). "Reverse engineering of geometric models—an introduction." Computer-aided design 29(4): 255-268.
37. Yang, X.-S. and S. Deb (2010). "Engineering optimisation by cuckoo search." International Journal of Mathematical Modelling and Numerical Optimisation 1(4): 330-343.
38. Yoshimoto, F., T. Harada and Y. Yoshimoto (2003). "Data fitting with a spline using a real-coded genetic algorithm." Computer-Aided Design 35(8): 751-760.
39. Yoshimoto, F., M. Moriyama and T. Harada (1999). Automatic knot placement by a genetic algorithm for data fitting with a spline. Shape Modeling and Applications, 1999. Proceedings. Shape Modeling International'99. International Conference on, IEEE.
40. Yuan, Y., N. Chen and S. Zhou (2013). "Adaptive B-spline knot selection using multi-resolution basis set." IIE Transactions 45(12): 1263-1277.
41. Yuan, Y., N. Chen and S. Y. Zhou (2013). "Adaptive B-spline knot selection using multi-resolution basis set." Iie Transactions 45(12): 1263-1277.