Bioinspired parallel 2D or 3D skeletonization

Bioinspired parallel 2D or 3D skeletonization Ra´ul Reina-Molina, Daniel D´ıaz-Pernil 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics University of Sevilla [email protected], [email protected] Abstract Algebraic Topology have been proved to be an useful tool to be used in image processing. In this case we will borrow some elements from Algebraic Topology in order to show a parallel algorithm for thinning a binary 3D image respecting its shape information. The parallelization of the thinning algorithm is based on Membrane Computing. This research area has already been proved to be useful in the development of parallel image processing algorithms. We present here the main guidelines of the algorithms along with a slight introduction about some basic required knowledge about Algebraic Topology and Membrane Computing. 1 Introduction Computer vision is one of the challenges for Computer Science in the next years. It counts with a big amount of current applications in computer vision as biometrics, surveillance or medical imaging. Many problems in the processing of 2D or 3D digital images have features which make it suitable for techniques inspired by nature. Some of them are the discreteness of the support of the image and the set of possible features associated to each point and hence. Other of such features is that the treatment of the image can be parallelized and locally modified. Regardless how large is the picture, the process can be performed in parallel in different local areas of it. Another interesting feature is that the information of the image can also be easily encoded in the data structures used in Natural Computing. Recently, a new research line has been open by applying well-known membrane computing techniques for solving problems from digital imagery. For example, the segmentation problem, [2, 4, 5, 6], thresholding [1] or smoothing [10]. In this demo, we focus on the problem of skeletonizing a 2D or 3D image. Skeletonization is one of the approaches for representing a shape with a small amount of information by converting the initial image into a more compact representation and keeping the meaning features. The conversion should remove redundant information, but it should also keep the basic structure. There are many different definitions of the skeleton of a black and white image and many skeletonizing algorithms , but in general, the image Bis a skeleton of the image A, if it has fewer black pixels than A, preserves its topological properties and, in some sense, keeps its meaning. The most important features concerning a shape are its topology (represented by connected components, holes, etc.) and its geometry (elongated parts, ramifications, etc.), thus these terms have to be preserved. When the skeletonizing process is made by the iterative removal of non-significant elements of the image, the process is known as thinning. We present here an implementation of the thinning algorithm in [8], based on Membrane Computing techniques. The fundamental idea of this algorithm is the use of cell complex to represent a binary image. A cell can be seen as a mathematical abstraction of a space unit. This space unit is built in some ndimensional space and embedded in a space of higher dimension, as a 2-dimensional square can be embedded in a 3D space. For a further reading, see [7], for example. 41 For implementing these ideas in the Membrane Computing framework, we present a family of tissue-like P systems endowed with priorities among rules, promoters and inhibitors. This paper follows the research line open with [3]. As pointed above, cell complexes1are mathematical abstractions to handle structured portions of a ndimensional space. On such abstractions, we can define several operators as the border one, which associates, for example, a 3D cell (cube) with six 2D cells (squares), or properties to define free cells or isolated cells. We follow T. Kaczy´nski, K. Mischaikow and M. Mrozek [7] in the description of a kind of combinatorial structure on a topological space, and we refer to it for further reading. When a cell is not a proper face of any cell in a given cell complex, it will be called isolated cell. A cell that is a proper face of exactly one cell in the complex is called free face. As we are interested in obtaining a simpler representation for a cell complex whilst the topology is preserved, we will use the concept of elementary collapse inherited from simplicial homology. Let Kbe a cubical complex and δa free cell in K. Let σbe the only cell in Ksuch that δis a proper face of σ. Let K�=K\{δ,σ}.K�is obtained from Kvia a process called elementary collapse of σby δ. One of the principal element in the segmentation algorithm is the simple pair. Let Kbe a cubical complex. A pair of cells �δ,σ�is said to be a simple pair if following conditions hold: •δis a free cell in K. •σis the only cell such that δ∈∂σ. The cell σis called the facet of the simple pair. As shown in related literature [7, 11], simple pairs removal does not change the topology of the given cell complex. 2 Description of the algorithm Let Kbe a cubical cell complex and let ∂be its border operator. As seen in the previous section, if only simple pairs of cells are removed, the topology is kept. For geometry preservation it is necessary to require some additional properties to those cells to be removed. The basic idea of the algorithm is to define an iterative process where some outer cells are removed. Here, the idea of outer cells makes reference to simple pairs, since in a simple pair �δ,σ� the cell δis a “terminal” cell as it does not lie in the border of any other one rather than σ. In the process of iterative thinning, given a cell σ, we will denote the later iteration when σis the facet of a simple pair by R(σ). The earlier iteration when σbecomes isolated will be denoted by I(σ). Liu et al. describe in [9] the relation between I(σ) and R(σ), and the maximum isotropic elongation in p+ 1 and pdirections, respectively, since dim σ=p.Thus,ifσis a p-cell in a cell complex, I(σ) measures the shortest discrete distance from σto the object boundary. This gives an idea of the size of the maximum disk centered at σand inscribed in the object. On the other hand, R(σ) measures the longest distance from σto the object boundary going along the skeleton (p−1)-cells. From the observation of the behaviour of previous measures, Liu defined two difference measures. The absolute one, R(σ)−I(σ), is called absolute medial persistence and is denoted by MPabs. On the other hand, relative medial persistence is defined as 1 −I(σ) R(σ)and denoted by MPrel. Both of them measure the duration in which a cell remains isolated during thinning process. The underlying idea to the presented algorithm is parallel removal of those simple pairs which are not sigficative enough, in the sense of having both significativity measures less than given thresholds. 1In this work we restrict the cell complexes to be cubical. 42 Figure 1: Flowchart of the skeletonization process. 3 Implementation We use here a variant of tissue-like P systems where the application of the rules are regulated by promoters and inhibitors. These catalizers have a clear biological inspiration. The rule is applied if the reactants are present, but it is also necessary the presence of all the promoters and none of the inhibitors in the corresponding cell. The promoters are not consumed nor produced by the application of the rule, but if they are not in the cell, the rule cannot be applied. In one step, each reactant in a membrane can only be used for one rule, but if several rules need the presence of the same promoter, then the presence of one unique copy of the promoter suffices for the application of the rules. In the general case, if there are several possibilities, the rule is non-deterministically chosen, but sometimes we will consider a priority relation between rules, so we need the concept of priority in our P systems. The parallel skeletonization algorithm behaviour is shown in figure 1, where the main stages can be seen: •Initialization: Initially isolated cells are marked. •Simple pair detection: Cells making a simple pair are marked. •Marking of simple pairs no significative enough: Those simple pairs which are no significative enough are marked to be removed. •Deletion of no significative enough simple pairs: Those simple pairs with low significativity are removed. •Marking of new isolated cells: New isolated cells are marked. Recall that every stage is run in parallel over all the cells. 43 Figure 2: Example of application. Left, cell scructure for initial image. Right, skeletonized image. References [1] Christinal, H.A., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J.: Thresholding of 2D images with cell-like P systems. Romanian Journal of Information Science and Technology 13(2), 131–140 (2010) [2] Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Segmentation in 2D and 3D image using tissue-like P system. In: Bayro-Corrochano, E., Eklundh, J.O. (eds.) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. Lecture Notes in Computer Science, vol. 5856, pp. 169–176. Springer (2009) [3] Christinal, H.A., D´ıaz-Pernil, D., Real, P.: P systems and computational algebraic topology. Mathematical and Computer Modelling 52(11-12), 1982–1996 (2010) [4] Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Region-based segmentation of 2D and 3D images with tissue-like P systems. Pattern Recognition Letters 32(16), 2206 – 2212 (2011) [5] D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Molina-Abril, H., Real, P.: A bio-inspired software for segmenting digital images. In: Nagar, A.K., Thamburaj, R., Li, K., Tang, Z., Li, R. (eds.) Proceedings of the 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications BIC-TA. vol. 2, pp. 1377 – 1381. IEEE Computer Society, Beijing, China (2010) [6] D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Molina-Abril, H., Real, P.: Designing a new software tool for digital imagery based on P systems. Natural Computing pp. 1–6 (2011) [7] Kaczy´nski, T., Mischaikow, K., Mrozek, M.: Computational homology. Applied mathematical sciences, Springer (2004) [8] Liu, L.: 3D thinning on cell complexes for computing curve and surface skeletons. Washington University (2009) [9] Liu, L., Chambers, E.W., Letscher, D., Ju, T.: A simple and robust thinning algorithm on cell complexes. Computer Graphics Forum 29(7), 2253–2260 (2010) [10] Pe˜na-Cantillana, F., D´ıaz-Pernil, D., Christinal, H.A., Guti´errez-Naranjo, M.A.: Implementation on CUDA of the smoothing problem with tissue-like P systems. International Journal of Natural Computing Research 2(3), 25–34 (2011) [11] Zhou, Q.Y., Ju, T., Hu, S.M.: Topology repair of solid models using skeletons. IEEE Transactions on Visualization and Computer Graphics 13(4), 675–685 (2007) 44