SIMILAR IMAGE RETRIEVAL
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
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.
-
Specification