Method of Characterizing the Overlap of Two Media Segments

• US 20080091366A1
• Filed: 06/24/2005
• Published: 04/17/2008
• Est. Priority Date: 06/24/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Avery Wang, Landmark Digital Services LLC
• Inventors: Wang, Avery
• Granted Patent: US 7,739,062 B2
• Time in Patent Office: Days
• US Class Current: 702/71
• CPC Class Codes: H04H 20/14 for monitoring programmes
• CPC Class Codes: H04H 60/37 for identifying segments of broadcast information, e.g. scenes or extracting programme ID
• CPC Class Codes: H04H 60/58 of audio determination or detection of speech characteristics in general G10L25/00; speech recognition in general G10L15/00

Abstract

A method of characterizing the overlap of two media segments is provided. In an instance where there is some amount of overlap of a file and a data sample, the file could be an excerpt of an original file and begin and end within the data sample. By matching identified features of the file with identified features of the data sample, a beginning and ending time of a portion of the file that is within the data sample can be determined. Using these times, a length of the file within the data sample can also be determined

Claims

1. A method of identifying common content between a first data stream and a second data stream comprising:

determining a first set of content features from the first data stream, each feature in the first set of content features occurring at a corresponding time offset in the first data stream;

determining a second set of content features from the second data stream, each feature in the second set of content features occurring at a corresponding time offset in the second data stream;

identifying matching pairs of features between the first set of content features and the second set of content features; and

within all of the matching pairs of features, identifying an earliest time offset corresponding to a feature in a given matching pair.

2. The method of claim 1, wherein the first data stream and the second data stream comprise audio streams.

3. The method of claim 1, further comprising within all of the matching pairs of features, identifying a latest time offset corresponding to a feature in a given matching pair.

4. The method of claim 3, further comprising determining a length of content from the second data stream that is present within the first data stream.

5. The method of claim 4, wherein determining the length of content from the second data stream that is present within the first data stream comprises determining a difference between the earliest time offset and the latest time offset.

6. The method of claim 1, further comprising generating a support list that includes a listing of matching time offset pairs that each corresponds to time-offsets within the first data stream and the second data stream where a matching pair of features is found.

7. The method of claim 6, further comprising obtaining a relative time offset of the second data stream within the first data stream, and wherein identifying matching pairs of features between the first set of content features and the second set of content features comprises identifying corresponding features within a predetermined tolerance and corresponding time offsets within a predetermined tolerance of the relative time offset.

8. The method of claim 6, wherein the support list characterizes an overlap region between the first data stream and the second data stream.

9. The method of claim 6, further comprising:

determining from the support list a time point density at various time offsets in the overlap region,

whereby the time point density characterizes a confidence of identified matching features.

10. The method of claim 9, wherein determining from the support list the time point density at various time offsets in the overlap region comprises:

determining a number of time points present within a span of a predetermined time interval T_d around a desired point t; and

searching the support list for a number of points in an interval [t−

T_d, t+T_d].

11. The method of claim 10, further comprising discarding from the support list time offsets that are in insufficiently dense neighborhoods.

12. The method of claim 11, wherein a time offset point is in a sufficiently dense neighborhood if there is at least a predetermined number of neighboring points within a predetermined time interval from a first time offset point within a matching time offset pair.

13. The method of claim 11, wherein the time offset point is in an insufficiently dense neighborhood if there is not at least a predetermined number of neighboring points within a predetermined time interval from a first time offset point within a matching time offset pair, wherein the predetermined time interval is [t−

T_d, t+T_d].

14. The method of claim 6, further comprising:

determining an earliest time from the support list; and

determining a latest time from the support list,

whereby the earliest time and the latest time in the support list characterize a length of an overlap region between the first data stream and the second data stream.

15. The method of claim 14, further comprising adjusting the earliest time and the latest time for density edge effects.

16. The method of claim 15, wherein adjusting the earliest time and the latest time for density edge effects comprises:

identifying a lowest time offset and a highest time offset within the support list;

subtracting a predetermined density compensation factor from the lowest time offset; and

adding a predetermined density-compensation factor to the highest time offset.

17. The method of claim 14, further comprising determining an overlap time interval by subtracting the earliest time from the latest time.

18. The method of claim 14, wherein a feature density is d time points per unit time interval when describing a valid overlapping region between the first data stream and the second data stream, and wherein an average time interval between feature points is 1/d, the method further comprising:

estimating an interval around the earliest time from the support list and the latest time from the support list to be [T_earliest−

½

d, T_latest+½

d]; and

calculating a length of an overlap region between the first data stream and the second data stream to be the difference between (T_earliest−

½

d) and (T_latest+½

d).

19. The method of claim 1, further comprising:

for each matching pair of features, forming an associated time-pair from the respective corresponding time offsets in the first data stream and the second data stream;

determining from the time-pairs a time-pair regression line; and

discarding identified matching pairs of features that deviate substantially from the time-pair regression line.

20. The method of claim 19, wherein determining from the time-pairs a time-pair regression line comprises:

for each time-pair, forming a time-pair relative offset by subtracting a first time offset of the time-pair from a second time offset of the time-pair;

forming a histogram of the time-pair relative offsets; and

identifying a peak in the histogram,

whereby the peak determines a best relative offset of the time-pair regression line.

21. The method of claim 1, wherein determining the first set of content features from the first data stream and the second set of content features from the second data stream comprises identifying peaks within a local frequency decomposition of the first data stream and the second data stream.

22. The method of claim 21, further comprising:

calculating a vector from the local frequency decomposition; and

determining a feature characterized by the vector.

23. The method of claim 1, wherein a content feature is a frequency-spectral peak of a data stream.

24. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 1.

25. A method of identifying content within a data stream comprising:

receiving a first data stream that includes at least a portion of a second data stream;

determining a length of the portion of the second data stream contained within the first data stream; and

determining which portion of the second data stream is the portion included within the first data stream.

26. The method of claim 25, further comprising:

determining a first set of content features from the first data stream, each feature in the first set of content features occurring at a corresponding time offset in the first data stream;

determining a second set of content features from the second data stream, each feature in the second set of content features occurring at a corresponding time offset in the second data stream;

identifying features from the second set of content features that are in the first set of content features; and

determining the length of the portion of the second data stream within the first data stream from corresponding time offsets of features from the second set of content features that are in the first set of content features.

27. A method of identifying content within a data stream comprising:

determining a first set of content features from a first data stream, each feature in the first set of content features occurring at a corresponding time offset in the first data stream;

determining a second set of content features from a second data stream, each feature in the second set of content features occurring at a corresponding time offset in the second data stream;

identifying features from the second set of content features that are in the first set of content features;

from the identified features, identifying a set of time-pairs, wherein a time-pair includes a time offset in the first data stream associated with a feature from the first data stream and a time offset in the second data stream associated with a feature from the second data stream that matches the feature from the first data stream; and

identifying time-pairs within the set of time-pairs having a linear relationship.

28. The method of claim 27, further comprising determining a length of a portion of the second data stream that is within the first data stream.

29. The method of claim 28, wherein determining the length of the portion of the second data stream that is within the first data stream comprises:

within the set of time-pairs having the linear relationship, identifying an earliest corresponding time offset and a latest corresponding time offset; and

calculating a difference between the earliest corresponding time offset and the latest corresponding time offset.