CONTENT-BASED IMAGE SEARCH

• US 20110106782A1
• Filed: 11/02/2009
• Published: 05/05/2011
• Est. Priority Date: 11/02/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: LI, YI, KE, QIFA, LIU, MING
• Granted Patent: US 9,710,491 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• 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;

identifying, by a computing device, at least one first descriptor identifier based on the search query, wherein the at least one first descriptor identifier corresponds to a descriptor that describes an interest point in an image;

searching a plurality of indexed images by comparing the at least one first descriptor identifier to one or more second descriptor identifiers associated with each of the indexed images; and

ranking one or more of the indexed images based on the comparison.

2. The computer-implemented method of claim 1, wherein the search query comprises an image.

3. The computer-implemented method of claim 1, wherein one or more candidate images are identified from a search engine inverted index, and wherein the 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 3, wherein searching the plurality of indexed images by comparing the at least one first descriptor identifier to the one or more second descriptor identifiers associated with each of the indexed images, further comprises:

traversing the index to identify a predetermined number of second descriptor identifiers having the location identifiers with the lowest value;

identifying the end-of-document location identifier that follows a largest location identifier value of the predetermined number of second descriptor identifiers having the lowest location identifier 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 when the location identifiers of all of the predetermined number of descriptor identifiers having the lowest location identifier values are greater than or equal to the start-of-document location value;

or

when the location identifiers of one or more of the predetermined number of second descriptor identifiers having the lowest location identifier values are less than the start-of-document location value, identifying the next lowest location identifier value that is not less than the start-of-document location value for at least one of the one or more of the predetermined number of second descriptor identifiers.

5. The computer-implemented method of claim 4, 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.

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

re-ranking the one or more indexed images based on one or more of 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.

7. The computer-implemented method of claim 6, wherein re-ranking the one or more indexed images is also based on one or more of 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.

8. The computer-implemented method of claim 1, wherein the search query includes a textual word, and wherein identifying the at least one first descriptor identifier comprises identifying one or more descriptor identifiers associated with the textual word.

10. One or more computer-readable media having computer-readable instructions embodied thereon that, when executed, perform a method for generating a representation of the content of an image for content-based image searching, the method comprising:

receiving an image;

identifying a plurality of interest points in the image, wherein an interest point comprises one of a point, a region, or an area in the image that is identified by an operator algorithm;

determining an image patch for one or more of the interest points that includes an area of the image inclusive of the respective interest point;

determining a descriptor for each patch;

mapping each descriptor to a descriptor identifier; and

representing the image as a set of descriptor identifiers based on the mapping.

9. The computer-readable media of claim 11, further comprising:

associating the at least one first descriptor identifier with a textual word;

performing a text-based search query using the textual word based on the one or more descriptor identifiers associated with the textual word.

11. The computer-readable media of claim 10, further comprising:

indexing the descriptor identifiers for the image.

12. The computer-readable media of claim 10, further comprising:

normalizing the image patches for each of the interest points to provide all of the patches in an equal size.

13. The computer-readable media of claim 10, wherein the operator algorithm is one or more of a difference of Gaussians or a Laplacian algorithm.

14. The computer-readable media of claim 10, wherein the patch is centered on the interest point and the size of the patch is determined from an output of the operator algorithm.

15. The computer-readable media of claim 10, wherein determining a descriptor for each patch further comprises:

determining a vector that represents the pixels contained in the patch.

16. The computer-readable media of claim 10, wherein mapping each descriptor to a descriptor identifier employs a quantization table that includes one or more representative descriptors associated with a respective descriptor identifier, and each descriptor is mapped to one or more representative descriptors that it matches or nearly matches.

17. The computer-readable media of claim 10, further comprising:

ranking each of the plurality of interest points based on a metric; and

selecting a subset of the plurality of interest points for further processing based on the ranking.

18. The computer-readable media of claim 17, wherein the metric includes one or more of a signal strength and a signal to noise ratio for the interest point.

19. The computer-readable media of claim 10, further comprising:

mapping one or more of the descriptor identifiers to one or more textual words.

20. A method of associating paid search results with algorithmic image-based search results, comprising the steps of:

receiving a search query;

a computing device identifying at least one descriptor identifier forming a first set of descriptor identifiers based on the search query, wherein each descriptor identifier corresponds to a descriptor that describes an image-based point of interest;

searching a plurality of indexed images by comparing the first set of descriptor identifiers with a second set of descriptor identifiers associated with the indexed images to generate search results;

associating at least one paid search listing with at least one of the descriptor identifiers in the first set to generate at least one paid search result.