Broadcast information classification system and method

• US 4,843,562 A
• Filed: 06/24/1987
• Issued: 06/27/1989
• Est. Priority Date: 06/24/1987
• Status: Expired due to Term

• Current Assignee: Broadcast Data Systems Limited Partnership
• Original Assignee: Broadcast Data Systems Limited Partnership
• Inventors: Sebastian, Richard L., Simkins, Laura J., Kenyon, Stephen C.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Teska, Kevin J.
• Application Number:
  US07/066,106
• Time in Patent Office: 734 Days
• Field of Search: 358/84, 381/42, 381/43, 364/604, 364/728, 364/487, 364/513.5, 382/34, 455/2
• US Class Current: 702/73
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G10L 15/00 Speech recognition G10L17/00 takes precedence
• CPC Class Codes: H04H 20/14 for monitoring programmes
• CPC Class Codes: H04H 60/44 for identifying broadcast stations
• 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

Method and apparatus for classifying broadcast information first receives the broadcast information and processes it to provide a plurality of a low bandwidth analyzed waveforms. The analyzed waveforms are used to generate a spectragram which is then compared with a plurality of reference spectragrams stored in a first stage reference library. The first stage reference spectragrams are then queued in order of their similarity to the generated spectragram. Next, a plurality of second stage reference patterns, which correspond to the first stage reference spectragrams, are correlated with one of the analyzed waveforms in the queueing order established previously. A correlation value is provided for each second stage reference pattern stored in the second stage reference library. When it is determined that a correlation value exceeds the threshold value, a recognition is declared and the broadcast information is classified as similar to the second stage reference pattern whose correlation value exceeds the threshold. The analyzed waveform used in the second stage classification may be time warped to account for speed fluctuations in the broadcast information.

Claims

1. A method of classifying broadcast information, comprising the steps of:

receiving broadcast information;

performing a spectral analysis of said information and providing a plurality of analyzed waveforms corresponding thereto;

generating a spectragram from said waveforms;

comparing the generated spectragram with a plurality of predetermined first stage reference spectragrams;

queueing the first stage reference spectragrams in order of their similarity to said generated spectragram;

correlating at least one of a plurality of predetermined second stage reference patterns which correspond to said first stage reference spectragrams with one of said analyzed waveforms in the queueing order established in the queueing step to provide a correlation value for each of the correlated second stage reference patterns;

monitoring said correlating step to determine when one of said correlation values exceeds a threshold correlation value;

identifying the second stage reference pattern which corresponds to the correlation value which exceeds said threshold value; and

classifying the broadcast information as similar to the identified second stage reference pattern.

2. A method according to claim 1 wherein said queueing step includes the step of restricting the queue to only those first stage reference spectragrams which are less than a similarity threshold with respect to said generated spectragram.

3. A method according to claim 1 wherein the step of generating said spectragram includes the steps of:

computing a plurality of linear combinations of said analyzed waveforms;

forming said linear combinations into a multi-channel feature sequence;

smoothing said feature sequence with a moving average filter;

resampling the smoothed feature sequence to provide a low bandwidth feature set; and

forming said feature set into a generated time/frequency spectragram having a matrix of elements.

4. A method according to claim 3 wherein each of said first stage reference spectragrams has a time/frequency matrix of elements, and wherein said step of comparing the generated and reference spectragrams includes the steps of:

(a) calculating a difference between each element of said generated spectragram and a corresponding element of one of said reference spectragrams;

(b) summing the differences between said generated spectragram elements and said one reference spectragram elements;

(c) calculating a distance between said generated spectragram and said one reference spectragram based on the difference sum; and

(d) repeating said steps (a)-(c) for each of said plurality of first stage reference spectragrams.

5. A method according to claim 4 wherein said step of comparing the generated and reference spectragrams includes the further step of:

(e) comparing each of the calculated distances with a threshold distance value, and wherein said queueing step includes the step of queueing only those first stage reference patterns whose corresponding distances fall below said threshold distance value.

6. A method according to claim 1 wherein said step of receiving broadcast information includes the step of simultaneously receiving a plurality of said broadcast information from a corresponding plurality of broadcast sources, and wherein said steps of performing, generating, comparing, queueing, correlating, monitoring, identifying, and classifying are performed on said plurality of broadcast information.

7. A method according to claim 1 wherein said step of performing said spectral analysis includes the steps of:

providing said broadcast information to a plurality of channels;

bandpass filtering, in each channel, said broadcast information to provide a filtered signal in each channel;

rectifying, in each channel, said filtered signal to provide a rectified signal in each channel; and

providing the plurality of rectified, filtered signals to said generating step.

8. A method according to claim 7 wherein said step of bandpass filtering includes the step of providing a different value bandpass filter in each of said channels.

9. A method according to claim 1 wherein said step of correlating includes the steps of:

receiving one of said analyzed waveforms from said performing step;

time warping said one analyzed waveform to provide at least one time warped waveform;

cross correlating said time warped waveform and said at least one second stage reference pattern to provide a plurality of correlation values; and

selecting a maximum correlation value from among said plurality of correlation values.

10. A method according to claim 9 wherein said time warping step includes the step of providing at least one stretched time warped waveform, and wherein said cross correlating step includes the step of independently cross correlating both said stretched waveform and said analyzed waveform with said second stage reference pattern to provide a plurality of correlation values for each of said analyzed waveform and said stretched waveform.

11. A method according to claim 10 wherein said time warping step includes the step of providing at least one compressed time warped waveform, and wherein said cross correlating step includes the step of independently cross correlating said second stage reference pattern with said compressed waveform, said stretched waveform, and said analyzed waveform.

12. A method according to claim 1 further including the training steps of:

receiving a plurality of reference broadcast information;

analyzing each reference broadcast information to determine a most spectrally distinctive section thereof;

generating a first stage reference spectragram for each of said plurality of reference broadcast information from the most distinctive section thereof; and

generating a second stage reference pattern for each of said plurality of reference broadcast information from the most distinctive section thereof.

13. A method according to claim 1 further including the step of normalizing the generated spectragram prior to said comparing step.

14. A method of classifying broadcast information, comprising the steps of:

receiving broadcast information;

comparing said information with a library of first stage reference patterns;

queueing the first stage reference patterns in an order of their similarity to said information;

correlating the broadcast information with a library of second stage reference patterns, which correspond to said first stage reference patterns, in the queueing order established in the queueing step; and

classifying said broadcast information as similar to one of said second stage reference patterns based on said correlating step.

15. A method according to claim 14 further including the steps of:

generating a plurality of analyzed waveforms from said broadcast information;

time warping one of said analyzed waveforms to provide at least one time warped waveform; and

wherein said correlating step includes the step of correlating both said one analyzed waveform and said time warped waveform with said library of second stage reference patterns.

16. A method according to claim 15 wherein said time warping step includes the step of linearly time warping said one analyzed waveform to provide a stretched waveform.

17. A method according to claim 14 wherein said receiving step includes the step of simultaneously receiving a plurality of broadcast information, and wherein said steps of comparing, queueing, correlating, and classifying are performed on said plurality of broadcast information, substantially simultaneously.

18. A method according to claim 14 further including the steps of:

processing said broadcast information to provide a plurality N of analyzed signal patterns corresponding to said broadcast information;

generating a spectragram from said analyzed signal patterns;

providing said spectragram to said comparing step for comparison to said first stage reference patterns; and

providing one of said analyzed signal patterns to said correlating step for correlation with said second stage reference patterns.

19. A method according to claim 18 wherein said step of processing includes the steps of:

bandpass filtering said broadcast information into a plurality of bands; and

computing a plurality of linear combinations of said plurality of bands to provide said plurality of analyzed signal patterns.

20. A method according to claim 19 wherein said step of bandpass filtering includes the steps of bandpass filtering, rectifying, and then lowpass filtering each said band.

21. A method according to claim 18 wherein said step of generating a spectragram includes the steps of:

sampling said plurality of analyzed signal patterns at a predetermined rate;

constructing a time/frequency matrix having N frequency channels, n time channels, and a plurality of N(n) of matrix elements;

calculating, for each matrix element, a matrix value X_N,n as follows;

space="preserve" listing-type="equation">X.sub.N,n (t)=[K.sub.l ×

V.sub.An (t)]+. . . [K.sub.N ×

V.sub.Nn (t)]

where;

t equals time at which samples are taken from said plurality of analyzed signal patterns;

V_An through V_Nn are amplitude values of first through N^th analyzed signal patterns taken at sample time t; and

K_l through K_N are constants preselected to minimize the influence of broadband impulsive energy.

22. A method according to claim 21 further including the step of normalizing said matrix to provide said spectragram.

23. A method according to claim 21 wherein each said first stage reference pattern comprises an Nxn reference matrix of elements, and wherein said step of comparing comprises the steps of:

measuring a variation between each element of the time/frequency matrix and a corresponding element of each of said reference matrices;

summing the measured variations between the time/frequency matrix and each reference matrix to provide a distance measurement for each reference matrix;

comparing each distance measurement with a threshold value; and

eliminating those first stage reference patterns whose corresponding distance measurement exceeds said threshold value.

24. A method according to claim 23 wherein said queueing step comprises the step of ordering non-eliminated first stage reference patterns according to their corresponding distance measurements.

25. A method according to claim 14 wherein said correlating step includes the steps of:

calculating a correlation value for at least one second stage reference pattern with reference to said broadcast information; and

comparing said correlation value with a threshold correlation value; and

wherein said classifying step includes the step of classifying said broadcast information as similar to only the second stage reference pattern whose corresponding correlation value exceeds said threshold reference value.

26. A method according to claim 14 further including the training steps of:

(a) analyzing reference broadcast information to identify a spectrally distinctive portion thereof;

(b) determining a figure of merit for said distinctive portion using a peak value and a standard deviation value from said distinctive portion;

(c) generating a first stage reference pattern from said distinctive portion;

(d) testing the generated first stage reference pattern for time alignment sensitivity;

(e) repeating said steps (a)-(d) when the generated first stage reference pattern does not pass the time sensitivity test; and

(f) using said spectrally distinctive portion to provide first and second stage reference patterns when said generated first stage reference pattern passe the time sensitivity test.

27. A method of classifying broadcast information, comprising the steps of:

comparing a portion of received broadcast information with a library of first stage reference patterns;

queueing said first stage reference patterns in an order of their similarity to said broadcast information portion;

correlating said portion with a library of second stage reference patterns in the queueing order established in said queueing step, said second stage reference patterns corresponding to said first stage reference patterns; and

classifying said broadcast information as similar to one of said second stage reference patterns based on said correlating step.

28. A method according to claim 27 further including the steps of:

receiving said broadcast information;

processing said broadcast to provide a plurality of spectrally distinguishable waveforms;

processing said waveforms to provide processed spectral information corresponding to said waveforms;

and wherein said comparing step compares said processed spectral information with said first stage reference patterns.

29. A method according to claim 28 wherein said step of processing said waveforms includes the step of processing said waveforms to provide a spectragram matrix having N(n) elements, and wherein each of said first stage reference patterns includes a reference matrix having N(n) elements;

measuring a distance value between each element of said reference matrix and a corresponding element of said spectragram matrix; and

summing distance values for all of said spectragram and reference matrix elements to provide a difference measurement for each reference matrix with respect to said spectragram matrix.

30. A method according to claim 29 wherein said queueing step comprises the steps of:

disregarding those reference matrices whose corresponding difference measurements exceed a predetermined threshold; and

queueing non-disregarded reference matrices according to their respective difference measurements.

31. A method according to claim 27 wherein said comparing step includes the steps of:

receiving said broadcast information;

processing said broadcast information to provide a plurality of waveforms; and

processing said waveforms to provide a plurality of feature sequences which are linear combinations of said waveforms;

and wherein said correlating step includes the steps of;

cross-correlating one of said feature sequences with said second stage reference patterns until a cross correlation value corresponding to one of said second stage reference patterns exceeds a predetermined threshold.

32. A method according to claim 31 further including the step of:

to provide a time-expanded feature sequence and a time-compressed feature sequence;

and wherein said cross-correlating step includes the step of cross-correlating said second stage reference pattern with at least one of said time-expanded feature sequence, said time-compressed feature sequence, and said one feature sequence.

33. A method according to claim 27 further including the training steps of:

providing a plurality of reference information;

analyzing each of said reference information to identify a spectrally distinctive portion thereof;

generating a first stage reference pattern from said distinctive portion;

testing the generated first stage reference pattern for time alignment sensitivity; and

generating a second stage reference pattern from said distinctive portion when the generated first stage reference pattern passes the time alignment sensitivity test.

34. Apparatus for classifying broadcast information, comprising:

means for receiving broadcast information;

means for performing a spectral analysis of said information and providing a plurality of analyzed waveforms corresponding thereto;

processing means for (a) generating a spectragram from said waveforms;

(b) comparing the generated spectragram with a plurality of predetermined first stage reference spectragrams;

(c) queueing the first stage reference spectragrams in order of their similarity to said generated spectragram;

(d) correlating at least one of a plurality of predetermined second stage reference patterns which correspond to said first stage reference spectragrams with one of said analyzed waveforms in the queueing order established to provide a correlation value for each of the correlated second stage reference patterns;

(e) monitoring the correlation to determine when one of said correlation values exceeds a threshold correlation value;

(f) identifying the second stage reference pattern which corresponds to the correlation value which exceeds said threshold value; and

(g) classifying the broadcast information as similar to the identified second stage reference pattern.

35. Apparatus according to claim 34 wherein said processing means restricts the queue to only those first stage reference spectragrams which are less than a similarity threshold with respect to said generated spectragram.

36. Apparatus according to claim 34 wherein said processing means (a1) computes a plurality of linear combinations of said analyzed waveforms;

(a2) forms said linear combinations into a multi-channel feature sequence;

(a3) smooths said feature sequence with a moving average filter;

resamples the smoothed feature sequence to provide a low bandwidth feature set; and

(a5) forms said feature set into a generated time/frequency spectragram having a matrix of elements.

37. Apparatus according to claim 36 wherein each of said first stage reference spectragrams has a time/frequency matrix of elements, and wherein said processing means (b1) calculates a difference between each element of said generated spectragram and a corresponding element of one of said reference spectragrams;

(b2) sums the differences between said generated spectragram elements and said one reference spectragram elements;

(b3) calculates a distance between said generated spectragram and said one reference spectragrm based on the difference sum; and

(b4) repeats the functions (b1)-(b4) for each of said plurality of first stage reference spectragrams.

38. Apparatus according to claim 37 wherein said processing means (b5) compares each of the calculated distances with a threshold distance value, and wherein said processing means queues only those first stage reference patterns whose corresponding distances fall below said threshold distance value.

39. Apparatus according to claim 34 wherein said means for receiving broadcast information simultaneously receives a plurality of said broadcast information from a corresponding plurality of broadcast sources, and wherein said means for performing and said processing means for (a) generating, (b) comparing, (c) queueing, (d) correlating, (e) monitoring, (f) identifying, and (g) classifying carries out these functions on said plurality of broadcast information.

40. Apparatus according to claim 34 wherein said means for performing said spectral analysis includes:

means for providing said broadcast information to a plurality of channels;

means for bandpass filtering, in each channel, said broadcast information to provide a filtered signal in each channel;

means for rectifying, in each channel, said filtered signal to provide a rectified signal in each channel; and

means for providing the plurality of rectified, filtered signals to said processing means.

41. Apparatus according to claim 40 wherein said means for bandpass filtering includes a different value bandpass filter in each of said channels.

42. Apparatus according to claim 34 wherein said processing means (d1) receives one of said analyzed waveforms from said means for performing;

(d2) time warps said one analyzed waveform to provide at least one time warped waveform;

(d3) cross correlates said time warped waveform with said at least one second stage reference pattern to provide a plurality of correlation values; and

(d4) selects a maximum correlation value from among said plurality of correlation values.

43. Apparatus according to claim 42 wherein said processing means provides at least one stretched time warped waveform, and wherein said processing means independently cross correlates both said stretched waveform and said analyzed waveform with said second stage reference pattern to provide a plurality of correlation values for each of said analyzed waveform and said stretched waveform.

44. Apparatus according to claim 43 wherein said processing means provides at least one compressed time warped waveform, and wherein said processing means independently cross correlates said second stage reference pattern with said compressed waveform, said stretched waveform, and said analyzed waveform.

45. A method according to claim 34 wherein said processing means (t1) receives a plurality of reference broadcast information;

(t2) analyzes each reference broadcast information to determine a most spectrally distinctive section thereof;

(t3) generates a first stage reference spectragram for each of said plurality of reference broadcast information from the most distinctive section thereof; and

(t4) generates a second stage reference pattern for each of said plurality of reference broadcast information from the most distinctive section thereof.

46. Apparatus according to claim 34 wherein said processing means normalizes the generated spectragram prior to said comparison.

47. Apparatus for classifying broadcast information, comprising:

means for receiving broadcast information;

processing means for (a) comparing said information with a library of first stage reference patterns;

(b) queueing the first stage reference patterns in an order of their similarity to said information;

(c) correlating the broadcast information with a library of second stage reference patterns, which correspond to said first stage reference patterns, in the queueing order established; and

(d) classifying said broadcast information as similar to one of said second stage reference patterns based on said correlation.

48. Apparatus according to claim 47 further including means for generating a plurality of analyzed waveforms from said broadcast information;

and wherein said processing means (a1) time warps one of said analyzed waveforms to provide at least one time warped waveform; and

wherein said processing means correlates both said one analyzed waveform and said time warped waveform with said library of second stage reference patterns.

49. Apparatus according to claim 48 wherein said processing means linearly time warp said one analyzed waveform to provide a stretched waveform.

50. Apparatus according to claim 47 wherein said means for receiving includes means for simultaneously receiving a plurality of broadcast information, and wherein said processing means performs the processing functions (a)-(d) on said plurality of broadcast information, substantially simultaneously.

51. Apparatus according to claim 47, wherein said processing means (a1) processes said broadcast information to provide a plurality N of analyzed signal patterns corresponding to said broadcast information;

(a2) generates a spectragram from said analyzed signal patterns;

(a3) provides said spectragram for comparison to said first stage reference patterns; and

(a4) provides one of said analyzed signal patterns for correlation with said second stage reference patterns.

52. Apparatus according to claim 51 wherein said processing means (a1a) bandpass filters said broadcast information into a plurality of bands;

and (a1b) computes a plurality of linear combinations of said plurality of bands to provide said plurality of analyzed signal patterns.

53. Apparatus according to claim 52 wherein said processing means rectifies, and then lowpass filters each said band.

54. A method according to claim 51 wherein said processing means (a2a) samples said plurality of analyzed signal patterns at a predetermined rate;

(a2b) constructs a time/frequency matrix having N frequency channels, n time channels, and a plurality of N(n) of matrix elements; and

(a2c) calculates, for each matrix element, a matrix value X_N,n as follows;

space="preserve" listing-type="equation">X.sub.N,n (t)=[K.sub.l ×

V.sub.An (t)]+. . . [K.sub.N ×

V.sub.Nn (t)]

where;

t equals time at which samples are taken from said plurality of analyzed signal patterns;

V_An through V_Nn are amplitude values of first through N^th analyzed signal patterns;

taken at sample time t; and

K_l through K_N are constants preselected to minimize the influence of broadband impulsive energy.

55. A method according to claim 54 wherein said processing means normalizes said matrix to provide said spectragram.

56. Apparatus according to claim 54 wherein each first stage reference pattern comprises an Nxn reference matrix of elements, and wherein said processing means (a5) measures a variation between each element of the time/frequency matrix and a corresponding element of each of said reference matrices;

(a6) sums the measured variations between the time/frequency matrix and each reference matrix to provide a distance measurement of each reference matrix;

(a7) compares each distance measurement with a threshold value; and

(a8) eliminates those first stage reference patterns whose corresponding distance measurement exceeds said threshold value.

57. Apparatus according to claim 56 wherein said processing means queues non-eliminated first stage reference patterns according to their corresponding distance measurements.

58. Apparatus according to claim 47 wherein said processing means (c1) calculates a correlation value for at least one second stage reference pattern with reference to said broadcast information;

and (c2) compares said correlation value with a threshold correlation value; and

wherein said processing means classifies said broadcast information as similar to only the second stage reference pattern whose corresponding correlation value exceeds said threshold reference value.

59. Apparatus according to claim 47 wherein said processing means analyzes said broadcast information to identify a spectrally distinctive portion thereof;

(f) determines a figure of merit for said distinctive portion using a peak value and a peak value standard deviation from said distinctive portion;

(g) generates a first stage reference pattern from said distinctive portion;

(h) tests the generated first stage reference pattern for time alignment sensitivity;

(i) repeats the functions (e)-(h) when the generated first stage reference pattern does not pass the time sensitivity test; and

uses said spectrally distinctive portion to provide first and second stage reference patterns when said generated first stage reference pattern passes the time sensitivity test.

60. Apparatus for classifying broadcast information, comprising:

means for receiving said broadcast information; and

processing means for (a) comparing a portion of the received broadcast information with a library of first stage reference patterns;

(b) queueing said first stage reference patterns in an order of their similarity to said broadcast information portion;

(c) correlating said portion with a library of second stage reference patterns in the queueing order established in said queueing step, said second stage reference patterns corresponding to said first stage reference patterns; and

(d) classifying said broadcast information as similar to one of said second stage reference patterns based on said correlating step.

61. Apparatus according to claim 60 further including

means for receiving said broadcast information;

means for processing said broadcast to provide a plurality of spectrally distinguishable waveforms;

and wherein said processing means (i) processes said waveforms to provide processed spectral information corresponding to said waveforms; and

(ii) compares said processed spectral information with said first stage reference patterns.

62. Apparatus according to claim 61 wherein said processing means (ia) processes said waveforms to provide a spectragram matrix having Nxn elements, wherein each of said first stage reference patterns includes a reference matrix having Nxn elements, (iia) measures a distance value between each element of said reference matrix and a corresponding element of said spectragram matrix, and (iib) sums distance values for all of said spectragram and reference matrix elements to provide a difference measurement for each reference matrix with respect to said spectragram matrix.

63. Apparatus according to claim 62 wherein said processing means (b1) disregards those reference matrices whose corresponding difference measurements exceed a predetermined threshold, and (b2) queues non-disregarded reference matrices according to their respective difference measurements.

64. Apparatus according to claim 60 wherein said processing means (a1) processes said broadcast information to provide a plurality of waveforms, and (a2) processes said waveforms to provide a plurality of feature sequences which are linear combinations of said waveforms;

and wherein said processing means (c1) cross-correlates one of said feature sequences with said second stage reference patterns until a cross correlation value corresponding to one of said second stage reference patterns exceeds a predetermined threshold.

65. Apparatus according to claim 64 wherein said processing means (ci) time warps said one feature sequence to provide a time-expanded feature sequence and a time-compressed feature sequence, and wherein said processing means (c2) cross-correlates said second stage reference pattern with at least one of said time-expanded feature sequence, said time-compressed feature sequence, and said one feature sequence.

66. Apparatus according to claim 60 wherein said processing means (t1) provides a plurality of reference information, (t2) analyzes each of said reference information to identify a spectrally distinctive portion thereof, (t3) generates a first stage reference pattern from said distinctive portion;

(t4) tests the generated first stage reference pattern for time alignment sensitivity; and

(t5) generates a second stage reference pattern from said distinctive portion when the generated first stage reference pattern passes the time alignment sensitivity test.