JEI Letters

Comments on “Robust embedding of visual watermarks using discrete wavelet transform and singular value decomposition” and theoretical analysis

[+] Author Affiliations
Liang Xiao, Zhihui Wei

Naning University of Science and Technology, School of Computer Science of Technology, Nanjing 210094, China

Jianbing Ye

Naning University of Science and Technology, Taizhou Institute of Science and Technology, Taizhou 225300, China

J. Electron. Imaging. 17(4), 040501 (December 16, 2008). doi:10.1117/1.3041170
History: Received January 18, 2008; Revised October 09, 2008; Accepted October 21, 2008; Published December 16, 2008
Text Size: A A A

Open Access Open Access

It is shown that the watermarking algorithm presented in another paper [] has a very high probability of a false-positive answer and has its limitations in practice. Furthermore, the intrinsic reasons of the high false-alarm probability are as follows: the basis space of singular value decomposition is image content dependent, there is no one-to-one correspondence between singular value vector and image content, because singular value vectors have no information on the structure of image. Thus, the most important reason is a result of a false conception to insert watermark singular value vectors without information on the structure of the watermark. Finally, some examples are given to prove our results of theoretical analysis.

Figures in this Article

In Ref. 1, the authors proposed a robust embedding of visual watermarks using discrete wavelet transform (DWT) and singular value decomposition (SVD) and demonstrated its high robustness against image distortion. In this paper, we prove that such an algorithm has a very serious problem of a high false alarm probability. The same problem also exists in the SVD-based watermarking algorithm in Ref. 2.

For simplicity and convenience of computations in Ref. 1 and in this letter, it is assumed that the cover image matrix is a square matrix A and a watermark is represented as a matrix W.

Briefly, the algorithm works as follows.

(I) Watermark embedding

  1. Using DWT, decompose the cover image A into four subbands: LL, HL, LH, and HH.
  2. Apply SVD to each subband image asDisplay Formula
    1Aαk=UαkSαkVαkk=1,2,3,4,
    where k denotes LL, HL, LH, and HH bands, and λik,i=1,2,,n, are the singular values of Sαk.
  3. Apply SVD to the visual watermark asDisplay Formula
    2W=UwSwVwT,
    where λwi,i=1,,n are the singular values of Sw.
  4. Modify the singular values of the cover image in each subband with the singular values of the visual watermark asDisplay Formula
    3λi*k=λik+αkλwi,i=1,,nandk=1,2,3,4.
  5. Obtain the four sets of modified DWT coefficients asDisplay Formula
    4A*k=UαkSα*kVαkT,k=1,2,3,4andk=1,2,3,4.
  6. Apply the inverse DWT using the four sets of modified DWT coefficients to produce the watermarked cover image.

  1. Using DWT, decompose the cover image A into four subbands: LL, HL, LH, and HH.
  2. Apply SVD to each subband image asDisplay Formula
    1Aαk=UαkSαkVαkk=1,2,3,4,
    where k denotes LL, HL, LH, and HH bands, and λik,i=1,2,,n, are the singular values of Sαk.
  3. Apply SVD to the visual watermark asDisplay Formula
    2W=UwSwVwT,
    where λwi,i=1,,n are the singular values of Sw.
  4. Modify the singular values of the cover image in each subband with the singular values of the visual watermark asDisplay Formula
    3λi*k=λik+αkλwi,i=1,,nandk=1,2,3,4.
  5. Obtain the four sets of modified DWT coefficients asDisplay Formula
    4A*k=UαkSα*kVαkT,k=1,2,3,4andk=1,2,3,4.
  6. Apply the inverse DWT using the four sets of modified DWT coefficients to produce the watermarked cover image.

(II) Watermark extraction

  1. Using DWT, decompose the watermarked and possibly attacked cover image A* into four subbands: LL, HL, LH, and HH.
  2. Apply SVD to each subband image asDisplay Formula
    5A*k=UαkSα*kVαkT,k=1,2,3,4,,
    where k denotes the attacked LL, HL, LH, and HH bands.
  3. Extract the singular values from each subband asDisplay Formula
    6λwik=(λi*kλik)αk,i=1,nandk=1,2,3,4.
  4. Construct the four visual watermarks using the singular vectors asDisplay Formula
    7Wk=UWSWkVWT,k=1,2,3,4.,
    In the following, we will shown that the above watermarking algorithm has a very high probability of false positive answers.

  1. Using DWT, decompose the watermarked and possibly attacked cover image A* into four subbands: LL, HL, LH, and HH.
  2. Apply SVD to each subband image asDisplay Formula
    5A*k=UαkSα*kVαkT,k=1,2,3,4,,
    where k denotes the attacked LL, HL, LH, and HH bands.
  3. Extract the singular values from each subband asDisplay Formula
    6λwik=(λi*kλik)αk,i=1,nandk=1,2,3,4.
  4. Construct the four visual watermarks using the singular vectors asDisplay Formula
    7Wk=UWSWkVWT,k=1,2,3,4.,
    In the following, we will shown that the above watermarking algorithm has a very high probability of false positive answers.

To discuss the problem of the above algorithm, let us briefly list some properties of SVD.3

Mathematically, every r×c (rc, without loss of generality) the matrix A can always have the SVD as A=USVT where U=(u1,u2,ur), V=(v1,v2,vc), S=(D,0)T,D=diag(λ1,λ2λc), 0 is c×(rc) zero matrix, λi’s are the singular values in a nonincreasing order. Furthermore, assuming the rank of A to be k, we haveDisplay Formula

8A=λ1u1v1T+λ2u2v2T++λrukvkT.

Property 1. uivjT, i=1,2,,r,j=1,2,,c forms a set of orthogonal basis matrices for the space Rr×c and can be termed as basis images.

Property 2. When projecting A to the basis images uivjTi=1,2,,r,j=1,2,,c, we have: (i) the coefficients are all non-negative; (ii) the coefficients are λi in the basis images uivjTi=1,2,,k; and (iii) the coefficients are zeros in the basis images complement to those in 8.

Proving these properties is simple and can be omitted here. Property 1 defines the concept of basis images, and the leading basis images (those corresponding to leading singular values) capture the great variances in the image A itself. Property 2 further offers some characteristics of these basis images.

Now let us discuss the problem of the algorithm in Ref. 1. It is clear to see that the most significant step in this algorithm of watermark detection is 7. Moreover, please note that the matrices Uw, SWk, Vw are required in watermark extraction, and Uw, Vw are the side information in Ganic and Eskicioglu1 algorithm. Hence, no matter what kind of the attacked cover image A*, even one whose content is not the same as that of the original A, is selected, but the same private matrices Uw, Vw that are tightly connected with the original watermark W are used to recover the watermark image. If we use four random matrices S**k, k=1,2,3,4, with λ**>0,i=1,,n conducted as Eq. 7, then four matrices W**k=UWS**kVWT, k=1,2,3,4 will be generated. But W**k are visual and geometrically similar to the original W with overwhelming probability, because all the geometrical features of the watermark image W are contained in Uw, Vw. Moreover, according to the watermark embedding procedure (4), only the singular value vectors SW of watermark W are inserted, while the geometrical features of the watermark image W are not inserted. Hence, it is worthwhile to point out that not only is the watermark extraction algorithm problematic, but so is the watermark embedding algorithm. The intrinsic reasons for the serious problem with high probability of false positive answers are (i) the basis space of SVD is image content dependent, and (ii) there is no one-to-one correspondence between the singular value vector and watermark image.

In addition, there is important evidence for our conclusion, which is the research in Ref. 2, in which the authors show that singular values do not contain necessary information for face recognition, and all useful information is contained in orthogonal matrices of image SVD decomposition. It is interesting that the Ganic and Eskicioglu algorithm in Ref. 1 is an improved algorithm of the Liu and Tan SVD-basis watermarking method,4 and the difference is that the Liu and Tan method is a spatial method. Hence, the serious problem with high probability of false positive answers still exists, and the same discussion can be conducted as above.

To show our theoretical analysis, we will give two interesting examples in the following. Image “Lena” is used as the cover image A, and image “Cameraman” is used as watermark Wc and image “Peppers” is used as watermark Wp (as shown in Fig. 1).

In our experiments, the two watermarks are applied to the cover image, respectively, to obtain the watermarked images denoted by Awc and Awp according to the embedding procedure [see Fig. 2]. Obviously, according to Eq. 2, the SVD of the watermark Wc and Wp can be written as WP=UwpSwpVwpT and Wc=UwcSwcVwcT. In real DRM systems, we do not know that whether there is a watermark embedded or which watermark is embedded in the image Awc or Awp. Now we try to detect whether watermark Wp (“Peppers”) is embedded in the watermarked image Awc [with watermark Wc (“Cameraman”)] or detect whether watermark Wc (“Peppers”) is embedded in the watermarked image Awp [with watermark Wp (“Peppers”)].

Then, by following Ganic and Eskicioglu algorithm’s procedure,1 at the detector end, we will find the surprising experimental results.

  1. If Uwc,Vwc are applied to the watermarked image Awp, according to Eq. 7, then four “Cameraman” watermarks are extracted instead of the real embedded watermark “Peppers,” as illustrated by Fig. 2.
  2. If Uwp,Vwp are applied to the watermarked image Awc, according to Eq. 7, four “Peppers” watermarks are extracted instead of the real embedded watermark “Cameraman,” as illustrated by Figs. 2.

  1. If Uwc,Vwc are applied to the watermarked image Awp, according to Eq. 7, then four “Cameraman” watermarks are extracted instead of the real embedded watermark “Peppers,” as illustrated by Fig. 2.
  2. If Uwp,Vwp are applied to the watermarked image Awc, according to Eq. 7, four “Peppers” watermarks are extracted instead of the real embedded watermark “Cameraman,” as illustrated by Figs. 2.

Graphic Jump LocationF1 :

Three images are used for our experiments. (a) Cover image “Lena,” (b) watermark image “Cameraman,” and (c) watermark image “Peppers.”

Graphic Jump LocationF2 :

A counter example: (a) Real watermark image “Peppers,” (b) watermarked image embedded with “Peppers,” (c) extracted “Cameraman,” (d) real watermark image “Cameraman,” (e) watermarked image embedded with “Cameraman,” and (f) extracted “Peppers.”

Figure 3 shows another very interesting counter example. A noise image whose elements are realizations of integer valued random variable, uniform distributed in interval [0; 255] are used as the possibly attacked cover image A*. When Uwp,Vwp are applied to the watermarked image A*, we can also recover four “Cameraman” watermarks.

Graphic Jump LocationF3 :

(a) Uniformly distributed random image and (b) estimate of watermark obtained from (a).

Because the watermark embedding algorithm only modifies singular values, but the basis images are not inserted with any information. As we know, the modification of singular values only changes the luminance of images. Hence, the contrast comparison function (CCF) is used to measure the difference between original watermark and the recovery watermarks, which takes a similar form,5Display Formula

9CCF(u,v)=2σww*σw2+σw*2,
where σw,σw* are the variance of image matrix W,W*σww*=1MNi=1Mj=1N(wijμw)(vijμw*).

According to Ref. 5, the CCF value provides a quantitative measurement of image structural similarity without considering the luminance factors. After computation, The CCF values between four “Peppers” watermarks estimated from Fig. 3 and original “peppers” shown in Fig. 1 are 0.89, 0.82, 0.82, and 0.81. In the Ref. 1, Pearson’s correlation between the original vector of singular values and extracted vector of singular values are used to subjective evaluate the robustness of watermarking algorithm. Pearson’s correlation shows the degree of linear relationship between two variables. We also use Pearson’s correlation to compute the coefficients, it is surprising that the Pearson’s correlation values between four “peppers” watermarks estimated from Fig. 3 and original “peppers” shown in Fig. 1 are 0.87, 0.79, 0.77, and 0.71.These facts are powerful to support our comment results.

According to the examples presented above, it is clear that the watermarking algorithm presented in Ref 1 has a very high probability of false positive answers; hence, the algorithm has rather huge limitations to protect the image’s rightful ownership in practice.

We thank the anonymous reviewers for their constructive comments that enhance this paper. This work is supported by the Natural Science Foundation of China under Grants No. 60672074 and No. 60802039, the National Research Foundation for the Post Doctoral Program under Grants No. 20060390285 and No. 200601005B, and the Natural Science Foundation of Jiangsu Province of China under Grant No. BK20065569.

Ganic  E., and Eskicioglu  A. M., “ Robust embedding of visual watermarks using discrete wavelet transform and singular value decomposition. ,” J. Electron. Imaging.  1017-9909 14, (4 ), 043004  ((2005)).
Tian  Y., , Tan  T., , Wang  Y., , and Fang  Y., “ Do singular values contain information for face recognition. ,” Pattern Recogn..  0031-3203 36, , 649–655  ((2003)).
Golub  G. H., and Van Loan  C. F.,  Matrix Computations. ,  Johns Hopkins University Press ,  New York  ((1995)).
Liu  R., and Tan  T., “ An SVD based watermarking scheme for protecting rightful ownership. ,” IEEE Trans. Multimedia.  1520-9210 4, (1 ), 121–128  ((2002)).
Wang  Z., , Bovik  A. C., , Sheikh  H. R., , and Simoncelli  E. P., “ Image quality assessment: From error visibility to structural similarity. ,” IEEE Trans. Image Process..  1057-7149 13, (4 ), 600–612  ((2004)).
© 2008 SPIE and IS&T

Citation

Liang Xiao ; Zhihui Wei and Jianbing Ye
"Comments on “Robust embedding of visual watermarks using discrete wavelet transform and singular value decomposition” and theoretical analysis", J. Electron. Imaging. 17(4), 040501 (December 16, 2008). ; http://dx.doi.org/10.1117/1.3041170


Figures

Graphic Jump LocationF1 :

Three images are used for our experiments. (a) Cover image “Lena,” (b) watermark image “Cameraman,” and (c) watermark image “Peppers.”

Graphic Jump LocationF2 :

A counter example: (a) Real watermark image “Peppers,” (b) watermarked image embedded with “Peppers,” (c) extracted “Cameraman,” (d) real watermark image “Cameraman,” (e) watermarked image embedded with “Cameraman,” and (f) extracted “Peppers.”

Graphic Jump LocationF3 :

(a) Uniformly distributed random image and (b) estimate of watermark obtained from (a).

Tables

References

Ganic  E., and Eskicioglu  A. M., “ Robust embedding of visual watermarks using discrete wavelet transform and singular value decomposition. ,” J. Electron. Imaging.  1017-9909 14, (4 ), 043004  ((2005)).
Tian  Y., , Tan  T., , Wang  Y., , and Fang  Y., “ Do singular values contain information for face recognition. ,” Pattern Recogn..  0031-3203 36, , 649–655  ((2003)).
Golub  G. H., and Van Loan  C. F.,  Matrix Computations. ,  Johns Hopkins University Press ,  New York  ((1995)).
Liu  R., and Tan  T., “ An SVD based watermarking scheme for protecting rightful ownership. ,” IEEE Trans. Multimedia.  1520-9210 4, (1 ), 121–128  ((2002)).
Wang  Z., , Bovik  A. C., , Sheikh  H. R., , and Simoncelli  E. P., “ Image quality assessment: From error visibility to structural similarity. ,” IEEE Trans. Image Process..  1057-7149 13, (4 ), 600–612  ((2004)).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.