The present invention pertains generally to digital image processing and relates more particularly to image processing that embeds inconspicuous identifying or authenticating information known as watermarks into an image and that detects the embedded information. The present invention for embedding information in an image and for detecting the embedded information may be incorporated into systems and methods that can be used to identify the printer used to generate a printed rendition of the image.
The proliferation of computers with increasing computational power has contributed to the growth of digital image processing. Digital images are attractive because they can be copied without concern for image degradation, and because they can be easily modified, enhanced and adapted to provide high-quality images that meet a wide range of application requirements. These characteristics of digital images are also sources of concern for owners of images that wish to protect copyrights in the images or that wish to detect and identify sources of unauthorized copying.
In response to these concerns, there have been attempts to develop ways to embed information into other information or xe2x80x9ccover objectsxe2x80x9d such as images that can identify the owner of the cover object or that can identify the device that was used to produce an unauthorized copy. In particular, there has been considerable effort to develop ways to hide authenticating information in images to enable subsequent proof of ownership. The other important application of embedding information in images is to enable source tracking for images produced on permanent media such as paper. This invention primarily relates to the latter application.
On the one hand, the identifying information should be inconspicuous in the sense that it does not visibly alter the image and yet is detectable using appropriate recovery techniques. The information needs to be detectably embedded regardless of image kind such as text or natural or graphics. Moreover, the detection needs to succeed even if only a small area of the printed image is available, and even if the image area has been degraded by repeated handling and wear and tear. Unfortunately, this reliability goal conflicts with the goal of inconspicuous embedding.
Two basic types of information hiding techniques have been developed to embed information that is robust and resistant to various types of printed image wear and tear. One type of technique embeds the information in a spatial or pixel domain. The second type of technique embeds the information in a spectral of frequency domain.
What is needed is an information hiding technique that can embed inconspicuous identifying information into a printed image in a manner that persists through ordinary or extraordinary modifications to the printed image, such as normal wear and tear, and deliberate attempts to tamper with the printed image.
It is therefore an object of the present invention to provide for efficient embedding of information into a cover object such as a printed image that is inconspicuous yet resistant to removal or alternation by a wide range of modifications to the printed image, and for the efficient detection of the embedded information.
According to one aspect of the present invention, a source-identifying watermark is applied to a digital signal by: obtaining a source identifier; constructing a multi-bit string, which includes the source identifier, representing the watermark to be embedded; randomly selecting a sequence of zero-mean patches, one for each bit of the watermark to be embedded, each patch comprising an array of patch elements, and respective offsets for these patches within a selected tile of the digital signal in which the watermark is to be embedded; and applying each zero-mean patch of the sequence to a randomly selected location within the selected tile of the digital signal so that, at the selected patch location, the digital signal has either a highly positive or highly negative correlation with the corresponding selected patch.
According to another aspect of the invention, a watermark is read from a cover object by: obtaining a first digital signal from the cover object; selecting a portion of the first digital signal from a search space to be examined to determine if the watermark is present in the cover object; obtaining a multi-bit string representing the watermark to be read; obtaining zero-mean patch kinds that were previously applied to a second digital signal of the cover object and the corresponding locations in that signal where the patches were applied; correlating the first digital signal with the appropriate zero-mean patch kind for a corresponding bit of the watermark over a plurality of tile locations in the first digital signal to obtain a sequence of bits; and comparing the sequence of bits obtained in the correlating step with corresponding bits of the multi-bit string to determine whether the watermark has been detected.
The watermark applying technique may be implemented in a printer by applying the watermark to a digital signal, such as digital image data representing the image to be printed, after the halftoning process but before printing. The watermark reading technique may be implemented in a computer system. Either technique may be embodied in a program of instructions for execution by the printer or computer.
Throughout the disclosure of the present invention, more particular mention is made of cover objects that are images conveyed by digital signals. It is anticipated that the present invention may have greater advantages in identifying an imaging device such as a printer which generates a printed rendition of the cover object; however, the principles of the present invention are not so limited and can be applied to other image processing applications and to a wide range of cover objects including text and audio.
As mentioned above, the present invention is carried out by processing signals with zero-mean patches. The term xe2x80x9cpatchxe2x80x9d refers to a set of discrete elements that are arranged to suit the needs of each application in which the present invention is used. In image processing applications, the elements of a single patch are arranged to coincide with digital image xe2x80x9cpixelsxe2x80x9d or picture elements. Patch elements may be arranged in essentially any pattern. Throughout the following disclosure, embodiments are discussed in which patch elements are arranged within a square area; however, no particular arrangement of patch elements is critical to the practice of the present invention.
The term xe2x80x9czero-mean patchxe2x80x9d refers to a patch that comprises elements having values the average of which is substantially equal to zero. An average value is substantially equal to zero if it is either exactly equal to zero or differs from zero by an amount that is arithmetically insignificant to the application in which the zero-mean patch is used. A wide variety of zero-mean patches are possible but only a few basic patches with unit magnitude elements are disclosed herein.
The present invention relies on the fact that for a digital signal conveying essentially any meaningful image (which would include natural images as well as synthetic graphics) zero is the expected value of the correlation score for a large number of small zero-mean patches that are located at random locations within the digital signal. The correlation score may be expected to equal zero because, over small regions of a meaningful image, digital signal intensities vary slowly almost everywhere in the image. Signal element or xe2x80x9cpixelxe2x80x9d intensities vary much more quickly at edges appearing in the image; however, for a large number of random locations, the edge contributions to the correlation score can be expected to substantially cancel one another.
The various features of the present invention and its preferred embodiments may be better understood by referring to the following discussion and the accompanying drawings in which like reference numerals refer to like elements in the several figures. The contents of the following discussion and the drawings are set forth as examples only and should not be understood to represent limitations upon the scope of the present invention.