Content-based image search

Patent metadata

Field	Value
Publication number	US-9710491-B2
Application number	US-61081009-A
Country	US
Kind code	B2
Filing date	Nov 2, 2009
Priority date	Nov 2, 2009
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

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.

First claim

The invention claimed is:

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 b

Assignees

• Ke Qifa
• Liu Ming
• Li Yi
• Microsoft Technology Licensing Llc

Inventors

• Ke Qifa
• Liu Ming
• Li Yi

Classifications

• G06F16/951

  Indexing; Web crawling techniques · CPC title

• G06F16/5838 Primary

  using colour · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F16/3329

  Natural language query formulation · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title