Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Segmentation of large images based on super-pixels and community detection in graphs

© The Institution of Engineering and Technology
Received 03/02/2016, Accepted 12/02/2017, Revised 24/01/2017, Published 16/03/2017

Image segmentation has many applications which range from machine learning to medical diagnosis. In this study, the authors propose a framework for the segmentation of images based on super-pixels and algorithms for community identification in graphs. The super-pixel pre-segmentation step reduces the number of nodes in the graph, rendering the method the ability to process large images. Moreover, community detection algorithms provide more accurate segmentation than traditional approaches based on spectral graph partition. The authors also compared their method with two algorithms: (i) the graph-based approach by Felzenszwalb and Huttenlocher and (ii) the contour-based method by Arbelaez. Results have shown that their method provides more precise segmentation and is faster than both of them.

Inspec keywords: object detection; graph theory; image segmentation

Other keywords: graph-based approach; spectral graph partition; contour-based method; super-pixel pre-segmentation step; medical diagnosis; image segmentation; machine learning; community detection algorithms

Subjects: Combinatorial mathematics; Computer vision and image processing techniques; Combinatorial mathematics; Optical, image and video signal processing

References

    1. 1)
      • 20. Wu, Z., Leahy, R.: ‘An optimal graph theoretic approach to data clustering: theory and its application to image segmentation’, IEEE Trans. Pattern Anal. Mach. Intell., 1993, 15, (11), pp. 1101–1113.
    2. 2)
      • 37. Finkel, R.A., Bentley, J.L.: ‘Quad trees a data structure for retrieval on composite keys’, Acta Inform., 1974, 4, (1), pp. 1–9.
    3. 3)
      • 36. Martin, D., Fowlkes, C., Tal, D., et al: ‘A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics’. Eighth IEEE Int. Conf. on Computer Vision, 2001, vol. 2, pp. 416–423.
    4. 4)
      • 1. Fu, K.S., Mui, J.K.: ‘A survey on image segmentation’, Pattern Recongnit., 1981, 13, (1), pp. 3–16.
    5. 5)
      • 6. Parker, J.R.: ‘Algorithms for image processing and computer vision’ (Wiley. com, 2010).
    6. 6)
      • 26. Cigla, C., Alatan, A.A.: ‘Efficient graph-based image segmentation via speeded-up turbo pixels’. 17th IEEE Int. Conf. on Image Processing, 2010, pp. 3013–3016.
    7. 7)
      • 34. Jain, A.K.: ‘Fundamentals of digital image processing’ (Prentice-Hall, Inc., 1989).
    8. 8)
      • 5. da Fontoura Costa, L., Cesar, R.M.Jr.: ‘Shape analysis and classification: theory and practice’ (CRC Press, Inc., 2000).
    9. 9)
      • 4. Zhang, H., Fritts, J.E., Goldman, S.A.: ‘Image segmentation evaluation: a survey of unsupervised methods’, Comput. Vis. Image Underst., 2008, 110, (2), pp. 260–280.
    10. 10)
      • 23. Wang, S., Siskind, J.M.: ‘Image segmentation with minimum mean cut’. Eighth IEEE Int. Conf. on Computer Vision, 2001, ICCV 2001, Proc., 2001, vol. 1, pp. 517–524.
    11. 11)
      • 8. Jain, A.K., Narasimha Murty, M., Flynn, P.J.: ‘Data clustering: a review’, ACM Comput. Surv., 1999, 31, (3), pp. 264–323.
    12. 12)
      • 2. Haralick, R.M., Shapiro, L.G.: ‘Image segmentation techniques’, Comput. Vis. Graph. Image Process., 1985, 29, (1), pp. 100–132.
    13. 13)
      • 22. Shi, J., Malik, J.: ‘Normalized cuts and image segmentation’, IEEE Trans. Pattern Anal. Mach. Intell., 2000, 22, (8), pp. 888–905.
    14. 14)
      • 3. Pal, N.R., Pal, S.K.: ‘A review on image segmentations techniques’, Pattern Recognit., 1993, 26, (9), pp. 1277–1294.
    15. 15)
      • 29. Girvan, M., Newman, M.E.J.: ‘Community structure in social and biological networks’, Proc. Natl. Acad. Sci., 2002, 99, (12), pp. 7821–7826.
    16. 16)
      • 12. Newman, M.E.J.: ‘Networks: an introduction’ (Oxford University Press, 2010).
    17. 17)
      • 27. Achanta, R., Shaji, A., Smith, K., et al: ‘SLIC superpixels’. Technical report, 2010.
    18. 18)
      • 9. Granell, C., Gómez, S., Arenas, A.: ‘Mesoscopic analysis of networks: applications to exploratory analysis and data clustering’, Chaos, Interdiscip. J. Nonlinear Sci., 2011, 21, (1), pp. 016102–016102.
    19. 19)
      • 11. Zanin, M., Papo, D., Sousa, P.A., et al: ‘Combining complex networks and data mining: why and how’, Phys. Rep., 2016, 635, pp. 1–44.
    20. 20)
      • 21. Cox, I.J., Rao, S.B., Zhong, Y.: ‘Ratio regions: a technique for image segmentation’. Proc. of the 13th Int. Conf. on Pattern Recognition, 1996, vol. 2, pp. 557–564.
    21. 21)
      • 16. Clauset, A., Newman, M.E.J., Moore, C.: ‘Finding community structure in very large networks’, Phys. Rev. E, 2004, 70, (6), p. 066111.
    22. 22)
      • 35. Csardi, G., Nepusz, T.: ‘The igraph software package for complex network research’, Int. J. Complex Syst., 2006, 1695, pp. 1–9.
    23. 23)
      • 25. Levinshtein, A., Stere, A., Kutulakos, K.N., et al: ‘Turbopixels: fast superpixels using geometric flows’, IEEE Trans. Pattern Anal. Mach. Intell., 2009, 31, (12), pp. 2290–2297.
    24. 24)
      • 15. Fortunato, S.: ‘Community detection in graphs’, Phys. Rep., 2010, 486, (3), pp. 75–174.
    25. 25)
      • 19. Howe, D., Costanzo, M., Fey, P., et al: ‘Big data: the future of biocuration’, Nature, 2008, 455, (7209), pp. 47–50.
    26. 26)
      • 14. da Fontoura Costa, L., Oliveira, O.N.Jr., Travieso, G., et al: ‘Analyzing and modeling real-world phenomena with complex networks: a survey of applications’, Adv. Phys., 2011, 60, (3), pp. 329–412.
    27. 27)
      • 7. Theodoridis, S., Koutroumbas, K.: ‘Pattern recognition’, 2003.
    28. 28)
      • 13. Fortunato, S., Hric, D.: ‘Community detection in networks: a user guide’, Phys. Rep., 2016, 659, (11), pp. 1–44.
    29. 29)
      • 32. Linares, O.C., Botelho, G., Rodrigues, F., et al: ‘An adjustable error measure for image segmentation evaluation’. 28th SIBGRAPI Conf. on Graphics, Patterns and Images (SIBGRAPI), 2015, August 2015, pp. 80–86.
    30. 30)
      • 24. Ren, X., Malik, J.: ‘Learning a classification model for segmentation’. Ninth IEEE Int. Conf. on Computer Vision, 2003, Proc., 2003, pp. 10–17.
    31. 31)
      • 28. Achanta, R., Shaji, A., Smith, K., et al: ‘SLIC superpixels compared to state-of-the-art superpixel methods’, IEEE Trans. Pattern Anal. Mach. Intell., 2012, 34, (11), pp. 2274–2282.
    32. 32)
      • 31. Arbelaez, P., Maire, M., Fowlkes, C., et al: ‘From contours to regions: an empirical evaluation’. IEEE Conf. on Computer Vision and Pattern Recognition, 2009, pp. 2294–2301.
    33. 33)
      • 30. Newman, M.E.J.: ‘Fast algorithm for detecting community structure in networks’, Phys. Rev. E, 2004, 69, (6), p. 066133.
    34. 34)
      • 17. Felzenszwalb, P.F., Huttenlocher, D.P.: ‘Efficient graph-based image segmentation’, Int. J. Comput. Vis., 2004, 59, (2), pp. 167–181.
    35. 35)
      • 18. Arbelaez, P., Maire, M., Fowlkes, C., et al: ‘Contour detection and hierarchical image segmentation’, IEEE Trans. Pattern Anal. Mach. Intell., 2011, 33, (5), pp. 898–916.
    36. 36)
      • 33. Cuadros, O., Botelho, G., Rodrigues, F., et al: ‘Segmentation of large images with complex networks’. 25th Conf. on Graphics, Patterns and Images (SIBGRAPI), 2012, pp. 24–31.
    37. 37)
      • 10. de Arruda, G.F., da Fontoura Costa, L., Rodrigues, F.A.: ‘A complex networks approach for data clustering’, Phys. A, Stat. Mech. Appl., 2011, 391, (23), pp. 6174–6183.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2016.0072
Loading

Related content

content/journals/10.1049/iet-ipr.2016.0072
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address