Capturing outlines of generic shapes with cubic B´ezier curves using the Nelder–Mead simplex method

Iranian Journal of Numerical Analysis and Optimization

مقاله 6، دوره 9، شماره 2 - شماره پیاپی 16، دی 2019، صفحه 103-121   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v9i2.70045

نویسندگان

A. Ebrahimi¹؛ G. B. Loghmani^{* 1}؛ M. Sarfraz²

¹Yazd University

²Kuwait University

چکیده

We design a fast technique for fitting cubic B´ezier curves to the boundary of 2D shapes. The technique is implemented by means of the Nelder–Mead simplex procedure to optimize the control points. The natural attributes of the B´ezier curve are utilized to discover the initial vertex points of the Nelder–Mead procedure. The proposed technique is faster than traditional methods and helps to obtain a better fit with a desirable precision. The comparative analysis of our results describes that the introduced approach has a high compression ratio and a low fitting error.

کلیدواژه‌ها

Interpolation؛ Splines؛ Curve fitting؛ Nelder-Mead Simplex Method؛ Computer aided design؛ Computer graphics

مراجع

1. B´ezier, P. Numerical control; mathematics and applications, John Wiley & Sons, 1972.

2. Biswas, S. and Lovell, B.C. B´ezier and splines in image processing and machine vision, Springer Science & Business Media, 2007.

3. Cabrelli, C.A. and Molter, U.M. Automatic representation of binary images, IEEE Trans. Pattern. Anal. Mach. Intell., 12 (1990), 1190–1196.

4. Chetverikov, D. and Szabo, Z. A simple and efficient algorithm for detection of high curvature points in planar curves, proc. of 23rd workshop of Australian Pattern Recognition Group, Steyr, (1999), 175–184.

5. Conn, A.R., Scheinberg, K. and Vicente, L.N. Introduction to derivative free optimization, MOS-SIAM Series on Optimization, 2009.

6. Farin, G. Curves and surfaces for computer-aided geometric design: a practical guide, Academic Press, 1997.

7. Freeman, H. On the encoding of arbitrary geometric configurations, IEEE Trans. Comput., 2 (1961), 260–268.

8. Hassanien, A.E., Grosan, C. and Tolba, M.F. Applications of intelligent optimization in biology and medicine: Current trends and open prob lems, Springer, 2015.

9. Hussain, M., Hussain, M.Z., and Sarfraz, M. Shape-preserving polynomial interpolation scheme, Iran. J. Sci. Technol. Trans. A Sci., 40 (2016), no. 1, 9–18.

10. Hussain, M.Z., Hussain, F. and Sarfraz, M. Shape-preserving positive trigonometric spline curves, Iran. J. Sci. Technol. Trans. A Sci. 42 (2018), no. 2, 1–13.

11. Itoh, K. and Ohno, Y.A curve fitting algorithm for character fonts, Electronic publishing , 6 (1993), no. 3, 195–205.

12. Khan, M.S., Ayob, A. F.M., Isaacs, A. and Ray, T. A novel evolution ary approach for 2d shape matching based on B-spline modeling, Proc. Congr. Evol. Comput., (2011), 655–661.

13. Klein, K. and Neira, J. Nelder–Mead simplex optimization routine for large-scale problems: A distributed memory implementation, Comput. Econ., 4 (2014), 447–461.

14. Lagarias, J.C., Reeds, J.A., Wright, M.H. and Wright, P.E. Convergence properties of the nelder–mead simplex method in low dimensions, SIAM. J. Optim. , 9 (1998), no. 1, 112–147.

15. Marji, M. and Siy, P. A new algorithm for dominant points detection and polygonization of digital curves, Pattern. Recognit., 10 (2003), 2239–2251.

16. Masood, A. and Haq, S.A. Object coding for real time image processing applications, Pattern Recognition and Image Analysis. ICAPR 2005. Lecture Notes in Computer Science, vol 3687. Springer, Berlin, Heidelberg.

17. Masood, A. and Sarfraz, M. An efficient technique for capturing 2d objects, Comput. Graph., 32 (2008), no 1, 93–104.

18. Masood, A. and Sarfraz, M. Capturing outlines of 2d objects with b´ezier cubic approximation, Image Vis. Comput., 6 (2009), 704–712.

19. Nelder, J. A., and Mead, R. A simplex method for function minimization, Comput. J., 7 (1965), no. 4, 308–313.

20. Piegl, L. and Tiller, W. The NURBS book. Springer Science & Business Media, 2012.

21. Plass, M. and Stone, M. Curve-fitting with piecewise parametric cubics, Comput. Graph., 17 (1983), no 3, 229–239.

22. Powell, S. Applications and enhancements of aircraft design optimization techniques, PhD thesis, University of Southampton, 2012.

23. Salomon, D. Curves and surfaces for computer graphics, Springer Science & Business Media, 2007.

24. Sarfraz, M. Some algorithms for curve design and automatic outlinecapturing of images, Int. J. Image. Graph., 2 (2004), 301–324.

25. Sarfraz, M. Computer-aided intelligent recognition techniques and applications, Wiley Online Library, 2005.

26. Sarfraz, M. Vectorizing outlines of generic shapes by cubic spline using simulated annealing, Int. J. Comput. Math., 8 (2010), 1736–1751.

27. Sarfraz, M. Capturing image outlines using simulated annealing approach with conic splines, The Proceedings of the International Con ference on Information and Intelligent Computing, (2011), 152–157.

28. Sarfraz, M. and Khan, M. Automatic outline capture of arabic fonts, Inf. Sci., 3 (2002), 269–281.

29. Sarfraz, M. and Khan, M. An automatic algorithm for approximating boundary of bitmap characters, Future. Gener. Comput. Syst., 8 (2004), 1327–1336.

30. Sarfraz, M. and Masood, A. Capturing outlines of planar images using b´ezier cubics, Comput. Graph., 5 (2007), 719–729.

31. Sarfraz, M., Masood, A. and Asim, M.R. A new approach to corner detection, Computer Vision and Graphics 32 (2006), 528533

32. Sarfraz, M. and Raza, A. Visualization of data with spline fitting: a tool with a genetic approach, CISST, 97(2002), 99–105.

33. Sarfraz, M. and Raza, S.A. Capturing outline of fonts using genetic algorithm and splines, Proceedings of IEEE International Conference on Information Visualization-IV’2001-UK, USA:IEEE Computer Society Press, (2001), 738–743.

34. Sarfraz, M. and Razzak, M. An algorithm for automatic capturing of the font outlines, Comput. Graph., 5 (2002), 795–804.

35. Sarfraz, M., Riyazuddin, M. and Baig, M. Capturing planar shapes by approximating their outlines, J. Comput. Appl. Math., 1 (2006), 494–512.

36. Sohel, F.A., Karmakar, G.C., Dooley, L.S. and Arkinstall, J. Enhanced bezier curve models incorporating local information, Proc. IEEE. Int. Conf. Acoust. Speech. Signal. Process., 4 (2005), 253–256.

37. Tang, Y. Y., Yang, F., and Liu, J. Basic processes of chinese character based on cubic b-spline wavelet transform, IEEE. Trans. Pattern. Anal. Mach. Intell., 12 (2001), 1443–1448.

38. Zheng, W., Bo, P., Liu, Y., and Wang, W. Fast B-spline curve fitting by L-BFGS, Comput. Aided. Geom. Des., 7 (2012), 448–462.

39. Zhu, F. Geometric Parameterisation and Aerodynamic Shape Optimisation, PhD thesis, University of Sheffield, 2014.