The number of convex polyominoes reconstructible from their orthogonal projections

Many problems of computer-aided tomography, pattern recognition, image processing and data compression involve a reconstruction of bidimensional discrete sets from their projections. [3-5, 10, 12, 16, 17]. 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 is an element of N-n and H is an element of N-n. 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.