Quantization-based data embedding in mapped data

• US 7,769,202 B2
• Filed: 05/20/2008
• Issued: 08/03/2010
• Est. Priority Date: 03/22/2001
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Stach, John, Bradley, Brett A.
• Primary Examiner(s): Johns; Andrew W
• Application Number:
  US12/124,032
• Publication Number:
  US 20090022360A1
• Time in Patent Office: 805 Days
• Field of Search: 382/100, 382/232, 382/251, 358/3.28, 713/176, 380/287, 380/54
• US Class Current: 382/100
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2200/36 Review paper; Tutorial; Survey
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: G10L 19/032 Quantisation or dequantisation of spectral components
• CPC Class Codes: G10L 21/00 Speech or voice signal processing techniques to produce another audible or non-audible signal, e.g. visual or tactile, in order to modify its quality or its intelligibility G10L19/00 takes precedence
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32154 Transform domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32187 with selective or adaptive application of the additional information, e.g. in selected frequency coefficients
• CPC Class Codes: H04N 1/32197 according to the spatial domain characteristics of the transform domain components
• CPC Class Codes: H04N 1/3232 Robust embedding or watermarking
• CPC Class Codes: H04N 1/32352 Controlling detectability or arrangements to facilitate detection or retrieval of the embedded information, e.g. using markers for decoding, detection or retrieval operations H04N1/32149 and subgroups take precedence

Abstract

Novel methods and systems for quantization based data embedding and reading in host signals, such as image, audio and video signals. To embed auxiliary data in a host signal, an embedder maps the host signal from a first domain into a mapped signal in a second domain. The embedder performs quantization based embedding of auxiliary data into the host signal using quantizers. The quantizers are adapted such that the relationship between corresponding quantizers in the first and second domains satisfies a predetermined constraint. The mapping improves the robustness of the data embedding method by increasing the chances that the embedded data can be recovered by an auxiliary data reader after modifications. A related embedding method projects the mapped signal unto a vector, and specifically, a pseudorandom vector. It performs quantization based embedding on the projected signal. The use of this projection provides added robustness of the embedded data to noise and other forms of distortion.

Claims

1. A method for data embedding into a host signal comprising:

mapping the host signal from a first domain into a mapped signal in a second domain;

computing quantization bins such that corresponding quantization bins in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantization bins in the first and second domains; and

performing quantization based embedding of auxiliary data into the host signal using quantization bins computed from the second domain.

2. The method of claim 1 wherein mapping comprising computing a cumulative distribution function of the host signal to compute the mapped signal.

3. The method of claim 1 wherein the quantization based embedding embeds the auxiliary data by adjusting values of the host signal such that the adjusted values fall into bins corresponding to auxiliary data symbols to be embedded.

4. The method of claim 3 wherein spacing of the bins is at least initially uniform in the second domain, and is non-uniform in the first domain.

5. The method of claim 3 including adapting spacing of the bins in the first domain to make the spacing more uniform in the first domain.

6. The method of claim 5 including embedding a reference signal comprising known auxiliary data values for use in deriving bin arrangement in an auxiliary data reader.

7. The method of claim 3 including using a finite state machine to assign the bins.

8. A computer readable medium on which is stored instructions, which, when executed by a computer, perform the method of claim 1.

9. The method of claim 1 including:

using a programmed computer to perform the acts of;

mapping the host signal from a first domain into a mapped signal in a second domain;

computing quantization bins such that corresponding quantization bins in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantization bins in the first and second domains; and

performing quantization based embedding of auxiliary data into the host signal using quantization bins computed from the second domain.

10. A method for data embedding into a host signal comprising:

mapping the host signal from a first domain into a mapped signal in a second domain;

projecting the mapped signal onto a pseudo random vector;

computing quantizers such that corresponding quantizers in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantizers in the first and second domains; and

performing a quantization based embedding on the projection of the mapped signal onto the pseudo random vector.

11. The method of claim 10 wherein the host signal is partitioned into vectors of elements, and each vector is projected onto a corresponding pseudorandom vector.

12. The method of claim 11 wherein the vectors of elements are selected from pseudorandom locations in the host signal.

13. The method of claim 10 including performing a weighted projection onto the pseudorandom vector.

14. The method of claim 13 wherein weights used in the weighted projection are derived from the host signal so as to increase robustness of the embedded data or perceptual quality of the host signal after embedding.

15. The method of claim 13 wherein weights used in the weighted projection are computed so as to be derivable from the host signal after embedding and distortion of the host signal.

16. The method of claim 13 including embedding a reference signal comprising known auxiliary values for use in deriving the weights in an auxiliary data reader for reading the embedded data from the host signal.

17. A computer readable medium on which is stored instructions, which, when executed by a computer, perform the method of claim 10.

18. The method of claim 10 including:

using a programmed computer to perform the acts of;

mapping the host signal from a first domain into a mapped signal in a second domain;

projecting the mapped signal onto a pseudo random vector;

computing quantizers such that corresponding quantizers in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantizers in the first and second domains; and

performing a quantization based embedding on the projection of the mapped signal onto the pseudo random vector.

19. A method of reading auxiliary data embedded in a host signal comprising:

mapping the host signal from a first domain into a mapped signal in a second domain that is robust to a class of modifications;

computing quantizers such that corresponding quantizers in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantizers in the first and second domains; and

performing quantization based reading of auxiliary data embedded into the host signal using quantizers computed from the second domain.

20. The method of claim 19 including:

using reference signal values embedded into the host signal to derive the quantizers.

21. The method of claim 20 wherein the reference signal comprises training data embedded using quantization based embedding.

22. The method of claim 19 including using dynamic programming to predict the quantizers.

23. The method of claim 19 including using a structured search through possible state transitions to predict the quantizers.

24. The method of claim 23 including using a Viterbi method to predict the quantizers.

25. A computer readable medium on which is stored instructions, which, when executed by a computer, perform the method of claim 19.

26. The method of claim 19 including:

using a programmed computer to perform the acts of;

mapping the host signal from a first domain into a mapped signal in a second domain that is robust to a class of modifications;

computing quantizers such that corresponding quantizers in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantizers in the first and second domains; and

performing quantization based reading of auxiliary data embedded into the host signal using quantizers computed from the second domain.

27. A method of reading auxiliary data embedded in a host signal comprising:

mapping the host signal from a first domain into a mapped signal in a second domain that is robust to a class of modifications;

projecting the mapped signal onto a pseudo random vector;

computing quantizers such that corresponding quantizers in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantizers in the first and second domains; and

performing a quantization based reading of the auxiliary data embedded in a projection of the mapped signal onto the pseudo random vector.

28. The method of claim 27 wherein the host signal is partitioned into vectors of elements, and each vector is projected onto a corresponding pseudorandom vector.

29. The method of claim 28 wherein the vectors of elements are selected from pseudorandom locations in the host signal.

30. The method of claim 27 including performing a weighted projection onto the pseudorandom vector.

31. The method of claim 30 wherein weights used in the weighted projection are derived from the host signal so as to increase robustness of the embedded data or perceptual quality of the host signal after embedding.

32. The method of claim 30 wherein weights used in the weighted projection are computed so as to be derivable from the host signal after embedding and distortion of the host signal.

33. The method of claim 30 including reading an embedded reference signal comprising known auxiliary values for use in deriving the weights.

34. A computer readable medium on which is stored instructions, which, when executed by a computer, perform the method of claim 27.

35. The method of claim 27 including:

using a programmed computer to perform the acts of;

mapping the host signal from a first domain into a mapped signal in a second domain that is robust to a class of modifications;

projecting the mapped signal onto a pseudo random vector;

computing quantizers such that corresponding quantizers in the first and second domains satisfy a constraint, wherein the mapping provides the corresponding quantizers in the first and second domains; and

performing a quantization based reading of the auxiliary data embedded in a projection of the mapped signal onto the pseudo random vector.