Correspondence Estimation

La Correspondence Estimation è il processo che accoppia ogni punto pi apparte-

nente alla nuvola P con un rispettivo punto qj appartenente alla nuvola Q. Una

corrispondenza sarà definita da una coppia di indici (i, j) che indicano una cop- pia di punti (pi, qj). Il metodo più utilizzato per il calcolo delle corrispondenze è

quello di portare a termine una ricerca esaustiva attraverso tutti i punti di Q del punto più vicino ad ogni singolo punto di P . Questo algoritmo però è computa- zionalmente dispendioso se la nuvola è formata da molti punti. Per questo sono state implementate strutture per la ricerca rapida chiamate kd-tree [30] e octree [31].

K-d tree

Il k-d tree, in figura 3.7, è una struttura di dati usata per organizzare un certo numero di punti in uno spazio k-dimensionale che, per il nostro scopo, cioè la ricerca di punti in una nuvola, verrà trattata nel caso tridimensionale. Si può pensare al k-d tree come a un albero binario in cui ogni livello divide i punti

(a) Nuvola di punti in ingresso.

(b) Nuvola con campionamento Uniforme, Voxelgrid.

(c) Nuvola con campionamento Random.

(d) Nuvola campionate con Normal Space Sampling.

(e) Nuvola campionata con Covariance Sampling

Figura 3.6: Confronto tra metodi di campionamento.

lungo un piano allineato agli assi. Nel caso in cui k > 3 la divisione è effettuata tramite un iperpiano.

Il piano scelto per la divisione è la mediana dei punti del sottoalbero rispetto alle coordinate sull’asse per generare il piano separatore. Questo equivale a ordina-

re i punti in ordine crescente rispetto alla coordinata scelta, e posizionare la metà inferiore dei punti nel sottoalbero di sinistra e la metà superiore nel sottoalbero di destra. Avendo scelto la mediana, i due sottoalberi conterranno esattamente lo stesso numero di punti, garantendo che l’albero finale sia bilanciato, cioè con foglie a circa la stessa profondità. Un albero bilanciato garantisce una profondità logaritmica e quindi anche tempi per l’attraversamento logaritmici. Detto n il nu- mero di punti della nuvola, il carico computazionale del k-d tree è O(n log n). (→ KdT ree)

(a) (b)

Figura 3.7: Esempi di K-d tree: bidimensionale (a) e tridimensionale (b).

Octrees

L’octree, in figura 3.8, è utilizzato per organizzare un certo numero di punti conte- nuti in uno spazio 3-dimensionale. L’octree è costituito da un albero binario i cui nodi rappresentano un cubo. Lo spazio di ogni nodo può essere diviso in otto cubi equivalenti, tramite dei piani paralleli agli assi x, y e z passanti per il centro del cubo stesso. Anche in questo caso la struttura di ricerca dei vicini si limita allora ad una ricerca in un albero binario. Esistono due metodi principali per costruire un octree:

1. Capacità limitata: ogni nodo può contenere al più un numero massimo di punti. Se quindi in un nodo vi sono più punti di quanto permetta il valore soglia questo viene diviso in otto cubi, nella modalità già descritta. In questo modo le foglie contengono un numero di punti inferiore al valore prefissato, ma non si ha garanzia sulla profondità della struttura ad albero dell’octree. 2. Dimensione limitata: ogni nodo interno non può avere il lato più piccolo di

fissato o non contiene punti, altrimenti si procede ricorsivamente. Questa strategia è quella implementata nelle PCL.

Anche se il tempo per formare un octree è inferiore rispetto al k-d tree, gra- zie alla strategia triviale di creazione, la struttura non risulta bilanciata, la sua profondità infatti varia a seconda della distribuzione dei punti nella nuvola.

(a) (b)

Figura 3.8: Esempio di Octree (b) e una sua rappresentazione bidimensionale (a).

Dopo aver descritto due diverse strutture per l’organizzazione dei punti e dun- que per la ricerca rapida di corrispondenze, spostiamo l’attenzione sugli algoritmi per la stima delle corrispondenze. Nelle PCL sono implementate delle funzioni diverse per effettuare la fase di correspondence estimation, le quali verranno ora presentate.

Correspondence Estimation Base

Questo algoritmo consiste nel costruire un sistema ad albero impostabile, octree o k-d tree, e cercare il punto qi appartenente alla nuvola target Q che ha distanza

minima dal punto pj della nuvola source P . (→ CorrespondenceEstimation)

Correspondence Estimation Back Projection

Dopo aver costruito un sistema ad albero, si cercano i k punti vicini qj, appar-

tenenti alla nuvola target Q, al punto pi della nuvola source P . Per ognuno di

questi punti si calcola il coseno dell’angolo θ tra la normale del punto stesso e la normale del punto in esame pi:

cos(θ) = normalx(pi) ∗ normalx(qj)

+normaly(pi) ∗ normaly(qj)

+normalz(pi) ∗ normalz(qj)

dove normalx(pi) identifica la normale in direzione dell’asse x del punto pi.

Si calcola poi la distanza tenendo conto della distanza spaziale punto-punto e della compatibilità della direzione della normale.

dist = q

(x(pi) − x(qj))2+ (y(pi) − y(qj))2+ (z(pi) − z(qj))2∗(2−(cos(θ))2

dove x(pi)è la coordinata x del punto pi in un sistema di riferimento comune

alle due nuvole di punti. Si imposta infine la corrispondenza tra pi e il punto che

ha distanza descritta minore da esso. Con questo algoritmo si tiene conto non solo della distanza euclidea ma anche della somiglianza della normale alla superficie in quei punti. (→ CorrespondenceEstimationBackP rojection)

Correspondence Estimation Normal Shooting

Anche con questo algoritmo si calcola un insieme K composto dai k punti vicini qj, appartenenti alla nuvola target Q, al punto pi della nuvola source P . Per ogni

punto di qj appartenente a K si calcola una matrice V (1 × 3) :

ptx= x(qj) − x(pi)

pty = y(qj) − y(pi)

ptz = z(qj) − z(pi)

V = (ptx, pty, ptz)

ed una matrice N(normalx(pi), normaly(pi), normalz(pi))relativa al punto

pi. Ora viene calcolata una matrice 3×1, C attraverso il prodotto vettoriale dei due

vettori precedenti, C = N × V . Infine si calcola la distanza utilizzando il valore assoluto di C e si imposta la corrispondenza tra il punto qj ∈ K, che ha distanza

da piminore, e il punto pi stesso. Grazie alla geometria lineare, si è impostata una

corrispondenza tra il punto pie il punti qj nella nuvola target che ha una distanza

perpendicolare minima alla retta che passa per il punto pi e ha direzione della

normale calcolata in esso. (→ CorrespondenceEstimationNormalShooting)

Correspondence Estimation Organized Projection

Questo algoritmo utilizza i parametri intrinseci ed estrinseci del sensore per pro- iettare la nuvola di punti source nella nuvola di punti target. É possibile trovare il

punto qj più vicino a pi, e quindi impostare la corrispondenza, tramite una sem-

plice approssimazione dovuta alla proiezione. Anche se il risultato non è preciso come nei precedenti, è molto più veloce ed evita di utilizzare strutture ad albero addizionali. Per questo metodo è necessario che la nuvola di punti target sia orga- nizzata. Una nuvola di punti organizzata ha una struttura simile ad un’immagine (o matrice), in cui i dati sono divisi in righe e colonne. In tale nuvola i vicini di un punto possono essere trovati utilizzando gli indici della struttura matriciale. (→ CorrespondenceEstimationOrganizedP rojection)

Infine si sottolinea la possibilità presente nei primi tre metodi descritti, di cal- colare le corrispondenze reciproche iterando due volte lo stesso algoritmo, scam- biando la nuvola source con la target (e viceversa) e verificando l’univocità delle corrispondenze. Questo approccio anticipa la fase della correspondence rejection poiché elimina tutte le corrispondenze i cui accoppiamenti non sono univoci, rendendo la registrazione più robusta.