Digital watermarking

• US 5,915,027 A
• Filed: 11/05/1996
• Issued: 06/22/1999
• Est. Priority Date: 11/05/1996
• Status: Expired due to Term

• Current Assignee: NEC Personal Computers, Ltd. (Lenovo Group Ltd.)
• Original Assignee: NEC Corporation, NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Miller, Matthew L., Tanaka, Kazuyoshi, Cox, Ingemar J., Wakasu, Yutaka
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/746,022
• Time in Patent Office: 959 Days
• Field of Search: 388/28, 388/51, 388/54
• US Class Current: 380/54
• CPC Class Codes: G06T 1/0035 Output size adaptive watermarking
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G06T 2201/0053 Embedding of the watermark in the coding stream, possibly without decoding; Embedding of the watermark in the compressed domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G11B 20/00913 based on a spread spectrum technique
• CPC Class Codes: H04N 1/32154 Transform domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32165 using cosine transforms
• CPC Class Codes: H04N 1/32277 Compression
• CPC Class Codes: H04N 1/32288 Multiple embedding, e.g. cocktail embedding, or redundant embedding, e.g. repeating the additional information at a plurality of locations in the image
• CPC Class Codes: H04N 1/32304 Embedding different sets of additional information
• CPC Class Codes: H04N 19/467 characterised by the embedded information being invisible, e.g. watermarking
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 21/23892 involving embedding information at multiplex stream level, e.g. embedding a watermark at packet level
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes
• CPC Class Codes: H04N 2201/328 Processing of the additional information
• CPC Class Codes: H04N 2201/3284 for error correction

Abstract

Digital watermarking of data, including image, video and audio data, is performed by repeatedly inserting the watermark into subregions or subimages of the data. Similarly, the watermark is repeatedly extracted from the subregions of the data.

Claims

1. A method for inserting a watermark signal into data to be watermarked comprising the steps of:

dividing data to be watermarked into a plurality of subregions;

computing frequency coefficients of the data to be watermarked in each subregion;

spread spectrum modulating a watermark signal to be inserted by mapping the watermark signal into a PN (pseudo-random noise) sequence;

spectral shaping the PN sequence as a function of the average power in each frequency coefficient of the data; and

inserting each spectral shaped PN sequence into predetermined coefficients in the data in each subregion.

2. A method for inserting a watermark signal into data to be watermarked as set forth in claim 1, where said inserting is performed after the data undergoes MPEG quantization processing.

3. A method for inserting a watermark signal into data to be watermarked as set forth in claim 1, where said frequency coefficients are DCT (discrete cosine transform) coefficients.

4. A method for inserting a watermark signal into data to be watermarked as set forth in claim 3, where each subregion is a 8×

8 block of pixels.

5. A method for inserting a watermark signal into data to be watermarked as set forth in claim 4, where said inserting is performed after the data undergoes MPEG quantization processing.

6. A method for inserting a watermark signal into data to be watermarked as set forth in claim 1, where each subregion is a 8×

8 block of pixels.

7. A method for inserting a watermark signal into data to be watermarked as set forth in claim 6, where said inserting is performed after the data undergoes MPEG quantization processing.

8. A method for inserting a watermark signal into data to be watermarked as set forth in claim 6, where the frequency coefficients of the watermark signal are rotated prior to inserting of each spectral shaped PN sequence into the subregion.

9. A method for inserting a watermark signal into data to be watermarked as set forth in claim 8, where said inserting is performed after the data undergoes MPEG quantization processing.

10. A method for inserting a watermark signal into data to be watermarked as set forth in claim 8, where only a subset of the watermark signal frequency coefficients is inserted into any one subregion.

11. A method for inserting a watermark signal into data to be watermarked as set forth in claim 10, where the watermark signal comprises a synchronization portion and a verification portion.

12. A method for inserting a watermark signal into data to be watermarked as set forth in claim 11, where said inserting is performed after the data undergoes MPEG quantization processing.

13. A method for inserting a watermark signal into data to be watermarked as set forth in claim 11, where the synchronization portion and the verification portion have very little correlation between each other.

14. A method for inserting a watermark signal into data to be watermarked as set forth in claim 1, where the spectral shaping as a function of the average power is typically 3×

1 window of the coefficient obtained from the one-dimensional vectorization by zigzagging of two-dimension frequency coefficients.

15. A method for inserting a watermark signal into data to be watermarked as set forth in claim 1, where the spectral shaping is a function of the average power based on the two four-connected frequency coefficients closest to the DC term.

16. A method of extracting a watermark from watermarked data comprising the steps of:

receiving subregions of watermarked data;

spectrum normalizing the watermarked data as a function of the average power in each frequency coefficient of the watermarked data in each subregion to generate respective normalized signals;

combining the respective normalized signals from each subregion to generate a single watermark;

correlating the single watermark with predetermined PN (pseudo-random noise) sequences corresponding to predetermined symbols to provide correlated signals for each predetermined PN sequence in each subregion;

deciding which correlated signal is most likely a current symbol; and

extracting a sequence of most likely current symbols corresponding to the watermark.

17. A method of extracting a watermark from watermarked data as set forth in claim 16, where the subregions are 8×

8 blocks used for MPEG encoding and decoding.

18. A method of extracting a watermark from watermarked data as set forth in claim 17, where said combining the normalized signals from each subregion to generate a single watermark, including removing the relative rotation of the watermark between blocks.

19. A method of extracting a watermark from watermarked data as set forth in claim 18, further comprising subsequently reconstructing the watermark from partial watermarks inserted into each block.

20. A method of extracting a watermark from watermarked data as set forth in claim 19, further comprising weighting the watermark coefficients based on their location within the frequency spectrum, where the weighting is a function of the susceptibility of each frequency coefficient to common signal transformations.

21. A method of extracting a watermark from watermarked data as set forth in claim 16, further comprising correlating with all rotational shifts of the extracted watermark and selecting the maximum value.

22. A method of extracting a watermark from watermarked data as set forth in claim 16, further comprising correlating with all rotational shifts of a synchronization portion of a watermark to determine a maximum value and subsequently rotating a verification portion of the watermark by the same amount as the synchronization portion is rotated to obtain the maximum value prior to correlating between the verification portion and predetermined PN sequences.

23. A method of extracting a watermark from watermarked data comprising the steps of:

receiving subregions of watermarked data;

spectrum normalizing the watermarked data as a function of the average power in each frequency coefficient of the watermarked data in each subregion to generate respective normalized signals;

correlating the respective normalized signals with predetermined PN sequences corresponding to predetermined symbols to provide correlated signals for each predetermined PN sequence in each subregion;

deciding which correlated signal is most likely a current symbol in each subregion for providing an extracted symbol stream;

error correcting the extracted symbol stream; and

extracting a sequence of most likely current symbols corresponding to the watermark.

24. A method of extracting a watermark from watermarked data as set forth in claim 23, where said error correction is Reed Solomon error correction.

25. A method for inserting a watermark signal into data to be watermarked comprising the steps of:

dividing data to be watermarked into a plurality of subregions;

dividing a watermark signal into a plurality of subwatermarks where portions of the watermark are contained in more than one subwatermark; and

inserting said plurality of subwatermarks into said plurality of subregions.

26. A method for inserting a watermark signal into data to be watermarked as set forth in claim 25, where each subwatermark is inserted into a respective subregion, so that each subregion contains at least one subwatermark.

27. A method for extracting a watermark signal from watermarked data comprising the steps of:

receiving a plurality of subregions of watermark data;

extracting a subwatermark from each subregion of said plurality of subregions; and

combining and averaging the subwatermarks extracted from all the subregions to obtain a signal commensurate with the watermark signal.

28. A method for extracting a watermark signal from watermarked data as set forth in claim 27, further comprising the steps of:

dividing the signal commensurate with the watermark signal into a plurality of symbol signals;

correlating each symbol signal with a set of predefined signals;

determining which predefined signal best corresponds to each symbol signal; and

combining the best corresponding predetermined signals to generate the watermark signal.