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

Ключевые слова :
выделение сообществ на графах, сегментация изображения.

Цитирование:
Белим, С.В. Алгоритм сегментации изображений, основанный на поиске сообществ на графах / С.В. Белим, C.Б. Ларионов // Компьютерная оптика. – 2016. – Т. 40, № 6. – С. 904-910. – DOI: 10.18287/2412-6179-2016-40-6-904-910.

Литература:

1. Park, I.K. Color image retrieval using hybrid graph representation / I.K. Park, I.D. Yun, S.U. Lee // Image and Vision Computing. – 1999. – Vol. 17, Issue 7. – P. 465-474. – DOI: 10.1016/S0262-8856(98)00139-5.
2. Xu, B. EMR: A scalable graph-based ranking model for content-based image retrieval / B. Xu, J. Bu, C. Chen, C. Wang, D. Cai, X. He // IEEE Transactions on knowledge and data engineering. – 2015. – Vol. 27, Issue 1. – P. 102-114. – DOI: 10.1109/TKDE.2013.70.
3. Johnson, J. Image retrieval using scene graphs / J. Johnson, R. Krishna, M. Stark, L.-J. Li, D. Shamma, M. Bernstein, L. Fei-Fei // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. – 2015. – P. 3668-3678. – DOI: 10.1109/CVPR.2015.7298990.
4. Белим, С.В. Использование алгоритма кластеризации для разбиения изображения на односвязные области / С.В. Белим, П.Е. Кутлунин // Наука и образование: электронное научно-техническое издание. – 2015. – № 3. – URL: http://technomag.bmstu.ru/doc/759275.html. – DOI: 10.7463/0315.0759275.
5. Белим, С.В. Выделение контуров на изображениях с помощью алгоритма кластеризации / С.В. Белим, П.Е. Кутлунин // Компьютерная оптика. – 2015. – Т. 39, № 1. – С. 119-124. – DOI: 10.18287/0134-2452-2015-39-1-119-124.
6. Newman, M.E.J. Analysis of weighted networks / M.E. Newman // Physical Review E. – 2004. – Vol. 70, Issue 5 Pt 2. – 056131. – DOI: 10.1103/PhysRevE.70.056131.
7. Cuadros, O. Segmentation of large images with complex networks / O. Cuadros, G. Botelho, F. Rodrigues, J.B. Neto // SIBGRAPI '12, Proceedings of the 2012 25th SIBGRAPI Conference on Graphics, Patterns and Images. – 2012. – P. 24-31. – DOI: 10.1109/SIBGRAPI.2012.13.
8. Clauset, A. Finding community structure in very large networks / A. Clauset, M.E.J. Newman, C. Moore // Physical Review E. – 2004. – Vol. 70, Issue 6 Pt 2. – 066111. – DOI: 10.1103/PhysRevE.70.066111.
9. Raghavan, U.S. Near linear time algorithm to detect community structures in large-scale networks / U.S. Raghavan, R. Albert, S. Kumara // Physical Review E. – 2007. – Vol. 76(3 Part 2). – P. 036106. – DOI: 10.1103/Phys­RevE.76.036106.
10. Ren, X. Learning a classification model for segmentation / X. Ren, J. Malik // Proceedings on the Ninth IEEE International Conference on Computer Vision. – 2003. – Vol. 2. – P. 10-17. – DOI: 10.1109/ICCV.2003.1238308.
11. Levinshtein, A. TurboPixels: Fast superpixels using geometric flows / A. Levinshtein, A. Stere, K.N. Kutulakos, D.J. Fleet, S.J. Dickinson, K. Siddigi // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2009. – Vol. 31, Issue 12. – P. 2290-2297. – DOI: 10.1109/TPAMI.2009.96.
12. Achanta, R. Slic superpixels / R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Susstrunk // EPFL Technical Report 149300, June 2010.
13. Cigla, C. Efficient graph-based image segmentation via speeded-up turbo pixels / C. Cigla, A.A. Alatan // 17th International Conference on Image Processing. – 2010. – P. 3013-3016. – DOI: 10.1109/ICIP.2010.5653963.
14. Mourchid, Y. New image segmentation approach using community detection algorithms / Y. Mourchid, M.E. Has­souni, H.A. Cherif // International Journal of Computer Information Systems and Industrial Management Applications. – 2016. – Vol. 8. – P. 195-204.
15. Nair, R.S. Modularity based color image segmentation / R.S. Nair, K.V. Vineetha // IJIREEICE. – 2016. – Vol. 3, Special Issue 1. – P. 109-113.
16. Pourian, P. Weakly supervised graph based semantic segmentation by learning communities of image-parts / P. Pou­rian, S. Karthikeyan, B.S. Manjunath // The IEEE International Conference on Computer Vision (ICCV). – 2015. – P. 1359-1367. – DOI: 10.1109/ICCV.2015.160.
17. Li, S. Modularity-based image segmentation / S. Li, D.O. Wu // IEEE Transactions on Circuits and Systems for Video Technology. – 2015. – Vol. 25, Issue 4. – P. 570-581. – DOI: 10.1109/TCSVT.2014.2360028.
18. Verma, S. An increased modularity based contour detection / S. Verma, A. Chugh // International Journal of Computer Applications. – 2016. – Vol. 135, Issue 12. – P. 41-44. – DOI: 10.5120/ijca2016908588.
19. Browet, A. Community detection for hierarchical image segmentation / A. Browet, P.-A. Absil, P. Van Dooren // IWCIA'11 Proceedings of the 14th International Conference on Combinatorial Image Analysis. – 2011. – P. 358-371. – DOI: 10.1007/978-3-642-21073-0_32.
20. Newman, M.E.J. Mixing patterns in networks / M.E.J. Newman // Physical Review E. – 2003. – Vol. 67(2). – P. 026126. – DOI: 10.1103/PhysRevE.67.026126.
21. Fortunato, S. Community detection in graphs / S. Fortunato // Physics Reports. – 2010. – Vol. 486(3-5). – P. 75-174. – DOI: 10.1016/j.physrep.2009.11.002.

---

© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20