Split and Merge: A Region Based Image Segmentation

Abstract

Image segmentation is a very challenging task in digital image processing field. It is defined as the process of takeout objects from an image by dividing it into different regions where regions that depicts some information are called objects.

There are different types of image segmentation algorithms. The segmentation process depends upon the type of description required for an application for which segmentation is to be performed. Hence, there is no universally accepted segmentation algorithm.

Region segmentation is divided into three categories region growing, merge and split and watershed. But this study confines only to split and merge techniques. This paper includes split and merge approaches and their extended versions. This study highlights the main limitations and potentials of these approaches.

Keywords: Image segmentation, Region based Techniques, Split and Merge, Region growing, Watershed transform.

Introduction

Image is considered as a great source of information because it consists of much more information than a block of text. Although, to understand the image information, it has e retrieved from the image. Digital image processing deals with this process of retrieving information from image by describing it.

In digital image processing to describe an image, the very first step is to divide the image into sub-parts, where each part is considered as object and depicts some information. This step is called image segmentation [1].

Effective image segmentation is a challenge in image processing field because errors in image segmentation might propagate to end results of image processing [2]. Image segmentation is broadly divided into two categories: dissimilarity based and similarity based.

Edge detection is dissimilarity based image segmentation technique is based on the sudden change in the intensity of pixels. Whereas similarity based image segmentation technique is based on the homogeneity (based on some properties such as intensity, texture, color or any other image statistics) of pixels and grouped together to form regions and called region based image segmentation.

Edge based techniques results in disconnected and false edge detection. Zucker in 1976 stated that image must be segment into regions and should follow the four conditions which are: first condition is that the segmentation should be completed that means each pixel must be processed once and be a part of at least one region, second is that regions should be continuous or connected, third states that the properties that the region should have and the fourth states the maximality of each region in segmentation [3].

The region based techniques fulfil all these conditions. Moreover, region segmentation is much easier and simple than edge detection [4]. The study concerns only to region based image segmentation.

This paper is divided into four sections, first section includes introduction, second section consists of region based image segmentation, third section includes literature review of split and merge algorithms and fourth section gives concluding remarks.

Region Based Image Segmentation

To analyse an image it is necessary to isolate and recognize different objects present in image. Finding regions instead of boundaries in an image is region based way of segmenting an image. A region is area in image whose pixels have same properties.

In 1967 Minsky and Pappert first described a technique which can directly convert grey scale images to regions by avoiding the edge finding procedures. The proposed method produces regions that are combination of two squares whose corners have same grey values [5].

In 1968 Guzman introduced a different method which divided the image into atomic regions and then pair of heuristics is used to join these regions to obtain regions having closed and smooth boundaries [6]. This method totally depends upon the assumption that all objects are on plane surface.

In 1968 Maurle formed regions by merging regional neighbors of similar properties [7].

Brice and Fennema in 1970 developed a new method that not only considers the local properties of pixels on the boundaries but also of the pixels inside the regions. They introduced two phagocytic and weakness heuristic methods as region growing methods.

Phagocytic heuristic cleans up the boundaries but results into false regions whereas weakness heuristic is natural separation method that depends only upon the strength of the boundary separates the two regions [4].

In 1971 Barrow and Popplestone described the region extraction method that takes account global properties of the pixels and make them sensitive to the changes in local properties [8]. 

Pavlidis in 1972 used functional approximation method for region merging [9].

Feldman and Yakimovsky in 1973 and 1975 presented semantic methods to do region merging [10] [11] whereas Rosenfeld et al. used relaxation operation [12].

In 1976 Horowitz and Pavlidis introduced split and merge method for image segmentation.

Regions are defined using approximation function where regions having similar approximation function are merged and regions having large approximation errors are fragmented [13].

In 1976 Zucker presented a survey paper on region growing where region based methods are divided into three categories: region growing, region splitting and region split and merge [3]. Region split and merge and region growing has high computational efficiency.

In 1979 Beucher and Lantuejoul presented the concept of watershed for image segmentation but this approach suffers from over-segmentation [14].

The study found that there are three main region based approaches: region growing, split and merge and watershed transform. This study only includes split and merge.

Split and Merge

Split and merge is based on the divide and conquer approach. In it input image is divided into sub regions until the sub regions become small enough for segmentation. Then appropriate merge rule is used to produce final segmentation results. This process is dividing into four phases split the image, merge similar sub regions and spatially adjacent regions and elimination of small regions.

In 1980 Kanade reviewed different region segmentation approaches based on three levels of knowledge: signal, semantic and physical [15]. 

Ohta in 1980 discussed the effectiveness of color feature in the framework of region splitting [16].

In 1982 Browning and Tanimoto proposed a space and time efficient split and merge method for image segmentation. In this method image is considered as a piece at a time called tile [17].

Suk in 1983 proposed a simple, systematic one pass image segmentation approach. It is based on the pixel partition mode test [18]. This method can easily detect slowly changing regions but have high computational cost.

In 1986 Cheevasuvit stated that the split and merge results depends upon the initialization and globally not optimal. To overcome these limitations, a multistage process was introduced which is suitable for aerial images. But, it results in high computation cost [19].

Pavlidis and Liow in 1988 presented a method that integrates split and merge and edge detection techniques [20]. The complexity of method depends upon the type of image.

Chen et al. in 1991 proposed an automatic adaptive split and merge image segmentation algorithm. The parameters are calculated automatically and totally depends upon the image to be segmented [21]. Strasters in 1991 introduced 3-D split and merge algorithm which is extension of 2-d SM algorithm proposed in [13]. It introduces the mixed tree concept that is mixture of octtree  and quad tree [22].

In 1998 Manousakas proposed 3-D SM algorithm. It is based on simulated annealing and boundary control to reduce the number of regions and smooth the region boundaries [23]. These 3-D methods preserve the connectivity between regions and produce quality results.

In 2000 Borges and Aldon gave a split-merge-fuzzy (SMF). In this SM method prototype based fuzzy clustering is used to make conventional SM method more robust [24].

Merigot in 2003 described a new SM method. This method has a new optimal variable split method that enhances the efficiency of SM method [25]. But has more time overhead than conventional SM method.

In 2009 Aneja et al. used this optimal split method and introduced new SM method having fast merging capacity [26]. This method works well for real time applications but only for grey images.

In 2003 Zhang et al. stated that merging is well defined problem whereas splitting is not. It is the extension of [27]. It overcomes the drawbacks of [27] by using singular valued decomposition and Cholesky decomposition [28]. 

Zhan et al. in 2006 proposed a robust SM method for text extraction from a complex background image. This method is divided into four phases: pre-processsing, splitting, merging and post processing. The proposed method extracts text image blocks into connected component equivalent to text through its color and scale information [29].

Xiang and Wang in 2004 found that expectation Maximization (EM) algorithm converge to local maximum, hence the results are not stable. A new SM method based on Gaussain Based Model (GMM)  for EM was proposed which also used Bayesian Information Criterion (BIC) [30]. This algorithm was improved by Li and Li in 2009.

In GMM the main difficulty is to find out the number of components which is not considered in [30].They proposed a new SM method for Gaussian Based Model (GMM) based on Minimum Message Length (MML).. This method not only decide the number of component values but determine the parameters in the mixture. This is an iterative procedure that stops when MML is maximized and present parameter values are considered as final values.

So, with these values Expectation Maximization (EM) algorithm is implemented to estimate global optimum of the parameters in mixture  [31].

Jaafar et al. in 2010 proposed a SM method for detection of exudates in retinal image. A local variation operation to outline boundaries and then split and merge algorithm is used to extract all bright candidates locally. But sometimes it extracts false structures [32].

In 2007 Xuejing et al. proposed two strategies for image segmentation based on SM method [33]. This was improved by Roy et al. in 2012.

A parallel pixel network is used to perform region splitting and modified merging criterion to reduce execution time [34]. But not overcome the drawbacks of SM method.

Popovic et al. in 2012 presented a novel SM method for hierarchical clustering of GMM, which tends to improve on the local optimal solution [35].

In 2013 Marine also proposed SM method based on GMM via EM [36]. The other mixture of model other than GMM can be used to improve this method.

In 2013 Szenasi used Split and Merge algorithm for image segmentation and produced promising results. This method overcomes the space complexity of region growing method [37]. But fails when compared to other advanced SM methods.

Sasi and Govindan in 2015 introduced a fuzzy SM method for shadow detection in an image. . This method uses Fuzzy predicate instead of a classical predicate function for splitting and merging [38]. The Fuzzy SM method gives accurate results but requires more execution time. Lee and Lee in 2017 proposed a SM method for nucleus segmentation.

Laplacian of Gaussian is used to find the region of interest. GMM model is used with SM method to determine the number of components or nucleus in an image. The proposed method works best in contrasting foreground and background as well as low contrast images [39]. But finding ROI in images with complicated backgrounds.

Conclusions

Split and merge is simple and computational efficient algorithm. There are different methods in literature based on SM. There are improvements in conventional SM method, but still has some disadvantages. Split and merge algorithm is a sequential segmentation algorithm.

The study also found that the SM method based on different homogeneity criterion results in different results. Hence, the best homogeneous criterion for merging and splitting is difficult to find.

Moreover, SM is an iterative algorithm which consumes more time and space and depends on the local properties and there is no simple way to add global properties of image. So, from this study, it is clear that the SM method still requires much more improvements.

References

[1] K.S. Fu and J.K. Mui, “A survey on image segmentation,” Pattern recognition, vol. 13, no. 1, pp. 3-16, Jan. 1981.

[2] R. M. Haralick, Image segmentation survey: Fundamentals in computer vision, O. D. Faugeras, Ed., Cambridge Univ. Press, Cambridge, 1983.

[3] S. W. Zucker, “Region growing: Childhood and adolescence,” Computer graphics and image processing, vol. 5, no. 3, pp. 382-399, Sep. 1976.

[4] C. R.Brice and C. L. Fennema, “Scene analysis using regions,” Artificial intelligence, vol.1, no.3-4, pp. 205-226, jan. 1970.

[5] M. Minsky and S. A. Papert, “Project MAC Progress Report-IV,” MIT press, Cambridge, 1967.

[6] A. Guzmán-Arenas, Decomposition of a Visual Scene Into Bodies, MIT, Artificial Intelligence Laboratory, 1967.

[7] J. L. Muerle, “Experimental evaluation of techniques for automatic segmentation of objects in a complex scene,” Pictorial pattern recognition, vol.1, pp. 3-13, 1968.

[8] H. G. Barrow and R. Popplestone, “Relational descriptions in picture processing,” Machine intelligence, vol. 6, no. 377-396, pp. 3-2, 1971.

[9] T. Pavlidis, “Segmentation of pictures and maps through functional approximation,” Computer Graphics and Image Processing, vol.1, no. 4, pp. 360-372, dec. 1972.

[10] Y. Yakimovsky and J. A. Feldman, “A Semantics-Based Decision Theory Region Analyser,” International Joint Conference on Artificial intelligence, vol.73, pp. 580-588, Aug. 1973.

[11] J. A. Feldman and Y. Yakimovsky, “Decision theory and artificial intelligence: I. A semantics-based region analyzer,” Artificial Intelligence, vol.5, no. 4, pp. 349-371, Feb. 1975.

[12] A. Rosenfeld, R. A. Hummel and S. W. Zucker, “Scene labeling by relaxation operations,”  IEEE Transactions on Systems, Man, and Cybernetics,vol.6 no. 6, pp. 420-433, Jun. 1976.

[13] S. L. Horowitz and T. Pavlidis, “Picture segmentation by a tree traversal algorithm,” Journal of the ACM (JACM), vol. 23, no. 2, pp. 368-388, Apr. 1976.

[14] S. Beucher and C. Lantuéjoul, “Use of watersheds in contour detection,” International Workshop on image Processing  Real-time Edge and Motion Detection/Estimation, Rennes, France, Sep. 1979.

[15] T. Kanade, “Region segmentation: signal vs semantics,” Computer Graphics and Image Processing, vol. 13, no. 4, pp. 279-297, Aug. 1980.

[16] Y.-I. Ohta, T. Kanade and T. Sakai, “Color information for region segmentation,” Computer graphics and image processing,  vol. 13, no. 3, pp. 222-241, Jul. 1980.

[17] J. D. Browning and S. L. Tanimoto, “Segmentation of pictures into regions with a tile-by-tile method,”  Pattern Recognition, vol. 15, no. 1, pp. 1-10, Jan. 1982.

[18] M. Suk and S.-M. Chung, “A new image segmentation technique based on partition mode test,” Pattern recognition, vol. 16, no. 5, pp. 469-480, Jan. 1983.

[19] F. Cheevasuvit, H. Maitre and D. Vidal-Madjar, “A robust method for picture segmentation based on a split-and-merge procedure,” Computer Vision, Graphics, and Image Processing, vol.34, no. 3, pp. 268-281, Jun. 1986.

[20] T. Pavlidis and Y.-T. Liow, “Integrating region growing and edge detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 3, pp. 225-233, Mar. 1990.

[21] S.-Y. Chen, W. –C. Lin and C. T. Chen, “Split-and-merge image segmentation based on localized feature analysis and statistical tests,” CVGIP: Graphical Models and Image Processing, vol. 53, no. 5, pp. 457-475, Sep. 1991.

[22] K. C. Strasters and J. J. Gerbrands, “Three-dimensional image segmentation using a split, merge and group approach,” Pattern Recognition Letters, vol. 12, no. 5, pp. 307-325, May 1991.

[23] I. Manousakas, P. Undrill, G. Cameron and T. Redpath, “Split-and-merge segmentation of magnetic resonance medical images: performance evaluation and extension to three dimensions,” Computers and Biomedical Research, vol. 31, no. 6, pp. 393-412, Dec. 1998.

[24] G. A. Borges and M.-J. Aldon, “A split-and-merge segmentation algorithm for line extraction in 2d range images,” in Proc.of 15^th International Conference of IEEE on Pattern Recognition 2000, vol.1, p. 441-444.

[25] A. Merigot, “Revisiting image splitting’, in Proc.of 12^th International Conference of IEEE on Image Analysis and Processing 2003, pp. 314-319.

[26] K. Aneja, F. Laguzet, L. Lacassagne and A. Merigot, “Video-rate image segmentation by means of region splitting and merging’, in International Conference on Signal and image Processing Applications, 2009. p. 437-442.

[27] N. Ueda, R. Nakano,Z. Ghahramani, and G. E. Hinton, “SMEM algorithm for mixture models’, in Proc. Of Advances in neural information processing systems,1999, p. 599-605.

[28] Z. Zhang, C. Chen, J. Sun and K. L. Chan, “EM algorithms for Gaussian mixtures with split-and-merge operation,” Pattern recognition, vol. 36, no. 9, pp. 1973-1983, Sep. 2003.

[29] Y. Zhan, W. Wang and W. Gao, “A robust split-and-merge text segmentation approach for images,” in Proc. Of 18^th IEEE International Conf. on Pattern Recognition, 2006, p. 1002-1005

[30] R. Xiang and R. Wang, “Range image segmentation based on split-merge clustering,” in Proc. Of 17^th IEEE International Conf. on Pattern Recognition 2004, p. 614-617.

[31] Y. Li and L. Li, “A split and merge EM algorithm for color image segmentation,” in Proc. Of IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009, p. 395-399

[32] H. F. Jaafar, A. K. Nandi and W. Al-Nuaimy, “Automated detection of exudates in retinal images using a split-and-merge algorithm,”  Proc. Of 18^th  IEEE European Conf. on Signal Processing, 2010, p. 1622-1626.

[33] G. Xuejing and Y Kangze, “Two parallel strategies of split-merge algorithm for image segmentation,” Proceedings of IEEE International Conference on Wavelet Analysis and Pattern Recognition, 2007, p. 840-845.

[34] P. Roy, D. Das and P. Biswas, “Real time VLSI implementation of a fast split and merge segmentation algorithm,” in Proc. Of IEEE International Conference on Intelligence and Computing Research, 2012, p. 1-8.

[35] B. Popović, M. Janev, D.  Pekar, N. Jakovljević, M. Gnjatović, M. Sečujski and V. Delić, “A novel split-and-merge algorithm for hierarchical clustering of Gaussian mixture models,” Applied Intelligence, vol. 37, no. 3, pp. 377-389, Oct. 2012.

[36] R. D. Marin, T. Botterill and R. D. Green, “Split-and-merge EM for vine image segmentation,” in Proc. Of IEEE 28^th International Conference on Image and Vision Computing New Zealand, 2013, p. 270-275.

[37] S. Szénási, “Medical image segmentation with split-and-merge method,” Proc. Of 5th IEEE International Symposium on Logistics and Industrial Informatics, 2013, p. 137-140

[38] R. K. Sasi and V. Govindan, “Fuzzy split and merge for shadow detection,” Egyptian Informatics Journal, vol. 16, no.1, pp. 29-35, Mar 2015.

[39] H.-G. Lee, S.-C. Lee, ”Nucleus Segmentation using Gaussian Mixture based Shape Models,” IEEE Journal Of Biomedical And Health Informatics, no. 99, pp.1-1, May 2017.