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 prents a cure(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 inrted in a spread-spectrum-like fashion into the perceptually most signifi-cant spectral components of the data.We argue that inrtion of a watermark under this regime makes the watermark robust to signal processing operations(such as lossy compression,filtering, 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 the cas,the watermark detector unambiguously identifies the owner.Further,the u of Gaussian noi,ensures strong resilience to m
ultiple-document,or collusional,attacks.Experimental results are provided to support the claims,along with an exposition of pending open problems. Index Terms—Intellectual property,fingerprinting,multime-dia,curity,steganography,watermarking.
I.I NTRODUCTION
erar的音标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 process.It is a visible,or preferably invisible,identification code that is permanently embedded in the data and remains prent within
Manuscript received January14,1996;revid 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(Spri
nger-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 Rearch Institute,Princeton,NJ08540 USA(e-mail:ingemar@m;joe@m).
F.T.Leighton is with the Mathematics Department and Laboratory for Computer Science,The Massachutts Institute of Technology,Cambridge, MA02139USA(e-mail:ftl@math.mit.edu).
T.Shamoon is with InterTrust STAR Laboratory,Sunnyvale,CA94086 USA(e-mail:).
Publisher Item Identifier 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 reprentations of text,but does include text reprented as an image.Many of the properties of the scheme prented in this work may be adapted to accommodate audio and video implementations,but the algorithms here specifically apply to images.
A simple example of a digital watermark would be a visible“al”placed over an image to identify the
copyright ,[2]).A visible watermark is limited in many ways.It marrs the imagefidelity and is susceptible to attack through direct image processing.A watermark may contain additional information,including the identity of the purchar 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 prence should not interfere with the work being protected.
Robustness:The watermark must be difficult(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 vere degradation infidelity 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.The 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 individuals who each posss a watermarked copy of the data.That is,the watermark should be robust to combining copies of the same data t to destroy the watermarks.Further,if a digital watermark is to be ud 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
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 identification should degrade gracefully in the face of attack.
There are two parts to building a strong watermark:the watermark structure and the inrtion strategy.In order for a watermark to be robust and cure,the two components must be designed correctly.We provide two key insights that make our watermark both robust and cure:We argue that the watermark be placed explicitly in the perceptually most significant components of the data,and that the watermark be compod of random numbers drawn from a Gaussian distribution.
The stipulation that the watermark be placed in the per-ceptually significant components means that an attacker must target the fundamental structural components of the data, thereby heightening the chances offidelity degradation.While this strategy may em counterintuitive from the point of view of steganography(how can the components hide any signal?),we discovered that the significant components have a perceptual capacity that allows watermark inrtion without perceptual degradation.Further,most processing techniques applied to media data tend to leave the perceptually significant components intact.While one may choo from a variety of such components,in this paper,we focus on the perceptually significant 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 inde
pendent,identically distributed(i.i.d.)samples drawn from a Gaussian distribu-tion.Once the significant components are located,Gaussian noi 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 fal positive and fal negative detection.This is discusd below,and elaborated on in[13].
Finally,note that the techniques prented herein do not provide proof of content ownership on their own.The focus of this paper are algorithms that inrt messages into content in an extremely cure and robust fashion.Nothing prevents someone from inrting 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,cure and robust owner identification 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 significant frequency components.Of cour,the major problem then becomes how to imperceptibly inrt a watermark into perceptually significant components of the frequency spectrum.Section III-A propos a solution bad on ideas from spread spectrum communications.In particular,we prent
a watermarking algorithm that relies on the u of the original image to extract the watermark.Section IV provides an analysis bad 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 bad 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 satisfies most of the properties discusd in the introduction,and displays strong immunity to a variety of attacks in a collusion resistant manner.Finally,Section VI discuss possible weakness and potential enhancements to the system and describes open problems and subquent work.
II.P REVIOUS W ORK
Several previous digital watermarking methods have been propod.Turner[25]propod a method for inrting an identification string into a digital audio signal by substituting the“insignificant”bits of randomly lected audio samples with the bits of an identification code.Bits are deemed “insignificant”if their alteration is inaudible.Such a system is also appropriate for two-dimensional(2-D)
data such as images,as discusd in[26].Unfortunately,Turner’s method may easily be circumvented.For example,if it is known that the algorithm only affects the least significant two bits of a word,then it is possible to randomlyflip all such bits,thereby destroying any existing identification 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 byfiltering 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]propo 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 individual characters.Unfortunately,all three proposals are easily defeated,as discusd by the authors. Moreover,the techniques are restricted exclusively to images containing text.
Tanaka et al.[19],[24]describe veral watermarking schemes that rely on embedding watermarks that remble quantization noi.Their ideas hinge on the notion that quan-tization noi is typically imperceptible to viewers.Their
COX et al.:SPREAD SPECTRUM WATERMARKING 1675
first scheme injects a watermark into an image by using a predetermined data stream to guide level lection in a predictive quantizer.The data stream is chon so that the resulting image looks like quantization noi.A variation on this scheme is also prented,where a watermark in the form of a dithering matrix is ud to dither an image in a certain way.There are veral drawbacks to the 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 propo a scheme for watermarking facsimile data.This scheme shortens or lengthens certain runs of data in the run length code ud to generate the coded fax image.This proposal is susceptible to digital-to-analog and analog-to-digital attacks.In particular,randomizing the
口语救生圈
least significant bit (LSB)of each pixel’s intensity will completely alter the resulting run length encoding.Tanaka et al.also propo a watermarking method for “color-scaled picture and video quences”.This method applies the same signal transform as the Joint Photographers Expert Group (JPEG)(discrete cosine transform of
assassins8
pairs of image points,,and increas 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,otherwi it is subtracted.The watermark is subtracted by first 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 quence of additions and subtractions.This method does not make u of perceptual relevance,but it is propod that the high frequency noi be prefiltered to provide some robustness to lowpass filtering.This scheme does not consider the problem of collusion attacks.
Koch,Rindfrey,and Zhao [14]propo two general methods for watermarking images.The first 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 bad on a belief that the “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 modification that would be perceptually noticeable.Superficially,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 t of frequencies is not chon bad on any direct perceptual significance,or relative energy considerations.Further,becau the variance between the eight frequency coefficients is small,one would expect that their technique may be nsitive to noi 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]ud not triples of frequencies but pairs of frequencies,and was again designed specifically for robustness to JPEG compression.Nevertheless,they state that “a lower quality factor will increa the likelihood that the changes necessary to superimpo the embedded code on the signal will be noticeably visible.”In a cond method,designed for black and
white images,no frequency transform is employed.Instead,the lected blocks are modified so that the relative frequency of white and black pixels encodes the final value.Both watermarking procedures are particularly vulnerable to multiple document attacks.To protect against this,Zhao and Koch propo a distributed
察觉的意思8
,for example)that
are lected bad 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
coefficients.Adelson recognizes that the method is susceptible
to noi and therefore propos 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 ffic i e n t s,
COX et al.:SPREAD SPECTRUM WATERMARKING1677
be immune to intentional manipulation by malicious parties. The manipulations can include combinations of the above distortions,and can also include collusion and forgery attacks, which are discusd in Section IV-E.
A.Spread Spectrum Coding of a Watermark
The above discussion illustrates that the watermark should not be placed in perceptually insignificant regions of the image (or its spectrum),since many common signal and geometric process affect the 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 lowpassfiltering. The problem then becomes how to inrt a watermark into the most perceptually significant regions of the spectrum in afidelity prerving fashion.Clearly,any spectral coefficient may be altered,provided such modification is small.However, very small changes are very susceptible to noi.
majorTo 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 noi that the immerd signal must be immune to.While we u this methodology to hide watermarks in data,the same rationale can be applied to nding 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 prent in any single frequency is undetectable.Similarly,the watermark is spre
ad over very many frequency bins so that the energy in any one bin is very small and certainly undetectable.Nevertheless, becau the watermark verification process knows the location and content of the watermark,it is possible to concentrate the many weak signals into a single output with high signal-to-noi ratio(SNR).However,to destroy such a watermark would require noi of high amplitude to be added to all frequency bins.
Spreading the watermark throughout the spectrum of an image ensures a large measure of curity against unintentional or intentional attack:First,the location of the watermark is not obvious.Furthermore,frequency regions should be lected in a fashion that ensures vere 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 e or hear.This will always be the ca if the energy in the watermark is sufficiently small in any single frequency coefficient.Moreover,it is possible to increa the energy prent 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 cas,time/pixel do
main)masking is
exploited
Fig.2.Stages of watermark inrtion 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 significant regions in the spectrum that can support the watermark without affecting perceptualfidelity.The wa-termark signal is then inrted into the regions in a manner described in Section IV-B.The preci magnitude of each modification is only known to the owner.By contrast,an attacker may only have knowledge of the possible range of modification.To be confident of eliminating a watermark,an attacker must assume that each modification was at the limit of this range,despite the fact that few such modifications 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 significant spectral components intact, otherwi the resulting image will be verely degraded.This is why the watermark is robust.
forsureIn principle,any frequency domain transform can be ud. However,in the experimental results of Section VI we u a Fourier domain method bad on the DCT[16],although we are currently exploring the u of wavelet-bad schemes as a variation.In our view,each coefficient in the frequency domain has a perceptual capacity,that is,a quantity of additional
