Per superare questo problema si pu`o organizzare la ricerca in modo ge- rarchico, ovvero su pi`u livelli di precisione che consentono di affinare passo dopo passo il risultato trovato. In questo caso si usa una gerarchia a due livelli pertanto devono essere selezionati dei casi di riferimento che fungono da super-classi rispetto agli altri. Un riferimento `e una posa scelta in modo tale da rappresentare un insieme di altre pose associate ad essa secondo un criterio. Quindi se nella prima fase il sistema associa un particolare riferi- mento alla posa incognita, allora nella seconda fase vengono considerate pose valide anche quelle rappresentate da quel riferimento. All’interno di questo sottoinsieme deve essere individuata la posa migliore.
Nello specifico per realizzare questo metodo `e necessario passare attra- verso le seguenti fasi:
• Fase offline:
– vengono stabilite le pose di riferimento fra quelle del precedente database;
– addestramento della rete neurale per distinguere un riferimento giusto da uno sbagliato;
• Fase operativa:
– usando la rete prodotta viene ritrovato il riferimento migliore (oppure i primi k riferimenti migliori);
– vengono trovate nel database le pose a lui associate, ovvero quelle che si trovano all’interno del settore centrato nel riferimento; – in questo sottoinsieme si esegue una ricerca lineare della posa
migliore (usando la rete gi`a addestrata con l’approccio a forza bruta).
Negli step della fase operativa si usa il sistema del capitolo 8 per calcolare gli output di somiglianza, cambiando rete a seconda del livello gerarchico.
9.2.1
Scelta dei set
Un modo per individuare dei riferimenti `e la partizione dello spazio delle rotazioni possibili da 0◦ a 360◦. Il metodo pi`u semplice e intuitivo consiste nel suddividere il precedente insieme di addestramento in riferimenti equa- mente distanziati di N gradi, con N divisore di 360, cio`e l’insieme di angoli 0, 2N, 4N, ..., 360 − 2N . Trovato il riferimento migliore, possono essere sele- zionate le pose all’interno di quel settore che distano fino a un massimo di ±N◦ dal riferimento, restringendo cos`ı il campo di ricerca.
Figura 9.4: Esempio riferimenti
Si prendono i riferimenti associati ai singoli oggetti, ovvero per ciascuno di essi vengono usate solo le pose corrispondenti agli angoli di riferimento. Si potrebbero anche usare riferimenti per categoria, cio`e fissando un oggetto rappresentativo della categoria e prendendo i riferimenti solo fra le sue pose, escludendo tutti i riferimenti degli altri oggetti della sua categoria. In questo esperimento si `e optato per la prima scelta.
Verranno eseguiti quattro esperimenti in cui rispettivamente i riferimenti rappresentano classi di pose distanti da loro fino a N=10, 15, 30 e 45 gradi. Quindi nel primo caso saranno considerati come riferimenti le pose degli oggetti in posizione 0, 20, ..., 340, nel secondo quelle a 0, 30, ..., 330, nel terzo esempio quelle a 0, 60, ..., 300, infine nel quarto saranno considerate solo le pose a 0, 90, 180 e 270 gradi.
Per creare le coppie da usare come insieme di addestramento e di test si mappano rispettivamente le pose del precedente database e insieme di test nei nuovi riferimenti usati per ciascun esperimento.
9.2.2
Assegnazione dei target
Il criterio di addestramento rimane sempre lo stesso, sfruttando i con- cetti di categoria, simmetria e rotazione. In questo modo solo i riferimenti somiglianti verranno considerati dalla rete.
9.2.3
Addestramento
Dato che sono stati eseguiti quattro addestramenti per ognuno dei due algoritmi di descrizione locale, SHOT ed FPFH, il numero di immagini che illustrano i risultati degli esperimenti `e molto alto. Non verranno riportate tutte ma soltanto le matrici di confusione e gli istogrammi degli errori relativi ad un esempio di esperimento con riferimenti equidistanti 60 gradi.
(a) con descrizione SHOT (b) con descrizione FPFH
Figura 9.5: Matrici di confusione - Riferimenti equidistanti 60 gradi La rete riesce a trovare dei buoni riferimenti somiglianti. Nelle matrici di confusione si possono notare ancora delle leggere differenze a favore di SHOT, anche se molte percentuali di risposta sono molto vicine fra loro, come nel caso dei true negatives. Si pu`o notare tuttavia che per esempio il numero dei falsi negativi `e diventato minore nelle descrizioni FPFH.
(a) con descrizione SHOT (b) con descrizione FPFH
Figura 9.6: Istogrammi degli errori in uscita - Riferimenti equidistanti 60 gradi
9.2.4
Test
Di seguito sono riportate le percentuali di riconoscimento del riferimento migliore, verificandone la somiglianza con la posa incognita. Non si tratta di una posa definitiva perch´e verr`a scelta nella seconda fase, ma permette di capire che tipo di riferimenti servono per individuare oggetti e pose entro un certo margine di errore.
Spazio settore Oggetti ric. Pose ric. Pose no ric. Sbagliati 20 (558 rif) 540 (96.8%) 421 (75.4%) 119 (21.3%) 18 (3.2%) 30 (372 rif) 528 (94.6%) 435 (78.0%) 93 (16.7%) 30 (5.4%) 60 (186 rif) 510 (91.4%) 343 (61.5%) 167 (29.9%) 48 (8.6%) 90 (124 rif) 489 (87.6%) 325 (58.2%) 164 (29.4%) 69 (12.4%)
Tabella 9.5: Miglior riferimento ottenuto con descrizione SHOT Spazio settore Oggetti ric. Pose ric. Pose no ric. Sbagliati
20 (558 rif) 543 (97.3%) 401 (71.9%) 142 (25.4%) 15 (2.7%) 30 (372 rif) 542 (97.1%) 402 (72.0%) 140 (25.1%) 16 (2.9%) 60 (186 rif) 525 (94.1%) 338 (60.6%) 187 (33.5%) 33 (5.9%) 90 (124 rif) 478 (85.7%) 278 (49.8%) 200 (35.8%) 80 (14.3%)
Tabella 9.6: Miglior riferimento ottenuto con descrizione FPFH Osservazioni:
• rispetto al metodo a forza bruta le percentuali sono scese a livello generale perch´e il database `e ridotto ai soli riferimenti, dando meno possibilit`a di trovare casi corretti;
• entrambe le tipologie di descrizione sono robuste nel riconoscimento degli oggetti perch´e vengono riconosciuti nella stragrande maggioranza di casi, anche con riferimenti molto distanti fra loro;
• usando i riferimenti l’algoritmo FPFH tende a riconoscere meglio gli oggetti rispetto all’algoritmo SHOT, il quale perde qualche punto per- centuale ma resta sullo stesso ordine di grandezza;
• invece per quanto riguarda la stima delle pose si pu`o notare che l’algo- ritmo SHOT individua i riferimenti migliori in modo pi`u preciso rispetto ad FPFH; la causa `e la maggiore descrittivit`a di SHOT (come si vede anche nei successivi risultati);
• settori pi`u ampi possono offrire pi`u possibilit`a di individuare una posa corretta perch´e aumenta il numero di pose che essi rappresentano (per esempio quello di 30 gradi). Questo fatto `e osservabile in entrambe le descrizioni;
• tuttavia la pose estimation diminuisce drasticamente man mano che i riferimenti diventano sempre pi`u lontani e il database sempre pi`u vuoto. La causa risiede nella scarsit`a di informazione di un database ridotto a poche pose perch´e non riescono a coprire la casistica possibile di rotazioni;
• dagli ultimi due punti si pu`o dedurre che potrebbe esistere una gran- dezza ottimale compresa fra 30 e 60 gradi in cui le percentuali vengono massimizzate.
Queste sono le percentuali relative alla posa finale trovata all’interno del sottoinsieme associato al riferimento individuato durante la prima fase.
Spazio settore Oggetti ric. Pose ric. Pose no ric. Sbagliati 20 (558 rif) 540 (96.8%) 421 (75.4%) 119 (21.3%) 18 (3.2%) 30 (372 rif) 528 (94.6%) 434 (77.8%) 94 (16.8%) 30 (5.4%) 60 (186 rif) 510 (91.4%) 366 (65.6%) 144 (25.8%) 48 (8.6%) 90 (124 rif) 489 (87.6%) 346 (62.0%) 143 (25.6%) 69 (12.4%) Tabella 9.7: Percentuali riconoscimento con descrizione SHOT e riferimenti
Spazio settore Oggetti ric. Pose ric. Pose no ric. Sbagliati 20 (558 rif) 543 (97.3%) 402 (72.0%) 141 (25.3%) 15 (2.7%) 30 (372 rif) 542 (97.1%) 402 (72.0%) 140 (25.1%) 16 (2.9%) 60 (186 rif) 525 (94.1%) 359 (64.3%) 166 (29.7%) 33 (5.9%) 90 (124 rif) 478 (85.7%) 296 (53.0%) 182 (32.6%) 80 (14.3%) Tabella 9.8: Percentuali riconoscimento con descrizione FPFH e riferimenti
Osservazioni:
• i riconoscimenti degli oggetti sono uguali alle tabelle precedenti perch´e il metodo cerca pose associate a quella di riferimento, quindi l’oggetto `
e gi`a stato individuato nella fase precedente;
• la stima dele pose `e migliorata per entrambe le tipologie di descrizione ma nel caso di SHOT i miglioramenti sono pi`u evidenti; la causa `e la capacit`a descrittiva di SHOT che produce descrittori a 356 bin, molto pi`u ampi rispetto a quelli di FPFH che possiedono 33 bin;
• in entrambi i casi le prestazioni diminuiscono all’aumentare dello spazio del settore, ovvero al diminuire del numero di riferimenti, a causa della minore informazione disponibile nel database;
• nei casi con pi`u riferimenti le percentuali sono affini a quelle della ricerca lineare perch´e tendono ad eguagliarla.
Queste considerazioni appaiono pi`u evidenti nei grafici in figura 9.7.
(a) Object recognition
(b) Pose estimation
Dal punto di vista empirico si deve tenere in considerazione che il criterio di assegnazione dei target (e di valutazione delle risposte) `e approssimativo e automatico.
Quindi pu`o accadere che due pose che differiscono per rotazioni maggio- ri siano state classificate dalla rete effettivamente simili, mentre il criterio restituisce di fatto una risposta approssimativa. Infatti se si controllassero manualmente gli output forniti dalla rete, tale percentuale potrebbe salire e potrebbe scendere quella delle pose sbagliate.
9.2.5
Tempo totale di risposta
I tempi medi per eseguire i cicli di confronti fra point cloud incognita e tutti i riferimenti sono riportati in tabella 9.9.
Spazio settore Riferimenti TSHOT (ms) TF P F H (ms)
20 558 8370 1674 30 372 5580 1116 60 186 2790 558 90 124 1860 372
Tabella 9.9: Tempo medio ciclo di calcolo miglior riferimento
Figura 9.8: Tempi medi di risposta dei cicli di confronti al variare del numero di casi nel database per entrambe le tipologie di descrizione locale
A questi tempi deve essere sommato il tempo iniziale di descrizione della point cloud incognita (T dSHOT = 192ms e T dF P F H = 1052ms), come ripor-
tato nella sezione dei tempi sulla ricerca lineare. I tempi totali sono riportati in tabella 9.10.
Spazio settore Riferimenti TSHOT (ms) TF P F H (ms)
20 558 8562 2726 30 372 5772 2168 60 186 2982 1610 90 124 2052 1424
Tabella 9.10: Tempo totale per trovare miglior riferimento
Il tempo successivo per eseguire un confronto della point cloud incognita con quelle del sottoinsieme di pose contigue al riferimento `e irrilevante ai fini della stima perch´e si tratta solo di calcolare uscite della rete neurale che risponde in tempi inferiori al millisecondo. Un ciclo di questo tipo produce ritardi dell’ordine di unit`a di millisecondi quindi si pu`o considerare la tabella 9.10 come rappresentativa dei tempi totali di risposta.
Si pu`o osservare che i tempi di calcolo sono inferiori rispetto alla ricerca di tipo lineare: il numero di confronti da eseguire `e diminuito quindi diminuisce anche il tempo richiesto per ottenere dalla rete la posa nota con somiglianza massima. FPFH continua ad essere pi`u veloce di SHOT perch´e possiede descrittori relativamente pi`u piccoli.
L’algoritmo SHOT offre prestazioni migliori ma in tempi maggiori, FPFH ha prestazioni leggermente inferiori ma in tempi pi`u rapidi.
Overview Sistema Ibrido
globale - locale
Il sistema sviluppato fino a questo punto `e molto descrittivo e d`a buo- ni risultati. I tempi di risposta sono altrettanto buoni ma in un contesto realtime si vorrebbe che fossero pi`u brevi. Si tratta di trovare un modo per abbassarli il pi`u possibile senza degradare o perdere i risultati ottenuti.
Per raggiungere lo scopo si pu`o intraprendere un approccio gerarchico molto pi`u spinto di quello precedentemente utilizzato, apportando le seguenti variazioni:
• oltre ad adoperare la stessa tipologia di descrizione locale, il nuovo sistema fa anche uso di un algoritmo di descrizione globale;
• la descrizione globale viene eseguita durante una prima fase al fine di scremare il database e trovare i primi kNN;
• questi k risultati vengono poi dati in pasto al sistema gi`a implementato (approccio locale con rete neurale) che provvede a descrivere le k coppie dal punto di vista locale e a individuare quale fra queste restituisce il massimo risultato di somiglianza.
La pipeline seguita durante la prima fase corrisponde pertanto all’altro ramo della pipeline di descrizione visibile in figura 5.5.
Il vantaggio di un approccio del genere `e che la prima fase, facendo uso di algoritmi globali, `e molto pi`u veloce dell’approccio gerarchico locale. Il confronto locale pu`o essere eseguito in modo lineare su tutte le k coppie, quindi la complessit`a della seconda fase `e sempre lineare ma k N , con N numero di riferimenti del database. Infatti il parametro k pu`o essere scelto molto basso a seconda della capacit`a dell’algoritmo globale di trovare buoni candidati, permettendo cos`ı di ridurre il numero di confronti da eseguire.
10.1
Descrizione globale
Viewpoint Feature Histogram (VFH) `
E l’algoritmo di descrizione globale utilizzato per implementare la prima fase di individuazione dei migliori kNN nel database. Si ispira ad FPFH, l’algoritmo di descrizione locale gi`a incontrato e usato in questo progetto.
La caratteristica distintiva del VFH consiste nel fatto che vuole replicare, da un punto di vista globale, la stessa forza descrittiva locale di FPFH. La gi`a discreta velocit`a dell’algoritmo locale in questo caso si riduce ulteriormente perch´e la descrizione viene compiuta sull’intera point cloud dell’oggetto e non su ciascuna delle singole regioni intorno ai keypoints.
VFH introduce anche una dipendenza del risultato rispetto al punto di osservazione (viewpoint), lasciandolo comunque invariante nei confronti del- la scala. Nello specifico l’algoritmo studia le propriet`a delle normali alla superficie in ciascun punto dell’oggetto rispetto alla direzione del punto di osservazione.
Il descrittore `e formato da due componenti: una relativa ad FPFH e l’altra al viewpoint.
Quest’ultima viene calcolata tramite le differenze fra il vettore direzione del punto di osservazione e le normali alla superficie in ciascun punto della nuvola. In pratica viene riposizionato il vettore del viewpoint su ogni punto e calcolato l’angolo formato con la sua normale (figura 10.1).
Figura 10.1: Viewpoint feature
Per quanto riguarda la parte FPFH, il keypoint stavolta `e uno solo: il baricentro della nuvola di punti. La terna di angoli < α, φ, θ > viene quin- di calcolata usando la normale del generico punto e quella del baricentro. L’insieme di tutti i punti della nuvola fornisce quindi una serie di terne che vengono poi ripartite nell’istogramma.
La giustapposizione dell’istogramma VFH con la versione FPFH globale forma un istogramma di 308 bin che rappresenta il descrittore di questo
algoritmo. In questo modo ogni normale alla superficie viene legata anche al viewpoint. Si tratta di un algoritmo ideato appositamente allo scopo di identificare gli oggetti, anche in condizioni di rumorosit`a delle point cloud acquisite.