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

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.

Authors:

• Deepthi Narayan
• Srikanta Murthy K.
• G. Hemantha Kumar

Keywords:

• Graph based image segmentation
• threshold
• Weighted Euclidean distance.

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.