Capitolo 4
Registrazione multipla
4.1 Stato dell’arte e problematiche
Quando abbiamo a che fare con oggetti che richiedono diverse scansioni (in particolare più di due) dobbiamo affrontare il problema della registrazione multipla. Una buona registrazione multipla dovrebbe sovrapporre le nuvole di punti senza creare spessori troppo grandi o separarle nettamente tra loro in una zona di sovrapposizione.
Un primo approccio alla registrazione multipla è quello di tipo sequenziale, cioè registrare le nuvole muovendone una alla volta, tenendo ferma la parte che è già stata processata, e muovendo la nuvola corrente. Questo tipo di approccio però può condurre a problemi tipo quello mostrato in figura 1.
Figura 1 - (a) Oggetto originale (b) Posizioni iniziali delle nuvole (c) Errore nella registrazione sequenziale
L’errore di registrazione, in questo caso, seppure resti piccolo tra due nuvole adiacenti, si accumula per tutto il perimetro dell’oggetto fino a diventare notevole alle due estremità.
Un altro tipo di problema può sorgere quando molte nuvole convergono sulla stessa zona di sovrapposizione come schematizzato in figura 2.
Figura 2 - (a) Sezione di un multiscan (b) Registrazione ideale della nuova nuvola (c) Probabile risultato dopo la registrazione
L’ultima nuvola registrata tende a convergere sulla superficie più esterna formata da tutte le nuvole precedentemente allineate, in questo modo si rischia di creare uno spessore non trascurabile della superficie di scansione.
Si rende quindi necessaria una strategia per stabilire le priorità di allineamento tra le nuvole. Un rimedio semplice ed intuitivo sarebbe quello di avere una vista che abbia almeno una zona di sovrapposizione con tutte le altre e registrare queste ultime sulla vista “centrale” [7] (che rimane ferma). Purtroppo a causa della forma o delle dimensioni degli oggetti da acquisire, non è sempre possibile avere una vista che riesca a coprire una parte così considerevole di superficie, oppure, anche se lo fa, la zone di sovrapposizione possono non essere abbastanza estese da assicurare “vincoli” sufficienti per una registrazione soddisfacente.
Il principio che tuttavia possiamo fare nostro di questo approccio, è che le nuvole con grande numero di sovrapposizioni si muovano il meno possibile, al fine di mantenere un riferimento più sicuro riguardo alla forma dell’oggetto.
L’obiettivo che intendiamo conseguire per ottenere una buon risultato inoltre, consiste nel
distribuire il più equamente possibile l’errore di registrazione su tutte le zone di sovrapposizione, in modo da non avere discontinuità visibili sulla superficie dell’oggetto dopo il processo di
allineamento.
L’idea che abbiamo seguito [8], è stata quella di eseguire la registrazione di ogni coppia di viste che abbiano sovrapposizione tra loro, indipendentemente dalle altre, e immagazzinare i dati provenienti da questi allineamenti ottimali per poi riutilizzarli durante il processo di registrazione multiplo. In pratica, per ogni coppia di nuvole registrata, conserviamo le coordinate dei punti nelle posizioni relative dopo la registrazione a coppie, di questi dati viene conservata solo una parte per permettere un processo di allineamento multiplo più veloce (ad es. se ne trattiene solo una percentuale del totale).
In questo modo il processo di ottimizzazione si svolge non tra punti di due nuvole diverse, ma sono minimizzate le distanze tra gli stessi punti aventi le coordinate della posizione corrente e di quelle di
dove dovrebbero andare se la registrazione risultasse ottimale (così come ottenute dalla registrazione a coppie, si l’esempio in figura 3).
nuvola 1
nuvola 2
Figura 3 – Registrazione mediante coppie virtuali. In tratteggio fine è indicata la posizione ideale della nuvola 2 rispetto alla nuvola 1, mentre le connessioni rappresentano le coppie virtuali che si sono formate durante la registrazione a coppie e le cui distanze vanno minimizzate. Si noti che i punti delle coppie contenuti nel rettangolo tratteggiato si muovono solidalmente alla nuvola 1.
Il vantaggio di questo tipo di metodologia è essenzialmente di carattere computazionale, infatti una volta che abbiamo immagazzinato tutti i dati relativi alle registrazioni a coppie, il processo di minimizzazione globale delle distanze è avviato con un numero ridotto di punti rispetto alle originali zone di sovrapposizione (viene fatta una semplice operazione di riduzione casuale dei punti).Così facendo evitiamo ogni volta di tenere in memoria tutti i punti delle nuvole durante la minimizzazione, risparmiando così la RAM del computer per i calcoli.
Tuttavia questo approccio introduce anche un altro vantaggio che concerne la precisione dei riallineamenti tra le nuvole. Nel caso infatti di un algoritmo che abbia come funzione obiettivo la minimizzazione dei punti effettivi appartenenti alle nuvole, la soluzione ai minimi quadrati è fortemente influenzata dalla coppia di scansioni con la registrazione peggiore. Anche un lieve disallineamento infatti, aumenterà maggiormente la somma dei quadrati delle distanze di punti corrispondenti più lontani piuttosto che i punti più vicini.
La coppie di nuvole con le somme delle distanze dei punti più lontani (dovuta ad esempio a
maggior rumore, maggior presenza di punti, o impliciti problemi di registrazione a coppie) saranno quelle che maggiormente comanderanno il processo di minimizzazione, cercando inutilmente di migliorare una qualità di allineamento implicitamente bassa, trascurando la qualità di registrazione in altre zone di sovrapposizione.
Figura 4a – Approccio con minimizzazione dei punti effettivi
Con il metodo delle coppie virtuali (virtual mates), questo problema è risolto perché la distanza che viene minimizzata è quella dei punti delle nuvole rispetto alla loro posizione ideale sull’altra nuvola, avvicinando quindi la nuvola più che all’altra, alla sua posizione ottimale di registrazione pairwise.
Figura 4b – Approccio con minimizzazione delle coppie virtuali
Al fine di ottenere una minimizzazione “bilanciata”, si è scelto di conservare lo stesso numero di punti corrispondenti durante l’operazione di sampling, su tutte le zone di sovrapposizione,
diversamente avrebbero potuto avere un “peso” maggiore le zone che contenti maggior quantità di punti.
4.2 Descrizione dell’algoritmo
L’algoritmo di registrazione funziona come segue: all’inizio vengono calcolate a due a due tutte le registrazioni relative delle nuvole che hanno sovrapposizione, al termine di ogni registrazione a coppie, si esegue una procedura di ricerca per la creazione di coppie di punti (appartenenti uno ad una nuvola ed uno all’altra), se si trova un numero sufficiente di coppie di punti con distanza all’interno di un certo range, si esegue una riduzione delle coppie e si procede
I dati trattenuti dopo le registrazioni a coppie sono: le posizioni di allineamento ottimale dei punti di una nuvola rispetto all’altra (facenti parte delle coppie trattenute dopo la riduzione), la posizione originale degli stessi punti prima della registrazione. I primi verranno vincolati alla nuvola fissa per indicare la posizione ottimale di quella mobile, i secondi saranno solidali alla nuvola in movimento e verranno usati per indicare la posizione corrente della nuvola da registrare. Durante il processo di allineamento multiplo saranno minimizzate le distanze di queste due strutture di punti.
Il processo di allineamento multiplo funziona dividendo le nuvole in due “set”. Uno è mantenuto consistentemente allineato (set attivo o active_set), l’altro contiene le nuvole nella loro posizione originale (set dormiente o dormant_set). All’inizio tutte le nuvole sono contenute nel set dormiente e vengono trasferite nel set attivo una per volta.
Ad ogni passo dell’algoritmo, viene selezionata la nuvola del dormant_set con maggior numero di sovrapposizioni con quelle del set attivo. Successivamente viene inserita in una coda di nuvole “mobili”. La coda viene processata finché non rimane vuota dopo aver allineato la nuvole al suo interno con quelle del set attivo e fondendo le nuvole vicine nuovamente all’interno della coda. Un diagramma di flusso dell’algoritmo riguardante solo la parte di allineamento multiplo è rappresentato in figura 6.
La parte dell’allineamento avviene con l’utilizzo dei dati immagazzinati dalle precedenti registrazioni a coppie. Ovviamente la nuvola di partenza è quella con maggior numero di sovrapposizioni all’interno del set dormiente.
Un importante caratteristica di questo algoritmo, è che le nuvole vengono aggiunte una alla volta al set attivo, evitando in questo modo di applicare contemporaneamente a tutte il processo di
minimizzazione con il rischio di ottenere la convergenza verso una configurazione di minimo locale, dovuta ad una particolare situazione di disallineamento iniziale (figura 5).
LE NUVOLE
VICINE SONO
+ DI UNA?
TRASFERISCE IN ACTIVE_SET DA DORMANT_SET LA
NUVOLA CON PIU’
SOVRAPPOSIZIONI (NUVOLA
CORRENTE) CON ACTIVE_SET
INSERISCE IN CODA LA
NUVOLA CORRENTE
INDIVIDUA LE NUVOLE VICINE ALLA NUVOLA CORRENTE NELL’ACTIVE_SET
ALLINEA LA NUVOLA CORRENTE CON LE VICINE
TOGLIE DALLA CODA LA
NUVOLA CORRENTE CODA VUOTA? DORMANT_ SET VUOTO?
UNISCE (SOLO NELLA
CODA) LE NUVOLE VICINE IN NUVOLA CORRENTE FINE ESTRAE L’ULTIMO ELEMENTO DALLA CODA E LA ASSEGNA COME NUVOLA CORRENTE SI NO NO SI SI NO
Figura 6 - Diagramma di flusso della parte di allineamento multiplo dell’algoritmo
Per quanto riguarda la registrazione a coppie, computata a due a due separatamente dalle altre per tutte le nuvole che presentano una zona di sovrapposizione in comune, si preferisce eseguire il calcolo all’inizio del procedimento. In questo modo quando inizia il processo di allineamento multiplo sono già disponibili tutte le posizioni ottimali relative tra le nuvole presenti in una struttura che comprende:
• I punti originali della nuvola
• Una parte dei punti originali che sono presi in considerazione per eseguire la registrazione sulle nuvole vicine
• Le coordinate di posizionamento ottimale delle nuvole vicine (ossia aventi zona di sovrapposizione con la nuvola presa in considerazione), che saranno associate, in fase di allineamento, ai punti scelti per la registrazione di queste ultime.
Tutte e tre queste strutture di punti si muovono solidalmente con la nuvola ad esse associata, quando quest’ultima viene movimentata per la registrazione, anche se dobbiamo sottolineare che i punti che prendono parte al processo di registrazione multipla sono soltanto quelli delle coppie virtuali.
Gli allineamenti a coppie iniziali vengono fatti con il metodo punto-piano utilizzando tutti punti delle nuvole (o facendo solamente un sampling in curvatura), mentre per la parte di allineamento multiplo si utilizza inizialmente il metodo punto-punto tra le coppie virtuali formatesi tra le zone di sovrapposizione e successivamente il metodo punto-piano con sempre gli stessi punti virtuali. Questo perché avendo meno punti a disposizione durante il processo di registrazione multipla ( e quindi minori “caratteristiche” di forma), il metodo punto-piano potrebbe portare ad eccessivi scorrimenti relativi delle nuvole, dovuti anche al fatto che spesso le zone di sovrapposizione possono non essere abbastanza estese per assicurare i vincoli necessari ad un corretto
posizionamento.
Quindi, dopo un primo avvicinamento delle nuvole fatto col metodo punto-punto per scongiurare eccessivi scorrimenti, si rifinisce la registrazione col metodo punto-piano che risulta essere più preciso e performante. Abbiamo verificato infatti come il metodo punto-punto da solo non guida ad una corretta configurazione finale, proprio per le intrinseche difficoltà di movimentazione di cui facevamo menzione nelle considerazioni al capitolo precedente.
4.3 Risultati
Figura 7 – Particolare di un motore scannerizzato con 5 acquisizioni prima e dopo registrazione multipla
In figura 7 sono mostrati gli effetti dell’algoritmo di registrazione multipla sulle nuvole di un motore.
