Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images

1 Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images Daniel Díaz-Pernil* Department of Applied Mathematics I, CATAM Research Group, University of Seville, Spain Email: [email protected] *Corresponding author Ainhoa Berciano Department of Didactic of Mathematics and Experimental Sciences, University of the Basque Country, Spain Email: [email protected] Francisco Pe˜ na-Cantillana and Miguel A. Guti´ errez-Naranjo Department of Computer Science and AI, Research Group on Natural Computing, University of Seville, Spain Email: [email protected] Email: [email protected] Abstract: In this paper, we present a bio-inspired parallel implementation of a solution of the problem of looking for the representative geometrical objects of the homology groups in a binary 2D image (extended-HGB2Iproblem), which is an extended version of a well-known problem in homology theory. In particular, given a binary 2D image, all black connected components and the representative curves of the holes of these components are obtained and labelled. To this aim, a new technique for labelling the connected components of a binary image is presented. In order to compute the solution, the formal framework uses techniques from membrane computing and the implementation has been done in a hardware architecture called compute unified device architecture (CUDA). The computational complexity of the proposed solution is O(m)with respect to the input (image) size m∼n2. Finally, some examples and applications are also presented. Keywords: homology groups; computational algebraic topology; membrane computing; tissue-like P systems; compute unified device architecture; CUDA. Reference to this paper should be made as follows: Díaz-Pernil, D., Berciano, A., Pe˜ na-Cantillana, F. and Guti´ errez-Naranjo, M.A. (xxxx) ‘Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images’, Int. J. Bio-Inspired Computation, Vol. x, No. x, pp.xxx–xxx. Biographical notes: Daniel Díaz-Pernil received his PhD in Mathematics in 2008. He has been an Assistant Professor of the Department of Applied Mathematics I Department at the University of Seville, Spain. He is also a member of the Research Group on Computational Algebraic Topology and Applied Mathematics of the University of Seville. His research interests include topics related to natural computing, digital topology, computational algebraic topology, image processing and pattern recognition. He has coauthored more than 30 scientific papers in these areas. Ainhoa Berciano Alcaraz received her PhD in Mathematics in 2006. Currently, she is an Associate Professor in the Department of Didactic of Mathematics and Experimental Sciences at the University of the Basque Country, Spain. She is also a member of the Research Group on Computational Algebraic Topology and Applied Mathematics of the University of Seville. Her research interests include topics related to computational algebraic topology, digital topology, image processing and pattern recognition, natural computing and didactic of mathematics. She has coauthored more than 25 scientific papers in these areas. 2D. Díaz-Pernil et al. Francisco Pe˜ na-Cantillana finished his studies of Computer Engineering in 2011 at the University of Seville, Spain. His research interests include topics related to digital image and natural computing, both from a theoretical and practical point of view. He is also interested in general-purpose computing on graphics processing units using CUDA. He has coauthored seven scientific papers in these areas. Miguel A. Guti´ errez-Naranjo obtained his PhD in Mathematics in 2002. Currently, he is an Associate Professor in the Computer Science and Artificial Intelligence Department at the University of Seville, Spain. He is also a member of the Research Group on Natural Computing of the University of Seville. His research interests include topics related to artificial intelligence and natural computing, both from a theoretical and practical point of view. He has coauthored more than 40 scientific papers in these areas. 1 Introduction The use of new hardware architectures for dealing with digital images (Rosenfeld and Kak, 1982) needs the development of new parallel algorithms (Parker, 2010; Davies, 2012) able to exploit these new capabilities. Such parallelisation is a complex process, and sometimes, the idea of a simultaneous application of a sequential algorithm to different pieces of the image is not the best starting point, since the synchronisation and coordination of the whole process can decrease the efficiency. Usually, the design of a new parallel implementation not inspired by the sequential one allows an open-mind vision of the problem and the proposal of new creative solutions. In this way, a new technique to label connected components of a binary 2D image is presented in this paper. This technique can be extended to nD images in a natural way. In this paper, a bio-inspired parallel implementation of a solution of the homology groups of binary 2D image HGB2I problem is presented. It is a well-known problem in homology theory which tries to calculate the number of connected components and the representative curves of the holes of these components of a given binary 2D image. In some sense, it tries to extract useful information from the topological interactions of the parts, instead of considering only their geometry. Such study goes beyond the mere description of the geometrical properties of the image and provides information for identifying objects in areas such as hand-writing, satellite image processing, structural pattern recognition or the analysis of some medical images. The proposed solution bridges algebraic topology and natural computing. Moreover, this new approach has been implemented in a parallel hardware technology which allows to obtain promising results from the practical point of view. The relationship between algebraic topology and natural computing is not new. Chao and Nakayama (1996) connected both areas using neural networks by extended Kohonen maps. Some years after, Giavitto and Michel (2002) studied the topological structure of the membrane computing and (Ceterchi et al., 2003a, 2003b) published two works where digital image is introduced in the framework of the membrane computing. The problem of calculating the homology groups of a binary 2D image has been broadly studied. In the literature, one can find some sequential solutions to this problem, as in Peltier et al. (2007), and even parallel solutions (see e.g., Christinal et al., 2009b, 2009c; Díaz-Pernil et al., 2010b). One of the drawbacks of the classical algorithms is related to the computational complexity. In this way, a new advance was presented in Christinal et al. (2009b, 2009c) where a solution was given in the framework of membrane computing. The necessary time to calculate the homology groups of 2D digital images with the membrane computing techniques defined in these papers is O(m)with respect to the input (image) size m∼n2. This means an improvement with respect to the algorithm developed by Peltier et al. (2007), where they use irregular graph pyramids with a time complexity of O(n5/3). The solution proposed in this paper is inspired by membrane computing techniques and it represents a significant improvement with respect to the design presented in the previous papers. The model of computation used in Christinal et al. (2009b) was a basic P system and the model in Christinal et al. (2009c) was tissue-like P systems. In both cases, two membrane systems are necessary: one for obtaining the number of connected components and a second system for the number of holes. After that, a better solution was given in Díaz-Pernil et al. (2010b), where a single system appears to obtain the Betti numbers (number of connected components and number of holes of these components of a given binary 2D image) and even the complexity results are improved. It is worth to remark that the proposed membrane system design solves an extended version of the homology groups problem using membrane computing. It does not only calculate the Betti numbers as in the papers previously cited; but also each black connected component and the boundary curve of each hole that appears in a given binary 2D digital image is found by using membrane computing techniques. The development of new parallel computer algorithms is currently explored in different hardware architectures (clusters, grids, FPGA, ...). The chosen hardware architecture for our parallel implementation has been the Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images 3 compute unified device architecture (CUDA). This is a general purpose parallel computing architecture that allows the parallel NVIDIA graphics processing units (GPUs) to solve many complex computational problems in a more efficient way than on a CPU. The use of this new parallel architecture is currently explored as a tool for parallelising the treatment of digital images (Carranza et al., 2012; Moulik and Boonn, 2011). The choice of this parallel architecture is supported by several reasons. Firstly, the computing language CUDA supplies to programmers a model for implementing easily parallel programs, but the main reason comes from the practical side. In the last years, there exists an increasing interest in the specialised industry for the development of more and more powerful Graphic Processing Units which can be used for general purposes. This interest leads, on the one hand, to a more economically accessible (and hence, more extended) hardware and, on the other hand, to the development of more powerful computational units. The theoretical foundation of our parallel implementation is based on natural computing processes, namely, membrane computing. As it will be shown below, membrane computing techniques are inspired in the flow of metabolites between cells of a living tissue or between the organelles in an eukaryote cell. This flow of metabolites takes place in parallel in Nature and can be interpreted as a flow of information for computational purposes. Instead of a set of few instructions with complex data structures, the computation steps in a membrane computing device are regulated by a set of rules with a notation close to biochemical reactions. From a computational point of view, such reactions can be read as a set of if A then B rules where Aand Bare very simple data. As we will show later, this theoretical construction fits perfectly for a computational implementation within the GPU architecture, although other parallel implementations of Membrane Computing systems can be found in the literature (see e.g., Petreska and Teuscher, 2003; Nagy and Szegedi, 2006; Van Nguyen et al., 2007; Díaz-Pernil et al., 2010a). The paper is organised as follows: firstly, the bio-inspired formal framework is described. Next, we briefly recall the HGB2I. In the next section, we explain in detail our solution in the framework of tissue-like P systems with promoters to the extended-HGB2I problem and provide an illustrative example. In Section 4.1, some applications are shown. Finally, some conclusions are presented. 2 Membrane computing Natural computing studies new computational paradigms inspired from Nature. It abstracts the way in which Nature acts, conceiving new computing models from natural phenomena in physics, chemistry and biology. It studies human-designed computing inspired in Nature as well as computation taking place in Nature. The former involves several well established fields, such as cellular automata (von Neumann and Burks, 1966), genetic algorithms (Holland, 1992), neural networks (McCulloch and Pitts, 1988) or swarm intelligence (Engelbrecht, 2005). The latter involves self-assembly (Krasnogor et al., 2008), the computational nature of biochemical reactions (Ehrenfeucht and Rozenberg, 2009) or bacterial communication (Xavier et al., 2011). In this paper we use techniques from membrane computing (P˘ aun, 2002; P˘ aun et al., 2010), an emergent cross-disciplinary branch of natural computing introduced by P˘ aun (2000). It has received important attention from the scientific community since then, with contributions by computer scientists, biologists, formal linguists and complexity theoreticians, enriching each other with results, open problems and promising new research lines. This research area was born from the assumption that the processes taking place within the compartmental structure of a living cell can be interpreted as computations (P˘ aun, 2002). In particular, it focuses on membranes, which are involved in many reactions happening inside various compartments of a cell. Biological membranes are much more than mere barriers that define compartments. They act as selective channels of communication between different compartments as well as between the cell and its environment (Alberts et al., 2002). The basis of the techniques used in this paper is that the biological cells can be seen as computational devices and the transport of chemicals across biological membranes can be seen as a flow of information between such computational devices. In biology, some proteins use the energy stored in the electrochemical gradient of Na+or H+ions to power the movement of another substance through a membrane in a process called cotransport. When the protein and the ion move in the same direction, the process is called symport; when they move in opposite directions, the process is called antiport. Symport/antiport rules were introduced in membrane computing in P˘ aun and P˘ aun (2002) and nowadays are profusely used in the flow of information. The computational devices in membrane computing are called P systems. Roughly speaking, a P system consists of a membrane structure that divides the Euclidean space into regions which contain objects. Such objects can be described by symbols from a given alphabet. The objects, and hence the information, can pass through membranes, under the control of specific rules. An input, encoded as a multiset of objects, is placed in a region at the beginning. Then, the flow of objects through the membranes starts. When the flow of information halts (no more rules can be applied), the multiset of objects placed in a specific region is considered the output of the computation. We will focus here on the so-called tissue-like P systems (Martín-Vide et al., 2003), based on intercellular communication and cooperation between cells in a tissue. A tissue-like P system can be seen as 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. tissue-like P systems have been extensively used to solve computational problems in other areas (see e.g., Alhazov et al., 2005; 4D. Díaz-Pernil et al. Sheeba et al., 2011; Guti´ errez-Escudero et al., 2009; Díaz-Pernil et al., 2007a, 2007b; Christinal et al., 2009a). From a technical point of view, let us notice that the basic tissue-like P system model used in this paper has been endowed with some extra features. First of all, the application of the rules is regulated by promoters. These promoters have a clear biological inspiration. The rule is applied if the reactants are present, but it is also necessary that the promoter is present in the cell. The promoter is not consumed nor produced by the application of the rule, but if it is not placed 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. The second feature is the partial priority relationship among the rules, which control the flow of objects. In the general case, if there are several possibilities, the rule is non-deterministically chosen, but sometimes, a priority relation between rules is considered. Such partial relation is static, i.e., it does not change along the computation and it is fixed in the definition of the P system. In a similar way to other computational devices, the tissue-like P systems with promoters and priorities used in this paper are designed to receive an input and to provide an output. In accordance with the biological inspiration, the input of the device is a multiset of objects from the alphabet that is placed in an input cell. The computation starts when the input is placed in such cell. It consists of a flow of objects among cells or against the environment according to a given rules. When the computation halts, the output is encoded as a multiset placed in a specific cell known as the output cell. 2.1 Formal framework Next, we recall the formal definition of these P systems. Definition 2.1: Atissue-like P system with promoters and priorities of degree q≥1is a tuple of the form Π = (Γ,Σ,E, w1, . . . , wq,R, P ri, iin, iout) where qis the number of cells of the P system and 1Γis a finite alphabet, whose symbols are 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. 3E ⊆ Γ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. 4w1, . . . , wqare strings over Γrepresenting the multisets of objects placed inside the cells at the starting of the computation. 5Ris a finite set of rules of the following form: (pro |i, u/v, j),for 0≤i=j≤q, pro, u, v ∈Γ∗ 6P ri is a finite set of relations Ri> Rj, where Riand Rjare rules from R: If Riand Rjcan be applied, then the application of Rihas priority on the application of Rj. 7iin ∈ {1,2, . . . , q}denotes the input cell, i.e., the cell where the input of the computation will be placed. 8iout ∈ {1,2, . . . , q}denotes the output cell, i.e., the objects placed in this cell in a halting configuration are interpreted as the output of the computation. Informally, a tissue-like P system with promoters and priorities of degree q≥1can be seen as a set of q cells labelled 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: If a rule (pro |i, u/v, j)is given, then cells iand jare considered linked. Notice that ior jcan be 0. This is the label of the environment: If i= 0, then, the cell jis considered linked with the environment and it can trade objects with it. The application of a rule (pro |i, u/v, j)consists on the trade of 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 vdisappears from the cell jand it appears in the cell i. The trade can also be between one cell and the environment, labelled by 0. The rule can be applied only if the multiset pro (promoter) is present in the cell labelled by i. The promoter is not modified by the application of the rule. If the promoter is empty, we will write (i, u/v, j)instead of (∅ | i, u/v, j). Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel synchronous way (a universal clock is considered). A configuration is an instantaneous description of the multisets of objects placed in the cells of the P system and it is represented as a tuple (w1, . . . , wq). Given a configuration, a computation step is performed and a new configuration is obtained 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. Acomputation is a sequence of computation steps such that either it is infinite or it is finite and the last step yields a halting configuration. 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. Let us notice that at the starting of the computation, the input cell has objects from two different sources: on the one hand, it contains the multiset wiwhich is settled in the description of the P system and it is common for all the computations; on the other hand, it also contains a multiset of objects encoding the specific input for a particular computation. If iis the label of the input cell,ˆwi will denote the initial multiset of the cell after adding the input. Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images 5 Example: Let us consider the following tissue-like P system with promoters and priorities of degree 2, Π = (Γ,Σ,E, w1, w2,R, P ri, iin, iout) where the working alphabet is Γ = {a, b, c, d, e, f, h, z}, the input alphabet is Σ = {a}, the environment alphabet is E={f}and the initial multisets of the cells 1 and 2 are w1=bdz2and w2=c2deh4. The set Rhas seven rules: R1≡(bd|1, az/h2,2) R2≡(1, z/d, 2) R3≡(2, de/f5,0) R4≡(f4|2, c2/ab, 1) R5≡(f3|2, a2z/d, 1) R6≡(z|1, c2/f, 0) R7≡(z2|2, ab/λ, 0) Pri ={R3> R2}, the input cell is iin = 1 and the output cell is iout = 2. The input for the computation will be the multiset a3(three copies of the object a), which will be placed in cell 1 at the beginning. In this way, the starting configuration is C0= ( ˆw1, w2)with ˆw1=a3bdz2 and w2=c2deh4. According to the set of rules, cells 1 and 2 are linked and both of them are linked to the environment. The computation starts from the initial configuration C0. Rule R1can be applied twice, since the promoter bd is placed in the cell 1 and there are objects enough for two applications. Applying twice this rule, the multiset a2z2is sent from cell 1 to cell 2 and the multiset h4from cell 2 to cell 1. The rule R2can also be applied once, since there is one object din membrane 2 and R3can be applied, since we are considering an arbitrarily large amount of objects fin the environment. Rules 2 and 3 cannot be applied simultaneously, since there is only one object din the cell 2. In order to decide which rule is applied, we look at the set P ri and observe that rule R3has priority over R2 and then, de will be traded against f5. Rules from R4to R7cannot be applied in this first step. By application of rules R1(twice) and R3the configuration C1= (w′ 1, w′ 2)is achieved with w′ 1=abdh4and w′ 2=a2c2f5z2. In the next step, rules from R1to R3,R6and R7 cannot be applied. The rule R4can be applied, since we can find four objects fin cell 2 that can act as promoters (in fact, more than 4). The application of this rule trades the multiset c2in the cell 2 against ab in cell 1. Analogously, R5can also be applied. The application of this rule sends the objects a2zto the membrane 1 and one object dis brought from it. By the application of the rules R4and R5 the configuration C2= (w′′ 1, w′′ 2)with w′′ 1=a2c2h4zand w′′ 2=abdf5zis obtained. In the next step, rules R2and R6can be applied and C3= (w′′′ 1, w′′′ 2)with w′′′ 1=a2dfh4and w′′′ 2=abf5z2is reached. Finally, only R7can be applied. This is a symport rule: objects ab are sent to the environment and nothing is brought from it. No more rules can be applied, C4= (w′′′′ 1, w′′′′ 2)with w′′′′ 1=a2dfh4fand w′′′′ 2=f5z2is a halting computation and the multiset f5z2placed in the output cell 2 is considered the output of the computation. 3 Obtaining representative geometrical objects of the homology groups In this paper, tissue-like P systems are used to obtain the representative geometrical objects of homology groups in 2D images. 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 Henri Poincar´ e. Homology groups (related to the different n-dimensional holes, connected components, tunnels, cavities, etc.) are invariants from algebraic topology, which are frequently used in digital image analysis and structural pattern recognition. In some sense, they reflect the topological nature of the object in terms of the number and characteristics of its holes. Computing the homology groups in a binary 2D image is counting the number of connected components and the number of 1-dimensional holes. Bearing this fact in mind, the computation of homology groups can be reduced to a process of labelling black and white connected components. The different black connected components are the generators of the 0-dimensional homology group of the black part of the image, whereas the closed black curves surrounding the different white connected components of the image are the generators of its 1-dimensional homology groups. The HGB2I problem can be written as follows: Given a binary 2D digital image, calculate the number of black connected components and the representative curves of the holes of these components. In this paper, the extended version of this problem is considered, where the representative geometrical objects of the homology groups of a binary 2D image are obtained. This problem is known as the extended-HGB2I problem. We consider a set of pixels P={(i, j):1≤i, j ≤ n}and a set of colors C={w, b}, where bstands for black and wstands for white. As usual, an image of size n2is a mapping I:P→ C, which can be denoted as the set of colored pixels I={cij |1≤i, j ≤n}, where c∈ {w, b}, i.e., cij stands for the color cin the pixel (i, j). We also consider the lexicographic order on the set of pixels P={(i, j):1≤i, j ≤n}. In the solution described below, we also use a more complex object, called pixel-flag, where a flag is a pair (k, l)with 1≤k, l ≤n associated to the colored pixel aij. The pair pixel-flag is written as (aij,(k, l)). Finally, let us remark that the presented solution can handle with 4-adjacency and 8-adjacency. There are only some technical details between both designs (more rules are needed in the first case). In this paper, we have considered 4-adjacency for black pixels and 8-adjacency for white pixels but other choices are possible (see, e.g., Khalimsky et al., 1990; Šlapal, 2003; Kovalevsky, 2004, 2008; Nagy, 2012). The reason for this choice has been to avoid the situation where one white connected component, which is not 4-adjacent to another component, is considered as a hole. 6D. Díaz-Pernil et al. 3.1 A membrane solution of the extended-HGB2I problem In order to provide a solution to our problem, we design a family of tissue-like P systems with promoters and priorities, Π={Π(n)}n∈N, i.e., for each n∈Nwe design a tissue-like P system with promoters and priorities Π(n). Such a P system Π(n)receives an image of size n2 (encoded as an appropriate multiset) as input and the multiset of objects placed in the output cell of the P system in the halting configuration is interpreted as the solution of the HGB2Iproblem for the image provided as input. As shown above, the input image can be seen as a set of objects aij where a∈ {b, w}and 1≤i, j ≤n. By using this notation, we define a P system where the input alphabet is the set of objects Aij with A∈ {B, W }and 1≤i, j ≤n. Table 1 A scheme of the computation of a tissue-like P system of our family Input stage (a) H0process (b) H1process (a.1) Label allocation stage (b.1) Label allocation stage (a.2) Label conversion stage (b.2) Label conversion stage (a.3) Answer Stage (b.3) Deleting stage (b.4) Segmenting stage (b.5) Answer stage Next, we provide a formal definition of the family of P systems. The symbols <and ≤will be used for the lexicographical order among indexes or pair of indexes with the natural meaning. For the sake of simplicity, the subscripts are omitted in Γn,Σn...if there is no confusion. A scheme of the computation steps followed by all systems of the previously defined family appears in Table 1: Π(n) = (Γ,Σ,E, ω1, ω2, ω3, ω4,R,P, iin, iout), where 1Γ = {zi: 1 ≤i≤n+ 8} ∪ {Bij, bij, b′ ij,¯ bij, Wij, wij, w′ ij,(bij,(k, l)),(wij ,(k, l)) : 1 ≤i, j, k, l ≤ n} ∪ {(pij,(0,0)),(pji,(0,0)) : i∈ {0, n + 1},0≤ j≤n+ 1}∪{Aijkl, Zijkl : (1,1) ≤(i, j)<(k, l)≤ (n, n)}. It is the alphabet of objects for encoding the information. 2Σ = {Aij :A=B∨W, 1≤i, j ≤n}. This is the input alphabet. The image used as input will be encoded with these symbols. 3E= Γ −Σ. It represents the alphabet of symbols placed in the environment. 4ω1=ω4=∅, ω2={z1}, ω3={z1,(pij,(0,0)),(pji,(0,0)) : i= 0 ∨i= n+ 1,0≤j≤n+ 1}. These are the multiset of objects placed in the corresponding cells in the initial configuration. 5 The set of rules Ris described below. 6P={R9> R4} ∪ {R6,i1j1,kl,k′l′> R6,i2j2,kl,k′l′: (i1, j1)<(i2, j2)} ∪ {R7,i1j1,kl,k′l′> R7,i2j2,kl,k′l′: (i1, j1)<(i2, j2)} ∪ {R6> R7, R8> R6, R8> R7} ∪ {R12,i1j1,kl,k′l′> R12,i2j2,kl,k′l′: (i1, j1)<(i2, j2)} ∪{R13,i1j1,kl,k′l′> R13,i2j2,kl,k′l′: (i1, j1)<(i2, j2)} ∪ {R12 > R13, R14 > R12, R14 > R13, R15 > R10, R17 > R10}. This set determines the priority relations among rules. 7iin = 1 is the input cell. 8iout = 4 is the output cell. Next, the set of rules R=R1∪ · · · ∪ R19 is provided together with a short description: 3.1.1 Input stage There are three schemes of rules associated to the input: •R1≡(1, Aij/aija′ ij,0) for 1≤i, j ≤n, A∈ {B, W }. Each object Aij coding a pixel of the image is changed by two new objects aij and a′ ij. •R2≡(1, aij/λ, 2) for 1≤i, j ≤n. The objects aij are sent to cell 2. •R3≡(1, a′ ij/λ, 3) for 1≤i, j ≤n. The objects a′ ij are sent to cell 3. 3.1.2 H0process The rules associated to the process to obtain the representative objects of all black connected components are: •R4≡(2, zi/zi+1,0) for 1≤i≤n+ 4. These rules generate in the computation step n+ 1 an object zn+2 that will be used by the system for the output. These objects (as zi) are called counters. Label allocation stage. •R5≡(2, bij/(bij,(i, j)),0) for 1≤i, j ≤n. These rules add labels to black pixels. Initially, these labels are given by the position of the pixel in the image, but later these labels will be changed. Label conversion stage. •R6≡Rij,kl,k′l′≡(2,(bij ,(k, l))(bij+1,(k′, l′))/ (bij,(k, l))(bij+1,(k, l))Aklk′l′,0) for (1,1) ≤(k, l)<(k′, l′)≤(n, n),1≤i≤nand 1≤j≤n−1. Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images 7 Figure 1 A simple example of a 3×3black image (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) C1: New promoters A1121, A1222, A1323 (1,1) (1,2) (1,3) (1,1) (1,2) (1,3) (3,1) (3,2) (3,3) C2: New promoters A1131, A1232, A1333, A1112 (1,1) (1,1) (1,3) (1,1) (1,2) (1,3) (1,1) (1,2) (1,3) C3: Used promoters A1112 (1,1) (1,1) (1,3) (1,1) (1,1) (1,3) (1,1) (1,1) (1,3) C4: New promoters A1113 (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) Notes: For the sake of simplicity, only the flags are represented. In the initial configuration, the flag is the same as the location of the pixel. By application of three rules from R7, the flags in (2,1),(2,2) and (2,3) have been changed and the promoters A1121,A1222,A1323 are considered. Such promoters are considered in the next step, by application of rules from R8in order to change the flags from the pixels at (3,1),(3,2) and (3,3). The process goes on and in the last configuration all the pixels have the same flag (1,1). •R7≡Rij,kl,k′l′≡(2,(bij ,(k, l))(bi+1j,(k′, l′))/ (bij,(k, l))(bi+1j,(k, l))Aklk′l′,0) for (1,1) ≤(k′, l′)<(k, l)≤(n, n),1≤i≤n−1 and 1≤j≤n. This kind of rules does an equivalent work by changing the labels of black adjacent pixels. All the pixels are ordered by lexicographic order and the labels of two adjacent pixels are compared. Then, the higher label is changed by the lower one. Firstly, each pixel is compared with its bottom neighbour (rule R6); after that, it is compared with the right neighbour (rule R7). This order is controlled by priority on the rules. •R8≡(Ak1l1k2l2|2,(bi′j′,(k2, l2))/(bi′j′,(k1, l1)),0) for 1≤i, j, i′, j′, k1, l1, k2, l2≤n. In these rules, promoters are used. The aim of these promoters is to accelerate the process. The promoter indicates that the pixels with label (k2, l2)are connected with the pixels with label (k1, l1). So, the label (k2, l2)can be changed by (k1, l1). In this way, pixels with connected labels are considered, instead of considering adjacent pixels. At the end, all the pixels in the same black connected component have the same label. This set of rules has priority with respect to the rules R6and R7. Let us remark that rules from R6and R7are quite different from rules in R8. Rules from R6and R7are applied only for adjacent pixels and they do not use promoters. Their target is twofold. On the one hand, they change the flag of one of the pixels. On the other hand, a new promoter is brought from the environment into the cell 2. Rules from the set R8 need the promoter to be applied. They also change the flag of a pixel, but they do not bring new promoters from the environment. Example 1: Figure 1 shows an example of how the promoters joined with priority between rules work. In Figures 2 and 3 a new example is shown, where the three rules work together. It can be easily checked how the labels B22 are growing at great speed. •R9≡(zn+5|2,(bij ,(i, j))/λ, 4). An element representing each connected component must be chosen. With these rules, the unique pixel in each connected component conserving its original label is chosen. These objects are sent to the output cell in the computation step n+ 3, using the object zn+2 as a promoter of the rule. These rules have priority with respect to the rules R4. In another way, the computation step number n+ 6 is reached and these rules cannot be applied. Figure 2 Configurations 5 and 6 of an example to see at the same time how the label conversion stage works Note: Configurations 7 and 8 are shown in Figure 3. 8D. Díaz-Pernil et al. Figure 3 Configurations 7 and 8 of an example to see at the same time how the label conversion stage works 3.1.3 H1process The process is quite similar to the computation of H0. In this case we look for white connected components instead of black ones. The surrounding white region has label (0,0) and it is not counted as a hole. At the end, the different labels encode the found connected components. The process can be split into two big parts. The first one consists of two stages (similar to the H0process). The second one consists of three stages including the output. •R10 ≡(3, zi/zi+1,0) for 1≤i≤n+ 7. Counters are considered again. An object zn+6 appears in cell 3 in the computation step n+ 7. Let us remark that this object could appear in the n+ 5-th computation step, but because of the action of rules R15 and R17 (by the priority), where zn+3 and zn+5 work as promoters, it is delayed two steps. Label allocation stage. •R11 ≡(3, wij/(wij,(i, j)),0) for 1≤i, j ≤n. These rules add labels to white pixels for dealing with them. Initially, these labels are given by the position of the pixel in the image. Label conversion stage. •R12 ≡(3,(wij,(k, l))(wij+1,(k′, l′))/ (wij,(k, l))(wij+1,(k, l))Zklk′l′,0) for (1,1) ≤(k, l)<(k′, l′)≤(n, n),1≤i≤nand 1≤j≤n−1. •R13 ≡(3,(wij,(k, l))(wi+1j,(k′, l′))/ (wij,(k′, l′))(wi+1j,(k′, l′))Zk′l′kl,0) for (1,1) ≤(k′, l′)<(k, l)≤(n, n),1≤i≤n−1 and 1≤j≤n. This kind of rules changes the labels of white adjacent pixels. The pixels are considered in lexicographic order. The labels of two adjacent pixels are compared and the higher of them is changed by the other one. As in rules R6and R7, firstly each pixel is compared with its bottom neighbour (rule R12); after that, it is compared with the right neighbour (rule R13). This order is also controlled by priority on the rules. Moreover, there is also priority between two rules from R12. The rule with lower priority is firstly applied and, analogously, for the set of rules R13. •R14 ≡(Zijkl|3,(wi′j′,(k2, l2))/(wi′j′,(k1, l1)),0) for 1≤i, j, i′, j′, k1, l1, k2, l2≤n. In these rules, promoters are used again. The promoter indicates that the pixels with label (k2, l2) are connected with the pixels with label (k1, l1). So, the label (k2, l2)is changed by (k1, l1). As described above, In this way, only pixels with connected labels are considered. At the end, all the pixels in the same black connected component have the same label. These rules have priority with respect to the rules R12 and R13. Deleting stage. •R15 ≡(zn+5|3,(pij ,(0,0))(wkl,(k′, l′))/ (pij,(0,0))(pkl,(0,0))Z00kl,0) for (i, j),(k, l)8-adjacent pixels, 0≤i, j ≤n+ 1, 1≤k, l, k′, l′≤n. When the object zn+5 appears in cell 3, white pixels adjacent to pink pixels change their label with the pink pixels (we will refer to the objects pij as pink pixels). Moreover, an object Z00kl is created for each white pixel changing its label. They will be used as promoters in the next scheme of rules. By using 8-adjacency, outer white pixels are transformed into pink pixels, in order to differentiate them from the interior white pixels (belonging to holes). This kind of rules has priority with respect to the rules from R10. •R16 ≡(Z00ij|3,(wi′j′,(i, j))/(pi′j′,(0,0)),0) for 1≤i, j, i′, j′≤n. When the promoters of the type Z00ij appear in the cell 3, these rules can be applied. They ensure the exchange of exterior white pixels by pink pixels. In this way, all the exterior white pixels are deleted in two steps. Let us remark that the border of the image is marked with pink pixels from the beginning of the computation. The use of promoters keeps these pixels inactive waiting for the object zn+5. When this object appears, rules from R15 are applied. Their target is twofold. On the one hand, white pixels adjacent to pink ones are turned into pink. In this way, white pixels that do not belong to a hole, are marked as pink. On the other hand, rules from R15 bring the Bio-inspired parallel computing of representative geometrical objects of holes of binary 2D-images 9 promoters Z00kl that activate rules from R16 and accelerate the process. Segmenting stage. •R17 ≡(zn+6|3,(wij ,(i′, j′))bkl/(wij,(i′, j′))¯ bkl,0) for 1≤i′, j′, i, j, k, l ≤nand (i, j),(k, l)8-adjacent pixels. When an object zn+5 appears in cell 3, the black pixels adjacent to white pixels (wij,(i′, j′)) are traded, with the environment, by black marked pixels ¯ bkl. This kind of rules has priority with respect to the rules from R10. Answer stage. •R18 ≡(3,¯ bij/λ, 4) for 1≤i, j ≤n. Black marked pixels are sent to the output cell, so we obtain which black pixels are in the boundary of some hole. •R19 ≡(zn+7|3,(wij ,(i, j))/λ, 4) for 1≤i, j ≤n. In order to obtain the number of holes, these rules send one white pixel for each hole to cell 4 in n+ 8-th computation step. The answer is provided in cell 4 with objects ¯ bij and wij. Theorem 2: The family of tissue-like P systems presented above solves the extended-HGB2I problem in O(m)with respect to the input (image) size m∼n2. The proof of this Theorem is provided in the Appendix. Table 2 Neccesary resources HGB2I problem Image size n2 Complexity Number of steps of a computation n+ 15 Necessary resources Size of the alphabet O(n4) Initial number of cells 4 Initial number of objects O(n) Number of rules O(n6) Upper bound for the length of rules of the P systems 5 Bearing in mind that the size of the input data is O(n2), the amount of necessary resources for defining the systems of our two families and the complexity of our problem can be observed in Table 2. It is worth mentioning that the design of the P systems family presented in this paper represents an improvement with respect to the design presented in Díaz-Pernil et al. (2010b). In such a paper, two different P systems were necessary to compute the Betti numbers related with H0and H1. In this paper, both numbers are computed with a unique P system. This improvement is also related with the number of computational steps. This new system only needs n+ 9 computational steps, instead of the 2n+ 9 steps needed in the system from Díaz-Pernil et al. (2010b). A second improvement is related to the curves representing the holes in the black components. In this new design, in order to obtain more information, the number of steps decreases significantly. Figure 4 Workflow of the implementation 4 Simulation with CUDA of our algorithm We present a simulation of our algorithm using CUDA. Let us remark that the implemented algorithm is not an emulation of the Membrane Computing algorithm since the language programming allows shortcuts for improving the efficiency. In this way, there is no an exact correspondence with the theoretical model. On one hand, thanks to multi-reading, auxiliary rules (for example, R1, R2, R3, R4, R9, R10, R18 and R19) are not needed. On the other hand, thanks to multi-writing, two rules using the same object can be applied (for example, in rules R6, R7, R8and R12, R13, R14, but not only them). So, the improvement from a computational point of view is clear with respect to the theoretical model, indeed. Bearing in mind these improvements, the workflow of the algorithm is shown in Figure 4 and the pseudocode is shown in Algorithm 1. We would like to mention that in Alnuweiri and Prasanna (1992), a parallel algorithm for image component labelling without practical results to compare; in Yang et al. (2005), a parallel label assignment algorithm working in linear time in the input data is presented, but no experimental results on a database are shown; finally, Johnston and Bailey (2008) present a FPGA algorithm without experimental results. 16 D. Díaz-Pernil et al. Lemma 9: At the end of the n+ 6-th computation step, the label (0,0) is added to the white pixels out of the holes in the input image. Proof: Initially, in cell 3, the system keeps a set of objects coding the frame of the input image (p0i, pn+1i, pi0, pin+1 for i= 0, . . . , n + 1) with the label (0,0) associated. When the object zn+5 in step n+ 4 appears in cell 3, the deleting stage starts. Rules from R15 are applied, because of priority with respect to the rules from R10. One step after, the rules from R16 are applied. So, in this point, all the white pixels out of the holes have the same label. So, promoters are created in a step with rules R15 and the promotion with rules from R16 is performed. Only two computation steps are needed.  Lemma 10: A segmentation of the holes is performed and the boundary pixels (coding by the objects bij) are sent to the output cell in the step n+ 13. Proof: At the same time that rules from R16 are applied, a rule from R10 changes zn+5 by zn+6 with the environment. So, the segmenting stage starts. If there are white pixels in cell 3 in this step, they are holes. By action of rules from R17, the system takes pairs of adjacent pixels, one black and the other white, adding a mark to the black pixels of these pairs. Then, the black pixels adjacent to a hole are marked. We need at most 8 steps to segment an image with P systems (see Christinal et al., 2009a).  Lemma 11: The representative objects of the holes, (wij,(i, j)), are sent to the output cell in the step n+ 14. Proof: When the rules from R17 are applied in the step n+ 12, the object zn+6 is traded in cell 3 by the object zn+7 using a rule from R10. In the next step, the objects (wij,(i, j)) are sent to the output cell by using rules from R19. Then, the computation halts.  Next, a short study of the time complexity study is provided. Lemma 12: The number of computation steps to solve the extended-HGB2I problem is O(m)with respect to the input (image) size m∼n2. Proof (outline): To calculate the number of steps of a computation, the objects zimust be considered. Two objects z1are taken initially. One in cell 2 and the other one in cell 3. On one hand, in the first cell, zn+5 appears after n+ 4 steps, and the computation in this cell finishes in the next step with the rules from R9. On the other hand, in cell 3, the system needs to give n+ 4 steps before the object zn+5 appears. After that, one more step is given to apply the rules from R15. In the following step, rules from R16 and rules from R10 are applied in parallel, changing the object zn+5 by the object zn+6. In the step n+ 6, rules from R17 are applied at most during 8 steps. Then, the application of this set of rules finishes in the step n+ 13. The rules from R18 and R10 are applied in the next step. Finally, in the step of computation n+ 15, the last set of rules is applied and the computation halts. 