Abstract
Image segmentation is a process of partitioning input image into meaningful regions. It is a challenging task that is involved in almost every image processing system. Currently lot of methods for image segmentation with different approaches was created. Between all of them the methods based on graph theory are more and more popular nowadays. Segmentation methods could be classified for example to interactive and automatic ones. The further class of methods benefits from a user interaction that provides valuable information about a segmentation problem. The later class of methods doesn’t incorporate any user interaction. Nevertheless fully automatic methods that are both precise and robust are still hard to find. In this paper a new method based on shortest path in a graph is presented. This method automatically places seed points that are further used for image segmentation in the sense of path basins. This method allows segment an input image to a predefined or to an undefined number of image segments. Derived seed points could also be used in other interactive methods instead of a user interaction. Experiments with this method show its potential for segmenting a general class of images.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Peng, L. Zhang, and D. Zhang, “A survey of graph theoretical approaches to image segmentation,” Pattern Recognition 46(3), 1020–1038 (2013).
P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph based image segmentation,” Int. J. Computer Vision 59(2), 167–181 (2004).
J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. Pattern Anal. Mach. Intellig. 22(8), 888–905 (2000).
I. J. Cox, S. B. Rao, and Y. Zhong, “Ratio regions: a technique for image segmentation,” in Proc. Int. Conf. on Pattern Recognition (San Francisco, 1996), pp. 557–564.
L. Grady, “Random walks for image segmentation,” IEEE Trans. Pattern Anal. Mach. Intellig. 28(11), 1768–1783 (2006).
M. Wertheimer, “Laws of organization in perceptual forms (partial translation),” in A Sourcebook of Gestalt Psychology (Routledge and Kegan Paul, London, 1938), pp. 71–88.
E. W. Dijkstra, “A note on two problems in connection with graphs,” Num. Math. 1(1), 269–271 (1959).
Y. Boykov and G. Funka-Lea, “Graph cuts and efficient N-D image segmentation,” Int. J. Computer Vision 70(2), 109–131 (2006).
E. N. Mortensen and W. A. Barrett, “Intelligent scissors for image composition,” in Proc. 22nd Annu. Conf. on Computer Graphics and Interactive Techniques SIGGRAPH 95, (Los Angeles, 1995), pp. 191–198.
A. X. Falcao, J. K. Udupa, and F. K. Miyazawa, “An ultra-fast user-steered image segmentation paradigm: live wire on the fly,” IEEE Trans. Med. Imag. 19(1), 55–62 (2000).
M. Pavan and M. Pelillo, “A new graph-theoretic approach to clustering and segmentation,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition (Madison, 2003), pp. 145–152.
C. Rother, V. Kolmogorov, and A. Blake, “GrabCut: interactive foreground extraction using iterated graph cuts,” ACM Trans. Graph. 23, 309–314 (2004).
S. Beucher, “Watershed, hierarchical segmentation and waterfall algorithm,” in Mathematical Morphology and Its Applications to Image Processing (Kluwer, Dordrecht, 1994), pp. 69–76.
R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, “SLIC Superpixels Compared to State-of the-art Superpixel Methods,” Trans. PAMI 34(11), 2274–2282 (2012).
C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” in Proc. 6th Int. Conf. on Computer Vision (Bombay, 1998).
A. Chambolle, “An algorithm for total variation minimization and applications,” J. Math. Imaging Vision 20, 89–97 (2004).
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper uses the materials of a report that was submitted at the 11th International Conference Pattern Recognition and Image Analysis: New Information Technologies that was held in Samara, Russia on September 23–28, 2013.
The article is published in the original.
Tomas Ryba was born in 1985 in Plzen, Czech Republic. He received his M.S. degree in Cybernetics from the University of West Bohemia (UWB), Plzen, Czech Republic in 2009. As a Ph.D. candidate at the Department of Cybernetics, UWB, his research interests focus on medical imaging and image segmentation. He is also a teaching assistant at UWB.
Milos Zelezny was born in Plzen, Czech Republic, in 1971. He received his M.S. and Ph.D. degrees in Cybernetics from the University of West Bohemia, Plzen, Czech Republic (UWB) in 1994 and in 2002 respectively. Since 2012 he is an associate professor at the UWB. He has been delivering lectures on Digital Image Processing, Structural Pattern Recognition and Remote Sensing since 1996. He is working in projects on multi modal humen-computer speech interfaces and computer vision.
Rights and permissions
About this article
Cite this article
Ryba, T., Zelezny, M. An automatic image segmentation algorithm involving shortest path basins. Pattern Recognit. Image Anal. 25, 89–95 (2015). https://doi.org/10.1134/S1054661815010162
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1054661815010162