(27) * << * >> * Russian * English * Content * All Issues

Iterative approximation of sequences along the maximum of the perimeter and using the triangle inequality

R.V. Khmelev 1, 2
1Image Processing Systems Institute of RAS
2Samara State Aerospace University (SSAU)

 PDF, 125 kB

Pages: 155-164.

Full text of article: Russian language.

Abstract:
The paper describes three proprietary algorithms of iterative approximation, primarily, iterative polygonal approximation of contour chains based on the principle of the maximum perimeter of an approximating polygon. The algorithms are designed to analyze the shape of the contours. A modification is also presented that allows to use these algorithms for iterative approximation of one-dimensional sequences, and that can be used in the analysis of sound and image raster.

Keywords:
iterative approximation, triangle inequality, maximum perimeter of an approximating polygon, image raster, sound.

Citation:
Khmelev RV. Iterative approximation of sequences along the maximum of the perimeter and using the triangle inequality. Computer Optics 2005; 27: 155-164.

Acknowledgements:
This work was supported by the Russian-American program “Basic Research and Higher Education” (BRHE), grants of the President of Russia No. NSh-1007.2003.01 and the Russian Foundation for Basic Research No. 04-07-96500.

References:
  1. Chetverikov D, Szabó Z. Detection of high curvature points in planar curves. Source: http://visual.ipan.sztaki.hu/corner/.
  2. Kolesnikov A. Efficient algorithms for vectorization and polygonal approximation. Ch 3. PhD Thesis 2003.
  3. Vallone U. Bidemensional shapes polygonalization by ACO. Proc 3rd Int Workshop on Ants Algorithms 2002: 296-297. DOI: 10.1007/3-540-45724-0_33.
  4. Dorigo N. Optimization, learning, and natural algorithms. PhD Thesis. Milano, Italia: Politecnico di Milano; 1992.
  5. Dorigo M, Di Caro G, Gambardella LM. Ant algorithms for discrete optimization. Artif Life 1999; 5(2): 137-172. DOI: 10.1162/106454699568728.
  6. Leu JG, Chen L. Polygonal approximation of 2-D shapes through boundary merging. Pattern Recognit Lett 1988; 7(4): 231-238. DOI: 10.1016/0167-8655(88)90107-9.
  7. Latecki LJ, Lakamper R. Convexity rule for shape decomposition based on discrete contour evolution. Comput Vis Image Underst 1999; 73(3): 441-454. DOI: 10.1006/cviu.1998.0738.
  8. Ku KM, Chiu KM. Polygonal approximation of digital curve by graduate iterative merging. Electron Lett 1995; 31(6): 444-446. DOI: 10.1049/el:19950319.
  9. Fahn C-S, Wang J-F, Lee J-Y. An adaptive reduction procedure for the piecewise linear approximation of digitized curves. IEEE Trans Pattern Anal Mach Intell 1989; 11(9): 967-973. DOI: 10.1109/34.35499.
  10. Wu J-S, Leou J-J. New polygonal approximation schemes for object shape representation. Pattern Recogn 1993; 26(4): 471-484. DOI: 10.1016/0031-3203(93)90103-4.
  11. Boxer L, Chang C-S, Miller R, Rau-Chaplin A. Polygonal approximation by boundary reduction. Pattern Recogn Lett 1993; 14(2): 111-119. DOI: 10.1016/0167-8655(93)90084-Q.
  12. Visvalingam M, Whyatt J. Line generalization by repeated elimination of points. Cartogr J 1993; 30(1): 46-51. DOI: 10.1179/000870493786962263.
  13. Pikaz A, Dinstein I. An algorithm for polygonal approximation based on iterative point elimination. Pattern Recogn Lett 1995; 16(6): 557-563. DOI: 10.1016/0167-8655(95)80001-A.
  14. Horst JA, Beichel I. A simple algorithm for efficient piecewise linear approximation of space curves. Proc Int Conf on Image Proces (ICIP'97) 1997; 2: 744-747. DOI: 10.1109/ICIP.1997.638603.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ko@smr.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20