Method and apparatus for fragile watermarking

• US 7,489,797 B2
• Filed: 06/28/2004
• Issued: 02/10/2009
• Est. Priority Date: 08/08/2003
• Status: Active Grant

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Izquierdo, Ebroul
• Primary Examiner(s): Johns; Andrew W.
• Assistant Examiner(s): Bitar; Nancy
• Application Number:
  US10/567,735
• Publication Number:
  US 20070009134A1
• Time in Patent Office: 1,688 Days
• Field of Search: 382/100, 382/232, 382/240, 380/51, 380/54, 380/201, 380/210, 380/252, 380/287, 370522-529, 283/72, 283 74- 81, 283/85, 283/93, 283/113, 713/176, 713/186
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0042 Fragile watermarking, e.g. so as to detect tampering
• 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: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: Y10S 283/901 Concealed data
• CPC Class Codes: Y10S 283/902 Anti-photocopy

Abstract

A method of fragile watermarking is characterized by the step of generating at least a first ill-conditioned operator, said ill-conditioned operator being related to values extracted from an image or portion thereof A.

Claims

1. A method of fragile watermarking comprising:

generating at least a first ill-conditioned operator related to values extracted from an image or portion thereof A; and

replacing a non-zero singular value of a singular value matrix S_A of an image or portion thereof A, with a solution to a linear equation comprising the ill-conditioned operator, wherein the non-zero singular value to be replaced is the smallest non-zero singular value S_r(A) in a singular value matrix S_A of rank r.

2. A method of fragile watermarking according to claim 1 wherein the ill-conditioned operator is generated by altering a value to increase the operator'"'"'s condition number.

3. A method of fragile watermarking according to claim 1, wherein a non-zero singular value of a single value matrix S_W of a watermark pattern or portion thereof W is replaced, such that said replacement increases the condition number of the singular value matrix S_W of the watermark pattern or portion thereof W, wherein the non-zero singular value to be replaced is the smallest non-zero singular value S_t(W) in a singular value matrix S_W of rank t.

4. A method of fragile watermarking according to claim 3, wherein a replacement non-zero singular value of singular value matrix S_W of a watermark or portion thereof W is calculated by calculating substantially the following equation part:

s_t(W)=ε

,

where ε

is a small positive real number that increases the condition number of the singular value matrix S_W.

5. A method of fragile watermarking according to claim 1, wherein the step of generating at least a first ill-conditioned operator comprises calculating substantially the following equation part:

B=Â

Ŵ

,

where Ŵ

is substantially constructed according to Ŵ

=U_WŜ

_WV_W^T, Ŝ

_W comprising at least one altered singular value s_t(W)=ε

, and such that B forms a parametric family of matrices B(ŝ

_r)=Â

(ŝ

_r)Ŵ

for possible values of ŝ

_r(A).

6. A method of fragile watermarking according to claim 5, wherein ŝ

_r(A) is determined by an L₂-norm solution of the at least squares problem

7. A method of fragile watermarking according to claim 1, wherein the replacement non-zero singular value of singular value matrix A is calculated by calculating substantially the following equation part:

8. A method of fragile watermarking according to claim 7, wherein ŝ

_r(A) further satisfies

ŝ

(A)= s_r(A)ε

[max (eps, s_r(A)−

δ

), s_r(A)+δ

], s_r(A)+δ

]=[H₀, H₁], where δ

is a distortion control and eps is machine precision, such that the step of calculating the replacement non-zero singular value comprises calculating substantially the following equation part;

9. A method of fragile watermarking according to claim 8, wherein for a sequential watermarking process comprising the watermarking of portion A^(k) after the watermarking of portion A^(k−

1), k=1, . . . , L of L portions, then the step of calculating b^(k) for portion A^(k) comprises calculating substantially the following equation part;

10. A method of fragile watermarking according to claim 1, wherein a watermarked image or portion thereof Â

comprises calculating substantially the following equation part;

Â

=U_AŜ

_AV_A^T

where Ŝ

_A comprises at least one replaced singular value, U_A and V_A being left and right singular matrices.

11. A method of fragile watermarking according to claim 1, wherein a watermark pattern or portion thereof W is generated by a pseudo-random generator seeded by a key K of predetermined value.

12. A method of fragile watermarking according to claim 11, wherein the watermark pattern or portion thereof W is generated by a pseudo-random generator seeded by a key K of predetermined value, combined with either a single or repeated instance of a logo.

13. A method of fragile watermarking according to claim 1, comprising the following steps:

i. generating a K-dependent watermark pattern W from Ω

, or recalling a pre-existing one;

ii. constructing a parametric family of matrices B(ŝ

_r);

iii. estimating a unique parameter s_r(A), that minimizes the expression

14. A method of fragile watermarking according to claim 1, comprising the following steps:

i. generating a K-dependent watermark pattern W from Ω

, or recalling a pre-existing one;

ii. constructing a parametric family of matrices B(ŝ

_r);

iii. estimating a unique parameter

s(A)ε

[max(eps, s_r(A)−

δ

), s_r(A)+δ

]=[H₀, H₁], that minimizes the expression;

15. A method of verifying a fragile watermark comprising:

generating at least a first ill-conditioned operator by altering a value to increase its condition number, said ill-conditioned operator being related to values extracted from a received image or portion thereof A*; and

calculating a solution to the least squares problem

16. A method of verifying a fragile watermark according to claim 15, wherein a positive square-root N* of the L₂-norm solution of the least squares problem

17. A method of verifying a fragile watermark according to claim 16, wherein the value N* is calculated by calculating substantially the following equation part: