Image skeletonization based on combination of one- and two-sub-iterations models
This paper is focused on the field of the skeletonization of the binary image. Skeletonization makes it possible to represent a binary image in the form of many thin lines, the relative position, sizes and shape of which adequately describe the size, shape and orientation in space of the correspondi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
2020-06-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1051 |
| _version_ | 1797877181424074752 |
|---|---|
| author | J. Ma V. Yu. Tsviatkou V. K. Kanapelka |
| author_facet | J. Ma V. Yu. Tsviatkou V. K. Kanapelka |
| author_sort | J. Ma |
| collection | DOAJ |
| description | This paper is focused on the field of the skeletonization of the binary image. Skeletonization makes it possible to represent a binary image in the form of many thin lines, the relative position, sizes and shape of which adequately describe the size, shape and orientation in space of the corresponding image areas. Skeletonization has many variety methods. Iterative parallel algorithms provide high quality skeletons. They can be implemented using one or more sub-iterations. In each iteration, redundant pixels, the neighborhoods of which meet certain conditions, are removed layer by layer along the contour and finally they leave only the skeleton. Many one-sub-iterations algorithms are characterized by a breakdown in connectivity and the formation of excess skeleton fragments. The highest-quality skeletons are formed by the well-known single-iteration OPTA algorithm, which based on 18 binary masks, but it is sensitive to contour noise and has a high computational complexity. The Zhang and Suen two-iteration algorithm (ZS), which is based on 6 logical conditions, is widely used due to its relative simplicity. But it suffers from the problem of the blurs of the diagonal lines with a thickness of 2 pixels and the lost of the square which size is 2×2 pixels. Besides, both algorithms mentioned above do not achieve the unit pixel thickness of the skeleton lines (many non-node pixels have more than two neighbors). Mathematical model and OPCA (One-Pass Combination Algorithm) algorithm which is based on a combination and simplification of single-iterative OPTA and two-iterative ZS are proposed for constructing extremely thin bound skeletons of binary images with low computational complexity. These model and algorithm also made it possible to accelerate the speed of skeletonization, to enhance recoverability of the original image on the skeleton and to reduce the redundancy of the bonds of the skeleton elements. |
| first_indexed | 2024-04-10T02:14:11Z |
| format | Article |
| id | doaj.art-a2e7b92c646b43e08f6e2f3f5889ae6a |
| institution | Directory Open Access Journal |
| issn | 1816-0301 |
| language | Russian |
| last_indexed | 2024-04-10T02:14:11Z |
| publishDate | 2020-06-01 |
| publisher | The United Institute of Informatics Problems of the National Academy of Sciences of Belarus |
| record_format | Article |
| series | Informatika |
| spelling | doaj.art-a2e7b92c646b43e08f6e2f3f5889ae6a2023-03-13T08:32:24ZrusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusInformatika1816-03012020-06-01172253510.37661/1816-0301-2020-17-2-25-35926Image skeletonization based on combination of one- and two-sub-iterations modelsJ. Ma0V. Yu. Tsviatkou1V. K. Kanapelka2Belarusian State University of Informatics and RadioelectronicsBelarusian State University of Informatics and RadioelectronicsBelarusian State University of Informatics and RadioelectronicsThis paper is focused on the field of the skeletonization of the binary image. Skeletonization makes it possible to represent a binary image in the form of many thin lines, the relative position, sizes and shape of which adequately describe the size, shape and orientation in space of the corresponding image areas. Skeletonization has many variety methods. Iterative parallel algorithms provide high quality skeletons. They can be implemented using one or more sub-iterations. In each iteration, redundant pixels, the neighborhoods of which meet certain conditions, are removed layer by layer along the contour and finally they leave only the skeleton. Many one-sub-iterations algorithms are characterized by a breakdown in connectivity and the formation of excess skeleton fragments. The highest-quality skeletons are formed by the well-known single-iteration OPTA algorithm, which based on 18 binary masks, but it is sensitive to contour noise and has a high computational complexity. The Zhang and Suen two-iteration algorithm (ZS), which is based on 6 logical conditions, is widely used due to its relative simplicity. But it suffers from the problem of the blurs of the diagonal lines with a thickness of 2 pixels and the lost of the square which size is 2×2 pixels. Besides, both algorithms mentioned above do not achieve the unit pixel thickness of the skeleton lines (many non-node pixels have more than two neighbors). Mathematical model and OPCA (One-Pass Combination Algorithm) algorithm which is based on a combination and simplification of single-iterative OPTA and two-iterative ZS are proposed for constructing extremely thin bound skeletons of binary images with low computational complexity. These model and algorithm also made it possible to accelerate the speed of skeletonization, to enhance recoverability of the original image on the skeleton and to reduce the redundancy of the bonds of the skeleton elements.https://inf.grid.by/jour/article/view/1051image skeletonizationalgorithm optaalgorithm zhang – suensingle-iteration skeletonizationdouble-iteration skeletonization |
| spellingShingle | J. Ma V. Yu. Tsviatkou V. K. Kanapelka Image skeletonization based on combination of one- and two-sub-iterations models Informatika image skeletonization algorithm opta algorithm zhang – suen single-iteration skeletonization double-iteration skeletonization |
| title | Image skeletonization based on combination of one- and two-sub-iterations models |
| title_full | Image skeletonization based on combination of one- and two-sub-iterations models |
| title_fullStr | Image skeletonization based on combination of one- and two-sub-iterations models |
| title_full_unstemmed | Image skeletonization based on combination of one- and two-sub-iterations models |
| title_short | Image skeletonization based on combination of one- and two-sub-iterations models |
| title_sort | image skeletonization based on combination of one and two sub iterations models |
| topic | image skeletonization algorithm opta algorithm zhang – suen single-iteration skeletonization double-iteration skeletonization |
| url | https://inf.grid.by/jour/article/view/1051 |
| work_keys_str_mv | AT jma imageskeletonizationbasedoncombinationofoneandtwosubiterationsmodels AT vyutsviatkou imageskeletonizationbasedoncombinationofoneandtwosubiterationsmodels AT vkkanapelka imageskeletonizationbasedoncombinationofoneandtwosubiterationsmodels |