Image Segmentation using Tissue-like P Systems with Multiple Auxiliary Cells

Image Segmentation using Tissue-like P Systems with Multiple Auxiliary Cells Ra´ul Reina-Molina, Javier Carnero, Daniel D´ıaz-Pernil 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics I University of Seville [email protected], [email protected], [email protected] Abstract. We present a solution of the segmentation problem using a distributed, non deterministic and parallel computational model known as tissue-like P systems. We present a new technique to segment images with respect to the algorithm appeared in [1], where we use multiple auxiliary cells and not only one. 1 Introduction Membrane systems are distributed and parallel computing devices processing multisets of objects in compartments delimited by membranes. Computation is carried out by applying given rules to every membrane content, usually in a maximal non-deterministic way, although other semantics are being explored. In our work, we present a family of tissue-like P systems (tlP systems) which solves the Segmentation Problem in Digital Imagery using multiple cells. Segmentation in computer vision (see [4]) refers to the process of partitioning a digital image into multiple segments (sets of pixels). Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.). 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, one can find several attempts for bridging problems from Digital Imagery with Membrane Computing. We can cite the works by K.G. Subramanian et al. [?] or recently some problems from Digital Imagery have been solved in the framework of Membrane Computing (see [3]). 2 Image Processing: Segmentation Problem The m-D Segmentation Problem with k auxiliary cells (mDSP-kC) can be settled as follows: given an m-D digital image, Iof size nm, to determine the edge pixels of this image using kauxiliary cells. The usual definition of edge pixel presents problems from a practical point of view with the noise and the degradation of colours, because we take as border points a lot of pixels that are not edge pixels from a practical point of view. 25 (a) Initial content (b) Content of second cell (c) Content of second cell after cleaning stage (d) Content of second cell before edge detection stage (e) Content of second cell after edge detection (f) Content of first cell once halting condition is reached Fig. 1: Full segmentation process zoomed. Next, we will show that 2DSP-kC can be solved in linear time (in the number of pixels of the image) by a family of tlP systems (see Fig.1). To this aim, let us construct a family Π={Π(n, k):n, k ∈N}where each system of the family will process every instance uof the problem (a 2D image Iwith n2pixels) and using kauxiliary cells. More formally, we define the size of the instance as s(u)="n, k#, where "x, y#=(x+y)(x+y+ 1)/2+xis the G¨odel mapping. In order to provide a suitable encoding of this instances into the systems, we will use the objects I(ij)ij , with 1 ≤i, j ≤n, to represent the pixels of the graph, and we will provide cod(u) as the initial multiset for the system, where cod(u) is the multiset of objects I(ij)! ij for 1 ≤i, j ≤n. Then, given an instance uof the 2DSP-kC problem, the system Π(s(u)) with input cod(u) give a solution to this problem, implemented in the following stages: –Cleaning noise. –Homogenize colours using a general thresholding in colour space. –Segmenting image process. The family Π={Π(n, k):n, k ∈N}of tlP systems of degree k+1 is defined as follows: for each n, k ∈N, Π(n, k) = (Γ,Σ,E,w 1, . . . , wk+1,R,i Π,o Π), defined as follows: –Γ=Σ∪{aija!! ij,¯aij,A ij,A ! ij,A !! ij,¯ Aij :1≤i, j ≤n, a ∈C} ∪{∗ij,∗ji :i= 0,n+1,0≤j≤n+1},Σ={a! ij :1≤i, j ≤n, a ∈C},E=Γ−Σ, 26 –w1=∗ij,∗ji with i=0,n+1,0≤j≤n+ 1, w2=· · · =wk+2 =T!n2/k", –Ris the following set of communication rules: •(1,a # ij/a8 ijAij,0) for 0 ≤i, j ≤n+ 1 and a∈C∪{∗} • 1, ci−1j−1di−1jei−1j+1 bij−1Aij fij+1 oi+1j−1hi+1jgi+1j+1 / T, t  for 1 ≤i, j ≤n,a, b, c, d, e, f, g, h, o ∈C∪{∗}and 2 ≤t≤k+1 indicating an auxiliary working cell. These rules are used to generate new elements. The P system uses these elements to work with the noise of our image. • t, ci−1j−1di−1jei−1j+1 bij−1Aij fij+1 oi+1j−1hi+1jgi+1j+1 /z " ij ,0 , t, ci−1j−1di−1jei−1j+1 bij−1Aij fij+1 oi+1j−1hi+1jgi+1j+1 /a " ij ,0  for 1 ≤i, j ≤n,a, b, c, d, e, f, g, h, o ∈C∪{∗}. We take µas the number of pixels adyacents to the ij possition with colours in Cand ∗= 0. Then, av =(b+c+d+e+f+g+h+o)/µ and z= max{s∈C:s≤av}and |a−av|≤ρ1, where ρ1∈(0,+∞). This set of rules is used to detect the noise and correct it with the average of colours of its adjacent pixels. We find here a local thresholding (with respect to the colours) with predefined threshold ρ1. The use of ∗grants a simple working for pixels in the border of I. •(t, b# ij/A# ij,0) for 1 ≤i, j ≤n,ν=(|C|/ρ2), l=0,1,2,...,ρ2. If b∈C then a∈C(a<b≤a+(ν−1) and a=ν·l) or (b=a=ν·l) and, if b=∗then A=∗. These rules are used to discretize the colours dividing the set of colours in ρ2subsets of length ν. We find here a general thresholding (with respect to the colours) with predefined threshold ν. •(t, A# ij/T, 1) for a∈C,0≤i, j ≤n+ 1 and 2 ≤t≤k+ 1. This set of rules are used to send our transformed image to the cell 1. Now, the objects A# ij codify the pixels of our image. •(1,A # ij/A## ija8 ij,0) for a∈C∪{∗}and 0 ≤i, j ≤n+ 1. The P system uses these rules to generate an number of copies of our image to do the segmentation process in the cells 2, . . . , k and k+ 1. • 0, ci−1j−1di−1jei−1j+1 bij−1A## ij fij+1 ii+1j−1hi+1jgi+1j+1 / T, t  for 1 ≤i, j ≤nand a, b, c, d, e, f, g, h, i ∈C∪{∗}. These rules are defined to send to the remainder of cells the new objects. •(t, A## ijbkl/Aij,0), for 1 ≤i, j, k, l ≤n,(i, j),(k, l) adjacent pixels, a, b ∈C and a<b. These rules are used to mark edge pixels. When we have two adjacent pixels with different colour, we take as edge pixel the pixel with less associated colour. In fact, the P system brings from the environment an object Aij (in this case). •(t, Aij/T, 1) for a∈Cand 1 ≤i, j ≤n. These rules send to the cell 1 the output objects. 27 –iΠ=oΠ= 1. A little study of the complexity aspects of this solution is given by the Fig.2 showing this is an efficient algorithm from a theoretical point of view. mDSP-kC Problem Complexity Number of steps of computation 9 Resources needed Size of the alphabet 8n2+4n+5 Initial number of cells k+1 Initial number of objects (n+ 2)2 Number of rules O(n2 ·h9 ·k) Upper bound for the length of the rules 10 Fig. 2: Complexity aspects, where the size of the input data is O(n2), |C| =his the number of colours of the image and kis the number of working cells. 3 Final Remarks We have designed a family of tissue-like P systems to do a segmentation of a digital image. With this algorithm we work with multiple cells, so we can obtain a bigger parallelization with respect to the design presented in [1]. Acknowledgement DDP acknowledges the support of the projects TIN2008-04487-E and TIN-200913192 of the Ministerio de Ciencia e Innovaci´on of Spain and the support of the Project of Excellence of the Junta de Andaluc´ıa, grant P08-TIC-04200. References 1. Carnero, J., D´ıaz-Pernil, D., Molina-Abril, H., Real, P.: Image segmentation inspired by cellular models using hardware programming. Image-A 1(3), 143–150 (2010) 2. 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) 3. 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, pages 1–6, 2011. 4. Shapiro, L.G., Stockman, G.C.: Computer Vision. Prentice Hall PTR, Upper Saddle River, NJ, USA (2001) 28