Image analysis – Applications
Reexamination Certificate
1998-04-15
2001-07-17
Au, Amelia M. (Department: 2723)
Image analysis
Applications
C382S278000, C380S054000
Reexamination Certificate
active
06263086
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention is directed to a system and method for automatically detecting invisible digital watermarks embedded in halftone images, or other images that use microstructures to simulate continuous tone color or grayscale images.
2. Description of Related Art
Methods for protecting copyrightable works have evolved from a simple designation below the work to highly complex methods for embedding watermarks in the work. Watermarking can take two basic forms: visible and invisible. Visible watermarks are the commonly-seen copyright logos or symbols that are generally affixed to the work before sales or distribution. Especially in the case of images, the presence of the watermark is very visible, and is generally difficult to remove without damaging the image. Generally speaking, visible watermarks do not harm the image, even though the watermarks may detract form the overall esthetics of the image. Furthermore, the visible watermark is a potential target for fraud. Since a fraudulent copier is actually placed on notice regarding the presence of the watermark, it is possible to attempt to remove the visible watermark from the image.
Invisible watermarks are far more creative and can encompass the standard and commonly used copyright logos or symbols, as well as company logos, serial numbers, origin identification marks, and/or encrypted data. These invisible watermarks are embedded into the work in a way which is not generally discernible without the aid of a visualization device such as a key or computer. Theoretically, these embedded images can be retrieved from the work at any time in the work's history or from any other form or embodiment into which the work may have been translated. This allows the owner to track the work and clearly establish ownership rights when those right are in dispute. Furthermore, since the embedded watermark image is essentially invisible to the unaided eye, the likelihood of tampering with or removal of the watermark is reduced.
SUMMARY OF THE INVENTION
This invention provides a system and method for embedding and retrieving digital watermarks that overcomes the problems associated with recovering these marks from non-original images.
This invention further provides a system and method that allows previously unretrievable embedded invisible watermarks to be recovered from works that have been converted from a digital format to a printed copy, such as a print, or from a reproduction made, for example, on a photocopier.
This invention also provides a system and method that uses localized autocorrelation to estimate the exact amount of the separation between two adjacent correlated halftone patterns that when properly combined produce a visible watermark. Localized autocorrelation of the two adjacent correlated halftone patterns can reduce the effect of distortion and nonuniformity to a minimum. Additionally, global scaling and/or rotation can be treated as individual local shifting and does not need global correction. Thus, localized autocorrelation generates a clearer result.
This invention additionally provides a system and method that uses a two-step autocorrelation process to extract or retrieve embedded digital watermarks from a printed or copied image.
Invisible watermark retrieval depends on the pixel-to-pixel comparison between a bitmap of a halftone image and the bitmap of the halftone image having a certain shift relative to itself. In some areas the bitmap and its shifted version are highly correlated, i.e., near identical, while in other areas they are uncorrelated or highly “conjugately” correlated, i.e., one bitmap is the inverse of the other bitmap. The pixel-to-pixel comparison between the original and shifted bitmaps can provide a contrast between the correlated areas and other areas. Therefore, the embedded, or hidden, watermark becomes visible.
However, retrieval of the original bitmaps from printed copies is not trivial, especially from high-resolution printed copies. Both printing and scanning processes introduce overlapping, distortion and nonuniformity, as well as noise, to the embedded image. The exact bitmap information in very dark regions of the image in the printed copy is difficult to recover. Even in the brighter regions of the image, where there is greater contrast, retrieving the digital watermark is expected to be successful only in a statistical sense. The spatial separation between the two adjacent correlated halftone patterns varies and the amount of shift is generally not an integer number of bitmap pixels on rescanned images. Accurately determining the spatial separation, or the location of a correlation peak, becomes the most critical requirement when detecting hidden watermarks.
Autocorrelation is most easily visualized by imagining two transparencies containing identical images. The two images are then overlayed so they are in perfect alignment. At this point, the maximum amount of light passes through the images. Autocorrelation with (0, 0) arguments refers to this perfect alignment, where there is zero shift between the two images and a maximum amount light of light passes through the images. The value of the autocorrelation with arguments other than (0, 0) can be visualized as one image being shifted relative to the other image, where the amount of light passing through the images is reduced. Usually, the reduction in transmitted light falls quickly near the (0, 0) position and the autocorrelation becomes approximately constant when its arguments, viewed as the relative shift between the two transparencies, are large. However, if the image contains spatially periodic structures, such as the halftone image generated by tiling a single halftone screen over the entire image, relative peaks of autocorrelation occur for certain arguments. These relative peaks may be visualized as the amount of light transmitted through the two transparencies for a certain relative shift The relative peak amount of transmitted light may not be as great as the primary, or absolute, peak amount of transmitted light that occurs when the images are perfectly aligned. However, this secondary relative peak is detectable. Therefore, if watermarks are embedded in a halftone image, i.e., in the periodic structure of the image, autocorrelation repeats itself to an extent when the periodic occurrences of the watermark are themselves aligned between the two images.
Therefore, by using a two-step autocorrelation process, the system and method of this invention enables recovery of invisible digital watermarks from printed copies.
These and other features and advantages of this invention are described in or are apparent from the following detailed description of the preferred embodiments.
REFERENCES:
patent: 4194221 (1980-03-01), Stoffel
patent: 4509150 (1985-04-01), Davis
patent: 4745633 (1988-05-01), Waksman et al.
patent: 4791671 (1988-12-01), Willems
patent: 5339172 (1994-08-01), Robinson
patent: 5694102 (1997-12-01), Hecht
patent: 5710636 (1998-01-01), Curry
patent: 5710834 (1998-01-01), Rhoads
patent: 5734752 (1998-03-01), Knox
patent: 5835639 (1998-11-01), Honsinger et al.
patent: 5859920 (1999-01-01), Daly et al.
patent: 5893067 (1999-04-01), Bender et al.
patent: 5905800 (1999-05-01), Moskowitz et al.
patent: 5930369 (1999-07-01), Cox et al.
patent: 0777197A2 (1991-06-01), None
patent: 0 493 053 A2 (1991-12-01), None
patent: 0901282A2 (1999-03-01), None
patent: WO 96/25005 (1996-08-01), None
patent: WO 98/11492 (1998-03-01), None
Bender et al. (Bender), “Techniques for Hiding Data”, IBM Systems Journal, vol. 35, Nos. 3&4, 1996.*
Knox and Wang, Digital watermarks using stochastic screens, Proc. SPIE vol. 3018, Apr., 1997, pp. 316-322.*
Tirkel, A.Z. et al., Image watermarking-a spead spectrum application, IEEE synposium on Spread Spectrum Techniques and Applications, Sep. 1996, vol. 2, pp. 785-789.*
Fieberg, Auto- and Crosscorrelation properties for extended m-sequences and related sequences, IEEE synposium on Spread Spectrum Techniques and Applications, Jul. 1994, vol. 2, pp. 406
Au Amelia M.
Miller Martin
Oliff & Berridg,e PLC
Xerox Corporation
LandOfFree
Automatic detection and retrieval of embedded invisible... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic detection and retrieval of embedded invisible..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic detection and retrieval of embedded invisible... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2439266