Complexity Results and Reconstruction
Algorithms for Discrete Tomography
Tesi di: Frosini Andrea
Coordinatore della ricerca: Prof. Alberto Del Lungo
1
Tomografia
TOMOGRAFIA COMPUTERIZZATA:
il processo mediante il quale è possibile ottenere informazioni circa la
distribuzione di densità di una struttura fisica a partire da un insieme di
proiezioni ottenute tramite raggi X. Matematicamente si vuole ricostruire una
funzione di densità (x), con x R2 o R3, a partire dalla conoscenza dei suoi
integrali di linea L (x) dx.
Caratteristiche:
la struttura da ricostruire ha, in generale, una grande quantità di valori di densità
il numero delle proiezioni varia tra 480 e 1000
2
Tomografia
TOMOGRAFIA DISCRETA:
area della Tomografia Computerizzata che si occupa di strutture fisiche aventi
un piccolo numero di valori di densità diversi. Matematicamente: si vuole
ricostruire una funzione di densità (x), con x Z2 o Z3, a partire dalla
conoscenza del numero di atomi/molecole della struttura presenti su linee
discrete.
Caratteristiche:
 la struttura esaminata è spesso costituita da uno o al massimo due tipi
diversi di atomi/molecole;
 il numero delle proiezioni varia tra 2 e 4;
 l’indagine utilizza strumenti basati principalmente sulla matematica
discreta, geometria e combinatoria.
3
Applicazioni
 Tomografia computerizzata industriale: si effettuano test non distruttivi su
materiali omogenei per verificarne l’integrità.
L’immagine ricostruita contiene solo due valori: 0 per l’aria ed un
valore associato al materiale.
 Compressione e codifica di dati: si considerano le proiezioni come codifica
di un oggetto. Difficoltà di ricostruzione possono garantirne la sicurezza,
mentre risultati di unicità la perfetta compressione.
Applicazioni mediche: nelle angiografie per la ricostruzione e, successivamente,
per la visualizzazione delle camere ventricolari a partire da sezioni planari di
queste. Nell’indagine si associa alla presenza del mezzo di contrasto il valore 1,
all’assenza il valore 0.
Analisi di strutture cristalline: in particolare nella ricostruzione della disposizione
degli atomi all’interno di strutture cristalline. Lo scopo è quello di utilizzare tali
informazioni per fare controlli di qualità su larga scala nell’ambito delle
tecnologie VLSI (Very Large-Scale Integration).
4
Il modello generale
Componente elementare
della struttura fisica
Struttura fisica
Punto x di Z3
Sottoinsieme S
finito di Z3
Direzione di proiezione
Vettore v in Z3
Proiezione di S lungo la
linea l (v) di direzione v
PS (l (v))=| S  l (v) |
Per lo studio di STRUTTURE CRISTALLINE privilegiamo:
 Strutture bidimensionali
 Le direzioni orizzontale e verticale: v1=(1,0) e v2=(0,1)
5
Rappresentazione del modello
per reticoli cristallini
3 4 1 3 0 6
5
2
3
4
1
2
x
l (1,0)
1
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
l (0,1)
v1= (1,0)
v2= (0,1)
6
Problemi principali
Sia  una classe di insiemi di Z2 e sia  = (v1,v2). Definiamo
Consistenza ( , )
Dati: due vettori H e V
Domanda: esiste un insieme S  avente H e V come proiezioni lungo v1 e v2 ?
Ricostruzione ( , )
Dati: due vettori H e V
Compito: costruire un insieme S  avente H e V come proiezioni lungo v1 e v2 ?
Unicità ( , )
Dati: un elemento S della classe 
Domanda: esiste un insieme S’  equivalente ad S rispetto alle proiezioni
lungo v1 e v2 ?
7
Alcuni risultati
Sia  la classe dei sottoinsiemi finiti di Z2.
Ryser, Gale (1957):
Ricostruzione ( , ) può essere eseguito in tempo polinomiale.
Consistenza ( , ) ammette soluzione in tempo polinomiale.
Unicità ( , ) ammette soluzione in tempo polinomiale.
Spesso il numero di matrici che soddisfano una coppia di soluzioni
è molto grande e queste possono risultare estremamente
diverse l’una dall’altra.
8
Eliminare le soluzioni equivalenti
AUMENTANDO IL NUMERO DI PROIEZIONI:
Gardner, Gritzmann, Prangerberg (1999):
Se   3, allora
Ricostruzione ( , ) è NP-hard.
Consistenza ( , ) è NP-completo.
Unicità ( , ) è NP-completo.
In tempo polinomiale possono essere ottenute solo soluzioni approssimate cioè
soluzioni le cui proiezioni sono “vicine” a quelle del sistema di partenza.
Sfortunatamente, se i dati in input non sono tali da determinare l’unicità della
soluzione, anche in questo caso il sistema ricostruito può essere molto diverso
da quello di partenza!
9
Eliminare le soluzioni equivalenti
UTILIZZANDO INFORMAZIONI A PRIORI:
Gli algoritmi di ricostruzione possono trarre vantaggio da proprietà geometriche
della struttura quali connessione o convessità.
Queste informazioni vengono sfruttate per ridurre l’ampiezza della classe  alla
quale la soluzione deve appartenere: ad esempio
Barcucci, Del Lungo, Nivat, Pinzani (1996):
Se  = (p), (h), (v), (p,h), (p,v), (h,v) e  = (v1,v2), allora
Ricostruzione ( , ) è NP-hard.
Consistenza ( , ) è NP-completo.
Se  = (p,h,v), allora
Ricostruzione ( , ) può essere eseguito in tempo polinomiale.
Consistenza ( , ) ammette soluzione in tempo polinomiale.
10
La tesi propone una serie di risultati volti alla caratterizzazione di
strutture piane con forti proprietà geometriche tramite le loro
proiezioni lungo due direzioni discrete.
Lo studio è stato condotto in sintonia con quelli che sembrano essere
attualmente i canoni metodologici della Tomografia Discreta.
Introduzione
Definizioni e
notazioni generali
Parte I
Studio di
strutture
periodiche
Parte II
Studio di strutture
a partire da proiezioni
con assorbimento
Parte III
Studio di
strutture composte
da dimeri
11
Parte I: studio di strutture periodiche
VINCOLO DI PERIODICITÀ
Una struttura si dice (p,q)-periodica se la matrice Am x n ad essa associata è
tale che
ai,j=1  ( ai+q,j+p=1 ) e ( ai-q,j-p=1 )
In A si definisce
 linea li,j : l’insieme degli elementi ai’,j’ =1 tali che
i’= i+kq , j’ = (j+kp) modn con k  Z;
 inizio e fine di una linea: i due elementi della linea che occupano
la minima e massima riga rispettivamente;
 linea lunga: una sequenza di linee tali che due di esse consecutive
hanno inizio e fine distanti p modn lungo le colonne;
 loop: una linea lunga nella quale l’inizio e la fine distano p modn
lungo le colonne.
12
Parte I: studio di strutture periodiche
ESEMPIO: MATRICI CON PERIODICITÀ (1,2)
T1
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
Due linee e tre punti
non appartenenti ad
alcuna linea.
T2
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
Un loop composto da due linee.
Sono evidenziati i punti di
inizio e fine di ciascuna linea.
13
Parte I: studio di strutture periodiche
FORMALIZZAZIONE DELLA TEORIA DEGLI SWITCHES
Si definisce switch ogni operatore che modifica gli elementi di una matrice
mantenendone inalterate le proiezioni lungo un insieme di direzioni prescelte.
Switches lungo la direzione orizzontale:
a) spostamento di una intera riga;
b) spostamento di punti isolati all’interno della stessa zona T1 o T2.
Siano A e B due matrici aventi le stesse proiezioni orizzontali.
Esiste una sequenza di switches del tipo a) e b) che trasformano A in B.
Switches lungo le direzioni orizzontale e verticale:
a) spostamento di elementi all’interno di una stessa linea lunga;
b) scambio di linee lunghe formate della stessa lunghezza;
c) scambio di elementi all’interno della stessa zona T1 o T2.
Studi volti alla caratterizzazione di tutti e soli gli switches lungo due direzioni sono
14
attualmente in corso.
Parte I: studio di strutture periodiche
RISULTATI PRINCIPALI
Sia  la classe dei sottoinsiemi finiti di Z2 aventi periodicità (p,q) e  = (v1).
Ricostruzione ( , ), Consistenza ( , ) ed Unicità ( , )
ammettono soluzione in tempo polinomiale.
Sia  la classe dei sottoinsiemi finiti di Z2 aventi periodicità (1,q) e  = (v1,v2).
Ricostruzione ( , ) può essere eseguito in tempo polinomiale.
Consistenza ( , ) ammette soluzione in tempo polinomiale.
Unicità ( , ) ammette soluzione in tempo polinomiale.
I tre problemi rimangono aperti nel caso generale.
15
Parte I: studio di strutture periodiche
DETTAGLI SULLA RICOSTRUZIONE DI MATRICI
(1,q)-PERIODICHE DA 2 PROIEZIONI
Sia  la classe dei sottoinsiemi finiti di Z2 aventi periodicità (1,q) e  = (v1,v2).
Ricostruzione ( , ):
Input: due vettori H e V.
Output: la matrice (1,q)-periodica A avente H e V come proiezioni orizzontali e
verticali.
Passo 1 - ricostruzione della parte fissa di A (preprocessing): vengono identificati
gli elementi non appartenenti ad alcuna linea e vengono ricostruiti separatamente
in una matrice F. I vettori H e V vengono aggiornati in H’ e V’.
Passo 2 - creazione di una istanza I’ del problema di ricostruzione di un poliomino
convesso su una superficie cilindrica da due proiezioni equivalente a
Ricostruzione ( , ) con input H’ e V’.
16
Parte I: studio di strutture periodiche
DETTAGLI SULLA RICOSTRUZIONE DI MATRICI
(1,q)-PERIODICHE DA 2 PROIEZIONI
Passo 3 - caratterizzazione di I’ tramite una formula Booleana appartenente a
2-SAT e sua soluzione (es. algoritmo di Aspvall, Plass e Tarjan, 1979).
Passo 5 - passaggio alla soluzione del problema Ricostruzione ( , ) con
input H’ e V’.
Passo 4 - fusione della soluzione trovata con la matrice F per ottenere la soluzione
finale A. Tale procedura necessita dell’applicazione dell’algoritmo di Ryser per la
ricostruzione di una matrice da due proiezioni.
N.B. qualora la periodicità ecceda le dimensioni della matrice,
l’algoritmo precedente si riduce al solo algoritmo di Ryser.
17
Parte I: studio di strutture periodiche
CORRISPONDENZA
MATRICE PERIODICA - POLIOMINO CONVESSO
0
0
0
M: 1
0
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
P:
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
1
1
1
0
0
1
1
1
0
0
0
1
1
1
Ciascuna linea della matrice (1,2)-periodica M viene trasformata in una barra
costituente il poliomino P.
18
Parte I: studio di strutture periodiche
PRODUZIONE:
A.Del Lungo, A.Frosini, M.Nivat, L.Vuillon,
“Discrete Tomography: Reconstruction under periodicity constraints”
Lecture Notes in Computer Science, No.2380, 38-56, Proceedings of Automata,
Languages and Programming, 29th International Colloquium, ICALP 2002.
A.Del Lungo, A.Frosini, M.Nivat, L.Vuillon,
“Reconstructing binary matrices under periodical constraints from
orthogonal X-rays” in preparazione.
A.Frosini,
“A characterization for the switches of periodical structures” in preparazione.
19
Parte II: modelli reali con assorbimento
DEFINIZIONI
Estendiamo il modello discreto alla situazione reale di un corpo che sia
contemporaneamente emettitore ed assorbente immerso in ambiente assorbente
e sia  il coefficiente di assorbimento di entrambi gli elementi del sistema.
-2
-1
+
+
-4
proiezioni
emettitore
-5
-5
ambiente
-5
rilevatori
A ciascun rilevatore posto al bordo del sistema, arriverà un segnale proporzionale al
numero di emettitori sulla sua linea di influenza ed inversamente proporzionale alla
-d
lunghezza del cammino d che questo ha percorso, secondo la legge I = I0  20
Parte II: modelli reali con assorbimento
DEFINIZIONI
Sia 0 il valore del coefficiente di assorbimento tale che 0-1 = 0-2 + 0-3:
0 = (1+ 5-1/2)/2 .
Chiamiamo 0 rappresentazione del numero r  R una parola w = w1 … wk tale che:
r = w10-1 +…+ wk 0-k .
es. 010110100, 010110011 e 100000100 sono 0 rappresentazioni equivalenti.
Le 0 rappresentazioni equivalenti possono essere considerate 1D switches!
Data una parola w = w1 … wk definiamo
rleft = w10-1 +…+ wk 0-k ed
.
rright = w10-k +…+ wk 0-1
21
Parte II: modelli reali con assorbimento
2D SWITCHES
Uno switch lungo le direzioni orizzontale e verticale è definito come composizione
degli switches base
011
E(0)= 1 0 0
100
100
E(1)= 0 1 1
011
100
011
es. E(1)*E(0)*E(0) = 0 1 x 1 x 1 1
10x00
10x00
Kuba, Nivat (2001):
1.
2.
Una matrice binaria è determinata univocamente da H e V sse non ha switches.
Date A e B matrici binarie che siano equivalenti rispetto ad H e V, esiste una
sequenza di switches che trasformano A in B.
22
Parte II: modelli reali con assorbimento
RISULTATI: RICOSTRUZIONE DI MATRICI DA PROIEZIONI
ORIZZONTALI DESTRE E SINISTRE CON ASSORBIMENTO
I due valori rleft ed rright determinano univocamente una sequenza di lunghezza fissata.
Ogni matrice binaria è determinata dalle sue proiezioni orizzontali destre e sinistre.
Sia  la classe dei sottoinsiemi finiti di Z2 e  = (v1left,v1right).
Ricostruzione ( , ) può essere eseguito in tempo polinomiale.
Consistenza ( , ) ammette soluzione in tempo polinomiale.
Unicità ( , ) ammette soluzione in tempo polinomiale.
L’algoritmo che ricostruisce una matrice binaria a partire dalle proiezioni
orizzontali destre e sinistre ha complessità lineare nelle dimensioni della soluzione.
23
Parte II: modelli reali con assorbimento
RISULTATI: RICOSTRUZIONE DI MATRICI DA PROIEZIONI
ORIZZONTALI E VERTICALI CON ASSORBIMENTO
1.
Le proiezioni orizzontali e verticali permettono di individuare tutti i possibili
punti di inizio degli switches all’interno dell’eventuale matrice soluzione.
2. L’evoluzione di ciascuno switch all’interno della matrice soluzione può essere
seguita utilizzando le proiezioni orizzontali e verticali, indipendentemente
dagli altri switches che eventualmente sono presenti in essa.
3. Due switches che hanno una o più posizioni in comune coincidono.
4. Ogni switch ha un numero di configurazioni diverse che è lineare nelle sue
componenti elementari
Sia  la classe dei sottoinsiemi finiti di Z2 e  = (v1,v2).
Ricostruzione ( , ) può essere eseguito in tempo polinomiale.
Consistenza ( , ) ammette soluzione in tempo polinomiale.
Unicità ( , ) ammette soluzione in tempo polinomiale.
24
Parte II: modelli reali con assorbimento
DETTAGLI SULLA RICOSTRUZIONE DI MATRICI
DA DUE PROIEZIONI CON ASSORBIMENTO
Strategia:
 la matrice soluzione viene ricostruita colonna per colonna, individuando
TUTTI i possibili punti di inizio di 2D switchings e seguendone ogni possibile
evoluzione grazie a computazioni parallele.
 Ad ogni istante, il numero di linee di computazione attive è pari al massimo
numero di possibili configurazioni per ciascun ipotetico switch ancora in fase
di ricostruzione.
 Se, ad un dato istante, non ci sono switches in fase di ricostruzione, la
computazione procede su una singola linea.
 Alla fine della ricostruzione di ciascuna colonna della matrice si procede alla
riduzione del numero di linee di computazione, eliminando quelle non necessarie.
25
Parte II: modelli reali con assorbimento
Fine switches
INCONSISTENZA!
Scambio delle
configurazioni
26
Parte II: modelli reali con assorbimento
PRODUZIONE
E.Barcucci, A.Frosini, S.Rinaldi,
“Reconstruction of discrete sets from two absorbed projections: an algorithm”
accettato al 9th International Workshop in Combinatorial Image Analysis-2003.
E.Barcucci, A.Frosini, A.Kuba,
“An algorithm for reconstructing discrete sets from their horizontal and vertical
absorbed projections” in preparazione.
27
Parte III: tilings con domini
DEFINIZIONI
L’estensione del modello discreto classico ai tilings di superfici rettangolari con
domini viene proposta per lo studio di sistemi fisici composti da dimeri, cioè
molecole la cui configurazione chimica si estende su due siti adiacenti.
X
X X
X
X
5
6
6
6
6
5
Conoscendo le dimensioni del tiling e le proiezioni orizzontali [verticali] è possibile
ricavare il numero di domini verticali [orizzontali] che iniziano o terminano su
ciascuna riga [colonna].
28
Parte III: tilings con domini
DEFINIZIONI
Dividiamo un tiling con domini di dimensione m x n in k sotto-tilings completi,
detti strisce, aventi minime dimensioni m1 x n , … , mk x n :
Striscia di altezza 2
Striscia di altezza 4
(+3, 0)
( 0 ,-3)
(+3, 0)
(+2,-3)
(+1,-2)
( 0 ,-1)
Si definisce grado di un domino tiling il massimo tra le altezze m1 , … , mk delle
strisce che lo compongono.
29
Parte III: tilings con domini
RICOSTRUZIONE DI TILINGS CON DOMINI DA UNA PROIEZIONE:
UN SEMPLICE ALGORITMO
Sia  la classe dei tilings con domini di dimensione n x m e  = (v1).
Ricostruzione ( , ):
Input: un vettore H=(h1,…,hm).
Output: un domino tiling T avente H come vettore delle proiezioni orizzontali.
Strategia: si ricostruisce il tiling riga per riga sistemando, nella riga i-esima, n - hi
domini orizzontali nelle posizioni più a sinistra possibili e completando le
rimanenti con domini verticali.
30
Parte III: tilings con domini
RICOSTRUZIONE DI TILINGS CON DOMINI DALLE PROIEZIONI
ORIZZONTALI E VERTICALI: TILINGS DI GRADO TRE.
Picouleau, (2001):
Ogni tiling con domini di grado due è ricostruibile in tempo polinomiale utilizzando
le proiezioni orizzontali e verticali.
Ogni striscia di altezza tre è percorsa da una linea di domini orizzontali.
Ogni tiling con domini di grado tre è ricostruibile in tempo polinomiale utilizzando
le proiezioni orizzontali e verticali.
31
Parte III: tilings con domini
RICOSTRUZIONE DI TILINGS CON DOMINI DALLE PROIEZIONI
ORIZZONTALI E VERTICALI: TILINGS DI GRADO QUATTRO.
Ogni striscia di altezza 4 può essere divisa in blocchi contenenti ciascuno zero o due
domini verticali.
Ogni striscia di altezza 4 ha un numero pari di domini verticali che iniziano nella
seconda riga e può essere ridotta ad una coppia di strisce di altezza 2 alzando o
abbassando di una posizione le coppie di domini verticali.
CONSEGUENZA: Ogni tiling con domini di grado quattro è ricostruibile in tempo
polinomiale utilizzando le proiezioni orizzontali e verticali.
32
Parte III: tilings con domini
TILINGS CON DOMINI BICOLORATI: DEFINIZIONI
I tilings composti da due tipi diversi di domini:
 risultano utili nello studio di strutture poliatomiche composte da dimeri;
 hanno forti connessioni con il problema 3-colors.
X
N.B. Le proiezioni NON danno
informazioni sul numero di domini
orizzontali e verticali di ciascun tipo.
X X
X
X
3,2
4,2
4,2
3,3
5,1
5,0
Picouleau, (2000):
If we know the horizontal and vertical projections, then
”the problem of deciding if a bicolored domino tiling exists is harder than the
three colors reconstruction problem”.
33
Parte III: tilings con domini
UNA PROVA DI NP-COMPLETEZZA
Numerical Matching with Target Sums
Istanza: tre vettori di numeri interi
X=(x1,…,xk ); Y=(y1,…,yk ); S=(s1,…,sk )
Domanda: esistono due permutazioni  e  degli elementi di X e Y tali che
X +Y = V ?
X = (2,3,2,1,4)
(9,0)
(8,2)
(7,2)
(6,4)
(4,4)
(2,8)
(1,8)
(0,10)
(0,10)
Le proiezioni verticali sono sufficienti ad assicurare la “convessità”
dei domini neri verticali!
34
Parte III: tilings con domini
UNA PROVA DI NP-COMPLETEZZA
Istanza I di NMTS:
X = (2,3,2,1,4) Y = (1,1,3,1,2)
S = (4,3,4,4,5)
Soluzione di I:
X = (1,2,3,2,4) Y = (3,1,1,2,1)
Istanza I’ di Consistenza( , (v1,v2)):
H = ((9,0), (8,2), … ,(8,2),(9,0))
V=((5,4), (5,4),…,(4,5),(4,5))
L’eventuale soluzione polinomiale di I’
darebbe luogo alla soluzione polinomiale di I.
35
Parte III: tilings con domini
PRODUZIONE
A.Frosini, G.Simi,
“The reconstruction of a bicolored domino tiling from two projections”
Lecture Notes in Computer Science, No. 2301, 136-144, Prooceedings of the
10th International Conference, DGCI 2002, Bordeaux, France, April 3-5, 2002.
A.Frosini, G.Simi,
“The NP-completeness of a tomographical problem on bicolored domino tilings”
sottomesso.
A.Frosini, G.Simi,
“Reconstruction of low degree domino tilings”
accettato al 9th International Workshop in Combinatorial Image Analysis-2003.
36