Abstract
In this paper, a polygonal approximation approach based on a multi-objective genetic algorithm is proposed. In this method, the optimization/exploration algorithm locates breakpoints on the digital curve by minimizing simultaneously the number of breakpoints and the approximation error. Using such an approach, the algorithm proposes a set of solutions at its end. This set which is called the Pareto Front in the multi objective optimization field contains solutions that represent trade-offs between the two classical quality criteria of polygonal approximation : the Integral Square Error (ISE) and the number of vertices. The user may choose his own solution according to its objective. The proposed approach is evaluated on curves issued from the literature and compared with many classical approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Salotti, M.: An efficient algorithm for the optimal polygonal approximation of digitized curves. PRL 22, 215–221 (2001)
Ramer, U.: An iterative procedure for the polygonal approximation of plane curves. CGIP 1, 291–297 (1972)
Pavlidis, T., Horowitz, S.L.: Segmentation of plane curves. IEEE Transaction on Computers 23, 860–870 (1974)
Wall, K., Danielsson, P.E.: A fast sequential method for polygonal approximation of digitized curves. CVGIP 28, 220–227 (1984)
Gupta, A., Chaudhury, S., Parthasarathy, G.: A new approach for aggregating edge points into line segments. PR 26, 1069–1086 (1993)
Hu, J., Yan, H.: Polygonal approximation of digital curves based on the principles of perceptual organization. PR 30, 701–718 (2002)
Teh, C., Chin, R.T.: On the detection of dominant points on digital curves. IEEE transaction on PAMI 23, 859–872 (1989)
Ansari, N., Delp, E.J.: On detecting dominant points. PR 24, 441–451 (1991)
Ray, B.K., Ray, K.S.: An algorithm for detecting dominant points and polygonal approximation of digitized curves. PRL 13, 849–856 (1992)
Ray, B.K., Ray, K.S.: Detection of significant points and polygonal approximation of digitized curves. PRL 12, 443–452 (1992)
Cornic, P.: Another look at the dominant point detection of digitized curves. PRL 18, 13–25 (1997)
Marji, M., Siy, P.: A new algorithm for dominant points detection and polygonization of digital curves. PR 36, 2239–2251 (2003)
Chung, P.C., Tsai, C.T., Chen, E.L., Sun, Y.N.: Polygonal approximation using a competitive Hopfield neural network. PR 27, 1505–1512 (1994)
Perez, J.C., Vidal, E.: Optimum polygonal approximation of digitized curves. PRL 15, 743–750 (1994)
Horng, J.H., Li, J.T.: An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves. PRL 23, 171–182 (2002)
Yin, P.Y.: A new method for polygonal approximation of digital curves. PRL 19, 1017–1026 (1998)
Huang, S.C., Sun, Y.N.: Polygonal approximation using genetic algorithm. PR 32, 1409–1420 (1999)
Sarkar, B., Singh, L.K., Sarkar, D.: Approximation of digital curves with line segments and circular arcs using genetic algorithms. PRL 24, 2585–2595 (2003)
Yin, P.Y.: A new circle/ellipse detector using genetic algorithm. PRL 20, 731–740 (1999)
Deb, K.: Multi-Objective optimization using Evolutionary algorithms. Wiley, London (2001)
Schaffer, J.D., Grefenstette, J.J.: Multiobjective learning via genetic algorithms. In: Proceedings of the 9th IJCAI, pp. 593–595 (1985)
Fonseca, C.M., Fleming, P.J.: Genetic algorithm for multi-objective optimization: formulation, discussion and generalization. In: The proceedings of the fifth ICGA, pp. 416–423 (1993)
Srinivas, N., Deb, K.: Multiobjective optimization using nondominated sorting in genetic algorithm. EC 2, 221–248 (1994)
Deb, K., Agrawal, S., Pratab, A., Meyarivan, T.: A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on EC 6, 182–197 (2000)
Knowles, J.D., Corne, D.W.: Approximating the nondominated front using the Pareto archived evolution strategy. EC 8, 149–172 (2000)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative study and the strength pareto approach. IEEE Transactions on EC 3, 257–271 (1999)
Coello Coello, C.A.: A short tutorial on Evolutionary Multiobjective Optimisation. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 21–40. Springer, Heidelberg (2001)
Chafekar, D., Xuan, J., Rasheed, K.: Constrained Multi-objective Optimization Using Steady State Genetic Algorithms. In: Proceedings of GECC, pp. 813–824 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Locteau, H., Raveaux, R., Adam, S., Lecourtier, Y., Heroux, P., Trupin, E. (2006). Polygonal Approximation of Digital Curves Using a Multi-objective Genetic Algorithm. In: Liu, W., Lladós, J. (eds) Graphics Recognition. Ten Years Review and Future Perspectives. GREC 2005. Lecture Notes in Computer Science, vol 3926. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11767978_27
Download citation
DOI: https://doi.org/10.1007/11767978_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34711-8
Online ISBN: 978-3-540-34712-5
eBook Packages: Computer ScienceComputer Science (R0)