System and method for compressed domain beat detection in audio bitstreams

• US 7,050,980 B2
• Filed: 09/28/2001
• Issued: 05/23/2006
• Est. Priority Date: 01/24/2001
• Status: Expired due to Fees

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Wang, Ye, Vilermo, Miikka
• Primary Examiner(s): Young, W. R.
• Assistant Examiner(s): Jackson, Jakieda R
• Application Number:
  US09/966,482
• Publication Number:
  US 20020178012A1
• Time in Patent Office: 1,698 Days
• Field of Search: 704/200.1, 704/204, 704/503, 381/56, 434/262, 382/107, 382/240, 600/437, 323/107
• US Class Current: 704/503
• CPC Class Codes: G10H 1/0058 Transmission between separate instruments or between individual components of a musical system G10H1/0083 takes precedence
• CPC Class Codes: G10H 2240/061 MP3, i.e. MPEG-1 or MPEG-2 Audio Layer III, lossy audio compression
• CPC Class Codes: G10H 2240/185 Error prevention, detection or correction in files or streams for electrophonic musical instruments
• CPC Class Codes: G10H 2240/245 ISDN [Integrated Services Digital Network]
• CPC Class Codes: G10H 2240/251 Mobile telephone transmission, i.e. transmitting, accessing or controlling music data wirelessly via a wireless or mobile telephone receiver, analog or digital, e.g. DECT GSM, UMTS smartphone, PDA or palmtop used for musical purposes G10H2230/015; mobile ringtone G10H2230/021
• CPC Class Codes: G10H 2240/295 Packet switched network, e.g. token ring circuit-switched networks, e.g. traditional analog telephone transmission G10H2240/241
• CPC Class Codes: G10H 2240/305 Internet or TCP/IP protocol use for any electrophonic musical instrument data or musical parameter transmission purposes
• CPC Class Codes: G10L 19/005 Correction of errors induced by the transmission channel, if related to the coding algorithm
• CPC Class Codes: G10L 19/0212 using orthogonal transformation

Abstract

A system and method for detecting beats in a compressed audio domain is disclosed where a beat detector functions as part of an error concealment system in an audio decoding section used in audio information transfer and audio download-streaming system terminal devices such as mobile phones. The beat detector includes a MDCT coefficient extractor, a band feature value analyzer, a confidence score calculator; and a converging and storage unit. The method provides beat detection by means of beat information obtained using both MDCT coefficients as well as window-switching information. A baseline beat position is determined using MDCT coefficients obtained from the audio bitstream which also provides a window-switching pattern. A window-switching beat position is compared with the baseline beat position and, if a predetermined condition is satisfied, the window-switching beat position is validated as a detected beat.

Claims

1. A method for detecting beats in a compression encoded audio bitstream, said method comprising the steps of:

(a) determining a baseline beat position using modified discrete cosine transform (MDCT) coefficients obtained from the audio bitstream;

(b) deriving from the audio bitstream a window-switching pattern for sub-band sampling windows used to generate the MDCT coefficients;

(c) determining a window-switching beat position based on the derived window-switching pattern;

(d) comparing said baseline beat position with said window-switching beat position; and

(e) validating said window-switching beat position as a detected beat if a predetermined condition is satisfied.

2. A method as in claim 1 further comprising the step of determining an inter-beat interval related to said baseline beat position.

3. A method as in claim 2 further comprising the step of storing said window-switching beat position and said inter-beat interval for subsequent retrieval.

4. A method as in claim 1 wherein said step of determining a baseline beat position comprises the step of determining at least one beat candidate and an inter-onset interval.

5. A method as in claim 4 wherein said step of determining a baseline beat position further comprises the step of checking said at least one beat candidate for reliability using a predetermined confidence threshold value.

6. A method as in claim 4 further comprising the step of converging two or more said beat candidates to a single beat candidate.

7. A method as in claim 1 wherein said step of deriving baseline beat information from the audio bitstream comprises the step of deriving an energy value for at least one subband from the compression encoded audio bitstream.

8. A method as in claim 7 wherein said subband comprises a member of the group consisting of a frequency interval from 0 to 459 Hz, a frequency interval from 460 to 918 Hz, a frequency interval from 919 to 1337 Hz, a frequency interval from 1.338 to 3.404 kHz, a frequency interval from 3.405 to 7.462 kHz, and a frequency interval from 7.463 to 22.05 kHz.

9. A method as in claim 7 wherein said step of deriving a beat position comprises the step of identifying a maximum energy value within a search window.

10. A method as in claim 7 wherein said step of deriving an energy value for at least one subband comprises the step of deriving an absolute energy value.

11. A method as in claim 7 wherein said step of deriving an energy value for at least one subband comprises the step of deriving an element-to-mean energy value.

12. A method as in claim 7 wherein said step of deriving an energy value for at least one subband comprises the step of deriving a differential energy value.

13. The method of claim 1, wherein step (a) comprises determining a baseline beat position prior to inverse modified discrete cosine transform (IMDCT) processing of the MDCT coefficients.

14. The method of claim 1, wherein the predetermined condition of step (e) comprises relative displacement of the window-switching and baseline beat positions by less than a predetermined amount.

15. The method of claim 1, wherein step (a) further comprises:

i) obtaining the MDCT coefficients from a portion of the audio bitstream within a search window,

ii) sorting the MDCT coefficients into a plurality of subband divisions,

iii) identifying beat candidates within some or all of the subband divisions,

iv) calculating a confidence score for beat candidates identified in step iii),

v) calculating a converged confidence score from the confidence scores of step iv), and

vi) determining the baseline beat position within the search window based on the converged confidence score.

16. The method of claim 15, wherein step iii) includes identifying a full band beat candidate across all of the subband divisions.

17. The method of claim 16, wherein step iv) includes calculating a confidence score using the following formula:

$R_i=\underset{k=1,2,3}{\max }<br><br>\left[\frac{\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)}{\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)+<br><br>\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)-\frac{\left(I_i-I_{\mathrm{last\_beat}}\right)}{k}<br><br>}\right]*f<br><br>\left(E_i\right),$

wherein

i is equal to F, 1, . . . , N, where 1 through N are indices of subband divisions and F is the index for the full band,

R_i is equal to the confidence score for index i,

{overscore (IOI)} is a vector of intervals between previous beat candidates within the subband divisions,

k is set to 1 unless the current interval between beat candidates within a subband division is two or three times longer than a predicted value because of a missed candidate, and set to 2 or 3 otherwise,

I_i is a granule index of a current beat candidate,

I<sub>last—

beat</sub> is a granule index of a previous beat, and

ƒ

(E_i) equals 0 if the energy (E) of a candidate for index i is less than a threshold, and is 1 if the energy (E) of that candidate is greater than the threshold.

18. The method of claim 17, wherein step v) includes calculating a converged confidence score using the following formula:

R_confidence=max{R_F, R_l, . . . , R_N}.

19. The method of claim 15, wherein the search window size is adaptive.

20. The method of claim 19, wherein the search window is sized according to the formula

$\mathrm{window\_size}$

_new = 2 * floor ⁡

( median ⁡

( IOI _ ) 2 ) + 1 ,

wherein window_size_new is a new size of the search window, and

{overscore (IOI)} is a vector of intervals between previous beat candidates within the subband divisions.

21. The method of claim 15, wherein step iii) comprises identifying a feature value, within a subband division and during the search window, exceeding a threshold.

22. The method of claim 21, wherein identifying a feature value comprises determining whether a primitive band energy E within a subband division exceeds a threshold value, and wherein the primitive band energy E is calculated according to the formula

$E_b$

( n ) = ∑

j = N1 N2 ⁢

⁢

[ X j ⁡

( n ) ] 2 ,

wherein

E_b(n) is the energy of subband b in granule n,

X_j(n) is the j^th normalized MDCT coefficient decoded at granule n,

N1 is a lower bound index of the MDCT coefficients sorted into subband b, and

N2 is an upper bound index of the MDCT coefficients sorted into subband b.

23. The method of claim 21, wherein identifying a feature value further comprises:

(1) determining the energy in a granule,

(2) determining the average energy in the search window,

(3) determining the ratio of the quantity determined in step (1) to the quantity determined in step (2).

24. The method of claim 21, wherein identifying a feature value further comprises computing a differential energy value for subband divisions using the formula E_b(n+1)−

E_b(n), wherein

$E_b<br><br>\left(n\right)=\underset{j=\mathrm{N1}}{\overset{\mathrm{N2}}{\sum <br><br>}}<br><br><br><br>{\left[X_j<br><br>\left(n\right)\right]}^2,$

E_b(n) is the energy of subband b in granule n of the audio bitstream,

X_j(n) is the j^th normalized MDCT coefficient decoded at granule n,

N1 is a lower bound index of the MDCT coefficients sorted into subband b,

N2 is an upper bound index of the MDCT coefficients sorted into subband b,

$E_b<br><br>\left(n+1\right)=\underset{j=\mathrm{N1}}{\overset{\mathrm{N2}}{\sum <br><br>}}<br><br><br><br>{\left[X_j<br><br>\left(n+1\right)\right]}^2,$

E_b(n+1) is the energy of subband b in granule n+1 of the audio bitstream,

X_j(n+1) is the j^th normalized MDCT coefficient decoded at granule n+1,

N1 is a lower bound index of the MDCT coefficients sorted into subband b, and

N2 is an upper bound index of the MDCT coefficients sorted into subband b.

25. The method of claim 1, wherein the audio bitstream is an MP3 encoded audio bitstream, and wherein step (b) comprises determining a pattern of long, long-to-short, short and short-to-long windows in the audio bitstream.

26. A beat detector suitable for placement into an audio device conforming to a compression-encoded audio transmission protocol, said beat detector comprising:

a modified discrete cosine transform coefficient extractor, for obtaining transform coefficients from an audio bitstream;

at least one band feature value analyzer for analyzing a feature value for a related band, the at least one band feature value analyzer receiving input from the modified discrete cosine transform coefficient extractor;

a confidence score calculator receiving input from the at least one band feature value analyzer, the confidence score calculator calculating a confidence score for beat candidates using stored values of previous inter-onset intervals; and

a converging and storage unit for combining two or more of said beat candidates.

27. The beat detector as in claim 26 wherein said feature value comprises a member of the group consisting of an absolute energy value, an element-to-mean energy value, and a differential energy value.

28. The beat detector as in claim 27 further comprising an element-to-mean ratio threshold comparator.

29. An audio encoder suitable for use with a compression-encoded audio transmission protocol, said audio encoder comprising:

a beat detector including

a modified discrete cosine transform coefficient extractor, for obtaining transform coefficients;

at least one band feature value analyzer for analyzing a feature value for a related band;

a confidence score calculator; and

means for including beat detection information as side information in audio transmission.

30. An audio decoder suitable for use with a compression-encoded audio transmission protocol, said audio decoder comprising:

a beat detector for providing beat position information, said beat detector including

a modified discrete cosine transform coefficient extractor, for obtaining transform coefficients;

at least one band feature value analyzer for analyzing a feature value for a related band;

a confidence score calculator; and

error concealment means for concealing packet loss in audio transmission by utilizing said beat position to identify audio data for replacement of packet loss.

31. An audio encoder, comprising:

a beat detector, said beat detector being configured to perform a method for detecting beats in a compression encoded audio bitstream, said method including the steps of

(a) determining a baseline beat position using modified discrete cosine transform (MDCT) coefficients obtained from the audio bitstream,

(b) deriving from the audio bitstream a window-switching pattern for sub-band sampling windows used to generate the MDCT coefficients,

(c) determining a window-switching beat position based on the derived window-switching pattern,

(d) comparing the baseline beat position with the window-switching beat position, and

(e) validating the window-switching beat position as a detected beat if a predetermined condition is satisfied.

32. The audio encoder of claim 31, wherein step (a) comprises determining a baseline beat position prior to inverse modified discrete cosine transform (IMDCT) processing of the MDCT coefficients.

33. The audio encoder of claim 31, wherein the predetermined condition of step (e) comprises relative displacement of the window-switching and baseline beat positions by less than a predetermined amount.

34. The audio encoder of claim 31, wherein step (a) further comprises:

i) obtaining the MDCT coefficients from a portion of the audio bitstream within a search window,

ii) sorting the MDCT coefficients into a plurality of subband divisions,

iii) identifying beat candidates within some or all of the subband divisions,

iv) calculating a confidence score for beat candidates identified in step iii),

v) calculating a converged confidence score from the confidence scores of step iv), and

vi) determining the baseline beat position within the search window based on the converged confidence score.

35. The audio encoder of claim 34, wherein step iii) includes identifying a full band beat candidate across all of the subband divisions.

36. The audio encoder of claim 35, wherein step iv) includes calculating a confidence score using the following formula:

$R_i=\underset{k=1,2,3}{\max }<br><br>\left[\frac{\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)}{\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)+<br><br>\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)-\frac{\left(I_i-I_{\mathrm{last\_beat}}\right)}{k}<br><br>}\right]*f<br><br>\left(E_i\right),$

wherein

i is equal to F, 1, . . . , N, where 1 through N are indices of subband divisions and F is the index for the full band,

R_i is equal to the confidence score for index i,

{overscore (IOI)} is a vector of intervals between previous beat candidates within the subband divisions,

k is set to 1 unless the current interval between beat candidates within a subband division is two or three times longer than a predicted value because of a missed candidate, and set to 2 or 3 otherwise,

I_i is a granule index of a current beat candidate,

I<sub>last—

beat</sub> is a granule index of a previous beat, and

ƒ

(E_i) equals 0 if the energy (E) of a candidate for index i is less than a threshold, and is 1 if the energy (E) of that candidate is greater than the threshold.

37. The audio encoder of claim 36, wherein step v) includes calculating a converged confidence score using the following formula:

R_confidence=max{R_F, R₁, . . . , R_N}.

38. The audio encoder of claim 34, wherein the search window size is adaptive.

39. The audio encoder of claim 38, wherein the search window is sized according to the formula

$\mathrm{window\_size}$

_new = 2 * floor ⁡

( median ⁡

( IOI _ ) 2 ) + 1 ,

wherein

window_size_new is a new size of the search window, and

{overscore (IOI)} is a vector of intervals between previous beat candidates within the subband divisions.

40. The audio encoder of claim 34, wherein step iii) comprises identifying a feature value, within a subband division and during the search window, exceeding a threshold.

41. The audio encoder of claim 40, wherein identifying a feature value comprises determining whether a primitive band energy E within a subband division exceeds a threshold value, and wherein the primitive band energy E is calculated according to the formula

$E_b$

( n ) = ∑

j = N1 N2 ⁢

⁢

[ X j ⁡

( n ) ] 2 ,

wherein

E_b(n) is the energy of subband b in granule n,

X_j(n) is the j^th normalized MDCT coefficient decoded at granule n,

N1 is a lower bound index of the MDCT coefficients sorted into subband b, and

N2 is an upper bound index of the MDCT coefficients sorted into subband b.

42. The audio decoder of claim 40, wherein identifying a feature value further comprises:

(1) determining the energy in a granule,

(2) determining the average energy in the search window,

(3) determining the ratio of the quantity determined in step (1) to the quantity determined in step (2).

43. The audio decoder of claim 40, wherein identifying a feature value further comprises computing a differential energy value for subband divisions using the formula E_b(n+1)−

E_b(n), wherein

$E_b<br><br>\left(n\right)=\underset{j=\mathrm{N1}}{\overset{\mathrm{N2}}{\sum <br><br>}}<br><br><br><br>{\left[X_j<br><br>\left(n\right)\right]}^2,$

E_b(n) is the energy of subband b in granule n of the audio bitstream,

X_j(n) is the j^th normalized MDCT coefficient decoded at granule n,

N1 is a lower bound index of the MDCT coefficients sorted into subband b,

N2 is an upper bound index of the MDCT coefficients sorted into subband b,

$E_b<br><br>\left(n+1\right)=\underset{j=\mathrm{N1}}{\overset{\mathrm{N2}}{\sum <br><br>}}<br><br><br><br>{\left[X_j<br><br>\left(n+1\right)\right]}^2,$

E_b(n+1) is the energy of subband b in granule n+1 of the audio bitstream,

X_j(n+1) is the j^th normalized MDCT coefficient decoded at granule n+1,

N1 is a lower bound index of the MDCT coefficients sorted into subband b, and

N2 is an upper bound index of the MDCT coefficients sorted into subband b.

44. The audio decoder of claim 31, wherein the audio bitstream is an MP3 encoded audio bitstream, and wherein step (b) comprises determining a pattern of long, long-to-short, short and short-to-long windows in the audio bitstream.

45. An audio decoder, comprising:

a beat detector, said beat detector being configured to perform a method for detecting beats in a compression encoded audio bitstream, said method including the steps of

(a) determining a baseline beat position using modified discrete cosine transform (MDCT) coefficients obtained from the audio bitstream,

(b) deriving from the audio bitstream a window-switching pattern for sub-band sampling windows used to generate the MDCT coefficients,

(c) determining a window-switching beat position based on the derived window-switching pattern,

(d) comparing the baseline beat position with the window-switching beat position, and

(e) validating the window-switching beat position as a detected beat if a predetermined condition is satisfied.

46. The audio decoder of claim 45, wherein step (a) comprises determining a baseline beat position prior to inverse modified discrete cosine transform (IMDCT) processing of the MDCT coefficients.

47. The audio decoder of claim 45, wherein the predetermined condition of step (e) comprises relative displacement of the window-switching and baseline beat positions by less than a predetermined amount.

48. The audio decoder of claim 45, wherein step (a) further comprises:

i) obtaining the MDCT coefficients from a portion of the audio bitstream within a search window,

ii) sorting the MDCT coefficients into a plurality of subband divisions,

iii) identifying beat candidates within some or all of the subband divisions,

iv) calculating a confidence score for beat candidates identified in step iii),

v) calculating a converged confidence score from the confidence scores of step iv), and

vi) determining the baseline beat position within the search window based on the converged confidence score.

49. The audio decoder of claim 48, wherein step iii) includes identifying a full band beat candidate across all of the subband divisions.

50. The audio decoder of claim 49, wherein step iv) includes calculating a confidence score using the following formula:

$R_i=\underset{k=1,2,3}{\max }<br><br>\left[\frac{\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)}{\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)+<br><br>\mathrm{median}<br><br>\left(\stackrel{\_}{\mathrm{IOI}}\right)-\frac{\left(I_i-I_{\mathrm{last\_beat}}\right)}{k}<br><br>}\right]*f<br><br>\left(E_i\right),$

wherein

i is equal to F, 1, . . . , N, where 1 through N are indices of subband divisions and F is the index for the full band,

R_i is equal to the confidence score for index i,

{overscore (IOI)} is a vector of intervals between previous beat candidates within the subband divisions,

k is set to 1 unless the current interval between beat candidates within a subband division is two or three times longer than a predicted value because of a missed candidate, and set to 2 or 3 otherwise,

I_i is a granule index of a current beat candidate,

I<sub>last—

bit</sub> is a granule index of a previous beat, and

ƒ

(E_i) equals 0 if the energy (E) of a candidate for index i is less than a threshold, and is 1 if the energy (E) of that candidate is greater than the threshold.

51. The audio decoder of claim 50, wherein step v) includes calculating a converged confidence score using the following formula:

R_confidence=max{R_F, R₁, . . . , R_N}.

52. The audio decoder of claim 48, wherein the search window size is adaptive.

53. The audio decoder of claim 52, wherein the search window is sized according to the formula

$\mathrm{window\_size}$

_new = 2 * floor ⁡

( median ⁡

( IOI _ ) 2 ) + 1 ,

wherein

window_size_new is a new size of the search window, and

{overscore (IOI)} is a vector of intervals between previous beat candidates within the subband divisions.

54. The audio decoder of claim 48, wherein step iii) comprises identifying a feature value, within a subband division and during the search window, exceeding a threshold.

55. The audio decoder of claim 54, wherein identifying a feature value comprises determining whether a primitive band energy E within a subband division exceeds a threshold value, and wherein the primitive band energy E is calculated according to the formula

$E_b$

( n ) = ∑

j = N1 N2 ⁢

⁢

[ X j ⁡

( n ) ] 2 ,

wherein

E_b(n) is the energy of subband b in granule n,

X_j(n) is the j^th normalized MDCT coefficient decoded at granule n,

N1 is a lower bound index of the MDCT coefficients sorted into subband b, and

N2 is an upper bound index of the MDCT coefficients sorted into subband b.

56. The audio decoder of claim 54, wherein identifying a feature value further comprises:

(1) determining the energy in a granule,

(2) determining the average energy in the search window,

(3) determining the ratio of the quantity determined in step (1) to the quantity determined in step (2).

57. The audio decoder of claim 54, wherein identifying a feature value further comprises computing a differential energy value for subband divisions using the formula E_b(n+1)−

E_b(n), wherein

$E_b<br><br>\left(n\right)=\underset{j=\mathrm{N1}}{\overset{\mathrm{N2}}{\sum <br><br>}}<br><br><br><br>{\left[X_j<br><br>\left(n\right)\right]}^2,$

E_b(n) is the energy of subband b in granule n of the audio bitstream,

X_j(n) is the j^th normalized MDCT coefficient decoded at granule n,

N1 is a lower bound index of the MDCT coefficients sorted into subband b,

N2 is an upper bound index of the MDCT coefficients sorted into subband b,

$E_b<br><br>\left(n+1\right)=\underset{j=\mathrm{N1}}{\overset{\mathrm{N2}}{\sum <br><br>}}<br><br><br><br>{\left[X_j<br><br>\left(n+1\right)\right]}^2,$

E_b(n+1) is the energy of subband b in granule n+1 of the audio bitstream,

X_j(n+1) is the j^th normalized MDCT coefficient decoded at granule n+1,

N1 is a lower bound index of the MDCT coefficients sorted into subband b, and

N2 is an upper bound index of the MDCT coefficients sorted into subband b.

58. The audio decoder of claim 45, wherein the audio bitstream is an MP3 encoded audio bitstream, and wherein step (b) comprises determining a pattern of long, long-to-short, short and short-to-long windows in the audio bitstream.