A Relative Comparison of Graph Based Techniques for Image Segmentation

1st International E-Conference on Recent Developments in Science, Engineering and Information Technology on 23rd to 25th September, 2020 Department of Computer Science, DDE, Madurai Kamaraj University, Tamil Nadu, India. International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC)

Abstract

Image division is one of the significant steps of image processing used in investigate the image. Image may be generic or medical. Even though a lot of research has been done on this topic, there is no ideal result for the task of image segmentation has been found and it till now it is a tough task since the features of the image are lot. There are numerous image segmentation techniques available. But among all graph based methods have been practically proven to be most effective and are having wider scope for further work. It is simply because graph based methods unambiguously classify the image components into a very good mathematical structures which intern builds the computation of the task further supple and the calculation even more proficient. An organized investigation of graph-based method for image division is presented in this paper. Firstly, the problem is represented by means of dividing a graph into a number of sub-graphs so that each divided segment corresponds to a significant object of interest in an image. These methods are broadly characterized into three types based on the approach: graph based methods with cost functions, graph based methods based on Markov Random Field (MRF), and the minimal path based techniques. A detailed technical explanation for each category is given. We used five quantitative evaluation indices namely, PR (Probabilistic Rand) index, NPR (Normalized Probabilistic-Rand) index, GCE (Global Consistency-Error), BDE (Boundary-Displacement Error) and VI (difference of Information) which played a vital role in graph based image segmentation.

References

[1] Ravindra S. Hegadi, Basavaraj A Goudannavar, "Interactive Segmentation of Medical Images Using GrabCut”, IJMI, Volume: 3, Issue: 3, Pages: 168-171, 2011.

[2] G. Funka-Lea, Y. Boykov, C. Florin, M.-P. Jolly, R. Moreau-Gobard, R. Ramaraj, and D. Rinck. “An Automatic Heart Isolation for CT coronary visualization by GraphCut, In IEEE International Symposium on Biomedical Imaging (ISBI), pp.614-617, 2006.

[3] Hui Xue, Leo Grady, Jens Guehring and Marie-Pierre Jolly,“Combining Registration and Minimum Surfaces for the Segmentation of the Left Ventricle in Cardiac Cine Images of MR” Proc. of MICCAI. pp. 910-918, 2009.

[4] M. Wertheimer, “Laws of Organization in Perceptual Forms”. A Sourcebook of Gestalt Psycychology, W.B.Ellis, ed., pp. 71-88, Harcourt, Brace, 1938.

[5] Z. Wu and R. Leahy, “Tissue classification in MR images using hierarchical segmentation”. In Proc. IEEE Int. Conf: Medical Imaging.12(1):81-85, 1990.

[6] J. Shi and J. Malik,“Normalized Cuts and Image Segmentation”, IEEE Transactions on Pattern Analysis and Machine Intelligence. 22(8):888-905, 2000.

[7] S. Wang and J.M. Siskind,“Image Segmentation with Minimum Mean Cut”, Proc. Eighth International Conference Computer Vision, vol. 1, pp. 517-524, 2001.

[8] S. Wang and J. M. Siskind,“Image Segmentation with Ratio Cut”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(6):675-690, 2003.

[9] Y. Li, J. Sun, C. K Tang and H.Y Shum,“Lazy Snapping”, ACM Transaction on Graphics. 23(3):303-308, 2004.

[10] C. Rother, V. Kolmogorov and A. Blake,“Grabcut interactive foreground extraction using iterated graph cuts”, In ACM Transactions on Graphics. 23(3):309-314, 2004.

[11] J. Liu, J. Sun, and H.Y. Shum,“Paint Selection”, SIGGRAPH 2009.

[12] E.W. Dijkstra,“Some theorems on spanning subtrees of a graph”,Indag. Math. 22(2): 196-199, 1960.

[13] A.X. Falcão, J.K. Udupa, S. Samarasekara and S. Sharma,“User-steered image segmentation paradigms: Live wire and live lane”, In Graphical Models and Image Processing. 60: 233-260, 1998.

[14] R. Unnikrishnan and M. Hebert,“Measures of Similarity”, Proc. IEEE Workshop Computer Vision Applications, 1:394-394, 2005.

[15] D. Martin, C. Fowlkes, D. Tal, and J. Malik,“A Database of Human Segmented Natural Images and Its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics”, Proc. International Conference, Computer Vision, 2:416-423, 2001.

[16] Basavaprasad B and Ravindra S. Hegadi, "A Survey on Traditional and Graph Theoretical Techniques for Image Segmentation", International Journal of Computer Applications (0975 – 8887) Recent Advances in Information Technology, 2014.

[17] G. Healey and D.K. Panjwani, “Markov random field models for unsupervised segmentation of textured color images”, (PAMI), Volume: 17, Pages: 939-54, 1995.

[18] Ravindra S. Hegadi and Basavaraj A. Goudannavar, "Tumor Segmentation from EndoscopicImages using GrowCut method", Communication Proceedings, Computation, Nanotechnology and Management (ICN), International Conference, Spetember-2011.

Keywords

segmentation, graph academic methods, GCE, PR index, BDE, VI.