ALGORITMO DI LAVALLEE E SZELISKI

La stima della posa, locazione e orientamento, dell’oggetto 3D con rispetto alla scena descritta dai dati ottenuti (immagini 2D o dati 3D) è il classico problema nella visione del modello base.

Formalmente, si definisce l’oggetto in un sistema di coordinate 𝑅𝑒𝑓_!! e i dati del sensore come contorni di immagine 2D in un sistema di coordinate 𝑅𝑒𝑓_!"#!$%, si stimano le sei componenti del vettore p che definisce la trasformazione T(p) del corpo rigido tra 𝑅𝑒𝑓_!! e 𝑅𝑒𝑓_!"#!$%. Quando si usano contorni 2D, sebbene questo problema possa in teoria essere risolto per una proiezione singola, in pratica due o più proiezioni sono necessarie per ottenere una stima sufficientemente accurata.

Questo metodo è stato pensato per essere utilizzato in operazioni chirurgiche come procedura di simulazione dell’intervento e perciò sono stati curati in particolare gli aspetti di velocità di calcolo, accuratezza e arbitrarietà della forma dell’oggetto.

Quest’algoritmo si basa sulla condizione di tangenza tra la superficie del modello 3D e i raggi di proiezione che generano i contorni esterni dell’oggetto nell’immagine. La tecnica può lavorare anche con contorni incompleti.

Il problema è di stimare la trasformazione T tra 𝑅𝑒𝑓_!"#!$% e 𝑅𝑒𝑓_!!, T è chiamata posa finale dell’oggetto e può essere definita da un vettore di traslazione e da una matrice di rotazione 3 x 3.

In breve il fluoroscopio è virtualmente modellato con un modello di proiezione prospettiva e la stima della posa 3D è ottenuta con una procedura iterativa che trova il miglior allineamento tra la superficie del modello osseo e le sue proiezioni fluoroscopiche 2D (generalmente immagini DICOM 1024 x 1024).

La qualità dell’allineamento è rappresentato dalla funzione costo definita come :

RMSD(p)= [! !! ! ,!! ]!

! !!!

RMSD è il valore efficacie della distanza tra la superficie 𝑆_!(𝑝) del modello m posizionato nella posa p=( 𝑇_!, 𝑇_!, 𝑇_!, 𝜃_!, 𝜃_!, 𝜃_!) e n proiezioni delle linee l. La proiezione delle linee l rappresenta i raggi X generati dai punti del bordo del segmento osseo estratto dal filtro di Canny nell’immagine fluoroscopica.

Per quantificare l’RMSD vengono campionate le linee 𝑙_! e, per ogni punto di campionatura, si stima la distanza da 𝑆_! 𝑝 .

La distanza della linea di proiezione dalla superficie è definita come la minima distanza tra 𝑆_!(𝑝) e i punti campionati:

d(𝑆_! 𝑝 , 𝑙_!) = min_![𝑑(𝑆_! 𝑝 , 𝑃_!!)]

Il miglior allineamento è infine identificato trovando i valori della posa p che minimizzano l’RMSD con un algoritmo di ottimizzazione:

𝑅𝑀𝑆𝐷_!"# =   min

! [𝑅𝑀𝑆𝐷 𝑝 ]

Per velocizzare il processo, si pre-computa una mappa di distanza 3D. Per migliorare lo spazio di memoria, l’accuratezza, la velocità computazionale e quella di costruzione, è stata sviluppata una mappa di distanza chiamata “octree spline” come DMR (Distance Map Resolution). L’idea è quella di ottenere maggior dettagli e pertanto maggior accuratezza vicino alla superficie piuttosto che lontano da questa.

Si possono usare diverse rappresentazioni della superficie ossea (nuvole di punti, triangoli ecc), in questa implementazione è stata utilizzata una rappresentazione a triangoli o mesh.

In breve:

1. Si costruisce l’octree associato con una serie di punti 𝑠_!. Partendo dal cubo iniziale V, ogni nodo che contiene punti (nodi grigi) è ricorsivamente suddiviso in otto sottocubi fino a che non contengono punti (nodi bianchi) o che si ha la massima suddivisione (nodi neri). Per ogni applicazione, l’octree tipicamente ha dai sei ai nove livelli corrispondenti ad una risoluzione dai 64 ai 512 cubi su lato.

2. L’octree precedentemente costruito potrebbe avere nodi vuoti vicino alla superficie perché non sono state introdotte regole circa la suddivisione vicino ad essa. Perciò si crea un’ulteriore suddivisione dell’octree per garantire che due nodi vicini lungo una faccia, contorno o angolo differiscano in dimensione da un fattore 𝑘_!=2.

La procedura di generazione impone una struttura gerarchica in quanto ogni cubo di un dato livello, eccetto il cupo capostipite, deriva dalla suddivisione di un cubo del livello immediatamente superiore. Si utilizza perciò una rappresentazione ad albero in cui i cubi Grigi costituiscono i nodi mentre quelli Bianchi o Neri le foglie. In questa rappresentazione, il volume esterno ed interno della superficie dell’oggetto non è uniformemente discretizzato. La mappa assegna ad ogni punto di discretizzazione la corrispondente distanza dalla superficie del modello che avrà segno positivo se fuori da essa o segno negativo se all’interno.

La distanza con segno (d) tra un generico raggio e S può essere calcolata velocemente utilizzando la mappa di distanza. Si discretizza pertanto il raggio in un insieme finito di punti scelti cercando le intersezioni tra il raggio ed i cubi del reticolo e si sfrutta la gerarchia della struttura ad albero, tenendo conto che se il raggio bon interseca un determinato cubo allora non interseca nemmeno quelli interni ad esso. Si valutano perciò solo i rami della mappa che rappresentano volumi attraversati dal raggio.

La distanza è rappresentata come la minima distanza tra il punto di discretizzazione e la superficie del modello osseo.

La mappa di distanza considerata è una mappa di distanza adattativa ossia costituita da un reticolo a passo variabile, minimo a

ridosso della superficie e crescente con la distanza assoluta, diradandosi sia all’interno che all’esterno dell’oggetto.

Si costruisce un reticolo di punti a passo variabile in modo da avere informazioni sempre più dettagliate via via che ci si avvicina alla superficie S.

Se  𝑠_!!è il lato dell’octant più piccolo contenente il punto campionato 𝑃_!! il prossimo punto per la stima della distanza sarà:

𝑃_!!!! =𝑙_! 𝜆_!!! ; 𝜆_!!! = 𝜆_! +  𝑠_!! 2

Tale procedura permette di passare attraverso tutti i cubi

intersecati, visto che due cubi hanno solo un livello di discontinuità per costruzione.

Infine 𝑙_! è ricalcolato nei punti più vicini alla superficie con un passo uniforme di lunghezza più piccola di dieci volte rispetto alla

precedente.

Figura 1-11: Schema della proiezione dei raggi nella procedura di campionatura. L’octree è suddiviso per iterazione solo se contenente un punto della superficie del modello.