IMAGE-BASED INDEXING IN A NETWORK-BASED MARKETPLACE

• US 20100241650A1
• Filed: 03/17/2009
• Published: 09/23/2010
• Est. Priority Date: 03/17/2009
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Chittar, Naren
• Granted Patent: US 8,825,660 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• 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 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 to process the query image to generate a plurality of index sets, each index set of the plurality of index sets corresponding to a respective portion of the query image, and comprising a set of index values, and each index value of the set of index values being indicative of an image attribute for a respective sub-portion of the corresponding portion of the query image;

a comparison module to identify at least one result image from a database of listing images 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 being associated with at least one listing image, and the at least one listing image being associated with an item listing; and

a result module 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, wherein the processing module is configured to process the query image by a method comprising:

dividing the query 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 index sets from the grid of index values, each index set comprising the index values representative of the respective portion of the image.

3. A computer system according to claim 2, in which the plurality of index sets is comprised of the index values of respective overlapping two dimensional selections of contiguous index values in the grid of index values.

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

5. A computer system according to claim 2, 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.

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

7. A computer system according to claim 1, in which the comparison module is configured to identify the at least one result item listing by ranking the listing images according to the number of matching index sets between, on the one hand, the plurality of index sets generated in respect of the query image, and, on the other hand, the index sets associated in the index database with the respective listing images.

9. A method according to claim 1, wherein the processing of the query image to generate the plurality of index sets comprises:

dividing the query 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 index sets from the grid of index values, each index set comprising the index values representative of the respective portion of the image.

10. A method according to claim 9, in which the plurality of index sets is comprised of the index values of respective overlapping two dimensional selections of contiguous index values in the grid of index values.

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

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

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

8. 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 index sets, each index set of the plurality of index sets corresponding to a respective portion of the query image, and comprising a set of index values, and each index value of the set of index values being indicative of an image attribute for a respective sub-portion of the corresponding portion of the query image;

identifying at least one result image from a database of listing images 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 being associated with at least one listing image, and the at least one listing image being associated with an item listing; and

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

11. A method according to claim 8, in which the database of listing images comprises a database entry for each unique pre-compiled index set, each of the database entries being linked to all listing images which share the respective index set.

15. A computer-readable medium comprising instruction 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 index sets, each index set of the plurality of index sets corresponding to a respective portion of the query image, and comprising a set of index values, and each index value of the set of index values being indicative of an image attribute for a respective sub-portion of the corresponding portion of the query image;

identifying at least one result image from a database of listing images 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 being associated with at least one listing image, and the at least one listing image being associated with an item listing; and

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

16. 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 to generate a plurality of index sets, each index set of the plurality of index sets corresponding to a respective portion of the query image, and comprising a set of index values, and each index value of the set of index values being indicative of an image attribute for a respective sub-portion of the corresponding portion of the query image;

means for identifying at least one result image from a database of listing images 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 being associated with at least one listing image, and the at least one listing image being associated with an item listing; and

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

17. 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 to generate a plurality of index sets, each index set of the plurality of index sets corresponding to a respective portion of the listing image, and comprising a set of index values, and each index value of the set of index values being indicative of an image attribute for a respective sub-portion of the corresponding portion of the listing image; and

an index database to store the plurality of index sets such that each index set is associated with the listing image.

18. A computer system according to claim 17, wherein the processing module is configured to process the listing image by a method 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 index sets from the grid of index values, each index set comprising the index values representative of the respective portion of the image.

19. A computer system according to claim 18, in which the plurality of index sets is comprised of the index values of respective overlapping two dimensional selections of contiguous index values in the grid of index values.

20. A computer system according to claim 17, in which the index database comprises a database entry for each unique index set, each of the database entries being linked to all listing images which share the respective index set.

21. A computer system according to claim 18, 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.

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

23. A computer system according to claim 22, 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.

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

25. A computer system according to claim 18, 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 index sets in respect of each grid of sub-portions.

26. A computer system according to claim 18, 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.

27. 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 index sets, each index set of the plurality of index sets corresponding to a respective portion of the listing image, and comprising a set of index values, and each index value being indicative of an image attribute for a respective sub-portion of the corresponding portion of the listing image; and

storing the plurality of index sets in an index database such that each index set is associated with the listing image.

28. A method according to claim 27, wherein the processing of the listing image to generate the plurality of index sets 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 index sets from the grid of index values, each index set comprising the index values representative of the respective portion of the image.

29. A computer-readable medium comprising instruction 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 index sets, each index set of the plurality of index sets corresponding to a respective portion of the listing image, and comprising a set of index values, and each index value being indicative of an image attribute for a respective sub-portion of the corresponding portion of the listing image; and

storing the plurality of index sets in an index database such that each index set is associated with the listing image.

30. 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 to generate a plurality of index sets, each index set of the plurality of index sets corresponding to a respective portion of the listing image, and comprising a set of index values, and each index value being indicative of an image attribute for a respective sub-portion of the corresponding portion of the listing image; and

means for storing the plurality of index sets in an index database such that each index set is associated with the listing image.