zbMATH — the first resource for mathematics

The number of convex polyominoes reconstructible from their orthogonal projections. (English) Zbl 0856.05024
Summary: Many problems of computer-aided tomography, pattern recognition, image processing and data compression involve a reconstruction of bidimensional discrete sets from their projections. The main difficulty involved in reconstructing a set \(\Lambda\) starting out from its orthogonal projections \((V,H)\) is the ‘ambiguity’ arising from the fact that, in some cases, many different sets have the same projections \((V,H)\). In this paper, we study this problem of ambiguity with respect to convex polyominoes, a class of bidimensional discrete sets that satisfy some connection properties similar to those used by some reconstruction algorithms. We determine an upper and lower bound to the maximum number of convex polyominoes having the same orthogonal projections \((V,H)\), with \(V \in \mathbb{N}^n\) and \(H\in\mathbb{N}^m\). We prove that under these connection conditions, the ambiguity is sometimes exponential. We also define a construction in order to obtain some convex polyominoes having the same orthogonal projections.

05B50 Polyominoes
05A15 Exact enumeration problems, generating functions
Full Text: DOI
[1] Barcucci, E.; Del Lungo, A.; Nivat, M.; Pinzani, R., Reconstructing convex polyominoes from their horizontal and vertical projections, Technical report DSI, RT 12/94, (1994), Università di Firenze
[2] Beauquier, D.; Nivat, M., Tiling the plane with one tile, (), 291-334 · Zbl 0755.52008
[3] Chang, S.K., The reconstruction of binary patterns from their projections commun., 14, 21-25, (1971), ACM · Zbl 0214.42603
[4] Chang, S.K.; Chow, C.K., The reconstruction of three-dimensional objects from two orthogonal projections and its application to cardiac cineangiography, IEEE trans. comput., C-22, 661-670, (1973)
[5] Chang, S.K.; Wang, Y.R., Three-dimensional object reconstruction from two orthogonal projections, Pattern recognition, 7, 167-176, (1975) · Zbl 0326.68065
[6] Delest, M., Polyominoes and animals: some recent results, J. comput. and chem., 8, 3-18, (1991)
[7] Del Lungo, A., Polyominoes defined by two vectors, Theoret. comput. sci., 127, 187-198, (1994) · Zbl 0797.05031
[8] Gardner, M.; Gardner, M., Mathematical games, Sci. am., Sci. am., 136-142, (November 1958)
[9] Golomb, S.W., Polyominoes, (1965), Scribner New York
[10] Gordon, R.; Herman, G.T., Reconstruction of pictures from their projections, Graphics image process, 14, 12, 759-768, (1971) · Zbl 0225.68053
[11] Klarner, D.A., My life among the polyominoes, (), 243-262 · Zbl 0476.05029
[12] Krishnan, S.; Prabhu, S.S.; Krishnamurthy, E.V., Probabilistic reinforcement algorithms for the reconstruction of pictures from their projections, Int. J. systems sci., 4, 661-670, (1973)
[13] Kuba, A., The reconstruction of two-directionally connected binary patterns from their two projections, Comput. vision, graphics image process., 27, 249-265, (1984)
[14] Kuba, A., On the reconstruction of binary matrices from their projections, (1986), Pubbl. dell’Ist. di Analisi Globale e Applicazioni, serie Problemi ben posti ed inversi, Firenze
[15] Ryser, H., Combinatorial mathematics, The carus mathematical monographs no. 14, (1963), The Mathematical Association of America Rahway · Zbl 0112.24806
[16] Shliferstein, A.R.; Chien, Y.T., Switching components and the ambiguity problem in the reconstruction of pictures from their projections, Pattern recognition, 10, 327-340, (1978) · Zbl 0389.68050
[17] Slump, C.H.; Gerbrands, J.J., A network flow approach to reconstruction of the left ventricle from two projections, Comput. graphics image process., 18, 18-36, (1982)
[18] Viennot, X.G., A survey of polyomino enumeration, Proc. Séries formelles et combinatoires algébrique, montréal, juin 1992, (1992), Publi. du LACIM 11, Université du Québec a Montréal
[19] Wang, Y.R., Characterization of binary patterns and their projections, IEEE trans. comput., C-24, 1032-1035, (1975) · Zbl 0324.68066
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.