Il problema dell’allineamento delle scansioni

Il processo di ricostruzione stereo presentato permette di generare più immagini dell'oggetto bersaglio. I metodi per ottenere queste immagini si basano sui modelli e sugli strumenti precedentemente descritti (4 microcamere per riprendere la scena e fonte di illuminazione artificiale).

A questo punto può risultare necessario combinare le varie nubi di punti in un'unica rappresentazione. Per far ciò bisogna ricostruire la forma dell'oggetto partendo dalle singole immagini; infatti ogni volta che viene acquisita una porzione di superficie si ottengono coordinate tridimensionali note per ogni punto, ma, mutando la posizione del riferimento (in questo caso delle telecamere), il sistema roto-trasla rigidamente in una posizione incognita e la nuova nube viene determinata a partire da tale posizione.

Per ottenere una nube unica, allora, è necessario allineare le varie immagini. Il processo di allineamento può essere affrontato con tecniche differenti (registrazioni multivista, zone di sovrapposizione, ricerca delle corrispondenze,ecc..) Principalmente in questo lavoro saranno distinti:

 Allineamenti  Registrazioni

I primi consistono nella determinazione pura e semplice delle matrici di roto-traslazione da applicare alle nubi sparse ottenendo un allineamento uniforme. Questi sistemi sono rapidi e in genere vengono utilizzati per un primo accostamento delle parti o per riallineamenti di oggetti non in contatto. I secondi (registrazioni) sono metodi più complessi ma sicuramente più precisi, che ottimizzano le corrispondenze fra i punti di sovrapposizione di due nubi (parzialmente allineate o con zone di sovrapposizione).

Da questo si può capire come, per una completa fusione delle varie parti in un modello preciso, sia necessario eseguire prima un allineamento dei punti con tecniche di trasformazione rigida dei sistemi e poi, se necessario, registrare le nubi così ottenute con sistemi più raffinati.

Nei paragrafi successivi saranno valutati alcuni metodi per la registrazione fine di nubi parzialmente allineate e sarà descritto il metodo di ottimizzazione ai minimi quadrati, utilizzato per risolvere sia il problema della triangolazione stereo (vedi capitolo 4), sia il problema della registrazione.

3.13.1 Registrazione

La ricostruzione di due nubi di punti avviene, come detto, in due parti: la prima stima la trasformazione fra i due sistemi di riferimento e la seconda raffina i dati ottenuti. In generale i metodi di allineamento di primo tentativo sono molto approssimativi e riguardano un piccolo numero di punti specifici (angoli, spigoli o superfici di appoggio), mentre nella fase di registrazione vera e propria si utilizzano moltissimi punti, attraverso metodi di calcolo iterativi che sfruttano modelli di ottimizzazione non lineare.

Il modello di calcolo più noto e quello chiamato ICP (Iterative Closest Point) [16] che, come si intuisce dal nome, ricerca le minime distanze fra le coppie di punti appartenenti a due distinti gruppi, calcola le trasformazioni per portare un punto su un'altro e ricomincia con una nuova coppia di punti, fino all'ottenimento della convergenza. Il procedimento si basa su modelli statistico-geometrici quali il calcolo delle minime distanze e risoluzione di sistemi sovra-determinati.

3.13.2 Matematica della registrazione

La distanza fra due punti di coordinate       ) , , ( ) , , ( 2 2 2 2 1 1 1 1 z y x r z y x r è data da: 2 1 2 2 1 2 2 1 2 2 1 r (x x ) (y y ) (z z ) r d         3.36

Per ottenere, invece, la minima distanza fra un set di punti e un punto p, è necessario imporre:

) , min(p a_j d 

dove p è il punto del 1° set (mobile) ed aj è un' elemento del secondo set (fisso). Lo stesso

ragionamento vale considerando come set di punti un'entità parametrica E (curva 0 superficie)

) , min(p E

Figura 3.32: Parametrizzazione di una superficie in triangoli

Se E viene divisa in parti discrete (triangoli di figura 3.32 in caso di superfici 0 polilinee in caso di curve) si ottiene una nuova formulazione per la (3.36). Dette (u,v) le coordinate dei vertici del singolo triangolo, nel caso di superficie, si può determinare ua che minimizza la distanza fra l'entità e il punto p. Questo problema può, quindi, essere risolto con il metodo di minimizzazione di Gauss-Newton, avendo a disposizione un valore di ua parametrico come punto di partenza

2 ) ( ) (u r u p f  

dove r e un elemento dell'entità E di coordinate (u,v). ua operatore gradiente, cioè:

0



f

valida quando f è minima. Attraverso alcuni passaggi si giunge alla formulazione del valore di u





1 k t k k

k u f u f u

u      

L'espressione sopra riportata può quindi essere iterata fino a raggiungere il valore di convergenza.

Se l'entità non è parametrica il problema si complica, infatti non è più possibile definire la

a

u come prima e quindi diventa necessario minimizzare la funzione obiettivo con vincoli

non lineari, ancora della forma:

2 )

(r r p

f   _3.37 attraverso soluzioni numeriche.

Con questo procedimento sono state calcolate le corrispondenze fra i punti dei due set che hanno minima distanza fra loro ( in effetti la distanza, in teoria, è portata ad un valore prossimo allo 0). Il passo successivo è il calcolo delle trasformazioni da applicare ai punti per ottenere la loro sovrapposizione; si schematizza, quindi, la (3.37) con la seguente:



 pi = elemento del set di partenza P  xi = elemento del set di arrivo X  Np = numero di punti dei due set

 R = matrice di rotazione (3x3)  T =vettore di traslazione (3xNp)

La cui soluzione viene implementata utilizzando metodi di decomposizione del valor singolo o SVD o con altri algoritmi [37].

3.13.3 Algoritmo iterativo

Grazie alle metodologie descritte nel paragrafo precedente è ora possibile determinare le distanze fra due insiemi (o set) di punti e le trasformazioni necessarie per minimizzarle. Eseguendo una serie di passi è possibile, quindi, implementare la seguente procedura:

 Dati P (con Np punti pi ) e X (con Nx punti xi ) come valori noti  Si Inizializza il problema con: P0=P, traslazione nulla e rotazione unitaria

 Si eseguono i calcoli :

 Calcolo della minima distanza

 Calcolo delle matrici di rototraslazione

 Applicazione delle suddetta al set P ottenendo Pi + Ì

 Ripetizione dei punti 1-2-3 fino a che l'errore calcolato non sia sotto una determinata soglia

Tale algoritmo converge sempre monotonicamente, come dimostrato da [38]. Questo modello, come illustrato in figura 3.33, può generare errori anche elevati, in presenza di non perfette corrispondenze, o può dover richiedere un tempo di calcolo eccessivo. Per migliorare le prestazioni dell' ICP, sono state, quindi, introdotte numerose varianti:

 L’algoritmo accelerato [37], che prevede il calcolo del vettore differenza, generando una direzione di registrazione

 Algoritmi che migliorano la ricerca delle corrispondenze con l’uso di superfici approssimate, parametriche o formate da triangoli [38], [39], [40] e [41]

 Algoritmi che valutano particolari soglie di distanza oltre le quali la corrispondenza è considerata errata [42], [43], [39] e [40]

 Sistemi di “sampling” di set [41] [42] o metodi che usano ottimizzazioni più raffinate [42] e [44]

 Sistemi basati su meccaniche di richiamo tipo molle nel calcolo incrementale [45] Senza contare metodi che registrano contemporaneamente più viste e algoritmi basati su metodologie differenti. Tutti questi sistemi, però, hanno il grosso svantaggio di richiedere, per poter risultare efficaci, una parziale sovrapposizione delle nubi da allineare. Infatti il calcolo della minima distanza, soprattutto in presenza di valori di soglia, deve necessariamente essere contenuto. Questo significa che, qualunque algoritmo sarà impiegato, occorrerà provvedere ad un primo riallineamento.

Molto spesso questo tipo di lavoro è svolto in maniera manuale o poco precisa, concentrando tutta l'attenzione sulla registrazione. Nei capitoli successivi, sarà proposto un sistema di allineamento di nubi sparse, al fine di allineare in maniera definitiva, o con piccoli interventi di registrazione, le acquisizioni effettuate.

Nel successivo paragrafo, invece, sarà valutato il problema matematico, trattato nel suo insieme. Lo scopo è fornire uno strumento che possa esser utilizzato, in maniera semplice ed efficacie, per l'allineamento delle nubi.