Metaheuristics Methods (GA and ACO) for Minimizing the Length of Freeman Chain Code from Handwritten Isolated Characters

Authors: Dewi Nasien, Habibollah Haron, Siti SophiayatiYuhaniz

Abstract:

This paper presents a comparison of metaheuristic algorithms, Genetic Algorithm (GA) and Ant Colony Optimization (ACO), in producing freeman chain code (FCC). The main problem in representing characters using FCC is the length of the FCC depends on the starting points. Isolated characters, especially the upper-case characters, usually have branches that make the traversing process difficult. The study in FCC construction using one continuous route has not been widely explored. This is our motivation to use the population-based metaheuristics. The experimental result shows that the route length using GA is better than ACO, however, ACO is better in computation time than GA.

Keywords: Handwriting Recognition, Feature Extraction, Freeman Chain Code, Genetic Algorithm and Ant ColonyOptimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081441

References:

[1] Shi-Fei Ding; Wei-KuanJia; Chun-Yang Su; Zhong-Zhi Shi; Research of pattern feature extraction and selection. Machine Learning and Cybernetics, 2008 International Conference on Volume 1, 12-15 July 2008 Page(s):466 - 471.
[2] ZhaoqiBian, Xuegong Zhang. Pattern Recognition. 2nd Edition, Tsinghua University Press, Beijing, 2000.
[3] Jixiang Sun, Modern pattern recognition, Defense University of Science and Technology Publishing House, Changsha, 2002.
[4] Kunaver, M.; Tasic, J.F.; Image feature extraction - an overview. Computer as a Tool, 2005. EUROCON 2005.The International Conference on Volume 1, 21-24 Nov. 2005 Page(s):183 - 186.
[5] Jähne, Bernd; Digital Image Processing: Concepts, Algorithms, and Scientific Applications. Edition: 6, Published by Springer, 2005.
[6] Liu, Y.K., Zalik, B.: An efficient chain code with Huffman coding, Pattern Recognition, 38(4), 2005, 553-557.
[7] Sánchez-Cruz, Hermilo., Bribiesca, Ernesto., Rodríguez-Dagnino, R.M. Efficiency of Chain Codes to Represent Binary Objects. Volume 40, Issue 6, June 2007, Pages 1660-1674.
[8] Wulandhari. L.A., HaronHabibolah. The Evolution and Trend of Chain Code Scheme. ICGST-GVIP, ISSN 1687-398X, Volume (8), Issue (III), October 2008.
[9] Freeman. H, Techniques for the Digital Computer Analysis of Chain- Encoded Arbitrary Plane Curves, Proc. Natn. Electron. Conf. 18 (1961) 312-324.
[10] Freeman H, Computer Processing of Line-Drawing Images, ACM Computing Surveys 6, 1974, 57-97.
[11] Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, New York.
[12] Dorigo, M., Di Caro, G.: The ant colony optimization meta-heuristic. In Corne, D., Dorigo, M., Glover, F., eds.: New Ideas in Optimization. McGraw-Hill, London (1999) 11-32.
[13] M. Dorigo and G. Di Caro, "The Ant Colony Optimization metaheuristic," in New Ideas in Optimization, D. Corne et al., Eds., McGraw Hill, London, UK, pp. 11-32, 1999.
[14] M. Dorigo, G. Di Caro, and L.M. Gambardella, "Ant algorithms for discrete optimization," Artificial Life, vol. 5, no. 2, pp. 137-172, 1999.
[15] Dorigo, M., Birattari, M., Stutzle, T., Ant Colony Optimization. IEEE Computational Intelligence Magazine. November 2006.
[16] Dorigo M (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B 26:1-13.
[17] J.-L. Deneubourg, S. Aron, S. Goss, J.-M. Pasteels, The self-organizing exploratory pattern of the argentine ant, J. Insect Behav. 3 (1990) 159- 168.
[18] Socha K, Dorigo M (2008) Ant colony optimization for continuous domain. Eur J Oper Res 185:1155-1173.
[19] Engkamat, A.A. Enhancement of Parallel Thinning Algorithm for Handwritten Characters Using Neural Network. MSc Thesis. Universiti Teknologi Malaysia, 2005.