Membrane parallelism for discrete Morse theory applied to digital images. (English) Zbl 1331.68258
Summary: In this paper, we propose a bio-inspired membrane computational framework for constructing discrete Morse complexes for binary digital images. Our approach is based on the discrete Morse theory and we work with cubical complexes. As example, a parallel algorithm for computing homology groups of binary 3D digital images is designed.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 55U05 | Abstract complexes in algebraic topology |
| 57Q10 | Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc. |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68U10 | Computing methodologies for image processing |
References:
| [1] | Bauer, U., Lange, C., Wardetzky, M.: Optimal topological simplification of discrete functions on surfaces. Discrete Comput. Geom. 47(2), 347-377 (2012) · Zbl 1243.57017 · doi:10.1007/s00454-011-9350-z |
| [2] | Berciano, A., Molina-Abril, H., Real, P.: Searching high order invariants in computer imagery. Appl. Algebra Eng. Commun. Comput. 23(1-2), 17-28 (2012) · Zbl 1247.68305 · doi:10.1007/s00200-012-0169-5 |
| [3] | Carnero, J., Díaz-Pernil, D., Gutiérrez-Naranjo, M.A.: Designing tissue-like P systems for image segmentation on parallel architectures. In: del Amor, M.A.M., Păun, Gh., de Mendoza, I.P.H., Romero-Campero, F.J., Cabrera, L.V. (eds.) Ninth Brainstorming Week on Membrane Computing, pp. 43-62. Fénix Editora, Sevilla, Spain (2011) |
| [4] | 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 (2009) · Zbl 1207.68137 |
| [5] | Christinal, H.A., Díaz-Pernil, D., Real, P.: Region-based segmentation of 2D and 3D images with tissue-like P systems. Pattern Recogn. Lett. 32(16), 2206-2212 (2011) · Zbl 1368.93242 · doi:10.1016/j.patrec.2011.05.004 |
| [6] | Christinal, H.A., Díaz-Pernil, D., Real, P.: P systems and computational algebraic topology. Math. Comput. Model. 52(11-12), 1982-1996 (2010) · Zbl 1207.68137 · doi:10.1016/j.mcm.2010.06.001 |
| [7] | Cazals, F., Chazal, F., Lewiner, T.: In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 351-360. ACM (2003) · Zbl 1377.92029 |
| [8] | Díaz-Pernil, D., Christinal, H.A., Gutiérrez-Naranjo, M.A., Real, P.: Using membrane computing for effective homology. Appl. Algebra Eng. Commun. Comput. 23(5-6), 233-249 (2012) · Zbl 1253.68331 · doi:10.1007/s00200-012-0176-6 |
| [9] | Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Molina-Abril, H., Real, P.: Designing a new software tool for digital imagery based on P systems. Nat. Comput. 11(3), 381-386 (2012) · Zbl 1251.68266 · doi:10.1007/s11047-011-9287-4 |
| [10] | Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Núñez, A.: A linear-time tissue P system based solution for the 3-coloring problem. Electr. Notes Theor. Comput. Sci. 171(2), 81-93 (2007) · Zbl 1277.68073 · doi:10.1016/j.entcs.2007.05.009 |
| [11] | Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Núñez, A.: Solving subset sum in linear time by using tissue P systems with cell division. In: Mira, J., Álvarez, J.R. (eds.) IWINAC (1). Lecture Notes in Computer Science, vol. 4527, pp. 170-179 (2007) · Zbl 1137.68384 |
| [12] | Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Real, P., Sánchez-Canales, V.: Computing homology groups in binary 2D imagery by tissue-like P systems. Roman. J. Inf. Sci. Technol. 13(2), 141-152 (2010) |
| [13] | Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90-145 (1998) · Zbl 0896.57023 · doi:10.1006/aima.1997.1650 |
| [14] | Gunther, D., Reininghaus, J., Hotz, I., Wagner, H.: Memory-efficient computation of persistent homology for 3D images using discrete morse theory. In: 2011 24th SIBGRAPI Conference on Graphics, Patterns and Images (Sibgrapi), pp. 25-32 (2011) · Zbl 1251.68266 |
| [15] | Gyulassy, A., Bremer, P.T., Hamann, B., Pascucci, V.: A practical approach to Morse-Smale complex computation: scalability and generality. IEEE Trans. Vis. Comput. Graph. 14(6), 1619-1626 (2008) · doi:10.1109/TVCG.2008.110 |
| [16] | Kaczyński, T., Mischaikow, K., Mrozek, M.: Computational homology. Applied Mathematical Sciences. Springer, Berlin (2004) · Zbl 1039.55001 |
| [17] | Lewiner, T., Lopes, H., Tavares, G.: Applications of Forman’s discrete Morse theory to topology visualization and mesh compression. IEEE Trans. Vis. Comput. Graph. 10(5), 499-508 (2004) · doi:10.1109/TVCG.2004.18 |
| [18] | Martín-Vide, C., Pazos, J., Păun, Gh., Rodríguez-Patón, A.: A new class of symbolic abstract neural nets: tissue P systems. In: Ibarra, O.H., Zhang, L. (eds.) COCOON. Lecture Notes in Computer Science, vol. 2387, pp. 290-299 (2002) · Zbl 1077.68645 |
| [19] | Martín-Vide, C., Păun, Gh., Pazos, J., Rodríguez-Patón, A.: Tissue P systems. Theoret. Comput. Sci. 296(2), 295-326 (2003) · Zbl 1045.68063 |
| [20] | Molina-Abril, H., Real, P.: Homological optimality in discrete Morse theory through chain homotopies. Pattern Recogn. Lett. 33(11), 1501-1506 (2012) · doi:10.1016/j.patrec.2012.01.014 |
| [21] | Molina-Abril, H., Real, P.: Homological spanning forest framework for 2D image analysis. Ann. Math. Artif. Intell. 64(4), 385-409 (2012) · Zbl 1270.55005 · doi:10.1007/s10472-012-9297-7 |
| [22] | Nithin, S., Vijay, N.: Parallel computation of 3D Morse-Smale complexes. Comput. Graph. Forum 31(3), 965-974 (2012) |
| [23] | Peña-Cantillana, F., Díaz-Pernil, D., Berciano, A., Gutiérrez-Naranjo, M.A.: A parallel implementation of the thresholding problem by using tissue-like P systems. In: Real, P., Díaz-Pernil, D., Molina-Abril, H., Berciano, A., Kropatsch, W.G. (eds.) CAIP (2). Lecture Notes in Computer Science, vol. 6855, pp. 277-284 (2011) |
| [24] | Peña-Cantillana, F., Díaz-Pernil, D., Christinal, H.A., Gutiérrez-Naranjo, M.A.: Implementation on CUDA of the smoothing problem with tissue-like P systems. Int. J. Nat. Comput. Res. 2(3), 25-34 (2011) · doi:10.4018/jncr.2011070103 |
| [25] | Păun, A., Păun, Gh.: The power of communication: P systems with symport/antiport. New Gener. Comput. 20(3), 295-306 (2002) · Zbl 1024.68037 |
| [26] | Păun, G., Pérez-Jiménez, M.J.: Solving problems in a distributed way in membrane computing: dP systems. Int. J. Comput. Commun. Control 5(2), 238-252 (2010) |
| [27] | Peterka, T., Ross, R., Gyulassy, A., Pascucci, V., Kendall, W., Shen, H.-W., Lee, T.-Y., Chaudhuri, A.: Scalable parallel building blocks for custom data analysis. 2011 IEEE Symposium on Large Data Analysis and Visualization (LDAV), pp. 105-112 (2011) |
| [28] | Real, P., Molina-Abril, H., Kropatsch, W.: Homological tree-based strategies for image analysis. Comput. Anal. Images Patterns (LNCS) 5702, 326-333 (2009) · doi:10.1007/978-3-642-03767-2_40 |
| [29] | Reininghaus, J., Hotz, I.: Combinatorial 2d vector field topology extraction and simplification. In: Topological Methods in Data Analysis and Visualization, pp. 103-114. Springer, Berlin, Heidelberg (2011) · Zbl 1217.68238 |
| [30] | Reininghaus, J., Lowen, C., Hotz, I.: Fast combinatorial vector field topology. IEEE Trans. Vis. Comput. Graph. 17(10), 1433-1443 (2011) · doi:10.1109/TVCG.2010.235 |
| [31] | Ritter, G.X., Wilson, J.N., Davidson, J.L.: Image algebra: an overview. Comput. Vis. Graph. Image Process. 49(3), 297-331 (1990) · doi:10.1016/0734-189X(90)90106-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
