Review of Various ImageSegmentation Techniques

Review of Various ImageSegmentation Techniques

Jagpreet Kaur¹, Dr. Raman Maini²

1M.Tech Student, Department of Computer Engineering, Punjabi University, Patiala, Punjab (India)

2Professor, Department of Computer Engineering, Punjabi University, Patiala, Punjab (India)

Abstract: Segmentation of an image is a process which partitions an image into regions which are more specific to a particular application. These regions are set of pixels which have high intra-region homogeneity and low inter-region homogeneity. Homogeneity is determined on the basis of various pixel characteristics like distance, connectivity, intensity, texture etc. Segmentation also involves detecting objects of interest. Several techniques and algorithms have been devised so far for segmentation of images. Image segmentation is an integral part of image analysis. Images segmented by use of various algorithms can be evaluated for judging performance of these techniques. The evaluation can be both subjective and objective. In this paper we review some of the segmentation techniques and compare their performance qualitatively.

Keywords: Image segmentation; pixels; region; threshold.

1. INTRODUCTION

   Images are one of the highly appropriate medium for conveying information. For conveying useful information a method is required, with the help of which, we can analyse images and extract objects of our interest. Image segmentation is one such method[3]. Image segmentation is the initial and most intricate step in image analysis. It aims at dividing the image into various regions [4]. The regions are of interest to particular applications. Image segmentation has variety of applications. It can be used for Content based image retrieval, Medical Imaging Locating Tumors ,Measuring Tissue Volumes, Diagnosis, Object Detection in satellite images, Traffic Surveillance, Face Recognition etc[10].

   Image segmentation techniques are classified into two main categories, depending upon two properties of image under consideration[2].

   1. Detecting similarities

      This involves partitioning an image into regions which consist of pixels similar to each other on the basis of some predefined criterion. It includes techniques like thresholding, region growing, region based splitting and merging etc.

   2. Detecting discontinuities

   Discontinuities or sharp intensity changes can be detected to determine objects of interest. Edges represent sharp intensity changes and thus segmentation on basis of discontinuity involves detecting edges. Edge detection can be done with variety of techniques such as Canny, Sobel, Laplacian of Gaussian etc[5].

   This paper is well organized into sections where section II reviews various image segmentation techniques. Section III presents few simulation examples and compares various techniques used in examples. Section IV presents the results and discussion of the simulated examples. Finally, we conclude the paper in section V.

2. SEGMENTATION TECHNIQUES

   1. Segmentation using Edge Detection Methods This method includes detecting sharp changes in intensity i.e. the edge points and then labeling them under edge segments. But noise is also present in the image in the form of sharp intensity changes, therefore prior to edge detection images are filtered for removal of any kind of noise[5].Then the images are enhanced to counter any blurring of desired content caused during smoothing of noise in the first step. After that edge points are detected. There are variety of filters present for detecting edges like Canny edge detector, Sobel, Prewitt, Laplacian of Gaussian etc[2]. Using one of the following criteria edge points are detected:

      • Areas where the first derivative of magnitude of pixel intensity is greater than some assumed or calculated threshold value.

        Example: Edge detection using Canny detector.

        One commonly and most widely used edge detector is canny edge detector. It is considered to be one of the best techniques for edge detection as it eliminates noise first and thus reduces the chances of false edge detection[1]. It also does non- maxima suppression for that purpose. The steps followed by this edge detector are enumerated below:

        1. Firstly noise is eliminated using Gaussian filter mask using convolution methods[7].

        2. Next step is to detect edge strengths using Sobel filter masks. Sobel performs 2-D gradient on image. Sobel operators used are:

           -1	0	+1
           -2	0	+2
           -1	0	+1

           +1	+2	+1
           0	0	0
           -1	-2	-1

           Gx Gy

           The magnitude is given by : |G|=|Gx|+|Gy|

        3. Then the direction of edge is computed as following:

           Ø= arctan(Gy/Gx).

           Now the major task is to perform non- Maxima suppression i.e. to eliminate all those edges that does not lie in direction of local maxima.

        4. Now Double thresholding is performed to eliminate false edges and then true edges are linked on basis of connectivity criteria[1].

        Advantages:

      • Segments the image into edges that are easily perceived by humans.

      • Works well with good contrast images.

        Disadvantages:

      • Creates chaos in images which have too many edges and thus makes it difficult to interpret.

      • Many false edges can be detected if proper noise suppression is not done.

      • Areas where the second derivative of pixel intensity yields zero crossing.

        Input Image

        Gray-Scale Image

        Noise Reduction

        Edge Detected

        Non-Maxima Suppression

        Masking

        Threshold

        Fig. 1: Steps involved in Canny edge detection [4].

   2. Threshold method

      The most simple way to segment an image is to segment it on the basis of pixel intensity values directly. This technique is called the thresholding based segementation. Thresholding algorithms can select Threshold value manually as per a prior knowledge of image intensity values or automatically by image information[2]. Thresholding is an old, easy and most widely used technique for image segmentation[1]. Segmenting an image by thresholding is an effective approach for images which have light foreground objects on a relatively darker background. Thresholding technique is based on intensity characteristics of an image [2]. Thresholding operation converts a gray-scale image into a binary image. It chooses a proper threshold T, and divides the image pixels into several regions and objects are separated from background. Firstly, thresholding procedure is used to determine an intensity value known as threshold, and this threshold divides the image pixels into desired classes. Thus, segmentation is achieved by grouping all pixels with intensity exceeding the threshold into one class, and all other pixels into another class[1]. Threshold value is decided in two ways:

      • Global thresholding: Here a single Threshold value (T) is applicable for the entire image. It is successful when image illumination is fair otherwise it fails to segment the image.

      • Local thresholding: Here value of T varies for clusters of pixels over the image. It can segment the image even when the background has unequal illumination. In this, multiple threshold values are used to compensate for the unfair illumination [2].

        Advantages:

      • This technique is computationally simple.

      • Works well with images which have proper illumination.

        Disadvantages:

      • Poorly illuminated images cant be segmented properly.

      • Does not consider pixel connectivity while segmenting, thus resulting segments may not be contiguous.

      • It is susceptible to noise and intensity heterogeneity.

   3. Region Based Segmentation

      A region (denoted by R ) of an image can be defined as a connected homogenous subpart of the image. Regions in an image are group of connected pixels with matching characteristics. This approach assigns every pixel to a particular region or associates it with a particular object. This technique segments the image on the basis of similarity of pixel characteristics that may be intensity or texture or any other[2]. The parameters considered are similarity of values (which includes difference of gray value and variance among gray values) and spatial proximity (which comprises of Euclidean distance metric and region compactness). They are further classified into two techniques:

      1. Region Growing: This method includes dividing the entire image into regions by grouping pixels on the basis of some predefined criteria[6]. The criteria may be pixel intensities collaborated with other factors such as connectivity, texture etc. Region growing is an approach to image segmentation in which neighboring pixels are analysed and collaborated with a region. This process is repeated for every pixel in the region. The region growing algorithm follows following steps[2]-

         • Select seed pixels within the image.

         • Find connected components of all seed pixels and erode all such components to one pixel and label them 1.

         • Form an image which has value 1 at pixel where predicate is true otherwise value is 0.

         • Now append all the 1-valued points from this image to those seed points to which they are 8-connected.

         • Label each connected component as separate region[1].

           .

           The algorithm is less susceptible to noise. This method has a limitation that, it requires a seed point, which generally requires manual interaction.

      2. Region Splitting and Merging: This technique is complementary to region growing. This technique works on entire image. Region splitting follows top-down approach. It begins with entire image and breaks it up such that the divided parts are more homogeneous than the entire image. Splitting alone is not sufficient for proper segmentation as it severely contains the segment shapes[1]. Hence, a merging algorithm after splitting is necessary, and thats why it is called split and merge algorithm.

         Region Splitting method:

         • Let R denote the entire image, and choose a predicate P.

         • Break the image hierarchically into smaller and smaller quadrant regions until the value of predicate for all regions comes to be true.

      Region Merging Method: in this all those regions which are adjacent and similar enough are merged.

      • Merge any adjacent regions that have enough similarity. This can be checked by seeing the value of predicate for the union of adjacent regions. If the predicate comes to be true for the union then merge those adjacent regions otherwise not[1].

      • Repeat the above step until all adjacent regions have been checked.

        Advantages:

      • More immune to noise.

      • Works well in condition when region homogeneity criteria is easy to define[2].

        Disadvantages:

      • Computationally lengthy.

      • Expensive in terms of memory.

      R1	R2
      R3	R41	R42
      	R43	R44

      R

      R1 R2 R3 R4

      R41

      R42 R43 R44

      Fig. 2: Quadrant regions and Quad trees used to represent Region based Segmentation[1].

   4. Segmentation using Clustering Methods

      Clustering technique involves unsupervised classification of region data. It does grouping of data in a way that similar pixels constitute one group and distinct pixels get distributed in different clusters. Generally clustering algorithms rely on distance metric between pixels. Clustering is classified into two categories hierarchical clustering and partition clustering[2].

      • Hierarchical clustering techniques use proximity matrix to result in tree of clusters.

      • Partition based clustering is iterative technique that focusses at optimizing an objective function f which measures clusters goodness.

   The most widely used clustering algorithm is K- means clustering algorithm. It does clustering by following these steps[8]:

   1. K is the number of clusters which are to be provided by user or can be estimated using Bayesian Information criterion or other such methods.

   2. Initially randomly K centroids are chosen. Every pixel is associated with these centroids on basis of distance criteria to form K clusters. Every pixel must be associated to one and only one cluster.

   3. Now re-compute the cluster centroids by calculating the cluster means. Then reassign the pixels to clusters on basis of distance from new centroids.

   4. Above step is repeated until centroids cease to differ from previous iterations. Thus iteratively clusters are obtained.

      Distance metric used can be Euclidean distance, squared distance etc.

      Advantages:

      • Simple to implement.

      • Minimize within cluster scatter.

        Disadvantages:

      • It converges but finds only local minima.

      • Outliers can cause undesirable variation in clusters.

      • No. of clusters must be determined in advance.

        Various algorithms have been proposed to overcome K- means clusterings weaknesses such as K-medoids clustering, fuzzy c-mean clustering , hard c-mean clustering etc[9].

3. SIMULATION EXAMPLES

   Various segmentation techniques are applied to various images to compare their performance.

   Fig. 3: Comparison of edge detection techniques applied on coins image.

   Fig. 4: Comparison of thresholding method with varying threshold values applied on coins image.

   Fig. 5: Thresholding method applied on an image with broad segments.

   Fig. 6: Various edge detectors applied on the image with poor noise suppression.

   Fig. 7: Region based Segmentation using texture functions.

4. RESULTS AND DISCUSSION

   We had applied all above methods to about 10-12 images, only a few have been displayed here. It is also clear from the pictures that no one method can be applied to all the images. The images were subjected to qualitative evaluation by showing them to numerous people. On the basis of visual perception of human beings and also on the basis of visual detail detected by various techniques the following results were concluded:

   • Canny edge detector yielded best results among all the edge detectors used as it has detected even the intricate edges. Laplacian of Gaussian also detected a fair amount of edges but they were less well defined. Both Sobel and Prewitt were almost same in detecting obvious edges(eg. figure3) .

   • However, Canny edge detector yielded too many false edges where the noise suppression was poor (eg. figure6).

   • Thresholding yielded good results where there were obvious and broad segments(eg

     .figure5).

   • Region based segmentation was successful in detecting regions on basis of simple criteria between pixels i.e. standard deviation and range(eg. figure7).

5. CONCLUSION

This paper provides a brief overview of major image segmentation techniques. The tecniques explained are widely used in Image analysis in many fields. MATLAB 7.10.0.499 has been used to simulate various techniques in order to compare their performance. Image segmentation is a promising Image Analysis technique and has a challenging future due to its expanded use. No single technique is

good for all type of images and not all techniques can be applied to all images. Moreover, images can be compared objectively using various parameters. Quantitative comparison of images provide opportunity for future work. Therefore, this area provides a lot of opportunities for research.

REFERENCES

1. Rafael C. Gonzalez, Richard E.Woods,Image Segmentation, third ed.,Digital Image Processing, Pearson , Ch: 10,pp. 689-763.

2. H.P. Narkhede, Review of Image Segmentation Techniques , International Journal of Science and Modern Engineering (IJISME) ISSN: 2319-6386, Vol.1, Issue-8, July 2013.

3. Manisha Sharma, Vandana Chouhan, Objective Evaluation Parameters of Image Segmentation Algorithms, International Journal of Engineering and Advanced Technology (IJEAT) ISSN: 2249 8958, Vol.2, Issue-2, December 2012.

4. Poonam Dhankhar, Neha Sahu, A Review and Research of

   Edge Detection Techniques for Image Segmentation, IJCSMC, Vol. 2, Issue-7, pp.86 92, July 2013.

5. Raman Maini , Dr. Himanshu Aggarwal Study and Comparison of various Image Edge Detection Techniques

   ,International Journal of Image Processing(IJIP),Vol.3,Issue-1.

6. S.Lakshmi , Dr.V.Sankaranarayanan A study of Edge Detection Techniques for Segmentation Computing Approaches IJCA Special Issue on Imaging and Biomedical Applications CASCT, 2010.

1. Nor Ashidi Mat Isa, Samy A. Salamah, Umi Kalthum Ngah, Adaptive Fuzzy Moving K-means Clustering Algorithm for Image Segmentation, IEEE Transactions on Consumer Electronics, Vol. 55, No. 4, November 2009.

2. V. K. Dehariya, S. K. Shrivastava, R. C. Jain,Clustering of Image Data Set using K-Means and Fuzzy K-Means Algorithms, International conference on CICN, pp. 386- 391, 2010.

3. Zhang, Y. J, An overview of Image and Video Segmentation in the last 40 years, Proceedings of the 6th International Symposium on Signal Processing and Its Applications, pp. 144- 151, 2001.