Image Segmentation Techniques:A Comparative Study

Download Full-Text PDF Cite this Publication

Text Only Version

Image Segmentation Techniques:A Comparative Study

A Comparative Study

Mira Parmar

Electronics & Telecommunication EnggDept Fr.C Rodrigues Institute of Technology,Vashi, Navi Mumbai, India.

Mrs. SadhanaPai

Electronics & Telecommunication EnggDept Fr.C Rodrigues Institute of Technology, Vashi, Navi Mumbai, India.

Abstract: Image segmentation plays an important role in the pre-processing phase of images.In day-to-day life, new technologies are emerging in the field of image processing.Asimage segmentation is the necessary part of processing, many general-purpose algorithms and techniques have been developed forit.Many times it becomes necessary to combine these algorithm and techniques with domain knowledge for achieving a common solution. This combination satisfactorilysolves the image segmentation problemfor a given application.This paper presents description andcomparison on some of the most commonly usedsegmentationtechniques like Thresholding, Edge detection and Region based segmentation.

Keywords: Image Segmentation;Thresholding; Edge Detection; Region based segmentation.

I. INTRODUCTION

The objective of image segmentation is to partition the image into components or regions of interest for a more detailed analysis of one or more of these regions. Segmentation should stop when the objects of interest in an application have been isolated. So the image segmentation is also one of the most difficult tasks in this image analysis process and the success of the image analysis operations is highly dependent on the success of the segmentation of an image.

Applications of imagesegmentationrangesfromcontent based image retrieval, filtering of noisy images, medical imaging, locating objects in satellite images, automatic traffic controlling systems, video surveillance, machine vision to problems of feature extraction and recognition.

II.IMAGE SEGMENTATION TECHNIQUES

There are mainly two different approaches of image segmentation, the first approach is the discontinuity based approachand the secondapproach is similarity based approach.

In discontinuity based approach, the partition or subdivision of an image is carried out based on some abrupt changes in intensity levels in an image or abrupt changes in gray levels of an image. The major interest lies in identification of isolated points or identification of lines present in the image or identification of edges.

In the similarity based approach, the approach is to group those pixels in an image which are similar in some sense. It includes operations like thresholding and region growing.

  1. DISCONTINUITIES BASED TECHNIQUES

    1. Point Detection

      The standard high pass mask is used for detecting points. A point is said to be detected at the location on which the mask is centered only if |R| .The output is obtained using expression,

      1 if ,

      g(x,y) = 0 otherwise

      whereg is the output image, T is a nonnegative threshold and R is the response of the mask at the center point.

    2. Line Detection

      To detect lines in a certain direction, only those masks that would emphasize a certain direction and be less sensitive to other directions are used.

    3. Edge Detection

      Edge detection is the most common approach for detecting any discontinuities in gray level of the pixels in the image. Basically, an edge is a set of connected pixels that lie on the boundary between two regions.A meaningful definition of edge requires the ability to measure gray-level transitions in an useful way. The masks are applied over the image to find out the edges. To find the edges in the given image, the

      zero crossings or the gradient method is used.The mask and the image are convolved and its results determine the edge set for the image. To detect the presence of an edge at a point in an image, the magnitude of the first derivative can be used. In the sane way, to determine whether an edge pixel lies on the dark or light side of an edgethe sign of the second derivation can be used.

      The classification of the edge detection operators can be done into two categories as: First order derivative operators and Second order derivative operators.

      1. First order derivative operators: The first derivative operator uses gradient method to find the edges.The minimum and maximum value of the gradient helps to locate the edges. The gradient is an indication of change in a function. Obtaining the gradient of an image requires the partial derivatives at every pixel location in the image. The operators used are the Roberts, Prewitt and Sobeloperator.Out of the above three operators,Sobelismost widely preferred first derivative operator to find edges.Itis the result of modification of Prewittoperator by changing its center coefficient to 2. It provides better noise suppression than Prewittoperator.

      2. Second Order Derivative operators: There aretwosecond derivative operators used, one is the Laplacian of Gaussian (LoG) operator and the other is canny edge operator. Though the Laplacian is a second-order derivative, it is unacceptably sensitive to noise. And hence it is unable to detect edge direction. The zero-crossing property of the Laplacian is used for edge location and then can also be usedfor deciding whether a pixel is on the darker or brighter side of an edge.

        1. Laplacianof Gaussian Operator: The rapid change in intensity is highlighted by the Laplacian operation on the image. This operator usually uses a single gray level image as input and it results into another gray level image as its output. Due to the shape of the LoG, it commonly referred as the Mexican Hat function [4].The Laplacian has an important advantage of being isotropic which not only corresponds to characteristics of human visual system but also responds equally to changes in intensity in any mask direction, thus avoiding having to use multiple masks to calculate the strongest response at any point in the image.

          (a)(b) (c) (d)

          Fig. 1 (a)Original image (b) the LoG output (c) thresholdedLoG and (d) zero crossings.

          The figure 1 above shows the results of the Laplacian of Gaussian operation performed on the image [4]. It is clear that the zero crossings help in process of edge linking.

        2. Canny Edge Operator:The approach of this operator is based on the three basic objectives (i) low error rate, (ii)

    edge points should be well localized and (iii) single edge point response. Although many other operators are available, The Canny edge operator is considered the best because its results in strong and weak edges of the image.A two dimension Gaussian function is used first to smoothen the image. The gradient of the result is computed to find the edge strength and direction at every point. Thegradient magnitude and direction are used for this.Manyundesirable ridges around local maxima are obtained while using the gradient magnitude array.These unwanted ridges are suppressed to obtain discrete orientations of the edge normal. This is done with the process of nonmaximasuppression [1]. If false fragments are produced then the double thresholding technique is employed to reducethem.The output image obtained from these detectors may contain pixels representing the edges as well as the noise. Due to this fact, the edge detection algorithms are followed by edge linking procedures. There are main two techniques used in edge linking. The first technique is local processing and second is global processing.

  2. SIMILARITIES BASED TECHNIQUES

    1. Thresholding

      Itis one of the simplesttechniques used to segment an image. Threshold based techniques produce regions of uniformity within the given image based on some threshold criteria [2]. This techniqueclassifies the image into two classes. The basic principle is that pixels belonging to certain range of intensity values will belong to one class and the rest of the pixels in the image would belong to the other class.

      There are two ways ofimplementing this technique either globally or locally. Global thresholding distinguishes object and background pixels by comparing with threshold value chosen. Then the binary partition is used to segment the image. Segmentation is achieved by scanning the entire image pixel by pixel and labeling each pixel as an object pixel or a background pixel depending on the value of that pixel. The threshold based segmentation techniques are inexpensive and computationallyfast.

      Local thresholding is also known as adaptive thresholding. The local characteristic of the subdivided region in the image are observed and accordingly the threshold values are varied. The threshold value is dependent upon a neighborhood property of the pixel as well as its grey level value. This technique is used when the image has a nonuniform illumination.

      Threshold selection based on the histograms was initially suggested by Nobuyuki Otsu in 1979.There are minor modifications done before applying it to an image.Otsu method is basically referred when there is a need ofthresholding large objects from the background. This method provides a set of thresholds or an optimal threshold which is selected by the discriminant criterion.To measure the difference the discriminant criteria needs to be maximized.Thesteps involved in global thresholding are first reading the image, and then plotting its histogram, choose a

      threshold value and finally segment the image into objects and background.

    2. Region based segmentation

    Region based segmentation algorithms work on the similarity criteria of the pixels within the region. The basic steps followed in region based segmentation are as follows:

    Let X represents the image region [4]. Segmentation algorithm partitions X into n sub regions, X1, X2Xn, such that

    (a)(b) (c)

    Fig.2 (a) Image showing defective welds (b) initial seedimage(c) segmentation result obtained by region growing.

    The figure 2 shows the segmentation by region growing technique on the X-ray image of a weld containing several cracks and porosities [4].The resulting image obtained indicates the need of concept of connectivity.

    ) =

    =1

    ) is a connected region, i = 1,2, n

    ) Xi = for all i and j, i j

    ) P(Xi) = TRUE for i = 1, 2,,n

    ) P(XiXj) = FALSE for any adjacent regions Xi and Xj

    Here P (Xi) is a predicate defined over the point in set Xi and is the null set. The above conditions can be summarized. The first condition indicates that every pixel must be in a region and the segmentation must be complete. The second requires a connected point in some predefined sense. The third condition indicates that the region must be disjoint. Condition fourth indicates that the pixel in a segmented region must satisfy some defined properties. The fifth one indicates that the adjacent regions Xi and Xj are different in the sense of predicate P.

    Region Splitting and Merging provides a different solution to the use of seed points for region growing [4]. The basic idea is to subdivide an image initially into a set of some arbitrary disjoint regions and then merge and/or split the regions to satisfy the conditions of image segmentation.

    This method works on the idea of subdividing the image into quadrants.The first step is to consider the whole image as one single region and second step is to divide the image into four quadrants. This division is done based on certain predefined criteria. The quadrants are checked for the same defined criteria andthenegative result of the test divides it further into four sub-quadrants and the process is continued till the criteria is satisfied or no further division is possible.

    To segment the image based on the similarity approach every pixel is compared with its neighbor for gray level, texture, color, shape whether they have some similar criteria.

    The positive result would decide that particular pixel is added

    to the pixel and in the same fashion a region is grown. When(a) (b)

    the similarity test fails, the region growing process should

    stop [1].

    Region based methods are fundamentally classified into two as (i) Region growing methods and(ii) Region split and merge methods.

    Region growing is a technique which makes groups of pixels or sub regions into larger regions based on predefined criteria for growing the regions of image. The basic step is to select and start with a set of seed points. With the help of seed points grow regions by appending to each seed those neighboring pixels that have predefined properties similar to the seed.

    When a priori information is not available, the procedure is to compute at every pixel to regions during the growing process. If the result of these operation shows clusters then the pixels whose properties place them near the centroid of these clusters can be used as seeds. The selection of similarity criteria depends not only on the problem under consideration, but also on the type of image data available.

    Fig. 3(a) Partitionedimage (b) Correspondingquadtree

    The figure 3 demonstrates the splitting technique forming quadtrees, that is, the trees in which each node has exactly four descendants [4]. The images corresponding to the nodes of a quadtree sometimes are called quadregions or quadimages.

    The region based segmentation methods can work well for images that have some uniformity that is images having uncluttered scenes. In most of the practical cases, images have a lot of details and hence region analysis is a complicated exercise. Despite this, these techniques are used as they are less sensitive to noise.

  3. EXPERIMENTAL RESULTS

    The various segmentation techniques are performed in this section. A simulation study is done to compare the various methods for segmentation and to detect the edges accurately. The results below show the output of edge detection using the Roberts, Prewitt and Sobel operator.

    Fig. 4 Result of Roberts operator

    Figure 4 shows the output obtained by using the most basic Roberts operator.

    Fig. 5 Result of Prewitt operator

    Figure 5 shows the output obtained by using the Prewitt operator.

    Fig. 6 Result of Sobel operator

    Figure 6shows the output obtained by using the Sobeloperator.Sobel is same as the Prewitt operator. The difference is that to get smoothing the coefficient of 2 is added. So the output detects the edges better and noise suppression is achieved.

    The experimental results of thresholding operation are shown in figure below.

    Fig.7Original image to be thresholded

    The figure 7 shows the original image that is to be thresholded.

    Fig.8The histogram of the image

    The figure 8 is the histogram representation of the original image. The histogram is bimodal and hence there are two peaks seen. One peak represents the objects and second peak represents the background.

    Fig.9The thresholded output

    The figure 9 shows the final threholded image. From the histogram of image the selection of threshold is done. Here selection of threshold is interactive. According to selection of threshold the output image obtained would be dark or bright.

  4. SOME OTHER TECHNIQUES

    1. Clustering based methods

      The goal of clustering techniques is to locate clusters from intensity values which are similar [8].The clustering methods are usually classified as hierarchical algorithms and partitionalalgorithms.TheK-means and fuzzy C-means algorithms are the most widely used algorithms. The K-means algorithm is an iterative technique. It i basically used to partition an image into K clusters. The selection of K can be done manually, randomly, or by a heuristic way. The initial set of clusters and the value of K decide the quality of the solution. FCM algorithm results in fuzzy partitioning of the matrix. This algorithm is iterative in nature and along with the objective function it also requires the cluster to be centered.

    2. Watershed transformation

      In the watershed transformation technique the gradient magnitude of an image is referred as a topographic surface [9].The watershed lines refer to thepixels having the highest gradient magnitude intensities. These lineswould then represent the region boundaries. Water that is placed on any of the pixel enclosed by a common watershed line would easily flow downwards to somecommon minimum local intensity level. A catch basin is formed by the draining of the

      pixels to some common minimum level which finally represents a segment.

    3. Graph partitioning methods

      In this technique the image is represented as a weighted and an undirected graph [7].The nodes are related to a pixel or a group of pixels. After this the edge weights would define the dissimilarity between the neighborhood pixels. To design better clusters, the graph or the image is then partitioned according to a criterion.These algorithms results in the partition of the nodes or pixels. This output is consideredasan object segment in the image. The normalized cuts, random walker, minimum cutand segmentation-based object

      categorization are some of the popular algorithms referred in this approach.

    4. Model based segmentation

    The approach is that the given image has such structures or organs which have a repetitive form of geometry [6]. For understanding the variation of the shape of the organ, a probabilistic model can be made. Such a method involves steps such as the registration of the training examples to a common pose, then the variation of the registered samples are represented in probabilistic way, and statistical inference between the model and the image is studied.

  5. COMPARISON OF VARIOUS IMAGE SEGMENTATION TECHNIQUES

    Table 1: Comparison of Image Segmentation Techniques

    Segmentation techniques

    Merits

    Demerits

    Roberts operator

    Oldest operator and easy to implement

    Highly sensitive to noise and kernels are too small to reliably find edges

    Prewitt operator

    Simpler to implement

    Produces lesser noise than Roberts but still noise is not reduced satisfactorily

    Sobel operator

    Produces smoothing effect and noise suppression is better than Prewitt

    Vulnerable to high frequency noise effect

    Laplacian of Gaussian

    Noise effect can be minimized

    Generate closed contours which are not realistic

    Canny edge detector

    Produces cleanest edge and gives improved feature detection

    Setting a threshold that works well on all types of images is difficult task

    Thresholding

    Computationally fast and useful for images having solid objects on contrast background

    Improper selection of threshold may produce overlapping of gray levels of the object and the background

    Region based segmentation

    Works well in noisy environment and produces the region with thin connected boundaries

    Incorrect selection of seed point results in wrong segmentation result and algorithm is highly iterative so needs computational time

    The table below gives a comparison between the various image segmentation techniques.

  6. CONCLUSION

Many image segmentation methods have been developed in the past several decades for segmenting images in various applications. But still it remains a challenging task. A segmentation method may perform well for one image but not for the other images of same type. Thus it is very hard to achieve a generic segmentation method that can be commonly used for all images.

In the discontinuities based approach we find that while using first derivative operator, Sobel operator gives

better noise suppression. Though the second order operators are more sensitive to noise but due to their zero crossing property the canny edge detector gives the exact location of the edges.

In the similarities based approach, thresholding is computationally fast and inexpensive.The region based segmentation is less sensitive to noise but the incorrect selection of seed points can give wrong segmentation results.

REFERENCES

  1. S SapnaVarshney, NavinRajpa and RavindarPurwar Comparative Study of Image Segmentation Techniques and Object Matching using Segmentation International Conference on Methods and Models in ComputerScience, 2009.

  2. MirceaWeingart and OrestVascan Image Segmentation Processing – some techniques and experimental results Electrical and Electronics Engineering (ISEEE), 2013 4th International Symposium.

  3. R. C. Gonzales, R. E. Woods, and S. L. Eddins, Digital ImageProcessing using MATLAB, Pearson Education.

  4. R. C. Gonzales and R. E. Woods, Digital Image Processing , 3rd Edition,

    Pearson Education

  5. Yogamangalam, Karthikeya,Segmentation Techniques Comparison in Image Processing , International Journal of Engineering and Technology ISSN : 0975-4024 Vol 5 No 1 Feb-Mar 2013

  6. http://en.wikipedia.org/wiki/Image_segmentation

  7. http://www2.maths.lth.se/vision/publdb/reports/pdf/eriksson-barr-etal- ssia-06.pdf

  8. Xiaoru Wang1,Junping Du, Shuzhe Wu, Xu Li and Fu Li2, Cluster Ensemble-based Image Segmentation,International Journal of Advanced Robotic Systems, 2013, Vol. 10, 297:2013

  9. Amanpreetkaur and AshishVerma, The Marker-Based Watershed Segmentation- A Review International Journal of Engineering and Innovative Technology Volume 3, Issue 3, September 2013

Leave a Reply

Your email address will not be published. Required fields are marked *