Approach for near duplicate image detection

• US 7,860,308 B2
• Filed: 08/17/2006
• Issued: 12/28/2010
• Est. Priority Date: 12/01/2005
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Shah, Shesha
• Primary Examiner(s): Alavi; Amir
• Application Number:
  US11/506,330
• Publication Number:
  US 20070127813A1
• Time in Patent Office: 1,594 Days
• Field of Search: 382/128, 382/132, 382/162, 382/164, 382/165, 382/167, 382/168, 382/170, 382/173, 382/190, 382218-220, 382/253, 382/254, 382/276, 382/277, 358/515, 358/518, 358/520, 358/522, 358/530, 345/589, 345600-604
• US Class Current: 382/170
• CPC Class Codes: G06V 10/40 Extraction of image or video features

Abstract

A content-based approach is provided for detecting near duplicate images. The approach generally involves analyzing the content of images to be compared and generating color and texture histogram descriptor data for each image. The images may then be compared based upon the color and texture histogram descriptor data to determine whether the images are near duplicate images. Content-based image signature data may also be generated for each of the images based upon the color and texture histogram descriptor data. The image signature data may then be compared to determine whether the corresponding images are near duplicate images.

Claims

1. A computer-implemented method for processing image data, the computer-implemented method comprising:

generating, based upon first color image data, first color histogram descriptor data that indicates a number of occurrences in the first color image data of each of a plurality of colors;

generating first gray-scaled image data based upon the first color image data;

generating, based upon the first gray-scaled image data, first texture histogram descriptor data that indicates a number of occurrences in the first gray-scaled image data of each of a plurality of edge orientations;

generating, based upon second color image data, second color histogram descriptor data that indicates a number of occurrences in the second color image data of each of a plurality of colors;

generating second gray-scaled image data based upon the second color image data;

generating, based upon the second gray-scaled image data, second texture histogram descriptor data that indicates a number of occurrences in the second gray-scaled image data of each of a plurality of edge orientations; and

determining whether the first color image data is a near duplicate of the second color image data by

comparing the first color histogram descriptor data to the second color histogram descriptor data, and

comparing the first texture histogram descriptor data to the second texture histogram descriptor data;

wherein one or more of the steps are performed using one or more processors.

2. The computer-implemented method as recited in claim 1, wherein the first and second color histogram descriptor data are quantized in RGB space and normalized.

3. The computer-implemented method as recited in claim 1, wherein the first and second texture histogram descriptor data are quantized to a subset of possible directions and normalized.

4. The computer-implemented method as recited in claim 1, wherein the determining whether the first color image data is a near duplicate of the second color image data includes determining an L1 similarity measure between the first and second color histogram descriptor data and determining an L1 similarity measure between the first and second texture histogram descriptor data.

5. The computer-implemented method as recited in claim 1, wherein the determining whether the first color image data is a near duplicate of the second color image data includes determining an LSH similarity measure between the first and second color histogram descriptor data and determining an LSH similarity measure between the first and second texture histogram descriptor data.

6. The computer-implemented method as recited in claim 1, wherein:

the computer-implemented method further comprises using the one or more processors to perform the steps of;

determining a first center of mass on luminance of the first color image data,

dividing the first color image data into a first plurality of segments based upon the first center of mass, and

determining a second center of mass on luminance of the second color image data

dividing the second color image data into a second plurality of segments based upon the second center of mass, and

the generating the first color histogram descriptor data includes generating first color histogram descriptor data for each of the first plurality of segments;

the generating the first texture histogram descriptor data includes generating first texture histogram descriptor data for each of the first plurality of segments;

the generating the second color histogram descriptor data includes generating second color histogram descriptor data for each of the second plurality of segments; and

the generating the second texture histogram descriptor data includes generating second texture histogram descriptor data for each of the second plurality of segments.

7. A computer-implemented method for processing image data, the computer-implemented method comprising:

generating, based upon first color image data, first color histogram descriptor data that indicates a number of occurrences in the first color image data of each of a plurality of colors;

generating first gray-scaled image data based upon the first color image data;

generating, based upon the first gray-scaled image data, first texture histogram descriptor data that indicates a number of occurrences in the first gray-scaled image data of each of a plurality of edge orientations;

generating, based upon second color image data, second color histogram descriptor data that indicates a number of occurrences in the second color image data of each of a plurality of colors;

generating second gray-scaled image data based upon the second color image data;

generating, based upon the second gray-scaled image data, second texture histogram descriptor data that indicates a number of occurrences in the second gray-scaled image data of each of a plurality of edge orientations;

generating first signature data based upon the first color histogram data and the first texture histogram data;

generating second signature data based upon the second color histogram data and the second texture histogram data;

determining whether the first color image data is a near duplicate of the second color image data by comparing the first signature data to the second signature data;

wherein one or more of the steps are performed using one or more processors.

8. The computer-implemented method as recited in claim 7, wherein:

the generating first signature data based upon the first color histogram data and the first texture histogram data includes generating first wavelet-based signature data by processing the first color histogram data and the first texture histogram data using a wavelet transform,

the generating second signature data based upon the second color histogram data and the second texture histogram data includes generating second wavelet-based signature data by processing the second color histogram data and the second texture histogram data using the wavelet transform, and

the comparing the first signature data to the second signature data includes comparing the first wavelet-based signature data to the second wavelet-based signature data.

9. The computer-implemented method as recited in claim 8, wherein the wavelet transform is a Haar transform with uniform quantization.

10. The computer-implemented method as recited in claim 8, wherein the comparing the first wavelet-based signature data to the second wavelet-based signature data includes determining a Hamming distance between the first wavelet-based signature data and the second wavelet-based signature data.

11. The computer-implemented method as recited in claim 7, wherein the first signature data is generated by processing the first color histogram data and the first texture histogram data using vector quantization and the second signature data is generated by processing the second color histogram data and the second texture histogram data using the vector quantization.

12. The computer-implemented method as recited in claim 11, wherein the comparing the first signature data to the second signature data includes identifying any exact matches of one or more portions of the first signature data with one or more portions of the second signature data.

13. A non-transitory computer-readable storage medium for processing image data, the non-transitory computer-readable medium storing instructions which, when processed by one or more processors, cause:

generating, based upon first color image data, first color histogram descriptor data that indicates a number of occurrences in the first color image data of each of a plurality of colors;

generating first gray-scaled image data based upon the first color image data;

generating, based upon the first gray-scaled image data, first texture histogram descriptor data that indicates a number of occurrences in the first gray-scaled image data of each of a plurality of edge orientations;

generating, based upon second color image data, second color histogram descriptor data that indicates a number of occurrences in the second color image data of each of a plurality of colors;

generating second gray-scaled image data based upon the second color image data;

generating, based upon the second gray-scaled image data, second texture histogram descriptor data that indicates a number of occurrences in the second gray-scaled image data of each of a plurality of edge orientations; and

determining whether the first color image data is a near duplicate of the second color image data by

comparing the first color histogram descriptor data to the second color histogram descriptor data, and

comparing the first texture histogram descriptor data to the second texture histogram descriptor data.

14. The non-transitory computer-readable storage medium as recited in claim 13, wherein the first and second color histogram descriptor data are quantized in RGB space and normalized.

15. The non-transitory computer-readable storage medium as recited in claim 13, wherein the first and second texture histogram descriptor data are quantized to a subset of possible directions and normalized.

16. The non-transitory computer-readable storage medium as recited in claim 13, wherein the determining whether the first color image data is a near duplicate of the second color image data includes determining an L1 similarity measure between the first and second color histogram descriptor data and determining an L1 similarity measure between the first and second texture histogram descriptor data.

17. The non-transitory computer-readable storage medium as recited in claim 13, wherein the determining whether the first color image data is a near duplicate of the second color image data includes determining an LSH similarity measure between the first and second color histogram descriptor data and determining an LSH similarity measure between the first and second texture histogram descriptor data.

18. The non-transitory computer-readable storage medium as recited in claim 13, wherein:

the computer-readable medium further comprises additional instructions which, when processed by the one or more processors, cause;

determining a first center of mass on luminance of the first color image data,

dividing the first color image data into a first plurality of segments based upon the first center of mass, and

determining a second center of mass on luminance of the second color image data

dividing the second color image data into a second plurality of segments based upon the second center of mass, and

the generating the first color histogram descriptor data includes generating first color histogram descriptor data for each of the first plurality of segments;

the generating the first texture histogram descriptor data includes generating first texture histogram descriptor data for each of the first plurality of segments;

the generating the second color histogram descriptor data includes generating second color histogram descriptor data for each of the second plurality of segments; and

the generating the second texture histogram descriptor data includes generating second texture histogram descriptor data for each of the second plurality of segments.

19. A non-transitory computer-readable storage medium for processing image data, the non-transitory computer-readable medium storing instructions which, when processed by one or more processors, cause:

generating, based upon first color image data, first color histogram descriptor data that indicates a number of occurrences in the first color image data of each of a plurality of colors;

generating first gray-scaled image data based upon the first color image data;

generating, based upon the first gray-scaled image data, first texture histogram descriptor data that indicates a number of occurrences in the first gray-scaled image data of each of a plurality of edge orientations;

generating, based upon second color image data, second color histogram descriptor data that indicates a number of occurrences in the second color image data of each of a plurality of colors;

generating second gray-scaled image data based upon the second color image data;

generating, based upon the second gray-scaled image data, second texture histogram descriptor data that indicates a number of occurrences in the second gray-scaled image data of each of a plurality of edge orientations;

generating first signature data based upon the first color histogram data and the first texture histogram data;

generating second signature data based upon the second color histogram data and the second texture histogram data;

determining whether the first color image data is a near duplicate of the second color image data by comparing the first signature data to the second signature data.

20. The non-transitory computer-readable storage medium as recited in claim 19, wherein:

the generating first signature data based upon the first color histogram data and the first texture histogram data includes generating first wavelet-based signature data by processing the first color histogram data and the first texture histogram data using a wavelet transform,

the generating second signature data based upon the second color histogram data and the second texture histogram data includes generating second wavelet-based signature data by processing the second color histogram data and the second texture histogram data using the wavelet transform, and

the comparing the first signature data to the second signature data includes comparing the first wavelet-based signature data to the second wavelet-based signature data.

21. The non-transitory computer-readable storage medium as recited in claim 20, wherein the wavelet transform is a Haar transform with uniform quantization.

22. The non-transitory computer-readable storage medium as recited in claim 20, wherein the comparing the first wavelet-based signature data to the second wavelet-based signature data includes determining a Hamming distance between the first wavelet-based signature data and the second wavelet-based signature data.

23. The non-transitory computer-readable storage medium as recited in claim 19, wherein the first signature data is generated by processing the first color histogram data and the first texture histogram data using vector quantization and the second signature data is generated by processing the second color histogram data and the second texture histogram data using the vector quantization.

24. The non-transitory computer-readable storage medium as recited in claim 23, wherein the comparing the first signature data to the second signature data includes identifying any exact matches of one or more portions of the first signature data with one or more portions of the second signature data.

25. An apparatus for processing image data, the apparatus comprising a memory storing instructions which, when processed by one or more processors, cause:

generating, based upon first color image data, first color histogram descriptor data that indicates a number of occurrences in the first color image data of each of a plurality of colors;

generating first gray-scaled image data based upon the first color image data;

generating, based upon the first gray-scaled image data, first texture histogram descriptor data that indicates a number of occurrences in the first gray-scaled image data of each of a plurality of edge orientations;

generating, based upon second color image data, second color histogram descriptor data that indicates a number of occurrences in the second color image data of each of a plurality of colors;

generating second gray-scaled image data based upon the second color image data;

generating, based upon the second gray-scaled image data, second texture histogram descriptor data that indicates a number of occurrences in the second gray-scaled image data of each of a plurality of edge orientations; and

determining whether the first color image data is a near duplicate of the second color image data by

comparing the first color histogram descriptor data to the second color histogram descriptor data, and

comparing the first texture histogram descriptor data to the second texture histogram descriptor data.

26. The apparatus as recited in claim 25, wherein the first and second color histogram descriptor data are quantized in RGB space and normalized.

27. The apparatus as recited in claim 25, wherein the first and second texture histogram descriptor data are quantized to a subset of possible directions and normalized.

28. The apparatus as recited in claim 25, wherein the determining whether the first color image data is a near duplicate of the second color image data includes determining an L1 similarity measure between the first and second color histogram descriptor data and determining an L1 similarity measure between the first and second texture histogram descriptor data.

29. The apparatus as recited in claim 25, wherein the determining whether the first color image data is a near duplicate of the second color image data includes determining an LSH similarity measure between the first and second color histogram descriptor data and determining an LSH similarity measure between the first and second texture histogram descriptor data.

30. The apparatus as recited in claim 25, wherein:

the memory further stores additional instructions which, when processed by the one or more processors, cause;

determining a first center of mass on luminance of the first color image data,

dividing the first color image data into a first plurality of segments based upon the first center of mass, and

determining a second center of mass on luminance of the second color image data

dividing the second color image data into a second plurality of segments based upon the second center of mass, and

the generating the first color histogram descriptor data includes generating first color histogram descriptor data for each of the first plurality of segments;

the generating the first texture histogram descriptor data includes generating first texture histogram descriptor data for each of the first plurality of segments;

the generating the second color histogram descriptor data includes generating second color histogram descriptor data for each of the second plurality of segments; and

the generating the second texture histogram descriptor data includes generating second texture histogram descriptor data for each of the second plurality of segments.

31. An apparatus for processing image data, the apparatus comprising a memory storing instructions which, when processed by one or more processors, cause:

generating, based upon first color image data, first color histogram descriptor data that indicates a number of occurrences in the first color image data of each of a plurality of colors;

generating first gray-scaled image data based upon the first color image data;

generating, based upon the first gray-scaled image data, first texture histogram descriptor data that indicates a number of occurrences in the first gray-scaled image data of each of a plurality of edge orientations;

generating, based upon second color image data, second color histogram descriptor data that indicates a number of occurrences in the second color image data of each of a plurality of colors;

generating second gray-scaled image data based upon the second color image data;

generating, based upon the second gray-scaled image data, second texture histogram descriptor data that indicates a number of occurrences in the second gray-scaled image data of each of a plurality of edge orientations;

generating first signature data based upon the first color histogram data and the first texture histogram data;

generating second signature data based upon the second color histogram data and the second texture histogram data;

determining whether the first color image data is a near duplicate of the second color image data by comparing the first signature data to the second signature data.

32. The apparatus as recited in claim 31, wherein:

the generating first signature data based upon the first color histogram data and the first texture histogram data includes generating first wavelet-based signature data by processing the first color histogram data and the first texture histogram data using a wavelet transform,

the generating second signature data based upon the second color histogram data and the second texture histogram data includes generating second wavelet-based signature data by processing the second color histogram data and the second texture histogram data using the wavelet transform, and

the comparing the first signature data to the second signature data includes comparing the first wavelet-based signature data to the second wavelet-based signature data.

33. The apparatus as recited in claim 32, wherein the wavelet transform is a Haar transform with uniform quantization.

34. The apparatus as recited in claim 32, wherein the comparing the first wavelet-based signature data to the second wavelet-based signature data includes determining a Hamming distance between the first wavelet-based signature data and the second wavelet-based signature data.

35. The apparatus as recited in claim 31, wherein the first signature data is generated by processing the first color histogram data and the first texture histogram data using vector quantization and the second signature data is generated by processing the second color histogram data and the second texture histogram data using the vector quantization.

36. The apparatus as recited in claim 35, wherein the comparing the first signature data to the second signature data includes identifying any exact matches of one or more portions of the first signature data with one or more portions of the second signature data.