Efficient watermark method and apparatus for digital signals

• US 6,219,634 B1
• Filed: 10/14/1998
• Issued: 04/17/2001
• Est. Priority Date: 10/14/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Liquid Audio Inc
• Inventors: Levine, Earl
• Primary Examiner(s): Dorvil, Richemond
• Application Number:
  US09/172,922
• Time in Patent Office: 916 Days
• Field of Search: 704/229, 704/230, 704/201, 704/200, 704/205, 704/206, 704/207, 704/500, 704/200.1
• US Class Current: 704/200.1
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal

Abstract

Watermark data is encoded in a digitized signal by forming a noise threshold spectrum which represents a maximum amount of imperceptible noise, spread-spectrum chipping the noise threshold spectrum with a relatively endless stream of pseudo-random bits to form a basis signal, dividing the basis signal into segments, and filtering the segments to smooth segment boundaries. The data encoded in the watermark signal is precoded to make the watermark data inversion robust and is convolutional encoded to further increase the likelihood that the watermark data will subsequently be retrievable notwithstanding lossy processing of the watermarked signal. The basis signal fits noise thresholds determined by constant-quality quantization approximation. Noise introduced by quantization is estimated by determining a continuously differentiable function which approximates noise introduced by such quantization and using the function to solve for a relatively optimal gain to be applied during such quantization. The continuously differentiable function includes a local quantization stepsize. A local quantization stepsize is determined by first determining widths of quantization steps at respective particular amplitudes and interpolating stepssizes for amplitudes between the particular amplitudes. The interpolation of stepsizes provides a smooth function. The continuously differentiable function based upon a local, interpolated quantization stepsize provides an estimation of quantization error which lends itself to efficient and convenient mathematical manipulation.

Claims

1. A method for determining a maximum imperceptible amount of noise which can be added to a digitized analog signal, the method comprising:

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise.

2. The method of claim 1 wherein the psycho-sensory model is a psycho-acoustic model.

3. The method of claim 1 wherein the psycho-sensory model is a psycho-visual model.

4. The method of claim 1 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

5. The method of claim 4 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

6. The method of claim 5 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

7. The method of claim 4 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

8. The method of claim 1 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

9. A method for encoding embedded data in a digitized analog signal, the method comprising:

determining a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise;

forming a basis signal from the digitized analog signal such that the basis signal is no greater than the maximum imperceptible amount of noise;

encoding the embedded data into the basis signal to form an encoded basis signal; and

adding the encoded basis signal to the digitized analog signal to form an encoded digitized analog signal.

10. The method of claim 9 wherein the psycho-sensory model is a psycho-acoustic model.

11. The method of claim 9 wherein the psycho-sensory model is a psycho-visual model.

12. The method of claim 9 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

13. The method of claim 12 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

14. The method of claim 13 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

15. The method of claim 12 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

16. The method of claim 9 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

17. The method of claim 9 wherein forming the basis signal comprises:

spread-spectrum chipping a noise threshold spectrum representing the noise thresholds in accordance with a stream of pseudo-random bits.

18. A method for decoding embedded data from a digitized analog signal, the method comprising:

determining a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise;

forming a basis signal from the digitized analog signal such that the basis signal is no greater than the maximum imperceptible amount of noise;

correlating the basis signal with the digitized analog signal to form a correlation signal; and

decoding the embedded data form the correlation signal.

19. The method of claim 18 wherein the psycho-sensory model is a psycho-acoustic model.

20. The method of claim 18 wherein the psycho-sensory model is a psycho-visual model.

21. The method of claim 18 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

22. The method of claim 21 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

23. The method of claim 22 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

24. The method of claim 21 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

25. The method of claim 18 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

26. The method of claim 18 wherein forming the basis signal comprises:

spread-spectrum chipping a noise threshold spectrum representing the noise thresholds in accordance with a stream of pseudo-random bits.

27. A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to determine a maximum imperceptible amount of noise which can be added to a digitized analog signal by:

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise.

28. The computer readable medium of claim 27 wherein the psycho-sensory model is a psycho-acoustic model.

29. The computer readable medium of claim 27 wherein the psycho-sensory model is a psycho-visual model.

30. The computer readable medium of claim 27 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

31. The computer readable medium of claim 30 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

32. The computer readable medium of claim 31 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

33. The computer readable medium of claim 30 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

34. The computer readable medium of claim 27 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

35. A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to encode embedded data in a digitized analog signal by:

determining a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise;

forming a basis signal from the digitized analog signal such that the basis signal is no greater than the maximum imperceptible amount of noise;

encoding the embedded data into the basis signal to form an encoded basis signal; and

adding the encoded basis signal to the digitized analog signal to form an encoded digitized analog signal.

36. The computer readable medium of claim 35 wherein the psycho-sensory model is a psycho-acoustic model.

37. The computer readable medium of claim 35 wherein the psycho-sensory model is a psycho-visual model.

38. The computer readable medium of claim 35 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

39. The computer readable medium of claim 38 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

40. The computer readable medium of claim 39 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

41. The computer readable medium of claim 38 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

42. The computer readable medium of claim 35 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

43. The computer readable medium of claim 35 wherein forming the basis signal comprises:

spread-spectrum chipping a noise threshold spectrum representing the noise thresholds in accordance with a stream of pseudo-random bits.

44. A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to decode embedded data from a digitized analog signal by:

determining a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise;

forming a basis signal from the digitized analog signal such that the basis signal is no greater than the maximum imperceptible amount of noise;

correlating the basis signal with the digitized analog signal to form a correlation signal; and

decoding the embedded data form the correlation signal.

45. The computer readable medium of claim 44 wherein the psycho-sensory model is a psycho-acoustic model.

46. The computer readable medium of claim 44 wherein the psycho-sensory model is a psycho-visual model.

47. The computer readable medium of claim 44 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

48. The computer readable medium of claim 47 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

49. The computer readable medium of claim 48 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

50. The computer readable medium of claim 47 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

51. The computer readable medium of claim 44 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

52. The computer readable medium of claim 44 wherein forming the basis signal comprises:

spread-spectrum chipping a noise threshold spectrum representing the noise thresholds in accordance with a stream of pseudo-random bits.

53. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

a noise threshold generator (i) which executes in the processor from the memory and (ii) which, when executed by the processor, causes the computer to determine a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise.

54. The computer system of claim 53 wherein the psycho-sensory model is a psycho-acoustic model.

55. The computer system of claim 53 wherein the psycho-sensory model is a psycho-visual model.

56. The computer system of claim 53 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

57. The computer system of claim 56 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

58. The computer system of claim 57 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

59. The computer system of claim 56 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

60. The computer system of claim 53 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

61. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

an encoder module (i) which executes in the processor from the memory and (ii) which, when executed by the processor, causes the computer to encode embedded data in a digitized analog signal by;

determining a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise;

forming a basis signal from the digitized analog signal such that the basis signal is no greater than the maximum imperceptible amount of noise;

encoding the embedded data into the basis signal to form an encoded basis signal; and

adding the encoded basis signal to the digitized analog signal to form an encoded digitized analog signal.

62. The computer system of claim 61 wherein the psycho-sensory model is a psycho-acoustic model.

63. The computer system of claim 61 wherein the psycho-sensory model is a psycho-visual model.

64. The computer system of claim 61 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

65. The computer system of claim 64 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

66. The computer system of claim 65 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

67. The computer system of claim 64 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

68. The computer system of claim 61 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

69. The computer system of claim 61 wherein forming the basis signal comprises:

spread-spectrum chipping a noise threshold spectrum representing the noise thresholds in accordance with a stream of pseudo-random bits.

70. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

a decoder module (i) which executes in the processor from the memory and (ii) which, when executed by the processor, causes the computer to decode embedded data from a digitized analog signal by;

determining a maximum imperceptible amount of noise which can be added to a digitized analog signal by;

producing noise thresholds according to a psycho-sensory model;

determining a continuously differentiable function which approximates a quantization error permissible by the noise thresholds;

estimating a preferred gain for each one of the noise thresholds according to the continuously differentiable function, wherein the preferred gains for the respective noise thresholds collectively represent the maximum imperceptible amount of noise;

forming a basis signal from the digitized analog signal such that the basis signal is no greater than the maximum imperceptible amount of noise;

correlating the basis signal with the digitized analog signal to form a correlation signal; and

decoding the embedded data form the correlation signal.

71. The computer system of claim 70 wherein the psycho-sensory model is a psycho-acoustic model.

72. The computer system of claim 70 wherein the psycho-sensory model is a psycho-visual model.

73. The computer system of claim 70 wherein determining the continuously differentiable function comprises:

determining a local quantization step-size function.

74. The computer system of claim 73 wherein determining a local quantization step-size function comprises:

identifying specific amplitudes and associated quantization step-sizes; and

interpolating local step-sizes for amplitudes other than the specific amplitudes.

75. The computer system of claim 74 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

76. The computer system of claim 75 wherein determining the continuously differentiable function further comprises:

squaring the local quantization step-size function.

77. The computer system of claim 70 wherein each of the noise thresholds is associated with a respective block of two or more frequencies;

and

further wherein the estimating a preferred gain for each subject one of the noise thresholds comprises;

estimating an individual noise threshold for each subject frequency of the two or more frequencies of the block associated with the subject noise threshold by;

adjusting an associated amplitude of the subject frequency according to the preferred gain of the subject noise threshold to form a gained amplitude; and

using a difference between the associated amplitude and the gained amplitude in determining the individual noise threshold.

78. The computer system of claim 70 wherein forming the basis signal comprises:

spread-spectrum chipping a noise threshold spectrum representing the noise thresholds in accordance with a stream of pseudo-random bits.