Video comparison using color histograms

• US 8,897,554 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,692
• Publication Number:
  US 20130148884A1
• 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/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 video comparison using color histograms are disclosed. An example method disclosed herein to compare a first video and a second video comprises obtaining a first color histogram corresponding to a sequence of frames of the first video, obtaining a second color histogram corresponding to a sequence of frames of the second video, determining a first 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 video and the second video match based on the first comparison metric.

Claims

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

obtaining a first color histogram corresponding to a sequence of frames of the first video;

obtaining a second color histogram corresponding to a sequence of frames of the second video;

determining adjusted bin values of the second color histogram;

determining a first 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 video and the second video match based on the first 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 an adjusted bin value of the second color histogram for a respective color bin to be a smaller of a scaled bin value of the second color histogram for the respective color bin and a respective 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 first comparison metric comprises summing the differences between the bin values of the first color histogram and the respective adjusted bin values of the second color histogram to determine the first comparison metric.

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

6. A method as defined in claim 1 further comprising:

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

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

7. A method as defined in claim 6 wherein determining whether the first video and the second video match comprises determining that the first video and the second video match when at least one of the first comparison metric or the second comparison metric is less than or equal to a threshold.

8. A method as defined in claim 1 wherein obtaining the second color histogram corresponding to the sequence of frames of the second video comprises:

tiling the sequence of frames of the second video to form a composite image;

quantizing color values of a set of pixels sampled from the composite image; and

including the set of pixels in color bins of the second color histogram based on the quantized color values of the set of pixels.

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

obtain a first color histogram corresponding to a sequence of frames of a first video;

obtain a second color histogram corresponding to a sequence of frames of a second video;

determine adjusted bin values of the second color histogram;

determine a first 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 video and the second video match based on the first 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 determine the adjusted bin values by:

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

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

11. A tangible machine readable medium as defined in claim 9 wherein the machine readable instructions, when executed, further cause the machine to sum the differences between the bin values of the first color histogram and the respective adjusted bin values of the second color histogram to determine the first comparison metric.

12. 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 video and the second video match when the first comparison metric is less than or equal to a threshold.

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

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

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

14. A tangible machine readable medium as defined in claim 13 wherein to determine whether the first video and the second video match, the machine readable instructions, when executed, cause the machine to determine that the first video and the second video match when at least one of the first comparison metric or the second 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 videos;

a histogram generator to generate a test color histogram corresponding to a sequence of frames of an input test video; and

a histogram comparator to compare the test color histogram and a first reference color histogram corresponding to a first reference video to determine whether the input test video and the first reference video substantially match, the histogram comparator to;

determine a first comparison metric based on differences between bin values of the first reference color histogram and adjusted bin values of the test color histogram, the adjusted bin values of the test color histogram being determined by comparing scaled bin values of the test color histogram with respective ones of the bin values of the first reference color histogram;

determine a second comparison metric based on differences between bin values of the test color histogram and adjusted bin values of the first reference color histogram, the adjusted bin values of the first reference color histogram being determined by comparing scaled bin values of the first reference color histogram with respective ones of the bin values of the test color histogram; and

determine whether the input test video and the first reference video substantially match based on the first comparison metric and the second comparison metric.

16. An apparatus as defined in claim 15 wherein the histogram comparator is to determine the adjusted bin values by:

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

determining a respective adjusted bin value of the test color histogram for a respective color bin to be a smaller of a scaled bin value of the test color histogram for the respective color bin and a respective bin value of the first reference color histogram for the respective color bin;

scaling bin values of the first reference color histogram by the scale factor to determine the scaled bin values of the first reference color histogram; and

determining a respective adjusted bin value of the first reference color histogram for the respective color bin to be a smaller of a scaled bin value of the first reference color histogram for the respective color bin and a respective bin value of the test color histogram for the respective 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 the first comparison metric by summing the differences between the bin values of the first reference color histogram and the respective adjusted bin values of the test color histogram, and the histogram comparator is to determine the second comparison metric by summing the differences between the bin values of the test color histogram and the respective adjusted bin values of the first reference color histogram.

19. An apparatus as defined in claim 15 wherein the histogram comparator is to determine that the first reference video substantially matches the input test video when at least one of the first 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 the first reference video does not substantially match the input test video when the first comparison metric and the second comparison metric are each greater than the threshold.