Method and apparatus for automatic detection and identification of broadcast audio and video signals
First Claim
1. A method executed by a signal processing system for determining whether a portion of a detected audio signal of a pre-determined number of sequential time frame duration is substantially the same signal as a portion of at least one known signal out of a plurality of known audio signals, each portion of the plurality of known signals comprised of a plurality of sequential time frame duration and each time frame of the known audio signal having an identification index and time frame index, comprising:
- Calculating for at least one of the time frames of at least one of the known audio signals a first signature comprised of a set of numbers derived from a pre-determined number of spectral magnitude values detected during the time frame;
Storing in a computer database each first signature with a reference to its corresponding signal identification index and a reference to the approximate location in time of the time frame from substantially the beginning of said known signal;
Calculating for at least one of the time frames of the detected signal a second signature comprised of a set of numbers derived from a pre-determined number of spectral magnitude values detected during the time frame;
Selecting from the stored set of first signatures those first signatures that in relation to the second signatures meet a predetermined matching test;
Determining whether the time frame indices corresponding to those selected first signatures meet a sequencing test.
4 Assignments
0 Petitions
Accused Products
Abstract
This invention relates to the automatic detection and identification of broadcast programming, for example music, speech or video that is broadcast over radio, television, the Internet or other media. “Broadcast” means any readily available source of content, whether now known or hereafter devised, including streaming, peer to peer delivery or detection of network traffic. A known program is registered by deriving a numerical code for each of many short time segments during the program and storing the sequence of numerical codes and a reference to the identity of the program. Detection and identification of an input signal occurs by similarly extracting the numerical codes from it and comparing the sequence of detected numerical codes against the stored sequences. Testing criteria is applied that optimizes the rate of correct detections of the registered programming. Other optimizations in the comparison process are used to expedite the comparison process.
27 Citations
26 Claims
-
1. A method executed by a signal processing system for determining whether a portion of a detected audio signal of a pre-determined number of sequential time frame duration is substantially the same signal as a portion of at least one known signal out of a plurality of known audio signals, each portion of the plurality of known signals comprised of a plurality of sequential time frame duration and each time frame of the known audio signal having an identification index and time frame index, comprising:
-
Calculating for at least one of the time frames of at least one of the known audio signals a first signature comprised of a set of numbers derived from a pre-determined number of spectral magnitude values detected during the time frame; Storing in a computer database each first signature with a reference to its corresponding signal identification index and a reference to the approximate location in time of the time frame from substantially the beginning of said known signal; Calculating for at least one of the time frames of the detected signal a second signature comprised of a set of numbers derived from a pre-determined number of spectral magnitude values detected during the time frame; Selecting from the stored set of first signatures those first signatures that in relation to the second signatures meet a predetermined matching test; Determining whether the time frame indices corresponding to those selected first signatures meet a sequencing test. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 25, 26)
-
-
19. A method executed by an audio signal processing system for determining whether a portion of a detected audio signal of a pre-determined number of sequential time frame duration is substantially the same signal as a portion of at least one known audio signal out of a plurality of a known signals, each portion of the plurality of known signals comprised of a plurality of sequential time frame duration and each time frame of the known signal having an identification index and a time frame index, comprising:
-
Calculating for at least one of the time frames of at least one of the known signals a first signature comprised of a set of numbers derived from a pre-determined number of frequency magnitude values detected during the time frame; Storing in a computer database each first signature with a reference to its corresponding known identification index and a reference to the approximate location in time of the time frame from substantially the beginning of said known signal; Calculating for at least one of the time frames of the detected signal a second signature comprised of a set of numbers derived from a pre-determined number of frequency magnitude values detected during the time frame; Selecting from the stored set of first signatures those first signatures that meet a predetermined matching test with the second signatures; Storing in at least one data structure and the time frame indices and the identification indices corresponding to the matching first signatures; Deleting from the data structures those time frame indices and corresponding identification indices where fewer than approximately K+1 enters in the list have the same identification index, where K is calculated such that 2K+1 is equal approximately to the predetermined number of time frames constituting the portion of the detected signal; Deleting from the list those time frame indices and identification indices where the time frame indices of the first signature are not confirmed to increase substantially in synchrony with the time frame indices of the detected signal.
-
-
20. A method executed by a audio signal processing system of searching a database comprised of a set of at least one predetermined first signatures with corresponding identification indices and time frame indices, where each first signature represents the frequency components of a known audio signal during the time frame, the search looking for all first signatures that meet a pre-determined matching test with a second signature, where the second signature represents the frequency components of a detected audio signal during a time frame, comprising:
-
Storing in computer memory a first data array comprised of all of the first signatures, whereby the n-th row in the first data array is the set of members of the n-th first signature; For at least one column in the first data array, sorting within the computer memory, the elements of the column in either ascending or descending order; Storing in computer memory an additional data array where one element in the second data array corresponds to an element in the one column of the first data array, and the value of the one element in the second data array cross-indexes to where the corresponding element in the first data array originated prior to the sorting step; Applying a search using the second signature to find best match between the second signature and the rows of the first data array; Recovering the identification index and time frame index of any matching first signature by using the cross-index of the second data array and applying it in the matching row. - View Dependent Claims (21)
-
-
22. A method executed by an audio signal processing system of searching a database comprised of at least one first signature representing a first audio signal using a query comprised of a second signature where the first and second signatures are both sets of a predetermined number of elements, each element a number, comprising:
-
For each first signature, applying a predetermined calculation to calculate a first integer as a function of a subset of elements comprising each first signature said elements derived from spectral magnitudes detected in the first audio signal; Storing in a computer memory location corresponding to the value of the first integer a reference to the corresponding first signature used in calculating the first signature; Calculating a second integer using the same predetermined calculation applied to the corresponding subset of the second signature said elements derived from spectral magnitudes detected in a second audio signal; Selecting memory locations corresponding to integer values within a predetermined error function from the second integer; Determining any first signatures and their identification index and time frame index corresponding to the selected memory locations. - View Dependent Claims (23, 24)
-
Specification