Spatial Image Index and Associated Updating Functionality

• US 20120155778A1
• Filed: 12/16/2010
• Published: 06/21/2012
• Est. Priority Date: 12/16/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Buchmueller, Daniel, Kroepfl, Michael, Nister, David Z., Aguera-Arcas, Blaise Hilary, Fynn, Scott V., Ofek, Eyal, Cugunovs, Vadim
• Granted Patent: US 8,971,641 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content

Abstract

An image matching system is described for finding reference images which match a query image. The image matching system performs this operation in expeditious fashion by restricting the matching to a bounding region; the bounding region, in turn, may be associated with a location at which the query image may have been captured. In addition, the image matching system provides various mechanisms that expedite adding new reference images to an image index, to thereby provide a re-enforced learning mechanism of the image matching system.

Claims

1. A method, using a physical image matching system, for performing a search based on a query image, comprising:

receiving a query image;

receiving location information which indicates a location that is associated with the query image;

identifying a bounding region associated with the location, based on the location information;

identifying, using an index, a set of candidate reference images that match the query image and the bounding region;

performing verification analysis to identify at least one final matching image, selected from among the candidate reference images, that successfully matches the query image; and

updating the index to include at least one image information entry that corresponds, respectively, to said at least one final matching image that successfully matches the query image.

2. The method of claim 1, wherein the query image comprises a digital image produced by a mobile computing device at the location.

3. The method of claim 1, wherein said identifying of the set of candidate images comprises:

generating quantized features based on the query image; and

using the quantized features, together with the index, to identify the set of candidate reference images.

4. The method of claim 3, further comprising producing the quantized features using a vocabulary tree.

5. The method of claim 1, wherein said performing verification analysis comprises:

generating non-quantized features based on the query image; and

using the non-quantized features to identify said at least one final matching image by performing pair-wise comparison of the query image with each of the set of candidate reference images.

6. The method of claim 5, further comprising:

receiving orientation information which indicates an orientation of a device that captured the query image; and

using the orientation information to refine matching performed by the verification analysis.

7. The method of claim 1, wherein the query image is captured in a capture session in which plural query images are captured, and wherein said updating occurs prior to capture of a next query image among the plural query images.

8. The method of claim 1, wherein, for a particular final matching image, said updating comprises:

distributing an image information entry, which corresponds to the final matching image, to an image bucket, selected from a plurality of image buckets;

determining whether the image bucket has received a bucket set comprising a predetermined number of image information entries;

if the image bucket has received the predetermined number of image information entries, forwarding the bucket set to at least one associated index server; and

updating, by said at least one index server, a portion of the index based on the bucket set.

9. The method of claim 1, further comprising updating relationship information to describe at least one relationship between the query image and said at least one final matching image.

10. The method of claim 1, further comprising using a temporary index server to receive a set of new reference images, wherein the temporary index server performs pair-wise verification analysis between the query image and any reference image in the set of new reference images that is associated with the bounding region, without use of the index.

11. An index updating module, implemented by physical data processing functionality, comprising:

a receiving module configured to receive image information entries corresponding to a plurality of corresponding new images to be added to an index;

a distribution module configured to distribute the image information entries to image buckets;

a forwarding module configured to;

determine whether any image bucket has received a bucket set comprising a predetermined number of image information entries;

if any image bucket has received the predetermined number of image information entries, forward the bucket set provided by the image bucket to at least one associated index server; and

said at least one associated index server updating a portion of the index based on the bucket set.

12. The index updating module of claim 11, wherein the new images to be added to the index correspond to query images that have been previously determined to match at least one reference image, indentified by the index.

13. The index updating module of claim 11, wherein the distribution module is configured to distribute the image information entries such that two consecutively-captured new images provide image information entries that are distributed to two different respective image buckets.

14. The index updating module of claim 11, wherein the predetermined number of image information entries is set so that updating of the index occurs in less than one minute.

15. The index updating module of claim 11, further comprising a temporary index server management module configured to forward the image information entries to a temporary index server.

16. The index updating module of claim 15, wherein the temporary index server management module is configured to remove each image information entry from the temporary index server after a prescribed amount of time.

17. A physical and tangible computer readable medium for storing computer readable instructions, the computer readable instructions providing an image matching system when executed by one or more processing devices, the computer readable instructions comprising:

logic configured to receive a query image;

logic configured to identify at least one final matching image, using an index, based on the query image, each final matching image associated with an image information entry; and

logic configured to update the index, for each final matching image, to include the image information entry,

the query image being captured in a capture session in which plural query images are captured, and wherein said logic configured to update is configured to update the index prior to capture of a next query image among the plural query images.

18. The computer readable medium of claim 17, wherein said logic configured to identify is configured to identify said at least one final matching image from a subset of reference images that are associated with a defined bounding region.

19. The computer readable medium of claim 17, wherein said logic configured to identify comprises:

logic configured to identify, using the index, a set of candidate reference images that match the query image; and

logic configured to identify, based on verification analysis, said at least one final matching image from among the set of candidate reference images.

20. The computer readable medium of claim 17, wherein the logic configured to update comprises:

logic configured to distribute each image information entry to an image bucket, selected from a plurality of image buckets;

logic configured to determine whether the image bucket has received a bucket set comprising a predetermined number of image information entries; and

logic configured to forward, if the image bucket has received the predetermined number of image information entries, the bucket set to at least one associated index server,

said at least one index server updating a portion of the index based on the bucket set.