nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

01.03.2015 | Original Paper

Membrane parallelism for discrete Morse theory applied to digital images

verfasst von: Raúl Reina-Molina, Daniel Díaz-Pernil, Pedro Real, Ainhoa Berciano

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 1-2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Computing fundamental groups from point clouds

Nächster Artikel Approximating persistent homology in Euclidean space through collapses

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In [13] Forman works with simplicial complexes, however the mathematical scaffolding provided by DMT can be settled with no change to finite cubical complexes.

The reader is supposed to be familiar with concepts of Image Algebra. For a detailed text, see [31].

Lemma 1 grants the identification of cubical cells in a cubical complex in \({\mathbb {R}}^k\) with \(k\)-tuples.

Introduced in [25].

In case of 2D images, \(B_\mathbf {i} = B_{i_1 i_2}\).

CW complex in [13] and cubical complex in this paper.

Bauer, U., Lange, C., Wardetzky, M.: Optimal topological simplification of discrete functions on surfaces. Discrete Comput. Geom. 47(2), 347–377 (2012)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)

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)

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)CrossRef

Christinal, H.A., Díaz-Pernil, D., Real, P.: P systems and computational algebraic topology. Math. Comput. Model. 52(11–12), 1982–1996 (2010)CrossRefMATH

Cazals, F., Chazal, F., Lewiner, T.: In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 351–360. ACM (2003)

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)CrossRefMATH

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)CrossRefMATHMathSciNet

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)CrossRef

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)

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)CrossRefMATHMathSciNet

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)

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)CrossRef

16.

Kaczyński, T., Mischaikow, K., Mrozek, M.: Computational homology. Applied Mathematical Sciences. Springer, Berlin (2004)

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)CrossRef

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)

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)

20.

Molina-Abril, H., Real, P.: Homological optimality in discrete Morse theory through chain homotopies. Pattern Recogn. Lett. 33(11), 1501–1506 (2012)CrossRef

21.

Molina-Abril, H., Real, P.: Homological spanning forest framework for 2D image analysis. Ann. Math. Artif. Intell. 64(4), 385–409 (2012)CrossRefMATHMathSciNet

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)CrossRef

25.

Păun, A., Păun, Gh.: The power of communication: P systems with symport/antiport. New Gener. Comput. 20(3), 295–306 (2002)

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)CrossRef

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)

30.

Reininghaus, J., Lowen, C., Hotz, I.: Fast combinatorial vector field topology. IEEE Trans. Vis. Comput. Graph. 17(10), 1433–1443 (2011)CrossRef

31.

Ritter, G.X., Wilson, J.N., Davidson, J.L.: Image algebra: an overview. Comput. Vis. Graph. Image Process. 49(3), 297–331 (1990)CrossRef

Titel: Membrane parallelism for discrete Morse theory applied to digital images
verfasst von: Raúl Reina-Molina
Daniel Díaz-Pernil
Pedro Real
Ainhoa Berciano
Publikationsdatum: 01.03.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 1-2/2015
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-014-0246-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1-2/2015

The third homotopy group as a $$\pi _1$$ π 1 -module

Cohomological learning of periodic motion

Approximating persistent homology in Euclidean space through collapses

Computing path categories of finite directed cubical complexes

Topology of acyclic complexes of tournaments and coloring

Editorial