Similar item detection

• US 9,454,713 B2
• Filed: 12/30/2014
• Issued: 09/27/2016
• Est. Priority Date: 12/30/2014
• Status: Expired due to Fees

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Borar, Sumit, Kallumadi, Surya, Liu, Ming
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US14/586,318
• Publication Number:
  US 20160189003A1
• Time in Patent Office: 637 Days
• Field of Search: 382/155, 382/165, 382/181
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06Q 30/0276 Advertisement creation
• CPC Class Codes: G06Q 30/0629 for generating comparisons
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

Abstract

A method to determine image similarities. The method may include obtaining a first image and a second image and determining a discrete transform difference between a first discrete transform of the first image and a second discrete transform of the second image. The method may also include determining multiple first intensity vectors for the first image and determining multiple second intensity vectors for the second image. The method may also include determining an intensity vector difference between the multiple first intensity vectors and the multiple second intensity vectors and determining a color difference between a first color histogram of the first image and a second color histogram of the second image. The method may also include determining a similarity between the first image and the second image based on the discrete transform difference, the intensity vector difference, and the color difference.

Claims

1. A system, comprising:

a database configured to store a first image associated with a first product offered for sale and a second image associated with a second product offered for sale; and

a computing system communicatively coupled to the database, the computing system configured to;

determine a similarity between the first image and the second image; and

based on a result of the determination, alter a presentation of the second image to a buyer,

wherein determining the similarity between the first image and the second image includes;

applying a discrete transform to the first image to generate a first transform matrix that is a frequency representation of the first image;

applying the discrete transform to the second image to generate a second transform matrix that is a frequency representation of the second image;

determining a discrete transform difference between the first transform matrix of the first image and the second transform matrix of the second image;

determining a plurality of first intensity vectors for the first image, each of the plurality of first intensity vectors corresponding to a different one of a plurality of first pixels of the first image;

determining a plurality of second intensity vectors for the second image, each of the plurality of second intensity vectors corresponding to a different one of a plurality of second pixels of the second image;

determining an intensity vector difference between the plurality of first intensity vectors and the plurality of second intensity vectors;

generating first color information of the first image based on one or more first color histograms of hue and saturation of the first image;

generating second color information of the second image based on one or more second color histograms of hue and saturation of the second image;

determining a color difference between the first image and the second image using the first color information and the second color information; and

determining the similarity between the first image and the second image based on the discrete transform difference, the intensity vector difference, and the color difference.

2. The system of claim 1, wherein the first image is determined to be similar to the second image when the second image is a duplicate of the first image and when the second image is a duplicate of the first image with a digital processing manipulation that results in a change to the second image that is not perceived by a human eye.

3. The system of claim 1, wherein the computing system is configured to alter the presentation of the second image to the buyer by not presenting the second image to the buyer or by adjusting a location of the second image in a list with multiple images.

4. The system of claim 1, wherein the computing system is configured to determine the similarity between the first image and the second image when the first and second images are selected for display in search results or in response to storage of both of the first and second images in the database.

5. The system of claim 1, wherein the computing system is configured to determine the similarity between the first image and the second image in response to the first and second images being uploaded by a same user.

6. The system of claim 1, wherein determining the similarity between the first image and the second image based on the discrete transform difference, the intensity vector difference, and the color difference includes providing the discrete transform difference, the intensity vector difference, and the color difference to a similarity model generated using machine learning.

7. The system of claim 1, wherein the first intensity vectors are first first-type intensity vectors, the second intensity vectors are second first-type intensity vectors, the plurality of first pixels are a plurality of first first-type pixels, and the plurality of second pixels are a plurality of second first-type pixels, wherein the determining the similarity between the first image and the second image further includes:

determining a plurality of first second-type intensity vectors for the first image, each of the plurality of first second-type intensity vectors corresponding to a different one of a plurality of first second-type pixels of the first image;

determining a plurality of second second-type intensity vectors for the second image, each of the plurality of second second-type intensity vectors corresponding to a different one of a plurality of second second-type pixels of the second image;

determining a second intensity vector difference between the plurality of first second-type intensity vectors and the plurality of second second-type intensity vectors; and

determining the similarity between the first image and the second image based on the discrete transform difference, the intensity vector difference, second intensity vector difference, and the color difference.

8. The system of claim 7, wherein:

the plurality of first pixels of the first image and the plurality of second pixels of the second image are corresponding pixels in the first image and the second image that are selected randomly,

the plurality of first pixels of the first image and the plurality of second pixels of the second image are corresponding pixels in the first image and the second image that are based on a particular grid of pixels, or

the plurality of first pixels of the first image are selected based on illumination intensity maximums in the first image and the plurality of second pixels of the second image are selected based on illumination intensity maximums in the second image.

9. One or more non-transitory computer-readable media having instructions stored thereon that, responsive to execution by one or more machines, cause the one or more machines to perform operations comprising:

obtaining a first image from a database, the first image associated with a first product offered for sale;

obtaining a second image from the database, the second image associated with a second product offered for sale;

determining a similarity between the first image and the second image, wherein determining the similarity between the first image and the second image includes;

applying a discrete transform to the first image to generate a first transform matrix that is a frequency representation of the first image;

applying the discrete transform to the second image to generate a second transform matrix that is a frequency representation of the second image;

determining a discrete transform difference between the first transform matrix of the first image and the second transform matrix of the second image;

determining a plurality of first intensity vectors for the first image, each of the plurality of first intensity vectors corresponding to a different one of a plurality of first pixels of the first image;

determining a plurality of second intensity vectors for the second image, each of the plurality of second intensity vectors corresponding to a different one of a plurality of second pixels of the second image;

determining an intensity vector difference between the plurality of first intensity vectors and the plurality of second intensity vectors;

generate first color information of the first image based on one or more first color histograms of hue and saturation of the first image;

generate second color information of the second image based on one or more second color histograms of hue and saturation of the second image;

determining a color difference between the first image and the second image using the first color information and the second color information; and

determining a similarity between the first image and the second image based on the discrete transform difference, the intensity vector difference, and the color difference; and

after the first image is determined to be similar to the second image, altering the second image in the database.

10. The non-transitory computer-readable media of claim 9, wherein the first image is determined to be similar to the second image when the second image is a duplicate of the first image and when the second image is a duplicate of the first image with a processing manipulation that results in a change to the first image that is not perceived by a human eye.

11. The non-transitory computer-readable media of claim 9, wherein the first intensity vectors are first first-type intensity vectors, the second intensity vectors are second first-type intensity vectors, the plurality of first pixels are a plurality of first first-type pixels, and the plurality of second pixels are a plurality of second first-type pixels, wherein the operations further comprises:

determining a plurality of first second-type intensity vectors for the first image, each of the plurality of first second-type intensity vectors corresponding to a different one of a plurality of first second-type pixels of the first image;

determining a plurality of second second-type intensity vectors for the second image, each of the plurality of second second-type intensity vectors corresponding to a different one of a plurality of second second-type pixels of the second image; and

determining a second intensity vector difference between the plurality of first second-type intensity vectors and the plurality of second second-type intensity vectors,

wherein the determining the similarity between the first image and the second image is based on the discrete transform difference, the intensity vector difference, the second intensity vector difference, and the color difference.

12. The non-transitory computer-readable media of claim 11, wherein the operations further comprise:

determining a plurality of first third-type intensity vectors for the first image, each of the plurality of first third-type intensity vectors corresponding to a different one of a plurality of first third-type pixels of the first image;

determining a plurality of second third-type intensity vectors for the second image, each of the plurality of second third-type intensity vectors corresponding to a different one of a plurality of second third-type pixels of the second image; and

determining a third intensity vector difference between the plurality of first third-type intensity vectors and the plurality of second third-type intensity vectors,

wherein the determining the similarity between the first image and the second image is based on the discrete transform difference, the intensity vector difference, the second intensity vector difference, the third intensity vector difference, and the color difference.

13. The non-transitory computer-readable media of claim 9, wherein determining the similarity between the first image and the second image based on the discrete transform difference, the intensity vector difference, and the color difference includes providing the discrete transform difference, the intensity vector difference, and the color difference to a similarity model generated using machine learning.

14. The non-transitory computer-readable media of claim 9, wherein the determining the intensity vector difference between the plurality of first intensity vectors and the plurality of second intensity vectors includes determining a preliminary intensity vector difference between corresponding vectors of the plurality of first intensity vectors and the plurality of second intensity vectors and averaging the preliminary intensity vector differences.

15. A computer-implemented method, comprising:

obtaining a first image from a database, the first image associated with a first product offered for sale;

obtaining a second image from the database, the second image associated with a second product offered for sale;

determining, using a computing system, a similarity between the first image and the second image, wherein determining the similarity between the first image and the second image includes;

determining a plurality of first value intensity vectors for the first image, each of the plurality of first value intensity vectors corresponding to a different one of a plurality of first value pixels of the first image;

determining a plurality of second value intensity vectors for the second image, each of the plurality of second value intensity vectors corresponding to a different one of a plurality of second value pixels of the second image;

determining a value intensity vector difference between the plurality of first value intensity vectors and the plurality of second value intensity vectors;

determining a plurality of first set intensity vectors for the first image, each of the plurality of first set intensity vectors corresponding to a different one of a plurality of first set pixels of the first image;

determining a plurality of second set intensity vectors for the second image, each of the plurality of second set intensity vectors corresponding to a different one of a plurality of second set pixels of the second image;

determining a set intensity vector difference between the plurality of first set intensity vectors and the plurality of second set intensity vectors;

determining a plurality of first random intensity vectors for the first image, each of the plurality of first random intensity vectors corresponding to a different one of a plurality of first random pixels of the first image;

determining a plurality of second random intensity vectors for the second image, each of the plurality of second random intensity vectors corresponding to a different one of a plurality of second random pixels of the second image;

determining a random intensity vector difference between the plurality of first random intensity vectors and the plurality of second random intensity vectors; and

determining a similarity between the first image and the second image based on the value intensity vector difference, the set intensity vector difference, and the random intensity vector difference; and

after the first image is determined to be similar to the second image, altering the second image in the database.

16. The computer-implemented method of claim 15, wherein:

the plurality of first random pixels of the first image and the plurality of second random pixels of the second image are corresponding pixels in the first image and the second image that are selected randomly,

the plurality of first set pixels of the first image and the plurality of second set pixels of the second image are corresponding pixels in the first image and the second image that are based on a particular grid of pixels, and

the plurality of first value pixels of the first image are selected based on illumination intensity maximums in the first image and the plurality of second value pixels of the second image are selected based on illumination intensity maximums in the second image.

17. The computer-implemented method of claim 16, wherein the plurality of first random pixels and the plurality of second random pixels are selected randomly with at least a minimum distance there between and wherein the particular grid of pixels is an equal spaced grid of pixels distributed through the first and second images.

18. The computer-implemented method of claim 15, wherein:

the determining the plurality of first random intensity vectors for one of the plurality of first random intensity vectors includes combining illumination intensities of a plurality of random region pixels that surround a random pixel of the plurality of first random pixels that corresponds with the one of the first random intensity vectors; and

the determining the plurality of first set intensity vectors for one of the plurality of first set intensity vectors includes combining illumination intensities of a plurality of set region pixels that surround a set pixel of the plurality of first set pixels that corresponds with the one of the first set intensity vectors,

wherein the plurality of set region pixels includes more pixels than the plurality of random region pixels.

19. The computer-implemented method of claim 15, further comprising:

determining a discrete transform difference between a first discrete transform of the first image and a second discrete transform of the second image; and

determining a color difference between a first color histogram of the first image and a second color histogram of the second image,

wherein the determining the similarity between the first image and the second image is based on the discrete transform difference, the value intensity vector difference, the set intensity vector difference, the random intensity vector difference, and the color difference.