zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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

68T10Pattern recognition, speech recognition
68U10Image processing (computing aspects)
Full Text: DOI
[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. Models of the perception of speech and visual forms, 362-380 (1967)
[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, No. 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, 437-446 (2005)
[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, 991-996 (2004)
[11] Latecki, L. J.; Lakämper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. vision image understanding 73, No. 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; Kumar, M. Pawan; 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, 417-423 (2004)
[24] Held, A.; Abe, K.; Arcelli, C.: Towards a hierarchical contour description via dominant point detection. IEEE trans. Syst. man cybern. 24, No. 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) · 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, No. 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, 398-409 (1999)
[32] Latecki, L. J.; Ghadially, R. -R.; Lakämper, R.; Eckhardt, U.: Continuity of the discrete curve evolution. J. electron. Imaging 9, No. 3, 317-326 (2000)
[33] Zhu, P.; Chirlian, P. M.: On critical point detection of digital shapes. IEEE trans. Pattern anal. Mach intell. 17, No. 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, No. 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.
[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.; Detection, K. W. Huang. Non-Parametric Dominant Points: 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.
[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.
[53] Zhu, Y.; Seneviratne, L. D.: Optimal polygonal approximation of digitized curves. IEE proc. Vision image signal process. 144, 8-14 (1997)