Method and apparatus for echo data hiding in audio signals

• US 5,893,067 A
• Filed: 05/31/1996
• Issued: 04/06/1999
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Bender, Walter, Gruhl, Daniel, Morimoto, Norishige
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/656,378
• Time in Patent Office: 1,040 Days
• Field of Search: 704/501, 704/500, 704/502, 704/229, 381/63, 381/62, 381/61
• US Class Current: 704/502
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: H04B 1/665 using psychoacoustic properties of the ear, e.g. masking effect
• CPC Class Codes: H04K 1/00 Secret communication

Abstract

A method of hiding information in a host audio signal introduces one or more echoes into the signal. The separation in time between the host signal and an echo is associated with the value of a datum embedded in the signal. The identity of the embedded datum is determined by observing the delay between the host signal and the echo.

Claims

1. A method of embedding a data value in a host audio signal, the method comprising the steps of:

a. defining an offset value associated with the data value;

b. defining a first echo amplitude associated with the data value; and

c. creating an encoded signal comprising the host audio signal and a first repetition of at least a portion of the host audio signal, the repetition having the first echo amplitude, and, in the encoded signal, being separated in time from the host audio signal by the offset value.

2. The method of claim 1 wherein the encoded signal comprises an additional repetition, having an additional echo amplitude, and being separated in time from the first repetition by the offset value.

3. The method of claim 1 wherein the encoded signal comprises a plurality of additional repetitions, each having a respective additional echo amplitude, and being separated in time from the first repetition by an integral multiple of the offset value.

4. The method of claim 3 wherein one of the additional repetitions has an additional echo amplitude equal to the product of the first echo amplitude and a decay rate, each other of the additional repetitions having a respective additional echo amplitude equal to the product of the first echo amplitude and an integral power of the decay rate.

5. The method of claim 4 wherein the decay rate equals the first echo amplitude.

6. The method of claim 4 wherein the first echo amplitude is less than 0.85.

7. The method of claim 4 wherein the first echo amplitude is less than 0.6.

8. The method of claim 4 wherein the first echo amplitude is between 0.4 and 0.8.

9. The method of claim 1 wherein the absolute value of the offset value is less than 1.5 milliseconds.

10. The method of claim 1 wherein the absolute value of the offset value is less than 1 millisecond.

11. The method of claim 1 wherein the absolute value of the offset value is between 0.5 and 1 millisecond.

12. The method of claim 1 wherein the offset value is positive.

13. The method of claim 1 wherein the offset value is negative.

14. The method of claim 1 wherein the encoded signal is for transmission by telephone.

15. The method of claim 1 wherein the encoded signal is for broadcast by radio.

16. The method of claim 1 wherein the encoded signal is part of an audiovisual medium.

17. A method of embedding information in a host audio signal, the method comprising the steps of:

a. defining a plurality of offset values, each offset value being associated with one of a plurality of data values;

b. defining a plurality of echo amplitudes, each amplitude being associated with one of the plurality of data values; and

c. creating an encoded string signal containing the host audio signal and echoes of sections of the host audio signal, each echo having one of the echo amplitudes and being separated in time from the host audio signal by one of the offset values, the echoes being ordered so as to encode a series of data values.

18. The method of claim 17 wherein the encoded string signal contains two echoes of the same section of the host audio signal, each of the two echoes being separated in time from the host audio signal in the encoded string signal by an offset value, each said offset value being unequal to the other, each said echo embedding a different data value.

19. The method of claim 18 wherein the encoded string signal contains embedded two series of data values.

20. The method of claim 17 further comprising the step of creating a plurality of encoded signals, each encoded signal having an embedded data value and, comprising a portion of the host audio signal and an echo of the portion of the host audio signal, the echo having one of the echo amplitudes and being separated in time from the host audio signal in the encoded signal by one of the offset values, the echo embedding the data value.

21. The method of claim 20 wherein the portion of the host audio signal in one of the encoded signals is identical to the portion in every other of the encoded signals and further comprising the steps of:

a. identifying a set of temporal points; and

b. using the set of temporal points to divide each of the encoded signals into a series of segments, each segment having an origin defined by a temporal point and containing an echo, corresponding to the value embedded in the respective encoded signal, of a section of the host audio signal, the encoded string signal comprising segments from the encoded signals, the segments arranged so that the encoded string signal contains the original host signal and echoes of sections of the host audio signal, the echoes being ordered so as to encode the series of data values.

22. The method of claim 20 wherein the portions of the host audio signal in any two of the encoded signals do not coincide, the encoded string signal being created by concatenating the encoded signals.

23. The method of claim 21 wherein the steps of dividing the first and second encoded signals into segments and of creating an encoded string signal comprise:

a. filtering each of the encoded signals with a respective mixer function having value equal to one at time values corresponding to a region between temporal points defining one or more segments of the respective encoded signal that are to be included in the encoded string signal and value equal to zero at time values corresponding to a region between temporal points defining one or more segments not to be so included, thereby creating a plurality of partial strings; and

b. adding the partial strings together.

24. The method of claim 23 wherein the value of each mixer function is between zero and one at time values corresponding to a region of the encoded signal filtered by that mixer function between a region to be included and a region not to be included in the encoded string signal.

25. The method of claim 17 wherein a first of the plurality of offset values is a one offset, associated with a binary one, and the second of a plurality of offset values is a zero offset, associated with a binary zero.

26. The method of claim 25 wherein the one offset and the zero offset differ by at least 0.2 milliseconds.

27. The method of claim 17 wherein the absolute value of each of the plurality of offset values is less than 1.5 millisecond.

28. The method of claim 17 wherein the absolute value of each of the plurality of offset values is less than 1 millisecond.

29. The method of claim 17 wherein the encoded string signal contains more than one echo, separated from one another by one of the plurality of bit values, of the same section of the host audio signal, the more than one echo embedding one bit having a bit value associated with the one of the plurality of bit values.

30. A method of embedding information in a host audio signal, the method comprising the steps of:

a. defining a pulse train comprising a copy pulse, having a copy amplitude, for reproducing the host audio signal, and a first echo pulse, having a first amplitude, for creating a first echo of the host audio signal, the copy pulse and the echo pulse being separated in time by an offset value, the offset value being associated with a data value, the ratio of the first amplitude to the copy amplitude defined to be the echo amplitude; and

b. processing the pulse train with the host audio signal, thereby creating an encoded signal, comprising the host audio signal and a first echo of the host audio signal, containing the data value.

31. The method of claim 30 wherein the pulse train farther comprises an additional pulse having a pulse amplitude and being separated in time from the first echo pulse by the offset value.

32. The method of claim 30 wherein the pulse train further comprises a plurality of additional pulses, each having a respective pulse amplitude, and being separated in time from the first echo pulse by an integral multiple of the offset value, each of the plurality of additional pulses creating an additional repetition of the host audio signal in the encoded signal.

33. The method of claim 32 wherein one of the one or more additional pulses has a pulse amplitude equal to the product of the first amplitude and a decay rate, each other of the one or more additional pulses having a respective pulse echo amplitude equal to the product of the echo amplitude and an integral power of the decay rate.

34. The method of claim 32 wherein the pulse train is a discrete-time exponential.

35. The method of claim 30 wherein the first amplitude is less than 0.85.

36. The method of claim 30 wherein the first amplitude is less than 0.6.

37. The method of claim 30 wherein the first amplitude is between 0.4 and 0.8.

38. The method of claim 30 wherein the echo pulse is a discrete impulse.

39. The method of claim 30 wherein the echo pulse is Gaussian in shape.

40. The method of claim 30 wherein the absolute value of the offset value is less than 1 millisecond.

41. The method of claim 30 wherein the absolute value of the offset value is less than 1.5 millisecond.

42. The method of claim 30 wherein the absolute value of the offset value is between 0.5 and 1 millisecond.

43. The method of claim 30 wherein the echo pulse has a form that introduces into the encoded signal a resonance perceived as a typical natural resonance.

44. A method for determining whether a test signal contains a datum embedded by creating an encoded signal comprising a host audio signal and a scaled repetition of the host audio signal, the scaled repetition in the encoded signal being separated in time from the host audio signal by an offset value associated with the value of the datum, the method comprising the steps of:

a. observing the amplitude of a function of the test signal at the offset value; and

b. determining whether the test signal contains the datum based on the amplitude of the function at the offset value.

45. The method of claim 44 wherein the step of observing the amplitude includes observing the autocorrelation of the test signal.

46. The method of claim 44 wherein the step of observing the amplitude includes observing the cepstrum of the test signal.

47. The method of claim 44 wherein the step of observing the amplitude includes observing the autocorrelation of the cepstrum of the test signal.

48. A method of decoding a string of data values embedded in an encoded string signal by defining a plurality of offset values, each offset value being associated with one of a plurality of data values, and creating an encoded string signal comprising a host audio signal, divided into encoding temporal segments, each encoding temporal segment corresponding to a position in the string, each segment containing an echo of a respective section of the host audio signal, the echo in each segment being separated in time from the host audio signal by a respective offset value, the respective segment representing the data value associated with the respective offset value, the method of decoding comprising the steps of:

a. dividing the encoded signal into decoding temporal segments corresponding to the encoding temporal segments;

b. in each segment, observing the amplitude of a function of the encoded signal at each of the plurality of offset values; and

c. assigning a segment data value to the segment based on the values observed.

49. The method of claim 48 wherein the step of observing the amplitude includes observing the autocorrelation of the test signal.

50. The method of claim 48 wherein the step of observing the amplitude includes observing the cepstrum of the test signal.

51. The method of claim 48 wherein the step of observing the amplitude includes observing the autocorrelation of the cepstrum of the test signal.

52. The method of claim 48 wherein the decoding temporal segments are related to the encoding temporal segments such that exactly one decoding temporal segment corresponds to each encoding segment.

53. The method of claim 48 wherein the decoding temporal segments are related to the encoding temporal segments such that two decoding temporal segments having the same length correspond to each encoding temporal segment.

54. The method of claim 53 wherein every other decoding segment is designated an odd decoding segment and the remaining decoding segments are designated even decoding segments, each segment data value being designated an odd segment data value or an even segment data value according to the decoding segment to which that segment data value is assigned, either the odd segment data values or the even segment data values being determined to be the string embedded in the encoded string signal, based on the presence or absence of an error correction code in the odd or even segment data values.

55. The method of claim 48 wherein the decoding temporal segments are related to the encoding temporal segments such that an odd number of adjacent decoding temporal segments of equal length form a segment set corresponding to an encoding temporal segment.

56. The method of claim 55 further comprising the step of ascribing the segment data value assigned to the majority of decoding segments in a segment set to every segment in that segment set, the entire segment set corresponding to a position in the string embedded in the encoded string signal.

57. The method of claim 48 wherein the same function is observed in each segment.

58. The method of claim 48 wherein the function observed in one of the segments differs from the function observed in another of the segments.

59. The method of claim 53 wherein the encoding temporal segments have an encoding segment length and the decoding temporal segments have a decoding segment length equal to less than half of the encoding segment length.

60. An apparatus for embedding information in a host signal, the apparatus comprising:

a. input means for accepting the host signal;

b. means for associating an offset value with a bit value; and

c. means for creating an encoded signal containing the host signal and an echo of the host signal, the echo being separated in time in the encoded signal from the host signal by an offset value associated with a bit value embedded in the encoded signal.

61. An apparatus for determining whether a test signal contains a bit embedded as an echo of a host audio signal, the echo being separated in time from the host audio signal in the test signal by an offset value associated with a value of the bit, the apparatus comprising:

a. input means for accepting the test signal

b. means for computing the amplitude of a function of the test signal at the offset value;

c. means for determining whether the test signal contains the bit based on the computed amplitude.