Image comparison using color histograms

• US 8,897,553 B2
• Filed: 12/13/2011
• Issued: 11/25/2014
• Est. Priority Date: 12/13/2011
• Status: Active Grant

• Current Assignee: Nielsen Company (US) LLC (RR Donnelley & Sons Company)
• Original Assignee: The Nielsen Company LLC (MOOD Media Corporation)
• Inventors: Lee, Morris
• Primary Examiner(s): Dang, Duy M
• Application Number:
  US13/324,624
• Publication Number:
  US 20130148883A1
• Time in Patent Office: 1,078 Days
• Field of Search: 382/164, 382/165, 382/170, 382/305, 348/700, 348/722, 725/19, 709/224
• US Class Current: 382/165
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

Methods, apparatus and articles of manufacture for image comparison using color histograms are disclosed. An example method disclosed herein to compare a first image and a second image comprises obtaining a first color histogram for a first set of pixels sampled from the first image, obtaining a second color histogram for a second set of pixels sampled from the second image, determining a comparison metric based on differences between bin values of the first color histogram and adjusted bin values of the second color histogram, and determining whether the first image and the second image match based on the comparison metric.

Claims

1. A method to compare a first image and a second image, the method comprising:

obtaining a first color histogram for a first set of pixels sampled from the first image;

obtaining a second color histogram for a second set of pixels sampled from the second image;

determining adjusted bin values of the second color histogram;

determining a comparison metric based on differences between bin values of the first color histogram and the adjusted bin values of the second color histogram; and

determining whether the first image and the second image match based on the comparison metric.

2. A method as defined in claim 1, wherein determining the adjusted bin values of the second color histogram comprises:

scaling bin values of the second color histogram by a scale factor to determine scaled bin values of the second color histogram; and

determining the adjusted bin values of the second color histogram for respective color bins to be a smaller of a scaled bin value of the second color histogram for the respective color bin and a corresponding bin value of the first color histogram for the respective color bin.

3. A method as defined in claim 2 wherein the scale factor is substantially equal to two.

4. A method as defined in claim 1 wherein determining the comparison metric comprises:

determining the differences between the bin values of the first color histogram and the respective adjusted bin values of the second color histogram; and

summing the differences to determine the comparison metric.

5. A method as defined in claim 1 wherein determining whether the first image and the second image match based on the comparison metric comprises determining that the first image and the second image match when the comparison metric is less than or equal to a threshold.

6. A method as defined in claim 1 further comprising sampling uniformly-spaced pixels of the second image to obtain the second set of pixels.

7. A method as defined in claim 1 further comprising randomly sampling pixels of the second image to obtain the second set of pixels.

8. A method to compare a first image and a second image, the method comprising:

obtaining a first color histogram for a first set of pixels sampled from the first image;

obtaining a second color histogram for a second set of pixels sampled from the second image;

determining a comparison metric based on differences between bin values of the first color histogram and adjusted bin values of the second color histogram; and

determining whether the first image and the second image match based on the comparison metric, wherein the first image is included in a set of reference images, and further comprising;

determining a set of comparison metrics corresponding to comparing respective ones of the set of reference images with the second image, each comparison metric being based on differences between bin values of a respective reference color histogram for a respective reference image and respective adjusted bin values of the second color histogram that are determined based on scaled bin values of the second color histogram and the bin values of the respective reference color histogram;

identifying a smallest comparison metric among the set of comparison metrics; and

determining that the first image and the second image match when the smallest comparison metric corresponds to a comparison of the first image and the second image, and the smallest comparison metric is less than or equal to a threshold.

9. A tangible machine readable medium comprising machine readable instructions which, when executed, cause a machine to at least:

obtain a first color histogram for a first set of pixels sampled from a first image;

obtain a second color histogram for a second set of pixels sampled from a second image;

determine adjusted bin values of the second color histogram;

determine a comparison metric based on differences between bin values of the first color histogram and the adjusted bin values of the second color histogram; and

determine whether the first image and the second image match based on the comparison metric.

10. A tangible machine readable medium as defined in claim 9 wherein the machine readable instructions, when executed, further cause the machine to:

scale bin values of the second color histogram by a scale factor to determine scaled bin values of the second color histogram; and

determine the adjusted bin values of the second color histogram for respective color bins to be a smaller of a scaled bin value of the second color histogram for the respective color bin and a corresponding bin value of the first color histogram for the respective color bin.

11. A tangible machine readable medium as defined in claim 10 wherein the scale factor is substantially equal to two.

12. A tangible machine readable medium as defined in claim 9 wherein the machine readable instructions, when executed, further cause the machine to:

determine the differences between the bin values of the first color histogram and the respective adjusted bin values of the second color histogram; and

sum the differences to determine the comparison metric.

13. A tangible machine readable medium as defined in claim 9 wherein the machine readable instructions, when executed, cause the machine to determine that the first image and the second image match when the comparison metric is less than or equal to a threshold.

14. A tangible machine readable medium comprising machine readable instructions which, when executed, cause a machine to at least:

obtain a first color histogram for a first set of pixels sampled from a first image;

obtain a second color histogram for a second set of pixels sampled from a second image;

determine a comparison metric based on differences between bin values of the first color histogram and adjusted bin values of the second color histogram;

determine whether the first image and the second image match based on the comparison metric, wherein the first image is included in a set of reference images;

determine a set of comparison metrics corresponding to comparing respective ones of the set of reference images with the second image, each comparison metric being based on differences between bin values of a respective reference color histogram for a respective reference image and respective adjusted bin values of the second color histogram that are determined based on scaled bin values of the second color histogram and the bin values of the respective reference color histogram;

identify a smallest comparison metric among the set of comparison metrics; and

determine that the first image and the second image match when the smallest comparison metric corresponds to a comparison of the first image and the second image, and the smallest comparison metric is less than or equal to a threshold.

15. An apparatus comprising:

storage to store a set of reference color histograms corresponding to a respective set of reference images;

a histogram generator to generate a test color histogram for a set of pixels sampled from an input test image; and

a histogram comparator to;

determine a set of comparison metrics corresponding to comparing respective ones of the set of reference images with the input test image, respective ones of the comparison metrics being based on differences between bin values of a respective reference color histogram for a respective reference image and respective adjusted bin values of the test color histogram that are determined based on comparing scaled bin values of the test color histogram with the bin values of the respective reference color histogram; and

process the set of comparison metrics to determine whether the input test image matches one or more reference images in the set of reference images.

16. An apparatus as defined in claim 15 wherein the histogram comparator is to:

scale bin values of the test color histogram by a scale factor to determine the scaled bin values of the test color histogram; and

determine, for a first reference image in the set of reference images and a corresponding first reference color histogram in the set of color histograms, a respective adjusted bin value of the test color histogram for a particular color bin to be a smaller of a scaled bin value of the test color histogram for the particular color bin and a respective bin value of the first reference color histogram for the particular color bin.

17. An apparatus as defined in claim 16 wherein the scale factor is substantially equal to two.

18. An apparatus as defined in claim 15 wherein the histogram comparator is to determine each comparison metric to be a sum of the differences between the bin values of the respective reference color histogram for the respective reference image and the respective adjusted bin values of the test color histogram.

19. An apparatus as defined in claim 15 wherein the histogram comparator is to:

identify a lowest comparison metric among the set of comparison metrics; and

determine that a first reference image in the set of reference images matches the input test image when the lowest comparison metric is a first comparison metric corresponding to comparing the first reference image and the input test image, and the lowest comparison metric is less than or equal to a threshold.

20. An apparatus as defined in claim 19 wherein the histogram comparator is to determine that no reference images match the input test image when the lowest comparison metric is greater than the threshold.