Strutture periodiche discrete:
introduzione del vincolo di periodicità e
studio della ricostruzione da due proiezioni.
A. Del Lungo, A. Frosini, M.Nivat, L.Vuillon
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
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.
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).
Il modello generale
Componente elementare
della struttura fisica
Punto x di Z3
Struttura fisica
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)
Rappresentazione del modello
3 4 1 3 0 6
5
2
3
4
1
2
x
l (1,0)
l (0,1)
v1= (1,0)
v2= (0,1)
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
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 ?
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.
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!
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.
Strutture periodiche: definizioni
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
(attenzione agli indici delle colonne);
 inizio e fine di una linea: i due elementi della linea che occupano
la minima e massima riga rispettivamente;
loop: una sequenza di linee consecutive nella quale anche il primo e l’ultimo
elemento sono consecutivi (loop = linea in un toro).
Strutture periodiche
ESEMPIO: MATRICI CON PERIODICITÀ (1,2)
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.
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.
Strutture periodiche: risultati
RISULTATI PRINCIPALI
Formalizzazione della teoria degli switches.
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.
Strutture periodiche:
algoritmo di ricostruzione
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 una classe di
poliomini convessi su una superficie toroidale a partire dalla conoscenza parziale
delle sue proiezioni orizzontali e verticali.
Strutture periodiche:
algoritmo di ricostruzione
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).
Una soluzione di I’ conduce ad una soluzione per Ricostruzione (’ , )
con input H’ e V’.
Passo 4 - passaggio alla soluzione del problema Ricostruzione ( , ) con
input H’ e V’.
Passo 5 - fusione della soluzione trovata con la matrice F per ottenere la soluzione
finale A. Tale procedura necessita di una variante dell’algoritmo di Ryser per la
ricostruzione di una matrice binaria da due proiezioni.
N.B. qualora la periodicità ecceda le dimensioni della matrice,
l’algoritmo precedente si riduce al solo algoritmo di Ryser.
Strutture periodiche:
dettagli sul passo 2, esempio
CORRISPONDENZA
MATRICE PERIODICA - POLIOMINO CONVESSO
0
0
0
M: 1
0
0
1
0
1
0
0
0
1
0
11
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.
Strutture periodiche:
dettagli sul passo 2, esempio
Il poliomino P:
 è convesso su un toro;
 ha le stesse proiezioni verticali di M;
 ciascuna proiezione orizzontale ha valore 3 o 4;
 su ciascuna colonna possono essere presenti al più una barra di
lunghezza 4 ed una barra di lunghezza 3 contemporaneamente.
Questi vincoli possono essere imposti tramite una formula
booleana in 2-SAT.
La trasformazione può essere facilmente invertita.
Ricostruzione di strutture periodiche:
esempio
Input: i due vettori H = (3, 3, 5, 2, 4, 5, 3, 4) e V = (4, 3, 4, 3, 3, 3, 4, 1, 1, 3).
Output: una matrice A con periodicità (1,3) e consistente con H e V.
Passo 1
- ricostruzione della parte fissa di A;
- creazione dei vettori H’ e V’.
H’ = (2, 3, 5, 2, 3, 5, 2, 3)
V’ = (2, 2, 4, 3, 3, 3, 4, 1, 1, 2).
3
3
5
2
4
5
3
4
0
0
0
0
10
0
10
0
0
0
0
0
0
0
0
01
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
01
0
0
0
0
0
0
0
Ricostruzione di strutture periodiche:
un esempio
Passi 2 e 3 - creazione di una istanza I’ del problema di ricostruzione di una classe
di poliomini convessi su di un toro dalla conoscenza parziale delle
proiezioni orizzontali e verticali:
• V’ = (2, 2, 4, 3, 3, 3, 4, 1, 1, 2)
• le proiezioni orizzontali possono
assumere i valori 2 o 3.
• al più due barre di lunghezza 2 ed una
di lunghezza 3 possono essere presenti
in una stessa colonna del poliomino.
- caratterizzazione del problema tramite una formula in 2-SAT e sua
soluzione.
Ricostruzione di strutture periodiche:
un esempio
Passi 4 e 5 - passaggio alla soluzione del problema Ricostruzione ( , ) con
input H’ e V’ e fusione della soluzione trovata con la parte fissa della
soluzione A ottenuta nel passo 1.
2 2 4 3 3 3 4 1 1 2
4 3 4 3 3 3 4 1 1 3
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
A:
0
1
1
0
0
0
0
1
1
0
1
0
1
1
0
0
0
0
0
1
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
3
3
5
2
4
5
3
4