Image Segmentation Based on Graph Theoretical Approach to Improve the Quality of Image Segmentation

Authors: Deepthi Narayan, Srikanta Murthy K., G. Hemantha Kumar

Abstract:

Graph based image segmentation techniques are considered to be one of the most efficient segmentation techniques which are mainly used as time & space efficient methods for real time applications. How ever, there is need to focus on improving the quality of segmented images obtained from the earlier graph based methods. This paper proposes an improvement to the graph based image segmentation methods already described in the literature. We contribute to the existing method by proposing the use of a weighted Euclidean distance to calculate the edge weight which is the key element in building the graph. We also propose a slight modification of the segmentation method already described in the literature, which results in selection of more prominent edges in the graph. The experimental results show the improvement in the segmentation quality as compared to the methods that already exist, with a slight compromise in efficiency.

Keywords: Graph based image segmentation, threshold, Weighted Euclidean distance.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333574

References:

[1] P.F. Felzenszwalb and D.P. Huttenlocher, "Efficient Graph-Based Image Segmentation," International Journal of Computer Vision, Vo.59, No.2, 2004.
[2] Ming Zhang, Reda Alhajj, "Improving the Graph-Based Image Segmentation Method "Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'O6), 2006, IEEE.
[3] Thiadmer Riemersma, Color metric, available at http://www.compuphase.com/cmetric.htm
[4] S.Arya and D.M. Mount, "Approximate nearest neighbor searching", Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 271-280, 1993.
[5] J. Shi and J. Malik, "Normalized Cuts and Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence, Vo1.22, No.8, pp.888- 905, 2000.
[6] C.T. Zahn, "Graph-theoretic methods for detecting and describing gestalt clusters", IEEE Transactions on Computing, vol 20, pages 68-86, 1971.
[7] P.F. Felzenszwalb and D.P. Huttenlocher," Image segmentation using local variation" Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pages 98-104, 1998.
[8] Test images for experimenting from Vision Texture Database. available at http://vismod.media.mit.edu/vismod/imagery/VisionTexture/vistex.html
[9] Test images from Berkeley Segmentation Dataset: Images available at http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/seg bench/BSDS300/html/dataset/images/color/134052.html
[10] Jing Dong Wang, PhD. thesis on graph based image segmentation, Hong Kong University, 2007.
[11] Gonzales R C and Woods R E, Digital Image Processing, 2nd ed., Pearson Education Asia, 2002.