Object recognition: differenze tra le versioni

Versione delle 20:13, 1 feb 2010

Versione delle 20:16, 1 feb 2010

Riga 48:

=== 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ò indivuduare 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 susulla [[coda di priorità]] per l'efficiente determinazione dell'ordine di ricerca. The best candidate match for each keypoint is found by identifying its [[nearest neighbor]] in the database of keypoints from training images. The [[nearest neighbor]]s are defined as the keypoints with minimum [[Euclidean distance]] from the given descriptor vector. The probability that a match is correct can be determined by taking the ratio of distance from the closest neighbor to the distance of the second closest.

Lowe<ref name="lowe04" /> rejected all matches in which the distance ratio is greater than 0.8, which eliminates 90% of the false matches while discarding less than 5% of the correct matches. To further improve the efficiency of the best-bin-first algorithm search was cut off after checking the first 200 [[nearest neighbor]] candidates. For a database of 100,000 keypoints, this provides a speedup over exact [[nearest neighbor]] search by about 2 orders of magnitude yet results in less than a 5% loss in the number of correct matches.