Iterative, maximally probable, batch-mode commercial detection for audiovisual content

• US 6,993,245 B1
• Filed: 11/18/2000
• Issued: 01/31/2006
• Est. Priority Date: 11/18/1999
• Status: Active Grant

• Current Assignee: Interval Licensing LLC
• Original Assignee: Vulcan Patents LLC
• Inventors: Harville, Michael L.
• Primary Examiner(s): TRAN, THAI Q
• Application Number:
  US09/715,901
• Time in Patent Office: 1,900 Days
• Field of Search: 386/1, 386/46, 358/908, 725/22, 348700-702
• US Class Current: 386/250
• CPC Class Codes: G11B 27/031 Electronic editing of digitised analogue information signals, e.g. audio or video signals
• CPC Class Codes: H04N 21/438 Interfacing the downstream path of the transmission network originating from a server, e.g. retrieving encoded video stream packets from an IP network
• CPC Class Codes: H04N 21/44008 involving operations for analysing video streams, e.g. detecting features or characteristics in the video stream arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59
• CPC Class Codes: H04N 21/812 involving advertisement data advertising per se G06Q30/02
• CPC Class Codes: H04N 5/76 Television signal recording
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/782 on tape
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 5/907 using static stores, e.g. storage tubes or semiconductor memories H04N5/91 takes precedence
• CPC Class Codes: H04N 7/163 by receiver means only
• CPC Class Codes: H04N 9/87 Regeneration of colour television signals H04N9/80 takes precedence
• CPC Class Codes: Y10S 358/908 Pause control, i.e. "commercial killers"

Abstract

Identification of starting and ending times of commercial breaks and commercials within those commercial breaks found in audiovisual content is disclosed. A solution to a “batch optimization” problem is used in which commercial locations within a set of audiovisual content are detected as a group by choosing a set of commercial locations which optimizes a cost function which can include considerations of, for example, 1) one or more cues, 2) relative locations of commercials within the audiovisual content, and/or 3) probability models based on statistics obtained regarding characteristics of typical commercial and commercial breaks. Optimization can be done over the total set of commercial location decisions, rather than on a per-commercial basis. Additionally, the cost function can be iteratively evaluated and many more types of cues and combinations of cues can be used in detection of commercials.

Claims

1. A method for detecting one or more commercial breaks in a set of audiovisual content spanning a duration of time, each commercial break including one or more commercials, the method comprising the steps of:

identifying candidate times within the duration of time spanned by the set of audiovisual content based on an evaluation of one or more cues identified in the audiovisual content, each candidate time representing a possible starting and/or ending time of a commercial;

assigning a score to each candidate time;

evaluating, for each of one or more candidate times,

     1) one or more secondary cues that are each different from the one or more cues used to identify the candidate time, and/or

     2) the relationship between the candidate time and one or more other candidate times, wherein the score assigned to the candidate time can be adjusted based on the evaluation; and

constructing the one or more commercial breaks based on an evaluation of

     1) the scores of the candidate times after the step of evaluating and

     2) a relationship between, or relationships among, the candidate times, including by;

comparing a relationship between, or relationships among, the candidate times to one or more probability models that specify an expected relationship between, or relationships among, commercial start and/or end times;

selecting the candidate time with the highest adjusted score to be a commercial start and/or end time in a current commercial break;

successively evaluating each candidate time not yet part of a commercial break, in order of decreasing adjusted score, for possible inclusion in the current commercial break as a commercial start and/or end time, wherein the evaluation of each candidate time for possible inclusion in the current commercial break comprises the steps of;

determining whether each probability of the temporal separation between the candidate time being evaluated and a candidate time already included in the current commercial break is above a specified threshold value;

determining whether the probability of the duration of the current commercial break, if the candidate time being evaluated is added to the current commercial break, is above a specified threshold value; and

determining whether each probability of the temporal separation between the candidate time being evaluated and an already existing commercial break, if any, is above a specified threshold value, wherein if each of the three probabilities is above the corresponding specified threshold value, the candidate time being evaluated is added to the current commercial break;

determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break;

if there are candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break, performing the steps of;

selecting the candidate time having the highest adjusted score above the specified threshold value that has not yet been included in a commercial break and has not yet been excluded from inclusion in a commercial break;

determining whether each probability of the temporal separation between the selected candidate time and an already existing commercial break is above a specified threshold value;

if each probability is above the specified threshold value, performing the steps of;

identifying the selected candidate time as a commercial start and/or end time in a current commercial break; and

repeating the step of successively evaluating; and

if each probability is not above the specified threshold value, performing the steps of;

excluding the selected candidate time from inclusion in a commercial break; and

repeating the step of determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break; and

if there are no candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break, performing the step of identifying the start and end time of each commercial break and the start time of each commercial in each commercial break.

2. A method as in claim 1, further comprising the step of identifying the presence of one or more cues in the audiovisual content.

3. A method as in claim 2, wherein the step of identifying the presence of one or more cues in the audiovisual content further comprises evaluating the audiovisual content to identify the presence of one or more cues regarding one or more of the following possible characteristics of the audiovisual content:

1) an audio pause in the audio content,

     2) a sequence of black frames in the visual content,

     3) a scene cut or fade in the visual content,

     4) a significant change in average volume in the audio content,

     5) the presence of music in the audio content,

     6) speaker identity,

     7) the density of scene breaks or fades in the visual content,

     8) the absence of a usually present network icon,

     9) the degree of motion in a period of visual content,

     10) the presence of text in the visual content,

     11) the occurrence of specified closed-captioning formatting signals and

     12) the absence of closed-captioning.

4. A method as in claim 2, wherein the step of identifying the presence of one or more cues in the audiovisual content further comprises evaluating the audiovisual content to identify the presence of a cue regarding the absence of a usually present network icon.

5. A method as in claim 2, wherein the step of identifying the presence of one or more cues in the audiovisual content further comprises evaluating the audiovisual content to identify the presence of a cue regarding the presence of music in the audio content.

6. A method as in claim 2, wherein the step of identifying the presence of one or more cues in the audiovisual content further comprises evaluating the audiovisual content to identify the presence of a cue regarding the density of scene breaks or fades in the visual content.

7. A method as in claim 2, wherein the step of identifying the presence of one or more cues in the audiovisual content further comprises evaluating the audiovisual content to identify the presence of a cue regarding speaker identity.

8. A method as in claim 1, wherein the step of assigning further comprises the step of assigning the same score to each candidate time.

9. A method as in claim 1, wherein the step of assigning further comprises the step of assigning a score to each candidate time in accordance with the type of cue or cues evaluated to identify the candidate time.

10. A method as in claim 1, wherein the step of assigning further comprises the step of assigning a score to each candidate time in accordance with the degree of presence in the audiovisual content of the cue or cues evaluated to identify the candidate time.

11. A method as in claim 1, wherein the step of assigning further comprises the step of assigning a score to each candidate time in accordance with the degree of confidence of identification of the cue or cues evaluated to identify the candidate time.

12. A method as in claim 1, wherein the step of evaluating further comprises the step of determining the presence or absence of a secondary cue within a time window that includes the candidate time or to which the candidate time is sufficiently proximate.

13. A method as in claim 12, wherein the duration and/or location of the time window depends on the type of the secondary cue.

14. A method as in claim 12, wherein the score is adjusted in accordance with the type of the secondary cue.

15. A method as in claim 12, wherein the score is adjusted in accordance with the degree of presence of the secondary cue.

16. A method as in claim 12, wherein the score is adjusted in accordance with the degree of confidence of identification of the secondary cue.

17. A method as in claim 1, wherein the step of evaluating further comprises the step of comparing the candidate time and/or a relationship between, or relationships among, the candidate time and one or more other candidate times to one or more probability models that specify one or more expected characteristics of commercial start and/or end times, and/or an expected relationship between, or relationships among, commercial start and/or end times.

18. A method as in claim 17, wherein one of the probability models specifies the expected temporal separation of commercial start and end times.

19. A method as in claim 17, wherein one of the probability models specifies the expected location of one or more commercial start and/or end times within the duration of time spanned by the set of audiovisual content.

20. A method as in claim 17, wherein one of the probability models is derived from statistics concerning any type of audiovisual content.

21. A method as in claim 17, wherein one of the probability models is derived from statistics concerning only audiovisual content that is of the same type as the set of audiovisual content in which the one or more commercials breaks are being detected.

22. A method as in claim 1, wherein the score adjustment varies in accordance with the magnitude of the score before adjustment.

23. A method as in claim 1, further comprising the step of eliminating candidate times having an adjusted score below a specified threshold.

24. A method as in claim 1, wherein one of the probability models specifies the expected duration of a commercial break.

25. A method as in claim 1, wherein one of the probability models specifies the expected temporal separation of commercial breaks.

26. A method as in claim 1, wherein one of the probability models is derived from statistics concerning any type of audiovisual content.

27. A method as in claim 1, wherein one of the probability models is derived from statistics concerning only audiovisual content that is of the same type as the set of audiovisual content in which the one or more commercials breaks are being detected.

28. A method as in claim 1, wherein the step of constructing further comprises the steps of:

determining whether there are any candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break;

if there are candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break, performing the steps of;

for each such candidate time that has not yet been included in a commercial break, performing the steps of;

identifying the most temporally proximate commercial break to the candidate time;

determining whether the probability of the duration of the most temporally proximate commercial break, if the candidate time is added to that commercial break, is above a specified threshold value; and

determining whether each probability of the temporal separation between the candidate time and a commercial break other than the most temporally proximate commercial break, if any, is above a specified threshold value, wherein if each of the two probabilities are above the corresponding specified threshold value, the candidate time is added to the most temporally proximate commercial break;

if the candidate time is added to the most temporally proximate commercial break, performing the steps of;

repeating the step of successively evaluating, for each candidate time having an adjusted score above a specified threshold value that has not yet been included in a commercial break, wherein the resulting commercial break is a modified commercial break;

for each candidate time of the modified commercial break, performing the steps of;

computing the average of the probabilities of each temporal separation between the candidate time and a temporally adjacent candidate time;

if the average is below a specified threshold value, performing the steps of;

 

if the adjusted score of the candidate time is lower than the average adjusted score of the adjacent candidate times, eliminating the candidate time; and

 

if the adjusted score of the candidate time is not lower than the average adjusted score of the adjacent candidate times, eliminating any adjacent candidate time that is less than a specified duration of time from the candidate time;

computing the average score of all of the candidate times of the modified commercial break;

comparing the average score of all of the candidate times of the modified commercial break to the average score of all of the candidate times of the commercial break before modification;

if the average score of all of the candidate times of the modified commercial break is greater than the average score of all of the candidate times of the original commercial break before modification, replacing the original commercial break with the modified commercial break; and

if the average score of all of the candidate times of the modified commercial break is not greater than the average score of all of the candidate times of the original commercial break before modification, retaining the original commercial break; and

if the candidate time is not added to the most temporally proximate commercial break, performing the step of excluding the candidate time from inclusion in a commercial break; and

determining whether a modified commercial break replaced an original commercial break;

if a modified commercial break replaced an original commercial break, repeating the step of determining whether there are any candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and the conditional step appropriate for the result of that determination; and

if no modified commercial break replaced an original commercial break, performing the step of maintaining the identification of the start and end time of each commercial break and the start time of each commercial in each commercial break as existent prior to the step of determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break; and

if there are no candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break, performing the step of maintaining the identification of the start and end time of each commercial break and the start time of each commercial in each commercial break as existent prior to the step of determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break.

29. A method as in claim 1, further comprising the step of editing the audiovisual content based on the detected commercial breaks.

30. A method as in claim 29, wherein the step of editing the audiovisual content based on the detected commercial breaks further comprises the step of deleting the audiovisual content representing a commercial.

31. A method as in claim 29, wherein the step of editing the audiovisual content based on the detected commercial breaks further comprises the step of modifying the audiovisual content representing a commercial.

32. A method for viewing audiovisual content in which commercial breaks have been detected as in claim 1, comprising the step of skipping a commercial during viewing of the audiovisual content.

33. A method for reviewing audiovisual content in which commercial breaks have been detected as in claim 1, comprising the step of searching for a commercial within the audiovisual content.

34. A method as in claim 1, wherein the audiovisual content is represented by a television signal.

35. A method as in claim 1, wherein the audiovisual content is represented by computer-readable data.

36. A method as in claim 35, wherein audiovisual content is represented by computer-readable data acquired via a computer network.

37. A method as in claim 36, wherein audiovisual content is represented by computer-readable data acquired via the Internet.

38. A method as in claim 1, wherein the method detects the one or more commercial breaks in real time as the audiovisual content is acquired for display by a display device.

39. A system for detecting one or more commercial breaks in a set of audiovisual content spanning a duration of time, each commercial break including one or more commercials, the system comprising:

means for identifying candidate times within the duration of time spanned by the set of audiovisual content based on an evaluation of one or more cues identified in the audiovisual content, each candidate time representing a possible starting and/or ending time of a commercial;

means for assigning a score to each candidate time;

means for evaluating, for each of one or more candidate times,

     1) one or more secondary cues that are each different from the one or more cues used to identify the candidate time, and/or

     2) the relationship between the candidate time and one or more other candidate times, wherein the score assigned to the candidate time can be adjusted based on the evaluation; and

means for constructing the one or more commercial breaks based on an evaluation of

     1) the scores of the candidate times after the step of evaluating and

     2) a relationship between, or relationships among, the candidate times, comprising;

comparing a relationship between, or relationships among, the candidate times to one or more probability models that specify an expected relationship between, or relationships among, commercial start and/or end times;

selecting the candidate time with the highest adjusted score to be a commercial start and/or end time in a current commercial break;

successively evaluating each candidate time not yet part of a commercial break in order of decreasing adjusted score, for possible inclusion in the current commercial break as a commercial start and/or end time, wherein the evaluation of each candidate time for possible inclusion in the current commercial break comprises the steps of;

determining whether each probability of the temporal separation between the candidate time being evaluated and a candidate time already included in the current commercial break is above a specified threshold value;

determining whether the probability of the duration of the current commercial break, if the candidate time being evaluated is added to the current commercial break, is above a specified threshold value; and

determining whether each probability of the temporal separation between the candidate time being evaluated and an already existing commercial break, if any, is above a specified threshold value, wherein if each of the three probabilities is above the corresponding specified threshold value, the candidate time being evaluated is added to the current commercial break;

determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break;

if there are candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break, performing the steps of;

selecting the candidate time having the highest adjusted score above the specified threshold value that has not yet been included in a commercial break and has not yet been excluded from inclusion in a commercial break;

determining whether each probability of the temporal separation between the selected candidate time and an already existing commercial break is above a specified threshold value;

if each probability is above the specified threshold value, performing the steps of;

identifying the selected candidate time as a commercial start and/or end time in a current commercial break; and

repeating the step of successively evaluating; and

if each probability is not above the specified threshold value, performing the steps of;

excluding the selected candidate time from inclusion in a commercial break; and

repeating the step of determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break; and

if there are no candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break, performing the step of identifying the start and end time of each commercial break and the start time of each commercial in each commercial break.

40. A computer readable storage medium or media encoded with one or more computer programs including instructions for detecting one or more commercial breaks in a set of audiovisual content spanning a duration of time, each commercial break including one or more commercials, the one or more computer programs comprising:

instructions for identifying candidate times within the duration of time spanned by the set of audiovisual content based on an evaluation of one or more cues identified in the audiovisual content, each candidate time representing a possible starting and/or ending time of a commercial;

instructions for assigning a score to each candidate time;

instructions for evaluating, for each of one or more candidate times,

     1) one or more secondary cues that are each different from the one or more cues used to identify the candidate time, and/or

     2) the relationship between the candidate time and one or more other candidate times, wherein the score assigned to the candidate time can be adjusted based on the evaluation; and

instructions for constructing the one or more commercial breaks based on an evaluation of

     1) the scores of the candidate times after the step of evaluating and

     2) a relationship between, or relationships among, the candidate times, comprising;

comparing a relationship between, or relationships among, the candidate times to one or more probability models that specify an expected relationship between, or relationships among, commercial start and/or end times;

selecting the candidate time with the highest adjusted score to be a commercial start and/or end time in a current commercial break;

successively evaluating each candidate time not yet part of a commercial break, in order of decreasing adjusted score, for possible inclusion in the current commercial break as a commercial start and/or end time, wherein the evaluation of each candidate time for possible inclusion in the current commercial break comprises the steps of;

determining whether each probability of the temporal separation between the candidate time being evaluated and a candidate time already included in the current commercial break is above a specified threshold value;

determining whether the probability of the duration of the current commercial break, if the candidate time being evaluated is added to the current commercial break, is above a specified threshold value; and

determining whether each probability of the temporal separation between the candidate time being evaluated and an already existing commercial break, if any, is above a specified threshold value, wherein if each of the three probabilities is above the corresponding specified threshold value, the candidate time being evaluated is added to the current commercial break;

determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break;

if there are candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break, performing the steps of;

selecting the candidate time having the highest adjusted score above the specified threshold value that has not yet been included in a commercial break and has not yet been excluded from inclusion in a commercial break;

determining whether each probability of the temporal separation between the selected candidate time and an already existing commercial break is above a specified threshold value;

if each probability is above the specified threshold value, performing the steps of;

identifying the selected candidate time as a commercial start and/or end time in a current commercial break; and

repeating the step of successively evaluating; and

if each probability is not above the specified threshold value, performing the steps of;

excluding the selected candidate time from inclusion in a commercial break; and

repeating the step of determining whether there are candidate times having an adjusted score above a specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break; and

if there are no candidate times having an adjusted score above the specified threshold value that have not yet been included in a commercial break and have not yet been excluded from inclusion in a commercial break, performing the step of identifying the start and end time of each commercial break and the start time of each commercial in each commercial break.