Оценка методов скелетизации двумерных бинарных изображений
Ключевые слова:
обработка изображений, техники скелетирования, скелет, двумерные бинарные изображенияАннотация
В сфере современной обработки изображений упор часто делается на инженерные подходы, а не на научные решения разнообразных практических задач. Одна из распространенных задач в этой области включает скелетирование бинарных изображений. Скелетонизация — это мощный процесс извлечения скелета объектов, находящихся в цифровом бинарном изображении. Этот процесс широко используется для автоматизации многих задач в различных областях, таких как распознавание образов, техническое зрение, анимация и анализ изображений. Существующие методы скелетизации в принципе основаны на трех подходах: эрозии границ, дистанционном кодировании и диаграмме Вороного для идентификации приблизительного скелета. В работе представлены результаты эмпирического оценивания набора хорошо известных методов. Затем выполнен расчет скелетов в двумерном бинарном изображении c выбором различных подходов и оценкой их эффективности. Визуальная оценка – это основной метод, используемый для демонстрации производительности выбранных алгоритмов скелетирования. Из-за отсутствия окончательного определения «истинного» скелета цифрового объекта точная оценка эффективности алгоритмов скелетирования представляет собой серьезную исследовательскую задачу. Были попытки проведения количественной оценки, однако применяемые меры обычно адаптировали для конкретных областей. Экспериментальные результаты, показанные в этой работе, иллюстрируют эффективность трех основных подходов к скелетизации изображений в различных перспективных приложениях.
Литература
1. Blum H. Biological Shape and Visual Science. J. Theor. Biol. 1973. vol. 38. pp. 205–287.
2. Zhang Y, Sang L, Grzegorzek M, See J, Yang C. BlumNet: Graph component detection for object skeleton extraction. Proceedings of the 30th ACM International Conference on Multimedia. 2022. pp. 5527–5536.
3. Sanchez-Salvador J.L., Campano C., Lopez-Exposito P., Tarrés Q., Mutjé P., Delgado-Aguilar M., Monte M.C. Blanco A. Enhanced morphological characterization of cellulose nano/microfibers through image skeleton analysis. Nanomaterials. 2021. vol. 11. no. 8. DOI: 10.3390/nano11082077.
4. Zhang F., Chen X., Zhang X. Parallel thinning and skeletonization algorithm based on cellular automaton. Multimedia Tools and Applications. 2020. vol. 79. pp. 33215– 33232.
5. Kotsur D., Tereshchenko V. An optimized algorithm for computing the Voronoi skeleton. International Journal of Computing. 2020. vol. 19. no. 4. pp. 542–554.
6. Wang Y., Xu Y., Tsogkas S., Bai X., Dickinson S, Siddiqi K. Deepflux for skeletons in the wild. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019. pp. 5287–5296.
7. Cha S.H. Comprehensive survey on distance/similarity measures be-tween probability density functions. International Journal of Mathe-matical Models and Methods in Applied Sciences. 2007. vol. 1(4). pp. 300–307.
8. Yatziv L., Bartesaghi A., Sapiro G. O(N) implementation of the fast marching algorithm. Journal of computational physics. 2006. vol. 212. no. 2. pp. 393–399.
9. Wang H., Yu Y., Yuan Q. Application of Dijkstra algorithm in robot path-planning. Second international conference on mechanic automation and control engineering. 2011. pp. 1067–1069.
10. Gonzalez R.C., Woods R.E. Digital Image Processing, 3rd edition. Pearson Education, 2010. 185 p.
11. Song C., Pang Z., Jing X., Xiao C. Distance field guided L1-median skeleton extraction. The Visual Computer. 2018. vol. 34. pp. 243–55.
12. Langer M., Gabdulkhakova A., Kropatsch W.G. Non-centered Voronoi skeletons. Discrete Geometry for Computer Imagery: 21st IAPR International Conference. 2019. pp. 355–366.
13. Boudaoud L.B., Solaiman B., Tari A. A modified ZS thinning algorithm by a hybrid approach. The Visual Computer. 2018. vol. 34. pp. 689–706.
14. Morbiducci U., Mazzi V., Domanin M., De Nisco G., Vergara C., Steinman D.A., Gallo D. Wall shear stress topological skeleton independently predicts long-term restenosis after carotid bifurcation endarterectomy. Annals of biomedical engineering. 2020. vol. 48. pp. 2936–2949.
15. Breuß M., Bruckstein A.M., Kiselman C.O., Maragos P. Shape Analysis: Euclidean, Discrete and Algebraic Geometric Methods. Dagstuhl Reports. 2018. vol. 8. no. 10. pp. 87–103.
16. Zhang W., Wang X., Li X., Chen J. 3D skeletonization feature based computer-aided detection system for pulmonary nodules in CT datasets. Computers in biology and medicine. 2018. vol. 92. pp. 64–72.
17. Malik N.U., Sheikh U.U., Abu-Bakar S.A., Channa A. Multi-View Human Action Recognition Using Skeleton Based-FineKNN with Extraneous Frame Scrapping Technique. Sensors. 2023. vol. 23. no. 5. DOI: 10.3390/s23052745.
18. Ma J., Ren X., Li H., Li W., Tsviatkou V.Y., Boriskevich A.A. Noise-Against Skeleton Extraction Framework and Application on Hand Gesture Recognition. IEEE Access. 2023. vol. 11. pp. 9547–9559.
19. Bataineh B., Alqudah M.K. Evaluation of Skeletonization Methods for Document Images with Rotation States. Amity International Conference on Artificial Intelligence. 2019. pp. 424–428. DOI: 10.1109/AICAI.2019.8701352.
20. Nazarkevych M., Dmytruk S., Hrytsyk V., Vozna O., Kuza A., Shevchuk O., Voznyi Y., Maslanych I., Sheketa V. Evaluation of the effectiveness of different image skeletonization methods in biometric security systems. International Journal of Sensors Wireless Communications and Control. 2021. vol. 11. no. 5. pp. 542–552.
21. Perumalla S.R., Alekhya B., Raju M.C. Digital Skeletonization for Bio-Medical Images. Proceedings of Third International Conference on Sustainable Expert Systems. 2023. pp. 277–291.
22. Ramakrishnan V., Schönmehl R., Artinger A., Winter L., Böck H., Schreml S., Gürtler F., Daza J., Schmitt V.H., Mamilos A., Arbelaez P. 3D Visualization, Skeletonization and Branching Analysis of Blood Vessels in Angiogenesis. International Journal of Molecular Sciences. 2023. vol. 24. no. 9. DOI: 10.3390/ijms24097714.
23. Zhu R., Oda M., Hayashi Y., Kitasaka T., Misawa K., Fujiwara M., Mori K. A skeleton context-aware 3D fully convolutional network for abdominal artery segmentation. International Journal of Computer Assisted Radiology and Surgery. 2023. vol. 18. no. 3. pp. 461–472.
24. Feng Y., Chow L.S., Gowdh N.M., Ramli N., Tan L.K., Abdullah S., Tiang S.S. Gradient-based edge detection with skeletonization (GES) segmentation for magnetic resonance optic nerve images. Biomedical Signal Processing and Control. 2023. vol. 1. no. 80. DOI: 10.3390/ijms24097714.
25. Feng M., Meunier J. Skeleton Graph-Neural-Network-Based Human Action Recognition: A Survey. Sensors. 2022. vol. 22. no. 6. DOI: 10.3390/s22062091.
26. Chen D., Zhang T., Zhou P., Yan C., Li C. OFPI: Optical Flow Pose Image for Action Recognition. Mathematics. 2023. vol. 11. no. 6. DOI: 10.3390/math11061451.
27. Xing Y., Dai Y., Hirota K., Jia A. Skeleton-based method for recognizing the campus violence. Proceedings of the 9th International Symposium on Computational Intelligence and Industrial Applications. 2020. pp. 19–20.
28. Cheriet M., Dentamaro V., Hamdan M., Impedovo D., Pirlo G. Multi-Speed Transformer Network for Neurodegenerative disease assessment and activity recognition. Computer Methods and Programs in Biomedicine. 2023. vol. 230(3). DOI: 10.1016/j.cmpb.2023.107344.
29. Alsaif O.I., Hasan S.Q., Maray A.H. Using skeleton model to recognize human gait gender. IAES International Journal of Artificial Intelligence. 2023. vol. 12. no. 2. pp. 974–983. DOI: 10.11591/ijai.v12.i2.pp974-983.
30. Yang W., Zhang J., Cai J., Xu Z. HybridNet: Integrating GCN and CNN for skeleton-based action recognition. Applied Intelligence. 2023. vol. 53. no. 1. pp. 574–585.
31. Xu J., Zhang Y., Zeng Q., Ren X., Cai X., Sun X. A skeleton based model for promoting coherence among sentences in narrative story generation. arXiv preprint arXiv:1808.06945, 2018.
32. Bai X., Ye L., Zhu J., Zhu L., Komura T. Skeleton filter: a self-symmetric filter for skeletonization in noisy text images. IEEE Transactions on Image Processing. 2019. vol. 29. pp. 1815–1826.
33. Faizullah S., Ayub M.S., Hussain S., Khan M.A. A Survey of OCR in Arabic Language: Applications, Techniques, and Challenges. Applied Sciences. 2023. vol. 13. no. 7. DOI: 10.3390/app13074584.
34. Abdo H.A., Abdu A., Manza R.R., Bawiskar S. An approach to analysis of Arabic text documents into text lines, words, and characters. Indonesian Journal of Electrical Engineering and Computer Science. 2022. vol. 26. no. 2. pp. 754–763.
35. Kiamouche O., Bennia A. Segmentation of Handwritten Arabic Words Using High Level Informative Scheme. 2nd International Conference on Advanced Electrical Engineering. 2022. 7 p. DOI: 10.1109/ICAEE53772.2022.9962062.
36. Arcelli C., Sanniti di Baja G., Serino L. Distance-driven skeletonization in voxel images. IEEE Trans. Pattern Anal. Mach. Intell. 2011. vol. 33. no. 4. pp. 709–720.
37. Bitter I., Kaufman A.E., Sato M. Penalized-distance volumetric skeleton algorithm, IEEE Trans. Vis. Comput. Graph. 2001. vol. 7. no. 3. pp. 195–206.
38. Lohou C., Bertrand G. A 3D 12-subiteration thinning algorithm based on P-simple points, Discrete Appl. Math. 2004. vol. 139. no. 1. pp. 171–195.
39. Lohou C., Bertrand G. A 3D 6-subiteration curve thinning algorithm based on P-simple points, Discrete Appl. Math. 2005. vol. 151. no. 1. pp. 198–228.
40. Németh G., Kardos P., Palágyi K., Thinning combined with iteration-by-iteration smoothing for 3D binary images, Graph. Models. 2011. vol. 73. pp. 335–345.
41. Ma J., Ren X., Tsviatkou V.Y., Kanapelka V.K. A novel fully parallel skeletonization algorithm. Pattern Analysis and Applications. 2022. vol. 25. 169–188. DOI: 10.1007/s10044-021-01039-y.
42. Perumalla S.R., Alekhya B., Raju MC. Digital Skeletonization for Bio-Medical Images. Proceedings of Third International Conference on Sustainable Expert Systems: ICSES. 2023. pp. 277–291.
43. Pinyoanuntapong E., Ali A., Wang P., Lee M., Chen C. GaitMixer: skeleton-based gait representation learning via wide-spectrum multi-axial mixer. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2023. DOI: 10.48550/arXiv.2210.15491.
44. Saha P.K., Borgefors G., di Baja G.S. A survey on skeletonization algorithms and their applications. Pattern recognition letters. 2016. vol. 76. pp. 3–12. DOI: 10.1016/j.patrec.2015.04.006.
45. Gittoes W., Botterill T., Green R. Quantitative analysis of skeletonisation algorithms for modelling of branches. Proceedings of Image and Vision Computing New Zealand. 2011. 6 p.
46. Abudalfa S., Mikki M. K-means algorithm with a novel distance measure. Turkish Journal of Electrical Engineering and Computer Sciences. 2013. vol. 21. no. 6. pp. 1665–1684.
2. Zhang Y, Sang L, Grzegorzek M, See J, Yang C. BlumNet: Graph component detection for object skeleton extraction. Proceedings of the 30th ACM International Conference on Multimedia. 2022. pp. 5527–5536.
3. Sanchez-Salvador J.L., Campano C., Lopez-Exposito P., Tarrés Q., Mutjé P., Delgado-Aguilar M., Monte M.C. Blanco A. Enhanced morphological characterization of cellulose nano/microfibers through image skeleton analysis. Nanomaterials. 2021. vol. 11. no. 8. DOI: 10.3390/nano11082077.
4. Zhang F., Chen X., Zhang X. Parallel thinning and skeletonization algorithm based on cellular automaton. Multimedia Tools and Applications. 2020. vol. 79. pp. 33215– 33232.
5. Kotsur D., Tereshchenko V. An optimized algorithm for computing the Voronoi skeleton. International Journal of Computing. 2020. vol. 19. no. 4. pp. 542–554.
6. Wang Y., Xu Y., Tsogkas S., Bai X., Dickinson S, Siddiqi K. Deepflux for skeletons in the wild. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019. pp. 5287–5296.
7. Cha S.H. Comprehensive survey on distance/similarity measures be-tween probability density functions. International Journal of Mathe-matical Models and Methods in Applied Sciences. 2007. vol. 1(4). pp. 300–307.
8. Yatziv L., Bartesaghi A., Sapiro G. O(N) implementation of the fast marching algorithm. Journal of computational physics. 2006. vol. 212. no. 2. pp. 393–399.
9. Wang H., Yu Y., Yuan Q. Application of Dijkstra algorithm in robot path-planning. Second international conference on mechanic automation and control engineering. 2011. pp. 1067–1069.
10. Gonzalez R.C., Woods R.E. Digital Image Processing, 3rd edition. Pearson Education, 2010. 185 p.
11. Song C., Pang Z., Jing X., Xiao C. Distance field guided L1-median skeleton extraction. The Visual Computer. 2018. vol. 34. pp. 243–55.
12. Langer M., Gabdulkhakova A., Kropatsch W.G. Non-centered Voronoi skeletons. Discrete Geometry for Computer Imagery: 21st IAPR International Conference. 2019. pp. 355–366.
13. Boudaoud L.B., Solaiman B., Tari A. A modified ZS thinning algorithm by a hybrid approach. The Visual Computer. 2018. vol. 34. pp. 689–706.
14. Morbiducci U., Mazzi V., Domanin M., De Nisco G., Vergara C., Steinman D.A., Gallo D. Wall shear stress topological skeleton independently predicts long-term restenosis after carotid bifurcation endarterectomy. Annals of biomedical engineering. 2020. vol. 48. pp. 2936–2949.
15. Breuß M., Bruckstein A.M., Kiselman C.O., Maragos P. Shape Analysis: Euclidean, Discrete and Algebraic Geometric Methods. Dagstuhl Reports. 2018. vol. 8. no. 10. pp. 87–103.
16. Zhang W., Wang X., Li X., Chen J. 3D skeletonization feature based computer-aided detection system for pulmonary nodules in CT datasets. Computers in biology and medicine. 2018. vol. 92. pp. 64–72.
17. Malik N.U., Sheikh U.U., Abu-Bakar S.A., Channa A. Multi-View Human Action Recognition Using Skeleton Based-FineKNN with Extraneous Frame Scrapping Technique. Sensors. 2023. vol. 23. no. 5. DOI: 10.3390/s23052745.
18. Ma J., Ren X., Li H., Li W., Tsviatkou V.Y., Boriskevich A.A. Noise-Against Skeleton Extraction Framework and Application on Hand Gesture Recognition. IEEE Access. 2023. vol. 11. pp. 9547–9559.
19. Bataineh B., Alqudah M.K. Evaluation of Skeletonization Methods for Document Images with Rotation States. Amity International Conference on Artificial Intelligence. 2019. pp. 424–428. DOI: 10.1109/AICAI.2019.8701352.
20. Nazarkevych M., Dmytruk S., Hrytsyk V., Vozna O., Kuza A., Shevchuk O., Voznyi Y., Maslanych I., Sheketa V. Evaluation of the effectiveness of different image skeletonization methods in biometric security systems. International Journal of Sensors Wireless Communications and Control. 2021. vol. 11. no. 5. pp. 542–552.
21. Perumalla S.R., Alekhya B., Raju M.C. Digital Skeletonization for Bio-Medical Images. Proceedings of Third International Conference on Sustainable Expert Systems. 2023. pp. 277–291.
22. Ramakrishnan V., Schönmehl R., Artinger A., Winter L., Böck H., Schreml S., Gürtler F., Daza J., Schmitt V.H., Mamilos A., Arbelaez P. 3D Visualization, Skeletonization and Branching Analysis of Blood Vessels in Angiogenesis. International Journal of Molecular Sciences. 2023. vol. 24. no. 9. DOI: 10.3390/ijms24097714.
23. Zhu R., Oda M., Hayashi Y., Kitasaka T., Misawa K., Fujiwara M., Mori K. A skeleton context-aware 3D fully convolutional network for abdominal artery segmentation. International Journal of Computer Assisted Radiology and Surgery. 2023. vol. 18. no. 3. pp. 461–472.
24. Feng Y., Chow L.S., Gowdh N.M., Ramli N., Tan L.K., Abdullah S., Tiang S.S. Gradient-based edge detection with skeletonization (GES) segmentation for magnetic resonance optic nerve images. Biomedical Signal Processing and Control. 2023. vol. 1. no. 80. DOI: 10.3390/ijms24097714.
25. Feng M., Meunier J. Skeleton Graph-Neural-Network-Based Human Action Recognition: A Survey. Sensors. 2022. vol. 22. no. 6. DOI: 10.3390/s22062091.
26. Chen D., Zhang T., Zhou P., Yan C., Li C. OFPI: Optical Flow Pose Image for Action Recognition. Mathematics. 2023. vol. 11. no. 6. DOI: 10.3390/math11061451.
27. Xing Y., Dai Y., Hirota K., Jia A. Skeleton-based method for recognizing the campus violence. Proceedings of the 9th International Symposium on Computational Intelligence and Industrial Applications. 2020. pp. 19–20.
28. Cheriet M., Dentamaro V., Hamdan M., Impedovo D., Pirlo G. Multi-Speed Transformer Network for Neurodegenerative disease assessment and activity recognition. Computer Methods and Programs in Biomedicine. 2023. vol. 230(3). DOI: 10.1016/j.cmpb.2023.107344.
29. Alsaif O.I., Hasan S.Q., Maray A.H. Using skeleton model to recognize human gait gender. IAES International Journal of Artificial Intelligence. 2023. vol. 12. no. 2. pp. 974–983. DOI: 10.11591/ijai.v12.i2.pp974-983.
30. Yang W., Zhang J., Cai J., Xu Z. HybridNet: Integrating GCN and CNN for skeleton-based action recognition. Applied Intelligence. 2023. vol. 53. no. 1. pp. 574–585.
31. Xu J., Zhang Y., Zeng Q., Ren X., Cai X., Sun X. A skeleton based model for promoting coherence among sentences in narrative story generation. arXiv preprint arXiv:1808.06945, 2018.
32. Bai X., Ye L., Zhu J., Zhu L., Komura T. Skeleton filter: a self-symmetric filter for skeletonization in noisy text images. IEEE Transactions on Image Processing. 2019. vol. 29. pp. 1815–1826.
33. Faizullah S., Ayub M.S., Hussain S., Khan M.A. A Survey of OCR in Arabic Language: Applications, Techniques, and Challenges. Applied Sciences. 2023. vol. 13. no. 7. DOI: 10.3390/app13074584.
34. Abdo H.A., Abdu A., Manza R.R., Bawiskar S. An approach to analysis of Arabic text documents into text lines, words, and characters. Indonesian Journal of Electrical Engineering and Computer Science. 2022. vol. 26. no. 2. pp. 754–763.
35. Kiamouche O., Bennia A. Segmentation of Handwritten Arabic Words Using High Level Informative Scheme. 2nd International Conference on Advanced Electrical Engineering. 2022. 7 p. DOI: 10.1109/ICAEE53772.2022.9962062.
36. Arcelli C., Sanniti di Baja G., Serino L. Distance-driven skeletonization in voxel images. IEEE Trans. Pattern Anal. Mach. Intell. 2011. vol. 33. no. 4. pp. 709–720.
37. Bitter I., Kaufman A.E., Sato M. Penalized-distance volumetric skeleton algorithm, IEEE Trans. Vis. Comput. Graph. 2001. vol. 7. no. 3. pp. 195–206.
38. Lohou C., Bertrand G. A 3D 12-subiteration thinning algorithm based on P-simple points, Discrete Appl. Math. 2004. vol. 139. no. 1. pp. 171–195.
39. Lohou C., Bertrand G. A 3D 6-subiteration curve thinning algorithm based on P-simple points, Discrete Appl. Math. 2005. vol. 151. no. 1. pp. 198–228.
40. Németh G., Kardos P., Palágyi K., Thinning combined with iteration-by-iteration smoothing for 3D binary images, Graph. Models. 2011. vol. 73. pp. 335–345.
41. Ma J., Ren X., Tsviatkou V.Y., Kanapelka V.K. A novel fully parallel skeletonization algorithm. Pattern Analysis and Applications. 2022. vol. 25. 169–188. DOI: 10.1007/s10044-021-01039-y.
42. Perumalla S.R., Alekhya B., Raju MC. Digital Skeletonization for Bio-Medical Images. Proceedings of Third International Conference on Sustainable Expert Systems: ICSES. 2023. pp. 277–291.
43. Pinyoanuntapong E., Ali A., Wang P., Lee M., Chen C. GaitMixer: skeleton-based gait representation learning via wide-spectrum multi-axial mixer. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2023. DOI: 10.48550/arXiv.2210.15491.
44. Saha P.K., Borgefors G., di Baja G.S. A survey on skeletonization algorithms and their applications. Pattern recognition letters. 2016. vol. 76. pp. 3–12. DOI: 10.1016/j.patrec.2015.04.006.
45. Gittoes W., Botterill T., Green R. Quantitative analysis of skeletonisation algorithms for modelling of branches. Proceedings of Image and Vision Computing New Zealand. 2011. 6 p.
46. Abudalfa S., Mikki M. K-means algorithm with a novel distance measure. Turkish Journal of Electrical Engineering and Computer Sciences. 2013. vol. 21. no. 6. pp. 1665–1684.
Опубликован
2023-09-25
Как цитировать
Абудальфа, Ш. И. (2023). Оценка методов скелетизации двумерных бинарных изображений. Информатика и автоматизация, 22(5), 1152-1176. https://doi.org/10.15622/ia.22.5.7
Раздел
Искусственный интеллект, инженерия данных и знаний
Copyright (c) Шади Ибрагим Абудальфа
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).