Calcolo delle normali

Il calcolo delle normali `e un passaggio necessario per la maggior parte degli algoritmi di descrizione tridimensionale pi`u accurati. Le normali alla superficie sono importanti propriet`a geometriche e sono largamente usate nella computer grafica.

Solitamente `e un procedimento facile determinare una normale data una superficie geometrica: la normale in un certo punto sulla superficie `e indivi- duata dal vettore unitario perpendicolare ad essa in quel punto. Tuttavia dal momento che le scene sono rappresentate da punti e non dalle vere superfici su cui giacciono, non si pu`o applicare questo metodo ma si possono seguire due strade.

I metodi sono i seguenti:

• ottenere la superficie sottostante ai punti mediante tecniche di meshing e poi ricavare dalla mesh le normali alla superficie; una mesh `e una rappresentazione tridimensionale di oggetti mediante aree geometriche elementari;

• approssimare le normali mediante una stima direttamente eseguita sulla point cloud.

La prima strategia si rivela proibitiva per lo scopo dell’applicazione perch´e richiederebbe tempo per un’ulteriore fase di trasformazione della point cloud. La seconda invece permette di ricavare le normali stimandole dai dati punti- formi direttamente in possesso quindi non necessita di passi ulteriori, a patto di accettare l’approssimazione che ora verr`a spiegata.

Il problema di determinare la normale alla superficie in un punto pu`o essere approssimato con il problema di stimare la normale di un piano tan- gente alla superficie. Si tratta quindi di approssimare ai mimini quadrati un piano tangente. Il problema si riduce all’analisi di autovalori e autovettori di una matrice di covarianza creata mediante i punti vicini a quello di interesse. Pi`u specificatamente per ogni punto p, viene costruita la matriceC nel modo seguente: C = 1 k k X i=1 ·(p_i− p) · (p_i− p)T_,

Dove p rappresenta il centroide (o baricentro) tridimensionale del vicina- to, k `e il numero di vicini considerati intorno a p

p = 1 k k X i=1 pi

λj `e il j-esimo autovalore della matrice di covarianza e ~vj il j-esimo

autovettore su una delle tre dimensioni spaziali. C · ~vj = λj· ~vj, j ∈ {1, 2, 3}

La matrice di covarianzaC `e semi-definita positiva e simmetrica, pertanto i suoi autovalori sono reali e gli autovettori associati ortogonali fra loro. L’approssimazione della normale corrisponde all’autovettore dell’autovalore minore. Per ulteriori approfondimenti si veda la teoria sul PCA (Principal Component Analysis).

La scelta del raggio di vicinato `e fondamentale per eseguire un fitting del piano tangente alla superficie in ciascun punto. La questione `e di estrema importanza e costituisce un limite inevitabile nel procedimento automatico di stima delle normali e delle features. La selezione di un raggio ampio o basso (alternativamente di un alto o basso numero di k-neighbors) pu`o influenzare molto il risultato finale ottenuto.

Una buona stima si pu`o vedere subito visivamente quando le normali sono effettivamente perpendicolari alla porzione infinitesimale di piano su cui giacciono. Possono capitare imperfezioni su angoli e spigoli ma sono dovuti alla criticit`a della superficie in quel particolare caso.

Tuttavia se il raggio impostato o la quantit`a di vicini da analizzare sono troppo grandi e sono tali da coprire anche superfici adiacenti, la stima del- le normali viene disturbata e distorta presentando rotazioni che rendono le normali non perpendicolari alle superfici; se invece il raggio o la quantit`a di vicini sono troppo piccoli, l’algoritmo non `e in grado di eseguire un fitting di un piano realmente tangente alla superficie con conseguente miscuglio di normali in direzioni sbagliate (figura 5.6)

(a) Raggio grande 10cm produce normali ruotate verso l’alto

(b) Raggio piccolo 5mm produce normali disordinate

(c) Raggio medio 2cm produce nor- mali perpendicolari

Figura 5.6: Influenza del raggio nella stima di normali

Ovviamente queste considerazioni valgono soltanto se la qualit`a della point cloud `e sufficientemente buona da poter individuare le superfici cor- rettamente e se la nuvola `e stata ripulita bene dagli outliers. Point cloud con occlusioni o parti mancanti risulteranno sempre penalizzate, ma in quel caso la soluzione `e da ricercarsi nell’acquisizione e nelle condizioni ambientali delle scene riprese.

Tutto dipende dalle necessit`a dell’applicazione. Se per esempio `e impor- tante che si distingua il punto di congiunzione di un manico di una tazza con il contenitore, allora conviene diminuire il raggio in modo che le superfici di tazza e manico vengano rilevate come distinte. Altrimenti con un raggio

maggiore verranno privilegiati i punti sulla tazza e sul manico, rispetto alla congiunzione, perch´e pi`u regolari e pi`u rappresentativi di una superficie.

Si deve anche considerare il tempo di calcolo del centroide e della matrice di covarianza, il tutto ripetuto per ogni punto della nuvola. La cosa posi- tiva `e che diminuendo il raggio diminuisce anche il tempo di calcolo quindi `

e possibile aggiustare empiricamente il parametro in modo da trovare una configurazione che vada sufficientemente bene per il dataset da analizzare e che risponda in tempi accettabili.

I criteri per scegliere e impostare un buon raggio sono dunque l’osservazio- ne del dataset da rappresentare, l’individuazione degli scopi da raggiungere nella rappresentazione e nel suo successivo utilizzo, infine i vincoli temporali richiesti dall’applicazione.

Figura 5.7: Test eseguito sul dataset [5])

I tempi1_{mostrati in figura sono relativi all’algoritmo di stima delle norma-}

li descritto sopra e implementato da PCL in OMP (Open MutiProcessing). Il raggio `e fissato per tutte le point cloud ed `e pari a 2cm (come nel risultato di figura 5.6), una misura ragionevole e realistica per la maggior parte di oggetti nell’ambito dell’afferraggio. Le oscillazioni in figura sono dovute alla correlazione tra forma della point cloud e stima delle normali; significa che non `e solo la dimensione della point cloud a determinare il

1_{Test eseguiti su dataset [5] con CPU Intel CoreR} TM_{i5-2430M @ 2.40GHz × 4, Kernel}

tempo ma anche la forma dell’oggetto che pu`o essere pi`u o meno complicata; tuttavia la figura rende comunque l’idea di quanto aumenta mediamente il tempo di risposta al crescere delle dimensioni.