Cell Complexes and Membrane Computing for Thinning 2D and 3D Images

Cell Complexes and Membrane Computing for Thinning 2D and 3D Images Ra´ul Reina-Molina1, Daniel D´ıaz-Pernil1, Miguel A. Guti´errez-Naranjo2 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics University of Sevilla [email protected], [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla [email protected] Summary. In this paper, we show a new example of bridging Algebraic Topology, Membrane Computing and Digital Images. In [24], a new algorithm for thinning multidimensional black and white digital images by using cell complexes was presented. Such cell complexes allow a discrete partition of the space and the algorithm preserves topological and geometrical properties of the image. In this paper, we present a parallel adaptation of such algorithm to P systems, by introducing some concepts of Algebraic Topology in the Membrane Computing framework. The chosen model for the implementation is tissue-like P systems with promoters, inhibitors and priorities. 1 Introduction Computer vision [36] is one of the challenges for Computer Science in the next years. From a biological point of view, vision is an extremely complex process involving the transformation of the light energy into a signal which leaves the eye by way of the optic nerve and arrives to the brain, where is interpreted. From the computational side, a 2D digital image can be roughly defined as a function from a two dimensional surface which maps each point from the surface onto a set of attributes as bright or color. Analogously, a 3D image maps a region of a tridimensional space onto a set of attributes. The different treatments of such mappings provide a big amount of current applications in computer vision as biometrics [1], surveillance [11] or medical imaging [2]. Many problems in the processing of 2D or 3D digital images have features which make it suitable for techniques inspired by nature. The subset of the integer plane or space taken to be the support of the image and the set of possible features 168 R. Reina-Molina et al. associated to each 2D or 3D point can be considered finite and hence, the transformation of an image into another can be made in a discrete way. Other of such features is that the treatment of the image can be parallelized and locally modified. Regardless how large is the picture, the process can be performed in parallel in different local areas of it. Another interesting feature is that the information of the image can also be easily encoded in the data structures used in Natural Computing. In the literature, we can find many examples of the use of Natural Computing techniques for dealing with such problems. One of the classic examples is the use of cellular automata [33, 35]. Other efforts are related to artificial neural networks as in [18, 38]. In Membrane Computing, there is a large tradition in the study of dealing information structured as two dimensional objects (see, e.g., [5, 6, 12, 23]). The main motivation for these studies is to bring together Membrane Computing and Picture Grammars. From a technical point of view, arrays are two-dimensional objects placed inside the membranes as strings are one-dimensional objects in the model of P systems with string objects [19, 31]. Recently, a new research line has been open by applying well-known membrane computing techniques for solving problems from digital imagery. For example, the segmentation problem, [8, 10, 13, 14], thresholding [7] or smoothing [29]. Special attention deserves Gimel’farb et al. [20], where the symmetric dynamic programming stereo (SDPS) algorithm [21] for stereo matching was implemented by using simple P modules with duplex channels. In this paper, we focus on the problem of skeletonizing a 2D or 3D image. Skeletonization is one of the approaches for representing a shape with a small amount of information by converting the initial image into a more compact representation and keeping the meaning features. The conversion should remove redundant information, but it should also keep the basic structure. There are many different definitions of the skeleton of a black and white image and many skeletonizing algorithms1, but in general, the image Bis a skeleton of the image A, if it has fewer black pixels than A, preserves its topological properties and, in some sense, keeps its meaning. The most important features concerning a shape are its topology (represented by connected components, holes, etc.) and its geometry (elongated parts, ramifications, etc.), thus these terms have to be preserved. When the skeletonizing process is made by the iterative removal of non-significant elements of the image, the process is known as thinning. In this paper, we present an implementation of the Liu’s algorithm [24] for thinning images based on Membrane Computing techniques. The basic notion of this algorithm is the cell complex. It can be seen as a mathematical abstraction of a space unit. This space unit is built in some ndimensional space and embedded in a space of higher dimension, as a 2-dimensional square can be embedded in a 3D space. All these concepts will be formalized below. 1A detailed description of skeletonizing algorithms is out of the scope of this paper. For a survey in this topic, see e.g., [34]. Cell Complexes and Membrane Computing for Thinning Images 169 In Liu’s work [24], a cell complex is processed in order to obtain another complex with the same topology, and the same geometry. We will start from a black and white 2D or 3D digital image by building a cell complex from it. This complex will be, then, processed by consecutive parallel removal of certain cells. The removal process does not change the topology nor the geometry of the starting cell complex. At the end of this process, the set of non-removed cells will make the skeleton. For implementing these ideas in the Membrane Computing framework, we present a family of tissue-like P systems endowed with priorities among rules, promoters and inhibitors. This paper follows the research line open with [9], but, to the best of our knowledge, this is the first work which put together Membrane Computing, Cells Complexes and thinning processes. The paper is organized as follows. In the first section, all technical requirements of Algebraic Topology are reviewed. Next, the basics for understanding the proposed algorithm are introduced, followed by the presentation of the Membrane Computing framework and the bioinspired 2D and 3D black and white image thinning algorithm. Next, an overview of the computation is presented, finishing with conclusions and future work. 2 Cubical Complexes As pointed above, cubical complexes are mathematical abstractions to handle structured portions of a ndimensional space. On such abstractions, we can define several operators as the border one, which associates, for example, a 3D cell (cube) with six 2D cells (squares), or properties to define free cells or isolated cells. We follow T. Kaczy´nski, K. Mischaikow and M. Mrozek [22] in the description of a kind of combinatorial structure on a topological space. Definition 1. [22] An elementary interval is a closed interval I⊂Rof the form I= [l, l + 1] or I= [l, l]for some l∈Z. The former are called nondegenerated, while the latter are called degenerated. The interval [l, l]that contains only one point will be denoted by [l]. Degenerated elementary intervals are simply points with 0 dimensions. Nondegenerated elementary intervals are segments (objects with one dimension). Next, we generalize this notion to any dimension. Definition 2. An elementary cube σis a finite product of elementary intervals: σ=I1×I2× · · · × Id⊂Rd where each Ijis an elementary interval, j∈ {1, . . . , d}. The set of all elementary cubes in Rdis denoted by Kd. The set of all elementary cubes is K= ∞ [ d=1 Kd 170 R. Reina-Molina et al. For example {(0,0,0)},{(x, 0,0) |0≤x≤1},{(x, y, 0) |0≤x, y ≤1}and {(x, y, z)|0≤x, y, z ≤1}are elementary cubes. Given an elementary cube σ= I1×I2×· · ·×Idin Rd, its embedding number dis denoted by emb σ. The dimension of σis defined to be the number of nondegenerated intervals in its definition and is denoted by dim σ. In this way, for the elementary cube Q≡ {(x, y, 0) |0≤x, y ≤ 1}, emb Qis 3 and dim Qis 2. The set of all elementary cubes with dimension pis denoted by Kp. The set of all elementary cubes in Rdwith dimension pis denoted by Kd p. The following definition gives sense to the decomposition of elementary cubes into lower-dimensional objects. Definition 3. Let δand σbe two elementary cubes of any dimension. If δ⊂σ, then δis a face of σ. If δis a face of σand δ6=σ, then δis a proper face of σ.δis a primary face of σif it is a face of σand dim δ= dim σ−1. Given an elementary cube σ∈ Kd p, the set of all primary faces of σis called the border of σ and it is denoted by ∂ σ. For example, let us consider the elementary cubes σ1={(x, 0,0) |0≤x≤1}, σ2={(x, y, 0) |0≤x, y ≤1}and σ3={(x, y, z)|0≤x, y, z ≤1}. Notice that σ1⊆σ2⊆σ3holds, and hence σ1,σ2and σ3are faces of σ3;σ1and σ2are proper faces of σ3;σ1is a primary face of σ2and σ2is a primary face of σ3. We also have that ∂ σ2={σ1, σ0 1, σ00 1, σ000 1}with σ0 1={(x, 1,0) |0≤x≤1}, σ00 1={(0, x, 0) |0≤x≤1},σ000 1={(1, x, 0) |0≤x≤1}. Definition 4. Let Ibe an elementary interval. The associated elementary cell is I=(l, l + 1) if I= [l, l + 1], [l]if I= [l]. Let σ=I1×I2×· · ·×Id⊂Rdbe an elementary cube, the associated elementary cell is σ=I1×I1× · · · × Id The dimension of an elementary cell σis defined as dim σ, i.e., the dimension of the associated elementary cube. The border for an elementary cell σcan also be defined as the set ∂ σ ={δ:δ∈∂ σ}. Definition 5. Acubical complex is a set of elementary cells such that, given an elementary cell σin the complex, all of its principal faces (the cells in ∂ σ) are in the complex. For the sake of simplicity, hereafter we will say cells instead of elementary cells, bearing in mind that we refer to such kind of objects. For example, Figure 1 (left) shows the cubical complex K={ABCD, AC, CD, BD, AB, BE, A, B, C, D, E} Cell Complexes and Membrane Computing for Thinning Images 171 This cubical complex has 1 cell of dimension 2 (ABCD), 5 cells of dimension 1 (AC, CD, BD, AB, BE) and 5 cells of dimension 0 (A, B, C, D, E). When a cell is not a proper face of any cell in a given cell complex, it will be called isolated cell. A cell that is a proper face of exactly one cell in the complex is called free face. The following proposition links the concepts of free faces, proper faces and dimension. The proof can be found in [22]. Proposition 1. Let δbe a free face in a cell complex and assume δis a proper face of σ. Then σis an isolated cell and dim δ= dim σ−1. As we are interested in obtaining a simpler representation for a cell complex whilst the topology is preserved. In the following definition, a way to reduce the number of cells in a cell complex is presented. This process reduces the number of cells by two and it does not change the topology of the cell complex. For example, let us consider the cell complex of Figure 1 (left). The cells ABCD and BE are isolated. The cells AC,CD,BD AB and Erare free faces, but A, B,Cand Dare not free faces, since they are proper faces of more than 1 cell complex. Definition 6. Let Kbe a cubical complex and δa free cell in K. Let σbe the only cell in Ksuch that δis a proper face of σ. Let K0=K\ {δ, σ}.K0is obtained from Kvia a process called elementary collapse of σby δ. Let us consider again the cell complex Kof Figure 1 (left). The cell Eis a free face of BE and, hence, we can consider the elementary collapse of BE by E. The effect of such elementary collapse is the removal of Eand BE from the cell complex K. Analogously, AC is a free face of ABCD. The elementary collapse of ABCD by AC is the removal of both cells (ABCD and AC) from K. Figure 1 (right) shows the final cubical complex obtained after both collapses. Definition 7. Let Kbe a cubical complex. A pair of cells hδ, σiis said to be a simple pair if following conditions hold: •δis a free cell in K. •σis the only cell such that δ∈∂ σ. The cell σis called the facet of the simple pair. As shown in related literature [22, 37], simple pairs removal does not change the topology of the given cell complex. 3 Cell Complex Thinning Skeletonization is usually considered as a pre-process in pattern recognition algorithms, but its study is also interesting by itself for the analysis of line-based 172 R. Reina-Molina et al. Fig. 1. Elementary collapse example: Ecollapses onto BE and AC collapses onto ABDC in the image at the left, producing the image at the right. images as texts, line drawings, human fingerprints or cartography. Skeletonization is a common transformation in Image Analysis. The concept of skeleton was introduced by Blum in [3], under the name of medial axis transform. Let Kbe a cubical2cell complex and let ∂be its border operator. As seen in the previous section, if only simple pairs of cells are removed, the topology is kept. For geometry preservation it is necessary to require some additional properties to those cells to be removed. The basic idea of the algorithm is to define an iterative process where outer cells are removed. Here, the idea of outer cells makes reference to simple pairs, since in a simple pair hδ, σithe cell δis a “terminal” cell as it does not lie in the border of any other one rather than σ. In the process of iterative thinning, given a cell σ, we will denote the later iteration when σis the facet of a simple pair by R(σ). The earlier iteration when σbecomes isolated will be denoted by I(σ). Liu et al. describe in [25] the relation between I(σ) and R(σ), and the maximum isotropic elongation in p+ 1 and p 2In the original work by Liu, [24], the thinning algorithm is designed for cell complexes of any kind, however we restrict to cubical complexes. Cell Complexes and Membrane Computing for Thinning Images 173 directions, respectively, since dim σ=p. Thus, if σis a p-cell in a cell complex, I(σ) measures the shortest discrete distance from σto the object boundary. This gives an idea of the size of the maximum disk centered at σand inscribed in the object. On the other hand, R(σ) measures the longest distance from σto the object boundary going along the skeleton (p−1)-cells. From the observation of the behaviour of previous measures, Liu defined two difference measures. The absolute one, R(σ)−I(σ), is called absolute medial persistence and is denoted by MPabs. On the other hand, relative medial persistence is defined as 1 −I(σ) R(σ)and denoted by MPrel. Both of them measure the duration in which a cell remains isolated during thinning process. The cell complex thinning algorithm is shown in algorithm 1. It starts by initializing the isolated cells. Next, the thinning iterations start. In each iteration, all simple pairs are selected, all the pairs where the facet cell has one of the medial persistence measures less than given thresholds are chosen. Finally, the cells in selected simple pairs are removed from the cell complex. Otherwise, the cells are removed and the thinning iterations stop, else, the iteration counter increases and the thinning iterations continue. When the algorithm halts, a cell complex representing the skeleton for the initial one is obtained. Algorithm 1 Cell complex thinning algorithm Require: Kcell complex, εa, εr>0 for all σ∈Kisolated do I(σ)←0 end for iter ←1 repeat Let S={hδ, σi:hδ, σiis a simple pair} for all σ∈π2(S)do R(σ)←iter end for Let S0={hδ, σi ∈ S:MPabs(σ)< εa∧MPrel(σ)< εr} K=K\ {σ, δ :hδ, σi ∈ S0} for all σ∈Knew isolated cell do I(σ)←iter end for iter ←iter + 1 until S0=∅ Here π2(hδ, σi) = σis the second projection for the pair hδ, σi. 4 Formal Framework The chosen P system model for a Membrane Computing implementation of the algorithm is the tissue-like P systems model endowed with some extra ingredients. 174 R. Reina-Molina et al. As it is well-known, the biological inspirations of this model are intercellular communication and cooperation between neurons [26, 27]. The communication among cells is based on symport/antiport rules3. Tissue-like P systems have been widely used to solve computational problems in other areas (see e.g. [15, 16]), but recently, they have been also used in the study of digital images (e.g., [4, 8, 10, 17, 28, 29]). In this paper, we use a variant of tissue-like P systems where the application of the rules are regulated by promoters and inhibitors. These promoters have a clear biological inspiration. The rule is applied if the reactants are present, but it is also necessary the presence of all the promoters and none of the inhibitors in the corresponding cell. The promoters are not consumed nor produced by the application of the rule, but if they are not in the cell, the rule cannot be applied. In one step, each reactant in a membrane can only be used for one rule, but if several rules need the presence of the same promoter, then the presence of one unique copy of the promoter suffices for the application of the rules. In the general case, if there are several possibilities, the rule is non-deterministically chosen, but sometimes we will consider a priority relation between rules, so we need the concept of priority in our P systems. Next, we recall the formal definition of these P systems. Definition 8. Atissue-like P system with promoters, inhibitors and priorities of degree q≥1is a tuple of the form Π= (Γ, Σ, E, w1, . . . , wq,R, Pri, iin, iout) where qis the number of cells (or membranes) of the P system and 1. Γis a finite alphabet, whose symbols will be called objects. These objects can be placed in the cells or in the surrounding space (called the environment). 2. Σ⊆Γis the input alphabet. The input of the computation performed by the P system is encoded by using this alphabet. 3. E ⊆ Γis a finite alphabet representing the set of the objects in the environment. Following a biological inspiration, the objects in the environment are available in an arbitrary large amount of copies; 4. w1, . . . , wqare strings over Γrepresenting the multisets of objects placed inside the cells at the starting of the computation; 5. Ris a finite set of rules of the following form: (pro ¬inh |i, u/v, j),for 0≤i6=j≤q, pro, inh, u, v ∈Γ∗ 6. Pri is a finite set of relations Ri> Rj, where Riand Rjare rules from R. It means that if Riand Rjcan be applied, then the application of Rihas priority on the application of Rj. 7. iin ∈ {1,2, . . . , q}denotes the input cell, i.e., the cell where the input of the computation will be placed. 8. iout ∈ {1,2, . . . , q}denotes the output cell, i.e., the cell where the output of the computation will be placed. 3Introduced in Membrane Computing in [30]. Cell Complexes and Membrane Computing for Thinning Images 175 Informally, a tissue-like P system with promoters, inhibitors and priorities of degree q≥1 can be seen as a set of qcells labeled by 1,2, . . . , q. The cells are the nodes of a virtual graph, where the edges connecting the cells are determined by the communication rules of the P system, i.e., as usual in tissue-like P systems, the edges linking cells are not provided explicitly: If a rule (pro ¬inh |i, u/v, j) is given, then cells iand jare considered linked. The application of a rule (pro ¬inh |i, u/v, j) consists of trading the multiset u(initially in the cell i) against the multiset v(initially in j). After the application of the rule, the multiset udisappears from the cell iand it appears in the cell j. Analogously, the multiset v disappears from the cell jand it appears in the cell i. The trade can also be between one cell and the environment, labeled by 0. The rule is applied if in the cell with label ithe objects of pro are present in the cell i(promoters), while any of the objects in inh do not appear in the cell (inhibitors). The promoters or the inhibitors are not modified by the application of the rule. If the promoters and inhibitors are empty, we will write (i, u/v, j) instead of (∅ ¬∅| i, u/v, j). Finally, we write (pro |i, u/v, j) or (¬inh |i, u/v, j) when only promoters or inhibitors appear, respectively. As usual, we also consider that some objects not belonging to Ecan arrive to the environment during a computation. So, in a configuration (not initial) we could find two types of objects in the environment: Firstly, those which belong to the environment and appear in an arbitrary large number of copies. Secondly, those which not belong to the environment but are been sent to the environment by the application of a rule. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way (a universal clock is considered). A configuration is an instantaneous description of the P system and it is represented as a tuple (w0, w1, . . . , wq), where ‘W0is the multiset of objects from Γ− E placed in the environment (initially, w0=∅). Given a configuration, we can perform a computation step and obtain a new configuration by applying the rules in a parallel manner as it is shown above. A configuration is halting when no rules can be applied to it. A computation is a sequence of computation steps such that either it is infinite or it is finite and the last step yields a halting configuration (i.e., no rules can be applied to it). Then, a computation halts when the P system reaches a halting configuration. The output of a computation is collected from its halting configuration by reading the objects contained in the output cell. 4.1 Image Algebra Next, we recall some basic definitions from Image Algebra used in thi paper4. For a point set X⊂Z2, a neighborhood function is a function N:X→2Z2. For each point x∈X,N(x)⊂Z2. The set N(x) is called a neighborhood for x. There are two neighborhood function on subsets of Z2which are of particular importance in image processing, the von Neumann neighborhood and the Moore 4A detailed introduction can be found in [32]. 182 R. Reina-Molina et al. where selected simple pairs have been removed, along with the auxiliary objects, and the remaining objects have been moved from the third to the fourth membrane. In the configuration C6, for priority reasons again, only the rules R15 can be selected, and their application marks the new isolated cells and updates the counter (I, i, D). Now, all available objects are updated in the fourth membrane, in the configuration C7. Then, only rules R16,R17 and R18 can be applied, resulting in the configuration C8where all the objects in the fourth membrane are moved to the fifth one. If no simple pairs have been marked for removal in configuration C9, there is no marker Rin the fifth membrane. In this situation, the only rules that can be applied are those in R24. The application of these rules leaves the P system in the configuration C10 which also is a halting configuration. Let us Ssppose there have been some simple pairs marked for removal in configuration C8, which ensures the presence of marker Rin the P system. Then, the application of rules in R19 updates the counter R, leaving the P system in the configuration C9. In this situation, only rules in R20,R21 and R22 can be applied. The former move objects to the second membrane, where the thinning iterations restart, the latter removes auxiliary objects from the fifth membrane. In this situation, the P system is in the configuration C10. The result for the example image is shown in Figure 4 (Right). Fig. 4. (Left) Cell complex representation for cells in membrane 2 after the first thinning iteration. (Right) The thinned cell complex. In previous situation, only the rules in R4and R23 can be applied. The former marks simple pairs in the second membrane, while the latter remove auxiliary remaining objects in the fifth membrane, leaving the P system in the configuration C11. From this point, the P system will evolve as above until it reaches the configuration C16 whether the halting condition may be reached in next configuration Cell Complexes and Membrane Computing for Thinning Images 183 C17, or not, depending on the presence of marker R. In the first case, the P system will start a new thinning iteration. In the second situation, the P system sends out the skeleton to the output membrane. In any case, the P system will reach the halting configuration in 7t+ 3 steps, where tstands for the thinning iterations performed. If we start from a k-D binary image of size nkwhere all the resels are black, and we do not pay attention to the shape significance, we perform a full thinning in a number of thinning iterations which, in addition, is the maximum. We have found that, in situation above, the greater number of thinning iterations is given by k(n+ 1). Hence, we can ensure that the P system halts in, at most, 7k(n+ 1) + 3 computation steps. In Figure 4 (Right), the resulting image, representing the cell complex in the sixth membrane when the halting condition is reached, is shown. The required computational resources for the family of tissue-like P systems defined in this paper is given in the table 1. k-D binary image thinning problem Complexity Number of steps of computation ≤7k(n+ 1) + 3 Resources needed Size of the alphabet O(nk+1) Initial number of cells 6 Initial number of objects 3|K| Number of rules O(nk+2) Upper bound for the length of the rules 3 Table 1. Complexity aspects, where the size of the input data is O(nk), |K|is the number of cells in the input cell complex K. 7 Conclusions and Future Work In this paper, we bring together Membrane Computing and Cell Complexes. Both disciplines deal with compartments of the Euclidean space on their foundations, but their inspiration and motivation are quite different. The former is a computation model inspired in the functioning of living cells and tissues and the latter is born as a tool for handle concepts of Algebraic Topology. In this paper, we use Membrane Computing techniques to implement a cell complex based algorithm for thinning images and show a new proof that the Membrane Computing framework is flexible enough to adapt to unexpected situations. In this way, this is a pioneer work that open a new research line that can be followed at different levels. Firstly, we can study if other P system models (cell-like P systems, SN P systems, a most restrictive model of tissue-like P systems, . . . ) are better than 184 R. Reina-Molina et al. the one used in this paper to implement the Liu’s algorithm in the Membrane Computing framework. Better should be considered here in a broad sense, since it can mean with a lower amount of resources, with less ingredients in the P system model o more efficient in some sense. Another line to follow is to study if other problems in Algebraic Topology already studied with Cells Complexes can be considered in the framework of Membrane Computing. This research line can open a flow of inquiries and solutions in both directions enriching both disciplines with new points of view. Finally, a more general question is the study of links on the foundations of Membrane Computing and Cell Complexes. As pointed out above, both disciplines shares a compartmental view of the Euclidean space and this can be a starting point for a deeper study of their common properties. Acknowledgements DDP and MAGN acknowledge the support of the projects TIN2008-04487-E and TIN-2009-13192 of the Ministerio de Ciencia e Innovaci´on of Spain and the support of the Project of Excellence with Investigador de Reconocida Val´ıa of the Junta de Andaluc´ıa, grant P08-TIC-04200. References 1. Adeoye, O.S.: A survey of emerging biometric technologies. International Journal of Computer Applications 9(10), 1–5 (November 2010) 2. Ayache, N.: Medical image analysis and simulation. In: Shyamasundar, R.K., Ueda, K. (eds.) ASIAN. Lecture Notes in Computer Science, vol. 1345, pp. 4–17. Springer (1997) 3. Blum, H.: An associative machine for dealing with the visual field and some of its biological implications. In: Bernard, E.E., Kare, M.R. (eds.) Biological Prototypes and Synthetic Systems. vol. 1, pp. 244–260. Plenum Press, New York (1962) 4. Carnero, J., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A.: Designing tissue-like P systems for image segmentation on parallel architectures. In: del Amor, M.A.M., P˘aun, Gh., de Mendoza, I.P.H., Romero-Campero, F.J., Cabrera, L.V. (eds.) Ninth Brainstorming Week on Membrane Computing. pp. 43–62. F´enix Editora, Sevilla, Spain (2011) 5. Ceterchi, R., Gramatovici, R., Jonoska, N., Subramanian, K.G.: Tissue-like P systems with active membranes for picture generation. Fundamenta Informaticae 56(4), 311– 328 (2003) 6. Ceterchi, R., Mutyam, M., P˘aun, Gh., Subramanian, K.G.: Array-rewriting P systems. Natural Computing 2(3), 229–249 (2003) 7. Christinal, H.A., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J.: Thresholding of 2D images with cell-like P systems. Romanian Journal of Information Science and Technology 13(2), 131–140 (2010) Cell Complexes and Membrane Computing for Thinning Images 185 8. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Segmentation in 2D and 3D image using tissue-like P system. In: Bayro-Corrochano, E., Eklundh, J.O. (eds.) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. Lecture Notes in Computer Science, vol. 5856, pp. 169–176. Springer (2009) 9. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: P systems and computational algebraic topology. Mathematical and Computer Modelling 52(11-12), 1982 – 1996 (2010) 10. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Region-based segmentation of 2D and 3D images with tissue-like P systems. Pattern Recognition Letters 32(16), 2206 – 2212 (2011) 11. Collins, R., Lipton, A., Kanade, T.: Introduction to the special section on video surveillance. Pattern Analysis and Machine Intelligence, IEEE Transactions on 22(8), 745 –746 (2000) 12. Dersanambika, K.S., Krithivasan, K.: Contextual array P systems. International Journal of Computer Mathematics 81(8), 955–969 (2004) 13. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Molina-Abril, H., Real, P.: A bio-inspired software for segmenting digital images. In: Nagar, A.K., Thamburaj, R., Li, K., Tang, Z., Li, R. (eds.) Proceedings of the 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications BIC-TA. vol. 2, pp. 1377 – 1381. IEEE Computer Society, Beijing, China (2010) 14. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Molina-Abril, H., Real, P.: Designing a new software tool for digital imagery based on P systems. Natural Computing pp. 1–6 (2011) 15. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A.: A linear-time tissue P system based solution for the 3-coloring problem. Electronic Notes in Theoretical Computer Science 171(2), 81–93 (2007) 16. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A.: Solving subset sum in linear time by using tissue P systems with cell division. In: Mira, J., ´ Alvarez, J.R. (eds.) IWINAC (1). Lecture Notes in Computer Science, vol. 4527, pp. 170–179. Springer (2007) 17. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Real, P., S´anchez-Canales, V.: Computing homology groups in binary 2D imagery by tissue-like P systems. Romanian Journal of Information Science and Technology 13(2), 141–152 (2010) 18. Egmont-Petersen, M., de Ridder, D., Handels, H.: Image processing with neural networks - a review. Pattern Recognition 35(10), 2279–2301 (2002) 19. Ferretti, C., Mauri, G., Zandron, C.: P systems with string objects. In: P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) The Oxford Handbook of Membrane Computing, pp. 168 – 197. Oxford University Press, Oxford, England (2010) 20. Gimel’farb, G., Nicolescu, R., Ragavan, S.: P systems in stereo matching. In: Real, P., D´ıaz-Pernil, D., Molina-Abril, H., Berciano, A., Kropatsch, W. (eds.) Computer Analysis of Images and Patterns, Lecture Notes in Computer Science, vol. 6855, pp. 285–292. Springer (2011) 21. Gimel’farb, G.L.: Probabilistic regularisation and symmetry in binocular dynamic programming stereo. Pattern Recognition Letters 23(4), 431–442 (2002) 22. Kaczy´nski, T., Mischaikow, K., Mrozek, M.: Computational homology. Applied mathematical sciences, Springer (2004) 23. Krishna, S.N., Rama, R., Krithivasan, K.: P systems with picture objects. Acta Cybernetica 15(1), 53–74 (2001) 24. Liu, L.: 3D thinning on cell complexes for computing curve and surface skeletons. Washington University (2009) 186 R. Reina-Molina et al. 25. Liu, L., Chambers, E.W., Letscher, D., Ju, T.: A simple and robust thinning algorithm on cell complexes. Computer Graphics Forum 29(7), 2253–2260 (2010) 26. Mart´ın-Vide, C., Pazos, J., P˘aun, Gh., Rodr´ıguez-Pat´on, A.: A new class of symbolic abstract neural nets: Tissue P systems. In: Ibarra, O.H., Zhang, L. (eds.) COCOON. Lecture Notes in Computer Science, vol. 2387, pp. 290–299. Springer (2002) 27. Mart´ın-Vide, C., P˘aun, Gh., Pazos, J., Rodr´ıguez-Pat´on, A.: Tissue P systems. Theoretical Computer Science 296(2), 295–326 (2003) 28. Pe˜na-Cantillana, F., D´ıaz-Pernil, D., Berciano, A., Guti´errez-Naranjo, M.A.: A parallel implementation of the thresholding problem by using tissue-like P systems. In: Real, P., D´ıaz-Pernil, D., Molina-Abril, H., Berciano, A., Kropatsch, W.G. (eds.) CAIP (2). Lecture Notes in Computer Science, vol. 6855, pp. 277–284. Springer (2011) 29. Pe˜na-Cantillana, F., D´ıaz-Pernil, D., Christinal, H.A., Guti´errez-Naranjo, M.A.: Implementation on CUDA of the smoothing problem with tissue-like P systems. International Journal of Natural Computing Research 2(3), 25–34 (2011) 30. P˘aun, A., P˘aun, Gh.: The power of communication: P systems with symport/antiport. New Generation Computing 20(3), 295–306 (2002) 31. P˘aun, Gh.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000) 32. Ritter, G.X., Wilson, J.N., Davidson, J.L.: Image algebra: An overview. Computer Vision, Graphics, and Image Processing 49(3), 297–331 (1990) 33. Rosin, P.L.: Training cellular automata for image processing. IEEE Transactions on Image Processing 15(7), 2076–2087 (2006) 34. Saeed, K., Tabedzki, M., Rybnik, M., Adamski, M.: K3M: A universal algorithm for image skeletonization and a review of thinning techniques. Applied Mathematics and Computer Science 20(2), 317–335 (2010) 35. Selvapeter, P.J., Hordijk, W.: Cellular automata for image noise filtering. In: NaBIC. pp. 193–197. IEEE (2009) 36. Shapiro, L.G., Stockman, G.C.: Computer Vision. Prentice Hall PTR, Upper Saddle River, NJ, USA (2001) 37. Zhou, Q.Y., Ju, T., Hu, S.M.: Topology repair of solid models using skeletons. IEEE Transactions on Visualization and Computer Graphics 13(4), 675–685 (2007) 38. Zhou, Y., Chellappa, R.: Artificial neural networks for computer vision. Research notes in neural computing, Springer-Verlag (1992)