From uniqueness results to reconstruction and characterization algorithms in discrete tomography

Tomography is a powerful technique to retrieve information about objects that are not directly accessible. Tomographic reconstructions have a wide range of applications, such as in medicine, industry, crystallography, and several other areas of research. Tomography was born thanks to the early work of Johann Radon, who published in 1917 a theoretical paper concerning the reconstruction of a function from the knowledge of its line integrals. The result was later exploited by Allan McLeod Cormack and Godfrey Newbold Hounsfield, who designed and invented the first scanner, based on the use of X-ray radiation along a number of directions. This allowed them to share the 1979 Nobel Prize in Medicine, and represented the beginning of Computerized Axial Tomography (CAT) as a powerful diagnostic method in Medicine. When trying to adapt the theory to real applications, one needs to change the continuous model into several critical items, which are obtained by introducing different discretization steps. This leads to discrete tomography, where the word ``discrete'' refers both to the discretization of the image, which is seen as a collection of pixels, and the discrete (and finite) number of admissible directions and densities. Discrete tomography is the topic of the present thesis. One of the main goals of tomography is uniqueness of reconstruction. In fact, the tomographic problem is ill-posed, due to the presence of the so-called ghosts. These are non-null functions having zero line sums along the considered directions, and consequently they can be added to a solution in order to obtain other admissible solutions. Some prior knowledge is exploited to lower the number of possible solutions. For instance, one can assume to know in advance the number of the grey levels in the object to be reconstructed (the limit case is represented by binary, i.e., black-and-white, images). Further, one can set the tomographic problem inside a finite grid of known size, or, also, the knowledge of some features of the object can be added, such as convexity, or the particular geometric class it belongs to. The present thesis focuses both on theoretical and algorithmic aspects of discrete tomography, mainly related to the uniqueness issue, to reconstruction and to characterization algorithms. Reconstruction algorithms are performed on binary images, with no other features (by employing special sets of four directions), and in the case of hv-convex polyominoes, for whom special frameworks are considered, namely, noisy projections and a blocking component. In the last case, a reconstruction algorithm is provided also for the subclass of L-convex polyominoes. On the other side, we characterize a subset of the set of uniquely determined pixels of an integer-valued function, depending only on the set of chosen directions. For both kinds of algorithms, simulations and experiments are provided.

La tomografia è una tecnica usata per ottenere informazioni su oggetti che non sono direttamente accessibili. Le ricostruzioni tomografiche hanno un’ampia gamma di applicazioni, dalla medicina all’industria, dalla cristallografia a molte altre aree di ricerca. La tomografia è nata grazie al lavoro di Johann Radon, che pubblicò nel 1917 un articolo teorico riguardante la ricostruzione di una funzione partendo dai suoi integrali di linea. Questo risultato fu poi sfruttato da Allan McLeod Cormack e Godfrey Newbold Hounsfield, che progettarono e costruirono il primo scanner, basato sull’uso della radiazione a raggi X lungo un certo numero di direzioni. Ciò permise loro di vincere il premio Nobel per la Medicina nel 1979 e rappresentò l’inizio dell’utilizzo della Tomografia Assiale Computerizzata (TAC) nella diagnostica medica. Quando si cerca di adattare i risultati teorici al mondo reale, si deve modificare il modello continuo, introducendo diversi passi di discretizzazione. Ciò porta alla tomografia discreta, dove la parola ``discreta” si riferisce sia alla discretizzazione dell’immagine, che è vista come un insieme di pixel, sia al numero discrete (e finito) di direzioni e densità utilizzate. La tomografia discreta è l’argomento di questa tesi. Uno dei principali obiettivi della tomografia è l’unicità di ricostruzione. Il problema tomografico, infatti, è mal posto, a causa della presenza dei cosiddetti ghost, immagini non nulle con somma zero lungo le direzioni considerate, che di conseguenza possono essere aggiunti ad una soluzione in modo da ottenere un’altra soluzione. Qualche tipo di conoscenza a priori viene sfruttata per abbassare il numero di possibili soluzioni. Ad esempio, si può supporre di conoscere il numero di livelli di grigio che costituiscono l’oggetto da ricostruire (fino al caso limite rappresentato da due soli livelli, bianco e nero, per le immagini binarie). Inoltre, si può circoscrivere il problema tomografico dentro una griglia finita di lato noto, o, anche, si possono conoscere altre caratteristiche dell’oggetto, come la convessità o l’appartenenza ad una particolare classe. Questa tesi si focalizza sugli aspetti teorici ed algoritmici della tomografia discreta, legati principalmente al problema dell’unicità, per produrre algoritmi di ricostruzione e di caratterizzazione. Gli algoritmi di ricostruzione sono applicati alle immagini binarie, sia senza altre caratteristiche (utilizzando particolari insiemi di quattro direzioni) sia nel caso dei poliomini hv-convessi, per i quali vengono considerate situazioni particolari, cioè proiezioni affette da rumore e la presenza di una componente bloccante. In quest’ultimo caso, viene fornito un algoritmo di ricostruzione anche per la sottoclasse dei poliomini L-convessi. D’altra parte, viene caratterizzato un sottoinsieme dell’insieme dei pixel di una funzione a valori interi univocamente determinati, e tale caratterizzazione dipende solo dall’insieme di direzioni considerato. Per entrambi i tipi di algoritmi vengono forniti simulazioni ed esperimenti.