Скелетизация изображений на основе комбинации одно- и двухподытерационных моделей

Рассматривается задача скелетизации бинарных изображений. Скелетизация дает возможность представить бинарное изображение в виде множества тонких линий, взаимное расположение, размеры и форма которых адекватно описывают размеры, форму и ориентацию в пространстве соответствующих областей изображения. Высокое качество скелетов обеспечивают итерационные параллельные алгоритмы. Они могут реализовываться с использованием одной или нескольких подытераций. На каждой из них происходит удаление избыточных элементов, окрестности которых удовлетворяют определенным условиям. Для многих одноподытерационных алгоритмов характерно нарушение связности и формирование избыточных фрагментов скелета. Наиболее качественные скелеты формирует известный одноподытерационный алгоритм OPTA (One-Pass Thinning Algorithm), основанный на 18 бинарных масках, который, однако, чувствителен к контурному шуму и имеет высокую вычислительную сложность. Благодаря относительной простоте широкую известность получил двухподытерационный алгоритм Zhang – Suen (ZS), основанный на шести логических условиях, но он размывает диагональные линии толщиной 2 пиксела и удаляет области размером 2×2 пиксела. Оба алгоритма не обеспечивают достижение минимальной толщины линий скелета (многие неузловые элементы имеют более двух соседей). Для построения предельно тонких связанных скелетов бинарных изображений с низкой вычислительной сложностью предлагаются математическая модель и алгоритм OPCA (One-Pass Combination Algorithm) одноподытерационной скелетизации на основе комбинации и упрощения моделей одно- и двухподытерационной скелетизации. Данные модель и алгоритм позволяют повысить скорость скелетизации, восстановить исходное изображение по скелету, снизить избыточность связей элементов скелета.

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.