Similar item detection

• US 9,767,382 B2
• Filed: 07/06/2016
• Issued: 09/19/2017
• Est. Priority Date: 12/30/2014
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Liu, Ming, Borar, Sumit, Kallumadi, Surya
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US15/203,715
• Publication Number:
  US 20160314376A1
• Time in Patent Office: 440 Days
• Field of Search: 382155, 382156, 382181
• CPC Class Codes: G06F 16/5838 using colour
• 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 computer-implemented method, comprising:

obtaining a first image from a database, the first image associated with a first database entry;

obtaining a second image from a database, the second image associated with a second database entry;

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

in response to determining that the first image is similar to the second image, altering the second database entry in the database, altering the second database entry in the database includes one or more of;

removing the second image from the database, altering the second image, and changing a status in the second database entry regarding placement of information from the second database entry in results from a search request,

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

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, the plurality of the second set pixels corresponding to the plurality of the first set pixels;

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 that are selected randomly in 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, the plurality of second random pixels selected based on and corresponding to the plurality of first random pixels;

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

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

wherein the similarity between the first image and the second image is determined based on the set intensity vector difference and the random intensity vector difference.

2. The computer-implemented method 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 computer-implemented method of claim 1, wherein the similarity between the first image and the second image is determined when the first and second images are selected for presentation in results from a search of entries in the database or in response to both the first image and second image being stored in the database.

4. The computer-implemented method of claim 1, wherein the similarity between the first image and the second image is determined in response to the first image and second image being obtained by the database from a same user.

5. The computer-implemented method of claim 1, wherein determining the similarity between the first image and the second image further 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; and

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

wherein the similarity between the first image and the second image is determined based on the set intensity vector difference, the value intensity vector difference, and the random intensity vector difference.

6. The computer-implemented method of claim 5, wherein determining the similarity between the first image and the second image further 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; and

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

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

7. The computer-implemented method of claim 6, wherein determining the similarity between the first image and the second image further includes:

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; and

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

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

8. One or more non-transitory computer-readable media having instructions stored thereon that, responsive to execution by one or more computing systems, cause the one or more computing systems to perform the computer-implemented method of claim 1.

9. A computer-implemented method, comprising:

obtaining a first image from a database, the first image associated with a first database entry;

obtaining a second image from a database, the second image associated with a second database entry;

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

in response to determining that the first image is similar to the second image, altering the second database entry in the database, altering the second database entry in the database includes one or more of;

removing the second image from the database, altering the second image, and changing a status in the second database entry regarding placement of information from the second database entry in results from a search request,

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 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 that are selected randomly in the first image; and

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, the plurality of second random pixels selected based on and corresponding to the plurality of first random pixels,

wherein the similarity between the first image and the second image is determined based on the first transform matrix, the second transform matrix, the plurality of first random intensity vectors, and the plurality of second random intensity vectors.

10. The computer-implemented method of claim 9, wherein determining the similarity between the first image and the second image further includes:

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, the plurality of first set pixels selected based on a geometric shape;

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, the plurality of the second set pixels selected based on and corresponding to the plurality of the first set pixels; and

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

wherein the similarity between the first image and the second image is further determined based on the set intensity vector difference.

11. The computer-implemented method of claim 10, wherein determining the similarity between the first image and the second image further 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, each of the plurality of first value pixels including intensity gradient magnitudes higher than intensity gradient magnitudes of pixels of the first image that are not part of the plurality of first value pixels and the intensity gradient magnitudes of each of the plurality of first value pixels determined based on an intensity value of the each of the plurality of first value pixels and one or more pixels adjacent to the each of the plurality of first value pixels;

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, each of the plurality of second value pixels including intensity gradient magnitudes higher than intensity gradient magnitudes of pixels of the second image that are not part of the plurality of second value pixels and the intensity gradient magnitudes of each of the plurality of second value pixels determined based on an intensity value of the each of the plurality of second value pixels and one or more pixels adjacent to the each of the plurality of second value pixels; and

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

wherein the similarity between the first image and the second image is further determined based on the value intensity vector difference, and the set intensity vector difference.

12. The computer-implemented method of claim 11, wherein determining the similarity between the first image and the second image further includes:

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; and

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

wherein the similarity between the first image and the second image is further determined based on the set intensity vector difference, the value intensity vector difference, and the color difference.

13. The computer-implemented method of claim 9, wherein determining the similarity between the first image and the second image further includes:

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 discrete transform difference between the first transform matrix of the first image and the second transform matrix of the second image,

wherein the similarity between the first image and the second image is determined based on the discrete transform difference and the random intensity vector difference.

14. The computer-implemented method of claim 13, wherein determining the similarity between the first image and the second image further 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, each of the plurality of first value pixels including intensity gradient magnitudes higher than intensity gradient magnitudes of pixels of the first image that are not part of the plurality of first value pixels and the intensity gradient magnitudes of each of the plurality of first value pixels determined based on an intensity value of the each of the plurality of first value pixels and one or more pixels adjacent to the each of the plurality of first value pixels;

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, each of the plurality of second value pixels including intensity gradient magnitudes higher than intensity gradient magnitudes of pixels of the second image that are not part of the plurality of second value pixels and the intensity gradient magnitudes of each of the plurality of second value pixels determined based on an intensity value of the each of the plurality of second value pixels and one or more pixels adjacent to the each of the plurality of second value pixels; and

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

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

15. The computer-implemented method of claim 9, wherein determining the similarity between the first image and the second image further 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, each of the plurality of first value pixels including intensity gradient magnitudes higher than intensity gradient magnitudes of pixels of the first image that are not part of the plurality of first value pixels and the intensity gradient magnitudes of each of the plurality of first value pixels determined based on an intensity value of the each of the plurality of first value pixels and one or more pixels adjacent to the each of the plurality of first value pixels;

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, each of the plurality of second value pixels including intensity gradient magnitudes higher than intensity gradient magnitudes of pixels of the second image that are not part of the plurality of second value pixels and the intensity gradient magnitudes of each of the plurality of second value pixels determined based on an intensity value of the each of the plurality of second value pixels and one or more pixels adjacent to the each of the plurality of second value pixels; and

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

wherein the similarity between the first image and the second image is further determined based on the value intensity vector difference.

16. One or more non-transitory computer-readable media having instructions stored thereon that, responsive to execution by one or more computing systems, cause the one or more computing systems to perform the computer-implemented method of claim 9.

17. The computer-implemented method 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 digital processing manipulation that results in a change to the second image that is not perceived by a human eye.

18. The computer-implemented method of claim 9, wherein the similarity between the first image and the second image is determined when the first and second images are selected for presentation in results from a search of entries in the database or in response to both the first image and second image being stored in the database.

19. The computer-implemented method of claim 9, wherein the similarity between the first image and the second image is determined in response to the first image and second image being obtained by the database from a same user.