An Efficient Agglomerative Algorithm Based On Modularity Optimization to Find Homogeneous Regions in Image

Authors

  • Vikalp Mishra  Department of Computer Science, Naraina Group of Institutions, Kanpur, Uttar Pradesh, India

Keywords:

Homogeneous Regions, Modularity Optimization, Data Set, Object-Level Segmentation, Image Segmentation, Community Aggregation, SSDS, HoS, VOI, BSDS500

Abstract

To address the problem of segmenting an image into sizeable homogeneous regions, this paper proposes an efficient agglomerative algorithm based on modularity optimization. Given an over-segmented image that consists of many small regions, our algorithm automatically merges those neighboring regions that produce the largest increase in modularity index. When the modularity of the segmented image is maximized, the algorithm stops merging and produces the final segmented image. To preserve the repetitive patterns in a homogeneous region, we propose a feature based on the histogram of states of image gradients, and use it together with the color feature to characterize the similarity of two regions. By constructing the similarity matrix in an adaptive manner, the over-segmentation problem can be effectively avoided. Our algorithm is tested on the publicly available Berkeley Segmentation Data Set as well as the Semantic Segmentation Data Set and compared with other popular algorithms. Experimental results have demonstrated that our algorithm produces sizable segmentation, preserves repetitive patterns with appealing time complexity, and achieves object-level segmentation to some extent.

References

  1. M. Dabbaghha, M. Dashtbayazi, S. Marjani, M. Sabaghi, “Increased Accuracy in Image Segmentation Considering the Modular Method Based on Texture Characteristics and Super Pixel,” Journal of Electrical and Electronic Engineering 2016; 4(3): 63-67.(Base paper)
  2. J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888–905, 2000.
  3. D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 7, pp. 1271–1283, 2010.
  4. P. Felzenszwalb and D. Huttenlocher, “Efficient graph-based image segmentation,” International Journal of Computer Vision, vol. 59, no. 2, pp. 167–181, 2004.
  5. P. Arbel´aez, M. Maire, C. Fowlkes, and J. Malik, “From contours to regions: An empirical evaluation,” in IEEE Conference on Computer Vision and Pattern Recognition, CVPR. IEEE, 2009, pp. 2294–2301.
  6. S. Rao, H. Mobahi, A. Yang, S. Sastry, and Y. Ma, “Natural image segmentation with adaptive texture and boundary encoding,” Asian Conference on Computer Vision, ACCV., pp. 135–146, 2010.
  7. P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “Contour detection and hierarchical image segmentation,” IEEE Transactions on Pattern Analysis and Machine  Intelligence, vol. 33, no. 5, pp. 898–916, 2011.
  8. H. Zhu, J. Zheng, J. Cai, and N. M. Thalmann, “Object-level image segmentation using low level cues,” IEEE Transactions on Image Processing, 2013.
  9. M. Wertheimer, “Laws of organization in perceptual forms,” A Source Book of Gestalt Psychology, pp. 71–88, 1938.
  10. D. D. Hoffman and M. Singh, “Salience of visual parts,” Cognition, vol. 63, no. 1, pp. 29–78, 1997.
  11. T. Cour, F. Benezit, and J. Shi, “Spectral segmentation with multiscale graph decomposition,” in IEEE Conference on Computer Vision and Pattern Recognition, CVPR., vol. 2. IEEE, 2005, pp. 1124–1131.
  12. L. Grady and E. L. Schwartz, “Isoperimetric graph partitioning for image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 3, pp. 469–475, 2006.
  13. J. Wang, Y. Jia, X.-S. Hua, C. Zhang, and L. Quan, “Normalized tree partitioning for image segmentation,” in IEEE Conference on Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE, 2008, pp. 1–8.
  14. C. Couprie, L. Grady, L. Najman, and H. Talbot, “Power watershed: A unifying graph-based optimization framework,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 7, pp. 1384– 1399, 2011.
  15. L. Vincent and P. Soille, “Watersheds in digital spaces: an efficient algorithm based on immersion simulations,” IEEE transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583–598, 1991.
  16. V. Grau, A. Mewes, M. Alcaniz, R. Kikinis, and S. K. Warfield, “Improved watershed transform for medical image segmentation using prior information,” IEEE Transactions on Medical Imaging, vol. 23, no. 4, pp. 447–458, 2004.
  17. X.-C. Tai, E. Hodneland, J. Weickert, N. V. Bukoreshtliev, A. Lundervold, and H.-H. Gerdes, “Level set methods for watershed image segmentation,” in Scale Space and Variational Methods in Computer Vision. Springer, 2007, pp. 178–190.
  18. V. Osma-Ruiz, J. I. Godino-Llorente, N. S´aenz-Lech´on, and P. G´omez-Vilda, “An improved watershed algorithm based on efficient computation of shortest paths,” Pattern Recognition, vol. 40, no. 3, pp. 1078–1090, 2007.
  19. A. Yang, J. Wright, Y. Ma, and S. Sastry, “Unsupervised segmentation of natural images via lossy data compression,” Computer Vision and Image Understanding, vol. 110, no. 2, pp. 212–225, 2008.
  20. M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, vol. 1, no. 4, pp. 321–331, 1988.
  21. C. Xu and J. L. Prince, “Snakes, shapes, and gradient vector flow,” IEEE Transactions on Image Processing, vol. 7, no. 3, pp. 359–369, 1998.
  22. “Generalized gradient vector flow external forces for active contours,” Signal processing, vol. 71, no. 2, pp. 131–139, 1998.
  23. T. F. Chan and L. A. Vese, “Active contours without edges,” IEEE Transactions on Image Processing, vol. 10, no. 2, pp. 266–277, 2001.
  24. B. Li and S. T. Acton, “Active contour external force using vector field convolution for image segmentation,” IEEE Transactions on Image Processing, vol. 16, no. 8, pp. 2096–2106, 2007.
  25. M. Newman, “Analysis of weighted networks,” Physical Review E, vol. 70, no. 5, p. 056131, 2004.
  26. W. Li, “Modularity segmentation,” in Neural Information Processing Springer, 2013, pp. 100–107.
  27. A. Browet, P.-A. Absil, and P. Van Dooren, “Community detection for hierarchical image segmentation,” in Combinatorial Image Analysis. Springer, 2011, pp. 358–371.
  28. H. Li, J. Cai, T. N. A. Nguyen, and J. Zheng, “A benchmark for semantic image segmentation,” in IEEE International Conference on Multimedia & Expo, ICME., 2013.
  29. V. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008.

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2017-06-30

Issue

Volume 2, Issue 3, May-June-2017

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Vikalp Mishra, " An Efficient Agglomerative Algorithm Based On Modularity Optimization to Find Homogeneous Regions in Image, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 3, pp.572-576, May-June-2017.