Raiymbek SULTANOV, Rita ISMAILOVA, Ahmet ATAKAN

An algorithm for line matching in an image by mapping into an n-dimensional vector space

This paper proposes a minimal length difference algorithm for construction of a line in an image by solvingthe problem of optimal contour approximation. In this algorithm, a method for finding interest points is proposed, andthe object matching (classification) is done by mapping interest points onto a vector space. In cases where the lines inthe representation of the images are not smooth, the algorithm converges rapidly. The results of the experiments showedthat for convergence of the contour simplification, there were 5-6 iterations for n = 13. To check how close the curveapproximation calculated by the algorithm above, the researchers have calculated the length of the curve simplificationmanually. This length was then compared to the length of the original curve. The results showed that the length of thesimplified curve grew rapidly to 92%–95% of the original curve length. The further increase in the number of points doesnot affect this indicator. According to the obtained results, the relative difference and the relative difference distanceare good metrics to match objects.

PDF

___

[1] Veltkamp RC, Hagedoor M. State of the art in shape matching. In: Lew MS, editor. Principles of Visual Information Retrieval. London, UK: Springer-Verlag, 2001. pp. 87-119.
[2] Alt H, Guibas LJ. Discrete geometric shapes: matching, interpolation, and approximation. In: Sack JR, Urrutia J, editors. Handbook of Computational Geometry. Amsterdam, the Netherlands: Elsevier, 2000. pp. 121-153.
[3] Balboa JLG, López FJA. Sinuosity pattern recognition of road features for segmentation purposes in cartographic generalization. Pattern Recogn 2009; 42: 2150-2159.
[4] Douglas DH, Peucker TK. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartogr: Int J Geogr Inf Geovisualization 1973; 10: 112-122.
[5] Schmid C, Mohr R, Bauckhage C. Evaluation of interest point detectors. Int J Comput Vision 2000; 37: 151-172.
[6] Heckbert PS, Garland M. Survey of polygonal surface simplification algorithms. Tech report, Carnegie-Mellon University, Pittsburgh, PA, USA, 1997.
[7] Saalfeld A. Topologically consistent line simplification with the Douglas–Peucker algorithm. Cartogr Geogr Inf Sc 1999; 26: 7-18.
[8] Wu ST, Marquez MRG. A non-self-intersection Douglas–Peucker algorithm. In: IEEE 2003 16th Brazilian Symposium on Computer Graphics and Image Processing. Sao Carlos, Brazil. Los Alamitos, CA, USA: IEEE; 2003. pp. 60-66.
[9] Park W, Yu K. Hybrid line simplification for cartographic generalization. Pattern Recogn Lett 2011; 32: 1267-1273.
[10] Song X, Cheng C, Zhou C, Zhu D. Gestalt-based Douglas–Peucker algorithm to keep shape similarity and area consistency of polygons. Sens Lett 2013; 11: 1015-1021.
[11] Pallero J L G. Robust line simplification on the plane. Comput Geosci 2013; 61: 152-159.
[12] Du S. Analyzing topological changes for structural shape simplification. J Visual Lang Comput 2014; 25: 316-332.
[13] Tienaah T, Stefanakis E, Coleman D. Contextual Douglas–Peucker simplification. Geomatica 2015; 69: 327-338.
[14] Hershberger JE, Snoeyink J. Speeding up the Douglas–Peucker line-simplification algorithm. In: 5th Symposium on Data Handling. Charleston, SC, USA: IGU Commission on GIS; 1992. pp. 134–143.
[15] Imai H, Iri M. Computational-geometric methods for polygonal approximations of a curve. Comput Vis Graph Image Process 1986; 36: 31-41.
[16] Douglas DH, Peucker TK. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. In: Dodge M, editor. Classics in Cartography: Reflections on Influential Articles from Cartographica. Oxford, UK: Wiley-Blackwell, 2011. pp. 15-28.
[17] Rodrigues ÉO. Combining Minkowski and Cheyshev: New distance proposal and survey of distance metrics using k-nearest neighbours classifier. Pattern Recogn Lett 2018; 110: 66-71.
[18] Perez JC, Vidal E. Optimum polygonal approximation of digitized curves. Pattern Recogn Lett 1994; 15: 743-750.
[19] Bradski G, Kaehler A. Learning OpenCV: Computer Vision with the OpenCV Library. Sebastopol, CA, USA: O’Reilly Media, 2008.
[20] Ballard D H, Brown C M. Computer vision. Englewood Cliffs, NJ, USA: Prentice-Hall, 1982.
[21] Li C, Wu P, Gu T, Liu X. A study on curve simplification method combining Douglas–Peucker with Li-Openshaw. In: International Conference on Geo-Informatics in Resource Management and Sustainable Ecosystems. Hong Kong, China. Singapore: Springer; 2016. pp. 286-294.
[22] Canny J. A computational approach to edge detection. IEEE T Pattern Anal 1986; Pami-8: 679-98.