×

Optimized polygonal approximation by dominant point deletion. (English) Zbl 1122.68550

Summary: An algorithm for polygonal approximation based on dominant point (DP) deletion is presented in this paper. The algorithm selects an initial set of DPs and starts eliminating them one by one depending upon the error associated with each DP. The associated error value is based on global measure. A local optimization of few neighboring points is performed after each deletion. Although the algorithm does not guarantee an optimal solution, the combination of local and global optimization is expected to produce optimal results. The algorithm is extensively tested on various shapes with varying number of DPs and error threshold. In general, optimal results were observed for about 96% of the times. A good comparative study is also presented in this paper

MSC:

68T10 Pattern recognition, speech recognition
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kartikeyan, B.; Sarkar, A., Shape description by time series, IEEE Trans. Pattern Anal. Mach. Intell., 11, 977-984 (1989)
[2] Kashyap, R.; Dhellapa, R., Stochastic models for closed boundary analysis: representation and reconstruction, IEEE Trans. Info. Theory, 27, 627-637 (1981) · Zbl 0471.68073
[3] Blum, H., A transformation for extracting new descriptors of the shape, (Whaten-Dunn, Models of the Perception of Speech and Visual Forms (1967), MIT Press: MIT Press Cambridge, MA), 362-380
[4] Koenderink, J. J.; van Doorn, A. J., The internal representation of solid shape with respect to vision, Biol. Cyber, 32, 211-216 (1979) · Zbl 0447.92028
[5] Chau, C. P.; Siu, W. C., New nonparametric dominant point detection algorithm, Vision Image Signal Process., 148, 5, 363-374 (2001)
[6] Cronin, T. M., A boundary concavity code to support dominant points detection, Pattern Recognition Lett., 20, 617-634 (1999)
[7] Marji, M.; Siy, P., A new algorithm for dominant points detection and polygonization of digital curves, Pattern Recognition, 36, 2239-2251 (2003) · Zbl 1054.68156
[8] Park, H.; Lee, J. H., Error-bounded B-spline curve approximation based on dominant point selection, (IEEE International Conference on Computer Imaging and Vision: New Trends (2005)), 437-446
[9] Rattarangsi, A.; Chin, R. T., Scale-based detection of corners of planar curves, Trans. Pattern Anal. Mach. Intell., 14, 430-449 (1992)
[10] Sarfraz, M.; Asim, M. R.; Masood, A., Piecewise polygonal approximation of digital curves, (8th IEEE International Conference on Information Visualisation, UK (2004), IEEE Computer Society Press: IEEE Computer Society Press USA), 991-996
[11] Latecki, L. J.; Lakämper, R., Convexity rule for shape decomposition based on discrete contour evolution, Comput. Vision Image Understanding, 73, 3, 441-454 (1999)
[12] Schuster, G. M.; Katsaggelos, A. K., An optimal polygonal boundary encoding scheme in the rate distortion sense, IEEE Trans. Image Process., 7, 13-26 (1998) · Zbl 0973.94012
[13] Goyal, Saurabh; Pawan Kumar, M.; Jawahar, C. V.; Narayanan, P. J., Polygon approximation of closed curves across multiple views, (Indian Conference on Vision, Graphics and Image Processing (2002))
[14] Attneave, F., Some informational aspects of visual perception, Psychol. Rev., 61, 183-193 (1954)
[15] Neumann, R.; Teisseron, G., Extraction of dominant points by estimation of the contour fluctuations, Pattern Recognition, 35, 1447-1462 (2002) · Zbl 1016.68087
[16] Hu, X.; Ahuja, N., Matching point features with ordered geometric, rigidity, and disparity constraints, IEEE Trans. Pattern Anal. Mach. Intell., 16, 1041-1049 (1994)
[17] Sethi, I. K.; Jain, R., Finding trajectories of feature points in a monocular image sequence, IEEE Trans. Pattern Anal. Mach. Intell., 9, 56-73 (1987)
[18] Yuen, P. C., Dominant point matching algorithm, Electron. Lett., 29, 2023-2024 (1993)
[19] Ray, B. K.; Ray, K. S., Determination of optimal polygon from digital curve using L1 norm, Pattern Recognition, 26, 505-509 (1993)
[20] Teh, C.; Chin, R., On the detection of dominant points on digital curves, IEEE Trans. Pattern Anal. Mach. Intell., 8, 859-873 (1989)
[21] Kurozumi, Y.; Davis, W. A., Polygonal approximation by the minimax method, Comput. Graphics Image Process, 19, 248-264 (1982) · Zbl 0534.65096
[22] Ramer, U., An iterative procedure for the polygonal approximation of plane curves, Comput. Graphics Image Process, 1, 244-256 (1972)
[23] Guru, D. S.; Dinesh, R.; Nagabhushan, P., Boundary based corner detection and localization using new ‘cornerity’ index: a robust approach, (1st Canadian Conference on Computer and Robot Vision (2004)), 417-423
[24] Held, A.; Abe, K.; Arcelli, C., Towards a hierarchical contour description via dominant point detection, IEEE Trans. Syst. Man Cybern., 24, 6, 942-949 (1994)
[25] Dunham, J. G., Optimum uniform piecewise linear approximation of planar curves, IEEE Trans. Pattern Anal. Mach. Intell., 8, 67-75 (1986)
[26] Sato, Y., Piecewise linear approximation of plane curves by perimeter optimization, Pattern Recognition, 25, 1535-1543 (1992)
[27] Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning (1989), Addison: Addison Reading, MA · Zbl 0721.68056
[28] Huang, S. C.; Sun, Y. N., Polygonal approximation using genetic algorithms, Pattern Recognition, 32, 1409-1420 (1999)
[29] Pal, N. R.; Nandi, S.; Kundu, M. K., Self crossover: a new genetic operator and its application to feature selection, Int. J. Syst. Sci., 2, 2, 207-212 (1998)
[30] Yin, P. Y., Genetic algorithms for polygonal approximation of digital curves, Int. J. Pattern Recognition Artif. Intell., 13, 1-22 (1999)
[31] Latecki, L. J.; Lakämper, R., Polygon evolution by vertex deletion, (2nd International Conference on Scale-Space Theories in Computer Vision (1999), Springer: Springer Berlin), 398-409
[32] Latecki, L. J.; Ghadially, R.-R.; Lakämper, R.; Eckhardt, U., Continuity of the discrete curve evolution, J. Electron. Imaging, 9, 3, 317-326 (2000)
[33] Zhu, P.; Chirlian, P. M., On critical point detection of digital shapes, IEEE Trans. Pattern Anal. Mach. Intell., 17, 8, 737-748 (1995)
[34] Freeman, H., On the encoding of arbitrary geometric configurations, IEEE Trans. Electron Comput., 10, 260-268 (1961)
[35] Rosin, P. L., Techniques for assessing polygonal approximations of curves, IEEE Trans. PAMI, 19, 6, 659-666 (1997)
[36] Sarkar, D., A simple algorithm for detection of significant vertices for polygonal approximation of chain-coded curves, Pattern Recognition Lett., 14, 959-964 (1993)
[37] Ray, B. K.; Ray, K. S., An algorithm for detecting dominant points and polygonal approximation of digitized curves, Pattern Recognition Lett., 13, 849-856 (1992)
[38] Perez, J. C.; Vidal, E., Optimum polygonal approximation of digitized curves, Pattern Recognition, 15, 743-750 (1994) · Zbl 0818.65008
[39] Lowe, D. G., Three-dimensional object recognition from single two dimensional images, Artif. Intell., 31, 355-395 (1987)
[40] S. Banerjee, W. Niblack, M. Flickner, A minimum description length polygonal approximation method, Technical Report no. RJ 10007, IBM Research Division, 1996.; S. Banerjee, W. Niblack, M. Flickner, A minimum description length polygonal approximation method, Technical Report no. RJ 10007, IBM Research Division, 1996.
[41] Chung, P. C.; Tsai, C. T.; Sun, Y. N., Polygonal approximation using a competitive hopfield neural network, Pattern Recognition, 27, 505-512 (1994)
[42] Arcelli, C.; Ramella, G., Finding contour-based abstractions of planar patterns, Pattern Recognition, 26, 563-577 (1993)
[43] Anderson, I. M.; Bezdek, J. C., Curvature and tangential deflection of discrete arcs, Trans. Pattern Anal. Mach. Intell., 6, 27-40 (1984) · Zbl 0537.68093
[44] Ray, B. K.; Ray, K. S., Detection of significant points and polygonal approximation of digital curves, Pattern Recognition Lett., 13, 443-452 (1992)
[45] Wu, W. Y., An adaptive method for detecting dominant points, Pattern Recognition, 36, 2231-2237 (2003) · Zbl 1054.68157
[46] Ansari, N.; Non-parametric dominant points detection, K. W.Huang., Pattern Recognition, 24, 849-862 (1991)
[47] Marji, M.; Siy, P., Polygonal representation of digital planar curves through dominant point detection—a nonparametric algorithm, Pattern Recognition, 37, 2113-2130 (2004)
[48] Horng, J. H.; Li, J. T., An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves, Pattern Recognition Lett., 23, 171-182 (2002) · Zbl 0993.68109
[49] Kolesnikov, A.; Fränti, P., Reduced search dynamic programming for approximation of polygonal curves, Pattern Recognition Lett., 24, 2243-2254 (2003) · Zbl 1035.68123
[50] M. Salotti, Improvement of Perez and Vidal algorithm for the decomposition of digitized curves into line segments, in: 15th International Conference on Pattern Recognition, vol. 2, 2000, pp. 878-882.; M. Salotti, Improvement of Perez and Vidal algorithm for the decomposition of digitized curves into line segments, in: 15th International Conference on Pattern Recognition, vol. 2, 2000, pp. 878-882.
[51] Horng, J. H., Improving fitting quality of polygonal approximation by using the dynamic programming technique, Pattern Recognition Lett., 23, 1657-1673 (2002) · Zbl 1010.68139
[52] A. Kolesnikov, P. Franti, Min-# polygonal approximation of closed curves, in: IEEE International Conference on Image Processing, vol. 2, 2005, pp. 522-525.; A. Kolesnikov, P. Franti, Min-# polygonal approximation of closed curves, in: IEEE International Conference on Image Processing, vol. 2, 2005, pp. 522-525.
[53] Zhu, Y.; Seneviratne, L. D., Optimal polygonal approximation of digitized curves, IEE Proc. Vision Image Signal Process., 144, 8-14 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.