Edge Tracing Based on Improved Genetic Algorithm

Abstract:

In this paper, we proposed a new edge tracing method with high robustness to noise. Through representing edge with maximal gradient path encoded by chain code, the edge tracing problems can be converted into combinatorial optimization problems, and so they can be solved by genetic algorithm. We optimized the traditional genetic algorithm in order to improve the convergence rate. Our method is effective to edges with any shape because it does not require any prior knowledge about the edges. In this paper we also discussed the problem of edge winding and folding and expatiated how to avoid it by designing proper gene coding method and punishment function. Furthermore, by transforming the region of interests from Cartesian coordinates to polar coordinates before edge tracing, this method can be used for closed edges. The experimental results show this is an effective edge tracing method with high robustness and flexibility.

• Periodical: Advanced Materials Research (Volumes 488-489)
• Pages: 904-912
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.488-489.904
• Online since: March 2012
• Authors: Bin Bing Liu, Hai Qing Chen, Chong Huang, Zhen Gang Yang
• Keywords: Coordinates Transformation, Differential Chain Code, Edge Tracing, Genetic Algorithm (GA), Maximal Gradient Path

References

[1] 1.M. Cheriet, J. N. Said, and C. Y. Suen: A Recursive Thresholding Technique For Image Segmentation. IEEE Transactions on Image Processing, Vol.7, No.6, June 1998.

DOI: 10.1109/83.679444

[2] 2.Kamal Hammouche, Moussa Diaf, Patrick Siarry: A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation. Computer Vision and Image Understanding, 109 (2008) 163–175.

DOI: 10.1016/j.cviu.2007.09.001

[3] 3.Wen-Bing Tao, Jin-Wen Tian, Jian Liu: Image segmentation by three-level thresholding based on maximum fuzzy entropy and genetic algorithm. Pattern Recognition Letters, 24 (2003) 3069–3078.

DOI: 10.1016/s0167-8655(03)00166-1

[4] 4.Dae N. Chun, Hyun S. Yangt: Robust image segmentation using genetic Algorithm with a fuzzy measure. Pattern Recognition, Vol.29, No.7, pp.l195-1211, 1996.

DOI: 10.1016/0031-3203(95)00148-4

[5] 5.Chih-Chin Lai, Chuan-Yu Chang: A hierarchical evolutionary algorithm for automatic medical image segmentation. Expert Systems with Applications, 36 (2009) 248–259.

DOI: 10.1016/j.eswa.2007.09.003

[6] 6.Mohamad Forouzanfar, Nosratallah Forghani, Mohammad Teshnehlab: Parameter optimization of improved fuzzy c-means clustering algorithm for brain MR image segmentation. Engineering Applications of Artificial Intelligence.

DOI: 10.1016/j.engappai.2009.10.002

[7] 7. Mohamed N. Ahmed, Sameh M. Yamany: A Modified Fuzzy C-Means Algorithm for Bias Field Estimation and Segmentation of MRI Data. IEEE Transactions on Medical Imaging, Vol.21, No.3, March 2002.

DOI: 10.1109/42.996338

[8] 8.Tianzi Jiang, Faguo Yang, Yong Fan, David J. Evans: A Parallel Genetic Algorithm for Cell Image Segmentation. Electronic Notes in Theoretical Computer Science, 46 (2001).

DOI: 10.1016/s1571-0661(04)80988-5

[9] 9.Victor Ayala-Ramirez, Carlos H. Garcia-Capulin, Arturo Perez-Garcia, Raul E. Sanchez-Yanez: Circle detection on images using genetic algorithms. Pattern Recognition Letters, 27 (2006) 652–657.

DOI: 10.1016/j.patrec.2005.10.003

[10] 10. S.Y. Wang, K. Tai: Graph representation for structural topology optimization using genetic algorithms. Computers and Structures, 82 (2004) 1609–1622.

DOI: 10.1016/j.compstruc.2004.05.005

[11] 11. Ernesto Bribiesca: A new chain code. Pattern Recognition, 32 (1999) 235-251.

DOI: 10.1016/s0031-3203(98)00132-0

[12] 12. G. Wagenknecht: A contour tracing and coding algorithm for generating 2D contour codes from 3D classified objects. Pattern Recognition, 40 (2007) 1294 – 1306.

DOI: 10.1016/j.patcog.2006.09.003

[13] 13. Paulo Nunes, Ferran MarqueHs, Fernando Pereira, Antoni Gasull: A contour-based approach to binary shape coding using a multiple grid chain code. Signal Processing: Image Communication, 15 (2000) 585-599.

DOI: 10.1016/s0923-5965(99)00041-7

[14] 14. Hermilo Sánchez-Cruz, Ernesto Bribiesca, Ramón M. Rodríguez-Dagnino: Efficiency of chain codes to represent binary objects. Pattern Recognition, 40 (2007) 1660 – 1674.

DOI: 10.1016/j.patcog.2006.10.013

[15] 15. Fabián Arrebola, Francisco Sandoval: Corner detection and curve segmentation by multiresolution chain-code linking. Pattern Recognition, 38 (2005) 1596 – 1614.

DOI: 10.1016/j.patcog.2005.03.006

[16] 16. Frank Y. Shih, Wai-Tak Wong: A one-pass algorithm for local symmetry of contours from chain codes. Pattern Recognition, 32 (1999) 1203-1210.

DOI: 10.1016/s0031-3203(98)00158-7

[17] 17. A. Bandera, C. Urdiales, F. Arrebola, F. Sandoval: 2D object recognition based on curvature functions obtained from local histograms of the contour chain code. Pattern Recognition Letters, 20 (1999) 49-55.

DOI: 10.1016/s0167-8655(98)00123-8

[18] 18. VictoriaJ.Hodge, Simon O'Keefe, JimAustin: A binary neural shape matcher using Johnson Counters and chain codes. Neurocomputing, 72(2009), 693–703.

DOI: 10.1016/j.neucom.2008.07.013