Secure spread spectrum watermarking for multimedia

IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER19971673

Secure Spread Spectrum

Watermarking for Multimedia Ingemar J.Cox,Senior Member,IEEE,Joe Kilian,F.Thomson Leighton,and Talal Shamoon,Member,IEEE

Abstract—This paper presents a secure(tamper-resistant)al-gorithm for watermarking images,and a methodology for digital watermarking that may be generalized to audio,video,and multimedia data.We advocate that a watermark should be constructed as an independent and identically distributed(i.i.d.) Gaussian random vector that is imperceptibly inserted in a spread-spectrum-like fashion into the perceptually most signi?-cant spectral components of the data.We argue that insertion of a watermark under this regime makes the watermark robust to signal processing operations(such as lossy compression,?ltering, digital-analog and analog-digital conversion,requantization,etc.), and common geometric transformations(such as cropping,scal-ing,translation,and rotation)provided that the original image is available and that it can be succesfully registered against the transformed watermarked image.In these cases,the watermark detector unambiguously identi?es the owner.Further,the use of Gaussian noise,ensures strong resilience to multiple-document,or collusional,attacks.Experimental results are provided to support these claims,along with an exposition of pending open problems. Index Terms—Intellectual property,?ngerprinting,multime-dia,security,steganography,watermarking.

I.I NTRODUCTION

T HE PROLIFERATION of digitized media(audio,image, and video)is creating a pressing need for copyright enforcement schemes that protect copyright ownership.Con-ventional cryptographic systems permit only valid keyholders access to encrypted data,but once such data is decrypted there is no way to track its reproduction or retransmission. Therefore,conventional cryptography provides little protection against data piracy,in which a publisher is confronted with unauthorized reproduction of information.A digital watermark is intended to complement cryptographic processes.It is a visible,or preferably invisible,identi?cation code that is permanently embedded in the data and remains present within

Manuscript received January14,1996;revised January24,1997.Portions of this work were reprinted,with permission,from the Proceedings of the IEEE Conference on Image Processing,1996,and from the Proceedings of the First International Conference on Data Hiding(Springer-Verlag,1996). The associate editor coordinating the reivew of this manuscript and approving it for publication was Prof.Sarah Rajala.

I.J.Cox and J.Kilian are with NEC Research Institute,Princeton,NJ08540 USA(e-mail:ingemar@4ef08e7301f69e31433294ff;joe@4ef08e7301f69e31433294ff).

F.T.Leighton is with the Mathematics Department and Laboratory for Computer Science,The Massachusetts Institute of Technology,Cambridge, MA02139USA(e-mail:ftl@4ef08e7301f69e31433294ff).

T.Shamoon is with InterTrust STAR Laboratory,Sunnyvale,CA94086 USA(e-mail:talal@4ef08e7301f69e31433294ff).

Publisher Item Identi?er S1057-7149(97)08460-1.the data after any decryption process.In the context of this work,data refers to audio(speech and music),images (photographs and graphics),and video(movies).It does not include ASCII representations of text,but does include text represented as an image.Many of the properties of the scheme presented in this work may be adapted to accommodate audio and video implementations,but the algorithms here speci?cally apply to images.

A simple example of a digital watermark would be a visible“seal”placed over an image to identify the copyright owner(e.g.,[2]).A visible watermark is limited in many ways.It marrs the image?delity and is susceptible to attack through direct image processing.A watermark may contain additional information,including the identity of the purchaser of a particular copy of the material.In order to be effective,a watermark should have the characteristics outlined below. Unobtrusiveness:The watermark should be perceptually invisible,or its presence should not interfere with the work being protected.

Robustness:The watermark must be dif?cult(hopefully impossible)to remove.If only partial knowledge is available (for example,the exact location of the watermark in an image is unknown),then attempts to remove or destroy a watermark should result in severe degradation in?delity before the watermark is lost.In particular,the watermark should be robust in the following areas.

?Common signal processing:The watermark should still be retrievable even if common signal processing oper-ations are applied to the data.These include,digital-to-analog and analog-to-digital conversion,resampling, requantization(including dithering and recompression), and common signal enhancements to image contrast and color,or audio bass and treble,for example.?Common geometric distortions(image and video data): Watermarks in image and video data should also be im-mune from geometric image operations such as rotation, translation,cropping and scaling.

?Subterfuge attacks(collusion and forgery):In addition, the watermark should be robust to collusion by multiple inpiduals who each possess a watermarked copy of the data.That is,the watermark should be robust to combining copies of the same data set to destroy the watermarks.Further,if a digital watermark is to be used in litigation,it must be impossible for colluders to combine their images to generate a different valid watermark with the intention of framing a third party.

1057–7149/97$10.00?1997IEEE

1674IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER1997

Universality:The same digital watermarking algorithm should apply to all three media under consideration.This is potentially helpful in the watermarking of multimedia products.Also,this feature is conducive to implementation of audio and image/video watermarking algorithms on common hardware.

Unambiguousness:Retrieval of the watermark should un-ambiguously identify the owner.Furthermore,the accuracy of owner identi?cation should degrade gracefully in the face of attack.

There are two parts to building a strong watermark:the watermark structure and the insertion strategy.In order for a watermark to be robust and secure,these two components must be designed correctly.We provide two key insights that make our watermark both robust and secure:We argue that the watermark be placed explicitly in the perceptually most signi?cant components of the data,and that the watermark be composed of random numbers drawn from a Gaussian distribution.

The stipulation that the watermark be placed in the per-ceptually signi?cant components means that an attacker must target the fundamental structural components of the data, thereby heightening the chances of?delity degradation.While this strategy may seem counterintuitive from the point of view of steganography(how can these components hide any signal?),we discovered that the signi?cant components have a perceptual capacity that allows watermark insertion without perceptual degradation.Further,most processing techniques applied to media data tend to leave the perceptually signi?cant components intact.While one may choose from a variety of such components,in this paper,we focus on the perceptually signi?cant spectral components of the data.This simultane-ously yields high perceptual capacity and achieves a uniform spread of watermark energy in the pixel domain.

The principle underlying our watermark structuring strategy is that the mark be constructed from independent,identically distributed(i.i.d.)samples drawn from a Gaussian distribu-tion.Once the signi?cant components are located,Gaussian noise is injected therein.The choice of this distribution gives resilient performance against collusion attacks.The Gaussian watermark also gives our scheme strong performance in the face of quantization,and may be structured to provide low false positive and false negative detection.This is discussed below,and elaborated on in[13].

Finally,note that the techniques presented herein do not provide proof of content ownership on their own.The focus of this paper are algorithms that insert messages into content in an extremely secure and robust fashion.Nothing prevents someone from inserting another message and claiming owner-ship.However,it is possible to couple our methods with strong authentication and other cryptographic techniques in order to provide complete,secure and robust owner identi?cation and authentication.

Section III begins with a discussion of how common sig-nal transformations,such as compression,quantization,and manipulation,affect the frequency spectrum of a signal.This discussion motivates our belief that a watermark should be embedded in the data’s perceptually signi?cant frequency components.Of course,the major problem then becomes how to imperceptibly insert a watermark into perceptually signi?cant components of the frequency spectrum.Section III-A proposes a solution based on ideas from spread spectrum communications.In particular,we present a watermarking algorithm that relies on the use of the original image to extract the watermark.Section IV provides an analysis based on pos-sible collusion attacks that indicates that a binary watermark is not as robust as a continuous one.Furthermore,we show that a watermark structure based on sampling drawn from multiple i.i.d Gaussian random variables offers good protection against collusion.Ultimately,no watermarking system can be made perfect.For example,a watermark placed in a textual image may be eliminated by using optical character recogni-tion technology.However,for common signal and geometric distortions,the experimental results of Section V suggest that our system satis?es most of the properties discussed in the introduction,and displays strong immunity to a variety of attacks in a collusion resistant manner.Finally,Section VI discusses possible weaknesses and potential enhancements to the system and describes open problems and subsequent work.

II.P REVIOUS W ORK

Several previous digital watermarking methods have been proposed.Turner[25]proposed a method for inserting an identi?cation string into a digital audio signal by substituting the“insigni?cant”bits of randomly selected audio samples with the bits of an identi?cation code.Bits are deemed “insigni?cant”if their alteration is inaudible.Such a system is also appropriate for two-dimensional(2-D)data such as images,as discussed in[26].Unfortunately,Turner’s method may easily be circumvented.For example,if it is known that the algorithm only affects the least signi?cant two bits of a word,then it is possible to randomly?ip all such bits,thereby destroying any existing identi?cation code.

Caronni[6]suggests adding tags—small geometric pat-terns—to digitized images at brightness levels that are imper-ceptible.While the idea of hiding a spatial watermark in an image is fundamentally sound,this scheme may be susceptible to attack by?ltering and redigitization.The fainter such watermarks are,the more susceptible they are such attacks and geometric shapes provide only a limited alphabet with which to encode information.Moreover,the scheme is not applicable to audio data and may not be robust to common geometric distortions,especially cropping.

Brassil et al.[4]propose three methods appropriate for document images in which text is common.Digital watermarks are coded by1)vertically shifting text lines,2)horizontally shifting words,or3)altering text features such as the vertical endlines of inpidual characters.Unfortunately,all three proposals are easily defeated,as discussed by the authors. Moreover,these techniques are restricted exclusively to images containing text.

Tanaka et al.[19],[24]describe several watermarking schemes that rely on embedding watermarks that resemble quantization noise.Their ideas hinge on the notion that quan-tization noise is typically imperceptible to viewers.Their

COX et al.:SPREAD SPECTRUM WATERMARKING 1675

?rst scheme injects a watermark into an image by using a predetermined data stream to guide level selection in a predictive quantizer.The data stream is chosen so that the resulting image looks like quantization noise.A variation on this scheme is also presented,where a watermark in the form of a dithering matrix is used to dither an image in a certain way.There are several drawbacks to these schemes.The most important is that they are susceptible to signal processing,especially requantization,and geometric attacks such as cropping.Furthermore,they degrade an image in the same way that predictive coding and dithering can.

In [24],the authors also propose a scheme for watermarking facsimile data.This scheme shortens or lengthens certain runs of data in the run length code used to generate the coded fax image.This proposal is susceptible to digital-to-analog and analog-to-digital attacks.In particular,randomizing the least signi?cant bit (LSB)of each pixel’s intensity will completely alter the resulting run length encoding.Tanaka et al.also propose a watermarking method for “color-scaled picture and video sequences”.This method applies the same signal transform as the Joint Photographers Expert Group (JPEG)(discrete cosine transform of

8

pairs of image points,,and increases the

brightness

at by one unit while correspondingly decreasing the brightness

of

pairs of points is

then

bits with the

LSB of each pixel.If the LSB is equal to the corresponding mask bit,then the random quantity is added,otherwise it is subtracted.The watermark is subtracted by ?rst computing the difference between the original and watermarked images

and then by examining the sign of the difference,pixel by pixel,to determine if it corresponds to the original sequence of additions and subtractions.This method does not make use of perceptual relevance,but it is proposed that the high frequency noise be pre?ltered to provide some robustness to lowpass ?ltering.This scheme does not consider the problem of collusion attacks.

Koch,Rindfrey,and Zhao [14]propose two general methods for watermarking images.The ?rst method,attributed to Scott Burgett,breaks up an image into

8

8DCT block.The choice of

the eight frequencies to be altered within the DCT block is based on a belief that the “middle frequencies...have moderate variance,”i.e.they have similar magnitude.This property is needed in order to allow the relative strength of the frequency triples to be altered without requiring a modi?cation that would be perceptually noticeable.Super?cially,this scheme is similar to our own proposal,also drawing an analogy to spread spectrum communications.However,the structure of their watermark is different from ours,and the set of frequencies is not chosen based on any direct perceptual signi?cance,or relative energy considerations.Further,because the variance between the eight frequency coef?cients is small,one would expect that their technique may be sensitive to noise or distortions.This is supported by the experimental results that report that the “embedded labels are robust against JPEG compression for a quality factor as low as about 50%.”By comparison,we demonstrate that our method performs well with compression quality factors as low as 5%.An earlier proposal by Koch and Zhao [15]used not triples of frequencies but pairs of frequencies,and was again designed speci?cally for robustness to JPEG compression.Nevertheless,they state that “a lower quality factor will increase the likelihood that the changes necessary to superimpose the embedded code on the signal will be noticeably visible.”In a second method,designed for black and white images,no frequency transform is employed.Instead,the selected blocks are modi?ed so that the relative frequency of white and black pixels encodes the ?nal value.Both watermarking procedures are particularly vulnerable to multiple document attacks.To protect against this,Zhao and Koch propose a distributed

8

,for example)that

are selected based on the binary digit to be transmitted.Thus,

1676IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER1997 Adelson’s method is equivalent to watermark schemes that

encode information into the LSB’s of the data or its transform

coef?cients.Adelson recognizes that the method is susceptible

to noise and therefore proposes an alternative scheme wherein

a2

l e v e l s a n d t h e h i g h f r e q u e n c y c o e f?c i e n t s,

COX et al.:SPREAD SPECTRUM WATERMARKING1677

be immune to intentional manipulation by malicious parties. These manipulations can include combinations of the above distortions,and can also include collusion and forgery attacks, which are discussed in Section IV-E.

A.Spread Spectrum Coding of a Watermark

The above discussion illustrates that the watermark should not be placed in perceptually insigni?cant regions of the image (or its spectrum),since many common signal and geometric processes affect these components.For example,a watermark placed in the high-frequency spectrum of an image can be easily eliminated with little degradation to the image by any process that directly or indirectly performs lowpass?ltering. The problem then becomes how to insert a watermark into the most perceptually signi?cant regions of the spectrum in a?delity preserving fashion.Clearly,any spectral coef?cient may be altered,provided such modi?cation is small.However, very small changes are very susceptible to noise.

To solve this problem,the frequency domain of the image or sound at hand is viewed as a communication channel, and correspondingly,the watermark is viewed as a signal that is transmitted through it.Attacks and unintentional signal distortions are thus treated as noise that the immersed signal must be immune to.While we use this methodology to hide watermarks in data,the same rationale can be applied to sending any type of message through media data.

We originally conceived our approach by analogy to spread spectrum communications[20].In spread spectrum commu-nications,one transmits a narrowband signal over a much larger bandwidth such that the signal energy present in any single frequency is undetectable.Similarly,the watermark is spread over very many frequency bins so that the energy in any one bin is very small and certainly undetectable.Nevertheless, because the watermark veri?cation process knows the location and content of the watermark,it is possible to concentrate these many weak signals into a single output with high signal-to-noise ratio(SNR).However,to destroy such a watermark would require noise of high amplitude to be added to all frequency bins.

Spreading the watermark throughout the spectrum of an image ensures a large measure of security against unintentional or intentional attack:First,the location of the watermark is not obvious.Furthermore,frequency regions should be selected in a fashion that ensures severe degradation of the original data following any attack on the watermark.

A watermark that is well placed in the frequency domain of an image or a sound track will be practically impossible to see or hear.This will always be the case if the energy in the watermark is suf?ciently small in any single frequency coef?cient.Moreover,it is possible to increase the energy present in particular frequencies by exploiting knowledge of masking phenomena in the human auditory and visual systems. Perceptual masking refers to any situation where information in certain regions of an image or a sound is occluded by perceptually more prominent information in another part of the scene.In digital waveform coding,this frequency domain (and,in some cases,time/pixel domain)masking is

exploited

Fig.2.Stages of watermark insertion process. extensively to achieve low bit rate encoding of data[9],[12].It is known that both the auditory and visual systems attach more resolution to the high-energy,low-frequency,spectral regions of an auditory or visual scene[12].Further,spectrum analysis of images and sounds reveals that most of the information in such data is located in the low-frequency regions.

Fig.2illustrates the general procedure for frequency domain watermarking.Upon applying a frequency transformation to the data,a perceptual mask is computed that highlights per-ceptually signi?cant regions in the spectrum that can support the watermark without affecting perceptual?delity.The wa-termark signal is then inserted into these regions in a manner described in Section IV-B.The precise magnitude of each modi?cation is only known to the owner.By contrast,an attacker may only have knowledge of the possible range of modi?cation.To be con?dent of eliminating a watermark,an attacker must assume that each modi?cation was at the limit of this range,despite the fact that few such modi?cations are typically this large.As a result,an attack creates visible(or audible)defects in the data.Similarly,unintentional signal distortions due to compression or image manipulation,must leave the perceptually signi?cant spectral components intact, otherwise the resulting image will be severely degraded.This is why the watermark is robust.

In principle,any frequency domain transform can be used. However,in the experimental results of Section VI we use a Fourier domain method based on the DCT[16],although we are currently exploring the use of wavelet-based schemes as a variation.In our view,each coef?cient in the frequency domain has a perceptual capacity,that is,a quantity of additional

1678IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER 1997

information can be added without any (or with minimal)impact to the perceptual ?delity of the data.To determine the perceptual capacity of each frequency,one can use models for the appropriate perceptual system or simple experimentation.In practice,in order to place a

length

image,we computed

the DCT of the image and

placed the watermark into

the

.In practice,we create a watermark where each

value is chosen independently

according

to

denotes a normal

distribution with

mean

a sequence of

values

to obtain an adjusted sequence of

values

.to

obtain a watermarked

document

and

for statistical signi?cance.We

extract

)and then

generating

.

Frequency-domain based methods for

extracting and

inserting

into

,which determines the extent to

which

.Three natural formulae for

computing

(2)

,which holds in all of our experiments.

Given

.

Equation (1)may not be appropriate when

the values vary widely.

If

adding 100will distort

this value unacceptably.Insertion based on (2)or (3)are more robust against such differences in scale.We note that (2)and (3)give similar results

when

may not be applicable for perturbing

all of the

values ,since different spectral components may exhibit more or less tolerance to modi?cation.More generally one can have multiple scaling

parameters

COX et al.:SPREAD SPECTRUM WATERMARKING 1679

can perceptually “get away”with

altering by a large factor without degrading the document.

There remains the problem of selecting the multiple scaling values.In some cases,the choice

of may be based on some general assumption.For example,(2)is a special case of the generalized

(1)

,extract the corresponding

values

whenever

.One way to combine this constraint with the empirical approach would be to

set according

to

.When we computed JPEG-based distortions

of the original image,we observed that the higher energy frequency components were not altered proportional to their magnitude [the implicit assumption of (2)].We suspect that we could make a less obtrusive mark of equal strength by attenuating our alterations of the high-energy components and amplifying our alterations of the lower energy components.However,we have not yet performed this experiment.C.Choosing the

Length,

dictates the degree to which the watermark

is spread out among the relevant components of the image.In general,as the number of altered components are increased the extent to which they must be altered decreases.For a more quantitative assessment of this tradeoff,we consider watermarks of the

form

where are chosen according

to independent normal distributions with standard

deviation

is proportional

to

.Even the act of

requantizing the watermarked document for delivery will

cause

.We measure the similarity

of

by

sim

(4)

Many other measures are possible,including the standard correlation coef?cient.Further variations on this basic metric are discussed in IV-D2.To decide

whether match,one determines whether

sim ,

where

and

(either

through the seller or through a watermarked document).Then,even conditioned on any ?xed value

for

is

independent

of

is a 4ef08e7301f69e31433294ffing the well-known

formula for the distribution of a linear combination of variables that are independent and normally

distributed,will be distributed according

to

is distributed according

to

then the probability that

sim

equal to six will cause spurious matchings to

be extremely rare.Of course,the number of tests to be performed must be considered in determining what false positive probability is acceptable.For example,if one tests an extracted watermark watermarks,then the probability of a false positive is increased by a multiplicative factor of 10

,the size of the

watermark.

However,

is generated

in the prescribed manner.As a rule of thumb,larger values

of

and

),

1680IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER

1997Fig.4.Bavarian couple image courtesy of Corel Stock Photo Library.

without causing larger similarity values

when

are independent.This bene?t must be balanced against the

tendency for the document to be more distorted

when

is generated with only ?nite pre-

cisions.However,this effect is caused only by the arithmetic

precision,and not on the constraints imposed by the document.

If

each is stored as a double-precision real number,the

difference between the calculated value of sim and its

“ideal”value will be quite small for any

reasonable

from

,

denoted

,differed substantially from zero,due to the effects

of a dithering procedure.While this artifact could be easily

eliminated as part of the extraction process,it provides a

motivation for postprocessing extracted watermarks.We found

that the simple

transformation yielded

superior values of sim .The improved performance

resulted from the decreased value

of

could

be greatly distorted for some values

of if

tolerance Again,the goal of such a transformation is to

lower

or

COX et al.:SPREAD SPECTRUM WATERMARKING

1681

(a)(b)

Fig.7.(a)Lowpass ?ltered,0.5scaled image of Bavarian couple.(b)Rescaled image showing noticeable loss of ?ne detail.

procedure for

extracting

and

multiple wa-termarked

copies

to produce an unwatermarked

document th

watermark is the same for

all

is generated by

either

adding

at random

to .Then as soon as one ?nds two documents with unequal values

for

documents one can,on average,

eliminate all but

a

,

where

as determin-ing a ?delity/undetectability tradeoff curve and the value

of

by a linear update rule,then

an averaging attack,which

sets

will result

in

will be

roughly

will be

1682IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER

1997

Fig.8.JPEG encoded version of Bavarian couple with 10%quality and 0%smoothing.

roughly .Thus,the similarity measure can be shrunk by

a factor of

reduction in the similarity measure.V.E XPERIMENTAL R ESULTS

In order to evaluate the proposed watermarking scheme,we took the Bavarian couple 2image of Fig.4and produced the watermarked version of Fig.5.We then subjected the watermarked image to a series of image processing and collusion style attacks.These experiments are preliminary,but show resilience to certain types of common processing.Of note is our method’s resistance to compression such as JPEG,and data conversion (printing,xeroxing and scanning).Note that in the case of af?ne transforms,registration to the original image is crucial to successful extraction.

In all experiments,a watermark length of 1000was used.We added the watermark to the image by modifying 1000of the more perceptually signi?cant components of the image spectrum using (2).More speci?cally,the 1000largest coef?-cients of the DCT (excluding the DC term)were used.A ?xed scale factor of 0.1was used throughout.A.Experiment 1:Uniqueness of Watermark

Fig.6shows the response of the watermark detector to 1000randomly generated watermarks of which only one matches the watermark present in Fig.5.The positive response due to the correct watermark is very much stronger that the response to

2The

common test image Lenna was originally used in our experiments,

and similar results were obtained.However,Playboy Inc.refused to grant copyright permission for electronic

distribution.

Fig.9.JPEG encoded version of Bavarian couple with 5%quality and 0%

smoothing.

Fig.10.Dithered version of the Bavarian couple image.

incorrect watermarks,suggesting that the algorithm has very low false positive response rates.B.Experiment 2:Image Scaling

We scaled the watermarked image to half of its original size,as shown in Fig.7(a).In order to recover the watermark,the quarter-sized image was rescaled to its original dimensions,as shown in Fig.7(b),in which it is clear that considerable ?ne detail has been lost in the scaling process.This is to be expected since subsampling of the image requires a lowpass spatial ?ltering operation.The response of the watermark detector to the original watermarked image of Fig.5was 32.0,which compares to a response of 13.4for the rescaled version of Fig.7(b).While the detector response is down by over 50%,the response is still well above random chance

COX et al.:SPREAD SPECTRUM WATERMARKING

1683

(a)(b)

Fig.11.(a)Clipped version of watermarked Bavarian couple.(b)Restored version of Bavarian couple in which missing portions have been replaced with imagery from the original unwatermarked image of Fig.4.

levels suggesting that the watermark is robust to geometric distortions.Moreover,it should be noted that75%of the original data is missing from the scaled down image of Fig.7.3 C.Experiment3:JPEG Coding Distortion

Fig.8shows a JPEG encoded version of the Bavarian cou-ple image with parameters of10%quality and0%smoothing, which results in clearly visible distortions of the image.The response of the watermark detector is22.8,again suggesting that the algorithm is robust to common encoding distortions. Fig.9shows a JPEG encoded version of Bavarian couple with parameters of5%quality and0%smoothing,which results is very signi?cant distortions of the image.The response of the watermark detector in this case is13.9,which is still well above random.

D.Experiment4:Dithering Distortion

Fig.10shows a dithered version of Bavarian couple.The response of the watermark detector is5.2,again suggesting that the algorithm is robust to common encoding distortions. In fact,more reliable detection can be achieved simply by removing any nonzero mean from the extracted watermark,as discussed in Section IV-D2.In this case the detection value is10.5.

E.Experiment5:Cropping

Fig.11(a)shows a cropped version of the watermarked image of Fig.5in which only the central quarter of the image remains.In order to extract the watermark from this image, the missing portions of the image were replaced with portions from the original unwatermarked image of Fig.4,as shown 3However,subsequent experiments have revealed that if small changes of scale are not corrected,then the response of the watermark detector is severely degraded.in Fig.11(b).In this case,the response of the watermark is 14.6.Once again,this is well above random even though75% of the data has been removed.

Fig.12(a)shows a clipped version of the JPEG encoded image of Fig.8in which only the central quarter of the image remains.As before,the missing portions of the image were replaced with portions from the original unwatermarked image of Fig.4,as shown in Fig.12(b).In this case,the response of the watermark is10.6.Once more,this is well above random even though75%of the data has been removed and distortion is present in the clipped portion of the image.

F.Experiment6:Print,Xerox,and Scan

Fig.13shows an image of the Bavarian Couple after1) printing,2)xeroxing,then3)scanning at300dpi using a UMAX PS-2400X scanner,and?nally4)rescaling to a size of

256

1684IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER

1997

(a)(b)

Fig.12.(a)Clipped version of JPEG encoded (10%quality,0%smoothing)Bavarian couple.(b)Restored version of Bavarian couple in which missing portions have been replaced with imagery from the original unwatermarked image of Fig.

4.

Fig.13.Printed,xeroxed,scanned,and rescaled image of Bavarian couple.1000randomly generated watermarks,which include the ?ve

watermarks present in the image.Five spikes clearly indicate

the presence of the ?ve watermarks and demonstrate that

successive watermarking does not unduly interfere with the

process.

H.Experiment 8:Attack by Collusion

In a similar experiment,we took ?ve separately water-

marked images and averaged them to form Fig.16in order to

simulate a simple collusion attack.As before,Fig.17shows

the response of the detector to 1000randomly generated

watermarks,which include the ?ve watermarks present in the

image.Once again,?ve spikes clearly indicate the presence

of the ?ve watermarks and demonstrate that simple collusion

based on averaging a few images is an ineffective

attack.Fig.14.Image of Bavarian couple after ?ve successive watermarks have

been added.

VI.C ONCLUSION A need for electronic watermarking is developing as elec-tronic distribution of copyright material becomes more preva-lent.Above,we outlined the necessary characteristics of such a watermark.These are:?delity preservation,robustness to com-mon signal and geometric processing operations,robustness to attack,and applicability to audio,image and video data.To meet these requirements,we propose a watermark whose structure consists

of

COX et al.:SPREAD SPECTRUM WATERMARKING

1685

Fig.15.Watermark detector response to1000randomly generated water-marks(including the?ve speci?c watermarks)for the watermarked image of Fig.14.Each of the?ve watermarks is clearly

indicated.

Fig.16.Image of Bavarian couple after averaging together?ve indepen-dently watermarks versions of the Bavarian couple image.

may be used for an image that is especially sensitive to large modi?cations of its spectral coef?cients,thus requiring weaker scaling factors for inpidual components.

We recommend that the watermark be placed in the per-ceptually most signi?cant components of the image spectrum. This maximizes the chances of detecting the watermark even after common signal and geometric distortions.Further,mod-i?cation of these spectral components results in severe image degradation long before the watermark itself is destroyed. Of course,to insert the watermark,it is necessary to alter these very same coef?cients.However,each modi?cation can be extremely small and,in a manner similar to spread spectrum communication,a strong narrowband watermark may be distributed over a much broader image(channel)spectrum. We have not performed an objective evaluation of the image quality,in part because the image quality can be adjusted to any desired quality by altering the relative power of the watermark using the scale factor term.Of course,as

the Fig.17.Watermark detector response to1000randomly generated water-marks(including the?ve speci?c watermarks)for the watermarked image of Fig.16.Each of the?ve watermarks is clearly detected,indicating that collusion by averaging is ineffective.

watermark strength is reduced to improve the image quality, the robustness of the method is also reduced.It will ultimately be up to content owners to decide what image degradation and what level of robustness is acceptable.This will vary considerably from application to application.

Detection of the watermark then proceeds by adding all of these very small signals,and concentrating them once more into a signal with high SNR.Because the magnitude of the watermark at each location is only known to the copyright holder,an attacker would have to add much more noise energy to each spectral coef?cient in order to be suf?ciently con?dent of removing the watermark.However,this process would destroy the image?delity.

In our experiments,we added the watermark to the image by modifying the1000largest coef?cients of the DCT(excluding the DC term).These components are heuristically perceptually more signi?cant than others.An important open problem is the construction of a method that would identify perceptually signi?cant components from an analysis of the image and the human perceptual system.Such a method may include additional considerations regarding the relative predictability of a frequency based on its neighbors.The latter property is important in combating attacks that may use statistical analyzes of frequency spectra to replace components with their maximum likelihood estimate.For example,the choice of the DCT is not critical to the algorithm and other spec-tral transforms,including wavelet type decompositions,are also possible.

We showed,using the Bavarian couple image,that our algorithm can extract a reliable copy of the watermark from imagery that we degraded with several common geometric and signal processing procedures.An important caveat here is that any af?ne geometric transformation must?rst be inverted.These procedures include translation,rotation,scale

1686IEEE TRANSACTIONS ON IMAGE PROCESSING,VOL.6,NO.12,DECEMBER1997

change,and cropping.The algorithm displays strong resilience to lossy operations such as aggressive scale changes,JPEG compression,dithering and data conversion.The experiments presented are preliminary,and should be expanded in order to validate the results.We are conducting ongoing work in this area.Further,the degree of precision of the registration proce-dures used in undoing af?ne transforms must be characterized precisely across a large test set of images.

Application of the method to color images is straightfor-ward.The most common transformation of a color image is to convert it to black and white.Color images are therefore converted into a YIQ representation and the brightness com-ponent Y is then watermarked.The color image can then be converted to other formats,but must be converted back to YIQ prior to extraction of the watermark.We therefore expect color images to be robust to the signal transformations we applied to gray-level images.However,robustness to certain color image processing procedures should be investigated.Similarly,the system should work well on text images,however,the binary nature of the image together with its much more structured spectral distribution need more work.We expect that our watermarking methodology should extend straightforwardly to audio and video data.However,special attention must be paid to the time-varying nature of these data.

Broader systems issues must be also addressed in order for this system to be used in practice.For example,it would be useful to be able to prove in court that a watermark is present without publicly revealing the original,unmarked document. This is not hard to accomplish using secure trusted hardware; an ef?cient purely cryptographic solution seems much more dif?cult.It should also be noted that the current proposal only allows the watermark to be extracted by the owner, since the original unwatermarked image is needed as part of the extraction process.This prohibits potential users from querying the image for ownership and copyright information. This capability may be desirable but appears dif?cult to achieve with the same level of tamper resistance.However, it is straightforward to provide if a much weaker level of protection is acceptable and might therefore be added as a secondary watermarking procedure.Finally,we note that while the proposed methodology is used to hide watermarks in data, the same process can be applied to sending other forms of message through media data.

A CKNOWLEDGMENT

I.Cox and T.Shamoon thank L.O’Gorman of AT&T Bell Laboratories for bringing this problem to their attention,and S. Roy for testing the robustness of the algorithm.I.Cox thanks H.Stone for advice on image transforms.

R EFERENCES

[1] E.H.Adelson,“Digital signal encoding and decoding apparatus,”U.S.

Patent4939515,1990.

[2]G.W.Braudaway,K.A.Magerlein,and F.C.Mintzer,“Color correct

digital watermarking of images,”U.S.Patent5530759,1996.

[3]W.Bender,D.Gruhl,and N.Morimoto,“Techniques for data hiding,”

in Proc.SPIE,vol.2420,p.40,Feb.1995.

[4]J.Brassil,S.Low,N.Maxemchuk,and L.O’Gorman,“Electronic

marking and identi?cation techniques to discourage document copying,”

in 4ef08e7301f69e31433294ffcom’94,pp.1278–1287.

[5] D.Boneh and J.Shaw,“Collusion-secure?ngerprinting for digital data,”

in Advances in Cryptology:Proc.CRYPTO’95.New York:Springer-Verlag,1995.

[6]G.Caronni,“Assuring ownership rights for digital images,”in Proc.

Reliable IT Systems,VIS’95..

[7]I.J.Cox,S.Roy,and S.L.Hingorani,“Dynamic histogram warping of

images pairs for constant image brightness,”in IEEE Int.Conf.Image Processing,1995.

[8]O.Faugeras,Three Dimensional Computer Vision:A Geometric View-

point.Cambridge,MA:MIT Press,1993.

[9] A.Gersho and R.Gray,Vector Quantization and Signal Compression.

Boston,MA:Kluwer,1992.

[10]R.C.Gonzalez and R.E.Woods,Digital Image Processing.New York:

Addison-Wesley,1993.

[11]P.J.Huber,Robust Statistics.New York:Wiley,1981.

[12]N.Jayant,J.Johnston,and R.Safranek,“Signal compression based on

models of human perception,”in Proc.IEEE,vol.81,no.10,1993. [13]J.Kilian et al.,“Resistance of watermarked documents to collusional

attacks,”in preparation.

[14] E.Koch,J.Rindfrey,and J.Zhao,“Copyright protection for multimedia

data,”in Proc.Int.Conf.Digital Media and Electronic Publishing,1994.

[15] E.Koch and Z.Zhao,“Toward robust and hidden image copyright

labeling,”in Proc.1995IEEE Workshop on Nonlinear Signal and Image Processing,June1995.

[16]J.S Lim,Two-Dimensional Signal Processing.Englewood Cliffs,NJ:

Prentice-Hall,1990.

[17] F.T.Leighton and S.Micali,“Secret-key agreement without public-key

cryptography,”in Proc.Cryptology,1993.

[18] B.M.Macq and J.-J.Quisquater,“Cryptology for digital TV broadcast-

ing,”in Proc.IEEE,vol.83,pp.944–957,1995.

[19]K.Matsui and K.Tanaka,“Video-steganography,”in Proc.IMA Intel-

lectual Property Project,1994,vol.1,pp.187–206.

[20]R.L.Pickholtz,D.L.Schilling,and 4ef08e7301f69e31433294fflstein,“Theory of spread

spectrum communications—A tutorial,”IEEE 4ef08e7301f69e31433294ffmun.,vol.

COMM-30,pp.855–884,1982.

[21]G.B.Rhoads,“Indenti?cation/authentication coding method and ap-

paratus,”Rep.WIPO WO95/14289,World Intellect.Property Org., 1995.

[22]W. F.Schreiber, A. E.Lippman, E.H.Adelson,and A.N.Ne-

travali,“Receiver-compatible enhanced de?nition television system,”

U.S.Patent5010405,1991.

[23] C.W.Therrien,Decision Estimation and Classi?cation:An Introduction

to Pattern Recognition and Related Topics.New York:Wiley,1989.

[24]K.Tanaka,Y.Nakamura,and K.Matsui,“Embedding secret informa-

tion into a dithered multi-level image,”in Proc.1990IEEE Military Communications Conf.,1990,pp.216–220.

[25]L.F.Turner,“Digital data security system,”Patent IPN WO89/08915,

1989.

[26]R.G.van Schyndel, A.Z.Tirkel,and C. F.Osborne,“A digital

watermark,”in Int.Conf.Image Processing,1994,vol.2,pp.

86–90.

Ingemar J.Cox(S’79–M’83–SM’95)received the

Ph.D.degree from Oxford University,Oxford,U.K.,

in1983.

From1984to1989,he was a principal investi-

gator in the Robotics Principles Department,AT&T

Bell Laboratories,Murray Hill,NJ,where his re-

search interests focused on issues of autonomous

mobile robots.He joined NEC Research Institute,

Princeton,NJ,as a senior research scientist in

1989.His principal research interests are broadly

in computer vision,speci?cally tracking,stereo and 3-D estimation,and multimedia,especially image database retrieval and electronic watermarking for copyright protection.

COX et al.:SPREAD SPECTRUM WATERMARKING

1687

Joe Kilian received the B.S.degree in computer science and in mathematics in1985,and the Ph.D.in mathematics in1989,both from the Massachusetts Institute of Technology,Cambridge.

He is a Research Scientist with NEC Research Institute,Princeton,NJ.His research interests are in

complexity theory and

cryptography.

F.Thomson Leighton received the B.S.E.degree

in electrical engineering and computer science from

Princeton University,Princeton,NJ,in1978,and

the Ph.D.degree in applied mathematics from the

Massachusetts Institute of Technology(MIT),Cam-

bridge,in1981.

He is a Professor of applied mathematics and a

member of the Laboratory for Computer Science

(LCS)at MIT.He was a Bantrell Postdoctoral

Research Fellow at LCS from1981to1983,and

he joined the MIT faculty as an Assistant Professor of applied mathematics in1982.He is a leader in the development of networks and algorithms for message routing in parallel machines,particularly in the use of randomness in wiring to overcome problems associated with congestion, blocking,and faults in networks.He has published over100research papers on parallel and distributed computing and related areas.He is the author of two books,including a leading text on parallel algorithms and

architectures.

Talal Shamoon(S’84–M’95)received the Ph.D.

degree in electrical engineering from Cornell Uni-

versity,Ithaca,NY,in January1995.

He joined the NEC Research Institute(NECI),

Princeton,NJ,in December of1994,where he held

the title of Scientist.He joined the InterTrust STAR

Laboratory,Sunnyvale,CA,in1997,where he is

currently a Member of the Research Staff working

on problems related to trusted rights management of

multimedia content.His research interests include

algorithms for audio,image and video coding and processing,multimedia security,data compression,and acoustic transducer design.He has worked on high-?delity audio coding and fast search algorithms for large image data bases.Since joining NECI,he has been actively involved in research on watermarking for multimedia systems.

本文来源：https://www.bwwdw.com/article/fqvl.html