Image-based indexing in a network-based marketplace

• US 8,825,660 B2
• Filed: 03/17/2009
• Issued: 09/02/2014
• Est. Priority Date: 03/17/2009
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Chittar, Naren
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US12/406,016
• Publication Number:
  US 20100241650A1
• Time in Patent Office: 1,995 Days
• Field of Search: 707/711, 707/728
• US Class Current: 707/741
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

A method and system to index and search item listings in a network-based publication system, such as a network-based marketplace. For example, a listing query may be received from a user, the listing query including a query image. The query image may then be processed to generate a plurality of index sets. Each index set of the plurality of index sets may correspond to a respective portion of the query image and may comprise a set of index values. Each index value of the set of index values may be indicative of an image attribute, such as light intensity, for a respective sub-portion of the corresponding portion of the query image. At least one result image from a database of listing images may be identified by comparing the plurality of index sets for the query image to pre-compiled index sets in an index database. Each pre-compiled index set may be associated with at least one listing image which, in turn, may be associated with an item listing on a network-based marketplace.

Claims

1. A computer system comprising:

a receiving module configured to receive a listing query related to a network-based marketplace which includes an item listing database, the listing query including a query image;

a processing module configured to process the query image, using one or more processors, to generate a plurality of index sets image fingerprints by performing operations comprising;

dividing the query image into a grid of sub-portions, each sub-portion comprising a respectively corresponding pixel set having multiple image pixels,

assigning to each sub-portion an index value based on attribute values of the corresponding pixel set, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint comprising a set of index values corresponding to a respective grid portion selected from the grid of index values, the grid portions for the plurality of image fingerprints being identical in shape, with at least some of the grid portion overlapping;

a comparison module configured, for separately comparing each of the plurality of image fingerprints for the query image to pre-compiled image fingerprints in an index database, each pre-compiled image fingerprint being associated with at least one listing image corresponding to an associated item listing and forming part of a database of listing images, each listing image being associated with multiple pre-compiled image fingerprints in the index database,

ranking the listing images according to the number of matching image fingerprints between, on the one hand, the plurality of image fingerprints generated in respect of the query image, and, on the other hand, the image fingerprints associated in the index database with the respective listing images, and

based at least in part on the ranking, identifying at least one image result from the database of listing images; and

a result module configured to provide at least one result item listing, the at least one result item listing being based on a respective result image.

2. A computer system according to claim 1, in which each of the grid portions of the plurality of image fingerprints is a two dimensional selection from the grid of index values, comprising a plurality of contiguous rows of a plurality of contiguous columns of the grid of index values.

3. A computer system according to claim 1 in which the processing module is configured to perform an edge detection operation on the query image before dividing the query image into the grid of sub-portions.

4. A computer system according to claim 3, in which the processing module is configured to perform a normalizing operation on the query image after performance of the edge detection operation.

5. A computer system according to claim 1, in which the database of listing images comprises a database entry for each unique pre-compiled image fingerprint, each of the database entries being linked to all listing images which share the respective image fingerprint.

6. A computer-implemented method comprising:

receiving a listing query related to a publication system which includes an item listing database, the listing query including a query image;

processing the query image to generate a plurality of image fingerprints, the processing comprising;

dividing the query image into a grid of sub-portions, each sub-portion comprising a respectively corresponding pixel set having multiple image pixels,

assigning to each sub-portion an index value based on attribute values of the corresponding pixel set, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint comprising a set of index values corresponding to a respective grid portion selected from the grid of index values, the grid portions for the plurality of image fingerprints being identical in shape, with at least some of the grid portion overlapping;

separately comparing each of the plurality of image fingerprints for the query image to pre-compiled image fingerprints in an index database, each pre-compiled image fingerprint being associated with at least one listing image corresponding to an associated item listing and forming part of a database of listing images, each listing image being associated with multiple pre-compiled image fingerprints in the index database;

ranking the listing images according to the number of matching image fingerprints between, on the one hand, the plurality of image fingerprints generated in respect of the query image, and, on the other hand, the image fingerprints associated in the index database with the respective listing images;

based at least in part on the ranking, identifying at least one image result from the database of listing images; and

providing at least one result item listing, the at least one result item listing being based on a respective result image.

7. A method according to claim 6, in which the plurality of image fingerprints is comprised of the index values of respective overlapping two dimensional selections of contiguous index values in the grid of index values.

8. A method according to claim 6, which includes performing an edge detection operation on the query image before dividing the query image into the grid of sub-portions.

9. A method according to claim 8, which includes performing a normalizing operation on the query image after performance of the edge detection operation.

10. A method according to claim 6, in which the database of listing images comprises a database entry for each unique pre-compiled image fingerprint, each of the database entries being linked to all listing images which share the respective image fingerprint.

11. A method according to claim 6, in which the identifying of the at least one result image comprises ranking the listing images according to the number of matching image fingerprints between, on the one hand, the plurality of image fingerprints generated in respect of the query image, and, on the other hand, the image fingerprints associated in the index database with the respective listing images.

12. A non-transitory computer-readable medium comprising instruction data in electronic form which, when implemented by one or more machines, cause the one or more machines to perform the following operations:

receiving a listing query related to a publication system which includes an item listing database, the listing query including a query image;

processing the query image to generate a plurality of image fingerprints, the processing comprising;

dividing the query image into a grid of sub-portions, each sub-portion comprising a respectively corresponding pixel set having multiple image pixels,

assigning to each sub-portion an index value based on attribute values of the corresponding pixel set, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint comprising a set of index values corresponding to a respective grid portion selected from the grid of index values, the grid portions for the plurality of image fingerprints being identical in shape, with at least some of the grid portion overlapping;

separately comparing each of the plurality of image fingerprints for the query image to pre-compiled image fingerprints in an index database, each pre-compiled image fingerprint being associated with at least one listing image corresponding to an associated item listing and forming part of a database of listing images, each listing image being associated with multiple pre-compiled image fingerprints in the index database;

ranking the listing images according to the number of matching image fingerprints between, on the one hand, the plurality of image fingerprints generated in respect of the query image, and, on the other hand, the image fingerprints associated in the index database with the respective listing images;

based at least in part on the ranking, identifying at least one image result from the database of listing images; and

providing at least one result item listing, the at least one result item listing being based on a respective result image.

13. A computer system comprising:

means for receiving a listing query related to a network-based publication system which includes an item listing database, the listing query including a query image;

means for processing the query image, using one or more processors, to generate a plurality of image fingerprints, the processing comprising;

dividing the query image into a grid of sub-portions, each sub-portion comprising a respectively corresponding pixel set having multiple image pixels,

assigning to each sub-portion an index value based on attribute values of the corresponding pixel set, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint comprising a set of index values corresponding to a respective grid portion selected from the grid of index values, the grid portions for the plurality of image fingerprints being identical in shape, with at least some of the grid portion overlapping;

means for separately comparing each of the plurality of image fingerprints for the query image to pre-compiled image fingerprints in an index database, each pre-compiled image fingerprint being associated with at least one listing image corresponding to an associated item listing and forming part of a database of listing images, each listing image being associated with multiple pre-compiled image fingerprints in the index database;

means for ranking the listing images according to the number of matching image fingerprints between, on the one hand, the plurality of image fingerprints generated in respect of the query image, and, on the other hand, the image fingerprints associated in the index database with the respective listing images;

means for, based at least in part on the ranking, identifying at least one image result from the database of listing images; and

means for providing at least one result item listing, the at least one result item listing being based on a respective result image.

14. A computer system comprising:

a receiving module to receive a listing image associated with an item listing on a network-based marketplace;

a processing module to process the listing image, using one or more processors, to generate a plurality of image fingerprints, the processing comprising;

dividing the listing image into a grid of sub-portions, each sub-portion comprising a plurality of pixels;

assigning to each sub-portion an index value based on attribute values of the sub-portion'"'"'s pixels, to generate a grid of index values; and

compiling the plurality of image fingerprints from the grid of index values,

each image fingerprint of the plurality of image fingerprints corresponding to a respective portion of the listing image, and comprising a set of index values, from the grid of index values and corresponding to respective set of the sub-portions within the corresponding portion of the listing image, wherein each portion of the listing image is a respective one of multiple identically shaped sub-divisions of the listing image, the multiple subdivision including two or more overlapping sub-divisions; and

an index database comprising a plurality of separate and unique database entries that are linked with the listing image, the plurality of database entries corresponding to the plurality of image fingerprints.

15. A computer system according to claim 14, in which the processing module is configured to perform an edge detection operation on the listing image before dividing the listing image into the grid of sub-portions.

16. A computer system according to claim 14, in which the processing module is configured to produce multiple grids of sub-portions of the listing image, the multiple grids having varying grid resolutions, and the processing module further being configured to generate a separate plurality of image fingerprints in respect of each grid of sub-portions.

17. A computer system according to claim 14, in which the processing module is configured to determine a category associated with the listing image, and to select a resolution for the grid of sub-portions based on the category.

18. A computer system according to claim 14, in which the processing module is configured to produce multiple variations of the listing image, and to generate a separate plurality of image fingerprints in respect of each variation of the listing image.

19. A computer system according to claim 18, in which the processing module is configured to produce the multiple variations of the listing image according to varying magnification levels of the listing image.

20. A computer system according to claim 18, in which the processing module is configured to produce the multiple variations of the listing image according to varying rotations of the listing image.

21. A computer-implemented method comprising:

receiving a listing image associated with an item listing on a network-based publication system;

processing the listing image to generate a plurality of image fingerprints, the processing comprising;

dividing the listing image into a grid of sub-portions, each sub-portion comprising a plurality of pixels,

assigning to each sub-portion an index value based on attribute values of the sub-portion'"'"'s pixels, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint of the plurality of image fingerprints corresponding to a respective portion of the listing image and comprising a set of index values from the grid of index values and corresponding to a respective set of the sub-portions within the corresponding portion of the listing image, wherein each portion of the listing image is a respective one of multiple identically shaped sub-divisions of the listing image, the multiple subdivision including two or more overlapping sub-divisions; and

linking a plurality of separate and unique database entries in an index database with the listing image, the plurality of database entries corresponding to the plurality of image fingerprints.

22. A method according to claim 21, wherein the processing of the listing image to generate the plurality of image fingerprints comprises:

dividing the listing image into a grid of sub-portions, each sub-portion comprising a plurality of pixels;

assigning to each sub-portion an index value based on attribute values of the sub-portion'"'"'s pixels, to generate a grid of index values; and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint comprising the index values representative of the respective portion of the image.

23. A non-transitory computer-readable medium comprising instruction data in electronic form which, when implemented by one or more machines, cause the one or more machines to perform the following operations:

receiving a listing image associated with an item listing on a network-based publication system;

processing the listing image to generate a plurality of image fingerprints, the processing comprising;

dividing the listing image into a grid of sub-portions, each sub-portion comprising a plurality of pixels,

assigning to each sub-portion an index value based on attribute values of the sub-portion'"'"'s pixels, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint of the plurality of image fingerprints corresponding to a respective portion of the listing image and comprising a set of index values from the grid of index values and corresponding to a respective set of the sub-portions within the corresponding portion of the listing image, wherein each portion of the listing image is a respective one of multiple identically shaped sub-divisions of the listing image, the multiple subdivision including two or more overlapping sub-divisions; and

linking a plurality of separate and unique database entries in an index database with the listing image, the plurality of database entries corresponding to the plurality of image fingerprints.

24. A computer system comprising:

means for receiving a listing image associated with an item listing on a network-based publication system;

means for processing the listing image, using one or more processors, the processing comprising;

dividing the listing image into a grid of sub-portions, each sub-portion comprising a plurality of pixels,

assigning to each sub-portion an index value based on attribute values of the sub-portion'"'"'s pixels, to generate a grid of index values, and

compiling the plurality of image fingerprints from the grid of index values, each image fingerprint of the plurality of image fingerprints corresponding to a respective portion of the listing image and comprising a set of index values from the grid of index values and corresponding to a respective set of the sub-portions within the corresponding portion of the listing image, wherein each portion of the listing image is a respective one of multiple identically shaped sub-divisions of the listing image, the multiple subdivision including two or more overlapping sub-divisions; and

means for linking a plurality of separate and unique database entries in an index database with the listing image, the plurality of database entries corresponding to the plurality of image fingerprints.