Array Tissue-like P Systems

Array Tissue-like P Systems Hepzibah A. Christinal1, Daniel D´ıaz-Pernil1, Miguel A. Guti´errez-Naranjo2, Mario J. P´erez-Jim´enez2 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics I {hepzi,sbdani}@us.es 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence {magutier,marper}@us.es University of Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain Summary. Array grammars have been studied in the framework of Membrane Computing by using rewriting rules from transition P systems. In this paper we present a new approach to dealing with array grammars by using tissue-like P systems and present an application to the segmentation of images in two dimensional computer graphics. 1 Introduction Array grammars can be considered as a straightforward extension of string grammars to two dimensional pictures. Such pictures are sets of symbols placed in the points with integer coordinates of the plane. They have been widely studied and have a large tradition in the literature (see, e.g. [2, 6, 16, 22]). Recently, Membrane Computing has also approximated to array grammars by setting bridges between both areas (see, e.g. [1, 14, 20]). The basic idea in such approaches is considering an array (i.e., a finite set of objects placed in points of the plane with integer coordinates) as a P system object and using rewriting rules of the type used in transition P systems [13] for replacing it. The type of rule used is x→y(tar) where x→yis a context-free rule and tar ∈here, out, in is the target which indicates the membrane where the generated object will be placed. Such rewriting rules capture the idea of array production p:A → B with Aand Barrays. In this paper we present a new approach for linking Membrane Computing to array grammars. Instead of using transition P systems to handle the arrays we propose to use tissue-like P systems. This approach allows us to use the power of symport-antiport rules for designing Membrane Computing algorithms which deal with array objects. In such P system model, the rules are of type (i, u/v, j) with the following interpretation: If the multiset uoccurs in a membrane with 38 H.A. Christinal et al. label iand the multiset voccurs in a membrane with label j, both multiset can be interchanged. We consider an extension of this type of rules. We will consider that two arrays Aand Bcan appear (respectively) in the multisets uand v. The semantics of such rule will be explained below, but the intuition is that the arrays in the membranes iand jwill be partially modified. As a case study, we present an application of array tissue-like P systems to the Segmentation Problem in computer vision. Segmentation in computer vision (see [8]), refers to the process of partitioning a digital image into multiple segments (sets of pixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze for an human. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics. In the literature, there exists different techniques to segment an image. Some of them are clustering methods [23], histogram-based methods [21], Watershed transformation methods [25] or graph partitioning methods [24]. Some of the practical applications of image segmentation are medical imaging [23], the study of anatomical structure, locate objects in satellite images (roads, forests, etc.) [19] or face recognition [7] among others. The paper is organized as follows: First we briefly recall some basic definitions related to graphs and multisets and introduce our definition of pixel and array. Next, we introduce a new P system model called Array tissue-like P systems on the basis of tissue P systems. In Section 4, this P system model is used to find a solution to the segmentation problem in Digital Image. 2 Definitions An alphabet,Σ, is a non-empty set, whose elements are called symbols. An ordered sequence of symbols is a string. The number of symbols in a string uis the length of the string, and it is denoted by |u|. As usual, the empty string (of length 0) is denoted by λ. The set of strings of length nbuilt with symbols from the alphabet Σ is denoted by Σnand Σ∗=∪n≥0Σn. A language over Σis a subset of Σ∗. A multiset over a set Ais a pair (A, f) where f:A→Nis a mapping. If m= (A, f) is a multiset then its support is defined as supp(m) = {x∈A|f(x)>0}and its size is defined as Px∈Af(x). A multiset is empty (resp. finite) if its support is the empty set (resp. finite). If m= (A, f) is a finite multiset over A, then it is denoted by m=af(a1) 1af(a2) 2· · · af(ak) k, where supp(m) = {a1, . . . , ak}, and for each element ai,f(ai) is called the multiplicity of ai. An undirected graph Gis a pair G= (V, E) where Vis the set of vertices and Eis the set of edges, each one of which is an (unordered) pair of (different) vertices. If {u, v} ∈ E, we say that uis adjacent to v(and also vis adjacent to u). The degree of v∈Vis the number of adjacent Array Tissue-like P Systems 39 vertices to v. In what follows we assume that the reader is already familiar with the basic notions and the terminology underlying P systems3. Next, we give a formalization of the arrays considered in this paper. Definition 1. Given a finite set V, called an alphabet of colors, a pixel on Vis a pair hx, visuch that x∈Z2and v∈V. An array on V,A, is a finite set of pixels such that if hx1, v1i,hx2, v2i ∈ Aand v16=v2then x16=x2. Finally, the support of the array Ais the set supp(A) = {x∈Z2| ∃v∈Vsuch that hx, vi ∈ A}. Given an array Aand z∈Z2, we will denote by A+zthe set A+z={hx+z, vi | hx, vi ∈ A} Example 1. Let V={R, G, B}be the alphabet of colors and Athe array on V A={h(3,2), Ri,h(3,3), Gi,h(5,5), Gi}. Let us consider z= (−2,1) ∈Z2. The array A+zis {h(1,3), Ri,h(1,4), Gi,h(3,6), Gi}. If there are no confusion about the alphabet of colors, we will omit it and we talk about pixels. As usual, we will denote by V∗2the set of all two dimensional arrays over V. 3 Array Tissue-like P Systems In the initial definition of the cell-like model of P systems [12], membranes are hierarchically arranged in a tree-like structure. Its biological inspiration comes from the morphology of cells, where small vesicles are surrounded by larger ones. This biological structure can be abstracted into a tree-like graph, where the root represents the skin of the cell (i.e. the outermost membrane) and the leaves represent membranes that do not contain any other membrane (elementary membranes). Besides, two nodes in the graph are connected if they represent two membranes such that one of them contains the other one. In tissue P systems, the tree-like membrane structure is replaced by a general graph. This model has two biological inspirations (see [9, 10]): intercellular communication and cooperation between neurons. The common mathematical model of these two mechanisms is a net of processors dealing with symbols and communicating these symbols along channels specified in advance. The communication among cells is based on symport/antiport rules, which were introduced as communication rules for P systems in [11]. 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. Formally, a tissue-like P system of degree q≥1 with input is a tuple of the form Π= (Γ, Σ, E, w1, . . . , wq,R, iΠ, oΠ), where 3We refer to [13] for basic information in this ares, to [15] for a comprehensive presentation and the web site [26] for the up-to-date information. 40 H.A. Christinal et al. 1. Γis a finite alphabet, whose symbols will be called objects, 2. Σ(⊂Γ) is the input alphabet, 3. E ⊆ Γ(the objects in the environment), 4. w1, . . . , wqare strings over Γrepresenting the multisets of objects associated with the cells at the initial configuration, 5. Ris a finite set of communication rules of the following form: (i, u/v, j), for i, j ∈ {0,1,2, . . . , q}, i 6=j,u, v ∈Γ∗, 6. iΠ∈ {0,1,2, . . . , q}, 7. oΠ∈ {0,1,2, . . . , q}. A tissue-like P system of degree q≥1 can be seen as a set of qcells (each one consisting of an elementary membrane) labeled by 1,2, . . . , q. We will use 0 to refer to the label of the environment, iΠand oΠdenote the input region and the output region (which can be the region inside a cell or the environment) respectively. The strings w1, . . . , wqdescribe the multisets of objects placed in the qcells of the system. We interpret that E ⊆ Γis the set of objects placed in the environment, each one of them available in an arbitrary large amount of copies. The communication rule (i, u/v, j) can be applied over two cells labeled by i and jsuch that uis contained in cell iand vis contained in cell j. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. Note that if either i= 0 or j= 0 then the objects are interchanged between a cell and the environment. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way (a universal clock is considered). In one step, each object in a membrane can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e, in each step we apply a maximal set of rules. In order to understand how we can obtain a computation of one of these P systems we present an example of them: Consider us the following tissue-like P system Π0= (Γ, Σ, E, w1, w2,R, iΠ, oΠ) where 1. Γ={a, b, c, d, e}, 2. Σ=∅, 3. E={a, b, e}, 4. w1=a3e, w2=b2c d, 5. Ris the following set of communication rules (a) (1, a/b, 2), (b) (2, c/b2,0), (c) (2, d/e2,0), (d) (1, e/λ, 0), 6. iΠ= 1, 7. oΠ= 0 Array Tissue-like P Systems 41 We can observe the initial configuration of this system in the Figure 1 (a). We have four rules to apply. First rule is (1, a/b, 2). The rule can be applied whenever an object ’a’ is founded in cell 1 and one copy of ’b’ appear in cell 2. This rule sends ’a’ to cell 2 and ’b’ from cell 2 to cell 1. Rule 2 is (2, c/b2,0) and implies that when symbol ’c’ present in cell 2 then this rule takes two copies of ’b’ from environment and sends ’c’ to the environment (i.e. cell 0). Rule 3 is similar to rule 2. Rule 4, (1, e/λ, 0), sends the object ’e’ to the environment. So, as we have 3 copies of ’a’ and 1 copy of ’e’ in cell 1 and 2 copies of ’b’, one copy of ’c’ and two copies of ’d’ appear in cell 2. Then, all the rules can be applied in a parallel manner. Figure 1(b) show the next configuration of the system after applying the rules. If reader observes the initial elements in the environment of a tissue-like P systems (in this case a, b), one can observe the number of the copies of these elements always appear as one, because we have an arbitrary large amount of copies of them. The only objects changing its number of copies in the environment during a computation are the elements were not appear there initially. In this example, dhas two copies because it is not an initial element of the environment. Fig. 1. (a) Initial Configuration of system Π0(b) Following Configuration of Π0 (a) (b) Next, we introduce a modification of this model in order to deal with arrays. An array tissue-like P system of degree q≥1 with input is a tuple of the form Π= (Γ, V, E, w0, w1, . . . , wq, A1, . . . , Aq,R, iΠ, oΠ), where 1. Γis a finite alphabet, whose symbols will be called objects, 2. Vis the alphabet of colors verifying V∩Γ=∅. 3. Eis a finite subset of arrays on V. 4. w0, w1, . . . , wqare strings over Γrepresenting the multisets of objects associated with the cells at the initial configuration, 5. A1, . . . , Anare arrays on V, placed on the corresponding cells at the initial configuration. 6. Ris a finite set of communication rules of the following form: (i, uiWi/ujWj, j), for i, j ∈ {0,1,2, . . . , q}, i 6=j,ui, uj∈Γ∗and Wi, Wjtwo arrays on V. 42 H.A. Christinal et al. 7. iΠ∈ {0,1,2, . . . , q}is the input cell. 8. oΠ∈ {0,1,2, . . . , q}is the output cell. In a similar way to tissue-like P systems, an array tissue-like P system of degree q≥1 can be seen as a set of qcells (each one consisting of an elementary membrane) labeled by 1,2, . . . , q. We will use 0 to refer to the label of the environment, iΠand oΠdenote the input region and the output region (which can be the region inside a cell or the environment) respectively. The strings w1, . . . , wqdescribe the multisets of objects placed in the qcells of the system. We interpret that w0is the set of objects placed in the environment, each one of them available in an arbitrary large amount of copies. For each i∈ {1, . . . , q}, each Aiis an array placed in the cell iin the initial configuration and Eis the set of arrays placed in the environment, each one of them available in an arbitrary large amount of copies. The empty array ∅always belongs to E. For all the non-empty copies, we will consider that the leftmost pixel of the bottom row in the array corresponds to the coordinates (0,0). Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way (a universal clock is considered), regardless if the environment is involved or not. In one step, each object in a membrane can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e, in each step we apply a maximal set of rules. The main difference with respect tissue-like P systems is related to the application of the rules. Definition 2. Let us consider two index i, j such that i6= 0 6=jand two nonempty arrays Wiand Wj. The communication rule (i, uiWi/ujWj, j)is applicable over two cells labeled by iand jif the following conditions are verified: •uiis contained in cell iand ujis contained in cell j •There exist two arrays, Aiin the cell iand Ajin the cell jand two pairs z1,z2∈Z2such that (a) Wi+z1⊆Ai (b) Wj+z2⊆Aj (c) supp(Wi)∩supp(Wj)6=∅ (d) supp(Ai−(Wi+z1)) ∩supp(Wj+z1) = ∅ (e) supp(Aj−(Wj+z2)) ∩supp(Wi+z2) = ∅ The application of this rule means that the objects of the multisets represented by uiand ujare interchanged between the two cells. The arrays, Aiin the cell i and Ajin the cell jare substituted by A0 iand A0 jrespectively, where A0 i= (Ai−(Wi+z1)) ∪(Wj+z1)A0 j= (Aj−(Wj+z2)) ∪(Wi+z2) Note that if either Aior Ajis the empty array, then the rule is not applicable. Array Tissue-like P Systems 43 Example 2. Let us suppose that we have two cells with labels 1 and 2 with the following objects and arrays, [ z2c3A1]1and [ d3k3bA2]2, with z2, c3, d3, k3, b objects and A1,A2arrays over {R, B, G} A1={h(1,1), Gi,h(1,2), Gi,h(2,2), Ri,h(2,3), Bi} A2={h(5,5), Gi,h(6,5), Gi,h(6,6), Gi} Let us consider the rule r1≡(1, z2W1/ d3k3W2,2) where W1and W2are the arrays W1={h(7,0), Gi,h(7,1), Gi,h(8,1), Ri} W2={h(7,1), Gi,h(8,1), Gi} We will check that r1is applicable to the cells 1 and 2 •z2is contained in the cell 1 and d3k3is contained in the cell 2. •Let us consider z1= (−6,1) ∈Z2and z2= (−2,4) ∈Z2 (a) W1+z1={h(1,1), Gi,h(1,2), Gi,h(2,2), Ri} ⊆ A1 (b) W2+z2={h(5,5), Gi,h(6,5), Gi} ⊆ A2 (c) supp(Wi)∩supp(Wj) = {((7,0),(7,1),(8,1)}∩{(7,1),(8,1)} 6=∅ (d) A1−(W1+z1) = {h(2,3), Bi} and W2+z1={h(1,2), Gi,h(2,2), Gi}. By considering their supports we have supp(A1−(W1+z1)) = {(2,3)}and supp(W2+z1) = {(1,2),(2,2)}, then supp(A1−(W1+z1)) ∩supp(W2+z1) = ∅ (e) A2−(W2+z2) = {h(6,6), Gi} and W1+z2={h(5,4), Gi,h(5,5), Gi, h(6,5), Ri}. By considering their supports we have supp(A2−(W2+z2)) = {(6,6)}and supp(W1+z2) = {(6,4),(5,5),(6,5)}, then supp(A2−(W2+z2)) ∩supp(W1+z2) = ∅ The rule r1is applicable to the cells 1 and 2, and the result of applying the rule is [ d3k3c3A0 1]1and [ z2bA0 2]2where A0 1= (A1−(W1+z1)) ∪(W2+z1) ={h(2,3), Bi,h(1,2), Gi,h(2,2), Gi} A0 2= (A2−(W2+z2)) ∪(W1+z2) ={h(6,6), Gi,h(5,4), Gi,h(5,5), Gi,h(6,5), Ri} Next, we define the applicability of a rule if one of the regions involved is the environment and the arrays are not empty. Definition 3. Let us consider an index i6= 0 and two non-empty arrays Wiand W0. The communication rule (i, uiWi/u0W0,0) is applicable over two cells labeled by iand 0if the following conditions are verified: •uiis contained in cell iand u0is contained in cell 0 •There exist an array Aiin the cell iand two pairs zi,z0∈Z2such that 44 H.A. Christinal et al. (a) Wi+zi⊆Ai (b) supp(Wi+zi)∩supp(W0+z0)6=∅ (c) supp(Ai−(Wi+zi)) ∩supp(W0+z0) = ∅ The application of this rule means that the objects of the multisets represented by uiis removed from the cell iand substituted by the multiset represented by u0. The arrays, Aiin the cell iis substituted by A0 iwhere A0 i= (Ai−(Wi+zi)) ∪(W0+z0) Example 3. Let us suppose the cell 1 with the following objects and arrays, [z3 2c3A1]1and A1the array over {R, B, G} A1={ h(5,2), Ri,h(6,2), Bi,h(7,2), Gi,h(8,2), Bi} h(9,2), Ri,h(6,1), Bi,h(8,1), Bi} Let us consider the rule r1≡(1, z2W1/ d2W0,0) where W1and W0are the arrays Wi={h(3,3), Bi,h(3,4), Bi} W0={h(0,0), Ri} Let us suppose that d2belongs to w0and W0belongs to E. In order to prove that r1is applicable, first we check that z2is contained in the cell 1 and, according to the previous claim, d2is contained in the environment. We have several possibilities to choose the pair zi,z0. The different choices show the no determinism of the system. We also apply the rule with maximal parallelism. In this case we take the following option: the pair zi,z0with zi= (3,−2) and z0= (6,1) for the first application of the rule and the pair z∗ i,z∗ 0with z∗ i= (5,−2) and z∗ 0= (8,2) for the second application. (a) W1+zi={h(6,1), Bi,h(6,2), Bi} ⊆ A1 (a) W1+z∗ i={h(8,1), Bi,h(8,2), Bi} ⊆ A1 (b) supp(Wi+zi)∩supp(W0+z0) = {(6,1),(6,2)}∩{(6,1)} 6=∅ (b) supp(Wi+z∗ i)∩supp(W0+z∗ 0) = {(8,1),(8,2)} ∩ {(8,1)} 6=∅ (c) supp(Ai−(Wi+zi)) ∩supp(W0+z0) = {(5,2),(7,2),(8,2),(9,2),(8,1)} ∩ {(6,1)}=∅ (c) supp(Ai−(Wi+zi)) ∩supp(W0+z0) = {(5,2),(6,2)(7,2),(9,2),(861)} ∩ {(8,2)}=∅ The rule r1is applicable and the result of applying the rule twice is [d2 2z2c3A0 1]1 where A0 1= (A1−(W1+z1)−(W1+z1)∗)∪(A0+z0)∪(A0+z∗ 0) ={h(5,2), Ri,h(7,2), Gi,h(9,2), Ri,h(6,1), Ri,h(8,2), Ri} Finally, let us consider the case in which one of the regions involved in the rule is the environment and the array considered in the environment is the empty array. Array Tissue-like P Systems 45 Definition 4. The communication rule (i, uiWi/u0,0) is applicable over two cells labeled by iand 0if the following conditions are verified: •uiis contained in cell iand u0is contained in cell 0 •There exist an array Aiin the cell iand a pair zi∈Z2such that Wi+zi⊆Ai The application of this rule means that the objects of the multisets represented by uiis removed from the cell iand substituted by the multiset represented by u0. The array Aiin the cell iis substituted by A0 iwhere A0 i= (Ai−(Wi+zi)) Example 4. Let us suppose the cell 1 with the following objects and arrays, [z3 2c3A1]1and A1the array over {R, B, G} A1={ h(5,2), Ri,h(6,2), Bi,h(7,2), Gi,h(8,2), Bi} h(9,2), Ri,h(6,1), Bi,h(8,1), Bi} Let us consider the rule r1≡(1, W1/ d, 0) where W1is the array Wi= {h(3,3), Bi}. Let us suppose that dbelongs to w0. In this case, we have four possibilities to choose zi. They are (3,−2),(3 −1),(5,−2),(5,−1). It is trivial to check that the rule is applicable. It will be applied with maximal parallelism, so the rule will be applied four times and the result of applying the rule twice is [d4z3 2c3A0 1]1where A0 1={h(5,2), Ri,h(7,2), Gi,h(9,2), Ri} 4 Using Array Tissue-like P Systems in Digital Image In digital image terminology, given a finite alphabet of colors Vand a blank object # such that # 6∈ V, a two-dimensional (2D) digital image is a pair (S, AS), where S⊂N2and AS:S→V∪ {#}is an array on S. The size of V,|V|, is the number of its elements. Moreover, we can introduce an order of colors in an image. We define the ordered alphabet associate to an image like a pair (V, <V), where <Vis an order in the set V. The definition of pixel is associated with arrays, i.e., with equivalence classes of arrays. In this way, it makes sense that we study the adjoining relation of two pixels of generic positions (i, j) and (i0, j0) by exploring the relation among these generic coordinates. For the sake of simplicity, we write the pixel <(i, j), a > as aij. There exists two natural way of defining adjacent pixels: 4-adjacency and 8-adjacency [17, 18]. In the first case, given a pixel Kij, the list of adjacent pixels to this is {Kij−1, Kij+1, Ki−1j, Ki+1j}i.e.; the adjacent pixels to any pixel Kij are just north, south, west, east of this (no in the diagonal respect to considered pixel). In the second we consider the pixel Kij (where K=B∨K=W), the list of adjacent pixels to this is {Ki−1j−1, Ki−1j, Ki−1j+1, Kij−1, Kij+1, Ki+1j−1, Ki+1j, Ki+1j+1}i.e.; the adjacent pixels to a any pixel Kij are just up, down, right and left of this and, moreover, we consider the diagonal objects.