System and method for detecting repetitions in a multimedia stream
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
28 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
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. - View Dependent Claims (21, 22, 23, 24, 25, 26)
-
-
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.
- 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;
-
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.
-
Specification