2020, issue 3, p. 85-89
Received 14.08.2020; Revised 29.08.2020; Accepted 23.10.2020
Published 27.10.2020; First Online 05.11.2020
Approximation of the Contour of an Object in an Image Using Vector Operations
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Introduction. One of the directions associated with identification, analysis of the shape of objects, their size, orientation, marking and other geometric characteristics is contour analysis.
Various methods for contour approximation are described in the literature. The proposed method is based on a well-known method. Its essence lies in the sequential search for possible directions and end points of approximating straight line segments belonging to the contour. The number of approximation nodes should be as small as possible. The calculation is carried out only for the next point of the contour, without returning to check the criterion of approximation to all previous points. The computational complexity of the algorithm is proportional to the number of points in the contour.
The purpose of the paper to propose a method of piecewise linear approximation of the contours of objects in images, which will allow to use the parallel computations at all stages of computer processing using vector operations.
Results. The paper proposes an improved method for piecewise linear approximation of a closed contour of an object in an image by a polygon, the vertices of which are directly the points of this contour. Approximation criterion: the distance from each point of the approximated section of the contour to the approximating segment should not exceed the approximation error. The method is focused on parallel computing using vector operations.
A method for parallel computation of integral vectors of extreme values of a sequence of numbers for the implementation of parallel computations using vector operations at all stages of approximation is also proposed.
Conclusions. Methods are proposed that are implemented using vector operations and provide an opportunity to speed up the solution of contour analysis problems, as well as other similar problems in real time. The gain in computing speed is proportional to the amount of data that a vector processor can simultaneously process. The presence of developed subsystems of vector instructions in Intel and ARM processors makes it possible to use the proposed computation methods in practice.
Keywords: image, object contour, piecewise linear approximation, parallel computations, vector operations.
Cite as: Sabelnikov P. Approximation of the Contour of an Object in an Image Using Vector Operations. Cybernetics and Computer Technologies. 2020. 3. P. 85–89. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.3.8
1. Furman Ya.A., Yuriev A.N., Yanshin V.V. Digital methods of processing and recognition of binary images. Krasnoyarsk: Izd-vo Krasnoyarsk. un-ta, 1992. 248 p. https://www.twirpx.com/file/260742/
2. Furman Ya.A., Krevetsky A.V., Peredreev A.K. etc. Introduction to contour analysis; applications to image and signal processing. Moscow: Fizmatlit, 2003. 592 p. https://www.twirpx.com/file/190580/
3. Melnik E.I. Highlighting lines and arcs of circles in technical drawings. Automation of image processing and recognition. Minsk: ITK ANB, 1995. P. 147–154.
4. Pratt W. Digital Image Processing Vol. 2. Moscow: Mir, 1982. 480 p. https://www.twirpx.com/file/73664/
5. Butakov E.A., Ostrovsky V.I., Fadeev I.L. Image processing on a computer. Moscow: Radio i sviaz, 1987. 240 p. http://computersbooks.net/books/photoshop/butakov-ea/1987/files/obrabotkaizobrageniynaevm1987.djv
6. Boyun V.P., Sabelnikov P.Yu., Sabelnikov Yu. A. Approximation of a closed contour image by a polygon. Computerni zasobi, mereshi ta sistemi. 2013. P. 89−97. http://dspace.nbuv.gov.ua/handle/123456789/69713
7. Sabelnikov P.Yu. Vector operating device: pat. Ukraina na vinahid №120139. V.M. Institute of Cybernetics Glushkova NAS of Ukraine. IPC G06F 7/00. № u2018 00962; declared 02/02/2018; publ. 10/10/2019 Bull. N 19. 5 p. https://base.uipv.org/searchINV/search.php?action=viewdetails&IdClaim=262085
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)