| Full Text |
FIELD OF THE INVENTION
The invention relates to a method of detecting a watermark in an information
signal that has possibly been watermarked by modifying values of said information signal in
accordance with (temporally or spatially) corresponding values of a watermark pattern. The
invention also relates to an arrangement for detecting a watermark.
BACKGROUND OF THE INVENTION
A prior art method as defined in the opening paragraph is disclosed in
International Patent Application WO-A-98/03014. The watermark is detected by computing
the correlation of the suspect information signal with an applied watermark pattern, and
comparing the correlation with a predetermined threshold. If the correlation is larger than the
threshold, the watermark is said to be present, otherwise it is said to be absent.
OBJECT AND SUMMARY OF THE INVENTION
It is an object of the invention to provide a suitable criterion for setting the .
threshold.
To this end, the invention provides a method of detecting a given watermark in
an information signal, comprising the steps of: computing the correlation of said watermark
and said information signal for a plurality of positions of said watermark with respect to said
information signal; and detecting whether at least one of the respective correlation values
exceeds a given threshold; characterized in that the method comprises the step of determining
the standard deviation of the respective correlation values, wherein said given threshold is a
given multiple of said standard deviation.
The invention exploits the insight that watermark detectors need to compute the
correlation value for a plurality of (temporal or spatial) positions of the watermark with respect
to the information signal (for example, an image) in practice, because the position of the-
watermark with respect to image is not absolutely known and/or information is embedded in
shifts of one or more watermark patterns. The detection thus yields a series of correlation
values, and it is the occurrence of relative peaks in such a series which is of interest rather than
absolute correlation values.
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 shows schematically an arrangement for embedding a watermark in a
signal.
Figs. 2 and 3 show diagrams to illustrate the operation of the embedder which is
shown in Fig. 1.
Fig. 4 shows schematically an arrangement for detecting the embedded
watermark.
Figs. 5, 6A and 6B show diagrams to illustrate the operation of the detector
which is shown in Fig. 4.
Fig. 7 shows a device for playing back a video bit stream with an embedded
watermark.
Fig. 8 shows schematically a preferred embodiment of the arrangement for
detecting the embedded watermark.
Figs. 9A and 9B show diagrams to illustrate the operation of the detector which
is shown in Fig. 8.
Fig. 10 shows schematically a further embodiment of the arrangement for
detecting the embedded watermark.
DESCRIPTION OF PREFERRED EMBODIMENTS
For the sake of convenience, the watermarking scheme in accordance with the
invention will be described as a system for attaching invisible labels to video contents but the
teachings can obviously be applied to any other contents, including audio and multimedia. We
will hereinafter often refer to this method as JAWS (Just Another Watermarking System).
Fig. 1 shows a practical embodiment of the watermark embedder to provide
background information. The embeddcr comprises an image source 11 which generates an
image P, and an adder 12 which adds a watermark W to the image P. The watermark W is a
noise pattern having the same size as the image, e.g. N, pixels horizontally and N2 pixels
vertically. The watermark W represents a key K, i.e. a multi-bit code which is to be retrieved
at the receiving end.
To avoid that the watermark detection process needs to search the watermark W
over the large N,xN2 space, the watermark is generated by repeating, and if necessary
truncating, smaller units called "tiles" W(K) over the extent of the image. This "tiling"
operation (15) is illustrated in Fig. 2. The tiles W(K) have a fixed size MxM. The tile size M
should not be too small: smaller M implies more symmetry in W(K) and therefore a larger
security risk. On the other hand M should not be too large: a large value of M implies a large
search space for the detector and therefore a large complexity. In JAWS we have chosen
M=128 as a reasonable compromise.
Then, a local depth map or visibility mask ?(P) is computed (16). At each pixel
position,?(P) provides a measure for the visibility of additive noise. The map ?(P) is
constructed to have an average value equal to 1. The extended sequence W(K) is subsequently
modulated (17) with ?(P), i.e. the value of the tiled watermark W(K) at each position is
multiplied by the visibility value of ?(P) at that position. The resulting noise sequence W(K,P)
is therefore dependent on both the key K and the image content of P. We refer to W(K,P) as an
adaptive watermark as it adapts to the image P.
Finally, the strength of the final watermark is determined by a global depth
parameter d which provides a global scaling (18) of W(K,P). A large value of d corresponds to
a robust but possibly visible watermark. A small value corresponds to an almost imperceptible
but weak watermark. The actual choice of d will be a compromise between the robustness and
perceptibility requirements. The watermarked image Q is obtained by adding (12)
W=dxW(K,P) to P, rounding to integer pixel values and clipping to the allowed pixel value
range.
In order to embed the multi-bit code K in the watermark W, every tile W(K) is
built up from a limited set of uncorrelated basic or primitive tiles {W,..Wn} and shifted
versions thereof, in accordance with
where "shift(W,,k,)" represents a spatial shift of a basic M*M tile W( over a vector k, with
cyclic wrap around. The signs se (-1 ,+1} and the shifts k depend on the key K via an encoding
function E (13). It is the task of the detector to reconstruct K after retrieving the signs si and
the shifts ki. Note that each basic tile Wf may occur several times. In Fig. 1, the encoder 13
generates W(K)=W1+W2-W2" where W2" is a shifted version of W2. Fig. 3 illustrates this
operation.
Fig. 4 shows a schematic diagram of the watermark detector in accordance with
the invention. The watermark detector receives possibly watermarked images Q. Watermark
detection in JAWS is not done for every single frame, but for groups of frames. By
accumulating (21) a number of frames the statistics of detection is improved and therefore also
the reliability of detection. The accumulated frames are subsequently partitioned (22) into
blocks of size MxM (M=128) and all the blocks are stacked (23) in a buffer q of size MxM.
This operation is known as folding. Fig. 5 illustrates this operation of folding.
The next step in the detection process is to assert the presence in buffer q of a
particular noise pattern. To detect whether or not the buffer q includes a particular watermark
pattern W, the buffer contents and said watermark pattern are subjected to correlation.
Computing the correlation of a suspect information signal q with a watermark pattern w
comprises computing the inner product d= of the information signal values and the
corresponding values of the watermark pattern. For a one-dimensional information signal
q={qn} and watermark pattern w={wn}, this can be written in mathematical notation as:
For the two-dimensional MxM image q={qii} and watermark pattern W={Wij}, the inner
product is:
In principle, the vector kf by which a tile Wi has been shifted can be found by
successively applying Wi with different vectors k to the detector, and determining for which k
the correlation is maximal. However, this brute force searching algorithm is time consuming.
Moreover, the image Q may have undergone various forms of processing (such as translation
or cropping) prior to the watermark detection, so that the detector does not know the spatial
location of the basic watermark pattern Wi with respect to the image Q.
Instead of brute force searching JAWS exploits the structure of the patterns
W(K). The buffer q is examined for the presence of these primitive patterns, their signs and
shifts. The correlation dk of an image q and a primitive pattern w being shifted by a vector k
(kx pixels horizontally and ky pixels vertically is:
The correlation values dk for all possible shift vectors k of a basic pattern Wf are
simultaneously computed using the Fast Fourier transform. As shown in Fig. 4, both the
contents of buffer q and the basic watermark pattern W; are subjected to a Fast Fourier
Transform (FFT) in transform circuits 24 and 25, respectively. These operatioris yield:
i
where q and w are sets of complex numbers.
Computing the correlation is similar to computing the convolution of q and the
conjugate of Wi. In the transform domain, this corresponds to:
where the symbol ® denotes pointwise multiplication and conj() denotes inverting the sign of
the imaginary part of the argument. In Fig. 4, the conjugation of w is carried out by a
conjugation circuit 26, and the pointwise multiplication is carried out by a multiplier 27. The
set of correlation values d={dk} is now obtained by inverse Fourier transforming the result of
said multiplication:
which is carried out in Fig. 4 by an inverse FFT circuit 28. The watermark pattern Wi is
detected to be present if a correlation value dk is larger than a given threshold.
Fig. 6A shows a graph of correlation values dk if the presence of watermark
pattern W, (see Figs. 1 and 3) in image Q is being checked. The peak 61 indicates that W, is
indeed found. The position (0,0) of this peak indicates that the pattern W, applied to the
detector happens to have the same spatial position with respect to the image Q as the pattern
W, applied to the embedder. Fig. 6B shows the graph of correlation values if watermark
pattern W2 is applied to the detector. Two peaks are now found. The positive peak 62 at (0,0)
denotes the presence of watermark W,, the negative peak 63 at (48,80) denotes the presence of
watermark -W2". The relative position of the latter peak 63 with respect to peak 62 (or, what is
similar, peak 61) reveals the relative position (in pixels) of W," with respect to W2, i.e. the
shift vector k. The embedded data K is derived from the vectors thus found.
The embedded information may identify, for example, the copy-right holder or
a description of the content. In DVD copy-protection, it allows material to be labeled as "copy
once", "never copy", "no restriction", "copy no more", etc. Fig. 7 shows a DVD drive for
playing back an MPEG bitstream which is recorded on a disc 71. The recorded signal is
applied to an output terminal 73 via a switch 72. The output terminal is connected to an
external MPEG decoder and display device (not shown). It is assumed that the DVD drive may
not play back video signals with a predetermined embedded watermark, unless other
conditions are fulfilled which are not relevant to the invention. For example, watermarked
signals may only be played back if the disc 71 includes a given "wobble" key. In order to
detect the watermark, the DVD drive comprises a watermark detector 74 as described above.
The detector receives the recorded signal and controls the switch 72 in response to whether or
not the watermark is detected.
The Fourier coefficients d are complex numbers, that is, they have a real part
and an imaginary part, or a magnitude and a phase. The inventors have found that the
reliability of the detector is significantly improved if the magnitude information is thrown
away and the phase is considered only. Fig. 8 shows a preferred embodiment of the detector"s
correlation circuitry. The embodiment differs from the one shown in Fig. 4 in that a magnitude
normalization circuit 30 has been inserted between the multiplier 27 and the inverse Fourier
Transform circuit 28. The operation of the normalization circuit comprises pointwise dividing
each coefficient by its magnitude. In mathematical notation:
0)
where F denotes pointwise division and abs() denotes:
(2)
where R() and I() denote the real and imaginary part of the argument, respectively.
Said normalization of magnitudes is referred to as Symmetrical Phase Only
Matched Filtering (SPOMF). Figs. 9A and 9B illustrate the effect of SPOMF correlation. More
particularly, Fig. 9A shows the correlation values dk when using linear correlation, i.e. without
the magnitude normalization circuit 30. The correlation value d00, expressed in units of
standard deviation of the whole matrix, amounts to 9.79. Fig. 913 shows the correlation values
when using SPOMF correlation. The correlation value d00, is now 62.77 times the standard
deviation. It will be appreciated that the peak in Fig. 9B can more reliably be detected than the
peak in Fig. 9A.
Because normalizing the magnitudes of d is equivalent to normalizing the
magnitudes of both q and w, the normalization circuit 30 in Fig. 8 may be replaced by two
normalization circuits after the FFT circuits 24 and 25. However, the embedded watermark
will already have a reasonably white (flat) frequency spectrum because it is a pseudo-random
noise pattern in practice, in which each sample is independently and identically drawn from a •
normal distribution. In view hereof, normalizing the magnitude of the information signal only
has been found to suffice. Fig. 10 shows such an embodiment. The magnitude normalization
circuit 30 is now located between the FFT circuit 24 and the multiplier 27. In this embodiment,
the magnitudes of d are not exactly, but substantially, the same.
It should further be noted that the FFT and the conjugation of the applied
watermark Wi (c.f. circuits 25 and 26, respectively, in Figs. 4, 8 and 10), as well as the
optional normalization of the magnitudes of w, can be pre-computed and stored in a memory.
This invention addresses the aspect of determining criteria for correlation values
dk to be peaks. To this end we consider the decision variable dk as a stochastic variable. A way
of formulating "largeness" of dk is by comparison to the standard deviation ad of d. If a
particular measurement dk is larger than Tad for some suitably chosen threshold T, then we say
that dk is an statistical outlier. This will be interpreted as the presence of a watermark.
Experiments have shown that d can be modeled to a very good approximation
as a normal distribution. This holds both for linear correlations as well as for SPOMF
correlations. This allows us to associate false positive rates to the threshold T. In particular the
probability that a measurement dk is larger than Tsd can be computed as erfc(T), where erfc is
the error function
[
A threshold value T=5 is generally considered to be safe and corresponds with a false alarm
probability of 2.8x10-7.
Each of the values dk can be seen as the correlation of a fixed watermark {w/j}
with an image qk where qk is a shifted version of q (with cyclic wrap around). Therefore we
can view the matrix dk as a matrix of instantiations of the stochastic process d. Experiments
have shown that d can be modeled to a very good approximation as a normal distribution. This
holds both for linear correlations as well as for SPOMF correlations. This allows us to
associate false positive rates to the threshold T. In particular the p|pbability that a
measurement dk is larger than Tsd can be computed as erfc(T), where erfc is the error function
A threshold value T=5 is generally considered to be safe and corresponds with a false alarm .
. probability of 2.8x10-7. The actual false alarm rate is orders of magnitudes lower due to the
way watermark information K is encoded as a combination of signs and peak positions. The
probability that for T=5 a legal combination of peaks and signs occurs by chance is
vanishingly small.
The actual false alarm rate is orders of magnitudes lower due to the way watermark
information K is encoded as a combination of signs and peak positions. The probability that
for T=5 a legal combination of peaks and signs occurs by chance is vanishingly small.
For linear correlations as described above, it can be shown that sd can be
directly expressed in terms of the standard deviation sq of the image q and the standard
deviation sw of the watermark w:
In practice, this implies that sd may be assumed to have a fixed predetermined value.
The value of sd can also be estimated directly from the matrix {dk}, viz.
The latter method of computing sd is particularly useful when the correlation values are
computed using SPOMF because for SPOMF correlation there are no easy theoretical
formulas for sd. With SPOMF detection, peak heights in {dk} are compared with this measured
standard deviation and judged relevant if larger than 5sd.
In summary, a method and arrangement for detecting a watermark in an
information signal is disclosed. The method comprises the steps of computing (24-28,30) the
correlation (dk) of said watermark (Wj) and said information signal (e.g. an image Q) for a
plurality of positions (k) of said watermark with respect to said information signal, and
detecting (29) whether at least one of the respective correlation values exceeds a given
threshold. The step of detecting (29) comprises determining the standard deviation (sd) of the
respective correlation values (dk), and setting the threshold to a given multiple (T) of said
standard deviation. The multiple (T) is derived form a desired false alarm rate (watermark
detected when there is none, or no watermark detected when there is one).
We claim:-
1. A method of detecting a given watermark (w) in an information signal (q)
comprising the steps of :
- computing the correlation (dk) of said watermark and said
information signal for a plurality of positions (k) of said
watermark with respect to said information signal;
- detecting whether at least one of the respective correlation
values exceeds a given threshold;
characterized in that the method comprises the step of determining the standard
deviation (sd) of the respective correlation values (dk), wherein said given threshold is a
given multiple (T) of said standard deviation.
2. An arrangement for carrying out the method as claimed in claim 1
comprising:
- means (24-28) for computing the correlation (dk) of the
watermark (w) and the information signal (q) for a plurality of
positions (k) of said watermark with respect to said information
signal;
- means (29) for detecting whether at least one of the respective
correlation values exceeds a given threshold;
characterized in that said detecting means include means for determining the standard
deviation (sd) of the respective correlation values, wherein said given threshold is a
given multiple (T) of said standard deviation.
A method and arrangement for detecting a watermark in an
information signal is disclosed. The method comprises the steps of computing
(24-28,30) the correlation (Dk) of said watermark (Wi) and said information
signal (e.g. an image Q) for a plurality of positions (k) of said watermark with
respect to said information signal, and detecting (29) whether at least one of the
respective correlation values exceeds a given threshold. The step of detecting
(29) comprises determining the standard deviation (sd) of the respective
correlation values (dk), and setting the threshold to a given multiple (T) of said
standard deviation. The multiple (T) is derived from a desired false alarm rate
(watermark detected when there is none, or no watermark detected when there
is one). |