a2, United States Patent
`US 6,359,998 B1
`(10) Patent No.:
`Mar.19, 2002
`(45) Date of Patent:
`Cooklev
`
`US006359998B1
`
`(54) METHOD AND APPARATUS FOR WAVELET-
`BASED DIGITAL WATERMARKING
`
`(75)
`
`Inventor: Todor Cooklev, Salt Lake City, UT
`(US)
`
`(73) Assignee: 3Com Corporation, Santa Clara, CA
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/065,815
`
`(22)
`
`Filed:
`
`Apr. 23, 1998
`
`(SL)
`TInt, C07 eee ecceeseeeeeeereeesersereensensenses G06K 9/00
`
`(52)
`.. 382/100; 382/248
`(58) Field of Search oo... eee 382/100, 101,
`382/118, 119, 120, 212, 232, 248, 249,
`250, 276, 280, 284, 293, 296; 380/54, 210,
`252, 287; 713/176
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`9/1983 Rivest et al. oo... 178/22
`4,405,829 A *
`..
`.. 382/100
`2/1998 Powell et al.
`5,721,788 A *
`
`we 382/232
`4/1998 Rhoads.........
`5,745,604 A *
`
`9/1998 Powell etal. .....
`.. 382/100
`5,809,160 A *
`
`.......... 380/51
`3/1999 Moskowitz et al.
`5,889,868 A *
`
`we. 382/284
`5/1999 Daly .........
`5,905,819 A *
`
`6/1999 Coxet al. ice 380/54
`5,915,027 A *
`7/1999 Cox et al. wee 380/54
`5,930,369 A *
`
`7/1999 Powell et al.
`..
`.. 382/100
`5,930,377 A *
`
`we. 358/405
`8/1999 Curry «0...
`5,946,103 A *
`
`2/2000 Tewfik et al... 380/54
`6,031,914 A *
`5/2000 Tewfik etal. ..
`«. 713/176
`6,061,793 A *
`3/2001 Cox et al. we 380/54
`6,208,735 B1 *
`OTHER PUBLICATIONS
`
`Areepongsaet al. (Steganography for a low bit-rate wavelet
`based image coder, Jul. 2000, IEEE).*
`Areepongsaet al. (Exploring steganography for low bit rate
`wavelet based coder in imageretrieval system, Aug. 2000,
`TEEE).*
`
`Chae et al. (A robust embedded data from wavelet coeffi-
`cients, Dec. 1997, SPIE, vol. 3312).*
`Inoue et al. (A digital watermark technique based on the
`wavelet transform and its robustness on image compression
`and transformation, SCIS, 1998).*
`Onishiet al. (Wavelet detection of watermark from a clipped
`picture using wavelet, Jul. 1997, ITE Technical).*
`Ishizuka et al. (On an experimental evaluation of steganog-
`raphy with wavelet transform, SCIS, 1997).*
`Matsui et al. (Embedding a signature to pictures under
`wavelet transformation, Jun. 1996, IEICE).*
`Cooklev et al., Two-Channel Multifilter Banks and Multi-
`wavelets, IEEE Publication No. 0-7803-3192, Mar. 1996.
`
`* cited by examiner
`
`Primary Examiner—Andrew W. Johns
`Assistant Examiner—Amir Alavi
`(74) Attorney, Agent, or Firm—Workman, Nydegger &
`Seeley
`
`(57)
`
`ABSTRACT
`
`The disclosed watermarking method utilizes a transform
`technique for inserting an imperceptible digital watermark
`into digital data that is strongly resistant to unauthorized
`detection and decoding. Methods for embedding a water-
`mark that is sufficiently robust to lossy compression and
`other image processing operations such as rescaling are also
`provided. The watermarking principle is based on wavelet
`transforms where the coefficients of the filters have binary
`values, and are thus very attractive for practical realization.
`The waveletfilters utilize complimentary polynomials and
`implement non-regular wavelet transforms upon which the
`digital watermark is inserted. Following the inverse trans-
`formation process, the digital watermark is spread across
`multiple frequencies of the original digital data thereby
`reducing the impact of signal processing operations such as
`compression or other frequency filtering based operations.
`Additional embodiments employing complimentary matrix
`polynomials which are closely related to multifilter banks
`are also provided.
`
`23 Claims, 6 Drawing Sheets
`
`50
`
`{DATA
`
`
`
`
`
`
`
`
`
`—
`
`
`
`OISTRIBUTE
`
`
`
`
`
`
`
`
`
`
`
`storace
`
`REFERENCE
`|_4—74
`
`
`oath |
`
`
`
`54
`
`
`
`
`WATERHARK
`WATERMARK
`TLIITt
`ITTtT1
`
`
`
`I T
`
`48
`
`“7
`
`1
`
`Exhibit 1068
`Samsung v. Smart Mobile
`IPR2022-01249
`
`
`
`LOSSY
`COHPRESSION
`
`necowpaession
`
`R
`
`VERIFY
`WATERMARKED DATA
`
`Exhibit 1068
`Samsung v. Smart Mobile
`IPR2022-01249
`
`1
`
`

`

`U.S. Patent
`
`Mar. 19,2002
`
`Sheet 1 of 6
`
`US 6,359,998 B1
`
`
`
`2
`
`

`

`U.S. Patent
`
`Mar. 19,2002
`
`Sheet 2 of 6
`
`US 6,359,998 B1
`
`
`
`
`|DATA
`
`
`
`
`
`
`
`
`: E
`
`MBED
`WATERMARK
`
`
`
`
`WATERMARKa,
`
`
`
`
`
`
`DISTRIBUTE
`
`WATERMARK
`
`DATA
`
`LOSSY
`COMPRESSION
`
`
`DECOMPRESSION
`J
`
`
`
` VERIFY
`
`WATERMARKED DATA
`
`FIG.
`
`3
`
`3
`
`

`

`U.S. Patent
`
`Mar. 19, 2002
`
`Sheet 3 of6
`
`US 6,359,998 B1
`
`EMBED WATERMARK~~°
`
`PARTITION DATA INTO BLOCKS
`
`GENERATE SUBBAND TREE
`(COMPLETE OR PRUNED)
`
`PERFORM FORWARD WAVELET
`TRANSFORM
`
`———§ =oi =cncs ~~S&SSo oO =
`
`INSERT WATERMARK INTO
`WAVELET COEFFICIENTS
`
`PERFORM INVERSE WAVELET
`
`}~°®
`
`58
`
`60
`
`62
`
`64
`
`FIG, 4
`
`4
`
`

`

`U.S. Patent
`
`Mar. 19,2002
`
`Sheet 4 of 6
`
`US 6,359,998 B1
`
`VERIFY WATERMARK DATA}-~22
`
`PARTITION DATA INTO BLOCKS
`
`|~78
`
`GENERATE SUBBAND TREE
`CONSISTENT WITH EMBEDDING
`SUBBAND TREE
`
`80
`
`PERFORM FORWARD
`
`(COMPLETE OR PRUNED)
`
`PERFORM FORWARD
` 84
`WAVELETTRANSFORM
`WAVELET TRANSFORM
`
`
`
`
`WATERMARKED DATA
`OF REFERENCE DATA
`
`COMPARE WAVELET COEFFICIENTS|-~8
`REFERENCE
`90
`WATERMARK
`
`3g.|COMPARE COEFFICIENT DIFFERENCES
`WITH REFERENCE WATERMARK
`
`
`92 DIFFERENCE
`
`WITHIN VERIFICATION
`
`THRESHOLD
`
`NO
`
`
`WATERMARK
`
`DETECTED IN
`DISTRIBUTED
`WATERMARKED
`DATA
`
`WATERMARK
`INSUFFICIENTLY
`DETECTED OR
`ABSENT
`
`
`
`96
`
`FIG.
`
`§
`
`5
`
`

`

`U.S. Patent
`
`Mar. 19,2002
`
`Sheet 5 of6
`
`US 6,359,998 B1
`
`ees»©eae«©«@“ssPmOSOO
`
`AS
`
`0
`
`O04
`
`02
`
`03
`
`04
`
`05
`
`06
`
`07
`
`08
`
`09
`
`1
`
`FIG.
`
`6
`
`FIG.
`
`7
`
`“Od
`
`O04
`
`02
`
`03
`
`04
`
`05
`
`06
`
`07
`
`08
`
`09
`
`1
`
`an
`
`"
`
`-20
`
`25
`
`—
`
`FIG.
`
`8
`
`0
`
`O04
`
`02
`
`03
`
`04
`
`05
`
`06
`
`07
`
`08
`
`09
`
`1
`
`6
`
`

`

`U.S. Patent
`
`Mar. 19,2002
`
`Sheet 6 of 6
`
`US 6,359,998 B1
`
`
`
`FORWARD
`
`NON-REGULAR
`
`WAVELET
`TRANSFORM
`
`
`
`
`MER
`INVERSE
`
`WATERMARK
`hoy’ ag
`NON-REGULAR
`WAVELET
`
` INSERT
`TRANSFORM
` WATERMARK
`
`9 F
`
`IG. 10
`
`FIG.
`
`7
`
`

`

`US 6,359,998 B1
`
`1
`METHOD AND APPARATUS FOR WAVELET-
`BASED DIGITAL WATERMARKING
`
`BACKGROUND OF THE INVENTION
`
`1. The Field of the Invention
`
`The present invention generally relates to the field of
`digital imaging of multimedia data. More particularly, the
`invention relates to embedding a sufficiently robust water-
`mark into the image data that can withstand lossy compres-
`sion schemes without degrading the digital watermark.
`2. Present State of the Art
`
`The numberof applications that use digital storage and
`transmissionis increasing at a rapid rate. Specifically, types
`of digital data include digital audio, digital
`images and
`digital video, which may be largely electronically distrib-
`uted over ubiquitous public networks such as cable and
`telephone infrastructures. Additionally, digital data may be
`physically exchanged and replicated into exact duplicates of
`the original.
`The proliferation of digital media, e.g., audio, image and
`video, creates property concerns relating to intellectual
`property rights, e.g., copyrights. Traditional cryptographic
`techniques have provided one level of protection by allow-
`ing decryption of the encrypted data to be performed only by
`decryption key holders. However, conventional cryptogra-
`phy provideslittle protection against data piracy, ie., unau-
`thorized reproduction of decrypted digital data, since
`decrypted digital data may be easily replicated and distrib-
`uted. Such schemes provide insufficient protection against
`unauthorized reproduction of information and the inability
`to determine the source or origin of unauthorized duplicates.
`It is known in the prior art to provide a “digital water-
`mark” on a document to address this problem. Traditional
`digital watermarks on a data file or document may be
`perceptible and even visible or may be sufficiently embed-
`ded within the digital data so as to be imperceptible to those
`perceiving the digital data. Such digital watermarks remain
`present within the data even after processing such as a
`decryption procedure. While visible or humanly perceivable
`digital watermarks may provide apparent identification of
`the incorporating entity, such as a copyright owner, notice-
`able digital watermarks are considered unacceptable for
`aesthetically integrous media, e.g., imaging and audio data.
`Imperceptible watermarks are comprised of an identifi-
`cation code that is permanently embedded within the digital
`data and may contain specific information such as the
`identity of the purchaser of a particular copy of the digital
`data, e.g., audio (speech and music), images (photographic
`and graphics) and video (movies).
`There are techniques that have been proposed for water-
`marking digital data. In U.S. Pat. No. 5,464,997 to Barton,
`a method and apparatusis disclosed for basic authentication
`of a digital block such as an image carrying authentication
`information provided by the user embedded into the digital
`block of data. A digital signature comprised of a reduced
`representation of the digital block of data is embedded by
`replacing predetermined bits within the digital blockofdata.
`The authentication process is performed in reverse order so
`as to expose the embeddeddigital signature, thereby authen-
`ticating the integrity of the digital block of data. It should be
`pointed out that such an implementation while adequate for
`digital data transmission and storage techniques that do not
`impose compression techniques, are wholly inoperative in
`modern communication channels that employ sophisticated
`modulation techniques and other lossy compression meth-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`ods. While it is possible to employ techniques such as those
`that use the least significant bits (LSBs) of the image data to
`conceal or embedthe digital watermark, such approachesare
`obviously not sufficiently robust for enduring lossy com-
`pression processes as lossy compression techniques tend to
`randomize the LSBs. Furthermore, employing the most
`significant bits of the data image renders the digital water-
`mark perceptible and therefore unacceptable or undesirable
`for aesthetically demanding forms of digital data.
`Additionally, employing a frequency transformation fol-
`lowed by embedding the digital watermark in the high
`frequency bandsis also insufficiently robust since elemen-
`tary lowpassfiltering results in the decimation of the digital
`watermark. Conversely, placing the digital watermark in the
`low frequency components causes the digital watermark to
`become perceptible and therefore aesthetically unaccept-
`able. Therefore, it should be apparent that the objectives of
`creating an imperceptible digital watermark that is addition-
`ally sufficiently robust
`to lossy image processing, e.g,,
`compression and rescaling, are in direct conflict. That is to
`say, if the digital watermark is sufficiently robust to lossy
`imaging processing operations,
`the digital watermark
`becomes perceptually significant and therefore unaccept-
`able. Conversely, embedding the digital watermark so as to
`be imperceptible results in an inadequately robust digital
`watermark.
`
`transforms e.g., Discreet
`is known that orthogonal
`It
`Cosine Transform (DCT) and Discreet Fourier Transform
`(DFT), can be used to perform digital watermarking in the
`transform domain as taught in Cox et al., Secure Spread
`Spectrum Watermarking for Images, Audio and Video, Pro-
`ceedings of the 1996 International Conference on Image
`Processing, Vol. III, pp. 243-246, 1996. In that particular
`public description, the authors propose inserting a water-
`mark into the spectral components of the digital data using
`techniques analogous to spread spectrum communications,
`1e., hiding a narrow band signal in a wide band channel
`which is represented by the digital data. However, in such
`DCT-based approaches, spectral energy is concentrated
`which facilitates data compression, but becomes disastrous
`for retaining the integrity of the digital watermark.
`In such DCT-based approaches, the low-frequency com-
`ponents are employed, but
`the mean-value coefficient is
`excluded. Such an implementation suggests that the DCT-
`based approachesare not systematic. Such approaches were
`studied and proposed by Coxet al. due to the popularity of
`DCTin the industry. Therefore, orthogonal transforms such
`as the DCT or the DFT are good choices for compression,
`but are less than desirable choices for digital watermarking.
`The fundamental disadvantage of such techniques result
`from the fact that such techniques offer energy compaction
`and are therefore not sufficiently adequate choices for a
`spread spectrum-based algorithm.
`Thus, it appears that there exists no digital watermarking
`scheme that is capable of embedding an adequately imper-
`ceptible digital watermark into a digital data file, wherein the
`digital watermark is sufficiently robust to withstand lossy
`image processing operations (e.g., compression and
`resealing), while remaining detectable following such deg-
`radation processing. There also does not exist any digital
`watermarking techniquethat is sufficiently strongly resistant
`to unauthorized detection and decoding, even by individuals
`cognizant of the present watermarking techniques. Finally,
`there exists no digital watermarking technique that may be
`applied to all media types, e.g., audio,
`images, video,
`graphics and text (when represented as an image), that may
`be universally applied.
`8
`
`8
`
`

`

`US 6,359,998 B1
`
`3
`SUMMARY AND OBJECTS OF THE
`INVENTION
`
`It is an object of the invention to provide a method for
`watermarking digital data in such a manneras to cause the
`digital watermark to remain resilient throughout lossy com-
`pression processes.
`It is a further object of the present invention to provide a
`methodfor designating and determining the origin of digital
`data which may be subjected to lossy compression tech-
`niques through the use of a digital watermark.
`It is a further object of the present invention to provide a
`methodfor spreading a digital watermark across digital data
`such that when a portion of the frequencies of the digital data
`are compressed and thereby disposed, the digital watermark
`remains intact and discernable.
`
`Yet another object of the present invention is to provide a
`method for determining the origin of a particular copy of
`digital data through the use of a digital watermark
`adequately embedded within the digital data such that lossy
`compression techniques do not obscure or degenerate the
`digital watermark.
`It is yet another object of the present invention to provide
`a method for determining the legitimacy of a copy of digital
`data which has a digital watermark embedded thereon.
`It is yet another object of the present invention to provide
`a digital watermark that is imperceptible when embedded
`within digital data and is thereby aesthetically acceptable for
`marking digital data, such as images, that dictate impercep-
`tible steganography or embedding of data such as a digital
`watermark.
`
`invention to
`is a further advantage of the present
`It
`provide a digital watermarking technique that is strongly
`resistant to unauthorized detection and decoding even to
`those familiar with the watermarking technique of the
`present invention.
`Yet another advantage of the present invention permits
`graceful degradation, such as lossy compression, of the
`digital data having the watermark embedded thereon while
`retaining the integrity of the watermark following a decom-
`pression process.
`It is yet another advantage of the present invention to
`provide a universal watermark that can be applied to a
`myriad of media types,(e.g., audio, images, video, graphics
`and text when represented as an image), while being imple-
`mented in a practical and efficient implementation that is
`conducive to computerized processing.
`Additional objects and advantagesof the invention will be
`set forth in the description which follows, and in part will be
`obvious from the description, or may be learned by the
`practice of the invention. The objects and advantages of the
`invention may be realized and obtained by means of the
`instruments and combinationsparticularly pointed out in the
`appended claims.
`To achieve the foregoing objects, and in accordance with
`the invention as embodied and broadly described herein, a
`method and apparatus fordigitally watermarking digital data
`is presented which is visually imperceptible and strongly
`resistant
`to unauthorized detection and decoding.
`Furthermore,
`the watermarking technique of the present
`invention is robust to lossy compression and other image
`processing operations such as rescaling. The watermarking
`principle of the present
`invention is based on wavelet
`transforms where the coefficients of the filters have binary
`values, and thus are very attractive for practical realization.
`These wavelet
`filters are related to complimentary
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`polynomials, which are also related to multifilter banks.
`Experimental results have shown that multifilter banks, in
`addition to scalar filter banks, are advantageous for appli-
`cations such as that of the present invention.
`Those skilled in the art of digital signal processing
`appreciate that the number of applications that use digital
`storage and transmission is increasing at a rapid rate. Such
`applications include digital audio, images and video, trans-
`mission of video over public networks (e.g., cable and
`telephone networks). Therefore, protection of these various
`forms of digital data are fundamental to securing certain
`rights, such as intellectual property rights, that enure to the
`benefit of the mght holder. For example, publishers and
`artisans have long relied upon access control(i.e., physically
`controlling access) to provide security to their works. Sub-
`sequent
`techniques such as cryptography have provided
`limited protection against unauthorized reproduction by
`restricting those individuals that are authorized or retain the
`decryption algorithm for decrypting their artistic work.
`However, once the data is decrypted, it is freely copyable
`without a trace of information describing the origin of the
`casually protected data. To provide a tag or other identifying
`information, prior implementations have utilized a digital
`watermark which was perceptually significant and thereby
`degraded the aesthetic value of the digital data. Furthermore,
`attempts to place watermarks throughout digital data have
`often been destroyed by image processing techniques such
`as data compression operations. If a watermark is to be
`robust to lossy image processing operations, it may become
`perceptually significant unless, as in the present invention,
`the digital watermark is spread across the digital data.
`Those skilled in the art of digital signal processing
`appreciate the value of transforming spatial data into a
`transform domain, such as the frequency domain, in which
`signal processing operations may be performed. One popu-
`lar transform is the discreet cosine transform (DCT). While
`a DCT process could be employed for embedding a
`watermark, the primary disadvantage of the DCTis that it
`offers energy concentration, as opposed to energy spreading
`which is necessary for a robust method of embedding a
`durable watermark. Yet another transform technique appre-
`ciated by those of skill in the art is the wavelet transform
`which, however, also provides energy compaction and even
`more so than the DCT. Therefore,
`traditional or regular
`wavelets, the most prominent of which are the Daubechies
`wavelets, are less desirable choices for watermarking. Those
`of skill
`in the art appreciate that regular wavelets are
`continuous functions which implies that
`the impulse
`responses of the filers which tenerate them are relatively
`smooth.
`
`While it is not wholly appreciated, there are other types of
`wavelets, such as non-regular wavelets or wavelets which do
`not provide continuous functions. Non-regular wavelets
`have completely contrasting physical properties from regu-
`lar wavelets. For example, they do not generate multireso-
`lution analysis and although the filter coefficients form
`orthogonal bases for the Hilbert space in the discrete-time
`case, non-regular wavelet functions do not form orthogonal
`bases for the Hilbert space of continuous-time functions. It
`is known that complimentary polynomials are intimately
`related to wavelets, and in fact, these complimentary poly-
`nomials are highly non-regular wavelets with coefficients
`having two values, 1 and -1. An additional embodimentof
`the present invention employs complimentary matrix poly-
`nomials which are related to multiwavelets.
`
`The present invention employs a suggested watermarking
`algorithm wherein the digital data or digital signal is parti-
`9
`
`9
`
`

`

`US 6,359,998 B1
`
`5
`tioned into blocks, which are not necessarily of the same
`length, but are partitioned such that the amplitude of the
`signal within a block does not change or vary significantly.
`A subsequent step of the watermarking algorithm of the
`present invention is to generate a subbandtree thatis either
`a pruned or a complete subband tree through which the
`wavelet transform may be performed. While a complete
`subband tree may be employed, additional security is
`derived by employing uniquely pruned subband trees. The
`forward orthogonal circular wavelet transform, or alterna-
`tively the multiwavelet transform, may be performed such
`that the filter coefficients have only two values, 1 and -1.
`Additionally, the polyphase components of the filters are
`complimentary sequences.
`The next step of the watermarking algorithm is to insert
`the watermark by modulating someor all of the wavelet
`coefficients. Since the wavelets are highly non-regular, this
`is equivalent to placing the watermark everywhere in the
`frequency domain. The watermarkitself may be a sequence
`of random numbersor it may be a predetermined sequence
`such as an ASCII text string. Both imperceptible and per-
`ceptible watermarks may be employed as long as the aes-
`thetic qualities of the digital data are not significantly
`impaired. Followingthe insertion or overlaying of the digital
`watermark, the inverse orthogonal circular wavelet trans-
`form is performed with the corresponding synthesis filter
`bank to obtain the watermarked digital data. The water-
`markeddigital data may be compressed, transmitted,filtered
`or otherwise processed with the watermark remaining dis-
`cernable and intact.
`
`The algorithm for verifying whether unknowndigital data
`incorporates a specific watermark may be performed by
`decomposing the digital data into blocks as was performed
`during the embedding process. Subsequently, the same sub-
`bandtree as was utilized in the embedding processing,either
`a complete or pruned subbandtree is reconstructed for the
`wavelet
`transform. A forward wavelet
`transform is per-
`formed on the unknownordistributed watermarked data to
`determine the wavelet coefficients. Likewise, a forward
`wavelet transform is performed on a previously stored copy
`of the original digital data, also knownasthe reference data,
`to determine the wavelet coefficients of the pristine or
`reference digital data. The wavelet coefficients of both of the
`forward transformed digital data (unknown data and refer-
`ence data) are comparedto extract a difference which would
`be representative of any watermark data present within the
`unknowndigital data. The extracted or corrupted difference
`sequence representing any resident watermark is compared
`with the watermark or reference watermark stored previ-
`ously during the embedding process. If the extracted water-
`mark sequenceis sufficiently close, (i.e. within a predefined
`verification threshold), such as if the extracted watermark
`sequence coincides with more than fifty percent of the
`reference watermark,then it is concluded that the watermark
`is present in the unknowndata. If the watermark is a random
`sequence, compared with the reference watermark,then it is
`determinedthat either the digital watermark wasnot present
`in the unknown data or the unknowndata wassufficiently
`corrupted to make the verification processstatistically chal-
`lenging.
`The watermarking technique of the present invention is
`robust to unauthorized detection, even if an attacker knows
`the original image and watermarkingprinciple, (i.e., even if
`the attacker knows that a wavelet transform has been used
`
`and the filter coefficients obtained form a complimentary
`sequences). To achieve success by an attacker, the attacker
`must find the exact numberoffilter coefficients and the exact
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`values of these coefficients. Since the number of different
`complimentary polynomials grows exponentially with their
`length, such an attack cannot be accomplished in a reason-
`able amount of time. Secondly, the attacker must also find
`the exact subband tree that has been employed. Any ran-
`domly pruned subbandtree can be used in the watermarking
`process of the present invention. Thirdly, since there are
`even more complimentary matrix polynomials than scalar
`complimentary polynomials, one may use multiwavelet
`transforms to achieve an even higher level of security.
`Additional objects and advantagesof the invention will be
`set forth in the description which follows,and in part will be
`obvious from the description, or may be learned by the
`practice of the invention. The objects and advantages of the
`invention may be realized and obtained by means of the
`instruments and combinationsparticularly pointed out in the
`appended claims.
`These and other objects and features of the present
`invention will become more fully apparent from the follow-
`ing description and appended claims or may be learned by
`the practice of the invention as set forth hereinafter.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`In order that the manner in which the above-recited and
`
`other advantages and objects of the invention are obtained,
`a more particular description of the invention briefly
`described above will be rendered by reference to specific
`embodiments thereof which are illustrated in the appended
`drawings. Understanding that these drawings depict only
`typical embodiments of the invention and are not therefore
`to be consideredto be limiting of its scope, the invention will
`be described and explained with additional specificity and
`detail through the use of the accompanying drawings in
`which:
`
`FIG. 1 is a high level block diagram showing an example
`apparatus structure, employable by the embodiments of the
`present invention;
`FIG. 2 is a depiction of a two channel orthogonal FIR
`filter bank, in accordance with a preferred embodiment of
`the present invention;
`FIG. 3 is a high level block diagram of an embodimentfor
`designating and determining the origin of digital data
`through the use of a digital watermark, in accordance with
`the embodiments of the present invention;
`FIG. 4 is a flow chart of the embedding process for
`embedding a digital watermark in digital data, in accordance
`with the embodiments of the present invention;
`FIG. 5 is a flow chart for verifying the presence of a
`digital watermark in unknowndigital data, in accordance
`with the embodiments of the present invention;
`FIGS. 6-8 depict the frequency responses of three exem-
`plary filters depicting the non-regularity of the wavelet
`transform,
`in accordance with the embodiments of the
`present invention;
`FIG. 9 depicts a simplified flow diagram of digital data
`undergoing an embedding process for inserting a digital
`watermark on digital data, in accordance with the embodi-
`ments of the present invention; and
`FIG. 10 depicts a simplified diagram of a two-channel
`vector filter bank, in accordance with an embodimentof the
`present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`The current invention embraces within its scope a method
`and apparatus for digitally watermarking digital data. Thus,
`10
`
`10
`
`

`

`US 6,359,998 B1
`
`7
`the descriptions of the preferred embodiments which follow
`should be read to include both methods and apparatuses.
`With particular regard to the apparatuses involved, no par-
`ticular limitation is envisioned. Thus, the apparatus may
`involve dedicated hardware including discreet components,
`shift registers, custom VLSI chips, and the like, as well as
`general purpose computer or digital signal processing hard-
`ware having a conventional arrangement including a pro-
`cessing unit, memory, input devices, display devices, mass
`storage devices, and the like. From the description which
`follows, those skilled in the art will recognize that a variety
`of hardware and/or software configurations are suitable
`apparatuses for practicing the disclosed invention.
`By way of example, and not limitation, a suitable hard-
`ware apparatus is illustrated in FIG. 1.
`In FIG. 1,
`the
`apparatus comprises processing means 18. Processing
`means18 preferably comprises a general purpose micropro-
`cessor like those commonly used in personal computers or
`workstation computers. Processing means 18 could,
`however, also comprise a digital signal processor, a special-
`ized processor custom tailored to the inventive method
`disclosed herein, or any combination of a general purpose
`microprocessor, a digital signal processor, and a specialized
`processor.
`Electrically connected to processing means 18 is memory
`20. Memory 20 is preferably comprised of a combination of
`both volatile and non-volatile memory. Depending on the
`application, however, memory 20 may also comprise either
`solely volatile or solely non-volatile memory.
`Processing means 18 is also electrically connected to
`mass storage 22. Mass storage 22 preferably comprises a
`combination of fixed and removable computer disk storage
`(either magnetic or optical) although the apparatus could be
`configured with only fixed computer disk storage or remov-
`able disk storage.
`Computer usable medium having computer-readable code
`means embedded or encoded thereon is also contemplated.
`In such an article of manufacture, the computer readable
`program code means will comprise various meansfor imple-
`menting the method disclosed herein. By way of example,
`and not limitation, suitable computer usable media include
`magnetic disks (both fixed and removable), optical, mag-
`netic tape, volatile memory, non-volatile memory, and the
`like. In these articles of manufacture, the term “embedded
`therein” should be read to include the various methods of
`encoding computer-readable program code means so they
`are contained on or in the computer usable media.
`Throughout this application, the invention is described in
`relation to digital data. By way of example, and not
`limitation, digital data include image data both fixed and
`video, audio data, as well as other forms of digital data
`including textual data represented as an image.
`The present invention employs digital signal processing
`techniques for manipulating and processing the digital data
`of the present invention. The mathematical implementation
`of the processing techniquesare first introduced followed by
`the specific methods employed by the present invention. For
`digital signal processing applications, two channel orthogo-
`nal finite impulse response (FIR)filter banks are among the
`most widely used class of filter banks. FIG. 2 depicts a
`typical two channel orthogonal FIR filter bank 30 whichis
`typically comprised of two parts. In a first part, an analysis
`part is comprised of two filters, H,(z) 32 and H,(z) 34,
`which are each followed by downsamplers 36 and 38,
`respectively. Filter bank 30 is further comprised of a syn-
`thesis or reconstruction portion comprising upsamplers 40
`and 42 followed by twofilters, Go(z) 44 and G,(z) 46.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`The twosignals exiting the analysis part, may be denoted
`by Y,(z) and Y,(z) and called subbandsignals, and are equal
`to:
`
`Yo()=4[Ho(2"XZ")+H(-2)X(-2)].
`
`Y,(@2)=4[H,(2¥/7)X(z’?)4+H,(-217)X(-z”7)].
`
`It is shownthat the output signal, X(z) is given by
`
`X@)=¥4[Ho(Z)Go(Z)+HZ)Ga(z)XZ)+
`
`*[Ho(-2)Go(z)+Hi(-2)G@)X(-2)
`
`@)
`
`(2)
`
`3)
`
`(4)
`
`In perfect-reconstruction (PR) filter banks, X(z)=X(z) and
`therefore
`
`H(2)Go(z)+Hy (2)G,(z)=2.
`
`Ho(-2)Go(z)+Hy Cz)G,(z)=0.
`
`(5)
`
`(6)
`
`The transform which represents the computation of the two
`subbandsignals y,[n] and y,[n] from x[n]is called a forward
`wavelet transform. The transform which computesthe signal
`&[n] (which is equal to x[n] provided the filter bank is PR)
`is called an inverse wavelet transform. Note that PR is very
`important even though the signals y,[n] and y,[n] are often
`perturbed in a controlled fashion prior to reconstruction. The
`sole reason for the deviation from PR lies in the additional
`processing of the subbandsignals.
`In orthogonal filter banks, the impulse response h,[n],
`together with its integer, translates to form an orthogonal
`basis for the Hilbert space of square summable sequences.
`The aperiodic auto-correlation function (ACF) of the
`impulse responses, h,[n] and h,[n], are half-band functions:
`
`<h,[n], ho[n+2k]>=6,,
`
`<hy[n], h,[n+2k]>=6,,
`
`while the cross-correlation is identically zero
`
`<h,[n], h,[n+2k]>=0
`
`(7)
`
`(8)
`
`9%
`
`Any two sequences h,[n]