Robust watermark method and apparatus for digital signals

• US 6,209,094 B1
• Filed: 10/14/1998
• Issued: 03/27/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, Brownell, Jason S.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Leaning, Jeffrey S.
• Application Number:
  US09/172,936
• Time in Patent Office: 895 Days
• Field of Search: 382/100, 382/232, 399/366, 713/176
• US Class Current: 713/176
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: H04N 21/23892 involving embedding information at multiplex stream level, e.g. embedding a watermark at packet level

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. Watermark data is encoded in a basis signal by division of the basis signal into segments and inverting the basis signal in segments corresponding to watermark data bits with a first logical value and not inverting the basis signal in segment corresponding to watermark data bits with a different logical value. The basis signal is smoothed at segment boundaries to eliminate any such discontinuities. Good results are achieved when scaling the basis signal by a cube-root of the positive half of a sine function which is aligned with segment boundaries such that the cube-root sine function tapers to zero at segment boundaries.

Claims

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

forming a basis signal from the digitized analog signal;

encoding the embedded data into the basis signal to form an encoded basis signal, wherein encoding includes;

dividing the basis signal into two or more segments; and

for each segment;

smoothing the basis signal near edges of the segment; and

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

2. The method of claim 1 wherein smoothing comprises:

adjusting the basis signal within the segment according to a function which provides a smooth transition from full strength of the basis signal near the center of the temporal segment to a reduced strength basis signal near edges of the temporal segment.

3. The method of claim 2 wherein the function includes a cube-root sine function.

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

forming a basis signal from the digitized analog signal;

correlating the basis signal with the digitized analog signal to form a correlation signal, wherein correlating includes;

dividing the basis signal into two or more segments; and

for each segment;

smoothing the basis signal near edges of the segment; and

decoding the embedded data from the correlation signal.

5. The method of claim 4 wherein smoothing comprises:

adjusting the basis signal within the segment according to a function which provides a smooth transition from full strength of the basis signal near the center of the segment to a reduced strength basis signal near edges of the segment.

6. The method of claim 5 wherein the function includes a cube-root sine function.

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

(a) forming a basis signal from the digitized analog signal;

(b) correlating the basis signal with the digitized analog signal to form a correlation signal, wherein correlating includes;

(i) dividing the basis signal into two or more segments;

(ii) collecting two or more subject ones of the segments which correspond to a particular bit of the embedded data; and

(iii) combining the two or more subject segments to provide a metric which represents a degree of likelihood that the particular bit represents a predetermined logical value, wherein combining includes;

(1) for each of the subject segments;

correlating the basis signal with the digitized analog signal within the subject segment to provide a metric signal; and

(2) combining the metric signals of the two or more segments to form a composite metric signal for the particular bit; and

(c) decoding the embedded data from the correlation signal.

8. The method of claim 7 wherein correlating the basis signal with the digitized analog signal within the subject segment to provide a metric signal comprises:

correlating the basis signal with the digitized analog signal within the subject segment to provide a segment correlation signal;

measuring the power of the basis signal within the subject segment to provide a segment power signal; and

forming the metric signal from a ratio between the segment correlation signal and the segment power signal.

9. The method of claim 8 wherein combining comprises:

forming a ratio between (i) a sum of correlation signals between the basis signal and the digitized analog signal within the two or more subject segments and (ii) a sum of basis signal power measurements within the two or more subject segments to form a ratio metric signal;

using the ratio metric signal to form the composite metric signal;

estimating the degree of likelihood using a hyperbolic tangent of the composite metric signal.

10. The method of claim 9 wherein estimating comprises:

adjusting the composite metric signal according to an estimated amount of noise in the digitized analog signal; and

estimating the degree of likelihood using the hyperbolic tangent of the composite metric signal as adjusted.

11. The method of claim 9 wherein the composite metric is the ratio metric signal.

12. The method of claim 7 wherein combining comprises forming a ratio between (i) a sum of correlation signals between the basis signal and the digitized analog signal within the two or more subject segments and (ii) a sum of basis signal power measurements within the two or more subject segments, the ratio being for use in forming the composite metric signal.

13. 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:

forming a basis signal from the digitized analog signal;

encoding the embedded data into the basis signal to form an encoded basis signal, wherein encoding includes;

dividing the basis signal into two or more segments; and

for each segment;

smoothing the basis signal near edges of the segment; and

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

14. The computer readable medium of claim 13 wherein smoothing comprises:

adjusting the basis signal within the segment according to a function which provides a smooth transition from full strength of the basis signal near the center of the segment to a reduced strength basis signal near edges of the segment.

15. The computer readable medium of claim 14 wherein the function includes a cube-root sine function.

16. 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:

forming a basis signal from the digitized analog signal;

correlating the basis signal with the digitized analog signal to form a correlation signal, wherein correlating includes;

dividing the basis signal into two or more segments; and

for each segment;

smoothing the basis signal near edges of the segment; and

decoding the embedded data from the correlation signal.

17. The computer readable medium of claim 16 wherein smoothing comprises:

adjusting the basis signal within the segment according to a function which provides a smooth transition from full strength of the basis signal near the center of the segment to a reduced strength basis signal near edges of the segment.

18. The computer readable medium of claim 17 wherein the function includes a cube-root sine function.

19. 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:

forming a basis signal from the digitized analog signal;

correlating the basis signal with the digitized analog signal to form a correlation signal, wherein correlating includes;

dividing the basis signal into two or more segments;

collecting two or more subject ones of the segments which correspond to a particular bit of the embedded data; and

combining the two or more subject temporal segments to provide a metric which represents a degree of likelihood that the particular bit represents a predetermined logical value, wherein combining includes;

for each of the subject segments;

correlating the basis signal with the digitized analog signal within the subject segment to provide a metric signal; and

combining the metric signals of the two or more segments to form a composite metric signal for the particular bit; and

decoding the embedded data from the correlation signal.

20. The computer readable medium of claim 19 wherein correlating the basis signal with the digitized analog signal within the subject segment to provide a metric signal comprises:

correlating the basis signal with the digitized analog signal within the subject segment to provide a segment correlation signal;

measuring the power of the digitized analog signal within the subject segment to provide a segment power signal; and

forming the metric signal from a ratio between the segment correlation signal and the segment power signal.

21. The computer readable medium of claim 20 wherein combining comprises:

forming a ratio between (i) a sum of correlation signals between the basis signal and the digitized analog signal within the two or more subject segments and (ii) a sum of basis signal power measurements within the two or more subject segments to form a ratio metric signal;

using the ratio metric signal to form the composite metric signal;

estimating the degree of likelihood using a hyperbolic tangent of the composite metric signal.

22. The computer readable medium of claim 21 wherein estimating comprises:

adjusting the composite metric signal according to an estimated amount of noise in the digitized analog signal; and

estimating the degree of likelihood using the hyperbolic tangent of the composite metric signal as adjusted.

23. The computer readable medium of claim 21 wherein the composite metric is the ratio metric signal.

24. The computer readable medium of claim 19 wherein combining comprises forming a ratio between (i) a sum of correlation signals between the basis signal and the digitized analog signal within the two or more subject segments and (ii) a sum of basis signal power measurements within the two or more subject segments, the ratio being for use in forming the composite metric signal.

25. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

an alignment 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;

forming a basis signal from the digitized analog signal;

encoding the embedded data into the basis signal to form an encoded basis signal, wherein encoding includes;

dividing the basis signal into two or more segments; and

for each segment;

smoothing the basis signal near edges of the segment; and

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

26. The computer system of claim 25 wherein smoothing comprises:

adjusting the basis signal within the segment according to a function which provides a smooth transition from full strength of the basis signal near the center of the segment to a reduced strength basis signal near edges of the segment.

27. The computer system of claim 26 wherein the function includes a cube-root sine function.

28. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

an alignment 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;

forming a basis signal from the digitized analog signal;

correlating the basis signal with the digitized analog signal to form a correlation signal, wherein correlating includes;

dividing the basis signal into two or more segments; and

for each segment;

smoothing the basis signal near edges of the segment; and

decoding the embedded data from the correlation signal.

29. The computer system of claim 28 wherein smoothing comprises:

adjusting the basis signal within the segment according to a function which provides a smooth transition from full strength of the basis signal near the center of the segment to a reduced strength basis signal near edges of the segment.

30. The computer system of claim 29 wherein the function includes a cube-root sine function.

31. A computer system comprising:

(a) a processor;

(b) a memory operatively coupled to the processor; and

(c) an alignment 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;

(A) forming a basis signal from the digitized analog signal;

(B) correlating the basis signal with the digitized analog signal to form a correlation signal, wherein correlating includes;

(1) dividing the basis signal into two or more segments;

(2) collecting two or more subject ones of the segments which correspond to a particular bit of the embedded data; and

(3) combining the two or more subject temporal segments to provide a metric which represents a degree of likelihood that the particular bit represents a predetermined logical value, wherein combining includes;

(i) for each of the subject segments;

correlating the basis signal with the digitized analog signal within the subject segment to provide a metric signal; and

(ii) combining the metric signals of the two or more segments to form a composite metric signal for the particular bit; and

(C) decoding the embedded data from the correlation signal.

32. The computer system of claim 31 wherein correlating the basis signal with the digitized analog signal within the subject segment to provide a metric signal comprises:

correlating the basis signal with the digitized analog signal within the subject segment to provide a segment correlation signal;

measuring the power of the digitized analog signal within the subject segment to provide a segment power signal; and

forming the metric signal from a ratio between the segment correlation signal and the segment power signal.

33. The computer system of claim 32 wherein combining comprises:

forming a ratio between (i) a sum of correlation signals between the basis signal and the digitized analog signal within the two or more subject segments and (ii) a sum of basis signal power measurements within the two or more subject segments to form a ratio metric signal;

using the ratio metric signal to form the composite metric signal;

estimating the degree of likelihood using a hyperbolic tangent of the composite metric signal.

34. The computer system of claim 33 wherein estimating comprises:

adjusting the composite metric signal according to an estimated amount of noise in the digitized analog signal; and

estimating the degree of likelihood using the hyperbolic tangent of the composite metric signal as adjusted.

35. The computer system of claim 33 wherein the composite metric is the ratio metric signal.

36. The computer system of claim 31 wherein combining comprises forming a ratio between (i) a sum of correlation signals between the basis signal and the digitized analog signal within the two or more subject segments and (ii) a sum of basis signal power measurements within the two or more subject segments, the ratio being for use in forming the composite metric signal.