On the Detection of Visual Features from Digital Curves Using a Metaheuristic Approach

Cecilia Di Ruberto

Department of Mathematics and Computer Science, University of Cagliari, Cagliari, Italy.

DOI: 10.4236/am.2012.331241                

Abstract

In computational shape analysis a crucial step consists in extracting meaningful features from digital curves. Dominant points are those points with curvature extreme on the curve that can suitably describe the curve both for visual perception and for recognition. Many approaches have been developed for detecting dominant points. In this paper we present a novel method that combines the dominant point detection and the ant colony optimization search. The method is inspired by the ant colony search (ACS) suggested by Yin in [1] but it results in a much more efficient and effective approximation algorithm. The excellent results have been compared both to works using an optimal search approach and to works based on exact approximation strategy.

Keywords

Digital Curve; Dominant Point; Polygonal Approximation; Ant Colony Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. Y. Yin, “Ant Colony Search Algorithms for Optimal Polygonal Approximation of Plane Curves,” Pattern Recognition, Vol. 36, No. 8, 2003, pp. 1783-1797. doi:10.1016/S0031-3203(02)00321-7
[2]	E. Attneave, “Some Informational Aspects of Visual Percaption,” Psychological Review, Vol. 61, No. 3, 1954, pp. 183-193. doi:10.1037/h0054663
[3]	C. H. The and R. T. Chin, “On the Detection of Dominant Points on Digital Curves,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 8, 1989, pp. 859-871. doi:10.1109/34.31447
[4]	W. Y. Wu and M. J. Wang, “Detecting the Dominant Points by the Curvature-Based Polygonal Approximation,” CVGIP: Graphical Model Image Processing, Vol. 55, No. 2, 1993, pp. 79-88. doi:10.1006/cgip.1993.1006
[5]	M. J. Wang, W. Y. Wu, L. K. Huang and D. M. Wang, “Corner Detection Using Bending Value,” Pattern Recognition Letters, Vol. 16, No. 8, 1995, pp. 575-583. doi:10.1016/0167-8655(95)80003-C
[6]	A. Held, K. Abe and C. Arcelli, “Towards a Hierarchical Contour Description via Dominant Point Detection,” IEEE Transactions on System Man Cybernetics, Vol. 24, No. 6, 1994, pp. 942-949. doi:10.1109/21.293514
[7]	A. Carmona-Poyato, N. L. Fernández-Garca, R. MedinaCarnicer and F. J. Madrid-Cuevas, “Dominant Point Detection: A New Proposal,” Image and Vision Computing, Vol. 23, No. 13, 2005, pp. 1226-1236. doi:10.1016/j.imavis.2005.07.025
[8]	J. Sklansky and V. Gonzalez, “Fast Polygonal Approximation of Digitized Curves,” Pattern Recognition, Vol. 12, No. 5, 1980, pp. 327-331. doi:10.1016/0031-3203(80)90031-X
[9]	B. K. Ray and K. S. Ray, “Determination of Optimal Polygon from Digital Curve Using L1 Norm,” Pattern Recognition, Vol. 26, No. 4, 1993, pp. 505-509. doi:10.1016/0031-3203(93)90106-7
[10]	U. Ramer, “An Iterative Procedure for the Polygonal Approximation of Plane Curves,” Computer Graphics Image Processing, Vol. 1, No. 3, 1972, pp. 244-256. doi:10.1016/S0146-664X(72)80017-0
[11]	N. Ansari and E. J. Delp, “On Detecting Dominant Points,” Pattern Recognition, Vol. 24, No. 5, 1991, pp. 441-450. doi:10.1016/0031-3203(91)90057-C
[12]	B. K. Ray and K. S. Ray, “A New Split-and-Merge Technique for Polygonal Approximation of Chain Coded Curves,” Pattern Recognition Letters, Vol. 16, No. 2, 1995, pp. 161-169. doi:10.1016/0167-8655(94)00081-D
[13]	J. G. Dunham, “Optimum Uniform Piecewise Linear Approximation of Planar Curves,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 8, No. 1, 1986, pp. 67-75. doi:10.1109/TPAMI.1986.4767753
[14]	Y. Sato, “Piecewise Linear Approximation of Plane Curves by Perimeter Optimization,” Pattern Recognition, Vol. 25, No. 12, 1992, pp. 1535-1543. doi:10.1016/0031-3203(92)90126-4
[15]	S. C. Huang and Y. N. Sun, “Polygonal Approximation Using Genetic Algorithms,” Pattern Recognition, Vol. 32, No. 8, 1999, pp. 1409-1420. doi:10.1016/S0031-3203(98)00173-3
[16]	P. Y. Yin, “Genetic Algorithms for Polygonal Approximation of Digital Curves,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 13, No. 7, 1999, pp. 1-22. doi:10.1142/S0218001499000598
[17]	P. Y. Yin, “A Tabu Search Approach to the Polygonal Approximation of Digital Curves,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 14, No. 2, 2000, pp. 243-255. doi:10.1142/S0218001400000167
[18]	J. H. Horng, “Improving Fitting Quality of Polygonal Approximation by Using the Dynamic Programming Technique,” Pattern Recognition Letters, Vol. 23, No. 14, 2002, pp. 1657-1673. doi:10.1016/S0167-8655(02)00129-0
[19]	F. Glover, “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computers & Operations Research, Vol. 13, No. 5, 1986, pp. 533-549. doi:10.1016/0305-0548(86)90048-1
[20]	M. Dorigo, “Optimization, Learning, and Natural Algorithms,” Ph.D. Thesis, Politecnico di Milano, Milano, 1992.
[21]	Wikipedia, 2012. http://en.wikipedia.org/wiki/Ant_colony_optimization
[22]	M. Dorigo, G. Di Caro and L. M. Gambardella, “Ant Algorithms for Discrete Optimization,” Artificial Life, Vol. 5, No. 2, 1999, pp.137-172. doi:10.1162/106454699568728
[23]	L. Costa and R. Cesar, “Shape Analysis and Classification Theory and Practice,” CRC Press, Boca Raton, 2001.
[24]	P. Y. Yin, “Polygonal Approximation of Digital Curves Using the State-of-the-Art Metaheuristics,” In: G. Obinata and A. Dutta, Eds., Vision Systems: Segmentation and Pattern Recognition, I-Tech, Vienna, 2007, pp. 451-464. doi:10.5772/4974
[25]	P. Cornic, “Another Look at Dominant Point Detection of Digital Curves,” Pattern Recognition Letters, Vol. 18, No. 1, 1997, pp. 13-25. doi:10.1016/S0167-8655(96)00116-X
[26]	W. Y. Wu, “Dominant Point Detection Using Adaptive Bending Value,” Image and Vision Computing, Vol. 21, No. 6, 2003, pp. 517-525. doi:10.1016/S0262-8856(03)00031-3
[27]	M. Marji and P. Siy, “A New Algorithm for Dominant Points Detection and Polygonization of Digital Curves,” Pattern Recognition, Vol. 36, No. 10, 2003, pp. 2239-2251. doi:10.1016/S0031-3203(03)00119-5
[28]	W. Y. Wu, “A Dynamic Method for Dominant Point Detection,” Graphical Models, Vol. 64, No. 5, 2003, pp. 304-315. doi:10.1016/S1077-3169(02)00008-4
[29]	C. Di Ruberto and A. Morgera, “A New Algorithm for Polygonal Approximation Based on Ant Colony System,” Lecture Notes in Computer Science, Vol. 5716, 2009, pp. 633-641. doi:10.1007/978-3-642-04146-4_68