tezza
Le feature visuali locali estratte con gli algoritmi visti finora vengono spesso utiliz- zate per molte funzioni dell’analisi visuale. In particolare sono molto efficaci per quanto riguarda compiti di riconoscimento visuale. Esempi applicativi sono: il ri- conoscimento di oggetti, il riconoscimento di punti di riferimento, le interrogazioni visuali, il recupero di immagini, etc. Nel corso di questo lavoro di tesi viene fatto uso di alcuni metodi di riconoscimento visuale. Vediamo quindi le modalità più utilizzate per implementare queste funzionalità, fornendo un’analisi delle tecniche impiegate allo stato dell’arte. Verrà inoltre mostrato come è possibile misurare l’accuratezza del riconoscimento.
2.3.1
Metodi di riconoscimento
Un sistema di riconoscimento è tipicamente caratterizzato dalla seguente struttu- ra: un dispositivo di acquisizione di immagini fornisce l’immagine in input, che contiene l’oggetto da riconoscere, e viene processata utilizzando uno degli algoritmi presentati nella Sezione 2.2. Il processo di riconoscimento utilizza un database di immagini di riferimento: per ognuna delle immagini del database vengono estratte le feature visuali corrispondenti, che vengono poi memorizzate. A questo punto deve essere identificata nel database l’immagine che è più simile all’immagine in input. Per fare questo si effettua un confronto tra le feature dell’immagine in in-
put e le feature di ognuna delle immagini del database. Per ognuno dei confronti l’algoritmo prende nota di quante corrispondenze ci sono tra le feature delle due immagini. Alla fine di questi processo, l’immagine del database con il più alto numero di corrispondenze viene considerata la più somigliante. Anche se que- sta procedura permette di ottenere dei buoni risultati di riconoscimento, possono essere implementati diversi miglioramenti per ottenere prestazioni migliori. Nel seguito ne vengono esposti due.
• Ricerca nearest neighbor:
per decidere se una una feature appartenente all’immagine in input corri- sponde ad una feature di un’immagine del database viene effettuata la cosid- detta ricerca del nearest neighbor, cioè del vicino più prossimo. Per feature a valori reali (come per SIFT), si utilizza la distanza euclidea, mentre per feature binarie si utilizza la distanza di Hamming. Tuttavia, il numero di feature contenuto nell’immagine di input e in ogni immagine del database può essere molto alto, nell’ordine delle centinaia o anche delle migliaia. Per questa ragione può essere molto costoso effettuare un confronto del gene- re tra l’immagine in input e quelle del database. Per ottimizzare i tempi possono essere quindi utilizzate tecniche di ricerca come quella del nearest neighbor [22] [23]. Tuttavia, molte feature di un’immagine non presentano una corrispondenza corretta in quanto derivano da uno sfondo poco definito o non sono state individuate nelle immagini su cui si è effettuato il training. Per questo motivo, al fine di scartare le feature che non hanno una buona corrispondenza con il database, può venire l’idea di una soglia globale sulla distanza dalla feature più vicina. Questa soluzione non risolve però il pro- blema, in quanto alcuni descrittori sono molto più discriminanti di altri. Un metodo più efficace è quello di confrontare la distanza del nearest neighbor con quella del secondo nearest neighbor, utilizzando il cosiddetto test del
rapporto. La corrispondenza viene considerata valida se:
d1 ≤ τ · d2 (2.11)
dove d1 e d2 sono rispettivamente le distanze del nearest neighbor e del
secondo nearest neighbor. E’ stato dimostrato [16] che l’impiego di un test del rapporto con una soglia τ nel range 0.6-0.8 può migliorare nettamente le prestazioni.
• Controllo di consistenza geometrica:
Anche il test del rapporto non è in grado di eliminare tutte le false corri- spondenze. Per questa ragione esiste un’altra soluzione in grado di scartare quelle corrispondenze che non rispettano una trasformazione geometrica glo- bale. Questo metodo è detto RAndom SAmple Consensus (RANSAC) [24], che è in grado di stimare una omografia tra l’immagine in input e quella del database e verificare quindi quali sono le corrispondenze che rispettano l’omografia stimata.
Alla conclusione della fase di confronto delle dipendenze viene generata una clas- sifica delle immagini del database sulla base del numero di corrispondenze trovate con l’immagine in input. Le immagini che sono in cima alla classifica sono quelle più simili all’immagine in input (avranno infatti il maggior numero di corrispon- denze). La Figura 2.8 mostra le corrispondenze rilevate su un’immagine d’esempio. Quando il numero di immagini nel database è molto elevato, un tipo di confronto come quello di cui si è parlato finora può essere molto dispendioso. Possono essere utilizzati approcci differenti, i quali si appoggiano su una rappresentazione anco- ra più ridotta dell’immagine basata su descrittori di dimensioni fisse. E’ il caso del modello Bag of Visual Words (BoW) [25], con il quale i descrittori vengono quantizzati in cosiddette parole visuali, definite a partire da descrittori derivati da
Figura 2.8: Esempio di corrispondenze trovate tra due immagini utilizzando BRISK. Le linee verdi mettono in relazione le corrispondenze trovate. Immagine tratta da [11]
un certo numero di immagini campione. Pe ogni immagine, viene prodotta una firma identificativa nella forma di un istogramma, che conta il numero di volte in cui una determinata parola visuale compare nell’immagine. La corrispondenza delle immagini viene quindi ottenuta tramite il confronto degli istogrammi, invece che analizzando la corrispondenza di ogni singola feature. Tuttavia, siccome la rappresentazione BoW ignora le relazioni spaziali delle feature locali, il processo descritto precedentemente (cioè il confronto a coppie seguito dal RANSAC) viene generalmente applicato per riclassificare i risultati ottenuti con l’approccio BoW.
2.3.2
Misure di accuratezza
Per stimare le prestazioni di un sistema di riconoscimento di immagini possono essere utilizzati diversi metodi. Uno degli indici di misura più utilizzati, e che viene usato anche in questa tesi, è il Mean of Average Precision (MAP). Data un’interrogazione q, la precisione media (AP) è definita come:
APq =
Pn
k=1Pq(k)rq(k)
Rq
, (2.12)
dove Pq(k) rappresenta la precisione (cioè la frazione degli elementi rilevanti recu-
rq(k) è una funzione che risulta uguale a 1 se l’elemento in posizione k è rilevan-
te per l’interrogazione e uguale a 0 altrimenti; Rq è il numero totale di elementi
rilevanti per l’interrogazione q e n è il numero totale degli elementi nella lista. Il valore medio di precisione (MAP) per un insieme Q di interrogazioni corrisponde alla media aritmetica dell’AP tra interrogazioni differenti:
M AP = PQ
q=1APq
Q , (2.13)