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.

 PDF

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

Keywords:
community detection, image segmentation.

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

References:

  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: áhttp://technomag.bmstu.ru/doc/759275.htmlñ. 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: journal@computeroptics.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20