A geometrical characterization of regions of uniqueness and applications to discrete tomography

In the reconstruction problem of Discrete Tomography, projections are considered from a finite set $\mathcal{S}$ of lattice directions. Employing a limited number of projections implies that the injectivity of the Radon transform is lost, and, in general, images consistent with a given set of projections form a huge class. In order to lower the number of allowed solutions, one usually tries to include in the problem some a priori information. This suggests that modeling the tomographic reconstruction problem as a linear system of equations is preferable. In this paper we propose to restrict the usual notion of uniqueness, related to the solutions of the linear system, and to provide, for each set $\mathcal{S}$, a geometrical characterization of the shape of a lattice subset, say region of uniqueness (ROU), forming a partial, fast reconstructible, solution. Any selected set $\mathcal{S}$ intrinsically determines its ROU inside an arbitrary lattice grid. For instance, trivially, if $|\mathcal{S}|=1$, the ROU is represented by two rectangles having sizes equal to the absolute values of the entries of the unique direction in $\mathcal{S}$, and placed at two opposite corners of the chosen grid. Surprisingly, if $|\mathcal{S}|=2$, the problem becomes much more complicated. Our purpose is to provide a geometrical characterization of the ROU. This is based on a double Euclidean division algorithm (DEDA), which runs in polynomial time. It turns out that the ROU is delimited by a zigzag profile obtained by means of numerical relations among the entries of the employed directions. According to different inputs in DEDA, the shape of the ROU can change consistently, as it can be easily observed from the provided examples. Moreover, after selecting a region of interest (ROI) from a given phantom, we exploit DEDA to reconstruct the part of the ROI which falls in the ROU and, with a few further a priori knowledge, even parts of the ROI which are outside the ROU.