This chapter proposes a scheme that helps digitizing hand printed and electronic planar objects or vectorizing the generic shapes. An evolutionary optimization technique, namely Genetic Algorithm (GA), is used to solve the problem of curve fitting with cubic and rational cubic spline functions. The underlying scheme is comprised of various phases including data of the image outlines, detection of corner points, using GA for optimal values of shape parameters in the description of spline functions, and fitting curve using spline functions to the detected corner points.
TopIntroduction
Fitting curves to the data extracted from generic planar shapes is the problem which is immensely worked on during last two decades. It still grabs the attention of researchers due to its applications in diverse fields and its demands in the industry. The process of vectorizing outlines of the images consists of several mathematical and computational phases and stages. This process aims to fit an optimal curve to the data extracted from the boundary of the image (Hou, Z. J. and Wei, G.W. (2002), Kirkpatrick, S., Gelatt, C. D. Jr., Vecchi, M. P. (1983), Sarfraz, M. (2004), Sarfraz, M. and Khan, M. A. (2004), Sarfraz, M., Hussain, M. Z. & Chaudary, F. S. (2005)). Although many contributions in the literature (Harada, T., Yoshimoto, F., and Aoyama, Y. (2000),Horng, J. H. (2003), Lavoue, G., Dupont, F. and Baskurt, A. (2005), Moriyama, M., Yoshimoto, F. and Harada, T. (1998), Sarfraz, M. (2006), Sarfraz, M. and Rasheed, A. (2007), Sarfraz, M. (2010), Yang, H., Wang, W. and Sun, J. (2004),Yang, X.N. and Wang, G.Z. (2001), Yang, Z. Deng, J. and Chen, F. (2005)) can be found in this area, there is still room for making more advancements and finding interactive approaches.
Least square fitting is common in optimization problems in which splines and higher order polynomials are used to approximate the data. One can see a cubic spline technique Sarfraz, M. and Khan, M. A. (2004) with least square fitting. Squared distance minimization has been used on B-spline curves in Yang, X. (2004). It uses iterative process to achieve an optimal curve.
Instead of parametric form, implicit form of the polynomial is also used for this purpose. Implicit B-spline curves Lavoue, G., Dupont, F. and Baskurt, A. (2005) are used to solve curve reconstruction problem by approximating the point clouds. It uses the heuristic of trust region algorithm. In (Jüttler, B. and Felis, A. (2002), Morse, B. S., Yoo, T. S., Chen, D. T., Rheingans, P., and Subramanian, K. R. (2001), Yang, X.N. and Wang, G.Z. (2001)), schemes were proposed for fitting implicitly defined algebraic spline curves and surfaces. This was achieved over the scattered data by simultaneously approximating points and associated normal vectors.
In this paper, a soft computing technique namely Genetic Algorithm (GA) Goldberg, D. E. (1989) is proposed to find the optimal spline curves to the data extracted from the boundaries of the generic images. This evolutionary technique incorporates the corner points from the outline of the input image. The detection of corner points is quite significant as it helps minimizing the time to achieve desired curve to the outline of the image. Curve fitting in this scheme is done by using cubic and rational cubic spline functions which contain shape parameters in their description. Basic target is to find those values of the parameters which assure minimum error between detected boundary of the image and the fitted spline curve.
The paper is organized in a way that the first and second steps (outline estimation and corner detection) of the proposed scheme are described, a generalized cubic spline curve scheme is given, Genetic Algorithm is explained, the proposed scheme is discussed and demonstrated with examples. Finally, the paper is concluded.