Discrete skeleton evolution
Discrete Skeleton Evolution (DSE) describes an iterative approach to reducing a morphological or topological skeleton.[1] It is a form of pruning in that it removes noisy or redundant branches (spurs) generated by the skeletonization process, while preserving information-rich "trunk" segments. The value assigned to individual branches varies from algorithm to algorithm,[1][2][3] with the general goal being to convey the features of interest of the original contour with a few carefully chosen lines. Usually, clarity for human vision (aka. the ability to "read" some features of the original shape from the skeleton) is valued as well.[3] DSE algorithms are distinguished by complex, recursive decision-making processes with high computational requirements. Pruning methods such as by structuring element (SE) convolution and the Hough transform are general purpose algorithms which quickly pass through an image and eliminate all branches shorter than a given threshold. DSE methods are most applicable when detail retention and contour reconstruction are valued.
Methodology
Pre-processing
Input images will typical contain more data than is necessary to generate an initial skeleton, and thus must be reduced in some way. Reducing the resolution, converting to grayscale, and then binary by masking or thresholding are common first steps. Noise removal may occur before and/or after converting an image to binary. Morphological operations such as closing, opening, and smoothing of the binary image may also be part of pre-processing. Ideally, the binarized contour should be as noise-free as possible before the skeleton is generated.
Skeletonization
DSE techniques may be applied to an existing skeleton or incorporated as part of the skeleton growing algorithm.[2][4] Suitable skeletons may be obtained using a variety of methods:[5]
- Thinning algorithms, such as the Grassfire transform
- Voronoi diagram
- Medial Axis Transform or Symmetry Axis Transform
- Distance Mapping
Significance Measures
DSE and related methods remove entire spurious branches while leaving the main trunk intact. The intended result is typically optimized for visual clarity and retention of information, such that the original contour can be reconstructed from the fully pruned skeleton. The value of various properties must be weighted by the application, and improving the efficiency is an ongoing topic of research in computer vision and image processing.[1][2][3][6] Some significance measures include:
- Discrete Bisector Function[2]
- Contour length[7]
- Bending Potential Ratio[4]
- Discrete Curve Evolution[3][6]
Iteration
Each branch is evaluated during a pass through the skeletonized image according to the specific algorithm being used. Low value branches are removed and the process is repeated until a desired threshold of simplicity is reached.
Reconstruction
If all points on the output skeleton are the center points of maximal disks of the image and the radius information is retained, a contour image can be reconstructed
Applications
Handwriting and text parsing
Variability in hand-written text is an ongoing challenge, simplification makes it somewhat easier for computer vision algorithms to make judgements about intended characters.[6]
Soft body classification (animals)
The maximal disks centered on the skeleton imply roughly spherical masses, the features of the extracted skeleton are relatively unchanged even as the soft body deforms or self-occludes. Skeleton information is one facet of determining whether two animals are the "same" some way, though it must usually be paired with another technique to effectively identify a target.[2]
Medical uses
Investigation of organs, tissue damage and deformation caused by disease.
References
- ↑ 1.0 1.1 1.2 Bai, Xiang; Latecki, Longin Jan (2007-08-27). "Discrete Skeleton Evolution". Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science. 4679. Springer, Berlin, Heidelberg. pp. 362–374. doi:10.1007/978-3-540-74198-5_28. ISBN 9783540741954.
- ↑ 2.0 2.1 2.2 2.3 2.4 Huichuan Duan; Jinling Wang; Xiyu Liu; Hong Liu (December 2008). "A scheme for morphological skeleton pruning". 2008 IEEE International Symposium on IT in Medicine and Education. IEEE. pp. 1112–1117. doi:10.1109/itme.2008.4744043. ISBN 9781424425105.
- ↑ 3.0 3.1 3.2 3.3 Bai, Xiang; Latecki, Longin; Liu, Wen-yu (March 2007). "Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution". IEEE Transactions on Pattern Analysis and Machine Intelligence 29 (3): 449–462. doi:10.1109/tpami.2007.59. ISSN 0162-8828. PMID 17224615.
- ↑ 4.0 4.1 Shen, Wei; Bai, Xiang; Hu, Rong; Wang, Hongyuan; Jan Latecki, Longin (February 2011). "Skeleton growing and pruning with bending potential ratio". Pattern Recognition 44 (2): 196–209. doi:10.1016/j.patcog.2010.08.021. ISSN 0031-3203. Bibcode: 2011PatRe..44..196S.
- ↑ "Part-Based Shape Similarity Project". http://www.dabi.temple.edu/~shape/partshape/structure/2.php.
- ↑ 6.0 6.1 6.2 Chacko, Binu P.; P, Babu Anto (February 2009). "Discrete Curve Evolution Based Skeleton Pruning for Character Recognition". 2009 Seventh International Conference on Advances in Pattern Recognition. IEEE. pp. 402–405. doi:10.1109/icapr.2009.63. ISBN 9780769535203.
- ↑ Duan, Huichuan; Wang, Jinling; Liu, Xiyu; Liu, Hong (October 2008). "A Skeleton Pruning Approach Using Contour Length as the Significance Measure". 2008 Third International Conference on Pervasive Computing and Applications. IEEE. pp. 360–364. doi:10.1109/icpca.2008.4783610. ISBN 9781424420209.
 |  |
