TY - JOUR

T1 - Uniqueness and reconstruction of finite lattice sets from their line sums

AU - Ascolese, Michela

AU - Dulio, Paolo

AU - Pagani, Silvia Maria Carla

PY - 2024

Y1 - 2024

N2 - If an unknown finite set $C\subset\mathbb{Z}^2$ is cut by lines parallel to given directions, then one may count the number of points of $C$ that are intercepted by each line, that is, the projections of $C$ in the given directions. The inverse problem consists in reconstructing the set $C$, interpreted as a binary image, from the knowledge of its projections.
In general, this challenging combinatorial problem, also related to the tomographic reconstruction of an unknown homogeneous object by means of X-rays, is ill-posed, meaning that different binary images exist that match the available projections. Therefore, as a preliminary step, one can try to find conditions to be imposed on the considered directions in order to limit the number of allowed solutions.
In this paper we address the above problems for sets $C$ contained in a finite assigned lattice grid, and generalize some results known in literature.
First, we describe special sets of lattice directions, called simple cycles, and focus on some of their properties. Then we prove that uniqueness of reconstruction for binary images is guaranteed if and only if the line sums are computed along suitable simple cycles having even cardinality.
As a second item, we prove that the unique binary solution can be explicitly
reconstructed from a real-valued solution having minimal Euclidean norm. This leads to an explicit reconstruction algorithm, tested on four different phantoms and compared with previous results, which points out a significant improvement of the corresponding performance.

AB - If an unknown finite set $C\subset\mathbb{Z}^2$ is cut by lines parallel to given directions, then one may count the number of points of $C$ that are intercepted by each line, that is, the projections of $C$ in the given directions. The inverse problem consists in reconstructing the set $C$, interpreted as a binary image, from the knowledge of its projections.
In general, this challenging combinatorial problem, also related to the tomographic reconstruction of an unknown homogeneous object by means of X-rays, is ill-posed, meaning that different binary images exist that match the available projections. Therefore, as a preliminary step, one can try to find conditions to be imposed on the considered directions in order to limit the number of allowed solutions.
In this paper we address the above problems for sets $C$ contained in a finite assigned lattice grid, and generalize some results known in literature.
First, we describe special sets of lattice directions, called simple cycles, and focus on some of their properties. Then we prove that uniqueness of reconstruction for binary images is guaranteed if and only if the line sums are computed along suitable simple cycles having even cardinality.
As a second item, we prove that the unique binary solution can be explicitly
reconstructed from a real-valued solution having minimal Euclidean norm. This leads to an explicit reconstruction algorithm, tested on four different phantoms and compared with previous results, which points out a significant improvement of the corresponding performance.

KW - Binary tomography

KW - Discrete tomography

KW - Lattice grid

KW - Lattice set

KW - Line sum

KW - Minimum norm solution

KW - Simple cycle

KW - Uniqueness of reconstruction

KW - X-ray

KW - Binary tomography

KW - Discrete tomography

KW - Lattice grid

KW - Lattice set

KW - Line sum

KW - Minimum norm solution

KW - Simple cycle

KW - Uniqueness of reconstruction

KW - X-ray

UR - http://hdl.handle.net/10807/282536

UR - https://www.sciencedirect.com/science/article/pii/s0166218x24002427

U2 - 10.1016/j.dam.2024.05.047

DO - 10.1016/j.dam.2024.05.047

M3 - Article

SN - 0166-218X

VL - 356

SP - 293

EP - 306

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -