Method for Generating an Improved Carrier for Use in an Image Data Embedding Application

The invention relates generally to the field of image processing, and in particular to a method of embedding normally non-visible information in an image.

In U.S. patent application Ser. No. 08/565,804 a technique has been described for embedding digital data in images that can be implemented either digitally or optically. This technique is aimed at satisfying the requirements that it will not visibly distort the image, it is not easily corrupted by the image content or defects, and that it is robust to basic image processing tasks such as filtering, cropping, rotation, resizing, or compression.

This technique of embedding digital message data in a source image includes the steps of: a) generating a multi-level message data image representing the digital message data; b) convolving the multi-level message data image with an encoding carrier image to produce a scrambled message data image; and c) adding the scrambled message data image to the source image to produce a source image containing embedded data. The message data is recovered from the source image containing embedded image data by: a) cross correlating the source image containing embedded data with a decoding carrier image to recover the message data image; and b) extracting the digital message data from the recovered message data image.

In the above invention, the preferred carrier signal is defined as a frequency modulated (FM) sinusoid. In particular, the FM signal is modulated in a radially symmetric fashion to accommodate the possibility that the image has been rotated. Further, the frequency undulation of the carrier as a function of distance from the center of the carrier is defined as either a linear or a logarithmic undulation function, wherein the logarithmic function is the preferred undulation function due to its robustness to small image scale changes.

However, the above invention has several shortcomings. First, because the carrier signal is deterministic, it is conceivable that a user of the images produced by the method of U.S. patent application Ser. No. 08/565,804 may deduce the carrier undulation function used in the data hiding process. Once the carrier function is understood it may be possible to subtract out the embedded data from the image. This is particularly a disadvantage when one intent of the process is to embed copyright or other secret messages.

Additionally, in the afore referenced patent application, it can be shown that the frequency amplitude spectrum of the carrier is not constant. As a result, the autocorrelation function of the frequency modulated (FM) sinusoid is not a delta function and has strong sidelobes. This has a negative influence on the quality of the extracted message data. In fact, as explained in that patent application, optimum data extraction is achieved only if the autocorrelation function of the carrier signal is an exact delta function.

The present invention is directed at overcoming the problems set forth above. In particular, the present invention provides a solution to the problem of achieving an optimal carrier while simultaneously achieving a secure messaging system. Briefly summarized, according to one aspect of the present invention, a method for embedding a message into a digitized image is disclosed comprising the steps of: forming a digitized version of the desired message; generating a random phase carrier; convolving said formed digitized version of the desired message and said generated random phase carrier to form a scrambled message; and combining said scrambled message with the digitized image to form an embedded message image.

Function wise, the improved carrier signal of the present invention is designed in the Fourier frequency domain. In the Fourier domain, the value of the signal at each frequency is characterized by a complex number that can be represented as either a real/imaginary pair or as an amplitude/phase pair. The carrier signal is designed in Fourier domain in such a way that the carrier's amplitude at each frequency is a constant and the carrier's phase at each frequency is a random number that is uniformly distributed between 0 and 360 degrees. The autocorrelation of such a carrier signal has a shape resembling a delta function, which, as described later in the present invention, improves the integrity of the recovered message.

In a preferred embodiment of the present invention, the random phase of the carrier is constructed by using the output of a stream cipher encryption system. As a result, it will be practically impossible for any unauthorized person who does not have access to the private key of the encryption system to duplicate the carrier function. Furthermore, in those cases when copyright protection is also desired, the private key can be made a function of the original image prior to data embedding such as the hashed value of the original image or certain other attributes of the original image. Since only the original owner has access to the original image, no one else can recover the key. Of course, in those applications where the secrecy of the carrier is not required, a known key can be used to generate the random stream of bits using the same random number generation system.

These and other aspects, objects, features, and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings.

FIG. 1 is a block diagram illustrating the overall operation of the present invention to derive a scrambled message;

FIG. 2A illustrates a digitized image to which the normally non-visible information (scrambled message) is to be added;

FIG. 2B illustrates the addition of the scrambled message, in a tiled fashion, to the digitized image;

FIG. 3 illustrates the method for recovering the scrambled message;

FIG. 4 illustrates in block diagram form the method of recovering the message from the scrambled message;

FIG. 5 illustrates the redundant and the non-redundant parts of a Fourier transform subject to Conjugate Symmetry constraint in the frequency domain;

FIG. 6 illustrates in flow diagram form the method for generating the improved carrier of the present invention;

FIG. 7 is a bar chart illustrating the results of using different block sizes (tile sizes); and

FIG. 8 illustrates in block diagram form a digital image processing system on which the present method may be implemented.

The technique described in the afore referenced patent application for forming non-visible information (message) in an image may be broken down into two parts, the process of embedding the message into an image and the process of extracting the message after the image has been used.

In the embedding part, the message and the carrier are convolved to form a scrambled signal. The scrambled signal then is scaled to ensure that the amplitude of the resultant scrambled message is not visually perceptible. Finally, the scrambled message is added to the image. In a preferred embodiment of that and the present invention, the specific form of the convolution operation is referred to as circular convolution (see "Digital Signal Processing" by Alan V. Oppenheim and Ronald W. Schafer, Prentice-Hall, Inc., pp-101-115) which can be efficiently performed in either space domain (image domain) or Fourier frequency domain representations. The process of data embedding can be mathematically described as

where I(x,y) denotes the original image, I'(x,y) denotes the final image containing the embedded data, M(x,y) denotes the message that is to be embedded in the original image, C(x,y) denotes the carrier signal, M(x,y)*C(x,y) denotes the scrambled image, .alpha. is scale factor, and * denotes the process of circular convolution.

It should be noted that the convolution of the carrier with the message distributes the message information throughout the spatial extent of the scrambled signal. The amplitude .alpha. is chosen to be small enough so that the message is visually undetectable to, but large enough to be recoverable by the message extraction process. That is, the value of .alpha. is chosen in such a way that the maximum amplitude of the embedded signal does not exceed a pre-specified threshold. When dealing with 8-bit images where the pixel codevalues range from 0-255, we have found a threshold of 10 codevalues to be adequate to render the embedded message invisible in most cases.

To extract the hidden message, the image I'(x,y) is cross correlated with a replica of the carrier, C(x,y), as described by the following:

where denotes the operation of circular cross correlation. Replacing I'(x,y) with the embedding equation above yields:

The above relationship simply states that the recovered message consists of the sum of two components, one term is the cross-correlation of the original image with the carrier signal, and the second term is the autocorrelation of the carrier signal convolved with a scaled version of the original message. The effect of the first term can be minimized by creating a random carrier that is uncorrelated with the original image. From examining the second term, it is clear that the resolvability of the recovered message is affected by the autocorrelation of the carrier signal C(x,y). Ideally, to achieve maximum resolvability, the autocorrelation of the carrier signal should be a delta function, .delta.(x,y), which from Fourier analysis theory is equivalent to suggesting that the carrier signal should contain all frequencies at equal amplitude.

In summary, in order to have M'(x,y) match M(x,y) as closely as possible, it is required that ##EQU1## where .delta.(x,y) is a Dirac delta function.

In the present invention starting with FIG. 1, the carrier signal C(x,y) is constructed in the Fourier domain and illustrated as a flat spectrum/random-phase two dimensional array 10. The details of that construction will be explained with the description of FIG. 6. The two dimensional array is circularly convolved with the message 12 in block 14. In block 16 of FIG. 1, the output of block 14 is scaled to an amplitude of approximately 1/25 of the amplitude of the maximum pixel values in the image to form the scrambled message 18.

FIG. 2A represents an image 20 to which the message is to be added. FIG. 2B illustrates the addition of the scrambled message 18 to the image 20 in a tiled fashion. Although tiling is used for the preferred embodiment it is well within the teachings of the present invention to add one or more larger scrambled messages to cover the entire image 20. In a like manner, a smaller scrambled message or messages could be added to the image at key spots without covering the entire image.

Preferred tile size data is presented in the bar chart of FIG. 7, which characterizes the number of message bits lost as a percentage of the total embedded bits due to image compression at various compression ratios. This chart suggests that a tile size of 64.times.64 or 128.times.128 is optimal. Similar results may be obtained when other conventional operations are performed on the image such as low-pass filtering or noise addition.

FIG. 3 represents the first stage of message recovery. Using the same tile grid as in FIG. 2B, the scrambled message 18 is extracted from the embedded image 20 by adding each tile section to the sum of the preceding tile sections. As a result of this operation, the image components add destructively and the scrambled message components add constructively.

Referring to FIG. 4, the scrambled message 18 (sum of sections) is correlated with the flat spectrum/random phase two dimensional array 10 in block 22 to output the original message 12.

The improved carrier is constructed in the Fourier frequency domain. Source code generated in the computer language C++ is provided in Appendix I. As discussed earlier, it is desirable to ensure that the amplitude spectrum is constant or flat so that the auto-correlation of the carrier approximates a delta function. The Fourier phase of the spectrum should be random to simultaneously provide a basis for a cryptographically secure system and to ensure that the message data is spatially dispersed after convolution with the carrier.

To construct a Fourier spectrum with these properties, we first note that the numbers in the Fourier domain are complex quantities, possessing both real and imaginary values. Alternatively, a complex number can be represented by its phase and magnitude. Given a complex quantity F(u,v) at the frequency location (u,v), the real and imaginary parts of F(u,v) may be related to its phase and magnitude by the following simple formulas:

Consequently, setting the magnitude of the Fourier frequency components to unity at all frequencies will result in a flat spectrum. Also, since we wish the carrier data to be real, we impose on its Fourier transform an additional constraint known as Conjugate Symmetry (see "Digital Image Processing," by William K. Pratt, Second Edition, pp. 196-200) as defined below:

where F.sup.* denotes the operation of taking the complex conjugate of F, N is the block size of the carrier (equal to 128 here), and m,n=0,.-+.1,.-+.2,.-+.3, . . .

The Conjugate Symmetry constraint implies that only about half of the Fourier components need to be specified, and that the remaining half may be constructed based on the symmetry conditions. The Conjugate Symmetry property is illustrated in FIG. 5 where the cross-hatched region shows the nonredundant components of the transform and the remaining region designates the redundant components. As a result, to generate a carrier with the desired properties, we need only specify the phase and the amplitude of the non-redundant portions of the Fourier transform and compute the rest of the components by using the appropriate values of m and n in the Conjugate Symmetry relationship described above.

FIG. 6 contains the details of the method for forming the improved carrier. For each location in the non-redundant part of the transform, a random number is chosen from a random number generator 100.

A preferred method of specifying this random phase is to first use a private-key encryption system to generate a stream cipher that resembles a random bit stream. One example of a stream cipher is a scheme called RC-4.TM., a commercially available product from RSA Data Security Inc. Further examples of methods used to generate cryptographically strong stream ciphers based on nonlinear combinations of linear feedback shift registers are described in the reference titled APPLIED CRYPTOGRAPHY, SECOND EDITION, PROTOCOLS, ALGORITHMS, AND SOURCE CODE IN C, "Pseudo-Random-Sequence Generators and Stream Ciphers," by Bruce Schneier, 1996, pp 369-395.

In a cryptographically strong cryptosystem it is computationally infeasible to generate the random bit stream unless the private key is known. By making the private key available only to the authorized users, it can be assured that the carrier signal cannot be duplicated by any unauthorized user. Next, the random bit stream that is generated by the stream cipher is converted into a random phase for the carrier signal at a given frequency. Depending on the accuracy desired, the bit stream can be blocked into N-bit blocks and each block of N bits is mapped into a number that is uniformly distributed between 0 and 360 degrees. For example, for N=10, the interval between 0 and 360 degrees can be divided into 1024 equal subintervals, where each subinterval is randomly (and with a uniform probability) chosen based on the 10-bit value.

Finally, in certain applications it may be desirable to create an encryption private key that depends on the original image values. This is particularly useful for those cases when an author creates an image and wishes to embed a copyright or another form of data in that image to prove ownership at a later time. In this case, an image-dependent key is generated and used to embed the data in the image according to the procedure described above. The user then locks the original image in a safe place and only makes available the watermarked image to the public. By making the key dependent on the original image, the user not only precludes unauthorized users from duplicating the carrier signal, but he can also use the original image (which only he could have had access to) in the court to produce the key and thus prove his ownership. One method of generating a key that depends on the original image is to hash the image through a one-way hashing algorithm (see "Secure Hash Standard" U.S. Department of Commerce Technology Administration National Institute of Standards and Technology, FIPS PUB 180, May 11, 1993, pp 1-20) to generate a fixed-sized hashed value that can then be used as the private key of the encryption algorithm.

The output of the random number generator 100 is normalized in block 110 to ensure it spans between 0 and 360 degrees in phase, or equivalently, between 0 and 2.pi. radians 110. The cosine of the phase is placed into the real part of the transform 120 and sine of the phase 130 is placed into the imaginary part of the transform. It should be mentioned that the Fourier amplitude is automatically flat since the amplitude is: ##EQU2##

To calculate values for the redundant part of the Fourier spectrum, use the Conjugate Symmetry Formula above. This assumes that the non-redundant part of the transform has been calculated. FIG. 5 shows that the redundant part of the transform may be divided into three regions, Region I, Region II, and Region III. The values m and n in the Conjugate Symmetry Formula must be specified in advance and must ensure that the resultant arguments in the term, F.sup.* (-u+mN,-v+nN), correspond to a non-redundant region. The following is a specification for m and n which works for all values of N:

The lower region, Region I, of the redundant part of the spectrum is calculated using m=1 and n=1 in the Conjugate Symmetry Formula. Region II appears on the middle right side of FIG. 5. This region is also be calculated by using m=1 and n=1 in the Conjugate Symmetry Formula. Region III appears on the upper right side of FIG. 5. This region is calculated by using m=0 and n=1 in the Conjugate Symmetry Formula.

As a further refinement, it is known that the Fourier amplitude spectrum of imagery is much larger in the very lowest frequencies when compared to their higher frequencies. Since the cross-correlation process (message extraction) may be described in the Frequency domain as the product of two functions' amplitude spectrums and the subtraction of their respective phases, the impact of the image on the recovered message may further be reduced by reducing the Fourier amplitude of the lowest frequencies of the carrier. The preferred embodiment of this improvement is to increase the amplitude from zero amplitude to a constant value (here the constant value is 1.0) starting at DC (or zero frequency) to 1/16th of Nyquist frequency. In our software implementation, the frequency arrangement shown in FIG. 5 is rearranged so that DC (or zero frequency) occurs at the center of the spectrum at point (N/2,N/2). This rearrangement may be effected by temporarily interchanging the lower right quadrant with the upper left quadrant and interchanging the lower left quadrant with the upper right quadrant. This enables us to directly express frequency as a function of distance from (N/2,N/2), whereas in the former frequency arrangement, references to each quadrant must be dealt with independently. Given this arrangement, our algorithm first introduces a variable called ramp radius which is equal to the value: Nyquist/16, which for N=128, is equal to 4 calculates for each frequency (u,v) less than ramp radius:

1) The distance, radius, from DC: ##EQU3## 2) A value: multiplier=(1-(ramp radius-radius)/ramp radius).sup.2

3) A modified value for F(u,v):

In practice, by constructing the carrier with the methods described in the present invention, the carrier will be uncorrelated with the image and hence the effect of the cross-correlation of the image and the carrier on the recovered image will be negligible.

Referring to FIG. 8, a system on which the present invention is practiced scans an image 210, via a scanner 212 and converts the scanned image to a digital image using an analog-to-digital converter 214. The analog-to-digital converter 214 may be part of the scanner 212. The digitized image is forwarded to a processor 216 wherein it is operated upon in accordance with the software (algorithm) of the present invention. A monitor 230 and mouse 231, or other input device, enables an operator to interface with the image in its digital form. The processed image may be stored in a memory 218 and/or printed out using a printer 220.

The invention has been described with reference to a preferred embodiment; However, it will be appreciated that variations and modifications can be effected by a person of ordinary skill in the art without departing from the scope of the invention.