Medical Image Segmentation Based on Watershed Transformation and Rough Sets Ran Li Dept. of Electronic and Communication Engineering North China Electric Power University Baoding, China liran800524sina.com AbstractTraditional watershed algorithm often causes over-segmentation because of its high sensitivity to the weak edge and the noise. To overcome this drawback and in light of the characteristics of medical image, a new segmentation algorithm based on watershed transformation and rough set theory is proposed. The original image is partitioned into the edge-detail sub-image and smooth sub-image according to indiscernibility relation of rough set theory. Two enhancement methods are designed for the two sub-images, and watershed transformation is used for the further segmentation in the smooth sub-image. Finally, combine the two processed sub-images to obtain the segmentation result. The proposed algorithm has been executed on Magnetic Resonance Imaging (MRI) image, the analysis of compare between conventional watershed algorithm and the proposed algorithm is given. The experimental result shows that this method is efficient to restrain the over-segmentation, thus obtaining good segmentation results. Keywords-image segmentation; watershed segmentation; rough set; over-segmentation; MRI image I. INTRODUCTION Image segmentation is a process to partition an image into non-overlap regions, which is an important step in image processing area and is fundamental for analysis and identification in image processing 1. Image segmentation is an important process for most of medical image analysis tasks, which is basic for higher-level image comprehension and analysis. A good segmentation will benefit clinicians and patients as it provides important information for surgical planning, early disease detection and 3-D visualization 23. Influenced by the complexity and variety of medical image, fuzzy edge of object, the asymmetry and squirming of human organ and noise caused by various medical image equipments(such as Computed Tomography (CT), Magnetic Resonance Imaging (MRI), Positron Emission Tomography (PET), etc.), medical image segmentation is a very difficult task. In order to solve the problems of medical image segmentation, many practical means have been advanced. These include watershed segmentation45, thresholding method6, region-growing method7, fuzzy cluster method8 and so on. The watershed algorithm is a classical and effective segmentation method by which one-pixel-wide continuous edge can be extracted. More importantly, it has the advantages of high segmentation precision and accurate positioning, and it is a fast, simple and intuitive method. Its drawbacks will include over-segmentation and sensitivity to noise3. Several methods have been proposed to overcome these drawbacks. Watersnakes algorithm is a method of minimal energy, which improves the accuracy and continuity of edge location9. However, over-segmentation is not solved effectively. Method of combining preprocess and region merging in 5 can alleviate over-segmentation appropriately, meanwhile, it makes segmentation more complex. In this work, with a view to the preprocessing, we propose a watershed segmentation algorithm of introducing rough set. First, partition original image into edge-detail sub-image and smooth sub-image using the rough set theory. Then, the two sub-images are enhanced via different enhancement methods. Moreover, further segmentation is practiced by watershed segmentation algorithm in the enhanced smooth sub-image. Finally, the two processed sub-images are fused into ultimate image. The experiment result shows that the method is effective for inhibiting over-segmentation. The used elementary theories are in section 2 and the proposed methodology is described in section 3. Results and discussion are provided in section 4, with the paper concluded in section 5. II. SUB-IMAGE DIVISION BASED ON ROUGH SET A. Rough Set Theory Knowledge system is an important concept in rough set theory, which has classification capability10. Generally speaking, information systems are used to represent knowledge. Rough set theory forms its information system by using undistinguished relationship to divide information1112, and the relationship between similar individuals is indiscernibility relation that is a kind of equivalent relation. When giving a finite and nonempty set U called the universe of discourse, and suppose R is an equivalence relation, the knowledge system ( , )KU R= is an approximate space. If x is an object of U, while X is a subset of U, then, ( )R x denotes a set composed of the 978-1-4244-4713-8/10/$25.00 2010 IEEEobjects which has the undistinguished relation from x. When X can be described by R accurately, Xis definable and is called accurate set of R. When X can not be described by R accurately, X is called the rough set of R. The universe of discourse of the researched object is U. The subset XU denotes the concept in set U. The knowledge in set U is represented as the group-set of conception. The special sort is composed of the knowledge system defined by the group in U. Normally the classification is replaced by the equivalence relation. If the equivalence relationship in U is denoted by R, objects of Ucan be represented as equivalent class-clusters based on R, marked as /UR. While PR and P , the intersection of all the equivalence relationship in P(marked as P) is also a equivalence relation, which is called undistinguished relation of P, marked as ( )ind P: ()ind PRXX= PR (1) If the certain knowledge system ( , )KU R= is given, for subset XU and an equivalence relationship ()Rind K, the set X can be classified according to the basic set of R. A category in Rcontaining an object xU is denoted by R(1,1)( ,1)(1,1)(1,1)( ,1)(1,1)Yf ijf i jf ijf ijf i jf ij=+ (10) Where i and j (1iM ,1jN) are coordinates of ( , )f i j. X denotes the sum of horizontal gradient, and Ydenotes the sum of vertical gradient. The pixel whose gradient is above threshold (W) belongs to edge-details region of the image, while the pixel whose gradient is below or equal to W belongs to smooth region of the image. Condition attribute is defined as 12,Cc c=. Where 1c stands for gradient attribute and 2c stands for noise attribute. 10,1c = is the gradient attribute of pixel. Where 1 stands for the pixel with large gradient which satisfies the inequality ( , )I i jW, where 0 stands for the pixel with small gradient which satisfies the inequality ( , )I i jW. 20,1c = is the noise attribute of pixel. Where 0 denotes that the absolute values of average gray difference between block (s) of 3 3 and its adjacent blocks are all lower than some threshold (represented by Q), where 1 denotes that the absolute values are all higher than Q. The pixels of one image are categorized by attribute C. First, the image is divided into two sub-images based on 1c, and the equivalent relation is defined as follows: 1( )( , )R xx I i jW= (11) Where 1( )R x stands for set of large gradient pixels, and 1( )R x stands for set of small gradient pixels. Then the image is divided into two sub-images based on 2c. Equivalent relation 2( )R s denotes set composed of all noise pixels, and 2( )R s is defined as follows: 21,1( )()()ijijijijR ssm sm sQ= (12) Where 11,111()(,)9i jklm sf ik jl=+ (13) ,()i jm s denotes average gray value of 3 3 sub-block. Where 1,1ijs stands for adjacent block of , i js. Sub-block , i js and 1,1ijs constitute macro-block. Average gray value of the macro-block is as follows: 11,1119i ji k j lklMs+= (14) Combine the two kinds of sub-images obtained by different division manner. We obtain the de-noise set of large gradient pixels (represented by 1F) and the de-noise set of small gradient pixels (represented by 2F). 1F is corresponding to the edge of the image, and 2F is corresponding to the smooth region of the image. They are defined as follows: 112( )( )FR xR s= (15) 212( )( )FR xR s= (16) 1F and 2F are pixel sets that need to be further processed by enhancement and segmentation. III. ALGORITHM ILLUSTRATION The two sub-images need to be processed in different way, the algorithm is performed based on the following procedure: 1) Obtain the gradients of all pixels in image F according to (8), (9) and (10), and ( , )I i j stands for the gradient image. 2) Generate two sub-images (1F and 2F) of F according to (15) and (16). Define the gray value of blank position of the two sub-images. To 1F, the gray values of low-gradient pixels are determined as half of the maximum gray-level, and the gray values of noise pixels are ijM obtained by (14). The complemented sub-image of 1F is denoted by 1F. Adopt the same method complement 2F, and the complemented sub-image of 2F is denoted by 2F. 3) Enhance 1F and 2F by different means. Enhance 1F by exponential transform method whose transform equation is as follows: 1( )()g xF= (17) Where and are parameters. Enhance 2F by the method of histogram equalization. 4) Implement watershed segmentation to enhanced 2F. Remove the pixels filled in procedure 2), and then obtain 1F and 2F. Combine 2F with 1F, and make sure the gray values of the pixels in combined image are all less than the gray-level of original image. So we obtain the segmentation result. Obviously, the above algorithm is composed of three parts: classifying pixels of the image by property C, enhancement and segmentation. The original image is divided into edge-detail and smooth sub-images. The edge-detail sub-image is enhanced by exponential transform method, which can change the dynamic range of the image by gray stretch. The gray gradient of pixels nearby edge are even larger by choosing suitable parameters ( and ). While adopt the method of histogram equalization to smooth sub-image, which weaken the noise. This method is accord with the properties of human visual system (HVS). Watershed transform is only implemented in smooth part of the image, which can improve the over segmentation problem. IV. SIMULATION RESULTS AND DISCUSSIONS The proposed method is experimented on a MRI image to illustrate the effectiveness of our proposed method. The image we select is a human brain MRI image provided by a hospital. Fig. 2(a) is original image. Fig. 2(b) is edge sub-image, and Fig. 2(c) is smooth sub-image. The segmentation result of smooth sub-image is show in Fig. 2(d). The ultimate segmentation result is shown in Fig. 2(e). Fig. 2(f) shows the comparison of segmentation result with the implementation of the conventional watershed transformation on the original image. (a) (b) (c) (d) (e) (f) Figure 2. (a) Original MRI image, (b) Edge sub-image, (c) Smooth sub-image, (d)Smooth sub-image after watershed transform, (e) Segmentation result of our proposed method, (f) Segmentation result of conventional watershed segmentation From Fig. 2(f), we can see over-segmentation phenomenon. The image is segmented into a large number of small regions in Fig. 2(f), and the regions are scattered. Using the method proposed in our paper, the over-segmentation problem is evidently improved (shown in Fig. 2(e) ). In Fig. 2(e), the brain image is divided into white matter, grey matter, bone, other tissues and background. In the experiment, we set 0.395W =, 0.5Q =, 1.25= and 0.8=. V. CONCLUSIONS Excellent segmentation effect can not be obtained because of the drawbacks of conventional watershed algorithm. Medical images contain much information of the research object, which has complex spatial correlation and uncertainty. Rough set theory is as a mathematical tool to describe problems with fuzzy and uncertainty knowledge. It can deal with uncertain information by special way and can deal with the imprecision and incomplete information effectively. So if rough set theory is applied in image segmentation, the segmentation result will be good. In this paper, a new segmentation algorithm in which rough set theory and watershed transform are effectively combined is presented. The image is divided into edge sub-image and smooth sub-image, and the two sub-images are implemented by different segmentation method. Watershed transform is only used on the smooth sub-image. The experimental results show our proposed method is effective in improving over segmentation problem and relieve the influence of noise in watershed segmentation process. But the edges of the result image obtained by the above-mentioned method are fuzzy in some degree. And this is our further work. REFERENCES 1 Dong Min, Li Xiangpeng, and Wang Li, “Image segmentation based on rough membership function, ” in Proc. IEEE Int. Conf. on Granular Computing, vol.1, pp. 141-144, 2005. 2 H.P.Ng, S.Huang. S.H.Ong, K.W.C.Foong, P.S.Goh, and W.L.Nowinski, “Medical image segmentation using watershed segmentation with texture-based region merging, ” in Proc. 30th Annual Int. Conf. of Engineering in Medicine and Biology Society, pp. 4039-4042, 2008. 3 H.P.Ng, S.H.ong, K.W.C.Foong, P.S.Goh, and W.L.Nowinski, “Medical image segmentation using K-means clustering and improver watershed algorithm,” in Proc. IEEE Southwest Symposium on Image Analysis and Interpretation, pp.61-65, 2006. 4 L. Vincent and P. Soille, “Watersheds in digital spaces: an efficient algorithm based on immersion simulations,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, No. 6, pp. 538-598, June 1991. 5 K. Haris, S. N. Efstratiadis, N. Maglaveras, and A. K. Katsaggelos, “Hybrid image segmentation using watersheds and fast region merging,” IEEE Trans. Image Processing, vol. 7, No. 12, pp.1684-1699, Dec. 1998. 6 D. Y. Kim, J. H. Kim, S.M. Noh, and J.W. Park, “Pulmonary nodule detection using chest CT images,” Acta Radiol, vol. 44, No. 3, pp. 252-257, May 2003. 7 F. Iseki, T. Baigalmaa, H. Kobatake, H. Omatsu, and R. Kakinuma, “Extraction of 3D tree structure of blood vessels in lung area from chest CT images,” in H.U. Lemke, M.W. Vannier, K.Inamura, A.G.Farman, Computer assisted radiology and surgery, vol.1165 pp.45-50, 1998. 8 C. W. Chen, J. Luo, K. J.Parker, and T.S.Huang, “A knowledge-based approach to volumetric medical image segmentation,” in Proc. IEEE Int. Conf. on Image Processing, vol. 3, pp.493-497, Nov. 1993. 9 T. Hieu, M. Marcel, and V. REIN, “Watersnakes: Energy-driven watershed segmentation,” IEEE Tran. Pattern Analysis and Machine Intelligence, vol.25, pp. 330-342, March 2003. 10 Y. Y. Yao, “Constructive and algebraic methods of the theory of rough sets,” Int. Journal of Information Sciences, vol. 109, pp. 21-47, Aug. 1998. 11 X.S. Wen, “Pattern recognition and condition monitoring,” Publishing House of Science, Beijing, 2006. 12 Z.Y. Che, M.G. Xia, and Y. He, “Image fusion algorithm using rough sets and wavelet analysis,” Journal of Electronics optics and control, vol. 12, No. 1, pp.18-21, Feb 2005.