A novel image thresholding method based on membrane computing and fuzzy entropy

A novel image thresholding method based on membrane computing and fuzzy entropy Hong Penga,c,∗, Jun Wangb, Mario J. P´erez-Jim´enezc and Peng Shid,e aSchool of Mathematics and Computer Engineering, Xihua University, Chengdu, China bSchool of Electrical and Information Engineering, Xihua University, Chengdu, China cResearch Group of Natural Computing, Department of Computer Science and Artificial Intelligence, University of Seville, Sevilla, Spain dDepartment of Computing and Mathematical Sciences, University of Glamorgan, Pontypridd, UK eSchool of Engineering and Science, Victoria University, Melbourne, Australia Abstract. Multi-level thresholding methods are a class of most popular image segmentation techniques, however, they are not computationally efficient since they exhaustively search the optimal thresholds to optimize the objective function. In order to eliminate the shortcoming, a novel multi-level thresholding method for image segmentation based on tissue P systems is proposed in this paper. The fuzzy entropy is used as the evaluation criterion to find optimal segmentation thresholds. The presented method can effectively search the optimal thresholds for multi-level thresholding based on fuzzy entropy due to parallel computing ability and particular mechanism of tissue P systems. Experimental results of both qualitative and quantitative comparisons for the proposed method and several existing methods illustrate its applicability and effectiveness. Keywords: Image segmentation, thresholding method, membrane computing, tissue P systems, fuzzy entropy 1. Introduction Image segmentation is one of the most important problems in computer vision and video applications. Thresholding is widely used as a popular tool in image segmentation. The goal of thresholding is to sepa-rate objects from background image or discriminate objects from objects that have distinct gray levels. Over these years, many thresholding techniques have been proposed [8, 24, 25]. Bi-level thresholding, which is firstly discussed, segments an image into two different regions. The pixels with gray values greater than a cer-tain threshold are classified as object pixels, and those with gray values lesser than the threshold are classified as background pixels. Otsu’s method [19] and Kapur’s method [11], which find the optimal thresholds by maximizing the between-class variance of gray levels and the entropy of the histogram respectively, are simple and effective in bi-level thresholding. However, gray level histograms of most of the images in the real world are multimodal. Therefore, multi-level thresholding has been received much attentions in recent years. Multilevel thresholding determines more than one threshold for an image and segments the image into several distinct regions, which correspond to one background and several objects. The Otsu’s and Papur’s methods can be extendable to multi-level thresholding but they are inefficient in determining the optimal thresholds due to the exponential growth in computation time. To improve the efficiency, some methods have been proposed to reduce the computational complexity of determining the multi-level thresholds, such as the recursive algorithm [14]. But it still suffers from long processing time when the number of thresholds increases. Fuzzy entropy has been introduced into image segmentation in recent years [1, 15, 26, 34]. Cheng et al. [1] proposed a thresholding method, where the fuzzy relation and the maximum fuzzy entropy were used to perform fuzzy partition on a two-dimensional histogram. In [26], Shelokar et al. found the optimal threshold by minimizing the sum of fuzzy entropies. Zhao et al. [34] presented a three-level thresholding method based on fuzzy entropy. In [15], Liu et al. presented a fuzzy classification entropy to deal with multi-level thresholding. However, these methods still suffer from the same problem mentioned above. In order to overcome this problem, intelligent computing methods have been applied to solve multi-level thresholding problems, such as genetic algorithm (GA), particle swarm optimization (PSO) and ant colony optimization (ACO). Yin et al. [32] presented a GA-based thresholding method, where the objective function was similar to Otsu’s or Kapur’s functions. In [2], Cheng et al. defined an approach to fuzzy entropy and employed the GA to find the optimal combination of fuzzy parameters. Tao et al. [28] presented a three-level thresholding method that uses the GA to find the optimal thresholds by maximizing the fuzzy entropy. In [6], Hammouche et al. proposed a multi-level thresholding method, which allows the determination of the appropriate number of thresholds as well as the adequate threshold values. However, GA has some drawbacks such as slow convergence rate and premature convergence to local minima. Thus, the PSO has been applied to multi-level thresholding [5, 17, 33]. In addition, Tao et al. [27] used the ACO to obtain the optimal parameters of the presented entropy-based object segmentation method. Membrane computing, as a new branch of natural computing, was proposed by P˘ aun [20] in 2000. Membrane computing is a novel class of distributed parallel computing models, which is inspired by the structure and the functioning of living cells as well as the interactions of living cells in tissues or higher order biological structures. The computing systems are commonly called P systems. Generally, a P system consists of three ingredients: membrane structure, multisets of objects and evolution rules [22]. Since then, a large number of P systems and their variants have been proposed [4, 7, 10, 13, 18, 21–23, 29–31]. Tissue P systems as a class of P systems, are inspired by the intercellular communication and cooperation between neurons [4]. Tissue P systems can be viewed as a net of processors dealing with symbols and communicating them along channels specified in advance. In addition to the advantage of distributed parallel computing, tissue P systems have evolution and communication mechanisms of objects, which allow the evolution of objects as well as the exchange and sharing of objects between elementary membranes. In this paper, we propose a new multi-level thresholding method based on tissue P systems to solve the problem mentioned above. Our main motivation is to improve and enhance the efficiency of the multi-level thresholding method based on the fuzzy entropy criterion by applying the parallel computing ability and evolution and communication mechanisms of tissue P systems. The proposed method is evaluated on several standard images and it is also compared with the traditional method and GA-based and PSO-based methods. The rest of this paper is organized as follows. Section 2 briefly describes the fuzzy entropy criterion. The proposed multi-level thresholding method based on tissue P systems is presented in Section 3. Experimental results are provided in Section 4. Finally, Section 5 draws the conclusions. 2. The fuzzy entropy criterion Let D={(i,j): i= 0,1,..., M-1; j= 0,1,..., N-1},G={0, 1,... ,L-1}, where M,Nand Lare three positive integers. Thus, an image defines a mapping I:D→G. Let I(x,y) be the gray level value of the image at the pixel (x,y). Then, its histogram Hcan be calculated by H={hk|k=0,1, ..., L −1} hk=nk/(N×M) where nkdenotes the number of pixels such that I(x,y)=k. Suppose we segment image Iinto Cpartitions by (C-1)-level thresholds, t1,t2,... ,tC-1, which meet t1<t2<... <tC-1. Formally, we denote the Cpartitions (classes) as A1,A2,... , AC. For sake of simplicity, denote t0=−1, tC=L-1. Thus, Gis divided into Cregions, R1,R2,... ,RC, where Ri=[ti-1,ti], i=1,2,... ,C. We use the following fuzzy membership function to express the C partitions (classes), which is similar to that in Huang et al. [9], µi(k)=1 1+|k−µi|/(L−1) ,k∈Ri 0,k/∈Ri (1) where i=1,2,... ,C, and ␮igives the mean value in the histogram of the region Ri, which is calculated by µi= ti  k=ti−1+1 k×hkti  k=ti−1+1 hk(2) Now, we consider the fuzzy entropy as follows, which is similar to that in Luo et al. [16], H(I)= C  i=1 H(Ai) (3) where H(Ai)=− L−1  k=0 hkµi(k) p(Ai)log hkµi(k) p(Ai)(4) where p(Ai)= L−1  k=0 hk µi(k)(5) Notice that Equation (4) gives the entropy of the distribution hk␮ik /p(Ai)ofith class, thus Equation (3) just accumulates the entropy of all classes. In this paper, maximizing Equation (3) will be regarded as our criterion to find the optimal segmentation thresholds, t1,t2,... ,tC-1. 3. The proposed multi-level thresholding method based on tissue P systems The proposed multi-level thresholding method is based on a tissue P system with symport/antiport rules. In symport rules, objects cooperate to traverse a membrane together in the same direction, whereas in the case of antiport rules, objects residing at both sides of the membrane cross it simultaneously but in opposite directions. From the membrane structure, tissue P systems are a directed graph with one layer. In order to deal with the multi-level thresholding problem Fig.1. Membranestructureandcommunicationrelationshipbetween elementary membranes. effectively, we design a special membrane structure, which consists of melementary membranes, shown in Fig. 1. These elementary membranes are labelled by 1, 2, . . . , m, respectively. Usually, the membrane labelled by 0 indicates the environment. In this paper, the environment is also an output membrane of the system. When the system halts, the object contained in membrane 0 will be regarded as output of the system. In Fig. 1, these directed lines indicate information exchange and sharing between the elementary membranes. In the developed tissue P system, after all objects are evolved in a computing step, each elementary membrane will transmit its best object into other (m-1) elementary membranes. Thus, each elementary membrane can receive (m-1) best objects from other elementary membranes. As usual in P systems, these evolution membranes work as parallel computing units in a maximally parallel way (a universal clock is considered here). As we know, every elementary membrane contains a certain number of objects. For simplicity, we assume that every elementary membrane contains the same number of objects, and the number is denoted by n. In this work, each object is a (C-1)-dimensional vector X=(x1,x2,... ,xC-1), where x1,x2,... ,xC-1are corresponding to segmentation thresholds of the image, t1,t2,... ,tC-1, respectively. Therefore, each object expresses in fact a candidate of the optimal segmentation thresholds to be found. In the tissue P system, the criterion Equation (3) will be regarded as fitness function of objects in the system to evaluate the quality of each object, i.e., Fit =H(I). Each elementary membrane will use evolution rules to evolve its objects. In this work, we develop an improved position-velocity model by integrating the inherent mechanism of tissue P systems, which can be viewed as a variant of the position-velocity model used in particle swarm optimization (PSO) [3, 12]. For jth object of kth elementary membrane, Xk,j, the improved position-velocity model is given as follows. Vkj =w·Xkj +c1r1(Pk,j −Xk,j) +c2r2(Gk−Xk,j)+c3r3(G∗−Xk,j) Xk,j =floor (Xk,j +Vk,j),j=1,2, ..., m, k=1,2, ..., m (6) where wis inertia weight, c1,c2and c3are learning factors, r1,r2,r3∈(0,1) are random numbers, and floor(×) is a rounded function. Xk,j =(xk,j,1,xk,j,2,... ,xk,j,C-1) expresses the position of object Xk,j in solution space, Vk,j =(vk,j,1,vk,j,2 ,... ,vk,j,C-1 ) is the corresponding velocity vector, and Pk,j is the found best position of object Xk,j so far. The improved position-velocity model uses two kinds of the best objects to guide the evolution of the objects in each elementary membrane: one is the best object in the current elementary membrane, Gk=(gk,1 ,gk,2,... ,gk,C-1 ), and another is randomly selected from the best objects that are transmitted from other (m-1) elementary membranes in previous computing step, G∗=(g1∗,g2∗,... ,gC-1∗), called external best object here. The improved position-velocity model has two advantages for the evolution of the objects: (i) The best object obtained by co-evolution of other elementarymembranesisinvolvedinguidingtheevolution of objects in each elementary membrane, so this mechanism will speed up the convergence of the system; (ii) Since the two best objects are taken from different sources, this mechanism can better improve the diversity of objects in the system, thus it can avoid premature convergence to local optima. This is an important feature of the presented multi-level thresholding method based on tissue P systems. In the developed tissue P system, in addition to above evolution rules, there are some communication rules between its elementary membranes. The role of communication rules is to exchange and share the objects between the elementary membranes. During each computing step, the position-velocity model (6) is used to evolve all objects in each elementary membrane. After all objects are evolved, each elementary membrane will transmit its best object into other elementary membranes and update the object in the output membrane. The used update rule is as follows: if fitness value of the transmitted object is higher than that of the existing object in the output membrane, it will replace the existing object; otherwise, replacement will not occur. The maximum execution step number is employed as halt condition in the multi-level thresholding method. When the system halts, the object in the output membrane is regarded as the output of the entire system. The proposed multi-level thresholding method based on tissue P systems is summarized in Table 1. 4. Experimental results The applicability and efficiency of the proposed multi-level thresholding method in image segmentation has been evaluated on six standard test images. Table 1 Algorithm: the multi-level thresholding method based on tissue P systems Input parameters: the number of elementary membranes m, the number of objects in each elementary membrane n, maximum execution step number Smax , and learning factors c1,c2and c3. Output results: the optimal thresholds, t=(t1,t2,…, tC-1). Step 1.Initialization for k=1tom for j=1ton Xk,j= rand(C,L); % Generate initial objects for each elementary membrane Fitk,j= FitnessCalculation(Xk,j); % Calculate the fitness value of the object according to Equation (4) end for end for Set computing step s=0; Step 2.Object evolution in elementary membranes for each elementary membrane k(k= 1, 2,…, m) in parallel do for j=1ton Evolve the object Xk,jin the elementary membrane kaccording to Eqution (6); Fitk,j= FitnessCalculation(Xk,j); Update Pk,j; % Update best position of the object Xk,jaccording to its fitness value Fitk,j end for Update Gk; % Update best object of membrane kaccording to the fitness values of its all objects end for Step 3.Object communication between elementary membranes for each elementary membrane k(k= 1, 2,…, m) in parallel do Receive best objects transmitted from other (m-1) elementary membranes; end for Update G∗; % Update external best object of membrane kaccording to these transmitted objects Step 4.Halt condition judgment If s>Smax is satisfied, the system exports object in environment as tand halts; otherwise, s=s+1,andgoto Step 2 Fig. 2. Test images and their histograms. (a) Lena; (b) Peppers; (c) Hunter; (d) House; (e) Baboon; (f) Butterfly. (a)–(f) are the corresponding histograms. These well-known images are Lena, Peppers, Hunter, House, Baboon and Butterfly respectively, shown in Fig. 2(a)–(f). The test images are all with size 512 ×512. Fig. 2(a)–(f) show the histograms of the six test images. In experiments, the parameters of the proposed multi-level thresholding method based on P systems are given as follows: (i) The tissue P system used includes five elementary membranes (m= 5), where the number of objects contained in each elementary membrane is n= 30, and the maximum execution Fig. 3. Three-level thresholding images obtained by different methods. (a)–(f) P systems; (a)–(f) PSO; (a)–(f) GA; (a)–(f) Luo et al. [16]. Fig. 4. Four-level thresholding images obtained by different methods. (a)–(f) P systems; (a)–(f) PSO; (a)–(f) GA. Table 2 Optimal thresholds obtained by different methods Images CP systems PSO GA Luo et al. [16] Lena 2 98.165 99.166 103.168 76.189 3 87.143.189 85.153.182 75.152.178 – Peppers 2 78.150 80.145 85.151 69.177 3 65.123.176 72.125.173 60.117.180 – Lunter 2 87.180 82.183 73.179 52.194 3 38.89.133 40.88.141 33.90.150 – House 2 55.130 59.130 49.141 40.156 3 44.103.164 47.105.168 35.116.180 – Baboon 2 97.149 94.154 86.165 78.174 3 83.128.161 78.125.174 65.129.186 – Butterfly 2 97.152 100.149 111.179 90.185 3 76.115.165 75.120.175 62.113.195 – step number Smax is 100; (ii) In the position-velocity model used, c1=c2=c3= 1.0, and wlinearly varies from 0.9 to 0.4. The segmentation results obtained by the proposed multi-level thresholding method are compared with PSO-based and GA-based methods as well as Lou’s method [16]. For PSO-based method, basic position-velocity model is employed and its parameters are given: population size NP = 30, maximum generation number Gmax = 100, c1=c2= 1.0, and wlinearly varies from 0.9 to 0.4. For GA-based method, its parameters are given: population size NP = 30, crossover probability Pc= 0.6, mutation rate Pm= 0.01 and maximum generation number Gmax = 100. Figure 3 gives optimal three-level segmentation results on the six test images for the proposed method based on P systems (in short, P systems), PSO-based method (in short, PSO), GA-based method (in short, GA) and Luo’s method, respectively. Their optimal segmentation thresholds are listed in Table 2. From the Fig. 3, we can see that results of the proposed method are slightly better than that of PSO-based method but evidently outperform that of GA-based method and Lou’s method. This illustrates the applicability of the proposed method for three-level thesholding. For four-level thresholding, Fig. 4 shows the optimal segmentation results on the six test images for the proposed method, PSO-based method and GA-based method, respectively. Table 2 gives the corresponding optimal segmentation thresholds. From the visual point of view, the proposed method has better segmentation quality compared with PSO-based and GA-based methods. This also indicates that the proposed method is applicable to four-level thesholding in image segmentation. In order to investigate the efficiency, all methods are compared according to the average CPU time (in Table 3 Comparisons of CPU time (in seconds) for different methods Methods CP systems PSO GA Luo et al. [16] Lena 2 7.528 9.136 11.654 82.294 3 7.951 9.847 12.042 – Peppers 2 6.993 9.849 12.117 80.195 3 7.232 10.125 12.936 – Hunter 2 7.819 9.521 11.973 83.552 3 8.257 10.046 12.348 – House 2 7.763 9.431 11.846 83.782 3 8.355 10.221 12.624 – Baboon 2 7.218 9.685 11.672 81.375 3 7.561 9.918 12.856 – Butterfly 2 7.249 9.772 11.995 84.017 3 8.361 10.342 12.983 – seconds) taken to converge the solution. Comparison results of all methods are given in Table 3. The experimental results are obtained on a personal computer with a Core 2 Duo 1.86 GHz. From Table 3, it is clear that the proposed method has a fast convergence compared with PSO-based and GA-based methods. The results demonstrate that the proposed method is more efficient and effective than other methods for multi-level thresholding. 5. Conclusions In this paper, we have described a fast multi-level thresholding method that used the fuzzy entropy as the evaluation criterion. The thresholding method was based on a tissue P system. A special membrane structure was designed, which allowed multiple elementary membranes to co-evolve the objects of the system, and an improved position-velocity model was used as evolution rules of elementary membranes. With its particular communication mechanism, two kinds of the best objects were used to guide the evolution of the objects: one was the best object in each elementary membrane and another was from other elementary membranes. This mechanism not only accelerates the speed of convergence effectively but also enhances the diversity of objects in the system. The proposed method has been tested on several standard images and was compared with the traditional method and GA-based and PSO-based methods. The experimental results showed that the proposed method outperforms the other methods in terms of the applicability and computation efficiency. Further works are to be carried out to study the feasibility of the proposed method for various types of image processing applications. Acknowledgments This work was partially supported by the National Natural Science Foundation of China (No. 61170030), Foundation of Sichuan Provincial Key Discipline of Computer Software and Theory (No. SZD0802- 09-1), Research Fund of Sichuan Key Laboratory of Intelligent Network Information Processing (No. SGXZD1002-10), Importance Project Foundation of the Education Department of Sichuan province (No. 12ZA163), and the Importance Project Foundation of Xihua University (No. Z1122632), China. References [1] H.D. Cheng, Y.H. Chen and X.H. Jiang, Thresholding using two-dimensional histogram and fuzzy entropy principle, IEEE Trans on Image Processing 9(4) (2000), 732–735. [2] H.D. Cheng, Y.H. Chen and Y. Sun, A novel fuzzy entropy approach to image enhancement and thresholding, Signal Processing 75 (1999), 277–301. [3] R.C. Eberhart, J. Kennedy and Y.H. Shi, Swarm Intelligence, San Mateo, Morgan Kaufmann, CA, 2001. [4] R. Freund, Gh. P˘ aun and M.J. P´ erez-Jim´ enez, Tissue-like P systems with channel-states, Theoretical Computer Science 330 (2005), 101–116. [5] H. Gao, W.B. Xu, J. Sun and Y.L. Tang, Multilevel thresholding for image segmentation through an improved quantum-behaved particle swarm algorithm, IEEE Trans On Instrumentation and Measurement 59(4) (2010), 934–946. [6] K. Hammouche, M. Diaf and P. Siarry, A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation, Computer Vision and Image Understanding 109 (2008), 163–175. [7] W. Hu, Real-time on-line video object segmentation based on motion, International Journal of Innovative Computing, Information and Control 7(4) (2011), 1845–1860. [8] L.K. Huang and M.J. Wang, Image thresholding by minimizing the measure of fuzziness, Pattern Recognition 28 (1995), 41–51. [9] L.K. Huang and M.J.J. Wang, Image thresholding by minimizing the measures of fuzziness, Pattern Recognition 28(1) (1995), 41–51. [10] M. Ionescu, Gh. P˘ aun and T. Yokomori, Spiking neural P systems, Fundameta Informaticae 71(2–3) (2006), 279–308. [11] J.N. Kapur, P.K. Sahoo and A.K.C. Wong, A new method for gray-level picture thresholding using the entropy of the histogram, Computer Vision, Graphics and Image Processing 29(3) (1985), 273–285. [12] J. Kennedy and R.C. Eberhart, Particle swarm optimization, In: Proc IEEE Int Conf Neural Networks, Perth., Perth, Australia, 4(1995), 1942–1948. [13] W. Kuo, C. Lin and W. Hsu, Medical image segmentation using the combination of watershed and FCM clustering algorithms, International Journal of Innovative Computing, Information and Control 7(9) (2011), 5255–5268. [14] P.S. Liao, T.S. Chen and P.C. Chung, A fast algorithm for multilevel thresholding, Journal of Information Sciences and Engineering 17(5) (2001), 713–727. [15] D. Liu, Z.H. Jiang and H.Q. Feng, A novel fuzzy classification entropy approach to image thresholding, Pattern Recognition Letters 27 (2006), 1968–1975. [16] X. Luo and J. Tian, ICM method for multi-level thresholding using maximum entropy criterion. in: Proc of Internat Conf on Image Analysis and Processing, 1999, pp. 108–113. [17] M. Maitra and A. Chatterjee, A hybrid cooperativecomprehensive learning based PSO algorithm for image segmentation using multilevel thresholding, Expert Systems with Applications 34 (2008), 1341–1350. [18] T.Y. Nishida, An application of P-system: A new algorithm for NP-complete optimization problems, in: Proc 8th World Multi-Conference on Systemics, Cybernetics and Informatics, 2004, pp. 109–112. [19] N. Otsu, A threshold selection method from gray level histograms, IEEE 481 Transactions on Systems, Man and Cybernetics SMC-9 (1979), 62–66. [20] Gh. P˘ aun, Computing with membranes, Journal of Computer System Sciences 61(1) (2000), 108–143. [21] Gh. P˘ aun and M.J. P´ erez-Jim´ enez, Membrane computing: Brief introduction, recent results and applications, BioSystem 85 (2006), 11–22. [22] Gh P˘ aun, G. Rozenberg and A. Salomaa, The Oxford Handbook of Membrance Computing, Oxford University Press, New York, 2010. [23] H. Peng, J. Wang, M.J. Perez-Jimenez, H. Wang, J. Shao and T. Wang, Fuzzy reasoning spiking neural P system for fault diagnosis, Information Sciences (2012), (Accepted). [24] A. Pikaz and A. Averbuch, Digital image thresholding based on topological stable state, Pattern Recognit 29(5) (1996), 829–843. [25] P.K. Sahoo, S. Soltani, A.K.C. Wong and Y.C. Chen, A survey of thresholding techniques, Comput Vis Graph Image Process 41(2) (1988), 233–260. [26] P.S. Shelokar, V.K. Jayaraman and B.D. Kulkarni, An ant colonyapproach for clustering, Anal Chim Acta 59 (2004), 187–195. [27] W.B. Tao, H. Jin and L.M. Liu, Object segmentation using ant colony optimization algorithm and fuzzy entropy, Pattern Recognit Lett 28(7) (2008), 788–796. [28] W.B. Tao, J.W. Tian and J. Liu, Image segmentation by three-level thresholding based on maximum fuzzy entropy and genetic algorithm, Pattern Recognit, Lett 2003 (24), 3069–3078. [29] H. Wang, H. Peng, J. Shao and T. Wang, A thresholding method based on P systems for image segmentation, ICIC Express Letters 6(1) (2012), 221–227. [30] J. Wang, L. Zhou, H. Peng and G.X. Zhang, An extended spiking neural P system for fuzzy knowledge representation, International Journal of Innovative Computing, Information and Control 7(7A) (2011), 3709–3724. [31] T. Wang, J. Wang, H. Peng and M. Tu, Optimization of PID controller parameters based on PSOPS algorithm, ICIC Express Letters 6(1) (2012), 273–280. [32] P.Y. Yin, A fast scheme for optimal thresholding using genetic algorithms, Signal Processing 72 (1999), 85–95. [33] E. Zahara, S.-K.S. Fan and D.M. Tsai, Optimal multithresholding using a hybrid optimization approach, Pattern Recognit Lett 26 (2005), 1085–1095. [34] M.S. Zhao, A.M.N. Fu and H. Yan, A technique of threelevel thresholding based on probability partition and fuzzy 3-partition, IEEE Trans on Fuzzy Systems 9(3) (2001), 469– 479. View publication statsView publication stats