Image-based indexing in a network-based marketplace

• US 9,600,497 B2
• Filed: 08/29/2014
• Issued: 03/21/2017
• Est. Priority Date: 03/17/2009
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Inventors: Chittar, Naren
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US14/473,809
• Publication Number:
  US 20140372449A1
• Time in Patent Office: 935 Days
• Field of Search: 707/711, 707/718, 707/696, 707/754, 707/999.107
• US Class Current: 1/1
• 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 system comprising:

a receiving module comprising one or more computer processors configured to access target image information representing a target image comprising a multiplicity of image pixels;

a processing module comprising at least one computer processor configured for processing the target image information to generate multiple image vectors for the target image by performing operations comprising;

partitioning the target image into a grid comprising multiple pixel blocks, each pixel block being made up by multiple contiguous image pixels of the target image, and the pixel blocks being substantially consistent in size and shape throughout;

for each of the pixel blocks, assigning to the pixel block an index value based at least in part on intensity values of the image pixels making up the pixel block;

identifying multiple image portions forming part of the grid, each image portion being made up by a plurality of contiguous pixel blocks forming part of the grid, the multiple image portions being substantially consistent in size and shape; and

for each one of the multiple image portions, compiling a respective index vector comprising the index values of the corresponding plurality of pixel blocks making up the image portion;

a comparison module comprising one or more processing devices configured to perform a similarity comparison between the target image and one or more candidate images based at least in part on the multiple image vectors of the target image; and

a result module comprising at least one processing device configured to output on a computer device a comparison result based on results of the similarity comparison.

2. The system of claim 1, wherein the image portions are substantially similar in shape to the pixel blocks, but differ in size from the pixel blocks.

3. The system of claim 2, wherein the size of the image portions is a whole number multiple of the size of the pixel blocks, so that each image portion is completely made up by a whole number of pixel blocks.

4. The system of claim 2, wherein each image portion is made up by a square grid of pixel blocks.

5. The system of claim 1, wherein at least some of the multiple image portions overlap, with each pair of overlapping image portions sharing at least one pixel block in common.

6. The system of claim 5, wherein the processing module is configured such that the operations for generating the multiple image vectors comprise a sliding window method in which a sliding window defining the size and shape of the image portions is successively moved over a grid of the pixel blocks making up the target image, to identify each possible image portion consisting of a grid of pixel blocks fitting wholly within the sliding window.

7. The system of claim 1, wherein the processing module is configured to assign index values to the pixel blocks such that the index value for each pixel block corresponds to a statistical average of respective attribute values of the multiple image pixels of the pixel block.

8. The system of claim 1, wherein the assigning of a respective index value to each of the pixel blocks is based on an average of the light intensity values of the multiple image pixels of the pixel block.

9. The system of claim 1, wherein the processing module is configured to perform one or more preprocessing operations on the target image to provide a preprocessed target image, the multiple image vectors for the target image to be generated based on the preprocessed target image.

10. The system of claim 9, wherein the one or more preprocessing operations comprises an edge detection operation.

11. The system of claim 10 wherein the one or more preprocessing operations further comprises a normalizing operation performed after the edge detection operation.

12. A method comprising:

accessing target image information representing a target image comprising a multiplicity of image pixels;

in an automated operation using a processing module comprising at least one computer processor configured for processing target image information, processing the target image information to generate multiple image vectors for the target image by performing operations comprising;

partitioning the target image into a grid comprising multiple pixel blocks, each pixel block being made up by multiple contiguous image pixels of the target image, and the pixel blocks being substantially consistent in size and shape throughout;

for each of the pixel blocks, assigning to the pixel block an index value based at least in part on intensity values of the image pixels making up the pixel block;

identifying multiple image portions forming part of the grid, each image portion being made up by a plurality of contiguous pixel blocks forming part of the grid, the multiple image portions being substantially consistent in size and shape; and

for each one of the multiple image portions, compiling a respective index vector comprising the index values of the corresponding plurality of pixel blocks making up the image portion;

performing an automated similarity comparison between the target image and one or more candidate images based at least in part on the multiple image vectors of the target image; and

outputting to a computer device a comparison result based on results of the similarity comparison.

13. The method of claim 12, wherein each image portion comprises a two-dimensional area which is square in outline and is fully made up by a square grid of pixel blocks contained within the image portion.

14. The method of claim 12, wherein at least some of the multiple image portions overlap, with each pair of overlapping image portions sharing at least one pixel block in common.

15. The method of claim 14, wherein the processing of the target image information comprises performing a sliding window method in which a sliding window defining the size and shape of the image portions is successively moved over a grid of the pixel blocks making up the target image, to identify each possible image portion consisting of a grid of pixel blocks fitting wholly within the sliding window.

16. The method of claim 12, wherein the assigning of the index values to the pixel blocks is such that the index value for each pixel block corresponds to a statistical average of respective light intensity attribute values of the multiple image pixels of the pixel block.

17. The method of claim 12, further comprising performing one or more preprocessing operations on the target image to provide a preprocessed target image, the multiple image vectors for the target image to be generated based on the preprocessed target image.

18. The method of claim 17, wherein the one or more preprocessing operations comprises an edge detection operation.

19. The method of claim 18 wherein the one or more preprocessing operations further comprises a normalizing operation performed after the edge detection operation.

20. A non-transitory computer readable storage medium having stored thereon instructions for causing a machine, upon execution of the instructions by the machine, to perform operations comprising:

accessing target image information representing a target image comprising a multiplicity of image pixels;

in an automated operation using a processing module comprising at least one computer processor configured for processing target image information, processing the target image information to generate multiple image vectors for the target image by performing operations comprising;

partitioning the target image into a grid comprising multiple pixel blocks, each pixel block being made up by multiple contiguous image pixels of the target image, and the pixel blocks being substantially consistent in size and shape throughout;

for each of the pixel blocks, assigning to the pixel block an index value based at least in part on intensity values of the image pixels making up the pixel block;

identifying multiple image portions forming part of the grid, each image portion being made up by a plurality of contiguous pixel blocks forming part of the grid, the multiple image portions being substantially consistent in size and shape; and

for each one of the multiple image portions, compiling a respective index vector comprising the index values of the corresponding plurality of pixel blocks making up the image portion;

performing an automated similarity comparison between the target image and one or more candidate images based at least in part on the multiple image vectors of the target image; and

outputting to a computer device a comparison result based on results of the similarity comparison.