Techniques for data hiding p

To view this page ensure that Adobe Flash Player version 9.0.124 or greater is installed.

Please login or register to make a comment!

313 © Copyright 1996 by International Business Machines Corpora- tion. Copying in printed form for private use is permitted without payment of royalty provided that (1) each reproduction is done without alteration and (2) the Journal reference and IBM copyright notice are included on the Urst page. The title and abstract, but no other portions, of this paper may be copied or distributed royalty free without further permission by computer-based and other infor- mation-service systems.

Permission to republish any other portion of this paper must be obtained from the Editor. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 0018-8670/96/$5.00 © 1996 IBM BENDER ET AL. Data hiding, a form of steganography, embeds data into digital media for the purpose of identiGcation, annotation, and copyright.

Several constraints affect this process: the quantity of data to be hidden, the need for invariance of these data under conditions where a chost d signal is subject to distortions, e.g., lossy compression, and the degree to which the data must be immune to interception, modiGcation, or removal by a third party. We explore both traditional and novel techniques for addressing the data-hiding process and evaluate these techniques in light of three applications: copyright protection, tamper- prooGng, and ... more. less.

augmentation data embedding. igital representation of media facilitates access and potentially improves the portability, efU- ciency, and accuracy of the information presented. Undesirable effects of facile data access include an increased opportunity for violation of copyright and tampering with or modiUcation of content. The moti- vation for this work includes the provision of protec- tion of intellectual property rights, an indication of content manipulation, and a means of annotation. Data hiding represents a class of processes used to embed data, such as copyright information, into vari- ous forms of media such as image, audio, or text with a minimum amount of perceivable degradation to the chost d signal; i.e., the embedded data should be invis- ible and inaudible to a human observer. Note that data hiding, while similar to compression, is distinct from encryption. Its goal is not to restrict or regulate access to the host signal, but rather to ensure that embedded data remain inviolate and recoverable. Two important uses of data hiding in digital media are to provide proof of the copyright, and assurance of content integrity. Therefore, the data should stay hid- den in a host signal, even if that signal is subjected to manipulation as degrading as Ultering, resampling, cropping, or lossy data compression. Other applica- tions of data hiding, such as the inclusion of augmen- tation data, need not be invariant to detection or removal, since these data are there for the beneUt of both the author and the content consumer. Thus, the techniques used for data hiding vary depending on the quantity of data being hidden and the required invari- ance of those data to manipulation. Since no one method is capable of achieving all these goals, a class of processes is needed to span the range of possible applications. The technical challenges of data hiding are formida- ble. Any choles d to Ull with data in a host signal, either statistical or perceptual, are likely targets for removal by lossy signal compression. The key to suc- cessful data hiding is the Unding of holes that are not suitable for exploitation by compression algorithms. A further challenge is to Ull these holes with data in a way that remains invariant to a large class of host sig- nal transformations. D Techniques for data hiding by W. Bender D. Gruhl N. Morimoto A. Lu BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 314 Features and applications Data-hiding techniques should be capable of embed- ding data in a host signal with the following restric- tions and features: 1.The host signal should be nonobjectionally degraded and the embedded data should be mini- mally perceptible. (The goal is for the data to remain hidden . As any magician will tell you, it is possible for something to be hidden while it remains in plain sight; you merely keep the person from looking at it. We will use the words hidden , inaudible , imperceivable , and invisible to mean that an observer does not notice the presence of the data, even if they are perceptible.) 2.The embedded data should be directly encoded into the media, rather than into a header or wrap- per, so that the data remain intact across varying data file formats. 3.The embedded data should be immune to modifi- cations ranging from intentional and intelligent attempts at removal to anticipated manipulations, e.g., channel noise, filtering, resampling, cropping, encoding, lossy compressing, printing and scan- ning, digital-to-analog ( D/A ) conversion, and ana- log-to-digital ( A/D ) conversion, etc. 4.Asymmetrical coding of the embedded data is desirable, since the purpose of data hiding is to keep the data in the host signal, but not necessarily to make the data difficult to access. 5.Error correction coding 1 should be used to ensure data integrity. It is inevitable that there will be some degradation to the embedded data when the host signal is modified. 6.The embedded data should be self-clocking or arbitrarily re-entrant. This ensures that the embed- ded data can be recovered when only fragments of the host signal are available, e.g., if a sound bite is extracted from an interview, data embedded in the audio segment can be recovered. This feature also facilitates automatic decoding of the hidden data, since there is no need to refer to the original host signal. Applications. Trade-offs exist between the quantity of embedded data and the degree of immunity to host signal modiUcation. By constraining the degree of host signal degradation, a data-hiding method can operate with either high embedded data rate, or high resistance to modiUcation, but not both. As one increases, the other must decrease. While this can be shown mathematically for some data-hiding systems such as a spread spectrum, it seems to hold true for all data-hiding systems. In any system, you can trade bandwidth for robustness by exploiting redundancy. The quantity of embedded data and the degree of host signal modiUcation vary from application to applica- tion. Consequently, different techniques are employed for different applications. Several prospective applica- tions of data hiding are discussed in this section. An application that requires a minimal amount of embedded data is the placement of a digital water mark. The embedded data are used to place an indica- tion of ownership in the host signal, serving the same purpose as an author 9s signature or a company logo. Since the information is of a critical nature and the signal may face intelligent and intentional attempts to destroy or remove it, the coding techniques used must be immune to a wide variety of possible modiUca- tions. A second application for data hiding is tamper-proof- ing. It is used to indicate that the host signal has been modiUed from its authored state. ModiUcation to the embedded data indicates that the host signal has been changed in some way. A third application, feature location, requires more data to be embedded. In this application, the embed- ded data are hidden in speciUc locations within an image. It enables one to identify individual content features, e.g., the name of the person on the left versus the right side of an image. Typically, feature location data are not subject to intentional removal. However, it is expected that the host signal might be subjected to a certain degree of modiUcation, e.g., images are routinely modiUed by scaling, cropping, and tone- scale enhancement. As a result, feature location data- hiding techniques must be immune to geometrical and nongeometrical modiUcations of a host signal. Trade-offs exist between the quantity of data and the immunity to modi"cation. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 315 Image and audio captions (or annotations) may require a large amount of data. Annotations often travel separately from the host signal, thus requiring additional channels and storage. Annotations stored in Ule headers or resource sections are often lost if the Ule format is changed, e.g., the annotations created in a Tagged Image File Format ( TIFF ) may not be present when the image is transformed to a Graphic Inter- change Format ( GIF ). These problems are resolved by embedding annotations directly into the data structure of a host signal. Prior work. Adelson 2 describes a method of data hid- ing that exploits the human visual system 9s varying sensitivity to contrast versus spatial frequency. Adel- son substitutes high-spatial frequency image data for hidden data in a pyramid-encoded still image. While he is able to encode a large amount of data efUciently, there is no provision to make the data immune to detection or removal by typical manipulations such as Ultering and rescaling. Stego, 3 one of several widely available software packages, simply encodes data in the least-signiUcant bit of the host signal. This tech- nique suffers from all of the same problems as Adel- son 9s method but creates an additional problem of degrading image or audio quality. Bender 4 modiUes Adelson 9s technique by using chaos as a means to encrypt the embedded data, deterring detection, but providing no improvement to immunity to host signal manipulation. Lippman 5 hides data in the chromi- nance channel of the National Television Standards Committee ( NTSC ) television signal by exploiting the temporal over-sampling of color in such signals. Typi- cal of Enhanced DeUnition Television Systems, this method encodes a large amount of data, but the data are lost to most recording, compression, and transcod- ing processes. Other techniques, such as Hecht 9s Data-Glyph, 6 which adds a bar code to images, are engineered in light of a predetermined set of geomet- ric modiUcations. 7 Spread-spectrum, 8-11 a promising technology for data hiding, is difUcult to intercept and remove but often introduces perceivable distortion into the host signal. Problem space. Each application of data hiding requires a different level of resistance to modiUcation and a different embedded data rate. These form the theoretical data-hiding problem space (see Figure 1). There is an inherent trade-off between bandwidth and crobustness, d or the degree to which the data are immune to attack or transformations that occur to the host signal through normal usage, e.g., compression, resampling, etc. The more data to be hidden, e.g., a caption for a photograph, the less secure the encoding. The less data to be hidden, e.g., a watermark, the more secure the encoding. Data hiding in still images Data hiding in still images presents a variety of chal- lenges that arise due to the way the human visual sys- tem ( HVS ) works and the typical modiUcations that images undergo. Additionally, still images provide a relatively small host signal in which to hide data. A fairly typical 8-bit picture of 200 × 200 pixels pro- vides approximately 40 kilobytes (kB) of data space in which to work. This is equivalent to only around 5 seconds of telephone-quality audio or less than a sin- gle frame of NTSC television. Also, it is reasonable to expect that still images will be subject to operations ranging from simple afUne transforms to nonlinear transforms such as cropping, blurring, Ultering, and lossy compression. Practical data-hiding techniques need to be resistant to as many of these transforma- tions as possible. Despite these challenges, still images are likely candi- dates for data hiding. There are many attributes of the HVS that are potential candidates for exploitation in a data-hiding system, including our varying sensitivity to contrast as a function of spatial frequency and the masking effect of edges (both in luminance and Figure 1Conceptual data-hiding problem space ROBUSTNESS BANDWIDTH EXTENT OF CURRENT TECHNIQUES BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 316 chrominance). The HVS has low sensitivity to small changes in luminance, being able to perceive changes of no less than one part in 30 for random patterns. However, in uniform regions of an image, the HVS ismore sensitive to the change of the luminance, approximately one part in 240. A typical CRT (cathode ray tube) display or printer has a limited dynamic range. In an image representation of one part in 256, e.g., 8-bit gray levels, there is potentially room to hide data as pseudorandom changes to picture brightness. Another HVS chole d is our relative insensitivity to very low spatial frequencies such as continuous changes in brightness across an image, i.e., vignett- ing. An additional advantage of working with still images is that they are noncausal. Data-hiding tech- niques can have access to any pixel or block of pixels at random. Using these observations, we have developed a variety of techniques for placing data in still images. Some techniques are more suited to dealing with small amounts of data, while others to large amounts. Some techniques are highly resistant to geometric modiUca- tions, while others are more resistant to nongeometric modiUcations, e.g., Ultering. We present methods that explore both of these areas, as well as their combina- tion. Low bit-rate data hiding With low bit-rate encoding, we expect a high level of robustness in return for low bandwidth. The emphasis is on resistance to attempts of data removal by a third party. Both a statistical and a perceptual technique are discussed in the next sections on Patchwork, texture, and applications. Patchwork: A statistical approach The statistical approach, which we refer to as Patch- work , is based on a pseudorandom, statistical process. Patchwork invisibly embeds in a host image a speciUc statistic, one that has a Gaussian distribution. Figure 2 shows a single iteration in the Patchwork method . Two patches are chosen pseudorandomly, the Urst A, the second B. The image data in patch A are lightened while the data in patch B are darkened (exaggerated for purposes of this illustration). This unique statistic indicates the presence or absence of a signature. Patchwork is independent of the contents of the host image. It shows reasonably high resistance to most nongeometric image modiUcations. For the following analysis, we make the following simplifying assumptions (these assumptions are not limiting, as is shown later): We are operating in a 256 level, linearly quantized system starting at 0; all brightness levels are equally likely; all samples are independent of all other samples. The Patchwork algorithm proceeds as follows: take any two points, A and B , chosen at random in an image. Let a equal the brightness at point A and b the brightness at point B . Now, let (1) The expected value of S is 0, i.e., the average value of S after repeating this procedure a large number of times is expected to be 0. Sab 3 = Figure 2A single iteration in the Patchwork method (photograph courtesy of Webb Chapel) IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 317 Although the expected value is 0, this does not tell us much about what S will be for a speciUc case. This is because the variance is quite high for this procedure. The variance of S , Ã s is a measure of how tightly sam- ples of S will cluster around the expected value of 0. To compute this, we make the following observation: Since S = a 2 b and a and b are assumed independent, can be computed as follows (this, and all other probability equations are from Drake 12 ): (2) where for a uniform S is: (3) Now, since a and b are samples from the same set, taken with replacement. Thus: (4) which yields a standard deviation Ã S H 104. This means that more than half the time, S will be greater than 43 or less than 2 43. Assuming a Gaussian clus- tering, a single iteration does not tell us much. How- ever, this is not the case if we perform the procedure many times. Let us repeat this procedure n times, letting a i and b i be the values a and b take on during the i th iteration, S i . Now let S n be deUned as: (5) The expected value of S n is: (6) This makes intuitive sense, since the number of times a i is greater than b i should be offset by the number of times the reverse is true. Now the variance is: (7) And the standard deviation is: (8) Now, we can compute S 10000 for a picture, and if it var- ies by more than a few standard deviations, we can be fairly certain that this did not happen by chance. In fact, since as we will show later S 2 n for large n has a Gaussian distribution, a deviation of even a few Ã S 2 s indicates to a high degree of certainty the presence of encoding (see Table 1). The Patchwork method artiUcially modiUes S for a given picture, such that S 2 n is many deviations away from expected. To encode a picture, we: 1.Use a specific key for a known pseudorandom number generator to choose ( a i , b i ). This is impor- tant, because the encoder needs to visit the same points during decoding. 2.Raise the brightness in the patch a i by an amount ´ , typically in the range of 1 to 5 parts in 256. 3.Lower the brightness in b i by this same amount ´ (the amounts do not have to be the same, as long as they are in opposite directions). 4.Repeat this for n steps ( n typically ~10000). Now, when decoded, S 2 n will be: (9) or: (10) So each step of the way we accumulate an expectation of 2 × ´ . Thus after n repetitions, we expect S 2 n to be: Ã S 2 Ã S 2 Ã a 2 Ã b 2 + = Ã a 2 Ã a 2 5418 H Ã a 2 Ã b 2 = Ã S 2 2 Ã × a 2 2 2550 3 () 2 12 ------------------------ × 10836 HH = S n S i i 1 = n 1 a i b i 3 i 1 = n 1 == S n nS × n 0 × 0 === Ã S n 2 n Ã S 2 × = Ã S n n Ã × n 104 × H = S n 2 a i ´ + () b i ´ 3 () 3 i 1 = n 1 = S n 2 2 ´ na i b i 3 () i 1 = n 1 + = Table 1Degree of certainty of encoding given deviation from that expected in a Gaussian distribution ( ´ =2) Standard Deviations Away Certainty n 0 1 2 3 50.00% 84.13% 97.87% 99.87% 0 679 2713 6104 BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 318 (11) As n or ´ increases, the distribution of S 2 n shifts over to the right (Figure 3 and Table 1). In Figure 3, as ´ or n increases, the distribution of S 2 n shifts further to the right. If we shift it far enough, any point that is likely to fall into one distribution is highly unlikely to be near the center of the other distribution. While this basic method works well by itself, we have made a number of modiUcations to improve perfor- mance including: 1.Treating patches of several points rather than sin- gle points. This has the effect of shifting the noise introduced by Patchwork into the lower spatial fre- quencies, where it is less likely to be removed by lossy compression and typical Finite Impulse Response ( FIR ) filters. 2.Making Patchwork more robust by using a combi- nation with either affine coding (described later) or some heuristic based upon feature recognition (e.g., alignment using the interocular line of a face). Patchwork decoding is sensitive to affine transformations of the host image. If the points in the picture visited during encoding are offset by translation, rotation, or scaling before decoding, the code is lost. 3.Taking advantage of the fact that Patchwork is fairly resistant to cropping. By disregarding points outside of the known picture area, Patchwork degrades in accuracy approximately as the log of the picture size. Patchwork is also resistant to gamma and tone scale correction since values of comparable luminance move roughly the same way under such modifications. Patch shape. The shape of the patches deserves some comment. Figure 4 shows three possible one-dimen- sional patch shapes, and next to them a very approxi- mate spectrum of what a line with these patches dropped onto it pseudorandomly would look like. In Figure 4A, the patch is very small, with sharp edges. This results in the majority of the energy of the patch being concentrated in the high frequency portion of the image spectrum. This makes the distortion hard to see, but also makes it a likely candidate for removal by lossy compressors. If one goes to the other extreme, as in Figure 4B, the majority of the informa- tion is contained in the low-frequency spectrum. The 2 ´ n Ã S n 2 --------- 0.028 ´ n H Figure 3As ´ or n increases, the distribution of S ´ n shifts further to the right. 04 TO 8 STANDARD DEVIATIONS Figure 4The contour of a patch largely determines which frequencies will be modiGed by the application of Patchwork. À 0 (A) (B) (C) PATCH MODIFIED À À 0 0 FREQUENCIES Figure 5Patch placement affects patch visibility. RECTILINEARHEXAGONALRANDOM (A)(B)(C) IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 319 last choice, Figure 4C shows a wide, sharp-edged patch, which tends to distribute the energy around the entire frequency spectrum. The optimal choice of patch shape is dependent upon the expected image modiUcations. If JPEG (Joint Pho- tographic Experts Group) encoding is likely, then a patch that places its energy in the low frequencies is preferable. If contrast enhancement is to be done, placing energy in higher frequencies would be better. If the potential image modiUcations are unknown, then spreading the patch energy across the spectrum would make sense. The arrangement of patches has an impact on patch visibility. For illustration, three possibilities are con- sidered (Figure 5). The simplest method is shown in Figure 5A, a simple rectilinear lattice. While simple, this arrangement is often a poor choice if a high n is to be used. As the grid is Ulled in, continuous edges of gradient are formed. The HVS is very sensitive to such edges. A second choice, Figure 5B breaks this sym- metry by using hexagons for the patch shape. A pre- ferred solution, shown in Figure 5C, is a completely random placement of patches. An intelligent selection of patch shape in both the horizontal and vertical dimensions will enhance the effectiveness of patch- work for a given picture. Uniformity. A simplifying assumption of a uniform luminance histogram was made above, but this is not a requirement of Patchwork. The only assumption Patchwork makes is that the expected value of S i = a i 2 b i is zero. It can be shown that this condition is always met through the following argument: 1.Let a r be the time reversed series of a . 2. A r = A * by definition ( A * is the complex conjugate of A ) . 3. F ( a 7 a r ) = AA * ( F is the Fourier transform). 4. AA * is everywhere real by definition of the com- plex conjugate. 5. F 31 ( AA * ) is even by definition. 6.Even sequences are symmetric around zero by def- inition. An image histogram (Figure 6, top) is a somewhat random distribution. The result of taking the complex conjugate (Figure 6, bottom) is symmetric around zero. Figure 6A histogram of Figure 2 and its autocorrelation Figure 7A histogram of the variance of the luminance of 365 Associated Pressphotos from March1996 0246810121416 500000 450000 400000 350000 300000 250000 200000 150000 100000 50000 0 315 310 35051015 2.5e +11 2e +11 1.5e +11 1e +11 5e +10 0 02000400060008000 50 45 40 35 30 25 20 15 10 5 0 10000 VARIANCE FROM (5418) EQUATION 3 BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 320 Variance. When searching through a large number of images with data embedded using the Patchwork method, such as when a robot is looking for copyright violations on the Internet World Wide Web ( WWW ), the use of a generic estimation of variance is desir- able. This avoids the necessity of calculating the vari- ance of every image. Suspect images can then be examined thoroughly. When, in the analysis above, the number of points needed in Equation 3 was computed, the variance of the luminance was assumed to be 5418. This assump- tion turns out to be higher than the average observed values (see Figure 7). The question is, then, what value should be used. An examination of the variance of 365 Associated Pressphotos from March 1996 yielded an average value of 3877.4 and a distribution that can be seen in Figure 7. While some pictures do have variances as high as two-thirds of the maximum, most are clus- tered around the lower variance values. Thus, 5418, the estimate derived from the uniformity assumption, is a conservative but reasonable value to use for a generic picture. A minimum value is that for a solid color picture (Fig- ure 8A). This has a variance of 0, a standard deviation of 0, and thus works very well for Patchwork, since any modiUcation is evident. The other extreme is that of a two-color, black and white picture. For these, the variance is: (12) These two values, 0 and 16256, deUne the extremes of the variance to consider when calculating the likeli- hood that a picture is encoded. What is the correct assumption to use for a given picture? The actual vari- ance of the picture being examined is a sensible choice, since in most cases Patchwork will increase the variance only slightly. (This depends on the size and depth of the patch, the number of patches, and the histogram of the original image.) However, if a large number of pictures are to examined, a generic value is a practical choice. Summary. There are several limitations inherent to the Patchwork technique. The Urst is the extremely low embedded data rate it yields, usually a one-bit signature per image. This limits its usefulness to low bit-rate applications such as the digital watermark. Second, it is necessary to register where the pixels in the image lie. While a number of methods have been investigated, it is still somewhat difUcult to decode the image in the presence of severe afUne transforma- tions. These disadvantages aside, without the key for the pseudorandom number generator, it is extremely difUcult to remove the Patchwork coding without degrading the picture beyond recognition. The Patchwork method is subject to cryptographic attack if it is used to encode a large number of identi- cally sized images using the same key. If the images are averaged together, the patches will show up as lighter or darker than average regions. This weakness is a common one in cryptography, and points to the truism that for a static key, as the amount of trafUc increases, it becomes easier to ccrack d the encryption. One solution is to use multiple pseudorandom pat- terns for the patches. Even the use of just two keys, while increasing decoding time, will make Patchwork much more robust to attack. Another solution is to use the same pattern, but to reverse the polarity of the patches. Both solutions deter cryptographic attack by averaging. Texture Block Coding: A visual approach A second method for low bit-rate data hiding in images is Texture Block Coding . This method hides data within the continuous random texture patterns of a picture. The Texture Block Coding technique is 0127 3 () 2 2 ------------------------ 255127.5 3 () 2 2 ----------------------------------- +16256 H Figure 8Histograms of pictures with minimum (A) and maximum (B) variance MINMAX ANY (A)(B) IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 321 implemented by copying a region from a random tex- ture pattern found in a picture to an area that has simi- lar texture. This results in a pair of identically textured regions in the image (see Figure 9). These regions can be detected as follows: 1.Autocorrelate the image with itself. This will pro- duce peaks at every point in the autocorrelation where identical regions of the image overlap. If large enough areas of an image are copied, this will produce an additional large autocorrelation peak at the correct alignment for decoding. 2.Shift the image as indicated by the peaks in Step 1. Now subtract the image from its shifted copy, pad- ding the edges with zeros as needed. 3.Square the result and threshold it to recover only those values quite close to zero. The copied region will be visible as these values. Since the two regions are identical, they are modiUed in the same way if the picture is uniformly trans- formed. By making the regions reasonably large, the inner part of the block changes identically under most nongeometric transformations. In our experiments, coded 16 × 16 pixel blocks can be decoded when the picture is subjected to a combination of Ultering, com- pression, and rotation. Texture Block Coding is not without its disadvan- tages. Currently it requires a human operator to choose the source and destination regions, and to eval- uate the visual impact of the modiUcations on the image. It should be possible to automate this process by allowing a computer to identify possible texture regions in the image to copy from and paste to. How- ever, this technique will not work on images that lack moderately large areas of continuous texture from which to draw. Figure 9Texture Block Coding example (photograph courtesy of Webb Chapel) BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 322 Future research in this area includes the possibility of cutting and pasting blocks from only part of the image frequency spectrum (this would allow less noticeable blocks to be moved around, and a Unal encoding that is considerably more robust to various image com- pression algorithms) along with automatic texture region selection and analysis of perceivability of the Unal result. High bit-rate coding High bit-rate methods can be designed to have mini- mal impact upon the perception of the host signal, but they do not tend to be immune to image modiUca- tions. In return, there is an expectation that a relatively large amount of data are able to be encoded. The most common form of high bit-rate encoding is the replace- ment of the least signiUcant luminance bit of image data with the embedded data. Other techniques include the introduction of high-frequency, low- amplitude noise and the use of direct sequence spread spectrum coding. All high bit-rate methods can be made more robust through the use of error-correction coding, at the expense of data rate. High bit-rate codes are only appropriate where it is reasonable to expect that a great deal of control will be maintained over the images. Individually, none of the known techniques for data hiding are resistant to all possible transforms or com- binations of transforms. In combination, often one technique can supplement another. Supplementary techniques are particularly important for recovery from geometric modiUcations such as afUne transfor- mations, and maintaining synchronization for spread- spectrum encoding. Af)ne coding. Some of the data-hiding techniques, such as Patchwork, are vulnerable to afUne trans- forms. It makes sense to develop methods that can be used to facilitate the recovery of embedded data after afUne application. Af>ne coding is one such method: A predeUned reference pattern is embedded into a host image using any of the high bit-rate coding tech- niques. Estimation of geometric transformation of the image is achieved by comparing the original shape, size, and orientation of the reference pattern to that found in the transformed image. Since afUne trans- forms are linear, the inverse transform can be applied to recover the original image. Once this is done, the image is ready for further extraction of embedded data. Applications Placing data in images is useful in a variety of appli- cations. We highlight below four applications that dif- fer in the quantity of data to be embedded and the type of transforms to which the data are likely to be sub- jected. Digital watermark. The objective of a digital water- mark is to place an indelible mark on an image. Usu- ally, this means encoding only a handful of bits, sometimes as few as one. This csignature d could be used as a means of tracing the distribution of images for an on-line news service and for photographers who are selling their work for digital publication. One could build a digital camera that places a watermark on every photograph it takes. Theoretically, this would allow photographers to employ a cweb-search- ing agent d to locate sites where their photographs appear. It can be expected that if information about legal own- ership is to be included in an image, it is likely that someone might want to remove it. A requirement of a digital watermark is that it must be difUcult to remove. Both the Patchwork and Texture Block Coding tech- niques show promise as digital watermarks. Patch- work, being the more secure of the two, answers the question cIs this my picture? d Texture Block Coding, which can be made readily accessible to the public, answers the question cWhose picture is this? d Figure 10Characterizing the difference between tamper-prooGng and other data-hiding techniques EFFORT (A) (B) MODIFICATION IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 323 Tamper-proo)ng. The objective of tamper-prooUng is to answer the question, cHas this image been modi- Ued? d Tamper-prooUng techniques are related, but distinct from the other data-hiding technologies. What differentiates them is the degree to which information is secured from the host signal. In Figure 10, the dif- ference between tamper-prooUng and other data-hid- ing techniques is characterized. Figure 10A illustrates that data hiding requires a deep information well that is resilient to large displacements. Figure 10B illus- trates that tamper-prooUng requires a shallow well that is only resilient to small displacements, but is triggered by large displacements. Most data-hiding techniques attempt to secure data in the face of all modiUcations. Tamper-prooUng techniques must be resilient to small modiUcations (e.g., cropping, tone- scale or gamma correction for images or balance or equalization for sounds) but not to large modiUcations (e.g., removing or inserting people from an image or taking words out of context in an audio recording). There are several ways to implement tamper-prooUng. The easiest way is to encode a check-sum of the image within the image. However, this method is trig- gered by small changes in the image. This suggests an approach involving a pattern overlaid on the image. The key to a successful overlay is to Und a pattern resilient to simple modiUcations such as Ultering and gamma correction, yet is not easily removed. The search for such patterns and other methods of detect- ing tampering remains an active area of research. Feature tagging. Another application of data hiding is tagging the location of features within an image. Using data hiding it is possible for an editor (or machine) to encode descriptive information, such as the location and identiUcation of features of interest, directly into speciUc regions of an image. This enables retrieval of the descriptive information wher- ever the image goes. Since the embedded information is spatially located in the image, it is not removed unless the feature of interest is removed. It also trans- lates, scales, and rotates exactly as the feature of inter- est does. This application does not have the same requirements for robustness as the digital watermark. It can be assumed that, since feature location is providing a ser- vice, it is unlikely someone will maliciously try to remove the encoded information. Embedded captions. Typical news photograph cap- tions contain one kB of data. Thus embedded captions is a relatively high bit-rate application for data hiding. As with feature tagging, caption data are usually not subject to malicious removal. While captions are useful by themselves, they become even more useful when combined with feature loca- tion. It is then possible for portions of the caption to directly reference items in the picture. Captions can become self-editing once this is done. If an item refer- enced in the caption is cropped out of the picture, then the reference to that item in the caption can be removed automatically. Data hiding in audio Data hiding in audio signals is especially challenging, because the human auditory system ( HAS ) operates over a wide dynamic range. The HAS perceives over a range of power greater than one billion to one and a range of frequencies greater than one thousand to one. Sensitivity to additive random noise is also acute. The perturbations in a sound Ule can be detected as low as one part in ten million (80 dB below ambient level). However, there are some choles d available. While the HAS has a large dynamic range, it has a fairly small differential range. As a result, loud sounds tend to mask out quiet sounds. Additionally, the HAS is unable to perceive absolute phase, only relative phase. Finally, there are some environmental distortions so common as to be ignored by the listener in most cases. We exploit many of these traits in the methods we dis- cuss next, while being careful to bear in mind the extreme sensitivities of the HAS . Audio environments When developing a data-hiding method for audio, one of the Urst considerations is the likely environments the sound signal will travel between encoding and decoding. There are two main areas of modiUcation which we will consider. First, the storage environ- ment, or digital representation of the signal that will be used, and second the transmission pathway the sig- nal might travel. Digital representation. There are two critical param- eters to most digital audio representations: sample quantization method and temporal sampling rate. The most popular format for representing samples of high-quality digital audio is a 16-bit linear quantiza- BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 324 tion, e.g., Windows Audio-Visual ( WAV ) and Audio Interchange File Format ( AIFF ). Another popular for- mat for lower quality audio is the logarithmically scaled 8-bit µ -law. These quantization methods intro- duce some signal distortion, somewhat more evident in the case of 8-bit µ -law. Popular temporal sampling rates for audio include 8kHz (kilohertz), 9.6 kHz, 10 kHz, 12 kHz, 16 kHz, 22.05kHz, and 44.1 kHz. Sampling rate impacts data hiding in that it puts an upper bound on the usable portion of the frequency spectrum (if a signal is sam- pled at ~8kHz, you cannot introduce modiUcations that have frequency components above ~4 kHz). For most data-hiding techniques we have developed, usable data space increases at least linearly with increased sampling rate. A last representation to consider is that produced by lossy, perceptual compression algorithms, such as the International Standards Organization Motion Pictures Expert Group 4Audio ( ISO MPEG-AUDIO ) perceptual encoding standard. These representations drastically change the statistics of the signal; they preserve only the characteristics that a listener perceives (i.e., it will sound similar to the original, even if the signal is com- pletely different in a least squares sense). Transmission environment. There are many differ- ent transmission environments that a signal might experience on its way from encoder to decoder. We consider four general classes for illustrative purposes (see Figure 11). The Urst is the digital end-to-end environment (Figure 11A). This is the environment of a sound Ule that is copied from machine to machine, but never modiUed in any way. As a result, the sam- pling is exactly the same at the encoder and decoder. This class puts the least constraints on data-hiding methods. The next consideration is when a signal is resampled to a higher or lower sampling rate, but remains digital throughout (Figure 11B). This transform preserves the absolute magnitude and phase of most of the signal, but changes the temporal characteristics of the signal. The third case is when a signal is cplayed d into an analog state, transmitted on a reasonably clean analog line and resampled (Figure 11C). Absolute signal magnitude, sample quantization, and temporal sam- pling rate are not preserved. In general, phase will be preserved. The last case is when the signal is cplayed into the air d and cresampled with a microphone d (Figure 11D). The signal will be subjected to possibly unknown nonlinear modiUcations resulting in phase changes, amplitude changes, drift of different fre- quency components, echoes, etc. Signal representation and transmission pathway must be considered when choosing a data-hiding method. Data rate is very dependent on the sampling rate and the type of sound being encoded. A typical value is 16bps, but the number can range from 2 bps to 128bps. Low-bit coding Low-bit coding is the simplest way to embed data into other data structures. By replacing the least signiUcant bit of each sampling point by a coded binary string, we can encode a large amount of data in an audio sig- nal. Ideally, the channel capacity is 1 kb per second (kbps) per 1 kilohertz (kHz), e.g., in a noiseless chan- Figure 11Transmission environments SOURCE SOURCE SOURCE SOURCE DESTINATION DIGITAL RESAMPLED ANALOG cOVER THE AIR d (A) (B) (C) (D) DESTINATION DESTINATION DESTINATION IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 325 nel, the bit rate will be 8 kbps in an 8 kHz sampled sequence and 44 kbps in a 44 kHz sampled sequence. In return for this large channel capacity, audible noise is introduced. The impact of this noise is a direct function of the content of the host signal, e.g., crowd noise during a live sports event would mask low-bit encoding noise that would be audible in a string quar- tet performance. Adaptive data attenuation has been used to compensate this variation. The major disadvantage of this method is its poor immunity to manipulation. Encoded information can be destroyed by channel noise, resampling, etc., unless it is encoded using redundancy techniques. In order to be robust, these techniques reduce the data rate, often by one to two orders of magnitude. In prac- tice, this method is useful only in closed, digital-to- digital environments. Phase coding The phase coding method works by substituting the phase of an initial audio segment with a reference phase that represents the data. The phase of subse- quent segments is adjusted in order to preserve the relative phase between segments. Phase coding, when it can be used, is one of the most effective coding methods in terms of the signal-to- perceived noise ratio. When the phase relation between each frequency component is dramatically changed, a noticeable phase dispersion will occur. However, as long as the modiUcation of the phase is sufUciently small (sufUciently small depends on the observer; professionals in broadcast radio can detect modiUcations that are imperceivable to an average observer), an inaudible coding can be achieved. Procedure. The procedure for phase coding is as fol- lows: 1.Break the sound sequence s [ i ], (0 d i d I 2 1), into a series of N short segments, s n [ i ] where (0 d n d N 2 1) (Figure 12A, 12B). 2.Apply a K-points discrete Fourier transform ( DFT ) 13 to n -th segment, s n [ i ], where ( K = I/N ), and create a matrix of the phase, Æ n ( É k ), and magni- tude, A n ( É k ) for (0 d k d K 2 1) (Figure 12C). 3.Store the phase difference between each adjacent segment for (0 d n d N 2 1) (Figure 12D): (13) Æ n 1 + É k ()Æ n 1 + É k ()Æ n É k () 3 = Figure 12Phase coding schematic (A) ORIGINAL SOUND SIGNAL (B) BREAK INTO N SEGMENTS S (C) TRANSFORM EACH SEGMENT INTO MAGNITUDE (D) CALCULATE THE PHASE DIFFERENCE BETWEEN (E) FOR SEGMENT S 0 CREATE AN ARTIFICIAL (F) FOR ALL OTHER SEGMENTS, CREATE NEW (G) COMBINE NEW PHASE AND ORIGINAL MAGNITUDE (H) CONCATENATE NEW SEGMENTS TO CREATE OUTPUT S 0 S 1 S 2 S N 3 1 A n S 2 n Æ n Æ2 0 Æ n É É É CONSECUTIVE SEGMENTS Æ n +1 2 Æ n É TO GET NEW SEGMENT S 2 n AND PHASE PHASE FRAMES ( Æ 2 0 + Æ 1 ) Æ 2 1 ABSOLUTE PHASE Æ 2 0 BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 326 4.A binary set of data is represented as a Æ data =À /2 or 2 À /2 representing 0 or 1 (Figure 12E): (14) 5.Re-create phase matrixes for n > 0 by using the phase difference (Figure 12F): (15) 6.Use the modified phase matrix Æ2 n ( É k ) and the orig- inal magnitude matrix A n ( É k ) to reconstruct the sound signal by applying the inverse DFT (Figure 12G, 12H). For the decoding process, the synchronization of the sequence is done before the decoding. The length of the segment, the DFT points, and the data interval must be known at the receiver. The value of the underlying phase of the Urst segment is detected as a 0 or 1, which represents the coded binary string. Since Æ2 0 ( É k ) is modiUed, the absolute phases of the following segments are modiUed respectively. How- ever, the relative phase difference of each adjacent frame is preserved. It is this relative difference in phase that the ear is most sensitive to. Evaluation. Phase dispersion is a distortion caused by a break in the relationship of the phases between each of the frequency components. Minimizing phase dis- persion constrains the data rate of phase coding. One cause of phase dispersion is the substitution of phase Æ2 0 ( É k ) with the binary code. The magnitude of the phase modiUer needs to be close to the original value in order to minimize distortion. The difference between phase modiUer states should be maximized in order to minimize the susceptibility of the encoding to noise. In our modiUed phase representation, a 0-bit is 2 À /2 and a 1-bit is + À /2. Another source of distortion is the rate of change of the phase modiUer. If distortion is applied to every bin of the DFT it is likely to break the phase relationship of the adjacent frequency components, resulting in a beat pattern. By changing the phase more slowly and tran- sitioning between phase changes, the audible distor- tion is greatly reduced. In Figure 13, a sharp versus smooth transition is illustrated. In Figure 13A, the edges of the phase transitions are sharp, causing noticeable distortion. In Figure 13B, they are smooth, reducing this. Note that in each case, the data points appear in the same place. This smooth variation has the disadvantage of causing a reduction in bandwidth, as space has to be left between each data point to allow for smooth transition. Results. In our experiments, the phase coding channel capacity typically varied from 8 bps to 32 bps, depending on the sound context. A channel capacity of ~8 bps can be achieved by allocating 128 frequency slots per bit under conditions of little background noise. Capacities of 16 bps to 32 bps can be achieved by allocating 32 to 64 frequency slots per slot when there is a noisy background. Spread spectrum In a normal communication channel, it is often desir- able to concentrate the information in as narrow a region of the frequency spectrum as possible in order to conserve available bandwidth and to reduce power. The basic spread spectrum technique, on the other hand, is designed to encode a stream of information by spreading the encoded data across as much of the frequency spectrum as possible. This allows the signal reception, even if there is interference on some fre- quencies. While there are many variations on spread spectrum communication, we concentrated on Direct Sequence Spread Spectrum encoding ( DSSS ). The DSSS method spreads the signal by multiplying it by a chip , a maxi- mal length pseudorandom sequence modulated at a Æ 0 2 Æ data 2 = Æ 1 2 É k ()Æ 0 2 É k () Æ 1 É k () + = () & Æ n 2 É k ()Æ n 1 3 2 É k () Æ n É k () + = () & Æ N 2 É k ()Æ N 1 3 2 É k () Æ N É k () + = () Figure 13Sharp verses smooth transition Æ É (A)(B) Æ É IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 327 known rate. Since the host signals are in discrete-time format, we can use the sampling rate as the chip rate for coding. The result is that the most difUcult prob- lem in DSSS receiving, that of establishing the correct start and end of the chip quanta for phase locking pur- poses, is taken care of by the discrete nature of the signal. Consequently, a much higher chip rate, and therefore a higher associated data rate, is possible. Without this, a variety of signal locking algorithms may be used, but these are computationally expensive. Procedure. In DSSS , a key is needed to encode the information and the same key is needed to decode it. The key is pseudorandom noise that ideally has Vat frequency response over the frequency range, i.e., white noise. The key is applied to the coded informa- tion to modulate the sequence into a spread spectrum sequence. The DSSS method is as follows: 8,9 The code is multi- plied by the carrier wave and the pseudorandom noise sequence, which has a wide frequency spectrum. As a consequence, the spectrum of the data is spread over the available band. Then, the spread data sequence is attenuated and added to the original Ule as additive random noise (see Figure 14). DSSS employs bi-phase shift keying since the phase of the signal alternates each time the modulated code alternates (see Figure 15). For decoding, phase values Æ 0 and Æ 0 + À are interpreted as a c0 d or a c1, d which is a coded binary string. In the decoding stage, the following is assumed: 1.The pseudorandom key is maximal (it has as many combinations as possible and does not repeat for as long as possible). Consequently it has a relatively flat frequency spectrum. 2.The key stream for the encoding is known by the receiver. Signal synchronization is done, and the start/stop point of the spread data are known. 3.The following parameters are known by the receiver: chip rate, data rate, and carrier frequency. Results. Unlike phase coding, DSSS introduces addi- tive random noise to the sound. To keep the noise level low and inaudible, the spread code is attenuated (without adaptation) to roughly 0.5 percent of the dynamic range of the host sound Ule. The combina- tion of simple repetition technique and error correc- tion coding ensure the integrity of the code. A short segment of the binary code string is concatenated and added to the host signal so that transient noise can be reduced by averaging over the segment in the decod- ing stage. The resulting data rate of the DSSS experi- ments is 4 bps. Echo data hiding Echo data hiding embeds data into a host audio signal by introducing an echo . The data are hidden by vary- ing three parameters of the echo: initial amplitude, decay rate, and offset (see Figure 16). As the offset (or Figure 14Spread spectrum encoding Figure 15Synthesized spread spectrum information encoded by the direct sequence method ENCODER OUTPUT CARRIER cCHIP d SIGNALDATA SIGNAL cCHIP d SIGNAL INPUT DECODER BAND-PASSPHASE FILTERDETECTOR DATA CARRIER WAVE PSEUDORANDOM SIGNAL ( cCHIP d) BINARY STRING (CODE) CODED 1 0 2 1 1 0 2 1 1 0 2 1 1 0 2 1 WAVEFORM BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 328 delay) between the original and the echo decreases, the two signals blend. At a certain point, the human ear cannot distinguish between the two signals. The echo is perceived as added resonance. (This point is hard to determine exactly. It depends on the quality of the original recording, the type of sound being ech- oed, and the listener. In general, we Und that this fusion occurs around 1/1000 of a second for most sounds and most listeners.) The coder uses two delay times, one to represent a binary one (offset) and another to represent a binary zero (offset + delta). Both delay times are below the threshold at which the human ear can resolve the echo. In addition to decreasing the delay time, we can also ensure that the information is not perceivable by setting the initial amplitude and the decay rate below the audible threshold of the human ear. Encoding. The encoding process can be represented as a system that has one of two possible system func- tions. In the time domain, the system functions are discrete time exponentials (see Figure 17) differing only in the delay between impulses. For simplicity, we chose an example with only two impulses (one to copy the original signal and one to create an echo). Increasing the number of impulses is what increases the number of echoes. We let the kernel shown in Figure 18A represent the system function for encoding a binary one and we use the system function deUned in Figure 18B to encode a zero. Processing a signal through either Figures 18A or 18B will result in an encoded signal (see Figure 19). The delay ( ´ b ) between the original signal and the echo is dependent on which kernel or system function we use in Figure 19. The cone d kernel (Figure 18A) is created with a delay of ( ´ 1 ) seconds while the czero d kernel (Figure 18B) has a ( ´ 0 ) second delay. In order to encode more than one bit, the original sig- nal is divided into smaller portions. Each individual portion can then be echoed with the desired bit by considering each as an independent signal. The Unal encoded signal (containing several bits) is the recom- bination of all independently encoded signal portions. In Figure 20, the example signal has been divided into seven equal portions labeled a, b, c, d, e, f, and g. We want portions a, c, d, and g to contain a one. There- Figure 17Discrete time exponential Figure 18Echo kernels (A) cONE d KERNEL(B) cZERO d KERNEL ´ 1 ´ 0 Figure 16Adjustable parameters ORIGINAL SIGNAL cZERO d cONE d OFFSETDELTA DECAY RATE INITIAL AMPLITUDE IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 329 fore, we use the cone d kernel (Figure 18A) as the sys- tem function for each of these portions. Each portion is individually convolved with the system function. The zeros encoded into sections b, e, and f are encoded in a similar manner using the czero d kernel (Figure 18B). Once each section has been individually convolved with the appropriate system function, the results are recombined. To achieve a less noticeable mix, we create a cone d echo signal by echoing the original signal using the cone d kernel. The czero d ker- nel is used to create the czero d echo signal. The resulting signals are shown in Figure 21. The cone d echo signal and the czero d echo signal con- tain only ones and zeros, respectively. In order to combine the two signals, two mixer signals (see Fig- ure 22) are created. The mixer signals are either one or zero depending on the bit we would like to hide in that portion of the original signal. The cone d mixer signal is multiplied by the cone d echo signal while the czero d mixer signal is multi- plied by czero d echo signal. In other words, the echo signals are scaled by either 1 or 0 throughout the sig- nal depending on what bit any particular portion is supposed to contain. Then the two results are added. Note that the czero d mixer signal is the complement of the cone d mixer signal and that the transitions within each signal are ramps. The sum of the two mixer signals is always one. This gives us a smooth transition between portions encoded with different bits and prevents abrupt changes in the resonance of the Unal (mixed) signal. A block diagram representing the entire encoding pro- cess is illustrated in Figure 23. Decoding. Information is embedded into a signal by echoing the original signal with one of two delay ker- nels. A binary one is represented by an echo kernel with a ( ´ 1 ) second delay. A binary zero is represented by a ( ´ 0 ) second delay. Extraction of the embedded information involves the detection of spacing between the echoes. In order to do this, we examine the magni- tude (at two locations) of the autocorrelation of the encoded signal 9s cepstrum: 14 (16) The following procedure is an example of the decod- ing process. We begin with a sample signal that is a series of impulses such that the impulses are separated by a set interval and have exponentially decaying F 1 3 ln complex Fx () () 2 () Figure 19Echoing example Figure 20Divide the original signal into smaller portions to encode information Figure 21The Grst step in encoding process is to create a cone d and a czero d echo signal (purple line is the echoed signal) Figure 22Mixer signals h(t) ´ b ´ b ORIGINAL SIGNALOUTPUT abcdefg 1011001 abcdefg 1011001 1011001 ´ 1 ´ 0 abcdefg 1011001 0 1 0 1 cONE d MIXER SIGNAL cZERO d MIXER SIGNAL BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 330 amplitudes. The signal is zero elsewhere (see Figure 24). The next step is to Und the cepstrum 14 of the echoed version. The result of taking the cepstrum makes the spacing between the echo and the original signal a lit- tle clearer. Unfortunately, the result of the cepstrum also dupli- cates the echo every ( ´ ) seconds. In Figure 25, this is illustrated by the impulse train in the output. Further- more, the magnitude of the impulses representing the echoes are small relative to the original signal. As such, they are difUcult to detect. The solution to this problem is to take the autocorrelation of the cepstrum. We echo the signal once with delay ( ´ ) using the ker- nel depicted in Figure 26. The result is illustrated in Figure 27. Only the Urst impulse is signiUcantly ampliUed as it is reinforced by subsequent impulses. Therefore, we get a spike in the position of the Urst impulse. Like the Urst impulse, the spike is either ( ´ 1 ) or ( ´ 0 ) seconds after the original signal. The remainder of the impulses approach zero. Conveniently, random noise suffers the same fate as all the impulses after the Urst. The rule for deciding on a one or a zero is based on the time delay between the original signal and the delay ( ´ ) before the spike in the autocorrelation. Figure 23Encoding process Figure 24Example signal: x [ n ] = a n u [ n ]; (0 < a < 1) cONE d KERNEL cZERO d KERNEL ORIGINAL SIGNAL ENCODED SIGNAL cONE d MIXER cZERO d MIXER + a a 2 a 3 a 4 Figure 25Cepstrum of the echo-encoded signal ´ ´ ´ ´ ´ CEPSTRUM CEPSTRUM ECHO KERNEL ORIGINAL SIGNAL CEPSTRUM OF ENCODED SIGNAL IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 331 Recall that a one was encoded by placing an echo ( ´ 1 ) seconds after the original and a zero was placed ( ´ 0 ) seconds after the original. When decoding, we assign a one if the magnitude of the autocorrelation function is greater at ( ´ 1 )seconds than it is at ( ´ 0 )seconds. A zero is assigned if the reverse is true. This is the same as deciding which kernel we used utilizing the fact that the cone d and czero d kernel differ only in the delay before the echo (Figure 18). Results. Using the methods described, it is indeed possible to encode and decode information in the form of binary digits into a media stream with mini- mal alteration to the original signal at approximately 16 bps (see Figure 28). By minimal alteration, we mean that the output of the encoding process is changed in such a way so that the average human can- not hear any signiUcant difference between the altered and the original signal. There is little, if any, degrada- tion of the original signal. Instead, the addition of res- onance simply gives the signal a slightly richer sound. While the addition of resonance may be problematic in some music applications, studio engineers may be able to Une-tune the echo hiding parameters during the mastering process, enabling its use. Supplemental techniques Three supplemental techniques are discussed next. Adaptive data attenuation. The optimum attenua- tion factor varies as the noise level of the host sound changes. By adapting the attenuation to the short-term changes of the sound or noise level, we can keep the coded noise extremely low during the silent segments and increase the coded noise during the noisy seg- ments. In our experiments, the quantized magnitude envelope of the host sound wave is used as a reference value for the adaptive attenuation; and the maximum noise level is set to 2 percent of the dynamic range of the host signal. Redundancy and error correction coding. In order to compensate for errors due to channel noise and host signal modiUcation, it is useful to apply error-correc- tion coding ( ECC ) 1 to the data to be embedded. While there exist some efUcient methods of ECC , its applica- tion always results in a trade-off between robustness and data rate. Sound context analysis. The detectability of white noise inserted into a host audio signal is linearly dependent upon the original noise level of the host signal. To maximize the quantity of embedded data, while ensuring the data are unnoticed, it is useful to express the noise level quantitatively. The noise level is characterized by computing the magnitude of change in adjacent samples of the host signal: (17) Ã local 2 1 S max ------------ 1 N ---- × sn 1 + () sn () 3 [] 2 n 1 = N 1 3 1 × = Figure 26Echo kernel used in example Figure 27Echoed version of the example signal ´ 1 1 ´ Table 2Audio noise level analysis Ã 2 local Quality < 0.005 > 0.01 Studio Crowd noise BENDER ET AL. IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996 332 where N is the number of sample points in the sequence and S max is the maximum magnitude in the sequence. We use this measure to categorize host audio signals by noise level (see Table 2). Data hiding in text Soft-copy text is in many ways the most difUcult place to hide data. (Hard-copy text can be treated as a highly structured image and is readily amenable to a variety of techniques such as slight variations in letter forms, kerning, baseline, etc.) This is due largely to the relative lack of redundant information in a text Ule as compared with a picture or a sound bite. While it is often possible to make imperceptible modiUcations to a picture, even an extra letter or period in text may be noticed by a casual reader. Data hiding in text is an exercise in the discovery of modiUcations that are not noticed by readers. We considered three major meth- ods of encoding data: open space methods that encode through manipulation of white space (unused space on the printed page), syntactic methods that utilize punctuation, and semantic methods that encode using manipulation of the words themselves. Open space methods. There are two reasons why the manipulation of white space in particular yields useful results. First, changing the number of trailing spaces has little chance of changing the meaning of a phrase or sentence. Second, a casual reader is unlikely to take Figure 28Result of autocepstrum and autocorrelation for (A) czero d and (B) cone d bits AUTOCEPSTRUM AUTOCORRELATION CEPSTRUM AMPLITUDE TIME (SECONDS) (A) ZERO (FIRST BIT) 18 16 6 4 2 0 00.00040.00060.00080.0010 0.00020.00120.00140.00160.00180.0020 TIME (SECONDS) (B) ONE (FIRST BIT) AUTOCEPSTRUM AUTOCORRELATION CEPSTRUM AMPLITUDE 18 16 6 4 2 0 00.00040.00060.00080.0010 0.00020.00120.00140.00160.00180.0020 IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996BENDER ET AL. 333 notice of slight modiUcations to white space. We describe three methods of using white space to encode data. The methods exploit inter-sentence spacing, end-of-line spaces, and inter-word spacing in justiUed text. The Urst method encodes a binary message into a text by placing either one or two spaces after each termi- nating character, e.g., a period for English prose, a semicolon for C-code, etc. A single space encodes a c0, d while two spaces encode a c1. d This method has a number of inherent problems. It is inefUcient, requir- ing a great deal of text to encode a very few bits. (One bit per sentence equates to a data rate of approxi- mately one bit per 160 bytes assuming sentences are on average two 80-character lines of text.) Its ability to encode depends on the structure of the text. (Some text, such as free-verse poetry, lacks consistent or well-deUned termination characters.) Many word pro- cessors automatically set the number of spaces after periods to one or two characters. Finally, inconsistent use of white space is not transparent. A second method of exploiting white space to encode data is to insert spaces at the end of lines. The data are encoded allowing for a predetermined number of spaces at the end of each line (see Figure 29). Two spaces encode one bit per line, four encode two, eight encode three, etc., dramatically increasing the amount of information we can encode over the previous method. In Figure 29, the text has been selectively justiUed, and has then had spaces added to the end of lines to encode more data. Rules have been added to reveal the white space at the end of lines. Additional advantages of this method are that it can be done with any text, and it will go unnoticed by readers, since this additional white space is peripheral to the text. As with the previous method, some programs, e.g., csendmail, d may inadvertently remove the extra space characters. A problem unique to this method is that the hidden data cannot be retrieved from hard copy. A third method of using white space to encode data involves right-justiUcation of text. Dat

less