Object recognition: differenze tra le versioni

Versione delle 10:55, 24 apr 2018

Versione delle 11:02, 24 apr 2018

Riga 43:

=== 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''<ref>{{en}} Beis, J., and Lowe, D.G “Shape indexing using approximate nearest-neighbour search in high-dimensional spaces”, Conference on Computer Vision and Pattern Recognition,Puerto Rico, 1997, pp. 1000–1006.</ref> che può individuare il ''[[K-nearest neighbors|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 (informaticastruttura dati)|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 il suoi vicini più prossimi nearest neighbor 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<ref name="lowe04" /> 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.