Genetic Algorithm Works for Vectoring Image Outlines of Generic Shapes

Misbah Irshad, Muhammad Sarfraz, Malik Zawwar Hussain

Department of Information Science, Kuwait University, Kuwait City, Kuwait.
Department of Mathematics, University of the Punjab, Lahore, Pakistan.

DOI: 10.4236/jsea.2013.67041                

Abstract

This work proposes a scheme which 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 a cubic spline function. GA works well for finding the optimal values of shape parameters in the description of the proposed cubic spline. The underlying scheme comprises of various phases including data of the image outlines, detection of corner points, using GA for optimal values of shape parameters, and fitting curve using cubic spline to the detected corner points.

Keywords

Spline; Approximation; Curve Fitting; Genetic Algorithm; Generic Shapes

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Sarfraz and M. A. Khan, “An Automatic Algorithm for Approximating Boundary of Bitmap Characters,” Future Generation Computer Systems, Vol. 20, No. 8, 2004, pp. 1327-1336. doi10.1016/j.future.2004.05.024
[2]	X. Yang, “Curve Fitting and Fairing Using Conic Splines,” Computer Aided Design, Vol. 36, No. 5, 2004, pp. 461-472. doi10.1016/S0010-4485(03)00119-2
[3]	G. Lavoue, F. Dupont and A. Baskurt, “A New Subdivision Based Approach for Piecewise Smooth Approximation of 3D Polygonal Curves,” Pattern Recognition, Vol. 38, No. 8, 2005, pp. 1139-1151. doi10.1016/j.patcog.2005.02.002
[4]	B. S. Morse, T. S. Yoo, D. T. Chen, P. Rheingans and K. R. Subramanian, “Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions,” Proceedings of Conference on Shape Modeling and Applications, Genova, 7-11 May 2001, pp. 89-98. doi10.1109/SMA.2001.923379
[5]	X. N. Yang and G. Z. Wang, “Planar Point Set Fairing and Fitting by Arc Splines,” Computer Aided Design, Vol. 33, No. 1, 2001, pp. 35-43. doi10.1016/S0010-4485(00)00059-2
[6]	D. E. Goldberg, “Geneticalgorithms in Search, Optimization and Machine Learning,” Addison-Wesley, Reading, 1989.
[7]	G. Avrahami and V. Pratt, “Sub-Pixel Edge Detection in Character Digitization,” Proceedings of International Conference on Raster Imaging and Digital Typography II, Boston, December 1991, pp. 54-64.
[8]	Z. J. Hou and G. W. Wei, “A New Approach to Edge Detection,” Pattern Recognition, Vol. 35, No. 7, 2002, pp. 1559-1570. doi10.1016/S0031-3203(01)00147-9
[9]	H. L. Beus and S. S. H. Tiu, “An Improved Corner Detection Algorithm Based on Chain Coded Plane Curves,” Pattern Recognition, Vol. 20, No. 3, 1987, pp. 291-296. doi10.1016/0031-3203(87)90004-5
[10]	D. Chetrikov and S. Zsabo, “A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves,” Proceedings of the 23rd Workshop of Austrian Pattern Recognition Group, Steyr, 27-28 May 1999, pp. 175-184.
[11]	H. Freeman and L. S. Davis, “A Corner Finding Algorithm for Chain-Coded Curves,” IEEE Transaction on Computer, Vol. 26, No. 3, 1977, pp. 297-303. doi10.1109/TC.1977.1674825
[12]	B. Jüttler and A. Felis, “Least Square Fitting of Algebraic Spline Surfaces,” Advances in Computational Mathematics, Vol. 17, No. 1-2, 2002, pp. 135-152. doi10.1023/A:1015200504295
[13]	M. Sarfraz, M. Z. Hussain and F. S. Chaudary, “Shape Preserving Cubic Spline for Data Visualization,” Computer Graphics and CAD/CAM, Vol. 1, No. 6, 2005, pp. 185-193.
[14]	T. Harada, F. Yoshimoto and Y. Aoyama, “Data Fitting Using a Genetic Algorithm with Real Number Genes,” Proceedings of the IASTED International Conference on Computer Graphics and Imaging, Las Vegas, 1-7 November 2000, pp. 131-138.
[15]	J. H. Horng, “An Adaptive Smoothing Approach for Fitting Digital Planar Curves with Line Segments and Circular Arcs,” Pattern Recognition Letters, Vol. 24, No. 1-3, 2003, pp. 565-577. doi10.1016/S0167-8655(02)00277-5
[16]	M. Jyoti, D. Ratna and G. Sainarayanan, “Harris Operator Corner Detection Using Sliding Window Method,” International Journal of Computer Applications, Vol. 22, No. 1, 2011, pp. 28-37.
[17]	H. Kano, H. Nakata and C. F. Martin, “Optimal Curve Fitting and Smoothing Using Normalized Uniform BSplines: A Tool for Studying Complex Systems,” Applied Mathematics and Computation, Vol. 169, No. 1, 2005, pp. 96-128. doi10.1016/j.amc.2004.10.034
[18]	S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol. 220, No. 4598, 1983, pp. 671-680.
[19]	M. Moriyama, F. Yoshimoto and T. Harada, “A Method of Plane Data Fitting with a Genetic Algorithm,” Proceeding of the IASTED International Conference on Computer Graphics and Imaging, Ames, 11-12 May 1998, pp. 21-31.
[20]	M. Sarfraz and A. Raza, “Visualization of Data Using Genetic Algorithm,” Soft Computing and Industry, Recent Applications, 2002, pp. 535-544.
[21]	M. Sarfraz, “Some Algorithms for Curve Design and Automatic Outline Capturing of Images,” International Journal of Image and Graphics, Vol. 4, No. 2, 2004, pp. 301-324. doi10.1142/S0219467804001427
[22]	M. Sarfraz, “Computer-Aided Reverse Engineering Using Simulated Evolution on NURBS,” International Journal of Virtual and Physical Prototyping, Vol. 1, No. 4, 2006, pp. 243-257. doi10.1080/17452750601130492
[23]	M. Sarfraz and A. Rasheed, “A Randomized Knot Insertion Algorithm for Outline Capture of Planar Images Using Cubic Spline,” The Proceedings of the 22nd ACM Symposium on Applied Computing, Seoul, 11-15 March 2007, pp. 71-75.
[24]	M. Sarfraz, “Vectorizingoutlines of Genericshapes by Cubic Spline Using Simulated an Nealing,” International Journal of Computer Mathematics, Vol. 87, No. 8, 2010, pp. 1736-1751. doi10.1080/00207160802452519
[25]	W.-C. Hu, “Multiprimitive Segmentation Based on Meaningful Break Points for Fitting Digital Planar Curves with Line Segments and Conic Arcs,” Image and Vision Computing, Vol. 23, No. 9, 2005, pp. 783-789. doi10.1016/j.imavis.2005.05.004
[26]	H. Yang, W. Wang and J. Sun, “Control Point Adjustment for B-Spline Curve Approximation,” Computer Aided Design, Vol. 36, No. 7, 2004, pp. 639-652. doi10.1016/S0010-4485(03)00140-4
[27]	Z. Yang, J. Deng and F. Chen, “Fitting Unorganized Point Clouds with Active Implicit B-Spline Curves,” Visual Computing, Vol. 21, No. 1, 2005, pp. 831-839. doi10.1007/s00371-005-0340-0