An algorithm of image segmentation based on community detection in graphs
S.V. Belim, S.B. Larionov


F.M. Dostoevskiy Omsk State University, Omsk, Russia

Full text of article: Russian language.


This article suggests an algorithm of image segmentation based on the community detection in graphs. The image is represented as a non-oriented weighted graph on which the community detection is carried out. Each pixel of the image is associated with a graph vertex. Only adjacent pixels are connected by edges. The weight of the edge is defined by subtracting the intensities of three color components of pixels. A Newman modularity function is used to check the quality of the graph partition into sub-graphs. It is suggested that a greedy algorithm should be applied to solving the image segmentation problem. Each community corresponds to a segment in the image. A computer experiment was carried out. The influence of the algorithm parameter to the segmentation results was revealed. The proposed algorithm was shown to be insensitive to random impulse noise.

community detection, image segmentation.

Belim SV, Larionov SB. An algorithm of image segmentation based on community detection in graphs. Computer Optics 2016; 40(6): 904-910. DOI: 10.18287/2412-6179-2016-40-6-904-910.


  1. Park IK, Yun ID, Lee SU. Color image retrieval using hybrid graph representation. Image and Vision Computing 1999; 17(7): 465-474. DOI: 10.1016/S0262-8856(98)00139-5.
  2. Xu B, Bu J, Chen C, Wang C, Cai D, He X. EMR: A scalable graph-based ranking model for content-based image retrieval. IEEE Transactions on knowledge and data engineering 2015; 27(1): 102-114. DOI: 10.1109/TKDE.2013.70.
  3. Johnson J, Krishna R, Stark M, Li L-J, Shamma D, Bernstein M, Fei-Fei L. Image retrieval using scene graphs. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition 2015: 3668-3678. DOI: 10.1109/CVPR.2015.7298990.
  4. Belim SV, Kutlunin PE. Usage of clustering algorithm to segment image into simply connected domains. Science & Education BMSTU 2015; 15(3). Source: áñ. DOI: 10.7463/0315.0759275.
  5. Belim SV, Kutlunin PE. Boundary extraction in images using a clustering algorithm. Computer Optics 2015; 39(1): 119-124. DOI: 10.18287/0134-2452-2015-39-1-119-124.
  6. Newman MEJ. Analysis of weighted networks. Physical Review E 2004; 70(5 Pt 2): 056131. DOI: 10.1103/Phys­RevE.70.056131.
  7. Cuadros O, Botelho G, Rodrigues F, Neto JB. Segmentation of large images with complex networks. SIBGRAPI 2012: 24-31. DOI: 10.1109/SIBGRAPI.2012.13.
  8. Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physical Review E 2004; 70(6 Pt 2): 066111. DOI: 10.1103/PhysRevE.70.066111.
  9. Raghavan US, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Phisical Review E 2007; 76(3 Pt 2): 036106.
  10. Ren X, Malik J. Learning a classification model for segmentation. ICCV 2003; 2: 10-17. DOI: 10.1109/ICCV.2003.1238308.
  11. Levinshtein A, Stere A, Kutulakos KN, Fleet DJ, Dickinson SJ, Siddigi K. TurboPixels: Fast superpixels using geometric flows. IEEE Transactions on Pattern Analysis and Machine Intelligence 2009; 31(12): 2290-2297. DOI: 10.1109/TPAMI.2009.96.
  12. Achanta R, Shaji A, Smith K, Lucchi A, Fua P, Susstrunk S. Slic superpixels. EPFL Technical Report 149300, June 2010.
  13. Cigla C, Alatan AA. Efficient graph-based image segmentation via speeded-up turbo pixels. ICIP '17 2010: 3013-3016. DOI: 10.1109/ICIP.2010.5653963.
  14. Mourchid Y, Hassouni ME, Cherif HA. New Image Segmentation Approach using Community Detection Algorithms. International Journal of Computer Information Systems and Industrial Management Applications 2016; 8: 195-204.
  15. Nair RS, Vineetha KV. modularity based color image Segmentation. IJIREEICE 2016; 3(Spec 1): 109-113.
  16. Pourian P, Karthikeyan S, Manjunath BS. Weakly supervised graph based semantic segmentation by learning communities of image-parts. The IEEE International Conference on Computer Vision (ICCV) 2015: 1359-1367. DOI: 10.1109/ICCV.2015.160.
  17. Li S, Wu DO. Modularity-based image segmentation. IEEE Transactions on Circuits and Systems for Video Technology 2015; 25(4): 570-581. DOI: 10.1109/TCSVT.2014.2360028.
  18. Verma S, Chugh A. An increased modularity based contour detection. International Journal of Computer Applications 2016; 135(12): 41-44. DOI: 10.5120/ijca2016908588.
  19. Browet A, Absil P-A, Van Dooren P. Community Detection for hierarchical image segmentation. IWCIA'11 2011: 358-371. DOI: 10.1007/978-3-642-21073-0_32.
  20. Newman MEJ. Mixing patterns in networks. Phys Rev E 2003; 67(2): 026126. DOI: 10.1103/PhysRevE.67.026126.
  21. Fortunato S. Community detection in graphs. Physics Reports 2010; 486(3-5): 75-174. DOI: 10.1016/j.phys­rep.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:; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20