Binary image reconstruction from a small number of projections and the morphological skeleton. (English) Zbl 1341.68303
Summary: In binary tomography, the goal is to reconstruct binary images from a small set of their projections. This task can be underdetermined, meaning that several binary images can have the same projections, especially when only one or two projections are given. On the other hand, it is known that a binary image can be exactly reconstructed from its morphological skeleton when all skeletal labels are known. However, if only the skeletal points are given, different labellings yield different reconstructed images. In this paper, we consider a mixture of the above problems, reconstructing a binary image from few projections and the morphological skeleton. We show that the problem is NP-complete, yet a result with low projection and pixel error usually can be achieved, even if only a single projection is available. Three different variants of a method based on Simulated Annealing are developed and compared with respect to reconstruction time and error using artificial binary images.
MSC:
| 68U10 | Computing methodologies for image processing |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
reconstruction; binary tomography; NP-completeness; morphological skeleton; simulated annealingReferences:
| [1] | Aert, S.V., Batenburg, K.J., Rossell, M.D., Erni, R., Tendeloo, G.V.: Three-dimensional atomic imaging of crystalline nanoparticles. Nature 470, 374-377 (2011) · doi:10.1038/nature09741 |
| [2] | Back, T.: Evolutionary Algorithms in Theory and Practice - Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, New York (1996) · Zbl 0877.68060 |
| [3] | Balázs, P.: A benchmark set for the reconstruction of hv-convex discrete sets. Discret. Appl. Math. 157, 3447-3456 (2009) · Zbl 1186.68488 · doi:10.1016/j.dam.2009.02.019 |
| [4] | Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Reconstructing convex polyominoes from horizontal and vertical projections. Theor. Comput. Sci. 155, 321-347 (1996) · Zbl 0872.68134 · doi:10.1016/0304-3975(94)00293-2 |
| [5] | Batenburg, K.J., Bals, S., Sijbers, J., Kuebel, C., Midgley, P.A., Hernandez, J.C., Kaiser, U., Encina, E.R., Coronado, E.A., Tendeloo, G.V.: 3D imaging of nanomaterials by discrete tomography. Ultramicroscopy 109(6), 730-740 (2009) · doi:10.1016/j.ultramic.2009.01.009 |
| [6] | Baumann, J., Kiss, Z., Krimmel, S., Kuba, A., Nagy, A., Rodek, L., Schillinger, B., Stephan, J.: Discrete tomography methods for nondestructive testing. In: Herman, G.T., Kuba, A (eds.) Advances in Discrete Tomography and Its Applications, pp. 303-331. Birkhäuser, Boston (2007) · Zbl 1130.65122 |
| [7] | Blum, H.: Biological shape and visual science (Part I). J. Theor. Biol. 38, 205-287 (1973) · doi:10.1016/0022-5193(73)90175-6 |
| [8] | Brunetti, S., Del Lungo, A., Del Ristoro, F., Kuba, A., Nivat, M.: Reconstruction of 8- and 4-connected convex discrete sets from row and column projections. Linear Algebra Appl. 339, 37-57 (2001) · Zbl 1007.65108 · doi:10.1016/S0024-3795(01)00435-9 |
| [9] | Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979) · Zbl 0411.68039 |
| [10] | Gesù, V.D., Bosco, G.L., Millonzi, F., Valenti, C.: A memetic algorithm for binary image reconstruction. In: Brimkov, V.E., Barneva, R.P., Hauptman, H.A. (eds.) IWCIA 2008. LNCS, Vol. 4958, pp. 384-395. Springer, Heidelberg (2008) |
| [11] | Giblin, P., Kimia, B.B.: A formal classification of 3D medial axis points and their local geometry. IEEE Trans. Pattern Anal. Machine Intell. 26(2), 238-251 (2004) · doi:10.1109/TPAMI.2004.1262192 |
| [12] | Gonzalez, R.C., Woods, R.E.: Digital Image Processing, 3rd edn. Prentice Hall (2008) |
| [13] | Hantos, N., Balázs, P.: The reconstruction of polyominoes from horizontal and vertical projections and morphological skeleton is NP-complete. Fundamenta Informaticae 125(3-4), 343-359 (2013) · Zbl 1270.68371 |
| [14] | Hantos, N., Balázs, P., Palágyi, K.: Binary image reconstruction from two projections and morphological skeleton. In: 15th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science, vol. 7655, pp. 263-274 (2012) · Zbl 1377.68304 |
| [15] | Herman, G.T., Kuba, A. (eds.): Advances in Discrete Tomography and Its Applications. Birkhäuser, Boston (2007) · Zbl 1117.65004 |
| [16] | Hochstättler, W., Loebl, M., Moll, C.: Generating convex polyominoes at random. Discret. Math. 153, 165-176 (1996) · Zbl 0854.05032 · doi:10.1016/0012-365X(95)00134-I |
| [17] | Irving, R.W., Jerrum, M.R.: Three-dimensional data security problems. SIAM J. Comput. 23, 170-184 (1994) · Zbl 0802.68046 · doi:10.1137/S0097539790191010 |
| [18] | Kirkpatrick, S., Gelatt, C.D. Jr., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [19] | Kuba, A.: Reconstruction in different classes of 2D discrete sets. Lect. Notes Comput. Sci. 1568, 153-163 (1999) · doi:10.1007/3-540-49126-0_12 |
| [20] | Maragos, P., Schafer, R.W.: Morphological skeleton representation and coding of binary images. IEEE Trans. Acoustics Speech Signal Process. 34(5), 1228-1244 (1986) · doi:10.1109/TASSP.1986.1164959 |
| [21] | Nagy, A., Kuba, A.: Parameter settings for reconstructing binary matrices from fan-beam projections. J. Comput. Inf. Technol. 14(2), 100-110 (2006) |
| [22] | Pierre, S.: Morphological Image Analysis. Springer-Verlag (2003) · Zbl 1012.68212 |
| [23] | Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9, 371-377 (1957) · Zbl 0079.01102 · doi:10.4153/CJM-1957-044-3 |
| [24] | Schüle, T., Schnörr, C., Weber, S., Hornegger, J.: Discrete tomography by convex-concave regularization and D.C. programming. Discret. Appl. Math. 151, 229-243 (2005) · Zbl 1131.68571 · doi:10.1016/j.dam.2005.02.028 |
| [25] | Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, New York (1982) · Zbl 0565.92001 |
| [26] | Siddiqi, K., Pizer, S. (eds.): Medial Representations - Mathematics, Algorithms and Applications. Computational Imaging and Vision, vol. 37. Springer (2008) · Zbl 1151.00014 |
| [27] | Woeginger, G.J.: The reconstruction of polyominoes from their orthogonal projections. Inf. Process. Lett. 77(5-6), 225-229 (2001) · Zbl 0996.68163 · doi:10.1016/S0020-0190(00)00162-9 |
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.
