Cancer Detection Using Modified Watershed

Cancer Detection Using Modified Watershed

Shanti L. Kadachha, Pinal J. Patel

segmentation, an image is partitioning into regions

Abstract

In this paper the Modified Watershed segmentation technique is propose for cancer detection. Basic watershed mainly suffers from problem of over- segmentation. Modified watershed reduces the over-segmentation using merging process after Initial segmentation. Watershed segmentation is used for initial segmentation. Hence proposed modified watershed algorithm provides better segmentation result.

1. INTRODUCTION

   There are two types of CAD techniques: computer aided detection (CADe) and computer aided diagnosis (CADx). CADe systems have been developed to aid radiologists in localizing suspect regions, leaving the characterization and diagnosis to the radiologist. [1] It only gives the location of suspect lesions by showing prompts to the radiologist, and serves as an aid in the detection task. CADe mainly includes pre-processing step and segmentation, and CADx involves classification task.

   Image segmentation is an important and, perhaps, the most difficult task in image processing. Segmentation refers to the grouping of image elements that exhibit similar characteristics, i.e. subdividing an image into its constituent regions or objects. All subsequent interpretation tasks, such as object recognition and classification, rely heavily on the quality of the segmentation process. [2] It may be defined as decomposing an image into its constituent parts extracting the location and the outline of Objects Of interests. Segmentation techniques mainly divided into two categories. First one is edge based segmentation and second is region based segmentation. Segmentation is very important step in computer aided cancer detection system.

   In edge-based segmentation, image is to partition an image based on changes in intensity, such as edges in an image. And in region based

   that are similar according to a predefined criteria. Region merging, region growing are included in this category. Watershed segmentation is included in edge-based as well as region-based. [3]

   In [4], basic watershed segmentation is used with random walk method. Random walk method is used for pre-processing the image. One limitation is that starting point must be found for random walk. In [5] combination of watershed and thresholding technique is used. Main problem with thresholding is to deciding threshold value. The proposed technique in [6] focuses on the solution of under segmentation problem of low contrast images by applying pre-processing on the input image. The technique for pre-processing on the images is Curvelet transform. It is an approach used to enhance the image contrast when image is degraded. In [7] marker based watershed is used but still there is problem of over-segmentation. Hence in this paper I proposed a method which uses watershed with region merging process.

2. BASIC WATERSHED

   The term watershed comes from geography. Watershed transformation is a morphological based tool for image segmentation. In grey scale mathematical morphology the watershed transformation for image segmentation is originally proposed by Digabel and Lantuejoul (1977) and later improved by Li et. al.(2003).[8]

   Figure 1: Illustration of immersion process of watershed transforms

   The idea of watershed can be view as a landscape immersed in a lake; catchment basins (CB) will be filled up with water starting at each local minimum. Dams must be built where the water coming from different catchment basins may be meeting in order

   to avoid the merging of catchment basins. The water shed lines are defined by the catchment basins divided by the dam at the highest level where the water can reach in the landscape. [5] As a result, watershed lines can separate individual catchment basins in the landscape. Following steps are required for implementing Basic Watershed in MATLAB. [9]

   • Read pre-processed image

   • Compute gradient magnitude

   • Compute Watershed of gradient magnitude

   • and superimpose the gradient on original image

     The division of the image through watershed algorithm relies mostly on an estimation of the gradients. Watershed algorithm mainly depends on Gradient. [5] Hence if there is small noise in image, then small gradients are created which leads to over-segmentation problem. Figure 2 shows the over-segmentation (right).here papsmear images are used for experiment. To reduce this problem Marker-based watershed is used.

     Figure 2: Original image (left) and basic watershed segmented image (right)

3. MARKER-BASED WATERSHED

   In Marker-based watershed segmentation markers are used. A marker is a connected component belonging to an image. The markers include the internal markers, associated with objects of interest, and the external markers, associated with the background. [9] Following steps are required for implementing marker based watershed:

   • Compute gradient magnitude of image

   • Find the regional minima of gradient image(internal marker)

   • Find the background object(external marker)

   • Compute the modified gradient

   • Compute the watershed transform of modified gradient

   • Superimpose modified gradient on original image

     But still there is problem of over segmentation occurs. Hence to overcome this problem modified watershed technique is proposed in this paper. Fig.3 show the result of Marker based watershed segmentation.

     Figure 3: Marker based watershed segmented image

4. PROPOSED MODIFIED WATERSHED

   In proposed modified Watershed algorithm region merging is used after watershed segmentation. Following steps are involved in proposed technique:

   1. Initial Segmentation

      In this step Basic watershed is used for initial segmentation. Based on initial segmentation remaining steps will be performed.

   2. Similarity measure

      After Initial segmentation, image is divided into small regions. Hence based on similarity of region, they have merged. Before this region representation is required for merging process. A region can be described in many aspects, such as the color, edge, texture, shape and size of the region.[10] Color is widely used descriptor because in initial segmentation small regions are varying a lot in size and shape, but high similarity in color. [11]

   3. Object and Background marking

      In this step object and background is marked by user using lines, point or curve. The regions that have pixels inside the object markers are thus called object marker regions(MO), while the regions that have pixels inside the background markers are called background marker regions(MB). After

      object marking, each region will be labeled as one of three kinds of regions: the marker object region, the marker background region and the non-marker region (MN).

   4. Similarity based merging

   In the proposed region merging method also starts from the initial marker regions and all the non- marker regions will be gradually labeled as either object region or background region. Let X be an adjacent region of Y and denote by i=1,2..,x the set of X's adjacent regions. The similarity between X and all its adjacent regions, i.e. i = 1,2,.,x, are calculated. Y

   is a member of . If the similarity between Y and X is the maximal one among all the similarities . We will merge Y and X. Based on similarity between two regions, they are meged together. [12]

   In merging process there are two stages. In the first stage, marker background regions (MB) are merged with their adjacent regions. For each region B MB, we form the set of its adjacent regions SB =

   {} i=1,2,…,r . Then for each and MB, we form its set of adjacent regions =

   }j=1,2,…,k. It is obvious that B . The similarity between Ai and each element in , i.e.

   is calculated. If B and Ai satisfy the

   and so do the non-marker background regions. The first and second stages of the algorithm are executed repeatedly until no new merging occurs. Figure 4 shows the resultant segmented image using Modified Watershed.

   Figure 4: Segmented image using Modified Watershed

   Another example is shown in following figures:

   Figure 5: Original image

   rule (1), i.e.

   ( (1)

   Then B and are merged into one region and the new region will have the same label as region B. Otherwise, B and will not merge. If the regions in MB will not find new merging regions, the first stage ends. After the region merging of this stage, some non-marker back- ground regions will be merged with the corresponding background markers. However, there are still non-marker background regions (MN) which cannot be merged because they have higher similarity scores with each other than with the marker background regions.

   In stage two these non marker background regions (MN) are merged together. In this stage, the non- marker object regions will be fused each other under the guidance of the maximal similarity rule

   Figure 6: Output of Basic watershed

   Figure 7: Output of Marker-based watershed

   Figure 8: Output of Proposed modified watershed

5. CONCLUSION

Segmentation is main task in cancer detection system hence segmentation technique should be effective and efficient to extract region of interest from the medical images. Watershed segmentation technique divides image into regions. Basic Watershed suffers from over-segmentation problem which divides region into very small regions. Marker-based Watershed reduces over- segmentation but not overcome from it. In Proposed Modified Watershed segmentation technique, region merging is used which solve the problem of over-segmentation. Above figures show that proposed modified watershed gives the better segmented result then other techniques.

REFERANCES

1. B. Senthilkumar, G. Umamaheswari , A Review on Computer Aided Detection and Diagnosis – Towards the Treatment of Breast Cancer, European Journal of Scientific Research ,ISSN 1450-216X Vol.52 No.4 (2011), pp.437-452

2. Manisha Bhagwat, R.K.Krishna ,V.E.Pise3, Image Segmentation by Improved Watershed Transformation in Programming Environment MATLAB, International

   Journal of Computer Science & Communication Vol. 1,

   No. 2, July-December 2010, pp. 171-174

3. Mokhled S. AL-TARAWNEH, Lung Cancer Detection Using Image Processing Techniques, Leonardo Electronic Journal of Practices and Technologies ,ISSN 1583-1078

   ,Issue 20, January-June 2012, p. 147-158B. Smith, An approach to graphs of linear forms (Unpublished work style), unpublished.

4. Malik Sikandar Hayat Khiyal, Aihab Khan, and Amna Bibi, Modified Watershed Algorithm for Segmentation of 2D Images, Informing Science and Information Technology Volume 6, 2009.

5. Anam Mustaqeem ,Ali Javed ,Tehseen Fatima, An Efficient Brain Tumor Detection Algorithm Using Watershed & Thresholding Based Segmentation, I.J. Image, Graphics and Signal Processing, 2012, 10, 34-39.

6. Mohamed Ali HAMDI, Modified Algorithm marker- controlled watershed transform for Image segmentation Based on Curvelet Threshold, Canadian Journal on Image Processing and Computer Vision Vol. 2 No. 8, December 2011

7. ] R.Kiruthikaa, S.Govindaraju, An Implementation Of Markers Based Watershed Segmentation Using Fpga Processor, pdf online.

8. Li, H., Elmoataz, A., Fadili, J. & Ruan, An improved image segmentation approach based on level set and mathematical morphology,2003

9. Gonzalez Woods Eddins, Digital image processing using Matlab

10. S. Birchfield, Elliptical head tracking using intensity gradients and color histograms, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 1998, pp. 232237.

11. M.J. Swain, D.H. Ballard, Color indexing, International Journal of Computer Vision 7 (1) (2002) 1132.

12. Jifeng Ninga, LeiZhanga, DavidZhanga, ChengkeWub,Interactive Image segmentation by maximum similarity region merging, Elsevier,2009