Efficient image matching

• US 8,630,489 B2
• Filed: 05/05/2009
• Issued: 01/14/2014
• Est. Priority Date: 05/05/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chrysanthakopoulos, Georgios
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): TORRES, JOSE
• Application Number:
  US12/435,447
• Publication Number:
  US 20100284604A1
• Time in Patent Office: 1,715 Days
• Field of Search: 382/153, 382/165, 382/170, 382/195, 382/218, 382/305, 382/190, 901/1, 707/706, 707E17019-E17025
• US Class Current: 382/190
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A system described herein includes a receiver component that receives a first image and a symmetry signature generator component that generates a first global symmetry signature for the image, wherein the global symmetry signature is representative of symmetry existent in the first image. The system also includes a comparer component that compares the first global symmetry signature with a second global symmetry signature that corresponds to a second image, wherein the second global symmetry signature is representative of symmetry existent in the second image. The system additionally includes an output component that outputs an indication of similarity between the first image and the second image based at least in part upon the comparison undertaken by the comparer component.

Claims

1. A method comprising the following computer-executable acts:

receiving an image;

extracting a plurality of features from the image, wherein a feature is a representation of a portion of an image;

creating a first global signature of the image based at least in part upon the plurality of features extracted from the image, wherein a global signature is a representation of an entirety of an image;

accessing a data repository that comprises a first plurality of global signatures that are representative of a corresponding plurality of images;

comparing the first global signature with the first plurality of global signatures in the data repository;

identifying a subset of images from the plurality of images based upon the comparing of the first global signature with the first plurality of global signatures, wherein a number of images in the subset of images is less than a number of images in the plurality of images;

subsequent to the identifying of the subset of images from the plurality of images, comparing the plurality of features extracted from the image with a plurality of features that correspond to the subset of images;

determining that a first image in the subset of images most closely matches the image based at least in part upon the comparing of the first global signature with the first plurality of global signatures and the comparing of the plurality of features extracted from the image with the plurality of features that correspond to the subset of images;

outputting an indication that the first image most closely matches the image.

2. The method of claim 1, further comprising:

generating a second global signature responsive to receipt of the image, wherein the second global signature is representative of symmetry in the image;

comparing the second global signature with a second plurality of global signatures retained in the data repository, wherein the second plurality of global signatures are representative of the corresponding plurality of images, wherein the second plurality of global signatures are representative of symmetries in the plurality of images; and

identifying the subset of images from the plurality of images based at least in part upon the comparing of the second global signature with the second plurality of global signatures.

3. The method of claim 2, further comprising:

generating a third global signature responsive to receipt of the image, wherein the third global signature is representative of colors existent in the image;

comparing the third global signature with a third plurality of global signatures retained in the data repository, wherein the third plurality of global signatures are representative of the corresponding plurality of images, wherein the third plurality of global signatures are representative of colors existent in the plurality of images; and

identifying the subset of images from the plurality of images based at least in part upon the comparing of the third global signature with the third plurality of global signatures.

4. The method of claim 3, wherein the third global signature is a color histogram and the third plurality of global signatures are color histograms.

5. The method of claim 1, wherein the plurality of features extracted from the image are vectors that comprise N entries.

6. The method of claim 5, wherein the first global signature comprises a first vector that comprises N entries, wherein each of the entries in the first vector is an average value of corresponding entries in the plurality of features extracted from the image.

7. The method of claim 5, wherein the first global signature comprises a second vector that comprises N entries, wherein each of the entries in the second vector is a standard deviation of values in corresponding entries in the plurality of features extracted from the image.

8. The method of claim 1, further comprising:

generating a plurality of global signatures that are representative of the image, wherein each of the plurality of images has global signatures that correspond to the generated plurality of global signatures that are retained in the data repository, wherein each type of global signature is assigned a weight;

comparing each of the plurality of generated global signatures with corresponding global signatures retained in the data repository, wherein the comparing takes into consideration weights assigned to each type of global signature; and

identifying the subset of images from the plurality of images based at least in part upon the comparing of each of the plurality of generated global signatures with the corresponding global signatures retained in the data repository.

9. The method of claim 8, further comprising:

automatically assigning weights to each of the types of global signature.

10. The method of claim 9, wherein automatically assigning weights to each of the types of global signature comprises:

locating a threshold number of images that most closely match the image using first weights assigned to the types of global signatures;

reviewing known correlations between images in the threshold number of images to ascertain whether the images in the threshold number of images were properly selected; and

modifying the weights based at least in part upon the reviewing of the known correlations.

11. The method of claim 1 configured for execution in a mobile robotic device.

12. The method of claim 1, further comprising:

causing a robotic device to move in a particular direction based at least in part upon the first image most closely matching the image.

13. A system comprising the following computer-executable components:

a receiver component that receives a first image;

a symmetry signature generator component that generates a first global symmetry signature for the image, wherein the global symmetry signature is representative of symmetry existent in the first image;

a comparer component that performs a first comparison of the first global symmetry signature with a plurality of global symmetry signatures that correspond to a respective plurality of images, wherein the plurality of global symmetry signatures are respectively representative of symmetries existent in the plurality of images, wherein the comparer component identifies a subset of images in the plurality of images based at least in part upon the first comparison, wherein a number of images in the subset of images is less than a number of images in the plurality of images, and wherein the comparer component, subsequent to identifying the subset of images, performs a second comparison of a first plurality of features of the first image with features that respectively correspond to the subset of images and identifies a second image from the subset of images that most closely matches the first image based upon the second comparison, wherein a feature is representative of a portion of a respective image; and

an output component that outputs an indication of similarity between the first image and the second image.

14. The system of claim 13, further comprising a controller component that controls motion of a robotic device based at least in part upon the indication of similarity output by the output component.

15. The system of claim 13, further comprising:

a feature extractor component that extracts the first plurality of features from the first image.

16. The system of claim 15, further comprising:

a feature signature generator component that generates a first feature signature for the first image, wherein the first feature signature for the first image is based at least in part upon the first plurality of features extracted from the first image, wherein the comparer component undertakes a third comparison between the first feature signature and feature signatures that respectively correspond to the plurality of images, and wherein the output component outputs the indication of similarity between the first image and the second image based at least in part upon the third comparison.

17. The system of claim 13, further comprising:

a color global signature generator component that generates a first color global signature for the first image, wherein the first color global signature is representative of color existent in the first image, wherein the comparer component undertakes a third comparison between the first color global signature for the first image and global signatures that respectively correspond to the plurality of images, wherein the output component outputs the indication of similarity between the first image and the second image based at least in part upon the third comparison.

18. A computing device comprising a computer-readable medium, the computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a first image;

responsive to receiving the first image, generating a first plurality of features for the first image, wherein a feature is representative of a portion of an image;

generating a first global signature for the first image, wherein the first global signature is representative of an entirety of the first image, wherein the first global signature is based at least in part upon the first plurality of features;

generating a second global signature for the first image, wherein the second global signature is representative of the entirety of the first image, wherein the second global signature is based at least in part upon symmetries in the first image;

generating a third global signature for the first image, wherein the third global signature is representative of the entirety of the first image, wherein the third global signature is based at least in part upon colors existent in the first image;

accessing a data repository that comprises data respectively corresponding to a plurality of images, wherein data for each image comprises features and global signatures that respectively correspond to the plurality of images;

comparing the first, second, and third global signatures with respective global signatures in the data repository that correspond to the plurality of images;

selecting a subset of the plurality of images based at least in part upon the comparing of the first, second, and third global signatures with the respective global signatures in the data repository, wherein a number of images in the subset of images is less than a number of images in the plurality of images;

comparing the features of the first image with features that respectively correspond to images in the subset of images; and

outputting a second image that most closely matches the first image based at least in part upon the comparing of the features of the first image with the features that respectively correspond to the subset of images.

19. The computing device of claim 18 being a mobile robotic device.

20. The computing device of claim 19, the acts further comprising:

controlling movement of the mobile robotic device based at least in part upon the second image most closely matching the first image.