Gray Wolf Optimizer for Knot Placement in B-Spline Curve Fitting

Abstract

Gerçek bir nesnenin dijital ortama aktarılmasıyla gerçekçi bir temsilinin oluşturulması yüzey modellemenin ana temasıdır. Bu aktarım işlemi öncelikle bu nesnelerin taranması daha sonra elde edilen veri noktalarından nesneyi temsil edecek verileri uydurarak eğri ve yüzey modelleri elde edilmesidir. Veri uydurma problemi geometrik modelleme, bilgisayarlı tasarım(CAD), bilgisayarlı modelleme(CAM) ve bilgisayarlı üretim alanlarındaki araştırma konuları içerisinde önemli bir yer tutmaktadır. Veri noktalarından eğri ve yüzey modellerinin elde etmek için tersine mühendislik kullanılmaktadır. B-Spline eğrileri özellikle yüzey modelleme ve eğri oluşturma için kullanımı çok esnek eğrilerdir. B-Spline eğri tahmini için literatürde birden fazla optimizasyon algoritmaları kullanmıştır.  Bu çalışmada, Gri Kurt Optimizasyon(GWO) Algoritması ile B-Spline eğri tahmini yapılmıştır.  GWO yöntemi ile yapılan eğri tahmininde düğüm yerlerinin tespiti ve düğüm sayısı gelişigüzel seçilerek en küçük hata ile eğri tahmini hedeflenmiştir. Eğri tahmini için literatürde sıklıkla kullanılan 6 farklı fonksiyonu kullanılmıştır. GWO ile birden fazla fonksiyon düşük hata oranı ile başarılı bir şekilde elde edilmiştir.  

Keywords

• B-Spline eğri uydurma,gri kurt optimizasyon(GWO),düğüm yerleştirme,optimizasyon,ters mühendislik

Gray Wolf Optimizer for Knot Placement in B-Spline Curve Fitting

Abstract

The formation of a realistic representation constitutes the main theme of the surface modeling by the transfer of a real object to digital media. This transfer process is performed by first scanning the objects and then obtaining curve and surface models by fitting the data representing the object from the data points obtained later. The data fitting for curve problem has an important area in research topics in geometric modeling, computer-aided design (CAD), computer-aided manufacturing (CAM), and computerized production. Reverse engineering is used to obtain curve and surface models from data points. B-Spline curves are very flexible curves, especially for surface modeling.  Several optimization algorithms have been used in the literature for B-Spline curve fitting. In this study, B-Spline curve fitting is carried out by Gray Wolf Optimizer (GWO). The estimation of the knot locations and the number of knots are randomly selected in the curve estimation by the GWO method and the curve estimation with the smallest error is aimed. For the curve fitting, six different functions are used which are frequently used in the literature.  The experimental studies show that the proposed algorithm obtains the results with low error rates for more than one functions.

Keywords

• B-Spline Curve Fitting,Gray Wolf Optimizer (GWO),Knot placement,Optimization,Reverse Engineering

References

1. T. Varady and RR.Martin. (2002). Reverse engineering.
2. H. Pottmann, S. Leopoldseder, A. Hofer, T. Steiner, and W. Wang, "Industrial geometry: recent advances and applications in CAD," Computer-Aided Design, vol. 37, pp. 751-766, Jun 2005.
3. A. D. L. Hoschek. J, Fundamentals of computer aided geometric design, 1993.
4. R. Barnhill, "Geometric processing for design and manufacturing," presented at the SIAM., Philadelphia:, 1992.
5. N. Patrikalakis, Maekawa T. Shape, "Shape interrogation for computer aided design and manufacturing," Heidelberg: Springer Verlag, 2002.
6. C. De Boor, "A Practical Guide to Splines," Springer Verlag, 2001.
7. W. Y. Ma and J. P. Kruth, "Parameterization of Randomly Measured Points for Least-Squares Fitting of B-Spline Curves and Surfaces," Computer-Aided Design, vol. 27, pp. 663-675, Sep 1995.
8. W. Ma and J. P. Kruth, "NURBS curve and surface fitting for reverse engineering," International Journal of Advanced Manufacturing Technology, vol. 14, pp. 918-927, 1998.

9. G. Echevarria, A. Iglesias, and A. Galvez, "Extending neural networks for B-spline surface reconstruction," Computational Science-Iccs 2002, Pt Ii, Proceedings, vol. 2330, pp. 305-314, 2002.
10. A. Galvez, A. Iglesias, and J. Puig-Pey, "Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction," Information Sciences, vol. 182, pp. 56-76, Jan 1 2012.
11. A. Galvez and A. Iglesias, "Particle swarm optimization for non-uniform rational B-spline surface reconstruction from clouds of 3D data points," Information Sciences, vol. 192, pp. 174-192, Jun 1 2012.
12. T. Varady, R. R. Martin, and J. Cox, "Reverse engineering of geometric models - An introduction," Computer-Aided Design, vol. 29, pp. 255-268, Apr 1997.
13. L. A. a. W. T. Piegl, The Nurbs Book. Heidelberg, Germany Springer Verlag, 1997.
14. R. Goldenthal and M. Bercovier, "Spline curve approximation and design by optimal control over the knots," Computing, vol. 72, pp. 53-64, Apr 2004.
15. G. Farin, "Curves and Surfaces for CAGD," presented at the 5th ed, SanFrancisco., 2002.
16. E. Ulker and A. Arslan, "Automatic knot adjustment using an artificial immune system for B-spline curve approximation," Information Sciences, vol. 179, pp. 1483-1494, Apr 29 2009.
17. E. Ulker, "B-Spline curve approximation using Pareto envelope based selection algorithm-PESA," presented at the Int. J. Comput. Commun. Eng. , 2013.
18. F. Yoshimoto, M. Moriyama, and T. Harada, "Automatic knot placement by a genetic algorithm for data fitting with a spline," Shape Modeling International '99 - International Conference on Shape Modeling and Applications, Proceedings, pp. 162-169, 1999.
19. G. S. Kumar, P. K. Kalra, and S. G. Dhande, "Parameter optimization for B-spline curve fitting using genetic algorithms," Cec: 2003 Congress on Evolutionary Computation, Vols 1-4, Proceedings, pp. 1871-1878, 2003.
20. A. Galvez, A. Iglesias, A. Avila, C. Otero, R. Arias, and C. Manchado, "Elitist clonal selection algorithm for optimal choice of free knots in B-spline data fitting," Applied Soft Computing, vol. 26, pp. 90-106, Jan 2015.
21. Ö. İnik, "Using The Gravitational Search Algorithm For The B-Spline Curves Fitting.," presented at the International Conference on Computer Science and Engineering (UBMK 2016) 2016.
22. C. De Boor, "A practical guide to splines," springer, 1978.
23. E. Sarıöz, "Course Notes of Computer Aided Ship Design and Production," ed. Istanbul Technical University 2005.
24. S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey Wolf Optimizer," Advances in Engineering Software, vol. 69, pp. 46-61, Mar 2014.
25. N. Jayakumar, S. Subramanian, S. Ganesan, and E. B. Elanchezhian, "Grey wolf optimization for combined heat and power dispatch with cogeneration systems," International Journal of Electrical Power & Energy Systems, vol. 74, pp. 252-264, Jan 2016.
26. E. T. Y. Lee, "Choosing Nodes in Parametric Curve Interpolation," Computer-Aided Design, vol. 21, pp. 363-370, Jul-Aug 1989.
27. H. Akaike, "Information theory and an extension of the maximum likelihood principle," in Second international symposium on information theory, Budapest, 1973, pp. 267-281.
28. H. Akaike, "A new look at the statistical model identification. ," presented at the IEEE Transactions on Automatic Control 1974.
29. G. Schwarz, "Estimating the dimension of a model," Annals of Statistics, vol. 6, pp. 461-464, 1978.
30. C. R. De Boor, J. R. , "Least Squares Cubic Spline Approximation Variable Knots," Computer Science Technical Reports, Purdue University, 1968.
31. D. L. B. Jupp, "Approximation to Data by Splines with Free Knots," SIAM Journal on Numerical Analysis, pp. 328-343 1978.
32. Y. Yuan, N. Chen, and S. Y. Zhou, "Adaptive B-spline knot selection using multi-resolution basis set," Iie Transactions, vol. 45, pp. 1263-1277, Dec 1 2013.
33. H. Schwetlick and T. Schutze, "Least-Squares Approximation by Splines with Free Knots," Bit, vol. 35, pp. 361-384, Sep 1995.
34. O. Valenzuela, M. Pasadas, I. Rojas, A. Guillen, and H. Pomares, "Automatic Knot Adjustment For B-Spline Smoothing Approximation Using Improved Clustering Algorithm," 2013 Ieee International Conference on Fuzzy Systems (Fuzz - Ieee 2013), 2013.
35. F. Yoshimoto, T. Harada, and Y. Yoshimoto, "Data fitting with a spline using a real-coded genetic algorithm," Computer-Aided Design, vol. 35, pp. 751-760, Jul 2003.
36. A. Galvez and A. Iglesias, "Efficient particle swarm optimization approach for data fitting with free knot B-splines," Computer-Aided Design, vol. 43, pp. 1683-1692, Dec 2011.