SIMILAR IMAGE RETRIEVAL

• US 20150169740A1
• Filed: 08/23/2012
• Published: 06/18/2015
• Est. Priority Date: 11/21/2011
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Stewenius, Henrik C., Gunderson, Steinar H., Pilet, Julien
• Application Number:
  US13/593,420
• Publication Number:
  US 20150169740A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for determining image search results. One of the methods includes receiving a query image. Multiple feature vectors from the query image are computed and quantized into one or more respective visual words. Multiple posting lists are identified, each posting list corresponding to a quantized visual word, each posting list identifying images that have the visual word, each identified image being associated with geometry data for the corresponding visual word. One or more matching images are identified that match the query image by before traversing the multiple posting lists more than once. While traversing the multiple posting lists, a score is computed for each matching image when identified as a matching image and before traversal of the multiple posting lists is complete.

Claims

1. A computer-implemented method for computing a score for an image by traversing multiple posting lists in parallel comprising:

receiving a query image;

determining a plurality of visual words from the query image;

identifying multiple posting lists for the plurality of visual words, including identifying a respective posting list for each of the visual words from the query image, each posting list comprising respective items that each identify an indexed image that has the visual word corresponding to the posting list, wherein each item of a particular posting list is associated with geometry data for a corresponding particular visual word from an indexed image identified by the item, and wherein each of the posting lists has a respective item cursor that designates a current posting list item in the posting list;

advancing a particular item cursor for one of the multiple posting lists by updating the item cursor of a particular posting list from designating a first item in the particular posting list to designating a subsequent item in the particular posting list;

determining a count of item cursors designating posting list items that identify a same particular indexed image, wherein the count of item cursors represents a number of visual words from the indexed image that match visual words from the query image;

determining that the count of item cursors designating posting list items that identify a same particular indexed image satisfies a threshold;

in response to determining that the count of item cursors designating items that identify a same particular indexed image satisfies a threshold, identifying geometry data associated with the items that identify the same particular indexed image, wherein the geometry data is geometry data for visual words from the particular indexed image;

computing a score for the particular indexed image before advancing to an end of the particular posting list, including comparing the visual words from the query image to the visual words from the particular indexed image using the geometry data associated with the items that identify the same particular indexed image; and

ranking the particular indexed image relative to one or more other images using the computed score.

2. The method of claim 1, wherein computing a score for the particular indexed image comprises computing a score for the particular indexed image before further advancing any item cursors for the posting lists.

3. The method of claim 1, wherein computing a score for the particular indexed image comprises computing a score for the particular indexed image before advancing to the end of any of the posting lists.

4. The method of claim 1, wherein advancing a particular posting list of the posting lists comprises:

advancing an item cursor of a posting list identified by a root node of a tree structure for the posting lists being traversed, wherein each leaf node of the tree structure corresponds to a posting list being traversed and includes a document identifier of a document identified by an item in the corresponding posting list, wherein items in each posting list are sorted by document identifier; and

updating a leaf node corresponding to the particular posting list with a first document identifier of a first document identified by the subsequent item in the particular posting list.

5. The method of claim 4, further comprising:

updating, for each particular parent node ascendant from the leaf node corresponding to the particular posting list, (1) a least-advanced document identifier among document identifiers of leaf nodes descendent from the particular parent node, a count of leaf nodes descendent from the particular parent node that identify the least-advanced document identifier, and (3) a list identifier of a posting list having a leaf node associated with the least-advanced document identifier.

6. The method of claim 1, further comprising weighting the computed score by a weight based on a computed feature space density of a feature cell for the corresponding visual word.

7. The method of claim 5, wherein updating each particular parent node comprises updating the parent node using at least one conditional move instruction.

8. The method of claim 7, wherein updating the parent node using at least one conditional move instruction comprises:

generating a sum node with elements of a child node of two or more child nodes of the parent node being updated, wherein a count element of the sum node is a sum of count elements of the two or more child nodes of the parent node that is being updated;

determining that the image identifier of a first child node of the two or more child nodes is less than an image identifier of a second child node of the two or more child nodes; and

moving, using the conditional move instruction, the contents of the first child node into the parent node.

9. The method of claim 7, wherein updating the parent node using at least one conditional move instruction comprises:

generating a sum node with elements of a child node of two or more child nodes of the parent node being updated, wherein a count element of the sum node is a sum of count elements of the two or more child nodes of the parent node that is being updated;

determining whether the image identifier of a first child node of the two or more child nodes is equal to an image identifier of a second child node of the one or more child nodes; and

moving, using the conditional move instruction, the contents of the sum node into the parent node.

10. The method of claim 6, further comprising:

computing the feature space density of the feature cell including;

quantizing each of a plurality of feature vectors into a corresponding feature cell; and

computing a size of each feature cell, wherein the feature space density is based at least in part on dividing a number of feature vectors quantized to the feature cell by the computed size of the feature cell.

11. The method of claim 10, wherein computing a size of each feature cell comprises computing respective distances between a cell center and feature vectors quantized to the feature cell.

12. A computer-implemented method comprising:

receiving a query image;

computing multiple feature vectors from the query image and quantizing each feature vector into one or more respective visual words;

identifying multiple posting lists, one posting list for each computed visual word, wherein each posting list is a list of items having document identifiers for respective images that are assigned a same visual word, wherein each of the multiple posting lists is associated with a respective cursor, wherein each cursor identifies an item on a corresponding posting list, wherein each item on the posting list is associated with geometry data for a visual word computed from an image identified by the document identifier of the item;

traversing the multiple posting lists by repeatedly;

selecting one of the cursors as a current cursor;

advancing a posting list of the current cursor by updating the cursor to identify a subsequent item on the posting list of the current cursor;

determining a count of cursors of the multiple posting lists that identify a same particular document identifier;

determining whether the count of cursors that identify the same particular document identifier satisfies a threshold;

computing a score for an image corresponding to the particular document identifier if the count of cursors that identify the same particular document identifier satisfies a threshold, wherein the score is based at least in part on the geometry data associated with posting list items that identify the particular document identifier, and wherein the score is computed before advancing to an end of the posting list of the current cursor; and

ranking the image corresponding to the same document identifier relative to one or more other images by respective computed scores.

13. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a query image;

determining a plurality of visual words from the query image;

identifying multiple posting lists for the plurality of visual words, including identifying a respective posting list for each of the visual words from the query image, each posting list comprising respective items that each identify an indexed image that has the visual word corresponding to the posting list, wherein each item of a particular posting list is associated with geometry data for a corresponding particular visual word from an indexed image identified by the item, and wherein each of the posting lists has a respective item cursor that designates a current posting list item in the posting list;

advancing a particular item cursor for one of the multiple posting lists by updating the item cursor of a particular posting list from designating a first item in the particular posting list to designating a subsequent item in the particular posting list;

determining a count of item cursors designating posting list items that identify a same particular indexed image, wherein the count of item cursors represents a number of visual words from the indexed image that match visual words from the query image;

determining that the count of item cursors designating posting list items that identify a same particular indexed image satisfies a threshold;

in response to determining that the count of item cursors designating items that identify a same particular indexed image satisfies a threshold, identifying geometry data associated with the items that identify the same particular indexed image, wherein the geometry data is geometry data for visual words from the particular indexed image;

computing a score for the particular indexed image before advancing to an end of the particular posting list, including comparing the visual words from the query image to the visual words from the particular indexed image using the geometry data associated with the items that identify the same particular indexed image; and

ranking the particular indexed image relative to one or more other images using the computed score.

14. The system of claim 13, wherein computing a score for the particular indexed image comprises computing a score for the particular indexed image before further advancing any item cursors for the posting lists.

15. The system of claim 13, wherein computing a score for the particular indexed image comprises computing a score for the particular indexed image before advancing to the end of any of the posting lists.

16. The system of claim 13, wherein advancing a particular posting list of the posting lists comprises:

advancing an item cursor of a posting list identified by a root node of a tree structure for the posting lists being traversed, wherein each leaf node of the tree structure corresponds to a posting list being traversed and includes a document identifier of a document identified by an item in the corresponding posting list, wherein items in each posting list are sorted by document identifier; and

updating a leaf node corresponding to the particular posting list with a first document identifier of a first document identified by the subsequent item in the particular posting list.

17. The system of claim 16, wherein the operations further comprise

updating, for each particular parent node ascendant from the leaf node corresponding to the particular posting list, (1) a least-advanced document identifier among document identifiers of leaf nodes descendent from the particular parent node, a count of leaf nodes descendent from the particular parent node that identify the least-advanced document identifier, and (3) a list identifier of a posting list having a leaf node associated with the least-advanced document identifier.

18. The system of claim 13, wherein the operations further comprise weighting the computed score by a weight based on a computed feature space density of a feature cell for the corresponding visual word.

19. The system of claim 17, wherein updating each particular parent node comprises updating the parent node using at least one conditional move instruction.

20. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a query image;

determining a plurality of visual words from the query image;

identifying multiple posting lists for the plurality of visual words, including identifying a respective posting list for each of the visual words from the query image, each posting list comprising respective items that each identify an indexed image that has the visual word corresponding to the posting list, wherein each item of a particular posting list is associated with geometry data for a corresponding particular visual word from an indexed image identified by the item, and wherein each of the posting lists has a respective item cursor that designates a current posting list item in the posting list;

advancing a particular item cursor for one of the multiple posting lists by updating the item cursor of a particular posting list from designating a first item in the particular posting list to designating a subsequent item in the particular posting list;

determining a count of item cursors designating posting list items that identify a same particular indexed image, wherein the count of item cursors represents a number of visual words from the indexed image that match visual words from the query image;

determining that the count of item cursors designating posting list items that identify a same particular indexed image satisfies a threshold;

in response to determining that the count of item cursors designating items that identify a same particular indexed image satisfies a threshold, identifying geometry data associated with the items that identify the same particular indexed image, wherein the geometry data is geometry data for visual words from the particular indexed image;

computing a score for the particular indexed image before advancing to an end of the particular posting list, including comparing the visual words from the query image to the visual words from the particular indexed image using the geometry data associated with the items that identify the same particular indexed image; and

ranking the particular indexed image relative to one or more other images using the computed score.