Determination of a best offset to detect an embedded pattern

• US 6,330,673 B1
• Filed: 10/14/1998
• Issued: 12/11/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): Hayes, Gail
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US09/172,583
• Time in Patent Office: 1,154 Days
• Field of Search: 713/176, 713/179, 380/31, 380/34, 380/36, 380/42, 380/54, 380/205, 380/210, 380/220, 380/253, 380/212, 375/130, 375/142, 375/150, 375/152, 375/200, 341/50
• US Class Current: 713/176
• 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. A watermark alignment module determines which of a large number of offsets of the watermarked data is most likely to correspond to a recognizable watermark. The watermark alignment module uses a single basis signal to evaluate a number of offsets over a relatively narrow range of offsets. In addition, offsets which differ by an integer multiple of a spatial/temporal granularity of respective noise threshold spectra are recognized as corresponding to equivalent noise threshold spectra. Accordingly, a previously generated noise threshold spectrum for one offset is reused for a second offset which differs by an integer multiple of the spatial/temporal granularity.

Claims

1. A method for determining a best offset with which to detect an embedded pattern in a digitized analog signal, the method comprising:

(a) selecting a range of two or more offsets of the digitized analog signal;

(b) selecting a selected offset of the range of offsets;

(c) forming a candidate basis signal in accordance with the selected offset of the digitized analog signal;

(d) for each offset of the range of offsets;

(i) shifting the digitized analog signal in accordance with the offset to form a shifted signal; and

(ii) comparing the candidate basis signal to the shifted signal to provide a respective correlation signal; and

(e) selecting the best offset of the range of offsets according to the respective correlation signals;

wherein the selected offset is a central offset of the range of offsets.

2. A method for determining a best offset with which to detect an embedded pattern in a digitized analog signal, the method comprising:

(a) selecting a range of two or more offsets of the digitized analog signal;

(b) selecting a selected offset of the range of offsets;

(c) forming a candidate basis signal in accordance with the selected offset of the digitized analog signal;

(d) for each offset of the range of offsets;

(i) shifting the digitized analog signal in accordance with the offset to form a shifted signal; and

(ii) comparing the candidate basis signal to the shifted signal to provide a respective correlation signal; and

(e) selecting the best offset of the range of offsets according to the respective correlation signals;

wherein forming a candidate basis signal comprises performing spread-spectrum chipping using a sequence of pseudo-random bits; and

further wherein performing spread-spectrum chipping comprises mixing the sequence of pseudo-random bits with a spectrum of noise thresholds formed according to a constant-quality psycho-sensory model.

3. A method for determining a best offset with which to detect an embedded pattern in a digitized analog signal, the method comprising:

deriving first spectral data from the digitized analog signal according to a first offset, wherein the first spectral data associate data according to groups of a predetermined number of samples of the digitized analog signal;

forming a first candidate signal from the first spectral data;

shifting the digitized analog signal in accordance with the first offset to form a first shifted signal;

comparing the first candidate signal to the shifted signal to provide a first correlation signal;

selecting a second offset which is separated from the first offset by an integer multiple of the predetermined number of samples;

forming a second candidate signal from the first spectral data;

shifting the digitized analog signal in accordance with the second offset to form a second shifted signal;

comparing the second candidate signal to the second shifted signal to provide a second correlation signal; and

selecting the best offset by comparison of two or more correlation signals which include the first and second correlation signals.

4. The method of claim 3 wherein forming a first candidate signal comprises:

combining the first spectral data with a first sequence of pseudo-random bits which are aligned with the first offset; and

further wherein the step of forming a second candidate signal comprises;

combining the first spectral data with a second sequence of pseudo-random bits which are aligned with the second offset.

5. The method of claim 3 wherein forming the second candidate signal comprises:

shifting the first spectral signal to form a second spectral signal; and

forming the second candidate signal from the second spectral signal.

6. The method of claim 5 wherein shifting the first spectral data comprises shifting the first spectral data by an amount corresponding to a difference between the first and second offsets.

7. The method of claim 3 wherein the digitized analog signal is an audio signal.

8. The method of claim 3 wherein the digitized analog signal is a video signal.

9. The method of claim 3 wherein forming the first and second candidate signals each comprises performing spread-spectrum chipping using a sequence of pseudo-random bits.

10. The method of claim 3 wherein the first spectral data includes a spectrum of noise thresholds formed according to a constant-quality psycho-acoustic model.

11. 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 best offset with which to detect an embedded pattern in a digitized analog signal by:

(a) selecting a range of two or more offsets of the digitized analog signal;

(b) selecting a selected offset of the range of offsets;

(c) forming a candidate basis signal in accordance with the selected offset of the digitized analog signal;

(d) for each offset of the range of offsets;

(i) shifting the digitized analog signal in accordance with the offset to form a shifted signal; and

(ii) comparing the candidate basis signal to the shifted signal to provide a respective correlation signal; and

(e) selecting the best offset of the range of offsets according to the respective correlation signals;

wherein the selected offset is a central offset of the range of offsets.

12. 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 best offset with which to detect an embedded pattern in a digitized analog signal by:

(a) selecting a range of two or more offsets of the digitized analog signal;

(b) selecting a selected offset of the range of offsets;

(c) forming a candidate basis signal in accordance with the selected offset of the digitized analog signal;

(d) for each offset of the range of offsets;

(i) shifting the digitized analog signal in accordance with the offset to form a shifted signal; and

(ii) comparing the candidate basis signal to the shifted signal to provide a respective correlation signal; and

(e) selecting the best offset of the range of offsets according to the respective correlation signals;

wherein form ing a candidate basis signal c omprises performing spread-spectrum chipping using a sequence of pseudo-random bits; and

further wherein performing spread-spectrum chi pping comprises mixing the sequence of pseudo-random bits with a spectrum of noise thresholds formed according to a constant-quality psycho-sensory model.

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 determine a best offset with which to detect an embedded pattern in a digitized analog signal by:

deriving first spectral data from the digitized analog signal according to a first offset, wherein the first spectral data associate data according to groups of a predetermined number of samples of the digitized analog signal;

forming a first candidate signal from the first spectral data;

shifting the digitized analog signal in accordance with the first offset to form a first shifted signal;

comparing the first candidate signal to the shifted signal to provide a first correlation signal;

selecting a second offset which is separated from the first offset by an integer multiple of the predetermined number of samples;

forming a second candidate signal from the first spectral data;

shifting the digitized analog signal in accordance with the second offset to form a second shifted signal;

comparing the second candidate signal to the second shifted signal to provide a second correlation signal; and

selecting the best offset by comparison of two or more correlation signals which include the first and second correlation signals.

14. The computer readable medium of claim 13 wherein forming a first candidate signal comprises:

combining the first spectral data with a first sequence of pseudo-random bits which are aligned with the first offset; and

further wherein the step of forming a second candidate signal comprises;

combining the first spectral data with a second sequence of pseudo-random bits which are aligned with the second offset.

15. The computer readable medium of claim 13 wherein forming the second candidate signal comprises:

shifting the first spectral signal to form a second spectral signal; and

forming the second candidate signal from the second spectral signal.

16. The computer readable medium of claim 15 wherein shifting the first spectral data comprises shifting the first spectral data by an amount corresponding to a difference between the first and second offsets.

17. The computer readable medium of claim 13 wherein the digitized analog signal is an audio signal.

18. The computer readable medium of claim 13 wherein the digitized analog signal is a video signal.

19. The computer readable medium of claim 13 wherein forming the first and second candidate signals each comprises performing spread-spectrum chipping using a sequence of pseudo-random bits.

20. The computer readable medium of claim 13 wherein the first spectral data includes a spectrum of noise thresholds formed according to a constant-quality psycho-acoustic model.

21. 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, c auses the computer to determine a best offset with which to detect an embedded pattern in a digitized analog signal by;

(a) select ing a range of two or more offsets of the digitized analog signal;

(b) selecting a selected offset of the range of offsets;

(c) forming a candidate basis signal in accordance with the selected offset of the digitized analog signal;

(d) for each offset of the range of offsets;

(i) shifting the digitized analog signal in accordance with the offset to form a shifted signal; and

(ii) comparing the candidate basis signal to the shifted signal to provide a respective correlation signal; and

(e) selecting the best offset of the range of offsets according to the respective correlation signals;

wherein the selected offset is a central offset of the range of offsets.

22. 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 determine a best offset with which to detect an embedded pattern in a digitized analog signal by;

(a) selecting a range of two or more offsets of the digitized analog signal;

(b) selecting a selected offset of the range of offsets;

(c) forming a candidate basis signal in accordance with the selected offset of the digitized analog signal;

(d) for each offset of the range of offsets;

(i) shifting the digitized analog signal in accordance with the offset to form a shifted signal; and

(ii) comparing the candidate basis signal to the shifted signal to provide a respective correlation signal; and

(e) selecting the best offset of the range of offsets according to the respective correlation signals;

wherein forming a candidate basis signal comprises performing spread-spectrum chipping using a sequence of pseudo-random bits; and

further wherein performing spread-spectrum chipping comprises mixing the sequence of pseudo-random bits with a spectrum of noise thresholds formed according to a constant-quality psycho-sensory model.

23. 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 determine a best offset with which to detect an embedded pattern in a digitized analog signal by;

deriving first spectral data from the digitized analog signal according to a first offset, wherein the first spectral data associate data according to groups of a predetermined number of samples of the digitized analog signal;

forming a first candidate signal from the first spectral data;

shifting the digitized analog signal in accordance with the first offset to form a first shifted signal;

comparing the first candidate signal to the shifted signal to provide a first correlation signal;

selecting a second offset which is separated from the first offset by an integer multiple of the predetermined number of samples;

forming a second candidate signal from the first spectral data;

shifting the digitized analog signal in accordance with the second offset to form a second shifted signal;

comparing the second candidate signal to the second shifted signal to provide a second correlation signal; and

selecting the best offset by comparison of two or more correlation signals which include the first and second correlation signals.

24. The computer system of claim 23 wherein forming a first candidate signal comprises:

combining the first spectral data with a first sequence of pseudo-random bits which are aligned with the first offset; and

further wherein the step of forming a second candidate signal comprises;

combining the first spectral data with a second sequence of pseudo-random bits which are aligned with the second offset.

25. The computer system of claim 23 wherein forming the second candidate signal comprises:

shifting the first spectral signal to form a second spectral signal; and

forming the second candidate signal from the second spectral signal.

26. The computer system of claim 25 wherein shifting the first spectral data comprises shifting the first spectral data by an amount corresponding to a difference between the first and second offsets.

27. The computer system of claim 23 wherein the digitized analog signal is an audio signal.

28. The computer system of claim 23 wherein the digitized analog signal is a video signal.

29. The computer system of claim 23 wherein forming the first and second candidate signals each comprises performing spread-spectrum chipping using a sequence of pseudo-random bits.

30. The computer system of claim 23 wherein the first spectral data includes a spectrum of noise thresholds formed according to a constant-quality psycho-acoustic model.