Method and computer program for extracting an embedded message from a digital image

[0002] The disclosure in the CD-ROM appendix of this patent disclosure of this patent document contains material to which a claim of copyright protection is made. The copyright owner has no objection to the reproduction of any one of the patent documents or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.

[0003] The invention relates generally to the field of image processing, and in particular to embedding and extracting hidden messages in digital image data. This field is also referred to as data hiding, information hiding, watermarking and also steganography.

[0004] U.S. Pat. No. 6,044,156, issued Mar. 28, 2000, entitled “Method For Generating An Improved Carrier For Use In An Image Data Embedding Application,” by Honsinger et al., discloses a technique for embedding messages in digital images data. This method for embedding a hidden message into a digitized image includes the steps of providing a message template indicating the relative locations of data in the embedded message, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked; placing message data at the data locations defined by the template; convolving the message data in the template with a carrier to form a dispersed message; and combining the dispersed message with the image.

[0005] The hidden messages are recovered from the embedded hidden message image by cross correlating the embedded hidden message image containing the dispersed message with a decoding carrier to recover the embedded dispersed message; and extracting the digital message data from the recovered dispersed message employing the message template to locate the message data.

[0006] One problem with the above described approach is that when the digital image is very noisy, for example when it is formed by scanning an inkjet printed image on ordinary paper, the method sometimes does not work to recover the embedded message. There is a need therefore for an improved method of recovering the embedded message.

[0007] The problem is solved according to the present invention by providing a method for extracting an embedded message from a digital image, the embedded message being formed by arranging message bits in predetermined locations represented by a message template, convolving the message with a random phase, flat Fourier amplitude carrier to form a dispersed message and tiling the dispersed message over the image, that includes the steps of:

[0008] a) locating the tile boundaries in the digital image;

[0009] b) correlating a tile with the carrier to extract the embedded message;

[0010] c) forming a multiplier A that is inversely proportional to the noise in the extracted message;

[0011] d) multiplying the embedded message by A to form a weighted embedded message;

[0012] e) repeat steps b) to d) for a second tile to generate a second weighted embedded message;

[0013] f) summing the weighted embedded messages to form a summed weighted embedded message; and

[0014] h) extracting the message bits from the summed weighted embedded message.

[0015] The method has the advantage of improving the signal quality for data embedding applications by weighting each recovered embedded message inversely with respect to noise in the recovered message and adding the recovered messages to reinforce the signal and cancel the noise. The improvement due to the method can be significant for images with large variations in business, such as portraits, or in images that are very noisy, such as digital images produced by scanning ink jet prints on plain paper.

[0016] FIG. 1 is a block diagram illustrating steps employed in preparing an image for the application of the present invention;

[0017] FIG. 2 is a diagram showing a message tiling pattern in a digital image;

[0018] FIG. 3 is a flow chart illustrating the method of the present invention; and

[0019] FIG. 4 is a diagram useful in describing the message data.

[0020] The present invention is useful for extracting hidden messages from photographic images recorded on film or paper and images that have been produced using digital printing techniques such as inkjet, electrographic, or thermal printing.

[0021] Referring to FIG. 1, the present invention employs a message template 10 that is used to indicate the location of the data in a message that is to be embedded in an image. The locations, indicated by the x's in FIG. 1, are filled in a predetermined order so that the extraction algorithm knows where to look for the data. As shown in FIG. 1 the message template 10 is represented as a rectangular array of pixel locations, however, it is recognized that its implementation could be a set of ordered values in a lookup table indicating the locations of the message data in an array. The message to be embedded is represented by a stream of bits. The stream of bits are represented as + or −1 (+1 representing an original bit value of 1 and −1 representing an original bit value of 0) at the locations indicated by an “x” in the template; all other locations are filled by 0's. The template is used both to embed and to extract message data from the digital image. It is preferred that the image be represented using floating point numbers so that issues of quantization and sign are minimized.

[0022] The template is used in both the embedding and the extraction process. The embedding process is performed by convolving the message data with a random phase carrier having substantially uniform amplitude in the frequency domain to produce a dispersed message and the dispersed message is combined with the image as shown in the following equation.

[0023] I′(x,y)=I(x,y)+(α(M(x,y)*C(x,y)),  Eq. (1)

[0024] where I′ (x,y) is the digital image having an embedded message, I(x,y) is the original digital image; * represents the operation of cyclic convolution; α is a multiplicative constant chosen to make the embedded message invisible to the human observer; M(x,y) is the original message; and C(x,y) a random carrier, which is substantially of uniform amplitude in the frequency domain, with the exception of very low frequencies which are zero, resulting in a carrier with zero mean.

[0025] As shown in FIG. 2, the dispersed message 16 is embedded in the digital image by tiling the dispersed message onto the digital image 14. The preferred tile size of the dispersed message is 128×128 pixels. This implies that the message template, message, and carrier are also 128×128 pixels.

[0026] Before the message is recovered, possible changes in rotation and scale need to be corrected for. The rotation and scale correction can be accomplished using the technique described in U.S. Pat. No. 5,835,639 issued Nov. 10, 1998 to Honsinger et al., entitled “Method For Detecting Rotation and Mangification in Images.” If the location of the tiles in the digital image are known, the recovery of the embedded message can proceed directly. However if the boundary location of the tiles are not known, the tile location can be determined as described in U.S. Ser. No. 09/453,160, filed Dec. 2, 1999, entitled, “Method and Computer Program for Embedding and Extracting an Embedded Message from a Digital Image,” by Honsinger.

[0027] The recovery of a tile of the dispersed message, is described by the following equations. If we correlate both sides of equation 1) with C(x,y) as follows,

[0028] I′(x,y){circle around (X)}C(x,y)=I(x,y){circle around (X)}C(x,y)+(α(M(x,y)*C(x,y)){circle around (X)}C(x,y)  Eq. (2)

[0029] the result will be an original message corrupted somewhat by noise. The first term, representing the corrupting noise, is small, I(x,y){circle around (X)}C(x,y)≈0. So that,

[0030] I′(x,y){circle around (X)}C(x,y)≈α(M(x,y)*(C(x,y){circle around (X)}C(x,y))  Eq. (3)

[0031] And furthermore, since the carrier is random, and substantially uniform in amplitude in the frequency domain,

[0032] C(x,y){circle around (X)}C(x,y)≈δ(x,y)  Eq. (4)

[0033] So that,

[0034] I′(x,y){circle around (X)}C(x,y)≈α(M(x,y)  Eq. (5)

[0035] The above analysis shows that the end result of correlating the tile with the carrier is the original message.

[0036] Referring to FIG. 3, an embedded message that has been formed by arranging message bits in predetermined locations represented by a message template, convolving the message with a random phase, flat Fourier amplitude carrier to form a dispersed message and tiling the dispersed message over the image, is recovered from a digital image by first locating the tile boundaries in the digital image and selecting a first tile (18). Next the selected tile is correlated with the random phase carrier to extract the embedded message (20). A multiplier A representing a weighting factor that is inversely proportional to the amount of noise in the extracted message is formed (22). For example, the weighting factor can be simply the reciprocal of the average value of the noise in the recovered message. Preferably, the weighting factor is the variance of the signal divided by the variance of the noise in the recovered message.

[0037] The embedded message is then multiplied (24) by A to produce a weighted message. The weighted embedded message is added (26) to an accumulator (which has been initialized to zero) and tested (28) to determine if the signal to noise ratio of the accumulated weighted message is acceptable. If acceptable, the process is complete. Otherwise, a new tile is selected (30) and the process is repeated until the signal to noise ratio of the accumulated weighted message is acceptable.

[0038] In a preferred embodiment of the invention, for a message having dimensions of 128×128 pixels and containing 130 bits of information, each bit being represented by one pixel, a signal to noise ratio of 2.3 has been found to be an useful criterion for stopping.

[0039] The formation of the preferred embodiment of multiplier A will now be described in more detail with reference to FIG. 4. The figure represents a portion of an extracted embedded message. Each message bit 32 is surrounded-by a region of ambiguity 34 having a diameter d. The value of diameter d is chosen based on the application. For most applications a value of 2 or 3 pixels for d works well. These regions of ambiguity are not clearly message bits, and not clearly background, they are the sidelobes of the recovered message bits. The region 36 outside of the regions of ambiguity are background.

[0040] To calculate the multiplier A, the overall message is first squared to make all the values positive. The template is used to determine where the message bits are located. The average squared value of the message bits (equal to the variance of the message bits) is calculated, and the average squared value of the background bits (equal to the variance of the message bits) is calculated. The ratio of the average squared value of the message bits to the average squared value of the background bits is equated to the multiplier A.

[0041] The reason that this approach works is because as the noise decreases, the factor A increases, giving more weight to the corresponding version of the embedded message. As the various weighted versions of the embedded message are accumulated (added pixel by pixel), the signal, which is deterministic, reinforces and the noise, which is relatively random tends to cancel out.

[0042] The present invention is preferably practiced in an image processing system including a source of digital images, such as a scanner, a computer programmed to process digital images, and an output device such as a thermal or inkjet printer. The method of the present invention may be sold as a computer program product including a computer readable storage medium bearing computer code for implementing the steps of the invention. Computer readable storage medium may include, for example; magnetic storage media such as a magnetic disc (e.g. a floppy disc) or magnetic tape; optical storage media such as optical disc or optical tape; bar code; solid state electronic storage devices such as random access memory (RAM)or read only memory (ROM); or any other physical device or medium employed to store a computer program.

[0043] Appendix A contains a computer program written in the C++ language for extracting an embedded message from a digital image according to the present invention.

[0044] The invention has been described in detail with particular reference to certain preferred embodiments thereof, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention.

[0045] 10 message template

[0046] 12

[0047] 14 digital image

[0048] 16 dispersed message

[0049] 18 select first tile step

[0050] 20 extract embedded message step

[0051] 22 form multiplier A step

[0052] 24 multiplication step

[0053] 26 add weighted embedded message to accumulator step

[0054] 28 test for completion step

[0055] 30 select new tile step

[0056] 32 message bit

[0057] 34 region of ambiguity

[0058] 36 background region