НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o281.pdf (949.25Кб)

УДК 004.93'14

Россия,  ОмГУ им. Ф.М. Достоевского

В статье предложена методика разбиения изображения на односвязные области по цвету. Пиксели исходного изображения представляются в виде точек пятимерного пространства, включающего в себя три цветовые координаты и две пространственные. Для устранения выделенных характеристик производится нормализация координат точек. Множеству точек сопоставляется полносвязный взвешенный граф. Вершинами графа служат точки пятимерного пространства. В качестве весов рёбер используется евклидово расстояние между точками. Для решения задачи кластеризации строится минимальное остовное дерево данного графа. Для выделения кластеров дерево разбивается на поддеревья путём удалением некоторых ребер. Каждое поддерево представляет односвязную область на изображении. С целью увеличения скорости работы и сокращения объема занимаемой памяти используется жадный алгоритм построения минимального остовного дерева для такого графа. Поиск удаляемых ребер осуществляется на графике зависимости длины присоединяемого ребра от порядкового номера его присоединения в жадном алгоритме. Искомые ребра определяются как максимумы на графике. Такой поиск основан на предположении, что переход к соседнему кластеру приводит к присоединению более длинного ребра по сравнению с ребрами в одном кластере. Разбиение на кластеры происходит итерационно. На каждом следующем шаге более крупные кластеры разбиваются на более мелкие. В результате чего может быть построена иерархия разбиения на кластеры. Проведён компьютерный эксперимент на искусственных и фотографических изображениях.
Предложенный метод свободен от недостатков, присущих самому распространенному методу  k-средних, и позволяет достаточно хорошо разделять области разного цвета с одинаковой интенсивностью. К тому же не требуется априорного определения количества кластеров. Вместо этого необходимо выбрать глубину разбиения, а количество кластеров будет определено автоматически. Также предложенный метод свободен от недостатков выделения контуров областей. Достаточно найти одну точку границы, чтобы отделить две области друг от друга.
Отличительной особенностью предложенного метода является естественное построение иерархии кластеров, которая позволяет выбирать уровень детализации. Данное свойство делает данный метод применимым в алгоритмах предобработки изображений для дальнейшего распознавания образов или поиска деталей на изображении.

1. Барталев С.А., Ховратович Т.С. Анализ возможностей применения методов сегментации спутниковых изображений для выявления изменений в лесах // Современные проблемы дистанционного зондирования Земли из космоса. 2011. Т. 8, № 1. С. 44-62.
2. Катаев С.Г., Кусков А.И. Проблемы исследования геофизических полей // Вестник ТГПУ. 2000. № 2 (15). С. 21-27.
3. Yingying Deng, Qingmin Liao. An accurate segmentation method for white blood cell images // Proc. 2002 IEEE International Symposium on Biomedical Imaging. IEEE, 2002. P. 245-248. DOI: 10.1109/ISBI.2002.1029239
4. Абламейко С.В., Недзьведь А.М., Белоцерковский А.М., Руцкая Е.А. Сегментация трехмерных изображений компьютерной томографии на основе глобально-локальной информации // Вестник БГУ. Сер. 1. Физика. Математика. Информатика. 2009. № 1. С. 58-64.
5. Ying Y., Tian G.Y. Defects area segmentation for X-ray images // Proceedings of the 12th Chinese Automation & Computing Society Conference. UK, Loughborough, England, 2006. P. 155-158.
6. Андрианов А.И. Локализация текста на изображениях сложных графических сцен // Современные проблемы науки и образования. 2013. № 3. Режим доступа:URL:http://www.science-education.ru/109-r9311 (дата обращения 01.01.2015).
7. Epshtein B., Ofek E., Wexler Y. Detecting Text in Natural Scenes with Stroke Width Transform // 23rd IEEE Conference on Computer Vision and Pattern Recognition (CVPR). San Francisco. IEEE, 2010. P. 2963-2970. DOI:10.1109/CVPR.2010.5540041
8. Нарасимхан Р. Автоматический анализ сложных изображений: сб. переводов: пер. с англ. М.: Мир, 1969. 310 с.
9. Rosenfeld A. Picture Processing by Computer. Academic Press, N.Y.; London, 1969.
10. Башкиров О.А., Рудометова С.Б., Чудинович Б.М. Выделение и счет связных областей на дискретном изображении // Автоматика и телемеханика. 1972. № 11. С. 84-91.
11. He L., Chao Y., Suzuki Y., Wu K. Fast connected-component labeling // Pattern Recognition. 2009. Vol. 42, no. 9. P. 1977-1987. DOI: 10.1016/j.patcog.2008.10.013
12. Pietikainen M., Maenpaa T., Ojala T. Multiresolution gray-scale and rotation in variant texture classification with local binary patterns // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. Vol. 24, iss. 7. P. 971-987. DOI: 10.1109/TPAMI.2002.1017623
13. Haralick R.M., Shapiro L.G. Image segmentation techniques // Computer Vision, Graphics, and Image Processing. 1985. Vol. 29, no. 1. P. 100-132. DOI: 10.1016/S0734-189X(85)90153-7
14. Fu K. S., Mu J. K. A survey on image segmentation // Pattern Recognition. 1981. Vol. 13, no.1. P. 3-16. DOI: 10.1016/0031-3203(81)90028-5
15. Wang J.Z., Li J., Wiederhold G. SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture Libraries // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. Vol. 23, no. 9. P. 947-963.
16. Wang J.Z., Du Y. Scalable Integrated Region-based Image Retrieval using IRM and Statistical Clustering // Proc. ACM/IEEE Joint Conference on Digital Libraries. Roanoke, VA. ACM, 2001. P. 268-277. DOI: 10.1145/379437.379679
17. Буй Т.Т.Ч., Спицын В.Г. Анализ методов выделения краев на цифровых изображениях // Доклады ТУСУР. 2010. № 2 (22), ч . 2. С . 221-223.
18. Senthilkumaran N.A., Rajesh R. Study on Edge Detection Methods for Image Segmentation // Proceedings of the International Conference on Mathematics and Computer Science (ICMCS-2009). Vol. 1. 2009. P. 255-259.
19. Jianping Fan, Yau D.K.Y., Elmagarmid A.K., Aref W.G. Automatic image segmentation by integrating color-edge extraction and seeded region growing // IEEE Transactions on Image Processing. 2001. Vol. 10, iss. 10. P. 1454-1466. DOI: 10.1109/83.951532
20. Calderero F., Marques F. Region Merging Techniques Using Information Theory Statistical Measures // IEEE Transactions on Image Processing. 2010. Vol. 19, no. 6. P. 1567-1586. DOI: 10.1109/TIP.2010.2043008
21. Reyad Y.A., El-Zaart A., Mathkour H., Al-Zuair M. Image Thresholding Using Split and Merge Techniques with Log-Normal Distribution // Canadian Journal on Image Processing and Computer Vision. 2010. Vol.1, no.3. P. 36-45.
22. Haris K., Efstratiadis S.N., Maglaveras N., Katsaggelos A.K. Hybrid Image Segmentation Using Watersheds and Fast Region Merging// IEEE Transactions on Image Processing. 1998. Vol. 7, no. 12. P. 1684-1699. DOI: 10.1109/83.730380
23. Baraldi A., Blonda P. A Survey of Fuzzy Clustering Algorithms for Pattern Recognition – Part I // IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics. 1999. Vol. 29, no. 6. P. 778-785. DOI: 10.1109/3477.809032
24. Veenman C. J., Reinders M. J. T., Backer E. A Maximum Variance Cluster Algorithm // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. Vol . 24, no . 9 . P . 1273-1280. DOI: 10.1109/TPAMI.2002.1033218
25. Башков Е.А., Вовк О.Л. Кластеризация изображений методом дендрограмм // Наукові праці Донецького національного технічного університету «Проблеми моделювання та автоматизації проектування динамічних систем». № 78. Донецк: ДНТУ, 2005. С . 152-161.