L’allineamento di nuvole di punt

In passato, soprattutto nell’area della Computer Vi- sion, notevoli sforzi sono stati fatti riguardo la temati- ca della registrazione di nuvole tridimensionali di pun- ti. Uno dei metodi più popolari, tuttora implementato nella maggior parte dei software commerciali che si occupano della gestione ed elaborazione di dati 3D, è l’algoritmo Iterative Closest Point (ICP), sviluppa- to da Besl e McKay, che sono considerati i pionieri della registrazione, in quanto sono riusciti a tradurre in modo formale l’allineamento di superfici [Besl & McKay, 1992]; il principio di funzionamento del pri- mo algoritmo è stato poi variato e sviluppato, anche da numerosi altri autori, nel corso degli anni.

L’algoritmo ICP applica in modo iterativo una roto- traslazione rigida nello spazio ad una delle due nuvole, considerata mobile, affinché si sovrapponga nel mi-

glior modo possibile all’altra nuvola, considerata fissa. Il metodo è un cosiddetto punto-punto, che si contrap- pone al metodo punto-piano sviluppato da Chen e Me- dioni [Chen & Medioni, 1992]. In entrambi i metodi adottati, la registrazione avviene tramite la ricerca del minimo di una funzione obiettivo.

Nel primo metodo (metodo punto-punto) questa fun- zione è data dalla somma dei quadrati delle distanze dei punti corrispondenti delle nuvole. I punti corri- spondenti si definiscono come la coppia formata da un punto di una nuvola e quello più vicino appartenente alla nuvola opposta. Nel secondo metodo (punto-pia- no), pur rimanendo la stessa struttura della funzione obiettivo, sono da minimizzare però le distanze tra i punti di una nuvola ed i piani di best-fit passanti per i punti dell’altra.

L’algoritmo procede in questo modo: date due super- fici P e Q da allineare, si considera un punto di P indi- cato con p, e si cerca un punto particolare di Q, detto punto corrispondente q, che coincide con il punto più vicino (punto a distanza minima); in pratica per ogni punto della nuvola mobile vengono ricercati, all’inter- no della nuvola fissa, i punti contenuti all’interno di una sfera di un certo raggio (multiplo di un parametro introdotto dall’utente) e di questi viene tenuto il più vicino, che sarà considerato il punto corrispondente. Questo avviene formalmente definendo un operatore “punto più vicino” (Closest Point Operator) C, fatto questo per tutti i punti della nuvola mobile e sommati i quadrati delle distanze relative, si ottiene il valore che sarà poi quello da minimizzare muovendo con delle rototraslazioni rigide la nuvola che si è scelta mobile. Si nota come in una procedura di ricerca così fatta, vengano escluse automaticamente tutte le coppie di punti corrispondenti che risultano avere una distanza superiore al valore del raggio della sfera da noi de- finita. Questo valore deriva da un parametro inserito dall’operatore, dal quale dipenderà anche l’esito del- la registrazione. Tale parametro in letteratura è con- venzionalmente stimato come il doppio della distanza media dei punti di una nuvola, tuttavia in caso di forti disallineamenti dovrà essere convenientemente au- mentato.

Naturalmente dopo un primo tentativo di minimizza- zione delle distanze dei punti corrispondenti, sarà mol- to improbabile che la registrazione sia andata a buon fine, infatti molte coppie di punti che si sono formate, risulteranno essere solo “fittizie” e non porteranno ver- so un vero allineamento.

Saranno necessarie quindi più iterazioni, all’interno delle quali ripetere le operazioni di ricerca dei pun- ti corrispondenti e di minimizzazione delle distanze. La convergenza dell’intero processo si avrà quando la variazione della matrice di rototraslazione tra due ite- razioni successive è minore di una certa percentuale (generalmente quando la differenza delle ultime due traslazioni e rotazioni è contemporaneamente minore dell’1%).

Le coppie di punti corrispondenti che si sono formate

Due immagini della fase di registrazione di tre scansioni, con la terna di target in comune e l’errore presente del target nella coppia di scansioni.

sono quelle all’interno della zona di sovrapposizione e in questo modo sono automaticamente esclusi tutti quei punti delle nuvole che non devono prendere parte al processo (punti di rumore o più generalmente fuori dalla zona di sovrapposizione).

Nel metodo di registrazione con minimizzazione delle distanze con metodo punto-piano, ad ogni punto del- la nuvola mobile viene associato un certo numero di punti dell’altra nuvola ottenuti scegliendoli tra quelli più vicini alla normale uscente dal punto della nuvo- la mobile. Questi punti vengono utilizzati per fare un best-fit, ossia trovare un piano che li approssima (col metodo dei minimi quadrati). Ogni punto della nuvola mobile si troverà così associato ad un piano sulla nu- vola fissa; la funzione obiettivo in questo caso è mini- mizzare la somma dei quadrati delle distanze punto- piano di tutti i punti della nuvola mobile.

A parte il diverso modo di intendere la funzione obiet- tivo, la struttura dell’algoritmo rimane essenzialmen-

te la stessa di quella del metodo punto-punto. Questo metodo permette una convergenza con un numero di iterazioni di un ordine di grandezza minore, grazie al fatto che possiamo muoverci su un piano (quindi su due dimensioni) per trovare il minimo della funzione. Sebbene il processo di best-fit dei piani risulti piutto- sto oneroso dal punto di vista computazionale, il meto- do punto-piano resta più veloce e più preciso di quello punto-punto.

L’algoritmo ICP originale è pairwase based, cioè l’al- lineamento avviene per due sole nuvole per volta; i software commerciali (ad esempio PolyWorks, Innov- metric; Geomagic Studio, Geomagic Inc.; RapidForm, INUS Technology) permettono di eseguire, dopo una prima fase di allineamento delle nuvole a due a due in cui ogni nuvola viene allineata con l’ultima ottenuta, un allineamento globale di tutte le nuvole insieme, allo scopo di ridistribuire e quindi minimizzare l’errore re- siduo di registrazione fra tutte le scansioni.