Location-aided recognition

• US 9,152,882 B2
• Filed: 06/17/2011
• Issued: 10/06/2015
• Est. Priority Date: 06/17/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hedau, Varsha, Sinha, Sudipta, Zitnick, Charles Lawrence, Szeliski, Richard
• Primary Examiner(s): Desire, Gregory M
• Application Number:
  US13/162,591
• Publication Number:
  US 20120321175A1
• Time in Patent Office: 1,572 Days
• Field of Search: 382/170, 382/181, 382/195, 382/217, 382/224
• US Class Current: 1/1
• CPC Class Codes: G06F 18/2115 by evaluating different subsets according to an optimisation criterion, e.g. class separability, forward selection or backward elimination
• CPC Class Codes: G06F 18/285 Selection of pattern recognition techniques, e.g. of classifiers in a multi-classifier system
• CPC Class Codes: G06V 10/87 using selection of the recognition techniques, e.g. of a classifier in a multiple classifier system
• CPC Class Codes: G06V 2201/10 Recognition assisted with metadata

Abstract

A mobile device having the capability of performing real-time location recognition with assistance from a server is provided. The approximate geophysical location of the mobile device is uploaded to the server. Based on the mobile device'"'"'s approximate geophysical location, the server responds by sending the mobile device a message comprising a classifier and a set of feature descriptors. This can occur before an image is captured for visual querying. The classifier and feature descriptors are computed during an offline training stage using techniques to minimize computation at query time. The classifier and feature descriptors are used to perform visual recognition in real-time by performing the classification on the mobile device itself.

Claims

1. A computer-readable storage medium storing thereon processor-executable instructions that when executed perform actions, the actions comprising:

obtaining one or more feature descriptors;

determining a similarity score for each feature descriptor with respect to a captured image, the similarity score representing a closest match of a feature descriptor to an image patch in the captured image, the similarity score computed for those feature descriptors matching an image patch in the captured image, the matching feature descriptors determined by a min-hash process; and

recognizing the captured image through use of the similarity scores.

2. The computer-readable storage medium of claim 1, further comprising:

determining a geophysical location that is used to obtain the feature descriptors, the feature descriptors associated with the geophysical location.

3. The computer-readable storage medium of claim 1, further comprising:

obtaining a classifier associated with a geophysical location, the geophysical location associated with the feature descriptors; and

applying the classifier to the feature descriptors and similarity scores to determine at least one probability that the captured image pertains to a class.

4. The computer-readable storage medium of claim 1, further comprising:

rectifying the captured image prior to determination of the similarity score.

5. The computer-readable storage medium of claim 1, further comprising:

representing the similarity score as a hamming distance; and

computing the hamming distance for those feature descriptors identified as having a matching image patch.

6. A computer-readable storage medium storing thereon processor-executable instructions that when executed perform actions, the actions comprising:

obtaining one or more feature descriptors from one or more training images, the training images associated with a common geophysical location;

determining a similarity score for each feature descriptor with respect to each training image, the similarity score representing a similarity between a feature descriptor and a most similar feature descriptor amongst all feature descriptors corresponding to image patches in a training image, the matching feature descriptors determined by performing Hamming distance computations which is accelerated using a min-hash process applied to the feature descriptors with respect to a training image; and

training a classifier through use of the similarity scores.

7. The computer-readable storage medium of claim 6, further comprising:

selecting the feature descriptors from image patches in the training images having more salient features.

8. The computer-readable storage medium of claim 6, further comprising:

generating one or more random decision trees as the classifier, each random decision tree trained using the feature descriptors and the similarity scores.

9. The computer-readable storage medium of claim 6, further comprising:

representing the similarity score as a hamming distance; and

computing the hamming distance for those feature descriptors matching an image patch in a training image.

10. The computer-readable storage medium of claim 9, further comprising:

applying a min-hash method to the feature descriptors to determine those feature descriptors having similar min-hash values; and

computing the Hamming distance for those feature descriptors having similar min-hash sketches.

11. A computer-implemented method, comprising:

receiving a compact classifier and a first set of feature descriptors associated with a geophysical location;

capturing an image associated with the geophysical location, the image having an unknown class;

generating a second set of feature descriptors from the captured image;

computing minhash values for each feature descriptor in the first set with each feature descriptor in the second set;

generating a similarity score for each feature descriptor in the second set having similar minhash values with a feature descriptor in the first set; and

applying the compact classifier to the captured image based on the similarity scores to determine a class for the captured image.

12. The computer-implemented method of claim 11, further comprising:

requesting the compact classifier from a first device, the request containing the geophysical location of the first device; and

wherein the compact classifier is received by a second device remotely located from the first device.

13. The computer-implemented method of claim 11, further comprising:

wherein the compact classifier is a random decision forest including a plurality of random decision trees; and

wherein applying the compact classifier to the captured image comprises;

traversing each random decision tree based on the similarity scores of the third set of features descriptors to obtain a likelihood that the captured image matches a particular class associated with a particular one of the random decision trees.

14. The computer-implemented method of claim 13, wherein the likelihood comprises a probability distribution;

and

averaging each probability distribution for each class overall the random decision trees to determine a class likely to be associated with the captured image.

15. The computer-implemented method of claim 13,

wherein each node of a random decision tree is associated with a threshold;

and

wherein traversing each random decision tree comprises comparing a similarity score of a feature descriptor in the third set with a threshold associated with each node in a random decision tree.

16. The computer-implemented method of claim 11, wherein each feature descriptor is a BRIEF feature descriptor.

17. The computer-implemented method of claim 11, wherein identifying a third set of feature descriptors based on a similarity score further comprises:

determining a minhash value for pairs of feature descriptors, each pair including one feature descriptor from the first set and a second feature descriptor from the second set; and

computing a similarity score for pairs having similar minhash values.

18. The computer-implemented method of claim 11, wherein the similarity score is based on a Hamming distance.

19. The computer-implemented method of claim 11, wherein the compact classifier and the feature descriptors are generated through an offline training phase.

20. The computer-implemented method of claim 11, wherein the method is implemented on a mobile device.