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

Authors(1) :-Vikalp Mishra

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.

Authors and Affiliations

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

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

  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.

Publication Details

Published in : Volume 2 | Issue 3 | May-June 2017
Date of Publication : 2017-06-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 572-576
Manuscript Number : CSEIT1723205
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

Vikalp Mishra, "An Efficient Agglomerative Algorithm Based On Modularity Optimization to Find Homogeneous Regions in Image", International 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.
Journal URL : http://ijsrcseit.com/CSEIT1723205

Article Preview

Follow Us

Contact Us