# Object recognition

Nella visione artificiale, il riconoscimento di oggetti, in inglese object recognition, è la capacità di trovare un determinato oggetto in una sequenza di immagini o video. L'essere umano riconosce una moltitudine di oggetti in immagini con poco sforzo, nonostante il fatto che l'immagine degli oggetti possa variare un po' in diversi punti di vista, in diversi formati/scala o rotazione; gli oggetti possono essere riconosciuti anche quando sono parzialmente esclusi dalla vista. Questo compito è ancora una sfida per la visione artificiale (in inglese computer vision) in generale. L'informatico David Lowe ha sperimentato la visione artificiale per l'estrazione e l'utilizzo della scala invariante SIFT in modo da rendere il riconoscimento più affidabile.
Per ogni oggetto in un'immagine, ci sono molte caratteristiche, che sono caratteristiche interessanti dell'oggetto, le quali possono essere estratte in modo da fornire una descrizione "caratteristica" dell'oggetto. Questa descrizione estratta da una immagine campione può poi essere utilizzata per identificare l'oggetto durante il tentativo di individuare l'oggetto in una immagine di test contenente più oggetti. È importante che l'insieme di caratteristiche estratte dall'immagine campione sia insensibile a variazioni di scala delle immagini, i disturbi, l'illuminazione e distorsioni geometriche, in modo da rendere affidabile il riconoscimento. Il metodo brevettato di Lowe può riconoscere gli oggetti in maniera affidabile, anche tra il disordine e con occlusione parziale perché il metodo SIFT è indipendente dalla scala, orientamento, distorsione e parzialmente dai cambiamenti d'illuminazione. Questo articolo presenta il metodo di Lowe e cita alcuni concorrenti tecniche disponibili per l'object recognition in presenza di disordine e occlusione parziale.

## Metodo di Lowe

I punti chiave SIFT degli oggetti sono prima estratti da una serie di immagini di riferimento e memorizzati in un database. Un oggetto è riconosciuto in una nuova immagine confrontando singolarmente ciascun elemento della nuova immagine con quello nel database trovando quello più simile secondo la distanza euclidea delle loro caratteristiche vettoriali. Da l'intera serie di corrispondenze, insieme di punti chiave che corrispondono all'oggetto e la sua ubicazione, scala, e orientamento, sono identificate nella nuova immagine estraendo le migliori. La determinazione dei gruppi più coerenti viene eseguita rapidamente utilizzando un'efficiente hash table implementazione della trasformata di Hough generalizzata. Ogni gruppo di 3 o più caratteristiche che concordano su un oggetto e la sua posizione è poi oggetto di ulteriori verifiche e, successivamente, i peggiori vengono scartati. Infine, viene calcolata la probabilità che un determinato insieme di caratteristiche indica la presenza di un oggetto, dando la precisione di adattamento e il numero di probabili corrispondenze errate. Gli oggetti trovati che passano tutte queste prove possono essere identificati come corretti con elevata affidabilità.
| Problema | Tecnica | Vantaggio |
| localizzazione / scala / rotazione | Dog / scala - spazio piramidale / assegnazione dell'orientamento | precisione, stabilità, invarianza di scala e di rotazione |
| distorsione geometrica | Sfocatura / ricampionamento del piano di orientamento dell'immagine | invarianza affine |
| Ricerca e indicizzazione | vicino più simile / Best Bin First search | Efficienza / velocità |
| Cluster identification | voto della trasformata di Hough | Modelli affidabili |
| Verifica di un modello / individuazione di scarto | Linear least squares | Miglior tolleranza con minor corrispondenze |
| Ipotesi di accettazione | Analisi della probabilità Bayesiana | Affidabilità |

## Fasi principali
### Funzione di rilevamento a scala invariante

Il metodo Lowe per la generazione di un'immagine caratteristica chiamata Scale Invariant Feature Transform (SIFT) trasforma l'immagine in una grande collezione di caratteristiche vettoriali, ognuna delle quali è invariante rispetto a traslazione, ridimensionamento, rotazione e, in parte rispetto all'illuminazione. Tale metodo è robusto rispetto a distorsioni geometriche. Queste caratteristiche hanno proprietà simili ai neuroni del lobo occipitale, i quali vengono utilizzati per il riconoscimento di oggetti nei sistema di visione dei primati. Le posizioni dei punti chiave sono definite come massimi e minimi del risultato della differenza delle gaussiane, di una serie di immagini ottenute col sistema spazio-scala. Vengono scartati i punti a basso contrasto e i punti di bordo che si trovano lungo un bordo. Maggiore credibilità viene assegnata ai punti chiave localizzati. Queste fasi garantiscono che i punti chiave siano più stabili durante il riconoscimento. La solidità del metodo SIFT rispetto alla distorsione è quindi ottenuta considerando i pixel nell'intorno del punto chiave e sfocando e ricampionando l'immagine locale.

### Ricerca e indicizzazione

L'indicizzazione è il problema di immagazzinare i punti chiave SIFT e di individuarli in una nuova immagine. Lowe ha usato una modifica dell'algoritmo k-d tree chiamato metodo del Best-bin-first search che può individuare il nearest neighbor con elevata probabilità utilizzando solo limitate risorse di elaborazione. L'algoritmo BBF utilizza un ordinamento di ricerca modificato per il k-d tree in modo che i bins nella proprietà spazio siano ricercati in funzione della loro minima distanza dalla posizione richiesta. Questo ordine di ricerca richiede l'uso di una heap basata sulla coda di priorità per l'efficiente determinazione dell'ordine di ricerca. L'appaiamento al miglior candidato per ogni keypoint viene trovato identificando i suoi vicini più prossimi nel database dei keypoints proveniente dalle immagini di addestramento. I nearest neighbors sono definiti come i keypoints con la minima distanza euclidea da un dato vettore descrittivo. La probabilità che un appaiamento sia corretto può essere determinata tramite il rapporto delle distanze con i due vicini più prossimi.
Lowe rigetta tutti gli accoppiamenti in cui il rapporto di distanza è superiore a 0.8, il che elimina 90% dei falsi accoppiamenti pur compromettendo meno del 5% degli appaiamenti corretti. Per migliorare ulteriormente l'efficienza dell'algoritmo di ricerca best-bin-first viene effettuato un cutoff dopo i primi 200 candidati nearest neighbor. Per un database di 100,000 keypoints, tutto ciò porta ad una velocizzazione sulla ricerca del corretto nearest neighbor di circa due ordini di grandezza compromettendo meno del 5% sul numero dei corretti accoppiamenti.

## Applicazioni

I metodi di riconoscimento di oggetti trovano le seguenti applicazioni:
* panorami di immagini;
* watermark di immagini;
* localizzazione di robot globale.