A NEW APPROACH OF WATERSHED
ALGORITHM USING DISTANCE
TRANSFORM APPLIED TO IMAGE
SEGMENTATION

P.P.Acharjya; A. Sinha; S.Sarkar; S.Dey; S.Ghosh

A NEW APPROACH OF WATERSHED ALGORITHM USING DISTANCE TRANSFORM APPLIED TO IMAGE SEGMENTATION

P.P.Acharjya, A. Sinha, S.Sarkar, S.Dey, S.Ghosh
Department of CSE, Bengal Institute of Technology and Management, Santiniketan, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

A new approach of Watershed Algorithm using Distance Transform is applied to Image Segmentation is discussed in this paper. After applying Watershed Algorithm we get an over-segmented image. The watershed algorithm with Laplacian of Gaussian (LoG) edge detector is used to detect the edges of the image and produce an image which is less over-segmented. The proposed algorithm will detect a detailed and an accurate image.

Keywords

Image Segmentation, Laplacian of Gaussian, Over Segmentation, Watershed Transform

INTRODUCTION

Image segmentation separates [1-3] the objects and components of the image. There are two ways of approaching image segmentation. The first in boundary based and detects local changes. The second is region-based and searches for pixel and region similarities. More precisely, image segmentation is the process of assigning label to every pixel in an image such that pixels with the same label share certain visual characteristics. It is based on discontinuity and similarity of image intensity values [4-9]. The approach is to partition an image based on abrupt changes in intensity value such as edges. The result of image segmentation is a set of segments that collectively cover the entire image, or a set of contours extracted from the image. After applying image segmentation to the image it can be used for 3D reconstruction in various fields. For intensity images four popular methods are there for image segmentation which includes threshold techniques, edge based methods, region based techniques and connectivity-preserving relaxation methods.

Edge detection is by far the most common approach for detecting meaningful discontinuities in intensity values. The points at which image brightness changes sharply are typically organized into a set of curved line segments called edges. Edge detection is a fundamental tool in image processing, machine vision and computer vision. An edgedetection filter can also be used to improve the appearance of blurred or anti-aliased image streams [10-11]. Edges can be detected using various edge detectors. These include Sobel, Prewitt, Roberts, Laplacian of Gaussian (LoG), Zero crossings and Canny. In this paper we have used LoG to detect the edge of the image. The watershed transform is a powerful morphological tool for image segmentation. Unfortunately, the watershed segmentation technique leads to an over segmentation problem [12-13]. Beucher and Lantuejoul were the first to apply the concept of watershed to digital image segmentation problems. A good number of works has already been carried out on watershed segmentation and these are available in the published or online literature. [14-16]. The Laplacian of Gaussian edge detection operator is used with the watershed algorithm to generate the final segmentation results with less over segmentation. The default mask of LoG is 5x5. The mask can be modified for obtaining a better segmentation result. The end result is to highlight edges. This paper is divided into various sections. Section 2 introduces a brief description on Watershed Algorithm. Section 3 introduces the Mathematical Formulation related to Watershed Algorithm. Section 4 introduces the Watershed with Distance Transform. Section 5 presents the proposed scheme. The experimental results are discussed in section 6 and we finish this paper with some concluding remarks with section 7.

WATERSHED ALGORITHM

Watershed transform is the technique which is commonly used in image segmentation. It is now being recognized as a powerful method used in image segmentation due to its many advantages such as simplicity, speed and complete division of the image. Watershed transform or Watershed Algorithm is based on grey-scale morphology. It is classified as a region-based segmentation approach. Even when the target regions having low contrast and week boundaries, watershed transformation can provide closed contours. When a landscape or topographic relief is flooded with water, the divide lines of the domains of rain falling over the regions forms the watersheds. Intuitively, a drop of water falling on a topographic relief flows towards the "nearest" minimum. The "nearest" minimum is that minimum which lies at the end of the path of steepest descent. In terms of topography, this occurs if the point lies in the catchment basin of that minimum. An alternative approach is to imagine the landscape being immersed in a lake in which holes are pierced in the local minima is called the catchment basin. Water will be filled up at these starting local minima and at points where water coming from different basins would meet and dams will be built. When the water level reaches the highest peak in the landscape the process is stopped. As a result, the landscape is partitioned into regions or basins separated by dams, called watershed lines or simply watersheds.

MATHEMATICAL FORMULATION

The watershed of f is the set of points which do not belong to any catchment basin:

So, the watershed transform of f assigns labels to the points of D, such that (i) different catchment basins are uniquely labeled, and (ii) a special label W is assigned to all points of the watershed of f.

WATERSHED WITH DISTANCE TRANSFORM

Distance transform is a common tool used in watershed transform for image segmentation. The concept is, the distance from every pixel to its nearest non zero valued pixel. Every single valued pixel has a distance transform value of 0, as it is the closest non zero valued pixel of itself. An example is given below, of a binary matrix and its distance transform value.

PROPOSED APPROACH

We have tried for a new approach on watershed algorithm for obtaining better result in image segmentation. For this a new algorithm is developed for getting better segmented image, and less over-segmentation. In the proposed approach, firstly a color image is chosen, and converted to greyscale image. Secondly, „log? operator is used for edge detection. Thirdly image complement is obtained from the previous resulted image. And finally watershed transformation using distance transform is applied to the image to get the desired result. A flowchart of this approach is given below:

EXPERIMENTAL RESULTS AND DISCUSSION

A new approach has been taken, for getting better result through watershed transformation. For that a new algorithm is developed as discussed earlier. Three different pictures are taken, of different dimensions. The first picture is, well known Lena image (400 by 225), and the others are, a image of nuts (666 by 500) and a image of a lady (256 by 256). The new developed algorithm is applied on these pictures, for better segmented images. The original images are shown in Figure 1 respectively. The watershed segmented images using conventional method which is obtained using watershed algorithm directly from a grayscale images are shown in figure 3respectively. The final segmented images using the proposed approach are shown in figure 3 respectively.

From the above images we can see that we have got sharp and prominent watershed lines with the proposed approach. The calculated entropy, PSNR and MSE of the segmented images are also presented below.

CONCLUSION

Edge Detection is an indispensable part of image processing. In this paper we have successfully introduced a new approach to edge detection technique which is based on Watershed Algorithm using Distance Transform. In the above table the relative performance of the 3 image are shown. Hence, it has been concluded that the new approach has certainly shown a difference in the PSNR and Entropy.

Tables at a glance

Table 1

Figures at a glance


Figure 1	Figure 2	Figure 3	Figure 4

References

A.K.Jain, Fundamentals of digital image processing, Second Edition, Prentice Hall, 2002.

S. Beucher, “Watersheds of functions and picture segmentation,” in Proc. IEEE Int. Conf. Acoustic, Speech, Signal Processing, pp. 1982-`931, 1982.

Gonzalez & Woods, Digital Image Processing, 3rd edition, Prentice Hall India, 2008

S. Beucher, “Watershed, hierarchical segmentation and water fall algorithm,” in Mathematical Morphology and Its Applications to Image Processing, Dordrecht, The Netherlands: Kluwer, 1994, pp. 69–76.

Beucher, S., and Meyer, F. The morphological approach to segmentation: the watershed transformation. In Mathematical Morphology in Image Processing, E. R. Dougherty, Ed. Marcel Dekker, New York, ch. 12, pp. 433-481, 1993.

Beucher, S., and Lantuejoul, C, “Use of watersheds in contour detection”, In Proc. International Work-shop on Image Processing, Real-Time Edge and Motion Detection/Estimation, Rennes, pp.17-21, France, September 1979.

Vicent L. Solille P, Watershed in digital spaces, “An efficient algorithm based immersion simulations,” IEEE Transections PAMI,vol. 13.no6. pp. 538-598, 1991.

M. Couprie and G. Bertrand, “Topological grayscale watershed transformation,” in Proc. SPIE Vision Geometry V, vol. 3168, pp. 136-146, 1997.

C. Riddell, p. Brigger, R. E. Carson and S. L. Bacharach, “The watershed algorithm: a method to segment noisy PET transmission images,” IEEE Trans. Nucl. Sci., vol. 46, no. 3, pp. 713-719, Mar, 1999.

P. Jackway, “Gradient watersheds in morphological scalespace,” IEEE Trans. Image Processing vol. l5, pp. 913–921, June, 1996.

Rafael C. Gonzalez, Richard E. Woods, Steven L. Eddins, “Digital Image Processing Using MATLAB,” Second Edition, GatesmarkPublishing, 2009.

S. Thilagamani, N.Shanthi, “A Novel Recursive Clustering Algorithm for Image Oversegmentation”, European Journal of Scientific Research,Vol.52, No.3, pp.430-436, 2011.

Peter Eggleston, “Understanding Oversegmentation and Region Merging”, Vision Systems Design, December 1, 1998.

M. W. Hansen and W. E. Higgins, “Watershed-based maximum-homogeneity filtering,” IEEE Trans. Image Process., vol. 8, no. 7, pp. 982-988, jul. 1999.

Chi Zhang, Ning Zhang, Chengjun Li, Guoping Wang, "Marker-Controlled Perception-Based Mesh Segmentation," Third International Conference on Image and Graphics (ICIG'04), icig, pp.390-393, 2004.

K. Parvati, B. S. Prakasa Rao and M. Mariya Das, “Image Segmentation Using Gray-Scale Morphology and Marker-ControlledWatershedTransformation”, Discrete Dynamics in Nature and Society,vol. 2008, pp. 1-8, 2008.