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 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.

1. Dinneen G. P. Programming pattern recognition. Western Joint Computer Conference, New York, 1–3 March 1955. New York, 1955, vol. 1, pp. 94–100.

2. Kirsch R. A, Cahn L., Ray C., Urban G. H. Experiments in processing pictorial information with a digital computer. Eastern Computer Conference, Washington, 9–13 December 1957. Washington, 1957, vol. 12, pp. 221–229.

3. Lam L., Lee S.-W., Suen C. Y. Thinning methodologies – a comprehensive survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, vol. 14, no. 9, pp. 869–885.

4. Holt C., Stewart A., Clint C., Perrott R. An improved parallel thinning algorithm. Communication ACM, 1987, vol. 30, pp. 156–160.

5. Manzanera A., Bernard T., Preteux F., Longuet B. Ultra-fast skeleton based on an isotropic fully parallel algorithm. Discrete Geometry for Computer Imagery, 1999, vol. 1568, pp. 313–324.

6. Bernard T. M., Manzanera A. Improved low complexity fully parallel thinning algorithm. Proceedings 10th International Conference on Image Analysis and Processing, Venice, Italy, 27–29 September 1999. Venice, 1999, pp. 215–220.

7. Chen C.-S., Tsai W.-H. A new fast one-pass thinning algorithm and its parallel hardware implementation. Pattern Recognition Letters, 1990, vol. 11, pp. 471–477.

8. Wu R.-Y., Tsai W.-H. A new one-pass parallel algorithm for binary images. Pattern Recognition Letters, 1992, vol. 13, pp. 715–723.

9. Deng W., Lyengar S. S, Brener N. E. A fast parallel thinning algorithm for the binary image skeletonization. International Journal of High Performance Computing Applications, 2000, vol. 14, pp. 65–81.

10. Stefanelli R., Rosenfeld A. Some parallel thinning algorithms for digital pictures. Journal of the ACM, 1971, vol. 18, pp. 255–264.

11. Chin R. T., Wan H. K., Stover D. L., Iverson R. D. A one-pass thinning algorithm and its parallel implementation. Computer Vision, Graphics, and Image Processing, 1987, vol. 40, pp. 30–40.

12. Harous, S., Elnagar A. Handwritten character-based parallel thinning algorithms: a comparative study. University of Sharjah Journal of Pure & Applied Sciences, 2009, vol. 6, no. 1, pp. 81–101.

13. Zhang T. Y., Suen C. Y. A fast parallel algorithm for thinning digital patterns. Communications of the ACM, 1984, vol. 27, no. 3, pp. 236–239.

14. Lu H. E., Wang P. S. P. A comment on "a fast parallel algorithm for thinning digital patterns". Communications of the ACM, 1986, vol. 29, no. 3, pp. 239–242.

15. Abdulla W. H., Saleh A. O. M., Morad A. H. A preprocessing algorithm for handwritten character recognition. Pattern Recognition Letters, 1988, vol. 7, no. 1, pp. 13–18.

16. Sossa J. H. An improved parallel algorithm for thinning digital patterns. Pattern Recognition Letters, 1989, vol. 10, pp. 77–80.

17. Guo Z., Hall R. W. Parallel thinning with two-subiteration algorithms. Communications of the ACM, 1989, vol. 32, no. 3, pp. 359–373.

18. Guo Z., Hall R. W. Fast fully parallel thinning algorithms. CVGIP: Image Understanding, 1992, vol. 55, no. 3, pp. 317–328.

19. Zhang Y. Y., Wang P. P. A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons. International Conference on Pattern Recognition, Vienna, Austria, 25–29 August 1996. Vienna, 1996, vol. 4, pp. 457–461.

20. Kundu M. K., Chaudhuri B. B., Majumder D. D. A parallel graytone thinning algorithm (PGTA). Pattern Recognition Letters, 1991, vol. 12, no. 8, pp. 491–494.

21. Kwon J.-S., Gi J.-W., Kang E.-K. An enhanced thinning algorithm using parallel processing. Proceeding of the International Conference on Image Processing, Thessaloniki, Greece, 7–10 October 2001. Thessaloniki, 2001, pp. 752–755.

22. Jang B. K., Chin R. T. One-pass parallel: analysis, properties, and quantitative evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, vol. 14, pp. 1129–1140.

23. Boudaoud L. B., Sider A., Tari A. A new thinning algorithm for binary images. 3rd International Conference on Control, Engineering & Information Technology, Tlemcen, Algeria, 25–27 May 2015. Tlemcen, 2015, pp. 1–6.

24. Sebastian T. B., Klein P. N., Kimia B. B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, vol. 26, no. 5, pp. 550–571.