THE TECHNIQUE OF HOMOTOPIC SKELETONIZATION OF BIT-MAPPED DRAWINGS OF PARTS OF SEA TRANSPORT

V. S. Molchanova

Abstract


Context. Skeletonization is used in image processing of technical drawings, including drawings of sea transport parts, since the object’s
skeleton reflects its topological structure. Сomparative analysis of the best methods of parallel topological skeletonization of the area
objects, using spatial masks, showed that they give iterative distortions to the topology of primitives and their compositions. Therefore,
the task of developing a technique for homotopic skeletonization of bit-mapped drawings of sea transport parts is relevant.
Objective. To develope technique of improvement of topological equivalence of the skeletons to the сontour of sea transport parts,
by means of gradual correction of typical skeleton’s distortions.
Method. Сorrection of skeleton’s iterative distortions by modified spatial masks of the basic method of skeletonization and the reconstruction of the resulting skeleton by masks to restore its homotopy to the original, on the basis of developed reconstruction rules.
Execution of the proposed technique was carried out on example of the basic method R.Y. Wu & W.H. Tsai.
Results. The proposed technique is implemented as a program application that allows to perform quality skeletonization of images
of drawings of sea transport parts.
Conclusions. The shown examples of results of skeletonization of drawings of parts confirm efficiency of the proposed technique.
The technique can be adapted to the methods of topological skeletonization of area objects, based upon application of spatial masks.

Keywords


сonnectivity; distortion; drawing; homotopic; mask; skeleton; technique.

References


Dori D., Liu W. Algorithms for 2D Engineering Drawings

Recognition: Implemen-tation and Evaluation, LAP LAMBERT

Academic Publishing, 2014, 88 p.

Chiang J. Y., Tue S. C. and Leu Y. C. A New Algorithm for Line

Image Vectorization, Pattern Recognition, 1998, No. 3, pp. 1541–

DOI: 10.1016/s0031-3203(97) 00157.

Zhang T. Y., Suen C. Y. A fast parallel algorithm for thinning

digital patterns, Communications of the ACM, 1984, No. 27,

Vol. 3, pp. 236–239. DOI: 10.1145/357994. 358023.

Kushnir O. A. Sravnenie formy binarnyh rastrovyh izobrazhenij

na osnove skeletizacii, Mashinnoe obuchenie i analiz dannyh,

, No. 3, pp. 252–263.

Roseborough J. B., Murase H. A. Partial Eigenvalue Decomposition for

Large Image Sets Using Run-Length Encoding, Pattern Recognition,

, No. 3, pp. 421–430. DOI: 10.1016/0031-3203(94)00113-z.

Baranov R. P., Favorskaja M. N. Algoritmy skeletizacii ob#ektov

na izobrazhenii, Aktual’nye problemy aviacii i kosmonavtiki,

, No. 7, Tom I, P. 349.

Klubkov I. M. Primenenie volnovogo algoritma dlja nahozhdenija

skeleta rastrovogo, Vestnik DGTU, 2001, No. 1 (7), pp. 9–16.

Ablamejko S. V., Lagunovskij D. M. Obrabotka izobrazhenij:

tehnologija, metody, primenenie. Minsk, Amalfeja, 2000, 304 p.

Hori O. O., Tanigawa S. T. Document Analysis and Recognition,

Raster-to-Vector Conversion by Line Fitting Based on Contours

and Skeletons. Kawasaki, Japan, 1993, pp. 272–281.

DOI: 10.1109 / icdar. 1993.395716

Gonsales R. C., Vuds R. Je., S. A. Jeddins. Cifrovaja obrabotka

izobrazhenij v srede Matlab. Moscow, Tehnosfera, 2006, 616 p.

Tropchenko A. Ju. Metody vtorichnoj obrabotki izobrazhenij i

raspoznavanija ob#ektov: uchebnoe posobie. SPb., SPbGU ITMO,

, 52 p.

Arcelli C., Cordella L. P., Levialdi S. Parallel thinning of binary

pictures, Electronic Letters, 1975, No. 11 (7), P. 148–149. DOI: 10.

/el:19750113.

Improved low complexity fully parallel thinning algorithm: In

Procee-dings 10th International Conference on Image Analysis

and Processing (ICIAP’99), (Venice, 27–29.09.1999), Venice,

, pp. 215-220. DOI: 10.1109/iciap.1999.797597.

Chin R. T., Wan H. K., Stover D. L. A one pass thinning algorithm

and its parallel implementation, Computer Vision, Graphics, and

Image Processing, 1987, № 40(1), pp. 30–40. DOI: 10.1016/

s0734-189x (87)80139-1.

Eckhardt U., Maderlechner G. Invariant thinning and distance

transform, Theoretical Foundations of Computer Vision, 1993,

Vol. 11, pp. 1115–1144. DOI: 10. 1007/978-3-7091-6586-7_2.

Guo Z., Hall R. W. Fast parallel thinning algorithms, CVGIP:

Image Understanding, 1992, Volume 55, Issue 3, pp. 317–328.

DOI: 10.1016/1049-9660(92)90029-3.

Jagna A. An efficient image independent thinning algorithm ,

International journal of advanced research in computer and

communication engineering, 2014, Vol. 3, Issue 10, pp. 8309–

DOI: 10.17148 / ijarcce.2014.31052.

Wu R. Y., Tsai W. H. A new one pass parallel thinning algorithm

for binary images, Pattern recognition letters, 1992, No. 10,

pp. 715–723. DOI: 10.1016/0167-8655 (92) 90101-5.

Holt C. M., Stewart A., Clint M. An improved parallel thinning

algorithm, Communications of the ACM, 1987, Volume 30, Issue

, pp. 156–160. DOI: 10.1016 / j.cag. 2012. 06.001.

Zou R. W., Cai Z. R., and Zhang F. A. Line Interpolation Method

and Error Estimation Based on Run Length Coding, J. Software,

, No. 8, pp. 404–410. DOI: 10.3724 / sp.j.1087.2008.02270.

Holt C. M., Stewart A., Clint M. An improved parallel thinning

algorithm, Communications of the ACM, 1987, Volume 30,

Issue 2, pp. 156–160.

Jang B. K., Chin R. T. Reconstructable parallel thinning,

International Journal of Pattern Recognition and Artificial

Intelligence, 1993, Volume 07, Issue 05, pp. 1145–1181.

DOI: 10.1142/9789812797858_0010.


GOST Style Citations


1. Dori D. Algorithms for 2D Engineering Drawings Recognition:
Implementation and Evaluation / D. Dori, W. Liu. – LAP
LAMBERT Academic Publishing, 2014. – 88 p.
2. Chiang J. Y. A New Algorithm for Line Image Vectorization /
J. Y. Chiang, S. C. Tue, and Y. C. Leu // Pattern Recognition. –
1998. – № 3. – P. 1541–1549. DOI: 10.1016/s0031-
3203(97)00157.
3. Zhang T. Y. A fast parallel algorithm for thinning digital patterns / T. Y. Zhang, C. Y. Suen // Communications of the ACM. – 1984. – №27, Т. 3. – P. 236–239. DOI: 10.1145/357994. 358023.
4. Кушнир О. А. Сравнение формы бинарных растровых изображений на основе ске-летизации / О. А. Кушнир // Машинное обучение и анализ данных. – 2012. – № 3. – С. 252–263.
5. Roseborough J. B. Partial Eigenvalue Decomposition for Large Image Sets Using Run-Length Encoding / J. B. Roseborough, H. A. Murase // Pattern Recognition. – 1995. – № 3. – P. 421–430. doi:10.1016/0031-3203(94)00113-z.
6. Баранов Р. П. Алгоритмы скелетизации объектов на изображении / Р. П. Баранов, М. Н. Фаворская // Актуальные проблемы авиации и космонавтики. – 2011. – № 7, Том I. – С. 349.
7. Клубков И. М. Применение волнового алгоритма для нахождения скелета растрового изображения / И. М. Клубков // Вестник ДГТУ. – 2001. – №1 (7). – С. 9–16.
8. Абламейко С. В. Обработка изображений: техноло-гия, методы, применение / С. В. Абламейко, Д. М. Лагуновский. – Минск: Амалфея, 2000. – 304 с.
9. Hori O. O. Document Analysis and Recognition / O. O. Hori,
S. T. Tanigawa // Raster-to-Vector Conversion by Line Fitting
Based on Contours and Skeletons. – Kawasaki, Japan. – 1993. –P. 272–281. DOI: 10.1109 / icdar. 1993.395716.
10. Гонсалес Р. C. Цифровая обработка изображений в среде Matlab / Р. C. Гонсалес, Р. Э. Вудс, С. А. Эддинс. – М. : Техносфера, 2006. – 616 c.
11. Тропченко А. Ю. Методы вторичной обработки изображений и распознавания объектов: учебное пособие / А. Ю. Тропченко. – СПб. : СПбГУ ИТМО, 2012. – 52 с.
12.Arcelli C. Parallel thinning of binary pictures / C. Arcelli,
L. P. Cordella, S. Levialdi // Electronic Letters. –1975. – № 11
(7). – P. 148–149. DOI: 10. 1049/el:19750113
13. Improved low complexity fully parallel thinning algorithm: InProceedings 10th International Conference on Image Analysis and Processing (ICIAP’99), (Venice, 27–29.09.1999). – Venice, 1999. – P. 215–220. DOI: 10.1109/iciap.1999.797597.
14.Chin R. T. A one pass thinning algorithm and its parallel
implementation / R. T. Chin, H. K. Wan, D. L. Stover// Computer Vision, Graphics, and Image Processing. – 1987. – № 40(1). – P. 30-40. DOI: 10.1016/s0734-189x (87)80139-1.
15.Eckhardt U. Invariant thinning and distance transform /
U. Eckhardt, G. Maderlechner // Theoretical Foundations of
Computer Vision. – 1993. – Vol. 11. – P. 1115–1144.
DOI: 10.1007/978-3-7091-6586-7_2.
16. Guo Z. Fast parallel thinning algorithms/ Z. Guo, R. W. Hall // CVGIP: Image Understanding. – 1992. – Volume 55, Issue 3. – P. 317–328. DOI: 10.1016/1049-9660(92)90029-3.
17. Jagna A. An efficient image independent thinning algorithm / A. Jagna // International journal of advanced research in computer and communication engineering. – 2014. – Vol. 3, Issue 10. – P. 8309–8311. DOI: 10.17148 / ijarcce.2014.31052.
18.Wu R. Y. A new one pass parallel thinning algorithm for binary images / R. Y. Wu, W. H. Tsai // Pattern recognition letters. – 1992. – № 10. – P. 715–723. DOI: 10.1016/0167-8655(92)90101-5.
19.Holt C. M. An improved parallel thinning algorithm /
C. M. Holt, A. Stewart, M. Clint // Communications of the
ACM. – 1987. – Volume 30, Issue 2. – P. 156–160. DOI: 10.1016 / j.cag. 2012.06.001.
20. Zou R. W. Line Interpolation Method and Error Estimation
Based on Run Length Coding / R. W. Zou, Z. R. Cai, and
F. A. Zhang // J. Software. – 1997. – № 8. – P. 404–410. DOI:
10.3724 / sp.j.1087.2008.02270.
21. Holt C. M. An improved parallel thinning algorithm / C. M. Holt, A. Stewart, M. Clint // Communications of the ACM. – 1987. – Volume 30, Issue 2. – P. 156–160.
22.Jang B. K. Reconstructable parallel thinning / B. K. Jang,
R. T. Chin // International Journal of Pattern Recognition and
Artificial Intelligence. – 1993. – Volume 07, Issue 05. – P. 1145- 1181. DOI: 10.1142/9789812797858_0010.




DOI: https://doi.org/10.15588/1607-3274-2018-1-16



Copyright (c) 2018 V. S. Molchanova

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.