System and method for detecting repetitions in a multimedia stream

• US 7,065,544 B2
• Filed: 11/29/2001
• Issued: 06/20/2006
• Est. Priority Date: 11/29/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Moreno, Pedro J.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Do, Chat C.
• Application Number:
  US09/997,731
• Publication Number:
  US 20030101144A1
• Time in Patent Office: 1,664 Days
• Field of Search: 708422-426, 704/200, 704/246, 704/244
• US Class Current: 708/422
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 2218/16 by matching signal segments

Abstract

Large amounts of multimedia data are transmitted over information networks in the form of a digital stream, analog video, or text captioning. Often, repetitions such as paid advertisements, theme music at the commencement of a TV broadcast, and common jingles and slogans occur in these streams. Detection of repetitions in a transmitted signal such as streaming audio or video is described, and includes extracting a plurality of samples from the information stream and accumulating the samples into segments comprising an interval of the transmitted signal. A vector indicative of the samples in each of the segments is generated, and each of the vectors in the segments is correlated to generate a covariance matrix, or signature, corresponding to the segment. Each of the covariance matrices are aggregated into a sequence of covariance matrices and compared to other covariance matrices to generate a distance matrix. The distance matrix includes a distance value, indicative of the similarity between the distance matrices, as a result of the comparing of each matrix. The distance matrix is then traversed to determine similar sequences of covariance matrices.

Claims

1. A method of matching sequences of signals from an information stream comprising:

extracting a stream of samples from a subject information stream, each of the extracted samples comprising a portion of the information stream;

computing, for each of the samples, a vector quantity indicative of the data in the sample;

correlating the vectors to generate a signature indicative of the stream of samples;

comparing the generated signatures to signatures generated from a match stream of samples using a distance metric to generate distance values;

generating, as a result of the comparing, a distance matrix containing entries of the distance values and indicative of signatures generated from similar samples;

traversing the distance matrix to determine if a similar distance value sequence is found;

querying, when a similar distance value sequence is found in the distance matrix, a library of previously found distance value sequences;

storing the distance value sequence in the library if a match is not found as a result of the querying;

updating, if a match is found as a result of the querying, a timestamp corresponding to the matching distance value sequence in the library;

traversing the distance value sequences in the library;

examining each of the timestamps of the distance value sequences; and

purging, when the timestamp is beyond a predetermined threshold, the distance value sequence corresponding to the timestamp.

2. The method of claim 1 wherein correlating includes generating the signature distinctively from signatures generated for other streams of samples.

3. The method of claim 1 wherein the correlating generates a covariance matrix as a signature indicative of the stream of samples.

4. The method of claim 1 further comprising arranging the samples into a plurality of segments.

5. The method of claim 1 wherein each of the extracted samples comprises a predetermined interval of the subject information stream.

6. The method of claim 1 wherein the match stream is the extracted stream of samples itself.

7. The method of claim 1 wherein the match stream is indicative of a predetermined sequence of samples stored from previously transmitted samples.

8. The method of claim 7 wherein signatures corresponding to the predetermined sequence are stored in a library.

9. A method of detecting repetitions in an information stream comprising:

providing an information stream of multimedia data corresponding to a transmitted signal;

extracting a plurality of samples from the information stream;

accumulating the samples into segments comprising a predetermined interval of the transmitted signal;

generating respective vectors indicative of the samples in each of the segments;

for each segment, correlating the vectors in the segments to generate a respective covariance matrix corresponding to the segment;

aggregating each of the covariance matrices corresponding to the segments into a sequence of covariance matrices;

comparing each of the covariance matrices in the sequence with each other covariance matrix in the sequence to generate a distance matrix;

traversing the distance matrix to determine if a similar distance value sequence is found;

querying, when a similar distance value sequence is found in the distance matrix, a library of previously found distance value sequences;

storing the distance value sequence in the library if a match is not found as a result of the querying;

updating, if a match is found as a result of the querying, a timestamp corresponding to the matching distance value sequence in the library;

traversing the distance value sequences in the library;

examining each of the timestamps of the distance value sequences; and

purging, when the timestamp is beyond a predetermined threshold, the distance value sequence corresponding to the timestamp.

10. The method of claim 9 wherein generating the distance matrix further comprises generating a distance value, indicative of the similarity between the distance matrices, as a result of the comparing.

11. The method of claim 9 further comprising traversing the distance matrix to determine similar sequences of covariance matrices.

12. The method of claim 11 wherein determining similar sequences further comprises searching for diagonals of similar distance values.

13. The method of claim 12 wherein searching for diagonals of similar distance values includes searching for distance values within a predetermined threshold.

14. The method of claim 9 wherein the covariance matrices correspond to a multidimensional space and comparing the covariance matrices further comprises:

determining, for each of the covariance matrices, a location in the multidimensional space; and

computing a distance value indicative of the distance between the covariance matrices in the multidimensional space.

15. The method of claim 14 further comprising ranking the distance values and storing the ranking in the distance matrix.

16. The method of claim 15 wherein a matching sequence is determined by similar diagonal values in the distance matrix.

17. The method of claim 16 wherein the similar diagonal values form a contiguous sequence for a predetermined number of locations in the distance matrix.

18. The method of claim 14 wherein the multidimensional space further comprises at least 39 dimensions.

19. The method of claim 9 wherein the information stream further comprises streaming audio or video.

20. A system for detecting repetitions in an information stream comprising:

a stream processor operable to extract a stream of samples from the subject information stream and further operable to arrange the samples into a plurality of segments, each of the samples comprising a portion of the information stream;

a segment processor operable to receive the segments and to compute, for each sample in the segments, a vector indicative of the data in the sample;

a correlator operable to correlate each of the vectors in at least one of the segments to generate a signature indicative of the segment;

a distance processor responsive to the correlator and operable to compare the signature to signatures generated from a match stream of samples using a distance metric to generate distance values, and further operable to generate, as a result of the comparing, a distance matrix containing entries of the distance values and indicative of signatures generated from similar samples in the match stream;

means for traversing the distance matrix to determine if a similar distance value sequence is found;

means for querying, when a similar distance value sequence is found in the distance matrix, a library of previously found distance value sequences;

means for storing the distance value sequence in the library if a match is not found as a result of the querying;

means for updating, if a match is found as a result of the querying, a timestamp corresponding to the matching distance value sequence in the library;

means for traversing the distance value sequences in the library;

means for examining each of the timestamps of the distance value sequences; and

means for purging, when the timestamp is beyond a predetermined threshold, the distance value sequence corresponding to the timestamp.

21. The system of claim 20 wherein the signature generated by the correlator is distinctive from signatures generated from other samples.

22. The system of claim 21 wherein the signature is a covariance matrix.

23. The system of claim 20 wherein each of the segments comprises a predetermined interval of the information stream.

24. The system of claim 20 wherein the match stream is the stream of samples itself.

25. The system of claim 20 wherein the match stream is indicative of a predetermined sequence of samples stored from previously transmitted samples.

26. The system of claim 25 wherein the signature corresponding to the predetermined sequence is stored in a library.

27. A computer program product encoded in a tangible computer readable medium having computer program code for matching sequences of signals from an information stream comprising:

computer program code for extracting a stream of samples from a subject information stream, each of the extracted samples comprising a portion of the information stream;

computer program code for computing, for each of the samples, a vector quantity indicative of the data in the sample;

computer program code for correlating the vectors to generate a signature indicative of the stream of samples, computer program code for comparing the generated signatures to signatures generated from a match stream of samples using a distance metric to generate distance values, computer program code for generating, as a result of the comparing, a distance matrix containing entries of the distance values and indicative of signatures generated from similar samples, computer program code for traversing the distance matrix to determine if a similar distance value sequence is found;

computer program code for querying, when a similar distance value sequence is found in the distance matrix, a library of previously found distance value sequences, computer program code for storing the distance value sequence in the library if a match is not found as a result of the querying;

computer program code for updating, if a match is found as a result of the querying, a timestamp corresponding to the matching distance value sequence in the library;

computer program code for traversing the distance value sequences in the library;

computer program code for examining each of the timestamps of the distance value sequences; and

computer program code for purging, when the timestamp is beyond a predetermined threshold, the distance value sequence corresponding to the timestamp.

28. A system for detecting repetitions in an information stream comprising:

means for extracting a stream of samples from a subject information stream, each of the extracted samples comprising a portion of the information stream;

means for computing, for each of the samples, a vector quantity indicative of the data in the sample;

means for correlating the vectors to generate a signature indicative of the stream of samples;

means for comparing the generated signatures to signatures generated from a match stream of samples using a distance metric to generate distance values;

means for generating, as a result of the comparing, a distance matrix containing entries of the distance values and indicative of signatures generated from similar samples;

means for traversing the distance matrix to determine if a similar distance value sequence is found;

means for querying, when a similar distance value sequence is found in the distance matrix, a library of previously found distance value sequences;

means for storing the distance value sequence in the library if a match is not found as a result of the querying;

means for updating, if a match is found as a result of the querying, a timestamp corresponding to the matching distance value sequence in the library;

means for traversing the distance value sequences in the library;

means for examining each of the timestamps of the distance value sequences; and

means for purging, when the timestamp is beyond a predetermined threshold, the distance value sequence corresponding to the timestamp.