5.3 Pipeline descrittiva
5.3.3 Features locali
Una feature `e una rappresentazione per dati 3D pi`u compatta rispetto alla semplice sequenza di punti ma sufficientemente ricca di informazioni.
Metodi di questo genere vengono progettati per essere invarianti o robusti rispetto a specifiche tipologie di trasformazioni e/o disturbi. Pertanto una feature `e buona se `e in grado di rilevare le somiglianze anche in presenza di trasformazioni rigide (rototraslazioni), di differenze sulla densit`a di punti e di rumore. L’aspetto fondamentale `e che l’algoritmo deve essere capace di catturare la fisionomia delle superfici in modo che le similitudini risaltino in caso di confronto.
Signature of Histogram of Orientation
SHOT [6] `e un descrittore per oggetti tridimensionali basato su istogram- mi. Gli istogrammi vengono calcolati contando differenze fra elementi geo- metrici sulle regioni di punti, in questo caso le normali alla superficie. L’algo- ritmo cerca quindi di descrivere tratti topologici dell’oggetto, cio`e quelli in- varianti alla rotazione e traslazione descrivendo l’orientamento delle superfici locali di punti.
Una descrizione del genere `e pi`u attinente alla forma dell’oggetto e pi`u rappresentativa rispetto alla semplice terna di coordinate spaziali. Inoltre l’uso di istogrammi rende la descrizione robusta in presenza di rumore, per esempio sulla direzione delle normali, dato che fa uso di bin cumulativi di occorrenze. Se una normale non `e perfettamente orientata `e comunque con- siderata equivalente a tutte le altre dello stesso bin che sono state calcolate correttamente.
Vediamo pi`u in dettaglio il procedimento descrittivo: intorno al keypoint viene definita una griglia tridimensionale di riferimento con le informazioni geometriche riguardanti le posizioni dei punti all’interno del supporto. Per ognuno di questi volumi parziali viene costruito un istogramma mediante una funzione dell’angolo θ fra la normale di un generico punto e la normale del punto chiave. Tale funzione fa uso del coseno e ha il pregio di essere facilmente calcolabile, dato che cosθ corrisponde al prodotto scalare delle due normali (altro non sono che due vettori unitari):
cosθ = ni· nk = nix· nkx+ niy· nky+ niz · nkz
dove con la notazione nx, ny, nz si intendono le rispettive componenti della
terna di coordinate spaziali che descrivono il vettore normale ¯n, con i l’indice del generico punto e k quello del keypoint di riferimento.
(a) Griglia SHOT (b) Confronto della nor- male di un punto con quella del keypoint
(c) Istogramma SHOT
Figura 5.10: Geometria descritta da SHOT
Quindi, una volta calcolata la differenza di direzione fra le due normali, verr`a incrementato il valore del corrispondente bin dell’istogramma.
Questo procedimento viene eseguito in parallelo per ogni porzione della griglia sferica; al termine gli istogrammi risultanti vengono giustapposti per formare l’istogramma completo che in questo algoritmo `e il descrittore locale della regione di punti.
Inoltre per renderlo indipendente dalla densit`a di punti ogni descrittore viene normalizzato in modo che la somma dei bin sia unitaria. In questo modo point cloud di oggetti acquisiti con pi`u telecamere a diverse risoluzioni possono essere confrontate fra loro.
Fast Point Features Histogram
FPFH [7] fa parte della categoria di algoritmi geometry-based, cio`e quel- li che fanno uso di vettori, normali, distanze e proiezioni. Nel dettaglio i descrittori FPFH rappresentano gli orientamenti relativi delle normali della point cloud, le loro direzioni e le distanze fra coppie di punti, cercando in pratica di descrivere le variazioni della superficie.
La figura 5.12 mostra un esempio di regione locale sferica analizzabile dall’algoritmo intorno al keypoint marcato in rosso.
Figura 5.12: Regione PFH
Le coppie possibili sono formate dai punti appartenenti alla stessa regione sferica locale intorno al punto chiave. Le coppie non vengono rappresentate dalle loro coordinate ma dalle distanze e dagli angoli α, φ, θ calcolati rispetto al sistema di coordinate fisse che fa uso della normale del primo punto, del vettore differenza normalizzato e dei prodotti vettoriali fra questi vettori risultanti, producendo una terna di versori ¯u, ¯v, ¯w:
u = ni
v = u × pi− pj kpi− pjk2
w = u × v Infine vengono calcolati gli angoli e la distanza:
α = vT · ni
φ = u ×pi− pj d
θ = arctan(w · ni, u · ni)
Figura 5.13: Rappresentazione dei parametri descrittivi di una coppia Si passa quindi da una rappresentazione della coppia di punti con una matrice 6x2 (3 coordinate di un punto pi`u 3 coordinate della sua normale, per due punti) ad una rappresentazione pi`u compatta formata dalla quadrupla < α, φ, θ, d >, rappresentata in figura 5.13
Infine l’insieme di tutte le quadruple viene mappato in un istogramma che rappresenta la descrizione della zona locale. Cos`ı funziona l’algoritmo PFH (Point Feature Histogram), in cui il risultato di una regione con n punti si ottiene con una complessit`a quadratica O(n2).
Si pu`o semplificare e velocizzare questo algoritmo apportando le seguenti modifiche per approssimazione: per abbattere il tempo quadratico si riduce il numero di coppie possibili, cio`e si calcolano le variabili < α, φ, θ, d > rispetto ai vicini solo per ogni keypoint (figura 5.14, coppie rosse).
Figura 5.14: Regione FPFH
Il risultato viene chiamato SPFH (simplified PFH). Il vero risultato fi- nale FPFH associato alla zona locale viene calcolato usando questi valori semplificati pesati in base alla loro distanza.
F P F H(pk) = SP F H(pq) + 1 k n X i=1 1 di SP F H(pi)
Pi`u gli altri keypoints sono vicini e pi`u il loro risultato semplificato viene considerato con maggior peso; in pratica sta delegando al vicino parte del calcolo.
Quindi FPFH non interconnette totalmente i vicini, risparmiando tempo e calcoli, cio`e pu`o tralasciare qualche coppia che potrebbe contribuire ad una descrizione geometrica pi`u precisa della zona intorno ad un keypoint, come farebbe PFH. Tuttavia grazie al contributo degli altri keypoints ha una visione pi`u ampia della superficie, fino ad un massimo pratico pari a due volte il raggio della regione locale (oltre questa distanza i contributi di tipo SPFH cominciano a diventare ininfluenti). Inoltre se le regioni di due o pi`u keypoints si intersecano, ovvero possiedono vicini in comune, il calcolo degli SPFH terr`a conto di quei vicini per due o pi`u volte.
Comunque accettando queste approssimazioni si ottiene un drastico calo dei tempi di esecuzione. Tale procedimento ha una complessit`a O(nk), con k numero di punti chiave su cui eseguire il calcolo ed n il numero di vicini. Pertanto FPFH viene incontro in modo relativamente migliore alle esigenze di applicazioni real-time rispetto al PFH da cui deriva.
Radius-based Surface Descriptor
RSD [8] `e un algoritmo che descrive la geometria in un regione locale tramite la stima delle relazioni radiali fra i punti. Si assume che ogni coppia di punti giaccia su una sfera il cui raggio viene trovato tramite una relazione fra d, la distanza dei punti e l’angolo α fra le loro normali. L’espressione `e la seguente:
d(α) =√2r√1 − cosα ≈ rα + rα
3
24 + O(α
5)
Questa relazione diventa approssimativamente lineare con il raggio r (in metri) come fattore di proporzionalit`a quando α ∈ (0, π/2).
Il descrittore `e costituito dalla coppia di raggi minimo e massimo che riescono a intersecare meglio i punti. Nel caso in cui l’angolatura linearizza la relazione le soluzioni coincidono.
Viene applicata una regressione lineare sulle coppie di minimo e massimo (α, d) allo scopo di stimare il minimo e il massimo raggio r in modo accurato. Il raggio tende ad infinito come estremo superiore, rappresentando quindi la condizione di planarit`a della superficie. Per valori tendenti a zero significa che la curvatura `e molto accentuata.
`
E possibile anche una approssimazione cilindrica in cui il raggio minimo approssima il raggio del cilindro mentre il raggio massimo sar`a infinito. 3D Shape Context
3DSC [9] `e l’estensione di un analogo algoritmo a due dimensioni.
La descrizione si ricava utilizzando una sfera tridimensionale centrata nel punto chiave e sovrapposta su tutti i punti suoi vicini.
All’interno di questa struttura di supporto vengono definiti dei settori tridimensionali individuati da azimut, altitudine e raggio (come mostrato in figura 5.15).
Figura 5.15: Supporto sferico
Le prime due dimensioni sono suddivise in intervalli equispaziati, invece il raggio viene suddiviso in modo logaritmico. Ognuno di questi settori `e quindi individuato da una terna di indici (j, k, l) rispettivamente associati alle tre componenti che individuano il settore.
Mediante questi indici il settore `e associato al suo bin in un istogramma tridimensionale che rappresenta l’output dell’algoritmo, ovvero il descrittore locale. Il valore del bin si ottiene mediante una somma di pesi per ogni punto che ricade all’interno del rispettivo settore. Il peso usato `e l’inverso della densit`a e del volume.
ω(pi) ≈
1
ρV (j, k, l) , pi ∈ V (j, k, l)
Quindi per ogni punto si vede in quale sfera ricade e viene incrementato il bin corrispondente di una quantit`a ω(pi). La divisione per il volume viene usata
per normalizzare i bin in modo da non rendere il risultato dipendente dalle diverse grandezze che i settori possono avere a seconda di dove si trovano all’interno dello sfera.
Il polo nord della griglia sferica `e allineato con la normale alla superficie stimata nel keypoint, ovvero il centro della sfera stessa. Tuttavia non viene fissato alcun orientamento della griglia (l’orientamento `e quello che definisce da dove partono i settori e di conseguenza tutti gli indici che li individua- no). L’algoritmo sceglie di ripetere la descrizione per ogni azimuth possibile fornendo pi`u di un descrittore per ogni keypoint.
Unique Shape Context
USC [10] `e la versione estesa dell’algoritmo 3DSC. La tecnica associata al calcolo dei bin `e sempre la stessa, la differenza sta nell’univocit`a della descrizione. Stavolta viene fissato subito un sistema di riferimento locale sul piano della normale al keypoint, centrato su di esso. In questo modo la griglia viene orientata in modo unico, producendo quindi un solo descrittore locale per ogni keypoint. Come conseguenza si risparmia una notevole quantit`a di memoria e si evita ambiguit`a in fase di matching per capire quando i descrittori di point cloud diverse si somigliano.
Confronto temporale
La complessit`a di calcolo degli algoritmi esposti varia notevolmente da uno all’altro. Nel caso di questa applicazione si deve innanzitutto puntare sulla rapidit`a di risposta perch´e i vincoli real-time di un afferraggio sono stringenti.
In figura 5.16 vediamo un confronto grafico dei tempi di descrizione al variare della grandezza delle point cloud (il dataset usato `e reperibile libera- mente all’indirizzo [5] e tutte le descrizioni sono state eseguite con gli stessi parametri al fine di renderle confrontabili).
Nella tabella 5.1 sono riportati i tempi medi delle stesse descrizioni di ciascun algoritmo.
Algoritmo Tempo medio (ms) SHOT 41 PFH 11145 FPFH 901 RSD 37 SC3D 1716 USC 990
Figura 5.16: Tempi di risposta degli algoritmi di descrizione locale
Si pu`o notare che:
• gli algoritmi SHOT ed RSD hanno i tempi di risposta pi`u rapidi. Ci`o non deve sorprendere perch´e compiono meno elaborazioni rispetto agli altri, come `e stato spiegato precedentemente;
• gli algoritmi di tipo SC (Shape Context) sono i pi`u lenti, perch´e pi`u complessi fra tutti, ma tendono a stabilizzarsi con l’aumentare delle dimensioni;
• i tempi di risposta dell’algoritmo FPFH, pur essendo relativamente rapidi per dimensioni medio/basse, tendono per`o a crescere per di- mensioni maggiori, senza tuttavia superare la banda di tempi degli SC.
Ai fini dell’applicazione serve prima di tutto un tempo di risposta3 il pi`u
possibile veloce per ottenere una descrizione della point cloud incognita. Non `
e l’unico fattore da considerare perch´e l’applicazione dovr`a poi confrontare questa descrizione con quelle delle point cloud presenti nel database di casi noti.
Pertanto diventa estremamente importante considerare i seguenti aspetti: • tempo di descrizione;
• quantit`a di memoria occupata dai descrittori (legata al tempo necessa- rio per eseguire un singolo confronto).
Come visto, una descrizione di questo tipo `e formata da una serie di strutture ognuna per ogni regione locale. La velocit`a con cui viene eseguito un singolo confronto dipende dalla memoria occupata dai descrittori, pi`u in dettaglio dipende dalle sue N dimensioni: pi`u il numero `e grande, pi`u tempo ci vorr`a per trovare le corrispondenze fra descrittori.
D’altra parte avere tante dimensioni pu`o voler dire avere un’elevata de- scrittivit`a. E cos`ı per i descrittori SC che sono molto lenti e producono` descrittori molto grandi (con 1980 bin o dimensioni, infatti un descrittore corrisponde ad un vettore e i bin alle sue dimensioni). Ci sono due algoritmi come SHOT ed FPFH che non confermano la regola. L’algoritmo SHOT `e molto semplice ma genera descrittori con 352 bin. Questa memoria serve per compensare la semplicit`a e velocit`a di esecuzione in modo da dettagliare la descrizione con pi`u precisione. FPFH al contrario `e un algoritmo pi`u com- plesso e pi`u descrittivo delle propriet`a geometriche ma al termine produce descrittori a 33 dimensioni, molto pi`u piccoli di quelli di SHOT.
3Test eseguiti su dataset [5] con CPU Intel CoreR TMi5-2430M @ 2.40GHz × 4, Kernel
Pertanto SHOT `e conveniente in fase iniziale per descrivere rapidamente la point cloud incognita ma successivamente, durante il ciclo di confronti, sof- fre il peso della memoria dei suoi descrittori. Invece FPFH compensa la com- plessit`a descrittiva iniziale con una minore memoria e quindi con maggiore velocit`a nell’analisi successiva.
Tuttavia non `e conveniente ridurre eccessivamente la quantit`a di memoria utilizzata dai descrittori, a meno che non siano straordinariamente complessi da poter sopperire alla riduzione di dettaglio.
Si rende quindi necessario operare un compromesso tra le cause che deter- minano i tempi sopracitati. Nel caso ideale servirebbe un descrittore veloce ma complesso in fase iniziale e che generi descrittori piccoli per la fase dei confronti. Nella pratica basta ricercare una buona capacit`a descrittiva che non occupi una quantit`a eccessiva di memoria.
RSD possiede il tempo di risposta alla descrizione pi`u basso di tutti ma a discapito della descrittivit`a: le sue descrizioni, basate su fitting della superfi- cie con due sfere e due raggi minimi e massimi, sono troppo approssimative. SHOT invece possiede entrambe le specifiche richieste: tempo di risposta basso e descrittivit`a pi`u alta grazie alla non eccessiva memoria utilizzata. Anche FPFH potrebbe essere un buon candidato perch´e `e un algoritmo pi`u complesso dei precedenti ma che richiede meno memoria di SHOT. Invece gli algoritmi della categoria SC sono onerosi anche per l’aspetto del consumo di memoria.
Pertanto nella fase successiva di analisi dei match fra liste di descrittori, i confronti verranno eseguiti con le descrizioni pi`u rappresentative dal punto di vista della descrittivit`a, del tempo di risposta, della memoria (che influenza il tempo richiesto per eseguire confronti), ovvero quelle prodotte dagli algoritmi SHOT, FPFH, USC, RSD, tralasciando le pi`u lente gi`a in fase iniziale ovvero PFH e 3DSC.
Matching fra descrittori
Una volta elaborate le descrizioni per ciascuna point cloud, queste possono essere confrontate a due a due. Per farlo `e necessario trovare la descrizione pi`u vicina (in questo caso `e una sola ma in generale il problema consiste nel trovare k descrizioni pi`u vicine, o kNN cio`e k Nearest Neighbors).
I descrittori locali non sono altro che vettori. Immaginandoli come punti posizionati in uno spazio ad N dimensioni, la loro vicinanza pu`o essere rica- vata mediante il calcolo della distanza euclidea: quella minima corrisponder`a al descrittore che pi`u si avvicina a quello richiesto. Si tratta quindi di trova- re un vettore N-dimensionale all’interno di un insieme di probabili candidati che sia il pi`u possibile vicino a quello analizzato.
Figura 6.1: Distanze euclidee minime
I descrittori di una point cloud tutti insieme fanno a loro volta un vettore di vettori. Quindi l’analisi del kNN va ripetuta per ciascun descrittore della point cloud incognita, scandendo la lista di descrittori della point cloud nota presente nel database.
Esistono alcune tecniche possibili per analizzare una lista di vettori e trovare quello che dista meno da un vettore incognito:
• Lineare o forza bruta: il confronto viene eseguito in un ciclo analizzando tutti i descrittori uno per volta (complessit`a lineare);
• k-D tree: spiegato in seguito (la complessit`a `e logaritmica, quindi mol- to migliore della precedente, ma all’aumentare delle dimensioni dei de- scrittori le prestazioni degradano fino a ricondursi alla tecnica lineare, perch´e i tempi di esplorazione si allungano).
6.1
k Nearest Neighbors e k-D tree
Un k-D tree `e un albero a k dimensioni. Si tratta di una struttura usata per organizzare un certo numero di punti in uno spazio a k dimensioni [13].
Viene usato per realizzare ricerche binarie ed `e molto utile per risolvere il problema di individuare k nearest neighbors o trovare punti all’interno di un range stabilito da una distanza massima.
Ogni nodo dell’albero `e un punto k-dimensionale. Ciascun livello dell’al- bero `e associato ad una delle k dimensioni e suddivide tutti i figli lungo la rispettiva dimensione usando un iperpiano perpendicolare all’asse corrispon- dente.
Per esempio, se ad una certa suddivisione a partire da un nodo si consi- dera la componente x di un vettore come discriminante, tutti i vettori con componente x inferiore a quella di quel nodo (che sar`a padre di due sottoal- beri) compariranno nel sottoalbero sinistro, mentre quelli con componente maggiore o uguale si troveranno nel sottoalbero destro. Questo vuol dire che l’iperpiano divisorio passa per il valore x del nodo padre e la sua normale `e l’asse x stessa.
Per costruire l’albero si usa una dimensione per volta ad ogni livello in cui viene ramificato. Alla radice dell’albero tutti i figli vengono divisi a partire dalla prima dimensione, nel secondo livello si usa la seconda dimensione come discriminante e in generale all’0i-esimo livello corrisponde la i-esima delle k dimensioni. Se all’ultima dimensione i punti non sono ancora finiti si prosegue la ramificazione ripartendo con la prima dimensione e un nuovo ciclo.
Esempio con punti tridimensionali: alla radice si creano due ramificazioni usando la componente x, da questi due nodi si creano altre due ramificazioni usando la componente y, al livello successivo si user`a la componente z; il ciclo riparte e viene riusata la componente x. Pertanto la radice avr`a due figli discriminati secondo x, 4 nodi nipoti discriminati secondo y, 8 bisnipoti
secondo z e poi riparte il ciclo con 16 pronipoti discriminati di nuovo secondo la componente x.
Vediamo un esempio pratico. Supponiamo di voler memorizzare i se- guenti i punti bidimensionali: (2, 4)(5, 6)(9, 7)(5, 6)(10, 8)(7, 2). Un possibile risultato `e mostrato nelle figure 6.2 e 6.3:
Figura 6.2: Esempio di 2-D tree
Dal punto di vista geometrico la suddivisione operata dai piani `e rap- presentabile in questo modo (le linee rosse corrispondono alle suddivisioni operate lungo la dimensione x e quelle blu lungo y):
Figura 6.3: Esempio di piani 2-D tree
In questo modo, nel caso ideale, si crea un k-D tree bilanciato in cui ogni nodo foglia si trova alla stessa distanza dalla radice. Non `e comunque
garantito che l’albero sia perfettamente bilanciato. Dipende dal numero di punti e dal punto selezionato per fare da nodo padre di due sottoalberi.
Per bilanciare il pi`u possibile `e sempre bene usare come nodo padre il punto mediano. Su tutti i punti rimasti da inserire nell’albero viene eseguito un algoritmo di ordinamento secondo la rispettiva dimensione associata al livello dell’albero; al termine verr`a selezionato il punto centrale come padre delle ramificazioni. Si pu`o usare per esempio un algoritmo come Heapsort che ha una complessit`a O(n logn). In questo caso la costruzione ha una complessit`a di O(nlog2 n). Per ridurre il costo computazionale `e preferibile
eseguire queste operazioni di ordinamento su un loro sottoinsieme, a costo di non ottenere un albero esattamente bilanciato.
L’ordinamento si pu`o anche eseguire prima della costruzione dell’albero: si applica k volte (come le dimensioni) lo Heapsort sui punti, cambiando ogni volta dimensione su cui ordinarli. Si ottengono quindi k liste di vettori ordinati. Al generico livello i-esimo si utilizza la lista i-esima per trovare il punto centrale da usare come nodo. Ovviamente verr`a eliminato anche dalle altre liste mediante riferimenti. In questo caso la complessit`a di costruzione dell’albero `e pari a O(kn logn) per gli ordinamenti pi`u O([k-1]n) test per costruire ognuno dei logn livelli. In totale O(kn logn) + O([k-1]n log n) Nearest Neighbor
L’algoritmo NN serve per trovare nell’albero il punto che `e pi`u vicino ad un punto di interesse. L’albero permette di eliminare in modo efficiente buona parte di casi sfavorevoli. L’algoritmo `e strutturato nel modo seguente:
• sia ¯pi il punto di interesse;
• partire dal nodo radice e procedere ricorsivamente:
– ad ogni livello analizzare il valore della rispettiva dimensione del