EFFICIENT IMAGE MATCHING

• US 20100284604A1
• Filed: 05/05/2009
• Published: 11/11/2010
• Est. Priority Date: 05/05/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chrysanthakopoulos, Georgios
• Granted Patent: US 8,630,489 B2
• Time in Patent Office: Days
• US Class Current: 382/153
• 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:

a) receiving an image;

b) extracting a plurality of features from the image received at act a), wherein a feature is a representation of a portion of an image;

c) 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;

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

e) comparing the first global signature created at act c) with the first plurality of global signatures in the data repository;

f) determining that a first image in the plurality of images most closely matches the image received at act a) based at least in part upon the comparison of act e); and

g) outputting an indication that the first image most closely matches the image received at act a).

2. The method of claim 1, further comprising:

h) comparing the plurality of features extracted at act b) with a plurality of features that correspond to the plurality of images in the data repository, wherein each of the images in the data repository has at least one feature corresponding thereto; and

i) determining that the first image in the plurality of images most closely matches the image received at act a) based at least in part upon the comparison of act h).

3. The method of claim 1, further comprising:

h) generating a second global signature responsive to receipt of the image, wherein the second global signature is representative of symmetry in the image received at act a);

i) 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

j) determining that the first image in the plurality of images most closely matches the image received at act a) based at least in part upon the comparison of act i).

4. The method of claim 1, further comprising:

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

i) 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

j) determining that the first image in the plurality of images most closely matches the image received at act a) based at least in part upon the comparison of act i).

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

6. The method of claim 1, wherein the plurality of features extracted at act b) are vectors that comprise N entries.

7. The method of claim 6, 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 at act b).

8. The method of claim 6, 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 at act b).

9. The method of claim 1, further comprising:

h) generating a plurality of global signatures that are representative of the image received at act a), 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;

i) 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

j) determining which of the plurality of images most closely matches the image received at act a).

10. The method of claim 9, further comprising:

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

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

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

m) 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

n) modifying the weights based at least in part upon the reviewing of act m).

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

13. The method of claim 1, further comprising:

h) prior to act f), determining a threshold number of M images that most closely match the image received at act a);

i) comparing the plurality of features corresponding to the image received at act a) with features corresponding to the Mimages; and

j) determining which of the M images most closely matches the image received at act a) based at least in part upon the comparing of act i).

14. The method of claim 1, further comprising:

h) causing a robotic device to move in a particular direction based at least in part upon the image determined to be the closest match to the image received at act a).

15. 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 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; and

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.

16. The system of claim 15, 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.

17. The system of claim 15, further comprising:

a feature extractor component that extracts a first plurality of features from the first image, wherein a feature is a representation of a portion of an image, wherein the comparer component compares the first plurality of features with a second plurality of features that correspond to the second image, wherein the output component outputs the indication of similarity between the first image and the second image based at least in part upon the comparison undertaken by the comparer component.

18. The system of claim 17, 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 comparison between the first feature signature and a second feature signature that corresponds to the second image, wherein the second feature signature is based at least in part upon the second plurality of features, 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 comparison between the feature signature and the second feature signature undertaken by the comparer component.

19. The system of claim 15, 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 comparison between the first color global signature for the first image and a second color global signature that corresponds to the second image, wherein the output component outputs the indication of similarity between the first image and the second image based at least in part upon the comparison undertaken by the comparer component.

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

receive a first image;

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

generating a first global signature, 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, 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, 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 corresponding to a plurality of images, wherein data for each image comprises features and global signatures that correspond to a plurality of other images;

comparing the first, second, and third global signatures with global signatures in the data repository;

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 global signatures in the data repository;

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

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