Fundamentals of Wearable Computers and Augmented Reality, 2nd Edition

215Scalable Augmented Reality on Mobile Devices

Fast and accurately retrieving the NN of a local feature from a large database

is the key to efcient and accurate object recognition, ensuring a satisfactory user

experience and scalability for MAR apps. Two popular techniques that have been

commonly used for large-scale NN matching are locality sensitive hashing (LSH)

and bag-of-words (BoW) matching.

LSH: Locality sensitive hashing. LSH, (Gionis etal. 1999), is a widely used tech-

nique for approximate NN search. The key of LSH is a hash function, which maps

similar descriptors into the same bucket of a hash table and different descriptors in

different buckets. To nd the NN of a query descriptor, we rst retrieve its matching

bucket and then ...