Method and apparatus for wavelet-based digital watermarking

• US 6,359,998 B1
• Filed: 04/23/1998
• Issued: 03/19/2002
• Est. Priority Date: 04/23/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Cooklev, Todor
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US09/065,815
• Time in Patent Office: 1,426 Days
• Field of Search: 382/100, 382/101, 382/118, 382/119, 382/120, 382/212, 382/232, 382/248, 382/249, 382/250, 382/276, 382/280, 382/284, 382/293, 382/296, 380/54, 380/210, 380/252, 380/287, 713/176
• US Class Current: 382/100
• CPC Class Codes: A61F 2/44 for the spine, e.g. vertebrae, spinal discs
• CPC Class Codes: A61F 2002/30001 Additional features of subject-matter classified in A61F2/28, A61F2/30 and subgroups thereof
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain

Abstract

The disclosed watermarking method utilizes a transform technique for inserting an imperceptible digital watermark into digital data that is strongly resistant to unauthorized detection and decoding. Methods for embedding a watermark that is sufficiently robust to lossy compression and other image processing operations such as rescaling are also provided. The watermarking principle is based on wavelet transforms where the coefficients of the filters have binary values, and are thus very attractive for practical realization. The wavelet filters utilize complimentary polynomials and implement non-regular wavelet transforms upon which the digital watermark is inserted. Following the inverse transformation process, the digital watermark is spread across multiple frequencies of the original digital data thereby reducing the impact of signal processing operations such as compression or other frequency filtering based operations. Additional embodiments employing complimentary matrix polynomials which are closely related to multifilter banks are also provided.

Claims

1. A method for watermarking digital data, comprising the steps of:

a) forward transforming said digital data into transformed data using a non-regular wavelet transform having non-continuous functions;

b) inserting a digital watermark throughout the entire frequency domain on said transformed data; and

c) inverse transforming said transformed data having said digital watermark embedded therein.

2. The method for watermarking digital data as recited in claim 1, wherein said method further comprises the step of prior to said forward transforming step, partitioning said digital data into blocks such that the amplitude of said digital data within each block exhibits comparable magnitudes.

3. The method for watermarking digital data as recited in claim 1, wherein said forward transforming step further comprises the step of generating a subband tree as a complete subband tree.

4. The method for watermarking digital data as recited in claim 1, wherein said forward transforming step further comprises the step of generating a subband tree that is pruned according to a predetermined pattern.

5. The method for watermarking digital data as recited in claim 1, wherein said forward transforming said digital data into transformed data using a non-regular wavelet transform step, further comprises the step of selecting said non-regular wavelet transform as a orthogonal circular wavelet transform wherein filter coefficients are of the values of either 1 or −

1.

6. The method for watermarking digital data as recited in claim 1, wherein said forward transforming said digital data into transformed data using a non-regular wavelet transform step, further comprises the step of selecting said non-regular wavelet transform as a multiwavelet transform wherein filter coefficients are of the values of either 1 or −

1.

7. A method for designating and determining the origin of digital data through the use of a digital watermark, comprising the steps of:

a) generating said digital watermark for uniquely designating said origin of said digital data;

b) embedding into said digital data said digital watermark throughout the entire frequency domain including the steps of;

i. forward transforming said digital data into transformed data using a non-regular wavelet transform having non-continuous functions;

i. inserting said digital watermark on said transformed data; and

i. inverse transforming said transformed data having said digital watermark embedded therein to form watermarked digital data such that said digital watermark remains resilient to lossy compression of said watermarked digital data; and

c) upon receipt of unknown digital data, processing said unknown digital data to verify said unknown digital data as being said watermarked digital data having said digital watermark embedded therein.

8. The method for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 7, wherein said generating step further comprises the step of generating a predetermined pattern for use in pruning a subband tree for said non-regular wavelet transform.

9. The method for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 7, wherein said forward transforming said digital data into transformed data using said non-regular wavelet transform step, further comprises the step of selecting said non-regular wavelet transform as a orthogonal circular wavelet transform wherein filter coefficients are of the values of either 1 or −

1.

10. The method for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 7, wherein said forward transforming said digital data into transformed data using a non-regular wavelet transform step, further comprises the step of selecting said non-regular wavelet transform as a multiwavelet transform wherein filter coefficients are of the values of either 1 or −

1.

11. The method for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 7, further comprising the step of following said embedding step, lossy compressing said watermarked digital data having said digital watermark embedded therein.

12. The method for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 11, wherein said lossy compressing step comprises the step of lossy compressing using JPEG compression said watermarked digital data having said digital watermark embedded therein.

13. A method for verifying the origin of digital data, comprising the steps of:

a) spreading a frequency response of said digital data in a transform domain by forward transforming said digital data with a non-regular circular wavelet transform having non-continuous functions to provide spreading of said digital data to form transformed digital data;

b) modulating coefficients of said transformed digital data with a digital watermark throughout the entire frequency domain on said transformed data to form watermarked transformed digital data;

c) despreading said frequency response of said watermarked transformed digital data to form watermarked digital data; and

d) upon receipt of unknown digital data, determining if said unknown digital data has said digital watermark embedded therein.

14. The method for verifying the origin of digital data, as recited in claim 13, wherein said modulating coefficients of said transformed digital data step comprises the step of inserting said digital watermark onto said coefficients of said transformed digital data.

15. The method for verifying the origin of digital data, as recited in claim 13, wherein said spreading a frequency response step further comprises the step of generating a subband tree that is pruned according to a predetermined pattern.

16. The method for verifying the origin of digital data, as recited in claim 13, further comprising the step of storing for use in said determining step a copy of said digital data and a copy of said digital watermark.

17. The method for verifying the origin of digital data, as recited in claim 16, wherein said determining if said unknown digital data has said digital watermark embedded therein step comprises the steps of:

a) forward wavelet transforming said watermarked digital data to obtain watermarked digital data coefficients;

b) forward wavelet transforming said copy of said digital data to obtain digital data coefficients;

c) comparing a difference between said watermarked digital data coefficients and said digital data coefficients with said copy of said digital watermark; and

d) when said difference as compared with said copy of said digital watermark is within a verification threshold, detecting said digital watermark within said unknown digital data.

18. A computer-readable medium having computer-executable instructions for designating and determining the origin of digital data through the use of a digital watermark, said computer executable instructions for performing the steps of:

a) generating said digital watermark for uniquely designating said origin of said digital data;

b) embedding into said digital data said digital watermark throughout the entire frequency domain including the steps of;

i. forward transforming said digital data into transformed data using a non-regular wavelet transform having non-continuous functions;

i. inserting said digital watermark on said transformed data; and

i. inverse transforming said transformed data having said digital watermark embedded therein to form watermarked digital data such that said digital watermark remains resilient to lossy compression of said watermarked digital data; and

c) upon receipt of unknown digital data, processing said unknown digital data to verify said unknown digital data as being said watermarked digital data having said digital watermark embedded therein.

19. The computer-readable medium having computer-executable instructions for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 18, wherein said computer-executable instructions for performing said generating step further comprise computer-executable instructions for performing the step of generating a predetermined pattern for use in pruning a subband tree for said wavelet transform.

20. The computer-readable medium having computer-executable instructions for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 18, wherein said computer-executable instructions for forward transforming said digital data into transformed data using a non-regular wavelet transform step, further comprise computer-executable instructions for performing the step of selecting said non-regular wavelet transform as a orthogonal circular wavelet transform wherein filter coefficients are of the values of either 1 or −

1.

21. The computer-readable medium having computer-executable instructions for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 18, wherein said computer-executable instructions for forward transforming said digital data into transformed data using a non-regular wavelet transform step, further comprise computer-executable instructions for performing the step of selecting said non-regular wavelet transform as a multiwavelet transform wherein filter coefficients are of the values of either 1 or −

1.

22. The computer-readable medium having computer-executable instructions for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 18, wherein said computer-executable instructions further comprise computer-executable instructions following said embedding step for performing the step of lossy compressing said watermarked digital data having said digital watermark embedded therein.

23. The computer-readable medium having computer-executable instructions for designating and determining the origin of digital data through the use of a digital watermark, as recited in claim 22, wherein said computer-executable instructions for performing said lossy compressing step comprise computer-executable instructions for performing the step of lossy compressing using JPEG compression said watermarked digital data having said digital watermark embedded therein.