Open Access Open Access  Restricted Access Subscription or Fee Access

Image Segmentation based on Region Merging using Breadth-First Search

Amandeep Kaur, Neeru Jindal


This paper proposed a new method for image segmentation based on region merging using breadth-first search (BFS). The image can be partitioned into multiple segments so that meaningful information is extracted out and then image is analyzed easily. In the proposed method, first the oversegmented image is obtained by applying a standard watershed transformation on original image. Then BFS is executed on the oversegmented image to obtain a segmented image. The quality parameter F-measure has been calculated for the segmented images. The proposed algorithm is also compared with existing method and better results are obtained.



Image segmentation, watershed transformation, BFS.

Full Text:



Kearney, Colm and Patton, J. Andrew, Survey on the image segmentation, Financial Review, 2000, 41:29-48p.

N. Pal and S. Pal, A review on image segmentation techniques, Pattern Recognition, Sep. 1993, 1277–1294p.

L. Yang, F. Albregtsen, T. Lonnestad, P. Grottum, A supervised approach to the evaluation of image segmentation methods, Computer Analysis of Images and Patterns, 1995, 759–765p.

R.C. Gonzalez and R.E. Woods, Digital image processing, Addison Wesley World Student Series, 1994.

Meyer F., Proceedings of the IEEE International Conference on Image Processing and its Applications: Colour image segmentation, April 7-9, 1992, Maastricht, Netherlands.

T. Malisiewicz and A. A. Efros, Improving spatial support for objects via multiple segmentations, Proc. BMVC, 2007.

Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: Thinnings, shortest path forests, and topological watersheds, PAMI 32, 2010, 925-939p.

L. Shafarenko, M. Petrou and J. Kittler, Automatic watershed segmentation of randomly textured color images, IEEE Trans. on PAMI, 1997, 6:1530-1544p.

D. Comanicui and P. Meer, Mean Shift: A Robust approach toward feature space analysis, IEEE Trans. on PAMI, 2002.

Chang Cheng, Andreas Koschan, Member, IEEE, Chung-Hao Chen, David L. Page, and Mongi A. Abidi, Outdoor Scene Image Segmentation Based on Background Recognition and Perceptual Organization, IEEE Transactions On Image Processing, March 2012.

Vincent, L., and Soille, P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations, IEEE Trans. Patt. Anal. Mach. Intell, 1991, 583-598p.

C. Allene, J.-Y. Audibert, M. Couprie, J. Cousty, and R. Keriven. Some links between min cuts, optimal spanning forests and watersheds, In ISMM’07, INPE, 2007, 2:253–264p.

Lamia Jaafar Belaid and Walid Mourou, Image Segmentation: A Watershed Transformation Algorithm, Image Anal Stereol, 2009, 28:93-102p.

Bieniek, A., and Moga, A connected component approach to the watershed segmentation, In Mathematical Morphology and its Applications to Image and Signal Processing, H. J. A. M. Heijmans and J. B. T. M. Roerdink, Eds. Kluwer Acad. Publ., Dordrecht, 1998, 215-222p.

Bieniek, A., Burkhardt, H., Marschner, H., Nolle, M., and Schreiber, G. Proceedings of 10th Scandinavian Conference on Image Analysis (SCIA'97): A parallel watershed algorithm, Lappeenranta, Finland, 1997.

P. Felzenszwalb, D. Huttenlocher, Efficient graph-based image segmentation, Int. J. of Computer Vision, 2004, 59:167–181p.

Moscheni, F. Bhattacharjee, S. Kunt, M. Spatio-temporal segmentation based on region merging, IEEE Transactions on Pattern Analysis and Machine Intelligence, Sep 1998, 20:897-915p.

Nock R. and Nielsen F., Statistical Region Merging, IEEE Trans. on Pattern Analysis and Machine Intelligence, 2004, 26:1452-1458p.

F. Calderero and F. Marques, Region merging techniques using information theory Statistical measures, IEEE Trans. Image Process., 2010, 19:1567–1586p.

S. Wan and W. Higgins, Symmetric region growing, IEEE Trans. Image Process, Sep. 2003, 12:1007–1015p.

Luis Garcia Ugarriza, Eli Saber, Sreenath Rao Vantaram, Vincent Amuso, Mark Shaw, and Ranjit Bhaskar, Automatic Image Segmentation by Dynamic Region Growth and Multiresolution Merging, IEEE Transactions On Image Processing, October 2009.

A. Yoo. E. chow, K. Henderson, W. McLendon, B. Hendrickson, and U. Catalyurek, Proceedings of the ACM/IEEE conference on Supercomputing: A scalable distributed parallel breadth-first search algorithm on blue gene, 2005, Washington, DC, USA, IEEE Computer Society.

Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan, and Renato F. Werneck. Proceedings of the 19th European conference on Algorithms, ESA’11: Maximum flows by incremental breadth-first search, 2011, Berlin, Heidelberg, Springer-Verlag.

M. Najork and J. Wiener, Proceedings of the 10th International World Wide Web Conference: Breadth-first search crawling yields high-quality pages, 2001.

D. Comaniciu and P. Meer, Mean Shift: A Robust Approach toward Feature Space Analysis, IEEE Trans. on Pattern Analysis and Machine Intelligence, May 2002, 24:603–619p.

Balázs Varga et al., High-resolution image segmentation using fully parallel mean shift, Varga and Karacs EURASIP Journal on Advances in Signal Processing, 2011.

Saiful Islam1 et al., Implementation of Image Segmentation for Natural Images using Clustering Methods, Int. J. of Emerging Tech. and Advanced Engg., March 2013.

Nassir Salman, Image Segmentation Based on Watershed and Edge Detection Techniques, Int. Arab Journal of Information Technology, April 2006.

Bo Peng, Lei Zhang, Member, IEEE, and David Zhang, Fellow, IEEE, Automatic Image Segmentation by Dynamic Region Merging, IEEE transactions on image processing, December 2011.

Agus Zainal Arifin and Akira Asano, Image segmentation by histogram thresholding using hierarchical cluster analysis, Pattern Recognition Letters, 2006.

Brij Mohan Singh et al. Parallel Implementation of Otsu’s Binarization Approach on GPU, Int. J. of Computer Applications, October 2011, 0975 – 8887p.

P. F. Felzenszwalb and D. P. Huttenlocher, Efficient graph-based image segmentation, Int. J. Comput. Vis., Sep. 2004, 167–181p.

J. Canny, A computational approach to edge detection, IEEE Trans. Pattern Anal. Mach. Intell., Nov. 1986, 8:679–698p.

D. Comanicu and P. Meer, Mean shift: A robust approach toward feature space analysis, IEEE Trans. Pattern Anal. Mach. Intell., May 2002, 24:603–619p.


  • There are currently no refbacks.