An Analysis on Polygonal Approximation Techniques for Digital Image Boundary
DOI:
https://doi.org/10.13052/jmm1550-4646.1815Keywords:
contour, break points, split and merge, dominant points, polygonal approximation, digital planar curve, integral square error, chain code, digital image boundaryAbstract
Polygonal approximation (PA) techniques have been widely applied in the field of pattern recognition, classification, shape analysis, identification, 3D reconstruction, medical imaging, digital cartography, and geographical information system. In this paper, we focus on some of the key techniques used in implementing the PA algorithms. The PA can be broadly divided into three main category, dominant point detection, threshold error method with minimum number of break points and break points approximation by error minimization. Of the above three methods, there has been always a tradeoff between the three classes and optimality, specifically the optimal algorithm works in a computation intensive way with a complexity ranges from O (N2) to O (N3).The heuristic methods approximate the curve in a speedy way, however they lack in the optimality but have linear time complexity. Here a comprehensive review on major PA techniques for digital planar curve approximation is presented.
Downloads
References
Aguilera-Aguilera, E.J. Carmona-Poyato, A. Madrid-Cuevas, F.J. and Medina-Carnicer R. “The computation of polygonal approximations for 2D contours based on a concavity tree”, Journal of Visual Communication and Image Representation, Vol. 25, No. 8, pp. 1905–1917, 2014.
Aguilera-Aguilera, E.J. Carmona-Poyato, A. Madrid-Cuevas, F.J. and Muoz-Salinas, R. “Novel method to obtain the optimal polygonal approximation of digital planar curves based on Mixed Integer Programming”, Journal of Visual Communication and Image Representation. Vol. 30, pp. 106–116, 2015.
Ansari, N. and Edward, J. Delp. “On detecting dominant points”, Pattern Recognition, Vol. 24, pp. 441–550, 1991.
Attneave, F. “Some informational aspects of visual perception”, Psychol Rev.Vol. 61 No. 2, pp. 183–193, 1954.
Backes, A.R. and Bruno, O.M. “Polygonal approximation of digital planar curves through vertex betweenness”, Inform. Sci, Vol. 222, pp. 795–804, 2013.
Bellman, R. “On the approximation of curves by line segments using dynamic programming”, Communications of ACM, Vol. 4, pp. 284, 1961.
Carmona-Poyato, A. Fernandez-Garcia, N.L. Medina-Carnicer, R. Madrid- Cuevas F.J. “Dominant point detection: a new proposal”, Image and Vision Computing”, Vol. 23, pp. 1226–1236, 2005.
Carmona-Poyato, A. Madrid-Cuevas, F. J. Medina-Carnicer, R. and Muñoz-Salinas, R. “Polygonal approximation of digital planar curves through break point suppression”, Pattern Recognition, Vol. 43, No. 1, pp. 14–25, 2010.
Carmona-Poyato, A., Aguilera-Aguilera, E.J., Madrid-Cuevas F.J. et al., “New method for obtaining optimal polygonal approximations to solve the min-ε
problem”, Neural Computing and Applications. Vol. 28, pp. 2383–2394, 2017.
Carmona-Poyato, A. Madrid-Cuevas, F. J. Fernández-García, N. L. Medina-Carnicer, R. “An improved method for obtaining optimal polygonal approximations”, International Journal of Applied Mathematics and Informatics, Volume 12, pp. 46–50, 2018.
Dilip K. Prasad, Maylor, K. H. Leung, Chai Quek and Siu-Yeung Cho. “A novel framework for making dominant point detection methods non-parametric”, Image and Vision Computing, Vol. 30, No. 11, pp. 843–859, 2012.
Douglas, D.H. and Peucker, T.K. “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature”, Cartograph: Int. J. Geograph. Inf. Geovisual. Vol. 10, No. 2, pp. 112–122, 1973.
Duda, R. O. and Hart, P. E. “Pattern Classification and Scene Analysis”, Wiley-Interscience Publications, New York, pp. 328–329, 1973.
Fernández-García, N.L. Del-Moral Martinez, L. Carmona-Poyato, A. “A new thresholding approach for automatic generation of polygonal approximations”, Journal of Visual Communication and Image Representation, Vol. 35, pp. 155–168, 2016.
Freeman, H. “On the encoding of arbitrary geometric configurations”, IEEE Transactions on Electronic Computer, Vol. 10, pp. 260–268, 1961.
Gluss, B. “Further remarks on line segment curve fitting using dynamic programming”, Communications of ACM, Vol. 5, pp. 441–443, 1962.
Guru, D.S. Dinesh, R. and Nagabhushan, P. “Boundary based corner detection and localization using new cornerity index: a robust approach”. 1st Canadian Conference on Computer and Robot Vision, Vol. 1, pp. 417–423, 2004.
Huang, S.C. and Sung, Y.N. “Polygonal approximation of digital using genetic algorithms”, Pattern Recognition, Vol. 32, pp. 1409–1420, 1999.
Hu, X. and Ahuja, N. “Matching point features with ordered geometric, rigidity, and disparity constraints”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 6, No. 10, pp. 1041–1049, 1994.
Jung, J.-W.; So, B.-C.; Kang, J.-G.; Lim, D.-W.; Son, Y. “Expanded Douglas–Peucker Polygonal Approximation and Opposite Angle-Based Exact Cell Decomposition for Path Planning with Curvilinear Obstacles”, Appl. Sci. 9, 638, 2019.
Kalaivani, S., Ray, B.K. “A heuristic method for initial dominant point detection for polygonal approximations”. Soft Comput 23, 8435–8452, 2019.
Kalaivani, S. and Ray, B.K. “A new dominant point detection technique for polygonal approximation of digital planar closed curves”, Int. J. Intelligent Enterprise, Vol. 8, No. 1, pp. 44–61, 2021.
Marji, M. and Siy, P. “Polygonal representation of digital planar curves through dominant point detection—a nonparametric algorithm”, Pattern Recognition, Vol. 37, pp. 2113–2130, 2004.
Masood, A. and Haq, S.A. “A novel approach to polygonal approximation of digital curves”, J. Vis. Commun. Image Represent, Vol. 18, pp. 264–274, 2007.
Masood, A. “Dominant point detection by reverse polygonization of digital curves”, Image Vis. Comput, Vol. 26, pp. 702–715, 2008a.
Masood A. “Optimized polygonal approximation by dominant point deletion”, Pattern. Recognition, Vol. 41, pp. 227–239, 2008b.
Nicolás Luis Fernández García, Luis Del-Moral Martínez, Ángel Carmona Poyato, Francisco José Madrid Cuevas, Rafael Medina Carnicer, “Unsupervised generation of polygonal approximations based on the convex hull, Pattern Recognition Letters”, Volume 135, Pages 138–145, ISSN 0167-8655, 2020.
R. Neumann, G. Teisseron. “Extraction of dominant points by estimation of the contour fluctuations”, Pattern Recognition Vol. 35, pp. 1447–1462, 2002.
Pavlidis, T. and Horowitz, S. L. “Segmentation of plane curves”, IEEE Transactions on Computers, Vol. 23, pp. 860–870, 1974.
Perez, J.C. and Vidal, E. “Optimum Polygonal Approximation of Digitized Curves”, Pattern Recognition Letters, Vol. 15, pp. 743–750, 1994.
Pikaz, A. and Dinstein, I . “Optimal polygonal approximation of digital curves,” Pattern Recognition, vol. 28, pp. 371–379, 1995.
Ramaiah, M. and Ray, B.K. “Polygonal approximation of digital planar curve using local integral deviation”, Int. J. Computational Vision and Robotics, Vol. 5, No. 3, pp. 302–319, 2015.
Ramer, U. “An iterative procedure for the polygonal approximation of plane curves”, Comput. Graph. Image Process, Vol. 1, No. 3, pp. 244–256, 1972.
Ray, B.K. and Ray, K.S. “A new split-and-merge technique for polygonal approximation of chain coded curves”, Pattern Recognition Letters, Vol. 16, No. 2, pp. 161–169, 1995.
Ray, B.K. and Ray, K.S. “A non-parametric sequential method for polygonal approximation of digital curves”, Pattern Recognition Letters, Vol. 15, pp. 161–167, 1994.
Rosin, P.L. “Techniques for assessing polygonal approximations of curves”, IEEE Trans. Pattern Analysis Machine Intelligence, Vol. 19, No.6, pp. 659–666, 1977.
Şahin Işık, “Dominant point detection based on suboptimal feature selection methods”, Expert Systems with Applications, Vol. 161, 113741, 2020.
Salotti, M. “An efficient algorithm for the optimal polygonal approximation of digitized curves”, Pattern Recognition Letters, Vol. 22, pp. 215–221, 2001.
Salotti, M. “Optimal polygonal approximation of digitized curves using the sum of square deviations criterion”, Pattern Recognition, Vol. 35, pp. 435–443, 2002.
Sarkar, A. “Simple algorithm for detection of signi?cant vertices for polygonal approximation of chain-coded curves”, Pattern Recognition Letters. Vol. 14, pp. 959–964, 1993.
Shu-Chien Huang, “Polygonal Approximation Using an Artificial Bee Colony Algorithm”, Mathematical Problems in Engineering, vol. 2015, Article ID 375926, 10 pages, 2015.
Sklansky, J. “Measuring concavity on a rectangular mosaic”, IEEE Trans. Comput., Vol. 21, pp. 1355–1364, 1972.
Stone, H. “Approximation of curves by line segments”, Mathematics of Computation, Vol. 15, pp. 40–47, 1961.
Semyonov, P.A. “Optimized unjoined linear approximation and its application for eog-biosignal processing”, in 12th IEEE International Conference on Engineering in Medicine and Biology Society, pp. 779–780, 1990.
Wang, B. Shu, H.Z. Li, B.S. and Niu, Z.M. “A mutation-particle swarm algorithm for error-bounded polygonal approximation of digital curves”, Lecture Notes in Computer Science. Vol. 5226, pp. 1149–1155, 2008.
Wang, B. Shu, H. and Luo, L.A. “Genetic algorithm with chromosome-repairing for min–# and min–e polygonal approximation of digital curves”, J. Vis.Commun Image Represent. Vol. 20, No.1, pp. 45–56, 2009.
Wang, B. Brown, D. Zhang, X. Li, H. Gao, Y. and Cao, J. “Polygonal approximation using integer particle swarm optimization”, Information Sciences, 2014, Vol. 278, pp. 311–326, 2014.
Xiao, Y. Zhou, J.J. and Yan, H. “An adaptive split-and-merge method for binary image contour data compression”, Pattern Recognition Letters, Vol. 22, pp. 299–307, 2001.
Yin, P.Y. “A new method for polygonal approximation using genetic algorithms”, Pattern Recognition Letters, Vol. 19, No. 11, pp. 1017–1026, 1998.
Yin P.Y. “A tabu search approach to polygonal approximation of digital curves”, International Journal of Pattern Recognition and Artificial Intelligence, Vol. 13, pp. 1061–1082, 1999.
Yin, P.Y. “Ant colony search algorithms for optimal polygonal approximation of plane curves”, Pattern Recognition, Vol. 36, No.8, pp. 1783–1997, 2003.
Yin, P.Y. “A discrete particle swarm algorithm for optimal approximation of digital curves”, J. Vis. Commun. Image Represent, Vol. 15, No. 2, pp. 241–260, 2004.
MPEG-7 Core Experiment CE-Shape-1Test set (Part B). Benchmarking Image Database for shape Recognition Techniques
