Method and apparatus for automatic detection and identification of broadcast audio and video signals

• US 20070168409A1
• Filed: 02/16/2005
• Published: 07/19/2007
• Est. Priority Date: 02/26/2004
• Status: Active Grant

• Current Assignee: Mobile Research Labs, Ltd.
• Original Assignee: Mobile Research Labs, Ltd.
• Inventors: Cheung, Kwan
• Granted Patent: US 8,468,183 B2
• Time in Patent Office: Days
• US Class Current: 708/400
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G10L 25/00 Speech or voice analysis techniques not restricted to a single one of groups G10L15/00 - G10L21/00 muting semiconductor-based amplifiers when some special characteristics of a signal are sensed by a speech detector, e.g. sensing when no signal is present, H03G3/34
• CPC Class Codes: H04H 60/37 for identifying segments of broadcast information, e.g. scenes or extracting programme ID
• CPC Class Codes: H04H 60/56 Arrangements characterised by components specially adapted for monitoring, identification or recognition covered by groups H04H60/29-H04H60/54
• CPC Class Codes: H04H 60/58 of audio determination or detection of speech characteristics in general G10L25/00; speech recognition in general G10L15/00
• CPC Class Codes: H04H 60/59 of video recognising characters or patterns in general G06F18/00, G06V20/00

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.

Claims

1. A method executed by a digital signal processing system of generating a signature associated with a lnown signal, the signature comprised of a set of numeric values of at least one element and corresponding to at least one time frame of the signal, such lnown signal being identified by an identification index and such time frame being identified by a time frame index, comprising:

Calculating for at least one time frame of the signal a pre-determined number of spectral magnitude values grouped in at least one frequency band of pre-determined width;

Calculating for each frequency band a numeric value that is equal to a pre-determined function of one or more of the calculated spectral magntude values grouped within the frequency band;

Storing the calculated numeric values in a computer database with a reference to their corresponding time frame index and their corresponding identification index.

2. The merhod according to claim 1 where the pre-determined function is comprised of either:

(i) a linear combination, (ii) a quadratic function, (iii) a centroid, (iv) a variance, or (v) an n-th order moment, where n is a pre-determined number.

3. The method according to claim 2 further comprising dividing the function result by the pre-determined number of spectral magnitude values in the corresponding frequency band.

4. The method according to claim 1 where the function is a linear combination where the coefficient of each term of the linear combination is substantially equal to the ordinal index of the spectral magnitude value within the frequency band divided by a predetermined constant.

5. The method according to claim 1 where the number of predetermined frequency bands is between 10 and 100.

6. The method according to claim 1 where the frequency bands occupy a range of above approximately 0 Hz and approximately equal to or below 4000 Hz.

7. The method according to claim 4 where the predetermined constant is substantially equal to the sum of the spectral magnitude values in the cotterpondeng frequency band.

9. The method according to claim 1 where the width of a frequency band is set to be substantially larger than the magnitude of the frequency shift that results fron a predetermined maximum amount of variation in the playback speed of the known signal, such shift being measured at one or both of the upper or lower boundary of the frequency band.

10. The method of claim 9, where the upper boundary of the frequency band is substantially equal to lower boundary plus a value equal to the absolute value of the maximum relative playback speed variation, times the lower boundary, times a constant, where the constant ranges between approximately 1 and 100.

11. The method of claim 10, where the constant os between approximately 10 and 50.

12. The method according to claim 9, where for each frequency band, the upper boundary of the frequency band is substantially equal to the value of the lower boundary of the frequency band times the sum of one plus a pre-determined value.

13. The method according to claim 10 where the pre-determined value is between the values of approximately 0 and approximately 10.

15. The method of claim 14 where the first signature and second signature is calculated and stored using one of the methods of claim 1, claim 2, claim 5, claim 7, claim 9, claim 11.

32. The method of claim 2 where the error function is one of;

(i) a determination whether the two integer values are within a threshold distance apart;

(ii) a selection of first integer that is the minimum destance to the second interger relative to all other first integers.

35. A machine comprising a central processing unit, a digital data transceiver device and a data storage device comprised of any machine readable media, where the machine readable media contains a computer program that when executed by the machine, performs any one of the methods of claims 1-14 or 16-34.

36. A machine readable media of anu type, which contains data that is a computer program that when executed by a computer, performs any one of the methods of claims 1-14 or 16-34.

8. The method according to clain 7 further comprising dividing the function result by the pre-determined number of spectral magnitude values in the corresponding frequency band.

14. A method executed by a signal processing system for determining whether a portion of a detecting 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 signals, each portion of the plurality of known signals comprised of plurality of sequential time frame duration and each time frame of the known 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 signals a first signature comprised of a set of numbers derived from a pre-determined number of apectral 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 signature meet a predetermined matching criteria, where such selection occurs as a result of the arrival of a new time frame in the detected signal.

16. The method of claim 14 where the predetermined matching criteria comprises:

Calculating a set of absolute values of the differences between each ordinal member of the set of numbers comprising the first signature and each such member'"'"'s corresponding ordinal member of the set of numbers comprising the second signature;

Calculating a sum of the absolute values; and

Determining whether the sum produces a value less than a pre-determined value.

17. The mathod of claim 14 where the predetermined matching criteria comprises:

Calculating a set of absolute values of the difference between each ordinal member of the set of numbers comprising the first signature and each such member'"'"'s corresponding ordinal member of the set of numbers comprising the second signature;

Calculating a sum of the set of absolute values;

Determining whether the sum is the minimum sum for all the first signatures tested.

18. The method of claim 14 where the predetermined matching criteria comprises:

Calculating an error value using one of the group;

(i) the approximate vector distance from the first signature to the second signature;

(ii) the approximate L-1 norm between the first signature and the second signature;

(iii) the approximate maximum difference between any member in the first signature and its corresponding ordinal member in the second signature;

(iv) the approximate minimum difference between any member in the first signature and its corresponding ordinal member in the second signature;

(v) the approximate average difference between all of the members in the first signature and their corresponding members in the second signature.

19. The method of claim 14 further comprising the steps:

Determining whether the number of first signatures that meet the predetermined matching criteria and have the same identification index is equal to or greater than a number between and including K+1 and 2K+1, where K is evaluated such that 2K+1 is substantially equal to the predetermined number of time frames.

20. The method of claim 14 where the matching criteria comprises:

Determining whether the values of the time frame indices corresponging to matching first signatures with the same identification index increase substantially monotonically in relation to the values of the time frame indices of the matching time frames of the detected signal.

21. The method of claim 14 where the matching criteria comprises:

Determining whether the values of the time frame indices corresponding to matching first signatures with the same identification index are substantially linearly correlated with the values of the time frame indices of the matching time frames of the detected signal.

22. The method of claim 14 where the matching criteria comprises:

Calculating an approximate regression analysis between the values of the time frame indices corresponding to matching first signatures with the same identification index and the values of the time frame indices of the matching time frames of the detected signal.

25. The method of claim 14 where the time frame indices of the detected signal and a matching known signal are periodically tracked to confirm that in a sequence of at least two time frames the time frame indices of the detected signal increase approximately in correspondence with the increase in the time frame indices of the matching known signal.

33. The methos of claim 14 where the signal is comprised of programming of unknown identity that has not been found to match any portion of any known signal further comprised of time frames with corresponding signatures comprising;

Creating an arbitrary identifier with an identification index;

Assiging the identification index to those signatures derived from the signal;

Replacing the arbitrary identifier with a correct identification when the unknown signal is identified.

34. The method of claim 33 further comprising replacing the arbitrary identification index in the database with a pre-existing identification index that references valid identification data identifying the signal.

23. The method of claim 23 where the determination is comprised of a test whether the linear slope is within a range from and including approximately 2 to and including approximately 6.

26. A method executed by a signal processing system for determining whether a portion of a detected 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 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 tome 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 comprise 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 together with the second signature meet a predetermined matching criteria;

Storing in at least one data structure and the time frame index and the identification index corresponding to the matching first signatures;

Deleting from the data structures those time frame indices and corresponding identification indices where fewer than approcimately 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 portin 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 indicies of the detected signal.

27. A method executed by a signal processing system of searching a database comprised of a set of at least n first signatures with corresponding identification indices and time frame indices, where each first signature represents the frequency components of a known signal during the time frame the search looking for all first signatures that together with a second signature meets a pre-determined matching criteria, where the second signature represents the frequency components of a detected signal during a time frame, comprising:

Storing in computer memory a first dats 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 arrat 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.

28. The method of claim 27 where, the search algorithm is one of binary search, B Tree. linear search, heuristic tree searching depth first search breadth first search.

29. A method executed by a signal processing system of searching a database comprised of at least one first signature representing a 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;

Storing in a computer memory locaton corresponding to the value of the first interger a reference to the corresponding first signature used in calculating the first signature;

Calculating a second interger using the same predetermined calculation applied to the corresponding subset of the second signature;

Selecting memory locations corresponding to integer values within a predetermined error function from the second interger;

Determining any first signatures and their identification index and time frame index corresponding to the selected memory locations.

30. The method of claim 29 where the predetermined calculation is a linear combination of at least two elements of the signature.

31. The method of claim 29 where the subset has less than five elements of the first signatures.