Comparative & Implementation of Various Image Segmentation Techniques

Comparative & Implementation of Various Image Segmentation Techniques

Patel Purvi J, Patel Fazila I, Chauhan Vidhatri M

Bachelor of Engineering, Department of Computer & Science Engineering, SVMIT Engineering College,

Bharuch, Gujarat, India

ABSTRACT

Image segmentation is a decomposition of scene into its components. Edge, point, line, boundary, texture and region detection are the various forms of image segmentation. Two of the main image segmentation techniques edge detection and region growing are highly in use for image segmentation. Edge detection technique when used alone for image segmentation results in small gaps in edge boundaries. Region growing technique when used alone results in errors in region boundaries. Edge based region growing corresponds to the optimum image segmentation technique in which the both edge detection approach and region growing approach is integrated.

Keywords: Image processing, Image segmentation, Sobel edge detector, Canny edge detector, Region growing, Edge based region growing

1. INTRODUCTION

   Digital image processing refers to processing of a two-dimensional picture by digital computer. It implies digital processing of two dimensional data. A digital image is an array of real or complex numbers represented by a finite number of bits. Image segmentation is a key step in digital image processing. Segmentation divides image into its constituent regions or objects. The level to which segmentation is carried out depends upon the

   problem being solved i.e. segmentation should stop when the objects of interest in an application have been isolated.

   Image segmentation is an important aspect of digital image processing. It basically aims at dividing an image into subparts based on certain feature. Features could be based on certain boundaries, contour, color, intensity or texture pattern, geometric shape or any other pattern. It provides an easier way to analyze and represent an image. In all segmentation is a process of assigning a label to pixels pertaining similar characteristics[1][2].

   There are five techniques for image segmentation:

   [Figure 1. Image segmentation technique]

2. RELATIONAL WORK

   Image segmentation is the most widely used image processing techniques that emerged in early 1960s. Recent segmentation schemes in

   are largely either texture based or edges based and are designed to operate on grey scale images.

   In 1986, an optimal canny edge detection technique was introduced by J.Canny. In the same year Bajcsy et al. showed that both edge detection and region growing are aspects of the same processes under the assumption of step edges and approximately uniform brightness within the regions. It was described that both processes can be unified by making the decision whether the point is on boundary or on a homogeneous surface.

   In 1998, a new region growing approach was introduced in which first region is grown and then the edges were defined so that boundaries obtained by region growing and edges detected collapse with each other.

   The various image segmentation techniques described above and introduced are either edge based or region based alone. The drawback of using edge based techniques alone for image segmentation is that the resultant edge boundaries are left with small gaps which allow merging of dissimilar regions. Similarly, if region based techniques are used alone for image segmentation, then errors occur in region boundaries and edge pixels might be joined with the any of the neighbouring pixels. In this thesis a new segmentation technique is described in which the edge information and region growing information are merged together.

1. EDGE BASED SEGMENTATION

   Edge based methods try to find the places of rapid transition from one to the other region of different brightness or color value. The

   basic principle is to apply some of the gradient operators convolving with the image. High values of the gradient magnitude are possible places of rapid transition between two different regions and are called edges. After finding edges on the image they are linked to form closed boundaries of the regions. Edge based techniques utilize the discontinuity of boundary (e.g., edge detection) and can extract the contour of region of interest. On the other hand, edge detection is also a useful method for image segmentation, since an edge often represents a junction of two adjacent regions[3].

   EDGE

   An edge is not a physical entity and it has no width. It is where the picture ends and the wall starts. It is where the vertical and the horizontal surfaces of an object meet. It is what happens between a bright[3].

   [Figure 2. Type of edges (a) Step edge (b) Ramp edge (c) Line edge (d) Roof edge]

   Edge detection refers to the process of identifying and locating sharp discontinuities in an image. The discontinuities are abrupt changes in pixel intensity which characterize boundaries of objects in a scene. There are a number of edge detection operators available, each designed to be sensitive to certain types of edges. The geometry of the operator determines a characteristic direction in which it is most sensitive to edges. Operators can be optimized to look for horizontal, vertical, or diagonal edges.

   In edge detection technique two operators for edge based segmentation, CANNY Operator, SOBEL Operator.

   1. SOBEL Operator

      • The Sobel operator is used in image processing, particularly within edge detection algorithms. Technically, it is a discrete differentiation operator, computing an approximation of the gradient of the image intensity function[4].

        • Steps of SOBEL operator are as follows:

          1. Mathematically, the gradient of a two each image point a 2D vector with the components given by the derivatives in the horizontal and vertical directions.

             (

             (

          2. The Sobel Edge Detector uses a simple magnitudes. For those you of mathematically inclined, applying can be represented as

             = tan1 ……(4)

             Where g is the gradient vector, g is the gradient magnitude and is the gradient direction.

   2. CANNY Operator[9]:

   1 0 1

   gx = 2	0	2
   1	0	1
   1	2	1
   gy = 0	0	0
   1	2	1

   [Figure 4. Matrix for canny operator]

   The Canny operator works in a multi- stage process. The canny edge detector first smoothes the image to eliminate gradient to highlight regions with high spatial derivatives. Then a simple 2-D first derivative operator is applied to the smoothed image to highlight regions of the image with high first spatial

   derivatives. The algorithm then tracks along

   =1

   =1

   , = 1

   1

   =1

   ,

   these regions and suppresses any pixel that is not

   , ) (1)

   1. So the Sobel Edge Detector uses two convolution kernels, one to detect changes in vertical contrast (hx) and another to detect horizontal contrast (hy)

      1 0 1

      hx= 2 0 2

      1 0 1

      1 2 1

      at the maximum (non maximum suppression)[4][5].

      The magnitude is above the high threshold, it is made an edge. And if the magnitude is between the 2 thresholds,then it is set to zero unless there is a path from this pixel to a pixel with a gradient above second

      threshold.

      hy=

      0 0 0

      1 2 1

      [Figure 3. Matrix for sobel operator]

   2. The amazing thing is that this data can now be represented as a vector (gradient vector). The two gradients computed using hx. Therefore we have a gradient magnitude and direction:

      = ..(2)

      = 2 + 2 ..(3)

      [Figure 5. Canny flow diagram]

      COMPARED RESULT OF CANNY & SOBEL EDGE DETECTOR

      1. (b) (c) [Figure 6. (a) Original image, (b) Canny edge

   detected image, (c) Sobel edge detected image]

   1. (b) (c) [Figure 7. (a) Original image, (b) Canny edge

      detected image, (c) Sobel edge detected image]

      1. (b) (c) [Figure 8. (a) Original image, (b) Canny edge

   detected image, (c) Sobel edge detected image]

   (a) (b) (c) [Figure 9. (a) Original image, (b) Canny edge

   detected image, (c) Sobel edge detected image]

   (a) (b) (c)

   [Figure 10. (a) Original image, (b) Canny edge detected image, (c) Sobel edge detected image]

2. REGION GROWING

   • Region growing approaches in the following way[6][7]:

   • An initial set of small areas is iteratively merged according to similarity constraints.

   • Start by choosing an arbitrary seed pixel and compare it with neighboring pixels.

   • Region is grown from the seed pixel by adding in neighboring pixels that are similar, increasing the size of the region. When the growth of one region stops we simply choose another seed pixel which does not yet belong to any region and start again. This whole process is continued until all pixels belong to some region. A number of regions are allowed to grow at the same time.

   • This is a bottom up method.

   • Region growing is based on 4 connector seed and 8 connector seed pixels[9].

   [Figure 11. 4 connector & 8 connector seed pixel]

   Algorithm: Region growing:

   In the algorithm, the image is called f, the seed has coordinates (x, y) and gray value g

   = f(x, y). The region growing is done by setting each merged pixels gray value to a value h (which must not equal g). The pixel under investigation has coordinates (a, b)[1].

   [Figure 12. Algorithm for region growing]

   1. (b)

      [Figure 13. (a) Original image, (b) Region grow image]

      (a) (b)

      [Figure 14. (a) Original image, (b) Region grow image]

      (a) (b)

      [Figure 15. (a) Original image, (b) Region grow image]

      (a) (b)

      [Figure 16. (a) Original image, (b) Region grow image]

      (a) (b)

      [Figure 17. (a) Original image, (b) Region grow image]

3. COUNT THE TOTAL NUMBER OF REGION

   The original image is first converted to binary image. The bwlabel function is then used to identify the objects in the binary image. The bwlabel function works with the 2-D objects only. This technique is used to count objects in the image. This technique can find the total number of object in any binary image.

   1. (b)

[Figure 18. (a) Original image, (b) Object counted image]

(a) (b)

[Figure 19. (a) Original image, (b) Object counted image]

(a) (b)

[Figure 20. (a) Original image, (b) Object counted image]

1. HYBRID APPROCH

   A. EDGE BASED REGION GROWING

   Edge based region growing is a combination of edge based segmentation technique and region growing technique, where we try to solve the drawbacks of both the technique and make one hybrid technique[10]. Here, first apply region growing technique and then detect the edges with the bwboundries[8].

   The three basic achievements in edge based region growing method are:

   1. The growing seeds are selected at the edge region automatically. In the image, the great

      difference intensity regions will be segmented into hot and cold seeds. No seeds are defined in the homogeneous intensity regions.

   2. The region growing procedure is performed in the homogeneous regions, and stops automatically when either the hot or cold seeds stop growing. The hot and cold seeds prevent each other from growing into the opposite seed region.

   3. The detected edge boundary is correctly located at the real object boundary.

      1. (b) (c)

         [Figure 21. (a) Original image, (b) Region grow image, (c)Edge based region grow image]

         1. (b) (c)

   [Figure 22. (a) Original image, (b) Region grow image, (c)Edge based region grow image]

   (a) (b) (c)

   [Figure 23. (a) Original image, (b) Region grow image, (c)Edge based region grow image]

   (a) (b) (c)

   [Figure 24: (a) Original Image, (b) Region Grow Image, (c)Edge Based Region Grow Image]

2. CONCLUSION

   In this thesis, canny edge detector is used which is one of the most powerful edge detector as the edge points determined, give rise to ridges in the gradient magnitude image. The canny algorithm then tracks at the top of these ridges and sets to zero all pixels that are not actually on the ridge top so as to give thin line as the output, a process known as non maximal suppression. Also due to the use of two thresholds, unlike other edge detectors it is able to detect small intensity variations in an image as edges.

   Sobel masks are generally used for detecting the edges in all the four directions, horizontal, Vertical and digonal. They are used to find the approximate absolute gradient magnitude with particular direction in input gray scale image.

   In the edge region detected by sobel operator the two types of region growing seeds (pixels) are grown, which are used to obtain the final segmented image.

   Edge based region growing segmentation combines the advantage of edge based segmentation and region growing segmentation.

   This method not only segments images with bad illumination, but also detects the object boundaries in such images correctly. This method is very successful on tool images because objects shown occupy areas of many pixels, making it easy to select objects in foreground to separate from background and noise.

3. REFERENCES

1. Digital Image Processing third edition by Rafael

   C. Gonzalez (University of Tennessee) and Richard E. Woods (MedData Interactive), pages 310-317.

2. R. M. Haralick and L. G. Shapiro, Image segmentation techniques, CVGIP, 29,pp. 100 132, 1985.

3. Edge Detection Techniques for Image Segmentation A Survey of Soft Computing Approaches N. Senthilkumaran1 and R. Rajesh School of Computer Science and Engineering, Bharathiar University, Coimbatore -641 046, India.

4. Study and Comparison of Various Image Edge Detection Techniques Raman Maini & Dr. Himanshu Aggarwal, Punjabi University pages 3-10.

5. J. Canny, A Computational Approach to Edge Detection, IEEE Transactions Pattern Analysis Intelligence, Vol. 8, pp. 679-714, 1986.

6. Maxime Lhuillier. Efficient dense matching for textured scenes using region growing. British Machine Vision Conference, pages 700709, 1998.

7. SA. Hojjatoleslami, J. Kittler, Region Growing: A new approach, IEEE Transactions of Image Processing, Vol. 7, No. 7, pp.1079-1084,2000.

8. Sanmeet Bawa, Edge Based Region Growing, Thapar Institute Of Engineering & Technology (Deemed University),2006.

9. An efficient detection of vanishing points using inverted coordinates image space Kyung-Seok Seo, Jung-Hwa Lee, Heung-Moon Choi,

Department of Electronics, Graduate School, Kyungpook National University, 1370,South Korea.

[10]M. Bajcsy, M. Mintz, and E. Liebman, A Common Framework for Edge Detection and Region Growing, Univ. Pennsylvania GASP Lab, Tech. Rep. 61, 1986.