4. CREAZIONE DI UN DATABASE DI FEATURES
4.1 Premessa
Come descritto nel paragrafo 3.2.4, l’algoritmo SIFT associa, a ciascun keypoint (o feature) restituito, un descrittore che non dipende dalla posizione (u,v) del punto sull’immagine ma dal valore dei pixel che stanno nell’ intorno del keypoint.
Ricordiamo che feature e keypoint sono sinonimi.
Fig.4.1 Viene mostrato graficamente che il descrittore di una feature dipende solo dall’intorno del keypoint.
Grazie alla proprietà che hanno descrittori di essere indipendenti dalla posizione sull’immagine, è possibile eseguire un matching dei keypoint anche su immagini che riprendono la scena da viste diverse. Per sfruttare in maniera completa queste proprietà, è stato deciso di creare un database di features che vengono seguite su frame diversi.
Tale database è già stato creato in [8] e in [9] ma nel primo caso si lavorava in ambienti interni e soprattutto statici, nel secondo si dovevano seguire oggetti a grande distanza utilizzando un sistema monoculare.
Ricordiamo che, nel nostro caso, si tratta di ambienti esterni e dinamici.
Prima di passare a spiegare l’implementazione del database è necessario chiarire quali proprietà ha il descrittore SIFT.
Fig.4.2 Interfaccia realizzata per l’analisi dei dati presenti nel database Le coppie di “quadrati” rappresentano l’intorno dei keypoints destro e sinistro
4.2 Proprietà del descrittore SIFT
4.2.1 Il descrittore di features ideale
Il descrittore di features ideale descrive univocamente un punto appartenente ad un oggetto indipendentemente dalla posizione dell’oggetto nello spazio tridimensionale. Due keypoint rappresentano lo stesso punto appartenente allo stesso oggetto se i due descrittori hanno lo stesso valore. Per verificare che due descrittori ideali rappresentano lo stesso punto appartenente al solito oggetto, basta verificare che i descrittori ideali dei due keypoint siano uguali.
Fig.4.2 Equivalenza di due descrittori ideali A sinistra: la croce in rosso evidenzia il keypoint K1
A destra: la croce in rosso evidenzia il keypoint K2
Il descrittore ideale possiede le seguenti proprietà: 1. Non cambia se cambia la scala dell’immagine. 2. Non cambia se l’immagine viene ruotata .
3. Non cambia se si ha un cambiamento del punto di vista del keypoint. 4. Non cambia se viene aggiunto rumore all’immagine.
5. Non cambia se cambia l’illuminazione della scena.
Il descrittore ideale permette di seguire un punto appartenente ad un oggetto su più immagini in cui è presente l’oggetto.
4.2.2 Il descrittore reale
Nella pratica è possibile creare dei descrittori che possiedono solo in misura ridotta le proprietà del descrittore ideale.
I descrittori creati dall’algoritmo SIFT sono quelli che, tra tutti quelli presenti in letteratura, possiedono le proprietà più vicine a quelle del descrittore ideale.[19].
Si utilizzano descrittori SIFT composti da 128 numeri reali perché ciò comporta prestazioni migliori. (par.3.2.4)
varia poco, è possibile verificare che la distanza euclidea sia bassa, ossia stia sotto ad una certa soglia, per sapere se i due keypoint rappresentano due viste differenti dello stesso punto.
Fig.4.3 Equazioni che verificano che i due keypoints rappresentino lo stesso punto A sinistra: equazione valida per il descrittore ideale
A destra: equazione valida per il descrittore reale
Esiste comunque il rischio di “confondere” due keypoint ossia c’è il rischio che due keypoint che hanno distanza euclidea sotto la soglia si riferiscano a punti tridimensionali differenti magari appartenenti ad oggetti differenti; si pensi ad un’immagine in cui ci sono due oggetti identici.
Fig.4.4 Due oggetti identici in una stessa immagine. I keypoint contrassegnati con la “X” rossa avranno descrittore simile.
Se osserviamo fig.4.4, possiamo notare che i due keypoint contrassegnati con la ‘X’ avranno un descrittore simile pur appartenendo a due oggetti diversi aventi aspetto simile.
Per far sì che il rischio di confondere keypoint aventi descrittore simile sia basso, si utilizza l’algoritmo di par.3.3 per fare il matching tra descrittori della telecamera destra e descrittori della telecamera sinistra.
L’algoritmo spiegato nel par.3.3 cerca di selezionare i punti da triangolare in modo che non vengano confusi, infatti solo le coppie keypoint che hanno i descrittori abbastanza lontani dagli altri keypoint vengono considerati come corrispondenti ,gli altri non vengono considerati. Anche nei precedenti lavori in cui è stato creato un database di keypoint SIFT si cerca di selezionare i punti in modo che descrittori che hanno distanza euclidea bassa si riferiscano allo stesso punto 3D appartenente allo stesso oggetto. [8], [9].
Il database rischia di diventare inutilizzabile se vengono confusi due keypoint, per questo motivo si è deciso di memorizzare nel database solo i punti che hanno una corrispondenza tra destra e sinistra dopo l’algoritmo di matching. Il fatto che due immagini stereo siano prese nello stesso istante e riprendano la stessa scena fa sì che sia difficile confondere due keypoint che vengono inseriti nel database dopo l’algoritmo di matching di par.3.3.
4.3 Implementazione
4.3.1 Strumenti utilizzati
Il database è stato realizzato in linguaggio C++. Come compilatore si è utilizzato Microsoft Visual C++ .NET 2003 in ambiente windows.
Si è scelto il linguaggio C++ soprattutto per le prestazioni elevate, che sono fondamentali per i sistemi di visione per i veicoli mobili, e per la possibilità di creare strutture dati a lista utilizzando la libreria standard (Standard Template Library).
Per l’acquisizione dei filmati e per la visualizzazione a video dei dati presenti nel database è stata utilizzata la libreria OpenCV distribuita dalla Intel.
4.3.2 Programma di gestione del database
Fig.4.5 Flow-Chart che descrive il funzionamento del programma che gestisce il database di features
Notare che, nel flow-chart di fig.4.5, esiste un blocco in cui si rimuovono i keypoint che non sono stati visti per un certo numero di frames. Questo viene fatto perché non vogliamo tenere nel database keypoints troppo “vecchi” che potrebbero venir confusi con keypoints nuovi.Questo passo dell’algoritmo può anche non venir eseguito ed il database rimane ugualmente valido.
4.3.3 Strutture dati
Ogni elemento del database contiene i seguenti dati:
• Descrittore del keypoint sinistro.
• Posizione (ul,vl) sull’immagine del keypoint sinistro • Scala del keypoint sinistro
• Orientazione del keypoint sinistro • Descrittore del keypoint destro
• Posizione (ur,vr) sull’immagine del keypoint destro • Scala del keypoint destro
• Orientazione del keypoint destro
• Posizione tridimensionale del punto rispetto al riferimento mobile • Posizione tridimensionale del punto rispetto al riferimento fisso • Numero del frame in cui sono stati acquisiti i keypoints
Gli elementi del database sono memorizzati in una struttura a doppia lista come mostrato in fig.4.6.
Fig.4.6 Database strutturato a doppia lista. Gli elementi con le frecce orizzontali fanno parte della prima lista. Ogni elemento della prima lista possiede a sua volta una sottolista (frecce
verticali)
• Funzione insKeypoint che permette di inserire i dati di una feature proveniente dalla telecamera sinistra o destra.
• Funzione addData che permette di inserire i dati di entrambe le features(sinistra e destra)
• Funzione calcRadius che permette di calcolare il raggio associato ad una feature utilizzato per la clusterizazione (vedi Cap.5)
• Funzione comp3Dpos che calcola la posizione 3D della features sia rispetto al sistema di riferimento mobile (robot) sia rispetto al sistema di riferimento fisso. Naturalmente deve essere state date in ingresso sia la feature sinistra che quella destra (funzioni addData e insKeypoint).Il calcolo della posizione 3D viene fatto con la tecnica presentata nel paragrafo 2.3.
• Funzione is3DPosMobComputed che restituisce VERO se la posizione 3D della feature nel riferimento mobile è stata calcolata, FALSO altrimenti.
• Funzione is3DposFixComputed che restituisce VERO se la posizione 3D della feature nel riferimento fisso è stata calcolata, FALSO altrimenti.
• Funzione howManySons che restituisce il numero di figli posseduti da un padre ossia il numero di elementi della sottolista(fig.4.6)
• Funzione lSon che restituisce il puntatore all’ultimo figlio della sottolista , se esisto figli altrimenti restituisce il puntatore nullo.
• Costruttore
• Distruttore che distrugge gli elementi presenti in memoria dinamica appartenenti all’oggetto di cui il distruttore è membro e, se si tratta di un padre, la sottolista.
4.3.3 Aggiunta degli elementi al database
Nel momento in cui un elemento va aggiunto al database bisogna decidere se inserirlo nella prima lista oppure in una delle sottoliste. Ciò equivale a decidere se quello da inserire nel database è un nuovo punto oppure un punto già visto precedentemente. Per decidere se l’elemento da inserire è un nuovo punto oppure un punto già visto precedentemente si controlla la distanza tra il descrittore dell’ elemento da inserire ed il descrittore dell’ elemento più recente di ogni sottolista (l’ultimo inserito), se la distanza sta al di sotto di una certa soglia significa che si tratta di un punto già visto precedentemente e viene aggiunto alla sottolista.
Come fattore discriminante viene utilizzata la distanza perché si ha a che fare con descrittori reali(par.4.2.2). Una soglia assoluta per la distanza funziona bene perché si ha a che fare con punti già selezionati dall’algoritmo di triangolazione.
Ogni nuovo elemento da inserire viene confrontato con l’elemento della sottolista più recente perché si ha a che fare con descrittori reali che cambiano col variare del punto di vista. L’elemento più recente sarà, infatti, quello il cui descrittore è stato calcolato partendo dal punto di vista che si avvicina di più a quello attuale. Il descrittore più recente della sottolista sarà quindi, con tutta probabilità, il descrittore che ha distanza minore dal descrittore dell’elemento da inserire nella sottolista perché il descrittore da inserire nella sottolista è stato calcolato a partire dalla vista attuale.
Se si verifica che un punto non sta al di sotto della soglia per nessuna sottolista significa che l’elemento da inserire è un nuovo punto da seguire e viene inserito nella prima lista cioè quella orizzontale.(fig.4.6)
4.4 Risultati
Il programma che gestisce il database è stato fatto girare su un video realizzato con il Kart Ulisse (paragrafo 2.2.1) davanti al piazzale di Ingegneria.
Fig.4.7 In alto: coppia di frame stereo catturata da un video girato davanti al piazzale di ingegneria, sono messe in evidenza le corrispondenze trovate.
In basso: vista dall’alto dei punti presenti nel database. In rosso i punti che sono stati ritrovati nella coppia di frames attuale. In nero i punti ancora presenti nel database che sono stati più di
una volta ma che non sono stati ritrovati nella coppia di frames attuale. In blu i punti presenti nel database che sono stati visti una volta sola e che non sono stati ritrovati nella coppia di
Notare che l’elemento cerchiato in blu sia sulla vista dall’alto che sulla coppia di frames, è stato ritrovato ben 52 volte.
Le rette blu rappresentano il percorso effettuato dal keypoint. Le rette vanno dalla posizione attuale a quella che i punti avevano la prima volta che sono stati trovati. Vediamo che le tre rette presenti hanno tutte la solita pendenza; questo perché si riferiscono allo stesso spostamento. La posizione rappresentata sul grafico si riferisce al sistema di riferimento mobile: i tre punti non si sono mossi ma è il sistema mobile che si è mosso proprio nella direzione indicata dalle rette.
