Matthieu Urvoy Florent Autrusseau

(LUNAM Université，Université de Nantes，IRCCyN UMR CNRS 6597，Polytech Nantes，rue Christian Pauc BP 50609 44306，Nantes，F(xiàn)rance)

0 Introduction

Robustness，capacity，security and invisibility are key requirements of watermarking，and more generally of data hiding．In steganography，for instance，high embedding capacities are essential，while the robustness to attack is less important:malicious attacks would involve hackers trying to read the secret message，but not to remove it．Conversely，with robust watermarking，one needs to be able to detect the watermark after various sorts of attacks:here，robustness is very important．The first watermarking algorithms appeared in the 1990＇s［1］;many more have been proposed since then，but very few are robust to geometric distortions，and particularly to print and scan．Early works operated simple luminance modifications or bit substitutions［2］， and allowed forquite significant amount of data to be embedded，but their robustness is limited to very slight distortions．Though spatial embedding methods are suitable for steganography，alternative domains need to be considered in watermarking，e．g．(resp．)DCT and DWT domains when robustness to(resp．)JPG and JPG2K compression is expected．

Commonly used watermark embedding techniques can mostly be classified into two categories:additive and multiplicative techniques．In Ref．［3］，Cox et al proposed pioneering works in which they designed and compared embedding techniques featuring both approaches．

Several approaches considered the robustness to geometric distortions and were designed subsequently．In Ref．［4］，the authors chose to additively embed the watermark in the Fourier domain;the watermark was generated by a Pseudo Random Number Generator(PRNG)whose output is spread as dots and modulated onto a circle in the Fourier spectrum．Such an approach shows limited performances when images are scaled．Similarly，in Ref．［5］，the watermark dots were embedded onto concentric circles within the Fourier domain．Here，a re-synchronisation step was used to compensate for geometric distortions prior to the detection;high amplitude frequency peaks located on the outer circle were used as registration clues．This method was further developed in Ref．［6］， in which the selection of the peak positions was optimized．Again，this watermark embedding technique can hardly resist scaling attacks．The peaks are randomly placed and embedded within a ring in the Fourier spectrum．The detection is non-blind:it requires the input image and the associated perceptual mask(used to weight the watermark with respect to edges and textured areas)．In Ref．［7］，it was proposed to embed a binary watermark as concentric circular segments in the Fourier domain．Both additive and multiplicative techniques were considered．A masking function computing the local variance was used to properly weight the watermark prior to its insertion．In Ref．［8］，unlike aforementioned studies，the watermark was inserted in the Fourier-Mellin domain that is geometric invariant．Indeed，the use of Log-polar maps in the Fourier domain makes the watermark robust against geometrical distortions，and avoids the necessity for re-synchronisation at the detection．The authors，however，did not provide any thorough evaluation of the robustness．

This paper introduces a watermark embedding method exhibiting high robustness to geometric distortions，and possibly be able to resist print and scan attacks．Furthermore，no re-synchronisation is required to detect the mark．Several embedding strategies are evaluated．This paper is organized as follows:Section 1 introduces the embedding algorithm，Section 2 is devoted to the detection method and Section 3 provides an in-depth analysis of the experimental results with respect to objective image quality and robustness．

1 Embedding Watermark into the Fourier Spectrum

As discussed earlier，most techniques showing high robustness to geometric distortions operate in the Fourier domain，which will also be used in our approach．Contrary to aforementioned techniques that spread the watermark onto circles or rings，it is spread onto a square(or rectangular)area from the Fourier spectrum and centered at a carrier frequency．

1．1 Modulation of Watermark at a Carrier Frequency

Previously discussed algorithms suffer from the dispersion of the watermark within the Fourier spectrum，that is，small distortions may easily modify the spectrum in such a way that the detection cannot find the watermarked frequencies anymore．For this reason，the watermarked frequencies are grouped in a square(or rectangular)patch:spectrum distortions still allow for the patch to be detected．Fig．1 depicts the embedding algorithm:①the input image is transformed into the Fourier domain;②a noise-like watermark in the form of a square patch of 64×64 coefficients is modulated onto the carrier frequencies(uw，vw);and ③ watermarked image is obtained by inverse transform．Note that，in Figs．1 and 2，the binary watermark pattern is exaggerated in order to show a possible shape and location of the watermark within the Fourier spectrum．In this paper，the carrier frequencies are uw=0．8max(u)and vw=0．8max(v)．

1．2 Evaluation of Embedding Strategies

Four strategies have been considered for embedding the watermark into the Fourier spectrum:classical multiplicative(Eq．(1))，additive(Eq．(2))，multiplicative(Eq．(3))and substitution(Eq．(4))．They obey to the following equations:

Fig．1 Embedding scheme:a binary patch is inserted at frequencies(uw，vw)in the spectrum

where yu，vis the watermarked transformed coefficient at frequencies(u，v)，xu，vis the original coefficient，wu，vis the noise-like watermark，and α is a weighting parameter(scalar)which is used to adapt the strength of the watermark．

2 Detection of Watermark by 2D Cross-Correlation

The detection algorithm uses the normalized 2D cross-correlation introduced in Ref．［9］，which exploits the Fourier correlation property．The correlation ρ between 2 signals s1and s2is written as whereand-1are respectively the direct and inverse Fourier transforms，andis the complex conjugate of(s)．The cross-correlation provides a similarity measure between s1and s2．

Depending on the embedding strategiesfrom Eqs．(1)to(4)，Eq．(5)is applied to different signals．For Eqs．(1)and(3)(multiplicative)，the crosscorrelation is computed between the weighted watermark(xu，v·wu，v)and the Fourier coefficients extracted from the watermarked spectrum．Here，the detection is semi-blind，and the watermarked coefficients need to be stored and transmitted．Conversely，for Eqs．(2)and(4)(resp．a(chǎn)dditive and substitutive)，blind detection is performed:the cross-correlation is computed between the initial watermark and the extracted Fourier coefficients．

Fig．2 depicts the overall detection algorithm:①the possibly watermarked image is transformed into the Fourier domain;②the initial patch of watermarked Fourier coefficients(Eqs．(1)，(2)and(3))or the initial noise-like watermark(Eq．(4))is cross-correlated with the matching coefficients of the image spectrum at the expected carrier frequencies(uw，vw);and③the higher the cross-correlation value，the more likely the watermark has been detected．

3 Experimental Results:Quality and Robustness

The performances of the proposed watermarking technique were thoroughly evaluated in terms of objective quality and robustness to attacks．Several types of distortions were considered，mostly a combination of rotations and noise．Two datasets were used in these experiments:10 images from the Kodak database(http:∥r0k．us/graphics/kodak/，set A)and 1 000 images from the BOWS database(http∥bows2 ec-lille．fr/index．php?mode=VIEW＆tmpl=indexl，set B)．

3．1 Security of Watermark:Detection of the Presence of a Watermark

All images from set B were watermarked．For each of the 1 000 images，detection was run three times:(H0)on the original un-watermarked image，(H1)on the watermarked image and(H2)on attacked watermarked image—rotation(0．4°)and noise of maximum amplitude 6 levels on the 8-bit chrominance plane．Fig．3 depicts the distribution of the peak correlation over the entire set B for Eqs．(1)and(2)．For Eq．(2)，both H1/H2 distributions are clearly disjoint from H0’s peaks distribution，even for the quite small embedding strength α =4000．With Eq．(2)，this is only true for scenario H1，and H0 and H2 distributions are overlapping．

Fig．2 Detection scheme:2D cross-correlation is performed in the Fourier domain

Fig．3 Detection scores for watermarked(H1，H2)and unwatermarked(H0)images

For embedding strategies from Eqs．(1)to(3)and several values of α，Table 1 lists the worst peak correlations obtained for scenarios H0(the maximum score)，H1 and H2(the minimum scores)．As can be seen，this is the case for all H1 scenarios，contrary to H2 scenarios where only Eq．(2)guarantees perfect detection．For Eqs．(1)and(3)，detection rate gets close to 100．0%when the embedding strength is increased．Maximum peak correlation values for scenario H0 can then be used as detection thresholds

3．2 Security of Watermark:Can an Erroneous Message be Detected?

Four images from set A were watermarked with 1000 different keys．For each of the 4000 marked images，detection was run twice:(H0)with the inserted key and then(H1)with a wrong key．This process was repeated for embedding strategies from Eqs．(1)to(3)．Table 2 lists，for scenario H0，the maximum peak correlation values guaranteeing that 95%and 100%of the wrong detections are considered as such;in other words，the minimum detection thresholdsguaranteeing the retrieval of the exact key．Table 2 also lists the minimum peak correlation scores of true detections．

Table 1 Peak correlation scores and detection rates for scenarios H0，H1 and H2．Starred values correspond to scenarios where the distributions of H0 and H1/H2 scores are disjoint，hence guaranteeing perfect detection for all set B

Table 2 Maximum correlation peaks obtained under H0 and minimum correlation peaks obtained under H1

3．3 Robustness to Attacks

Fig．4 Robustness to 28 attacks(7 rotations，4 noises)for Eq．(2)

Robustness performances of Eqs．(1)to(4)were evaluated on set A．28 attacks，namely a combination of 7 rotations(angles 0．2°，0．4°，0．6°，0．8°，1．0°，1．5°and 2．0°)and 4 Gaussian noises(amplitudes 6，8，10 and 12 color levels)，were applied to all watermarked images． Fig．4 shows the peak correlation scores obtained with Eq．(2)．Thick lines are average values for the entire set，while thin grey lines correspond to scores for individual images．The x-axis is split into 7 areas，one for each rotation angle，each of which showing the results for 5 embedding strengths(from 2 to 6)．As can be seen，the 2nd embedding strategy performs well when considering threshold(see Section 3．1)，but fails to remain above threshold(see Section 3．2)．Similar results are obtained for Eqs．(1)and(3)．Fig．5(a)compares the robustness of Eqs．(1)to(4)with Ref．［7］on image Lena，with rotations(0．4°，0．6°，0．8°，1．0°and 1．2°)and noise(same values as before)．As shown in Fig．5，Eqs．(1)to(3)perform better than Ref．［7］—whose threshold is=0．18—when considering thresholds，and Eq．(1)performs better even for threshold

Finally，images from set A were watermarked(Eq．(2)，α =8000)and printed on a poor quality office laser printer(DELL 2330N)at 600 dpi．Prints were scanned with an office scanner(EPSON XP 605)at 300dpi．The average peak correlation of the detection was 0．284(minimum 0．214，maximum 0．373)，thus always being greater than detection thresholdand also greater thanfor 5 images．

3．4 Quality Evaluation of the Proposed Embedding Strategies

Fig．5(b)shows PSNR and VIF［10］scores obtained(mean scores on set A)with the following embedding strengths:Eq．(1):α =4，Eq．(2):α =8000，Eq．(3):α =4 and Eq．(4):none．Even with such high embedding strengths，the quality scores are higher than those obtained in Ref．［7］．As a rough guide—assuming that the obtained scores follow a normal distribution—one should note that confidence intervals obtained with Eqs．(1)to(4)are not overlapping with the one from Ref．［7］．Wilcoxon rank-sum tests show that Eqs．(1)to(4)provide significantly higher PSNRs than that in Ref．［7］(p ＜0．008)．For VIF scores，the same test reaches significance for all 4 equations as well(p＜0．0002)．Moreover，the proposed embedding method was also compared with the works from“Digimarc-for-images”(http:∥www．digimarc．com/digimarc-for-images)．Five natural images were tested;attacks combined a rotation(0．4°，0．6°，0．8°，1．0°，1．5°or 2．0°)and noise addition(with average amplitude 6，8，10 or 12)．Significant results are presented in Fig．6，in which both the best and the worst case scenario out of the five tested images are shown．It is important to note that the“Digimarc-forimages”tool provides not a correlation coefficient but a percentage bar that has been normalized in the scope of this experiment for a better comparison．

Fig．5 Comparison between Ref．［7］and proposed embedding strategies from Eqs．(1)to(4)

Fig．6 Comparison between the proposed embedding method(Eq．(2))and“Digimarc-for-images”

4 Conclusions

In this paper，a new watermarking algorithm that is robust to slight rotations and noise is proposed．The watermark is embedded within the Fourier domain and modulated at a high carrier frequency．Four embedding methods were evaluated in terms of robustness and quality;strategies from Eqs．(1)to(3)all performed well．The proposed approach is low computational and only requires about 1s to insert or detect a watermark into a 768×512 image，similarly to the fast technique presented in Ref．［4］．Practical experiments show that the proposed method is robust to print and scan．

［1］Tirkel A Z，Rankin G A，van Schyndel R M，et al．Electronic water mark ［C］∥DICTA 93．［S．l．］:Macquarie University，1993:666-673．

［2］Bender W，Gruhl D，Morimoto N，et al．Techniques for data hiding［J］．IBM Systems Journal，1996，35(3/4):313-336．

［3］Cox I J，Kilian J，Shamoon T．Secure spread spectrum watermarking for multimedia ［J］．IEEE Transactions on Image Processing，1997，6(12):1673-1687．

［4］Poljicak A，Mandic L，Agic D．Discrete Fourier transform based watermarking method with an optimal implementation radius［J］．Journal of Electronic Imaging，2011，20(3):033008．

［5］Chiu Y C，Tsai W H．Copyright protection against printand-scan operations by watermarking for color images using coding and synchronization of peak locations in frequency domain ［J］．Journal of Information Science and Engineering，2006，22(3):483-496．

［6］Tang Y L ，Huang Y T．Print-and-scan resilient watermarking for authenticating paper-based certificates［C］∥Proceedings of 1st International Conference on Pervasive Computing Signal Processing and Applications．Harbin:［s．n．］，2010:357-361．

［7］Solachidis V，Pitas I．Circularly symmetric watermark embedding in 2-d dft domain ［J］．IEEE Transactions on Image Processing，2001，10(11):1741-1753．

［8］O’Ruanaidh J J K，Pun T．Rotation，scale and translation invariant digital image watermarking［C］∥Proceedings of International Conference on Image Processing．Santa Barbara:IEEE，1997:536-539．

［9］Lewis J P．Fast normalized cross-correlation ［J］．Vision Interface，1995，10:120-123．

［10］Sheikh H R，Bovik A C．Image information and visual quality ［J］．IEEE Transactions on Image Processing，2006，15(2):430-444．