Computing Homology Groups in Binary 2D Imagery by Tissue-like P Systems

ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY Volume 13, Number 2, 2010, 141–152 Computing Homology Groups in Binary 2D Imagery by Tissue-like P Systems Daniel D´ IAZ-PERNIL1, Miguel A. GUTI´ ERREZ-NARANJO2, Pedro REAL1, Vanesa S´ ANCHEZ-CANALES1 1Research Group on Computational Topology and Applied Mathematics, Department of Applied Mathematics, University of Sevilla, Spain E-mail: {sbdani,real,vscanales}@us.es 2Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Spain E-mail: [email protected] Abstract. We present a new solution for the Homology Groups of Binary 2D Image (HGB2I) Problem by using Membrane Computing techniques. This is a classical problem in Homology Theory which tries to calculate the number of connected components and the representative curves of the holes of these components from a given binary 2D image. To this aim, we present a family of P systems which solves all the instances of the problem in the framework of Tissue-like P systems with catalysts. This is a new framework which combines the membrane structure and symport-antiport communication rules of tissuelike P systems with the power of catalysts. 1. Introduction Homology theory is a branch of Algebraic Topology that attempts to distinguish between spaces by constructing algebraic invariants that reflect the connectivity properties of the space. The field has its origins in the work of the French mathematician, theoretical physicist, and philosopher of science Jules Henri Poincar´e. Homology groups (related to the different n-dimensional holes, connected components, tunnels, cavities, etc., of a geometric object) are invariants from Algebraic Topology which are frequently used in Digital Image Analysis and Structural Pattern Recognition. In 142 D. D´ıaz-Pernil et al. some sense, they reflect the topological nature of the object in terms of the number and characteristics of its holes. In this paper, we explore one of the main problems from Homology Theory in terms of Membrane Computing1. The chosen problem is the Homology Groups of Binary 2D Image (HGB2I) Problem: Given a binary 2D digital image, calculate the number of connected components and the representative curves of the holes of these components. The algorithms for solving this problem have an immediate application in Digital Imagery, since the topological information is one of the key points in image classification, indexing, shape description and shape recognition. This is not the first bio-inspired approach to problems in Algebraic Topology. In 1996, Chao and Nakayama connected Natural Computing and Algebraic Topology using Neural Networks [5] by extended Kohonen mapping. Some years after, Subramanian et al. presented in [3, 4] two works where Digital Image and Natural Computing were linked. Our paper can be seen as a new step from the work by Cristinal et al. [6, 7] in their effort for bridging Membrane Computing and Algebraic Topology. The solution presented in this paper to the HGB2I problem has been designed in a new P system framework called tissue-like P systems with catalysts. It combines the membrane structure and symport-antiport communication rules with the power of catalysts. The time to calculate the homology groups of 2D digital images with these P systems is logarithmic with respect to the input data with size n2. This involves an improvement with regard to the algorithms developed by Peltier et al. in [21], where they use irregular graphs pyramids with a time complexity of O(n5/3). The paper is organized as follows: in the next section we formally present the framework of tissue-like P systems with catalysts. In Section 3, we show how these P systems can be used to solve the H0and H1problems in Homology Theory and illustrate the solution with a pair of examples. The paper ends with some final remarks and open lines for the future. 2. Tissue-like P Systems with Catalysts Tissue P systems were introduced in [14, 15]. This P system model is inspired by the intercellular communication and cooperation between neurons. The mathematical model of these devices 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 [16]. Symport rules move objects across a membrane together in one direction, whereas antiport rules move objects across a membrane in opposite directions. In tissue-like P systems the membrane structure is a general undirected graph. The edges of such graph are not given explicitly, but they are deduced from the set of rules. From the seminal definition of tissue P systems, several research lines have 1We refer to [18] for basic information in this area, to [20] for a comprehensive presentation and the web site [22] for the up-to-date information. Computing Homology Groups by P Systems 143 been developed and other variants have arisen (see, for example, [1, 2, 10, 12, 19]). Catalytic P systems were introduced by P˘aun in [17]. The main feature of these P systems is the presence of objects in membranes such that they are not consumed by the application of the rule, but their presence in the membrane is necessary for triggering the rules. Catalysts have been deeply studied in Membrane Computing (see, e.g. [9, 11, 13]), but to the best of our knowledge, this is the first time when catalysts are used for tissue P systems2. Next, we provide the definition of tissue-like P systems with catalysts: Definition 2.1. Atissue-like P system with catalysts of degree q≥1 is a tuple of the form Π = (Γ,E, w1, . . . , wq,R, i0), where: 1. Γ is a finite alphabet, whose symbols will be called objects. 2. E ⊆ Γ is a finite alphabet representing the set of the objects in the environment available in an arbitrary large amount of copies. 3. w1, . . . , wqare strings over Γ representing the multisets of objects associated with the cells in the initial configuration. 4. Ris a finite set of catalytic rules of the following form: (cat |i, u/v, j) for i, j ∈ {0,1,2, . . . , q}, i 6=jand cat, u, v ∈Γ∗. The length of a catalytic rule is defined as |u|+|v|. The catalyst cat is not modified by the application of the rules. 5. i0∈ {0,1,2, . . . , q}denotes the output region, which can be the environment (i0= 0) or the region inside a cell (1 ≤i0≤q). Informally, a tissue-like P system with catalysts of degree q≥1 can be seen as a set of qcells (each one consisting of a single membrane) 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 system, i.e., as usual in tissue-like P systems, the edges linking cells are not provided explicitly: If a rule (cat |i, u/v, j) is given, then cells iand jare considered linked. The application of a catalytic rule (cat |i, u/v, j) consists of the trade of the multiset u(initially in the cell i) against the multiset v(initially in j). The rule can be applied if the multiset cat is placed in the membrane with label i. We can also trade objects between one cell and the environment, labeled by 0. The rule is applied if in the cell with label ithe objects of the multiset cat are present. If the catalyst cat is empty, then the rule is called a communication rule. In our definition, all objects in the alphabet can act as catalysts, depending on the applied rule. 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 2Comprehensive information about catalytic P systems can be found at [8]. 144 D. D´ıaz-Pernil et al. 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 multiset of rules. Aconfiguration is an instantaneous description of the P system and it is represented as a tuple (w0 1, . . . , w0 q). 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 sequence of computation steps is called a computation. A configuration is halting when no rules can be applied to it. The output of a computation is collected from its halting configuration by reading the objects contained in the output cell. Example 2.1. Let us consider the following tissue-like P system with catalysts of degree 3, Π = (Γ,E, w1, w2, w3,R, i0) where Γ = {a, b, c, d, e},E={a, b},w1=a, w2=bd and w3=ce. The set Rhas four rules: r1≡(c|2, b/a, 1) r2≡(e|3, c/d, 2) r3≡(3, d/a, 0) r4≡(3, d/b2,0) The output region is i0= 3. According to the set of rules, cell 2 is linked to cells 1 and 3 and cell 3 is linked to the environment. The computation starts from the initial configuration C0= (w1, w2, w3). Rule r1cannot be applied in this initial configuration, since the catalyst cdoes not appear in cell 2. Rules r3and r4cannot be applied, since object dis not placed in cell 3. In this initial configuration, we only can apply rule 2, since objects eand care placed in membrane 3 and dis placed in membrane 2. After applying this rule, we obtain a new configuration. C1= (w0 1, w0 2, w0 3) with w0 1=a,w0 2=bc and w0 3=de. Now, rule 1 can be applied by interchanging objects aand b, because the catalyst cis placed in cell 2. The communication rules 3 and 4 can be applied, since dappears in cell 3 and the environment contains objects a and b, but only one of them can be applied, and it is non-deterministically chosen. If we choose rule 3, then the new configuration is C2= (w00 1, w00 2, w00 3) with w00 1=b, w00 2=ac and w00 3=ae. No more rules can be applied and the computation finishes. The output of the computation is the multiset in cell 3 in the halting configuration w00 3=ae. If we choose rule 4, the obtained configuration is the same, but w00 3=b2e. 3. Using Tissue-like P Systems to Obtain H0and H1 As pointed out above, given a binary 2D digital image, the HGB2I problem consists of calculating the number of connected components and the representative curves of the holes of these components (a hole is a white connected component surrounded by one black connected component). We can divide this problem in two sub-problems: the H0problem consists of calculating the number of connected components and the H1problem, which consists of calculating the number of holes. In this paper we present a new technique to use tissue-like P systems with catalysts to obtain homological information of binary 2D digital images. A 2D digital image Ican be considered as a matrix of objects called pixels. In this paper, a pixel of a digital image will be an object Kij, where (i, j) denotes the Computing Homology Groups by P Systems 145 position of the object in the matrix and Kis the color of the pixel, K=b(black) or K=w(white). The basic relation among pixels is the adjacency relation. There exist two natural possibilities: the 4-adjacency (Von Neumann neighborhood in cellular automata) and the 8-adjacency (Moore neighborhood in cellular automata). In the first case, given a pixel Kij, the set of its adjacent pixels is {Kij−1, Kij+1, Ki−1j, Ki+1j}, i.e., the adjacent pixels to any pixel Kij are just north, south, west, east from it. In the second case, the set of adjacent pixels to Kij 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 pixel are north, south, west, east ones and the diagonal pixels. In this paper, we will consider 4-adjacency for black pixels and the 8-adjacency for white pixels. We must remember this consideration is due to the concept of holes. If we see Figure 1, we find two connected black components and no holes. If we would consider 4-adjacency for white pixels we would have a hole, then we choose 8-adjacency for white pixels. 3.1. Solving H0Problem In order to provide a logarithmic-time uniform solution to the H0problem, we design a family of tissue-like P systems with catalysts, Π0={Π0(n)}n∈N. Each P system Π0(n) of the family will process all pictures of n×npixels3. Given an n×n image I, we will consider a set of n2objects zij with z=wor z=bas the encoding of the image. Besides the objects wij and bij, the alphabet of the P system will contain objects {ai: 1 ≤i≤n+ 2}which will be used as a counter and {(bij,(k, l)) : (1,1) ≤ (i, j)≤(k, l)≤(n, n)}, where we consider the lexicographic4order between pixels. Given an object (bij,(k, l)) we will say that (k, l) is a label associated with bij . We will also consider objects {Aijkl : (1,1) ≤(i, j)<(k, l)≤(n, n)}. The family of P systems is defined as follows: Π0(n) = (Γ,E, ω1, ω2,R, i0) where: •Γ = {ai: 1 ≤i≤n+ 2}∪{bij, wij : 1 ≤i, j ≤n} ∪ {(bij,(k, l)) : (1,1) ≤ (i, j)≤(k, l)≤(n, n)}∪{Aijkl : (1,1) ≤(i, j)<(k, l)≤(n, n)}. • E = Γ − {bij, wij : 1 ≤i, j ≤n} •ω1={a1}. •ω2=∅. • R is the set of rules: 3The input will be a squared digital image. If the initial image is not squared, it will be filled with white pixels. 4(i, j)<(k, l)⇔i<k∨(i=k∧j < l) 146 D. D´ıaz-Pernil et al. ◦R1≡(1, ai/ai+1,0) for 1 ≤i≤n+ 1. These rules generate a counter that will be used in the output of the system. ◦R2≡(1, bij/(bij,(i, j)),0) for 1 ≤i, j ≤n. These rules add labels to black pixels in order to work with them. ◦R3≡(1,(bij,(k, l))(bi0j0,(k0, l0))/(bij,(k, l))(bi0j0,(k, l))Aklk0l0,0) for (1,1) ≤(k, l)<(k0, l0)≤(n, n), and (i, j), (i0, j0) adjacent positions in the array. ◦R4≡(1,(bij,(k, l))(bi0j0,(k0, l0))/(bij,(k0, l0))(bi0j0,(k0, l0))Ak0l0kl,0) for (1,1) ≤(k0, l0)<(k, l)≤(n, n) and (i, j), (i0, j0) adjacent positions in the array. The two last types of rules change the labels of adjacent pixels. We need all the adjacent black pixels to have the same label, so we will know that they are all in the same connected component. ◦R5≡(Aijkl|1,(bi0j0,(k, l))/(bi0j0,(i, j)),0) for 1 ≤i, j, k, l, i0, j0≤n. In these rules, objects Aijkl act as catalysts. The catalyst has been created when the pixel labeled by (k, l) traded its label for (i, j), so (i, j) and (k, l) are adjacent pixels and other pixels with these labels can be changed. ◦R6≡(an+2|1,(bij,(i, j))/λ, 2). With these rules we send one pixel for each connected component to the cell 2. •i0= 2 is the output cell. The initial configuration will be C0= (w1∪I, w2), where Iis the encoding of the image by objects wij and bij. Each system of the family implements the following stages: 1. Label Allocation Stage: Cell 1 trades objects bij against others of the form (bij,(i, j)) with the environment. The white objects are not transformed. 2. Label Conversion Stage: We can compare the black adjacent pixels by using catalyst, and we trade the label of the greatest pixel against the label of the other pixel, i.e., (1,(bij,(i0, j0))(bkl,(k0, l0))/(bij,(i0, j0))(bkl,(i0, j0))Ai0j0k0l0,0), where (i, j) and (k, l) are adjacent pixels. Moreover, we can see a new object arriving to cell i. It is a catalyst and it is used to codify if two labels must be compared. Later, they are connected, and one of them can be traded against the other one, as we can see in the Figure 1. 3. Answer Stage: In the step n+ 2, the object an+2 arrives to the cell 1 due to the counter. It is used by the system as a catalyst, and the objects of the form (bij,(i, j)) are sent to the output cell representing each one to a black connected component. The P system has used n+ 2 steps to obtain the number of black connected components of an n2image. Figure 1 shows a computation of the Π0(7) system whose input data is the configuration C0of the picture. Computing Homology Groups by P Systems 147 Fig. 1. A simple example to obtain H0. 3.2. Solving H1Problem With respect to the H1problem we use the same technique presented above, where labels are associated with the objects codifying pixels. The main technical novelty is that we introduce priorities in the rules of the tissue P system with catalysts. We construct a family of tissue-like P systems with catalysts Π1={Π1(n)}n∈Nto obtain a solution of the H1problem. Moreover, we can obtain the curves formed by black pixels containing the holes of the black connected components of the input image. So, we introduce in this paper a technique for segmenting images using catalysts. Given an image Iof size n2we take the system of the family Π1(n) to work with I. The input data (image I) is codified by a set of the following objects: bij and wij for 1 ≤i, j ≤n. Then, each pixel of the image is given by an object zij with z=b∨z=w. The family of P systems is defined as follows: Π1(n) = (Γ,E, ω1, ω2,R=R1∪ · · · ∪ R10},{R6,R8}> R1, i0) where: •Γ = {zi: 1 ≤i≤n+ 3} ∪ {bij,¯ bij, wij,(wij,(k, l)) : 1 ≤i, j, k, l ≤n} ∪ {(pij,(0,0)),(pji,(0,0)) : i= 0, n + 1,0≤j≤n+ 1} ∪ {Zijkl : (1,1) ≤(i, j)<(k, l)≤(n, n)}. • E = Γ − {bij, wij : 1 ≤i, j ≤n}. •ω1={z1,(pij,(0,0)),(pji,(0,0)) : i= 0, n + 1,0≤j≤n+ 1}. •ω2=∅. •The sets of rules are: ◦R1≡(1, zi/zi+1,0) for 1 ≤i≤n+ 5. This rule counts the number of steps of the process. We will use this to 148 D. D´ıaz-Pernil et al. start the Deleting Stage after n+ 2 steps, and the Segmenting Stage after n+ 4 steps. ◦R2≡(1, wij/(wij,(i, j)),0) for 1 ≤i, j ≤n. These are the unique rules used in the Label Allocation Stage. These rules add labels to white pixels in order to work with them. ◦R3≡(1,(wij,(k, l))(wi0j0,(k0, l0))/(wij,(k, l))(wi0j0,(k, l))Zklk0l0,0) for (1,1) ≤(k, l)<(k0, l0)≤(n, n), wij, wi0j0adjacent pixels. ◦R4≡(1,(wij,(k, l))(wi0j0,(k0, l0))/(wij,(k0, l0))(wi0j0,(k0, l0))Zk0l0kl,0) for (1,1) ≤(k0, l0)<(k, l)≤(n, n), wij, wi0j0adjacent. These two set of rules are used in Label Conversion Stage to compare two adjacent white pixels, and change the label of one of them. We need all the adjacent white pixels to have the same label. ◦R5≡(Zijkl|1,(wi0j0,(k, l))/(wi0j0,(i, j)),0) for 1 ≤i, j, k, l, i0, j0≤n. The catalyst Zijkl increases the speed of the process. It has been created when the pixel labeled by (k, l) traded its label for (i, j), so (i, j) and (k, l) are adjacent pixels and other pixels with these labels can be changed. ◦R6≡(zn+3|1,(pij,(0,0))(wkl,(k0, l0))/(pij,(0,0))(pkl,(0,0))Z00kl,0) for (i, j),(k, l) 8-adjacent pixels, 0 ≤i, j ≤n+ 1, 1 ≤k, l, k0, l0≤n. These rules uses objects (pij ,(0,0)). We will refer to these objects as pink pixels. The rules are used in Deleting Stage to delete white pixels which are out of the connected black component. By using 8-adjacency, we transform outer white pixels into pink pixels, in order to differentiate them from the interior white pixels (holes). ◦R7≡((Z00ij|1,(wi0j0,(i, j))/(pi0j0,(0,0)),0). A new catalyst acts in the same way, trading white exterior pixel for pink pixels. In this way, the Deleting Stage takes only 2 steps. ◦R8≡(zn+5|1,(wij,(i0, j0))bkl/(wij,(i0, j0))¯ bkl,0) for wij, bkl 8-adjacent pixels 1 ≤i0, j0, i, j, k, l ≤n. In the Segmenting Stage a black pixel is marked if it and a white pixel are 8-adjacent pixels. It starts after n+ 2 steps. ◦R9≡(1,¯ bij/λ, 2) for 1 ≤i, j ≤n. At the end, in the Answer Stage, black marked pixels are sent to membrane number 2, so we obtain which black pixels are containing the holes. ◦R10 ≡(zn+6|1,(wij,(i, j))/λ, 2) for 1 ≤i, j ≤n. We want to obtain the number of holes as well, so these rules send one white pixel for each hole to membrane number 2. • {R6, R8}> R1represents the priority relation among the rules from the sets R1,R6and R1: Rules from sets R6and R8are applied before rules from the set R1. •i0= 2 is the output cell. Computing Homology Groups by P Systems 149 The initial configuration is C0= (w1∪I, w2). The computation of each P system of the family has the following phases: 1. Label Allocation Stage: Cell 1 trades objects wij against others with the form (wij,(i, j)) with the environment. 2. Label Conversion Stage: We compare the labels of two white adjacent pixels, and we trade the label of the greatest pixel against the label of the other pixel, i.e., we use rules with the form (1,(wij,(i0, j0))(wkl,(k0, l0))/(wij,(i0, j0))(wkl,(i0, j0))Zi0j0k0l0,0) where (i, j) and (k, l) are adjacent pixels. Moreover, we can see a new object arriving to cell i,Zi0j0k0l0. It is a catalyst and is used to codify when two labels must be compared. Then, the labels are connected, and one of them can be changed by the other one, as we can see in C7 in the Figure 2. Fig. 2. Representative configurations of a simple example to obtain H1. 3. Deleting Stage: Initially, the system keeps in cell 1 a set of objects codifying the frame of the input image (p0i, pn+1i, pi0, pin+1 for i= 0, . . . , n + 1) with the associated label (0,0). When the input data is introduced in the system, the white pixels not contained inside of black connected components are sent to the environment to trade against objects with the form of the frame. We need a linear number of steps with respect to nto eliminate all the possible white pixels. We can see the result in C11 in the Figure 2.