Watermarking with cone-forest detection regions
In a watermarking system, an embedder embeds one of several alternative watermark patterns that represent the source message using side information to improve robustness. A detector uses normalized correlation to test all of the patterns, indicating that the source message is present if any one of the patterns is detected. The detection process results in a detection region that is the union of several disjoint cones, or a cone-forest, in media space.
1. A method of embedding a source message as a watermark in a cover Work comprising the steps of:
identifying a subset of a one-to-many code where each code vector in the subset corresponds to the source message
applying an extraction process to a cover Work to obtain an extracted vector;
searching the subset to identify the code vector that yields the highest detection value when compared against the extracted vector;
creating a mixed vector that is perceptually close to the extracted vector with respect to the cover Work, and that obtains a predetermined robustness value when the mixed vector is compared against the identified code vector; and
applying an inverse extraction process to the mixed vector and to the cover Work to create a watermarked Work.
2. The method of embedding as set forth in claim 1 , wherein the cover Work is an image.
3. The method of embedding as set forth in claim 1 , wherein the cover Work is an audio clip.
4. The method of embedding as set forth in claim 1 , wherein said applying an extraction process is performed by computing the linear correlation between the cover Work and each of a set of reference patterns, each such correlation yielding one component of the extracted vector.
5. The method of embedding as set forth in claim 4 , wherein said applying an inverse extraction process comprises scaling each of the reference patterns by the difference between the corresponding elements of the mixed vector and the extracted vector to obtain a plurality of scaled reference patterns; and
adding the scaled reference patterns to the cover Work.
6. The method of embedding as set forth in claim 5 , wherein the reference patterns consist of 0's, 1's, and −1's.
7. The method of embedding as set forth in claim 5 , wherein the reference patterns are low frequency patterns.
8. The method of embedding as set forth in claim 1 , wherein each code vector is drawn from an independent, identically-distributed Gaussian distribution.
9. The method of embedding as set forth in claim 1 , wherein the detection value is obtained by normalized correlation.
10. The method of embedding as set forth in claim 1 , wherein the detection value is obtained by correlation coefficient.
11. The method of embedding as set forth in claim 1 , wherein the robustness value (r 2 ) is obtained by the equation
r
2
=
(
v
·
w
T
w
)
-
v
·
v
,
where v is the mixed vector, w is a code vector, and T is a constant.
12. The method of embedding as set forth in claim 11 , wherein the value of T depends on the quantity of code vectors in the subset.
13. The method of embedding as set forth in claim 1 , wherein said searching is performed by exhaustive search.
14. The method of embedding as set forth in claim 1 , wherein said creating a mixed vector is performed by minimizing the Euclidian distance between the mixed vector and the extracted vector, while maintaining the predetermined robustness value unchanged.
15. The method of embedding as set forth in claim 14 , wherein said minimizing is performed by exhaustive search.
16. The method of embedding of claim 15 , wherein the exhaustive search comprises the steps of
identifying an X, Y plane by letting
X
=
w
w
Y
=
v
-
X
(
v
·
X
)
v
-
X
(
v
·
X
)
;
projecting the code vector w and the extracted vector v onto the X, Y plane by letting
x w =1 y w =0
x v =v·X y v =v·Y;
stepping through several values of y between 0 and y v , letting
x
=
T
2
(
r
2
-
y
2
)
1
-
T
2
and identifying the such x, y pair x m , y m with minimum Euclidian distance between x m , y m and x v , y v ; and
obtaining the mixed vector v m by computing
v m =x m X+y m Y.
17. A method of detecting a message in a Work comprising the steps of
applying an extraction process to the Work to obtain an extracted vector;
searching a one-to-many code to find a code vector that yields the highest detection value when compared against the extracted vector; and
identifying a message which has a corresponding subset of the one-to-many code containing the found code vector.
18. The method of detecting as set forth in claim 17 , wherein the Work is an image.
19. The method of detecting of claim 17 , wherein the Work is an audio clip.
20. The method of detecting as set forth in claim 17 , wherein said extraction process is performed by computing the linear correlation between the Work and each pattern of a set of reference patterns, each such correlation yielding one component of the extracted vector.
21. The method of detecting as set forth in claim 20 , wherein the reference patterns consist of 0's, 1's, and −1's.
22. The method of detecting as set forth in claim 20 , wherein the reference patterns are low frequency patterns.
23. The method of detecting as set forth in claim 17 , wherein each watermark pattern in the one-to-many code is drawn from an independent, identically-distributed Gaussian distribution.
24. The method of detecting as set forth in claim 17 , wherein the detection value is obtained by normalized correlation.
25. The method of detecting as set forth in claim 17 , wherein the detection value is obtained by correlation coefficient.
26. The method of detecting as set forth in claim 17 , wherein said searching is performed by exhaustive search.
27. The method of detecting as set forth in claim 17 , further comprising the step of reporting that the Work contains the message if the highest detection value is at least equal to a predetermined detection threshold, and reporting that the Work does not contain a message if the highest detection value is below a predetermined detection threshold.
28. The method of detecting as set forth in claim 27 , wherein the Work is an image.
29. The method of detecting of claim 27 , wherein the Work is an audio clip.
30. The method of detecting as set forth in claim 27 , wherein said extraction process is performed by computing the linear correlation between the Work and each pattern of a set of reference patterns, each such correlation yielding one component of the extracted vector.
31. The method of detecting as set forth in claim 30 , wherein the reference patterns consist of 0's, 1's, and −1's.
32. The method of detecting as set forth in claim 30 , wherein the reference patterns are low frequency patterns.
33. The method of detecting as set forth in claim 27 , wherein each watermark pattern in the one-to-many code is drawn from an independent, identically-distributed Gaussian distribution.
34. The method of detecting as set forth in claim 27 , wherein the detection value is obtained by normalized correlation.
35. The method of detecting as set forth in claim 27 , wherein the detection value is obtained by correlation coefficient.
36. The method of detecting as set forth in claim 27 , wherein said searching is performed by exhaustive search.