Object recognition: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Check Wikipedia using AWB |
|||
Riga 47:
=== Ricerca e indicizzazione ===
L'indicizzazione è il problema di immagazzinare i punti chiave [[Scale-invariant feature transform|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>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 [[nearest neighbor]]s 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 il suoi vicini più prossimi [[nearest neighbor]] nel database dei keypoints proveniente dalle immagini di addestramento. I [[nearest neighbor]] sono definiti come i
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.
|