Image analysis – Applications
Reexamination Certificate
2000-06-15
2004-10-12
Werner, Brian (Department: 2621)
Image analysis
Applications
C382S237000, C358S003060
Reexamination Certificate
active
06804373
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a method and system for watermarking of images as printed with digital printers, and more particularly to a method and system such as printers or other graphical media including screens of various sorts, that can only display a limited number of colors at each pixel.
2. Description of the Related Art
An “imperceptible watermark” (hereafter “watermark” for short), is defined herein as an alteration of the data set which is mostly not perceptible to a human (i.e., the watermark should be (mostly) invisible), but can be recognized by a machine such as a computer. The general principle of such a watermark has been disclosed, for instance, in “Digital Watermarking for High-quality Imaging”, by M. M. Yeung, F. C. Mintzer, G. W. Braudaway, and A. R. Rao,
Proceedings of the IEEE Signal Processing Society Multimedia Workshop,
Princeton, N.J., 1997.
In the above-mentioned paper, the emphasis is on computer images and other images where each pixel contains information described by one or more real numbers (i.e., all together 8 or more bits of information per pixel for black and white, and several times this amount for color, depending on the number of basic colors being used, usually 4 to 6).
However, hitherto the present invention, there have been few methods or techniques known for producing a digital watermark which is mostly targeted at prints and other images where each pixel contains information described by one or more small integer numbers, or by one or more rational numbers with a small denominator (i.e., the denominator is smaller than 16; altogether usually 4 or less bits of information per pixel for black and white, and several times this amount for color, depending on the number of basic colors being used, usually 4 to 6).
Hence, when building watermarks for electronic images, one is greatly helped by there being a lot of information per pixel. For example, one can hide the watermarks in the least significant bits at some or all pixels. However, when dealing with digital prints, one loses most of this freedom as there is anywhere from one to a small number (usually at most four) digits of information (per color) per pixel. This problem was solved for instance in “Counterfeit Detection Method” by Turho, Xerox Disclosure Journal Vol. 20 No 6 November/December 1995, in U.S. Pat. No. 5,488,664 to Shamir, and in U.S. Pat. No. 5,734,752 to Knox. Both Shamir and Knox provide methods allowing visual recognition of a watermark by comparing a print to a second print, the second print being printed on a transparent medium. The inventions of Shamir and Knox both use pixel blocks, but in a quite different manner.
That is, Knox also uses pixel blocks, larger than the ones used by Shamir, although this use of pixel blocks is not stated explicitly. More precisely, Knox uses two or more different dithering masks with identical boundaries but different, stochastic, interior parts. The part of a half-toned image where a given mask has been used can be thought of as a “pixel block”. It is noted that the methods in Shamir and Knox, of using a transparent medium to visually recognize a watermark, can be used as a way to implement the verification stage of the present invention described below.
However, this implementation would not be very practical as some substantial amount of computation must be performed to verify a public signature, whereas the inventions of Shamir and Knox are aimed at helping in situations only requiring moderate levels of security where less information needs to be checked to accept a document or other object as authentic.
Problems of the conventional techniques to which the present invention is aimed at solving include:
1) For watermarks which are being used for the protection of the integrity and originality of an image, in contexts where high levels of security are required, it is advantageous, for both practicality and increased security, that the watermark be designed using public key cryptography. Part of the problem of using a public key infrastructure (PKI) for images is to find means to stably read information out of the image in order to check a signature.
More precisely, this problem is trivial to anyone versed in the art of cryptography, as long as the image is kept and circulated only in electronic form, as one can then reasonably hope that the information content of the image is invariant in time and predictable from what can be known at the time of the signature.
However, when an image is printed, the information is less stable, and even the problem of recovering the precise content of each pixel is difficult because the image must be perfectly placed on a scanner glass, as the pixels are quite small. A solution to this problem in the case of high quality printed images, as can be provided for instance with offset printing or dye sublimation, is disclosed in U.S. patent application Ser. No. 09/398,203, to G. Aggarwal et al., filed Sep. 17, 1999. The problem which is considered in the present invention is halftoned images, as provided by digital or multitone printers as well as files with similar formats, as described below.
2) When it is desirable to have the precise halftone of a image to be preserved, the halftoned part can be stored and circulated, for instance on the world-wide-web (WWW). Also, with the increasing use of smaller computing devices with limited display capabilities, halftone images have increased room in the new electronic age.
One problem in keeping an image in halftone form is that halftones are hard to compress. It would be advantageous to hide a small copy of a halftoned image in the halftoned image itself. This would allow a user to decide, for example, if the full image is worthwhile receiving using information which needs not be sent again in case the decision is made of receiving the full image.
SUMMARY OF THE INVENTION
In view of the foregoing and other problems, disadvantages, and drawbacks of the conventional methods and structures, an object of the present invention is to provide a method and system for using such watermarks which solve the above-mentioned problems.
Another object is to provide watermarks for digital prints so as to provide the requisite security for authenticating documents.
Below, first, the watermarks solving the above-mentioned problems, will be described assuming that scanning of the printed images can be done very exactly without difficulty.
Then, it will be described how to implement the invention to overcome this further difficulty. The present invention will be presented in the context of digital black and white printers. Adaptation to color and multitone would be obvious to anyone versed in the art taking the present application as a whole.
In a first aspect, a method (and system) of watermarking a half-toned image, includes grouping pixels of an image into blocks each containing a plurality of pixels, using as many gray levels as there are pixels in a block to halftone the image formed in the same blocks of pixels, based on a data set formed by the gray levels of the blocks of the halftoned image, generating at least one of a digital signature and a compressed version of the image, to form a generated unit, and inserting the generated unit in the halftoned image to form the watermark, by selecting how a predetermined number of pixels in a block are placed in the block.
In a second aspect, a method of watermarking a digital print, includes reserving a space N
0
(m,N) in a memory to print a half-toned version of an image, where 1≦m≦H′ and 1≦n≦V′, reserving a smaller space for receiving a matrix M(h, v), the smaller space being determined by the size h
0
-by-v
0
of the pixel blocks, determining, based on a size of the pixel blocks, a list of gray levels to be used, the list representing that either 0, 1, 2, . . . , h
0
.v
0
pixels can be black in the pixel blocks, using, by a half-toning algorithm, the list of gray levels, and determining the image I={I(i,j)} to
Gambaudo Jean-Marc
Tresser Charles Philippe
Miller Ryan J.
Werner Brian
LandOfFree
Method and system using renormalized pixels for public key... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system using renormalized pixels for public key..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system using renormalized pixels for public key... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3259950