Content-based image search

• US 9,710,491 B2
• Filed: 11/02/2009
• Issued: 07/18/2017
• Est. Priority Date: 11/02/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Li, Yi, Ke, Qifa, Liu, Ming
• Primary Examiner(s): Choi, Carol
• Application Number:
  US12/610,810
• Publication Number:
  US 20110106782A1
• Time in Patent Office: 2,815 Days
• Field of Search: 707742, 707706, 707999003
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

Image descriptor identifiers are used for content-based search. A plurality of descriptors is determined for an image. The descriptors represent the content of the image at respective interest points identified in the image. The descriptors are mapped to respective descriptor identifiers. The image can thus be represented as a set of descriptor identifiers. A search is performed on an index using the descriptor identifiers as search elements. A method for efficiently searching the inverted index is also provided. Candidate images that include at least a predetermined number of descriptor identifiers that match those of the image are identified. The candidate images are ranked and at least a portion thereof are presented as content-based search results.

Claims

1. A computer-implemented method for searching a plurality of images, the method comprising:

receiving a search query that includes an image;

identifying, by a computing device, a plurality of first descriptor identifiers based on the search query, each of the first descriptor identifiers comprising an identifier used to identify a respective descriptor, each descriptor having been calculated over a respective portion of the image comprising a subset of pixels of the image that includes a respective interest point in the image;

searching a plurality of indexed images in a search engine inverted index by comparing one or more of the first descriptor identifiers to one or more second descriptor identifiers associated with the indexed images to identify one or more candidate images, wherein the searching comprises;

traversing the search engine inverted index to identify a predetermined number of second descriptor identifiers having location identifiers with lowest values;

identifying an end-of-document location identifier that follows a largest location identifier value of the predetermined number of second descriptor identifiers having the location identifier with lowest values;

identifying a start-of-document location value for a candidate indexed image that is identified by the end-of-document location identifier; and

returning the candidate indexed image as a candidate image based on determining the location identifiers of all of the predetermined number of second descriptor identifiers having the lowest location identifier values are greater than or equal to the start-of-document location value; and

ranking the one or more candidate images.

2. The computer-implemented method of claim 1, wherein the search query includes one or more textual words.

3. The computer-implemented method of claim 1, wherein the search engine inverted index is based on a flat index location space in which the second descriptor identifiers for each of the plurality of indexed images are listed sequentially with an end-of-document identifier following the second descriptor identifiers for each indexed image, and each second descriptor identifier and end-of-document identifier includes a location identifier that indicates their respective location in the flat index location space.

4. The computer-implemented method of claim 1, wherein the predetermined number of second descriptor identifiers is increased based on a minimum total number of matching second descriptor identifiers for a candidate image in a group of candidate images.

5. The computer-implemented method of claim 1, wherein the one or more candidate images are ranked based at least in part on one or more selected from the following:

a term frequency ranking score, a geometric verification, or a two-dimensional image transformation including one or more of a similarities transformation and an affine transformation.

6. The computer-implemented method of claim 5, wherein the one or more candidate images are also ranked based on one or more selected from the following:

image quality, metadata associated with one or more of the indexed images, and extracted data that is extracted and aggregated from a web page in which the indexed image is published.

7. The computer-implemented method of claim 1, further comprising:

associating at least one of the first descriptor identifiers with a textual word; and

performing a text-based search query using the textual word.

8. One or more computer storage memory storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations comprising:

receiving a search query;

identifying a plurality of first descriptor identifiers based on the search query;

searching a plurality of indexed images in a search engine inverted index by comparing one or more of the first descriptor identifiers to one or more second descriptor identifiers associated with the indexed images to identify one or more candidate images, each of the one or more second descriptor identifiers comprising an identifier used to identify a respective descriptor, each descriptor having been calculated over a respective portion of a respective indexed image comprising a subset of pixels of the respective indexed image that includes a respective interest point in the respective indexed image, wherein the searching comprises;

traversing the search engine inverted index to identify a predetermined number of second descriptor identifiers having location identifiers with lowest values;

identifying an end-of-document location identifier that follows a largest location identifier value of the predetermined number of second descriptor identifiers having the location identifier with lowest values;

identifying a start-of-document location value for a candidate indexed image that is identified by the end-of-document location identifier; and

returning the candidate indexed image as a candidate image based on determining the location identifiers of all of the predetermined number of second descriptor identifiers having the lowest location identifier values are greater than or equal to the start-of-document location value; and

ranking the one or more candidate images.

9. The one or more computer storage memory of claim 8, wherein the search query includes one or more textual words.

10. The one or more computer storage memory of claim 8, wherein the search query includes one or more images.

11. The one or more computer storage memory of claim 8, wherein the search engine inverted index is based on a flat index location space in which the second descriptor identifiers for each of the plurality of indexed images are listed sequentially with an end-of-document identifier following the second descriptor identifiers for each indexed image, and each second descriptor identifier and end-of-document identifier includes a location identifier that indicates their respective location in the flat index location space.

12. The one or more computer storage memory of claim 8, wherein the predetermined number of second descriptor identifiers is increased based on a minimum total number of matching second descriptor identifiers for a candidate image in a group of candidate images.

13. The one or more computer storage memory of claim 8, wherein the one or more candidate images are ranked based at least in part on one or more selected from the following:

a term frequency ranking score, a geometric verification, or a two-dimensional image transformation including one or more of a similarities transformation and an affine transformation.

14. The one or more computer storage memory of claim 13, wherein the one or more candidate images are also ranked based on one or more selected from the following:

image quality, metadata associated with one or more of the indexed images, and extracted data that is extracted and aggregated from a web page in which the indexed image is published.

15. The one or more computer storage memory of claim 8, the operations further comprising:

associating at least one of the first descriptor identifiers with a textual word; and

performing a text-based search query using the textual word.

16. A computer device comprising:

one or more processors; and

one or more computer storage devices storing computer-useable instructions that, when used by the one or more processors, cause the one or more processors to;

identify a plurality of first descriptor identifiers based on a search query;

search a plurality of indexed images in a search engine inverted index by comparing one or more of the first descriptor identifiers to one or more second descriptor identifiers associated with the indexed images to identify one or more candidate images, each of the one or more second descriptor identifiers comprising an identifier used to identify a respective descriptor, each descriptor having been calculated over a respective portion of a respective indexed image comprising a subset of pixels of the respective indexed image that includes a respective interest point in the respective indexed image, wherein the searching comprises;

traversing the search engine inverted index to identify a predetermined number of second descriptor identifiers having location identifiers with lowest values;

identifying an end-of-document location identifier that follows a largest location identifier value of the predetermined number of second descriptor identifiers having the location identifier with lowest values;

identifying a start-of-document location value for a candidate indexed image that is identified by the end-of-document location identifier; and

return the candidate indexed image as a candidate image based on determining the location identifiers of all of the predetermined number of second descriptor identifiers having the lowest location identifier values are greater than or equal to the start-of-document location value; and

rank the one or more candidate images.

17. The computer device of claim 16, wherein the search query includes one or more textual words and/or one or more images.

18. The computer device of claim 16, wherein the search engine inverted index is based on a flat index location space in which the second descriptor identifiers for each of the plurality of indexed images are listed sequentially with an end-of-document identifier following the second descriptor identifiers for each indexed image, and each second descriptor identifier and end-of-document identifier includes a location identifier that indicates their respective location in the flat index location space.

19. The computer device of claim 16, wherein the predetermined number of second descriptor identifiers is increased based on a minimum total number of matching second descriptor identifiers for a candidate image in a group of candidate images.

20. The computer device of claim 16, wherein the one or more candidate images are ranked based at least in part on one or more selected from the following:

a term frequency ranking score, a geometric verification, a two-dimensional image transformation including one or more of a similarities transformation and an affine transformation, image quality, metadata associated with one or more of the indexed images, and extracted data that is extracted and aggregated from a web page in which the indexed image is published.