Scientific and Technical Journal

ELECTROTECHNIC AND COMPUTER SYSTEMS

ISSN Print 2221-3937
ISSN Online 2221-3805
ANALYSIS OF SKELETONIZATION ALGORITHMS’ FOR BYNARY IMAGES
Abstract:
Binary images skeletons constructing algorithms have been studied. The modern definition of a plane figure skeleton was clarified. The review and classification of existing skeletonization algorithms skeletonization has been performed. Algorithms were classified according to the technique of image processing inside the frame and according to the applied principles of skeletonization. There was marked that the skeleton of a plane figure constructing is Hadamard's ill-posed problem. Incorrectness of the problem produces the faults in resulting skeleton of two types - the formation of false skeleton branches and a violation of its continuity. Two quality indexes of the skeleton that cha-racterize these faults have been introduced for a quantitative comparison of different algorithms. The computing speed has been selected as another measure for comparing the performance of different algorithms. The computing speed is estimated with time of the skeleton constructing procedure for a given algorithm. This estimation should be carried out on the same hardware and software platform to provide comparability of different procedures. Five of the most popular algorithms were chosen to compare the quality of skeletonization: classical morphological skeletonization, two parallel iterative algorithms - Zhang-Suen's and Guo-Hall's ones, iterative sequential Stentiford's algorithm and high quality sequential algorithm by Schepin-Nepomnyaschiy. The algorithms have been implemented as a software in C ++ using OpenCV library in a cost-average performance computing platform for a comparative analysis. The frames of video stream of human moving with the size is 640 * 480 pixels obtained by the consumer webcam were used as original images for skeletonization. A comparative analysis was conducted from the view of the applicability of algorithms in the remote motor rehabilitation of patients. The figure skeletonization algorithm inside the frame is the most resource-intensive computing operation in such systems. Therefore, the purpose of the comparative analysis was skeletonization algorithm selection that works in near-real time and provides a sufficiently high quality skeleton for further patient's movement analysis. The analysis was conducted for processed 340 images from the motor rehabilitation database. It was established that a compromise for motor rehabilitation systems is the Zhang-Suen's algorithm. This algorithm combines high speed with high quality of produced skeleton.
Authors:
Keywords
DOI
10.15276/etks.17.93.2015.15
References
1. Kanunova E.E., Orlov A.A., and Sady-ikov S.S. Metody i algoritmy restavratsii izo-brazheniy arhivnyih tekstovyih dokumentov, [Methods and Algorithms for Image Restoration of Archival Documents], (2006), Moscow, Rus-sian Federation, Mir Publ., 135 p. (In Russian).
2. Afonasenko A.V., and Elizarov A.I. Ob-zor metodov raspoznavaniya strukturirovannyih simvolov [Review of Methods of Detection of Structured Symbols], (2008), Doklady TUSURa, Tomsk, Russian Federation, Vol.2 (18), pp. 83 –88 (In Russian).
3. Inyutin A.V. Algoritm poiska i klassi-fikatsii defektov topologii pechatnyih plat [The Search Algorithm and Classification of Defects in PCB Layout], (2011), Shtuchniy In-telekt, Donetsk, Ukraine, Vol. 3, pp. 228 – 237 (In Russian).
4. Gudkov V.Yu., and Bokov M.V. Byistraya obrabotka izobrazheniy otpechatkov paltsev [Fast Processing of Fingerprint Images], (2012), Infor-matika i ee Primeneniya, Moscow, Russian Fed-eration, Vol.4, pp.99 – 107 (In Russian).
5 Nguen G.K. Primenenie sistem kom-pyuternogo zreniya v zadachah reabilitatsii pat-sientov s boleznyami oporno-dvigatelnogo ap-parata [Application of Computer Vision in the Problems of Rehabilitation of Patients with Dis-eases of the Musculoskeletal System], (2013), Trudyi MNTK “Sovremennyie Informatsionnyie i Elektronnyie Tehnologii SIET–2013”, Odessa, Ukraine, Vol. 1, pp. 53 – 54 (In Russian).
6. Nhuen Hui Kiong, Boltenkov V.O., and Malyavin D.V. Printsipi pobudovi kom-p'yuternih sistem distantsiynogo trenu-vannya na osnovi analizu videopotoku [Principles of Computer Systems for Remote Training by Analyzing the Video Stream], (2014), Vos-tochno-Evropeyskiy Zhurnal Peredovyih Tehnologiy, Kharkov, Ukraine, Vol. 5/2 (71), pp. 25 – 33 (In Ukrainian).
7. Waleed Abu-Ain, , Siti Norul Huda Sheikh Abdullah, Bilal Bataineh, Tarik Abu-Ain, and Khairuddin Omar, (2013), Skeletoniza-tion Algorithm for Binary Images, Procedia Technology, Vol.11, pp. 704 – 709.
8. Blum H., (1967), A Transformation for Extracting new Descriptors of Shape, Models for the Perception of Speech and Visual Form, MIT Press, pp. 362 – 380.
9. Serra J., (1982), Image Analysis and Mathematical Morphology, London-New York, Academic Press, 485 p.
10. Mestetskiy L.M. Nepreryivnaya mor-fologiya binarnyih izobrazheniy. Figuryi. Skele-tyi. Tsirkulyaryi [Continuous Morphology of Bbinary Images. Figure. Skeletons. Circulars], (2009), Moscow, Russian Federation, Fizmatlit Publ., 287 p. (In Russian).
11. Rosenfeld A., and Pfalz J.L., (1967), Computer Representation of Planar Regions by their Skeleton, Comm. of ACM, Vol.10, pp.119 – 125.
12. Domahina L.G. Regulyarizatsiya skele-ta dlya zadachi sravneniya formyi [Regulariza-tion of the Skeleton for the Problem of Compar-ing the Shape], (2009), Matematicheskie meto-dyi Raspoznavaniya Obrazov: Dokladyi XIV Vseros. Konf., Moscow, Russian Federation, pp. 342 – 346 (In Russian).
13. Rogov A.A., Rogova K.A., Kirikov P.V., and Byistrov M.Yu. Nekotoryie metodyi klas-sifikatsii i poiska v elektronnoy kollektsii graficheskih dokumentov, [Some Methods of Classification and Search in the Electronic Col-lection of Graphic Documents], (2010), Trudyi 12-y Vserossiyskoy Nauchnoy Konferentsii “El-ektronnyie Biblioteki: Perspektivnyie Metodyi i Tehnologii, Elektronnyie Kollektsii”, Kazan, Russian Federation, pp. 409 – 414 (In Russian).
14. Soille P., (1999), Morphological Image Analysis, Berlin– Springer-Verlag., 434 р.
15. Zhang T.Y., and Suen C.Y., (1984), A fast Parallel Algorithm for Thinning Digital Pat-terns, Comm. of ACM, Vol. 27, pp. 236 – 239.
16. Guo Z., and Hall R.W., (1989), Parallel Thinning with two Subiteration Algorithms, Comm. of the ACM, Vol. 32, pp. 359 – 373.
17. Stentiford F.W.M., and Mortimer R.G., (1983), Some New Heuristics for Thinning Bi-nary hand Printed Characters for OCR, IEEE Transactions on Systems, Man, and Cybernet-ics, Vol. 13, pp. 81 – 84.
18. Schepin E. V., and Nepomnyaschiy G. M. K topologicheskomu podhodu v analize izo-brazheniy, [On a Topological Approach in Im-age Analysis], (1990), “Geometriya, Topologiya i Prilozheniya”, Mezhvuzovskiy Sbornik Na-uchnyih Trudov, Moskovskiy Institut Priboros-troeniya Publ., Moscow, Russian Federation, pp. 13 – 25 (In Russian).
19. Open CV, (2014), [Internet resource], available at: URL: http://opencv.org. (accessed 01.09.2014).
Published:
Last download:
2017-11-17 12:18:53

[ © KarelWintersky ] [ All articles ] [ All authors ]
[ © Odessa National Polytechnic University, 2014. Any use of information from the site is possible only under the condition that the source link! ]
Яндекс.Метрика