cNEC Research Institute(cid:2) Technical Report  (cid:2) (cid:7)
`
`Secure Spread Spectrum Watermarking for Multimedia
`
`Ingemar J(cid:2) Coxy(cid:3) Joe Kiliany(cid:3) Tom Leightonz and Talal Shamoony
`
`Abstract
`
`We describe a digital watermarking method for use in audio(cid:2) image(cid:2) video and multimedia data(cid:3) We
`argue that a watermark must be placed in perceptually signicant components of a signal if it is to be
`robust to common signal distortions and malicious attack(cid:3) However(cid:2) it is well known that modication
`of these components can lead to perceptual degradation of the signal(cid:3) To avoid this(cid:2) we propose to insert
`a watermark into the spectral components of the data using techniques analogous to spread sprectrum
`communications(cid:2) hiding a narrow band signal in a wideband channel that is the data(cid:3) The watermark is
`dicult for an attacker to remove(cid:2) even when several individuals conspire together with independently
`watermarked copies of the data(cid:3) It is also robust to common signal and geometric distortions such as
`digital(cid:6)to(cid:6)analog and analog(cid:6)to(cid:6)digital conversion(cid:2) resampling(cid:2) and requantization(cid:2) including dithering
`and recompression and rotation(cid:2) translation(cid:2) cropping and scaling(cid:3) The same digital watermarking
`algorithm can be applied to all three media under consideration with only minor modications(cid:2) making it
`especially appropriate for multimedia products(cid:3) Retrieval of the watermark unambiguously identies the
`owner(cid:2) and the watermark can be constructed to make counterfeiting almost impossible(cid:3) Experimental
`results are presented to support these claims(cid:3)
`
`
`
`Introduction
`
`The proliferation of digitized media audio(cid:2) image and video is creating a pressing need for copyright en(cid:10)
`
`forcement schemes that protect copyright ownership(cid:7) Conventional cryptographic systems permit only valid
`
`keyholders access to encrypted data(cid:2) but once such data is decrypted there is no way to track its reproduc(cid:10)
`
`tion or retransmission(cid:7) Conventional cryptography therefore provides little protection against data piracy(cid:2)
`
`in which a publisher is confronted with unauthorized reproduction of information(cid:7) A digital watermark is
`
`intended to complement cryptographic processes(cid:7) It is a visible(cid:2) or preferably invisible(cid:2) identication code
`
`that is permanently embedded in the data(cid:2) that is(cid:2) it remains present within the data after any decryption
`
`process(cid:7) In the context of this work(cid:2) data refers to audio speech and music(cid:2) images photographs and
`
`graphics(cid:2) and video movies(cid:7)
`
`It does not include ASCII representations of text(cid:2) but does include text
`
`yPost(cid:2) NEC Research Institute(cid:3)  Independence Way(cid:3) Princeton(cid:3) NJ (cid:8)
`Email(cid:2) ingemar(cid:2)joe(cid:2)talal(cid:3)research(cid:4)nj(cid:4)nec(cid:4)com
`zPost(cid:2)Mathematics Department and Laboratory for Computer Science(cid:3) MIT(cid:3) Cambridge(cid:3) MA  (cid:8)
`Email(cid:2) ftl(cid:2)math(cid:3)mit(cid:3)edu
` Authors appear in alphabetical order(cid:8)
`
`
`
`Sony Exhibit 1020
`Sony v. MZ Audio
`
`

`

`represented as an image(cid:2) A simple example of a digital watermark would be a visible seal(cid:4) placed over
`
`an image to identify the copyright owner(cid:2) However(cid:5) the watermark might contain additional information(cid:5)
`
`including the identity of the purchaser of a particular copy of the material(cid:2)
`
`In order to be eective(cid:5) a watermark should be(cid:7)
`
`Unobtrusive The watermark should be perceptually invisible(cid:5) or its presence should not interfere with the
`
`work being protected(cid:2)
`
`Robust The watermark must be dicult hopefully impossible to remove(cid:2) Of course(cid:5) in theory(cid:5) any
`
`watermark may be removed with sucient knowledge of the process of insertion(cid:2) However(cid:5) if only
`
`partial knowledge is available(cid:5) for example(cid:5) the exact location of the watermark within an image is
`
`unknown(cid:5) then attempts to remove or destroy a watermark by say(cid:5) adding noise(cid:5) should result in severe
`
`degradation in data delity before the watermark is lost(cid:2) In particular(cid:5) the watermark should be robust
`
`to
`
`Common signal processing The watermark should still be retrievable even if common signal pro(cid:12)
`
`cessing operations are applied to the data(cid:2) These include(cid:5) digital(cid:12)to(cid:12)analog and analog(cid:12)to(cid:12)digital
`
`conversion(cid:5) resampling(cid:5) requantization including dithering and recompression(cid:5) and common sig(cid:12)
`
`nal enhancements to image contrast and color(cid:5) or audio bass and treble(cid:5) for example(cid:2)
`
`Common geometric distortions image and video data Watermarks in image and video data
`
`should also be immune from geometric image operations such as rotation(cid:5) translation(cid:5) cropping
`
`and scaling(cid:2)
`
`Subterfuge Attacks(cid:4) Collusion and Forgery In addition(cid:5) the watermark should be robust to col(cid:12)
`
`lusion by multiple individuals who each possess a watermarked copy of the data(cid:2) That is(cid:5) the
`
`watermark should be robust to combining copies of the same data set to destroy the watermarks(cid:2)
`
`Further(cid:5) if a digital watermark is to be used as evidence in a court of law(cid:5) it must not be possible
`
`for colluders to combine their images to generate a dierent valid watermark with the intention
`
`of framing a third(cid:12)party(cid:2)
`
`Universal The same digital watermark algorithm should apply to all three media under consideration(cid:2) This
`
`is potentially helpful in the watermarking of multimedia products(cid:2) Also(cid:5) this feature is conducive to
`
`implementation of audio and imagevideo watermarking algorithms on common hardware(cid:2)
`
`
`
`

`

`Unambiguous Retrieval of the watermark should unambiguously identify the owner(cid:2) Further(cid:3) the accuracy
`
`of owner identication should degrade gracefully in the face of attack(cid:2)
`
`Previous digital watermarking techniques(cid:3) described in Section (cid:3) are not robust(cid:3) and the watermark
`
`is easy to remove(cid:2) In addition(cid:3) it is unlikely that any of the earlier watermarking methods would survive
`
`common signal and geometric distortions(cid:2) The principal reason for these weaknesses is that previous methods
`
`have not explicitly identied the perceptually most signicant components of a signal as the destination for
`
`the watermark(cid:2) In fact(cid:3) it is often the case that the perceptually signicant regions are explicitly avoided(cid:2)
`
`The reason for this is obvious  modication of perceptually signicant components of a signal results
`
`in perceptual distortions much earlier than if the modications are applied to perceptually insignicant
`
`regions(cid:2) Hence(cid:3) for example(cid:3) the common stategy of placing a watermark in the high frequency components
`
`of a signal(cid:7)s spectrum(cid:2)
`
`The key insight of this paper is that in order for it to be robust(cid:3) the watermark must be placed in
`
`perceptually signicant regions of the data despite the risk of potential delity distortions(cid:2) Conversely(cid:3) if
`
`the watermark is placed in perceptually insignicant regions(cid:3) it is easily removed(cid:3) either intentionally or
`
`unintentionally by(cid:3) for example(cid:3) signal compression techniques that implicitly recognize that perceptually
`
`weak components of a signal need not be represented(cid:2)
`
`The perceptually signicant regions of a signal may vary depending on the particular media audio(cid:3)
`
`image or video at hand(cid:3) and even within a given media(cid:2) For example(cid:3) it is well known that the human
`
`visual system is tuned to certain spatial frequencies and to particular spatial characteristics such as line
`
`and corner features(cid:2) Consequently(cid:3) many watermarking schemes that focus on dierent phenomena that are
`
`perceptually signicant are potentially possible(cid:2) In this paper(cid:3) we focus on perceptually signicant spectral
`
`components of a signal(cid:2)
`
`Section begins with a discussion of how common signal transformations(cid:3) such as compression(cid:3) quan(cid:12)
`
`tization and manipulation(cid:3) aect the frequency spectrum of a signal(cid:2) This motivates why we believe that
`
`a watermark should be embedded in the data(cid:7)s perceptually signicant frequency components(cid:2) Of course(cid:3)
`
`the major problem then becomes how to insert a watermark into perceptually signicant components of the
`
`frequency spectrum without introducing visible or audible distortions(cid:2) Section (cid:2) proposes a solution based
`
`on ideas from spread spectrum communications(cid:2)
`
`The structure of a watermark may be arbitrary(cid:2) However(cid:3) Section  provides an analysis based on possible
`
`collusion attacks that indicates that a binary watermark is not as robust as a continuous one(cid:2) Furthermore(cid:3)
`
`
`
`

`

`we show that a watermark structure based on sampling drawn from multiple i(cid:2)i(cid:2)d Gaussian random variables
`
`oers good protection against collusion(cid:2)
`
`Of course(cid:4) no watermarking system can be made perfect(cid:2) For example(cid:4) a watermark placed in a textual
`
`image may be eliminated by using optical character recognition technology(cid:2) However(cid:4) for common signal and
`
`geometric distortions(cid:4) the experimental results of Section  strongly suggest that our system satises all of the
`
`properties discussed in the introduction(cid:4) and displays strong immunity to a wide variety of attacks(cid:4) though
`
`more extensive experiments are needed to conrm this(cid:2) Finally(cid:4) Section  discusses possible weaknesses and
`
`enhancements to the system(cid:2)
`
` Previous Work
`
`Several previous digital watermarking methods have been proposed(cid:2) L(cid:2) F(cid:2) Turner Tur  proposed a method
`
`for inserting an identication string into a digital audio signal by substituting the insignicant(cid:13) bits of
`
`randomly selected audio samples with the bits of an identication code(cid:2) Bits are deemed insignicant(cid:13) if
`
`their alteration is inaudible(cid:2) Such a system is also appropriate for two dimensional data such as images(cid:4) as
`
`discussed in vSTO (cid:2) Unfortunately(cid:4) Turner(cid:15)s method may easily be circumvented(cid:2) For example(cid:4) if it is
`
`known that the algorithm only aects the least signicant two bits of a word(cid:4) then it is possible to randomly
`
`ip all such bits(cid:4) thereby destroying any existing identication code(cid:2)
`
`Caronni Car  suggests adding tags (cid:17) small geometric patterns  to digitized images at brightness
`
`levels that are imperceptable(cid:2) While the idea of hiding a spatial watermark in an image is fundamentally
`
`sound(cid:4) this scheme is susceptible to attack by ltering and redigitization(cid:2) 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(cid:2) Moreover(cid:4) the scheme is not applicable to audio data and may not be robust to
`
`common geometric distortions(cid:4) especially cropping(cid:2)
`
`Brassil et al BLMO  propose three methods appropriate for document images in which text is common(cid:2)
`
`Digital watermarks are coded by(cid:19)   vertically shifting text lines(cid:4)  horizontally shifting words(cid:4) or  
`
`altering text features such as the vertical endlines of individual characters(cid:2) Unfortunately(cid:4) all three proposals
`
`are easily defeated(cid:4) as discussed by the authors(cid:2) Moreover(cid:4) these techniques are restricted exclusively to
`
`images containing text(cid:2)
`
`Tanaka et al TNM (cid:4) MT  describe several watermarking schemes that rely on embedding watermarks
`
`that resemble quantization noise(cid:2) Their ideas hinge on the notion that quantization noise is typically im(cid:26)
`
`
`
`

`

`perceptible to viewers(cid:2) Their rst scheme injects a watermark into an image by using a predetermined data
`
`stream to guide level selection in a predictive quantizer(cid:2) The data stream is chosen so that the resulting
`
`image looks like quantization noise(cid:2) A variation on this scheme is also presented(cid:4) where a watermark in the
`
`form of a dithering matrix is used to dither an image in a certain way(cid:2) There are several drawbacks to these
`
`schemes(cid:2) The most important is that they are susceptible to signal processing(cid:4) especially requantization(cid:4) and
`
`geometric attacks such as cropping(cid:2) Furthermore(cid:4) they degrade an image in the same way that predictive
`
`coding and dithering can(cid:2)
`
`In TNM (cid:4) the authors also propose a scheme for watermarking facsimile data(cid:2) This scheme shortens
`
`or lengthens certain runs of data in the run length code used to generate the coded fax image(cid:2) This
`
`proposal is susceptible to digital(cid:9)to(cid:9)analog and analog(cid:9)to(cid:9)digital attacks(cid:2)
`
`In particular(cid:4) randomizing the
`
`LSB of each pixel(cid:10)s intensity will completely alter the resulting run length encoding(cid:2) Tanaka et al also
`
`propose a watermarking method for color(cid:9)scaled picture and video sequences(cid:12)(cid:2) This method applies the
`
`same signal transform as JPEG DCT of    sub(cid:9)blocks of an image and embeds a watermark in the
`
`coecient quantization module(cid:2) While being compatible with existing transform coders(cid:4) this scheme is quite
`
`susceptible to requantization and ltering and is equivalent to coding the watermark in the least signicant
`
`bits of the transform coecients(cid:2)
`
`In a recent paper(cid:4) Macq and Quisquater MQ  briey discuss the issue of watermarking digital images
`
`as part of a general survey on cryptography and digital television(cid:2) The authors provide a description of
`
`a procedure to insert a watermark into the least signicant bits of pixels located in the vicinity of image
`
`contours(cid:2) Since it relies on modications of the least signicant bits(cid:4) the watermark is easily destroyed(cid:2)
`
`Further(cid:4) their method is restricted to images(cid:4) in that it seeks to insert the watermark into image regions
`
`that lie on the edge of contours(cid:2)
`
`Bender at al BGM  describe two watermarking schemes(cid:2) The rst is a statistical method called
`
`Patchwork(cid:12) that somewhat resembles the statistical component of our proposal(cid:2) Patchwork randomly
`
`chooses n pairs of image points(cid:4) ai(cid:2) bi(cid:4) and increases the brightness at ai by one unit while correspondingly
`
`decreasing the brightness of bi(cid:2) The expected value of the sum of the dierences of the n pairs of points
`
`is then claimed to be n(cid:4) provided certain statistical properties of the image are true(cid:2) In particular(cid:4) it is
`
`assumed that all brightness levels are equally likely(cid:4) that is(cid:4) intensities are uniformly distributed(cid:2) However(cid:4)
`
`in practice(cid:4) this is very uncommon(cid:2) Moreover(cid:4) the scheme may   not be robust to randomly jittering the
`
`intensity levels by a single unit(cid:4) and  be extremely sensitive to geometric ane transformations(cid:2)
`
`The second method is called texture block coding(cid:12)(cid:4) wherein a region of random texture pattern found in
`
`
`
`

`

`the image is copied to an area of the image with similar texture(cid:2) Autocorrelation is then used to recover each
`
`texture region(cid:2) The most signicant problem with this technique is that it is only appropriate for images
`
`that possess large areas of random texture(cid:2) The technique could not be used on images of text(cid:4) for example(cid:2)
`
`Nor is there a direct analog for audio(cid:2)
`
`Digimarc Corporation or Portland(cid:4) Oregon(cid:4) describe a method that adds or subtracts small random
`
`quantities from each pixel(cid:2) Addition or subtraction is determined by comparing a binary mask of L bits
`
`with the LSB of each pixel(cid:2) If the LSB is equal to the corresponding mask bit(cid:4) then the random quantity
`
`is added(cid:4) otherwise it is subtracted(cid:2) The watermark is subtracted by rst computing the dierence between
`
`the original and watermarked images and then by examining the sign of the dierence(cid:4) pixel by pixel(cid:4) to
`
`determine if it corresponds to the original sequence of additions and subtractions(cid:2) The Digimarc method
`
`does not make use of perceptual relevance and is probably equivalent to adding high frequency noise to the
`
`image(cid:2) As such(cid:4) it may not be robust to low pass ltering(cid:2)
`
`Koch(cid:4) Rindfrey and Zhao KRZ  propose two general methods for watermarking images(cid:2) The rst
`
`method(cid:4) attributed to Scott Burgett(cid:4) breaks up an image into    blocks and computes the Discrete Cosine
`
`Transform DCT of each of these blocks(cid:2) A pseudorandom subset of the blocks is chosen(cid:4) then(cid:4) in each
`
`such block(cid:4) a triple of frequencies is selected from one of  predetermined triples and modied so that their
`
`relative strengths encode a or value(cid:2) The  possible triples are composed by selection of three out of eight
`
`predetermined frequencies within the    DCT block(cid:2) The choice of the  frequencies to be altered within
`
`the DCT block is based on a belief that the middle frequencies (cid:2) (cid:2) (cid:2) have moderate variance(cid:16)(cid:4) i(cid:2)e(cid:2) they have
`
`similar magnitude(cid:2) This property is needed in order to allow the relative strength of the frequency triples
`
`to be altered without requiring a modication that would be perceptually noticeable(cid:2) Supercially(cid:4) this
`
`scheme is similar to our own proposal and(cid:4) in fact(cid:4) also draws analogy with spread spectrum communication(cid:2)
`
`However(cid:4) the structure of their watermark is dierent from ours(cid:2) The set of frequencies is not chosen based
`
`on any perceptual signicance or relative energy considerations(cid:2) Further(cid:4) because the variance between
`
`the eight frequency coecients is small(cid:4) one would expect that their technique may be sensitive to noise or
`
`distortions(cid:2) This is supported by the experimental results which report that the embedded labels are robust
`
`against JPEG compression for a quality factor as low as about (cid:16)(cid:2) By comparison(cid:4) we demonstrate that
`
`our method performs well with compression quality factors as low as (cid:2) An earlier proposal by Koch and
`
`Zhao KZ  used not triples of frequencies but pairs of frequencies(cid:4) and was again designed specically for
`
`robustness to JPEG compression(cid:2) Nevertheless(cid:4) 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(cid:2)(cid:3)
`
`In a second method(cid:4) designed for black and white images(cid:4) no frequency transform is employed(cid:3) Instead(cid:4)
`
`the selected blocks are modied so that the relative frequency of white and black pixels encodes the nal
`
`value(cid:3) Both watermarking procedures are particularly vulnerable to multiple document attacks(cid:3) To protect
`
`against this(cid:4) Zhao and Koch propose a distributed    block created by randomly sampling  pixels from
`
`the image(cid:3) However(cid:4) the resulting DCT has no relationship to that of the true image and consequently may
`
`be likely to cause noticeable artifacts in the image and be sensitive to noise(cid:3)
`
`In addition to direct work on watermarking images(cid:4) there are several works of interest in related areas(cid:3)
`
`Adelson Ade  describes a technique for embedding digital information in an analog signal for the purpose
`
`of inserting digital data into an analog TV signal(cid:3) The analog signal is quantized into one of two disjoint
`
`ranges(cid:4) f(cid:0) (cid:0)  (cid:2) (cid:2) (cid:2)g(cid:4)f (cid:0) (cid:0)  (cid:2) (cid:2) (cid:2)g(cid:4) for example which are selected based on the binary digit to be transmitted(cid:3)
`
`Thus Adelson(cid:19)s method is equivalent to watermark schemes that encode information into the least signicant
`
`bits of the data or its transform coecients(cid:3) Adelson recognizes that the method is susceptible to noise and
`
`therefore proposes an alternative scheme wherein a   Hadamard transform of the digitized analog signal
`
`is taken(cid:3) The dierential coecient of the Hadamard transform is oset by or unit prior to computing
`
`the inverse transform(cid:3) This corresponds to encoding the watermark into the least signicant bit of the
`
`dierential coecient of the Hadamard transform(cid:3) It is not clear that this approach would demonstrate
`
`enhanced resilience to noise(cid:3) Furthermore(cid:4) like all such least signicant bit schemes(cid:4) an attacker can eliminate
`
`the watermark by randomization(cid:3)
`
`Schreiber et al SLAN  describe a method to interleave a standard NTSC signal within an enhanced
`
`denition television EDTV signal(cid:3) This is accomplished by analyzing the frequency spectrum of the EDTV
`
`signal larger than that of the NTSC signal and decomposing it into three sub(cid:22)bands L(cid:4)M(cid:4)H for low(cid:4) medium
`
`and high frequency respectively(cid:3) In contrast(cid:4) the NTSC signal is decomposed into two subbands(cid:4) L and
`
`M(cid:3) The coecients(cid:4) Mk(cid:4) within the M band are quantized into m levels and the high frequency coecients(cid:4)
`
`Hk(cid:4) of the EDTV signal are scaled such that the addition of the Hk signal plus any noise present in the
`
`system is less than the minimum separation between quantization levels(cid:3) Once more(cid:4) the method relies on
`
`modifying least signicant bits(cid:3) Presumably(cid:4) the mid(cid:22)range rather than low frequencies were chosen because
`
`these are less perceptually signicant(cid:3) In contrast(cid:4) the method proposed here modies the most perceptually
`
`signicant components of the signal(cid:3)
`
`Finally(cid:4) it should be noted that many(cid:4) if not all(cid:4) of the prior art protocols are not collusion resistant(cid:3)
`
`
`
`

`

`Watermarked
`Image or Sound
`
`W
`
`Transmission
`
`Compression
`
`Lossy
`
`Geometric
`Distortions
`
`Processing
`Signal
`
`Conversion
`D/A-A/D
`
`Typical Distortions or Intentional Tampering
`
`Transmission
`
`W
`
`Corrupted
`Watermarked Image or Sound
`
`Figure (cid:3) Common processing operations that a media document could undergo
`
` Watermarking in the Frequency Domain
`
`In this section(cid:4) we rst discuss how common signal distortion aect the frequency spectrum of a signal(cid:7) This
`
`analysis supports our contention that a watermark must be placed in perceptually signicant regions of a
`
`signal if it is to be robust(cid:7) Section (cid:7) proposes inserting a watermark into the perceptually most signicant
`
`components of the spectrum using spread spectrum techniques(cid:7)
`
` (cid:2) Common signal distortions and their eect on the frequency spectrum of a
`signal
`
`In order to understand the advantages of a frequency(cid:10)based method(cid:4) it is instructive to examine the processing
`
`stages that an image or sound may undergo in the process of copying(cid:4) and to study the eect that these
`
`stages could have on the data(cid:4) as illustrated in Figure (cid:7) In the gure(cid:4) transmission(cid:14) refers to the application
`
`of any source or channel code(cid:4) andor standard encryption technique to the data(cid:7) While most of these steps
`
`
`
`

`

`are information lossless(cid:2) many compression schemes JPEG(cid:2) MPEG etc(cid:4) can potentially degrade the data(cid:6)s
`
`quality(cid:2) through irretrievable loss of data(cid:4)
`
`In general(cid:2) a watermarking scheme should be resilient to the
`
`distortions introduced by such algorithms(cid:4)
`
`Lossy compression is an operation that usually eliminates perceptually non(cid:7)salient components of an
`
`image or sound(cid:4) If one wishes to preserve a watermark in the face of such an operation(cid:2) the watermark
`
`must be placed in the perceptually signicant regions of the data(cid:4) Most processing of this sort takes place
`
`in the frequency domain(cid:4) In fact(cid:2) data loss usually occurs among the high frequency components(cid:4) Hence(cid:2)
`
`the watermark must be placed in the signicant frequency components of the image or sound spectrum(cid:4)
`
`After receipt(cid:2) an image may endure many common transformations that are broadly categorized as
`
`geometric distortions or signal distortions(cid:4) Geometric distortions are specic to images and video(cid:2) and
`
`include such operations as rotation(cid:2) translation(cid:2) scaling and cropping(cid:4) By manually determining a minimum
`
`of four or nine corresponding points between the original and the distorted watermark(cid:2) it is possible to
`
`remove any two or three dimensional ane transformation Fau (cid:4) However(cid:2) an ane scaling shrinking
`
`of the image leads to a loss of data in the high frequency spectral regions of the image(cid:4) Cropping(cid:2) or the
`
`cutting out and removal of portions of an image(cid:2) also leads to irretrievable loss of data(cid:4) Cropping may be a
`
`serious threat to any spatially based watermark such as Car  but is less likely to aect a frequency(cid:7)based
`
`scheme(cid:2) as shown in Section (cid:4)(cid:4)
`
`Common signal distortions include digital(cid:7)to(cid:7)analog and analog(cid:7)to(cid:7)digital conversion(cid:2) resampling(cid:2) re(cid:7)
`
`quantization(cid:2) including dithering and recompression(cid:2) and common signal enhancements to image contrast
`
`andor color(cid:2) and audio frequency equalization(cid:4) Many of these distortions are non(cid:7)linear(cid:2) and it is dicult
`
`to analyze their eect in either a spatial or frequency based method(cid:4) However(cid:2) the fact that the original
`
`image is known allows many signal transformations to be undone(cid:2) at least approximately(cid:4) For example(cid:2)
`
`histogram equalization(cid:2) a common non(cid:7)linear contrast enhancement method(cid:2) may be removed substantially
`
`by histogram specication GW  or dynamic histogram warping CRH  techniques(cid:4)
`
`Finally(cid:2) the copied image may not remain in digital form(cid:4) Instead(cid:2) it is likely to be printed(cid:2) or an analog
`
`recording made onto analog audio or video tape(cid:4) These reproductions introduce additional degradation
`
`into the image that a watermarking scheme must be robust to(cid:4)
`
`The watermark must not only be resistant to the inadvertant application of the aforementioned distor(cid:7)
`
`tions(cid:4) It must also be immune to intentional manipulation by malicious parties(cid:4) These manipulations can
`
`include combinations of the above distortions(cid:2) and can also include collusion and forgery attacks(cid:4)
`
`
`
`

`

` (cid:2) Spread spectrum coding of a watermark
`
`The above discussion makes it clear that the watermark should not be placed in perceptually insignicant
`
`regions of the image or its spectrum since many common signal and geometric processes aect these compo(cid:4)
`
`nents(cid:5) For example(cid:6) 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 low pass ltering(cid:5)
`
`The problem then becomes how to insert a watermark into the most perceptually signicant regions of an
`
`spectrum without such alterations becoming noticeable(cid:5) Clearly(cid:6) any spectral coecient may be altered(cid:6)
`
`provided such modication is small(cid:5) However(cid:6) very small changes are very susceptible to noise(cid:5)
`
`To solve this problem(cid:6) the frequency domain of the image or sound at hand is viewed as a communication
`
`channel(cid:6) and correspondingly(cid:6) the watermark is viewed as a signal that is transmitted through it(cid:5) Attacks
`
`and unintentional signal distortions are thus treated as noise that the immersed signal must be immune to(cid:5)
`
`While we use this methodology to hide watermarks in data(cid:6) the same rationale can be applied to sending
`
`any type of message through media data(cid:5)
`
`Rather than encode the watermark into the least signicant components of the data(cid:6) we originally con(cid:4)
`
`ceived our approach by analogy to spread spectrum communications PSM(cid:5) In spread spectrum communi(cid:4)
`
`cations(cid:6) one transmits a narrowband signal over a much larger bandwidth such that the signal energy present
`
`in any single frequency is imperceptible(cid:5) Similarly(cid:6) the watermark is spread over very many frequency bins so
`
`that the energy in any one bin is very small and certainly undetectable(cid:5) Nevertheless(cid:6) because the watermark
`
`verication process knows of the location and content of the watermark(cid:6) it is possible to concentrate these
`
`many weak signals into a single signal with high signal(cid:4)to(cid:4)noise ratio(cid:5) However(cid:6) to destroy such a watermark
`
`would require noise of high amplitude to be added to all frequency bins(cid:5)
`
`Spreading the watermark throughout the spectrum of an image ensures a large measure of security
`
`against unintentional or intentional attack(cid:12) First(cid:6) the location of the watermark is not obvious(cid:5) Furthermore(cid:6)
`
`frequency regions should be selected in a fashion that ensures severe degradation of the original data following
`
`any attack on the watermark(cid:5)
`
`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(cid:5) This will always be the case if the energy in the watermark is suciently small
`
`in any single frequency coecient(cid:5) Moreover(cid:6) it is possible to increase the energy present in particular
`
`frequencies by exploiting knowledge of masking phenomena in the human auditory and visual systems(cid:5)
`
`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(cid:2)
`
`In digital waveform
`
`coding(cid:3) this frequency domain and(cid:3) in some cases(cid:3) timepixel domain masking is exploited extensively to
`
`achieve low bit rate encoding of data JJS (cid:3) GG (cid:2) It is clear that both the auditory and visual systems
`
`attach more resolution to the high energy(cid:3) low frequency(cid:3) spectral regions of an auditory or visual scene
`
`JJS (cid:2) Further(cid:3) spectrum analysis of images and sounds reveals that most of the information in such data
`
`is located in the low frequency regions(cid:2)
`
`Figure  illustrates the general procedure for frequency domain watermarking(cid:2) Upon applying a frequency
`
`transformation to the data(cid:3) a perceptual mask is computed that highlights perceptually signicant regions
`
`in the spectrum that can support the watermark without aecting perceptual delity(cid:2) The watermark
`
`signal is then inserted into these regions in a manner described in Section (cid:2)(cid:2) The precise magnitude of
`
`each modication is only known to the owner(cid:2) By contrast(cid:3) an attacker may only have knowledge of the
`
`possible range of modication(cid:2) To be condent of eliminating a watermark(cid:3) an attacker must assume that
`
`each modication was at the limit of this range(cid:3) despite the fact that few such modications are typically
`
`this large(cid:2) As a result(cid:3) an attack creates visible or audible defects in the data(cid:2) Similarly(cid:3) unintentional
`
`signal distortions due to compression or image manipulation(cid:3) must leave the perceptually signicant spectral
`
`components intact(cid:3) otherwise the resulting image will be severely degraded(cid:2) This is why the watermark is
`
`robust(cid:2)
`
`In principle(cid:3) any frequency domain transform can be used(cid:2) However(cid:3) for the experimental results of
`
`Section  we use a Fourier domain method based on the discrete cosine transform DCT Lim (cid:3) although
`
`we are currently exploring the use of wavelet(cid:17)based schemes as a variation(cid:2) In our view(cid:3) each coecient in the
`
`frequency domain has a perceptual capacity(cid:3) that is(cid:3) a quantity of additional information can be added without
`
`any or with minimal impact to the perceptual delity of th