International Journal of Fuzzy Mathematics and Systems. ISSN 2248-9940 Volume 2, Number 1 (2012), pp. 1–10 © Research India Publications http://www.ripublication.com/ijfms.htm Medical Image Segmentation using Fuzzy Binary Relation Rogi Jacob Department of Mathematics, U.C. College, Mahatma Gandhi University, Kerala, India. E-mail: [email protected] Sunny Kuriakose A Department of Mathematics, U.C.College, Mahatma Gandhi University, Kerala, India E-mail: [email protected] Sony George International School of Photonics, Cochin University of Science and Technology, Kerala, India E-mail: [email protected] Abstract Image segmentation is one of the most challenging aspects of image processing, particularly in the case of medical images. It is rather difficult to extract and characterise the anatomical structures with respect to some input features or expert knowledge. Even though several methods are available in the literature, all of them have certain limitations. Therefore it is worth exploring better methods. In this article, we introduce a clustering method for image segmentation based on fuzzy binary relation which produces the clusters automatically. The proposed method is proved to be superior to those are already in existence. This is substantiated with the help of two examples. AMS subject classification: Keywords: Fuzzy binary relation, Equivalence relation, α − cut, Segmentation. 2 1. Rogi Jacob, Sunny Kuriakose A, and Sony George Introduction Image segmentation is one of the most challenging tasks in image processing. It comes from the objective of partitioning or classifying an image into regions and is useful in visualisation of different objects presented in the images. Even though several methods are available in literature, [1] [2] [5] [6] [7] accurate image segmentation is very difficult in most of the image processing application especially in medical images. Medical image segmentation has been an active research area for a long time. Images obtained using computed tomography and MRI images are very high resolution images and mostly contain unknown noise, inhomogenity and complicated structure. The analysis of this high resolution images are very complex due to its vagueness and imprecision of boundaries existing in the anatomical structures. In short, most of the images are fuzzy in nature. There are different types of fuzzy based methods available such as fuzzy c-means clustering [11] [13], contour methods [4] [12], entropy method [6] [7] [8] etc, even if they are powerful in some aspects, they lack in many ways [1] [6]. In fuzzy c-means or kmeans algorithms, we should specify the number of clusters in advance [11]. The contour methods can only segment objects which are ring, compact spherical or a combination of ring-shaped objects and it does not produce better segmented results for objects having other shapes [4] [12]. The proper selection of an optimum threshold is a disadvantage of thresholding and entropy methods [6] [8] [15] [12]. In this paper, we propose a segmentation technique based on fuzzy binary relation. Despite the fact that there are many segmentation algorithms for medical images, [1 − 8] there is no generic algorithm for totally successful segmentation of medical images. For example consider clustering technique in [1] for computed tomography images but it may fail for X-ray images. Also in segmentation using fuzzy similarity relation [1], only distance function of Minkowski’s class is used to build the relation from all pixels of image. Here we build a fuzzy binary relation from the distinct pixels of the image so that it considerably reduces the computational complexity. This paper is organized as follows. In section 2 we briefly state and review the definition and results of fuzzy similarity relation and crisp equivalence relation. In section 3, a definition of segmentation method is given. Section 4 presents the image segmentation method based on the fuzzy binary relation. Section 5 discusses the complexity of algorithm. Segmentation results using X-ray image of kidney and MRI image of brain are presented in Section 6. Concluding remarks are given in Section 7. 2. Preliminaries In this section, we recall certain standard defnitions already in literature. Let A and B be any two sets, then any crisp relation from A to B is a subset of A × B. We can represent a binary fuzzy relation γ : X → Y using membership matrices and any fuzzy binary relation from A to B as a fuzzy subset of A × B. γ −1 denote inverse of γ . Let γ 1 : X → Y and γ 2 : Y → Z be two binary fuzzy relation. Then the standard Medical Image Segmentation using Fuzzy Binary Relation 3 composition of relation γ 1 and γ 2 is another fuzzy relation γ 3 : X → Z given by: max γ 3 (x, z) =y ∈ Y min γ 1 (x, y), γ 2 (y, z) ∀x ∈ X, y ∈ Y, z ∈ Z A crisp relation R on X is said to be i. reflexive if xRx∀x ∈ X. ii. symmetric if R(x, y) = R(y, x)∀x, y ∈ X. iii. transitive if xRy,yRz then xRz ∀x, y, z ∈ X. A crisp relation R is said to be a tolerance relation if it is reflexive and symmetric. A crisp relation R is said to be an equivalence relation if R is reflexive, symmetric and transitive. If the crisp relation R is only a tolerance relation, we can make it an equivalence relation using the following algorithm: Warshall’s algorithm (To compute transitive closure matrix)[1] Step 1 : assume T = R Step 2 : For k = 1 to n do For i = 1 to n do For j = 1 to n do T (i, j ) = T (i, j ) + (T (i, k) + T (k, j ) Step 3 : Terminates with R’ = T We can extend the idea of equivalence relation in the framework of fuzzy set as given in the following defnition. Defnition 2.1. A binary fuzzy relation γ is said to be an equivalence relation if 1. γ is reflexive i.e.γ (x, x) = 1∀x ∈ X 2. γ is symmetric i.e.γ (x, y) = γ (y, x)∀x ∈ X, y ∈ Y 3. γ is transitive i.e.γ (x, y) = λ1 andγ (y, z) = λ2 then ∃λ3 such that γ (x, z) = λ3 ≥ λ1 If γ satisfies only first two conditions, then γ is said to be a fuzzy similarity relation and we can make a fuzzy equivalence relation by using Warshall’s algorithm explained in above section. Theorem 2.2. Let X be any set and let γ be a fuzzy similarity relation defined on X, then each alpha cut α γ is a crisp equivalence relation on X. Proof. Let X be any set and let γ be a fuzzy similarity relation on X. Case 1 4 Rogi Jacob, Sunny Kuriakose A, and Sony George α γ is reflexive For, γ is reflexive ⇒ ∀x ∈ X, γ (x, x) = 1 therefore we can assign a characteristic function to the set α γ such that 1 if x ∈ A α χx( γ ) = 0 if x ∈ /A Hence α γ is reflexive. Case 2 α γ is Symmetric For, γ is symmetric ⇒ γ (x, y) = γ (y, x) α γ (x, y) = {(x, y) ∈ X × Y/γ (x, y) ≥ α} = {(x, y) ∈ X × Y/γ (y, x) ≥ α} = α γ (y, x) Hence α γ is symmetric. Case 3 If α γ is not transitive, we can make it a transitive relation by using Warshall’s algorithm. Theorem 2.3. Let X be any set and let γ be a fuzzy similarity relation defined on X. Also let α ∈ (γ ), level set then the number of partition π (α γ ) of a given set X increases if the value of α increases. Proof. Let (γ ) = {α 1 , α 2 , . . . , α n } , α i ∈ [0, 1] such that α1 ≤ α2 ≤ · · · ≤ αn. α Let (γ ) = π i γ ∈ [0, 1] be the partition of X. From the above defnitions it is clear that if α 1 ≤ α 2 then π α2 γ ⊇ π α1 γ i.e the cardinality of α γ is greater than or equal to cardinality π 1 γ . Also if α 2 ≤ α 3 then by above steps we’ve π α3 γ ⊇ π α2 γ π α 2 Proceeding like this, we’ve α α π n γ ≥ π n−1 γ Hence if the value of α increases the number of partition also increases. Medical Image Segmentation using Fuzzy Binary Relation 5 Every fuzzy relation can be uniquely represented in terms of its alpha cuts. [9] [10] i.e. γ = α • α γ , where α γ is crisp relation over X and α ∈ [0, 1]. From Theorem 1 it is clear that if γ is a fuzzy equivalence relation on X then each alpha cut, α γ is a crisp equivalence relation on X. Also we know that each equivalence relation groups elements that are equivalent under the relation into disjoint classes and each equivalence class forms a partition on X. Let π α γ denote the partition corresponding to the equivalence relation α γ and the union of all partitions, we get nonempty set X. Two elements x and y belong to the same partition if γ (x, y) ≥ α. If α ≥ β then the partitions are nested in the sense that π (α γ ) is a refinement of π(β γ ). 3. Segmentation method Clustering of data is very important in statistical analysis. [2] By finding the structure, we can classify data according to similar patterns, attributes, features and other characteristics. Image segmentation is also the classification of data into different clusters according to some pre-defined criteria or not. [1] Image segmentation can be generally defined as follows: Defnition 3.1. Let X be the entire image regions and let Y = {y1 , y2 , . . . , yn } be a finite family of connected non empty subsets (clusters of X) and R be one argument homogeneity predicate, defined over clusters of connected pixels. Then image segmentation is a partition of the set X into a finite family of connected non empty subsets of X {y1 , y2 , . . . , yn } st 1. Yi ∩ Yj = φf ori = j (i, j ∈ {1, 2, . . . , n} 2. n Yi = X i=1 3. R(Yi )= true for any Yi ⊂ X and 4. A(Yi ∪ Yj )= false (for any two different Yi , Yj ⊂ X) 4. The Proposed method An automatic segmentation method based on fuzzy binary relation is presented below. The proposed technique is based on an input image X and user defined fuzzy binary relation R on X. This algorithm converts given fuzzy binary relation into a fuzzy similarity relation on X. For each value of α, in the level set of R, it considers α R and based on this α R generates the segmented image S. If it is difficult to define a fuzzy relation R, then the algorithm will work with default relation. 6 Rogi Jacob, Sunny Kuriakose A, and Sony George Definition 4.1. Let X = {x1 , x2 , . . . , xn } be a subset of R m , where n is the number of distinct elements of data set and where m = 2 for grey scale images or m = 3 for color images using RGB space. Then fuzzy relation γ on X can be defined as: γ : X × X → [0, 1] such that ⎧ 1 ⎪ ⎨ 2 if xj > 0 → (1) γ (xi , xj ) = 1 + xi − xj ⎪ ⎩ 1 if xj = 0 Algorithm Input : X, R Output : S Step 1 : Input the original image X = {x1 , x2 , . . . , xn } which is a subset of R m , where n is the number of distinct pixels of X and m = 2 for grey scale images or m = 3 for color images using RGB space. Step 2 : Use (1) in definition 3 or input user defined relation. Step 3 : Find the inverse relation γ −1 of γ . Step 4 : Compute a fuzzy similarity relation Q (Step 2 and Step 3) Step 5 : Choose an α ∈ (Q) Step 6 : Obtain an equivalence relation α Q from Step 5 Step 7 : Take the image clusters as equivalence classes obtain under the partition induced by α Q Step 8 : Generate the segmented image S with respect to image clusters, obtained in step 7 and thus stops algorithm. The complexity of proposed algorithm is O(n3 ) and which shows that algoritm is efficient or fast [17]. 5. Segmentation Results For the illustration of the proposed algorithm, consider the image given above, where the relation given in definition 3 is used. The proposed technique converts the fuzzy binary relation to fuzzy similarity relation and by selecting an arbitrary α produces image clusters automatically. Fig 1(a) is the MRI image of a human brain. The boundaries between the different parts of human brain is not clear. The output produced using different methods are given in Fig.1(b)-(d). But in the segmented image (Fig 1(b)) the main parts of human brain such as telencephalon, mesencephalon, cerebellum etc can be observed very clearly. Consider the Aortic angiogram of kidneys and blood vessels (Image courtesy of Dr.Thomas R.Gest) shown in Fig 2(a). The kidneys and blood vessels in lower part are segmented clearly by proposed algorithm. As for a comparison other images are produced using fuzzy c-means algorithm and k-means. All the segmented results are obtained with the help of MATLAB. Medical Image Segmentation using Fuzzy Binary Relation 7 The proposed algorithm is tested for different types of medical images and new results are obtained. The computation time is fairly small in comparison with the fuzzy c-means algorithm. The selection of α is explained below: Let (Q) = {α 1 , α 2 , . . . , α n } be the level set of fuzzy similarity relation as obtained n from algorithm and α ∈ [0, 1]. Let n be the total number of elements in , the β 1 = 4 n denote the first quartile number, the β 2 = denote the second quartile number and the 2 3n β3 = denote the third quartile number. 4 Define k1 = β + β3 β1 + β2 and k2 = 2 . 2 2 8 Rogi Jacob, Sunny Kuriakose A, and Sony George Choose an α from level set such that k1 + k2 ± β 1 th item = α 2 . The quality of segmentation results obtained using values of α and different binary relation is summarized in Table1: Table 1: Segmentation using different relations Relations |X − Y | DEFAULT CITYBLOCK MINKOWSKI-3 MINKOWSKI-5 CHEBYCHEV MOD(X,Y) REM(X,Y) Relations |X − Y | DEFAULT CITYBLOCK MINKOWSKI-3 MINKOWSKI-5 CHEBYCHEV MOD(X,Y) REM(X,Y) MRI Image α = 0.0063 α = 0.0049 Good Better Good Better Good Better Good Better Good Better Good Better Poor(α = 0.0258) Very Poor(α = 0.0135) Poor(α = 0.0258) Very Poor(α = 0.0135) Kidney Image α = 0.0112 α = 0.0067 Better Good Better Good Better Good Better Good Better Good Better Good Very Poor(α = 0.0321) Poor(α = 0.0144) Very Poor(α = 0.0321) Poor(α = 0.0144) From the above discussions, it appears that the overall performance of the proposed method is consistently satisfactory compared to other clustering techniques. [11] [13] 6. Conclusion Automatic medical image segmentation for medical images using fuzzy binary relation is proposed. This approach is relevant to medical image segmentation as well as it is applicable to other fields. From the preceding sections it is clear that the complexity of algorithm is O(n3 ). The α values can be accurately predicted by neural networks incorporated with the proposed technique. Medical Image Segmentation using Fuzzy Binary Relation 9 References [1] Martin, Tabakov, A Fuzzy segmentation method for computed tomography Images, Int. J. Intelligent Information and Database Systems, 1(1):79–89, 2007. [2] Martin, Tabakov, A Fuzzy Clustering technique for medical image segmentation, International symposium on evolving fuzzy systems, pp. 118–122, 2006. [3] Pierre-Louis, Bazin, and Dzung, L. Pham., Homeomorphic brain image segmentation with topological and statistical atlases, Medical Image Analysis, 12:616–625, 2008. [4] Anke, Neumann, Graphical Gaussian Shape Models and their Application to Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(3):316–329, 2003. [5] M, Ameer Ali, Laurence, S. Dooley, and Gour, C. Karmakar, Object based image segmentation using Fuzzy Clusturing, ICASSP’06, IEEE, pp. II-105-ii-108, 2006. [6] Nikhil, R. Pal, and Sankar, K. Pal, Entropy:A New Definition and its Applications, IEEE Transactions on Systems, Man, and Cybernetics, 21(5):1260–1270, 1991. [7] Rogi Jacob, and Sunny, Kuriakose A., Some new measures of entropy using Fuzzy Cardinality, International Journal of Fuzzy Mathematics, (accepted), 2010. [8] El-Feghi, S. Huang M.A., Sid. Hameed, and M.Ahamadi, X-ray image segmentation using auto adaptive fuzzy index measure, 47th International Midwest Symposium on circuits and systems, IEEE, pp. 499–502, 2004. [9] Yager, R.R., Some properties of fuzzy relationships, Cybernetics and Systems, 12(1-2):123–140, 1981. [10] Zadeh, L.A, Similarity relations and fuzzy orderings, Information Sciences, 3(2):177–200, 1971. [11] Mohammad, Ali. Balafar, ABD, Rahman Ramli, M. Iqbal Saripan, and Syamsiah Mashohor, Medical image segmentation using fuzzy c-mean(FCM), bayesian method and user interaction, Proceedings of the 2008 International Conference on Wavelet Analysis and Pattern Recognition, Hong Kong, pp. 68–73, 2008. [12] P.A. Bromiley, and N.A. Thacker, Multi-dimensional Medical Image Segmentation with Partial Volume and Gradient Modelling, BMVA, 2:1–22, 2008. [13] Dzung L. Pham, and Jerry L. Prince, An adaptive Fuzzy c-means Algorithm for image segmentation in the presence of intensity homogenities, Elsivier, 1998 (pre print). [14] Ety. Navon, Ofer Millerl, Amir Averbuch*, Color image segmentation based on adaptive local thresholds, Image and Vision Computing, 23:69–85, 2005. [15] Tan. Ou., Jia. Chunguang, Dum Huilong, and Lu. Weixue, Automatic Segmentation and Classification of Human Brain Images Based On TT Atlas, Proceedings of the 10 Rogi Jacob, Sunny Kuriakose A, and Sony George 20th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, 20(2):700–702, 1998. [16] Timothy J. Ross, Fuzzy Logic with Engineering application, McGraw Hill International editions, 1995. [17] Horowitz, Sahini, Rajasekaran, Fundamentals of Computer Algorithms, Galgotia Publications Pvt. Ltd, India, 1998.