Image analysis – Applications
Reexamination Certificate
1998-04-15
2001-04-03
Au, Amelia (Department: 2623)
Image analysis
Applications
C380S054000
Reexamination Certificate
active
06212285
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to steganography. More particularly, this invention relates to techniques for embedding a tracking number in a still image in a manner executable by a printing system.
BACKGROUND OF THE INVENTION
The appearance of commercial color photocopiers in the 1970's presented counterfeiters around the world with a powerful, widely accessible tool for creating passable reproductions of currency and other security documents such as treasury bills and airline tickets.
The proliferation in recent years of inexpensive color scanning and printing technology for personal computers has presented treasury departments with a new challenge with respect to currency counterfeiting. For example, an inexpensive system including a 720×720 color ink-jet printer with a 300 DPI flatbed scanner can be used to create color reproductions that exceed the quality of color photocopiers costing more than a hundred times as much.
This development has brought about a need for embedding a serial number, on the order of
32
bits, in an image printed by a printing system including an ink-jet printer in a manner that does not adversely affect image quality. At the same time, the encoding should not require extensive or expensive computational resources, since the goal would be ultimately to integrate the encoder into the printer itself. Also, for analysis, the bits should be detectable after digitizing by a flatbed scanner of typical consumer resolution, currently 600 DPI or less.
Enabling such an ink-jet printer to encode its serial number or some other identifying bit string onto its printed output differs fundamentally from the analogous problem for a photocopier. The dithering algorithm is not integral to the printer but is handled by software on a host computer or a plug-in card. An ink-jet printer handles data for only a small number of lines, corresponding to one or two passes of the printing head, at one time. A consumer ink-jet typically prints a quarter-inch BAND across an 8.5-inch path length in a single pass. Ideally, any technique should require image data from only one pass at a time.
Decoding the embedded serial number may be complicated by the nonlinear modifications introduced into the document by the print/scan sequence. Ink-jet printing subjects the document to be reproduced to nonlinear modifications not necessarily introduced by photocopying; these modifications take the form of spatial resolution lost to dithering in order to enhance the color depth obtainable from the four to seven colors of ink in its palette. If this output is then scanned, to examine the document for an encoded serial number for example, the creation of its RGB representation introduces further modifications. Scanning also typically introduces some translation and rotation of the image.
In terms of data hiding, this situation differs from the traditional information hiding problems. Typically for images, data hiding techniques are designed with the understanding that the quality of a test image might be largely degraded compared to the original unaltered host image in terms of signal-to-noise ratio through perceptual coding methods such as JPEG; that arbitrary resampling might have been done through scaling; and that cropping is a possibility. Most commercial systems also presuppose that a test image presented to the decoder has not been rotated with respect to the host image; often such systems require the test image to be untranslated as well. Furthermore, it is often assumed that the test image will be in a similar color/luminance space—RGB v. CMYK, for example—as the original host image.
By contrast, data hiding for detecting counterfeiting of security documents is constrained by an almost complementary set of circumstances. An offender is motivated to create a reproduction that looks as much as possible like a legitimate document before trying to pass it. Thus the quality of the reproduced image that would serve as a test image is usually excellent, and the size and scale of the reproduction is fixed.
SUMMARY OF THE INVENTION
Summary of the Invention
The invention provides a technique for embedding a tracking number as a series of bits in a host image in a manner executable by a printing system, including printing systems that operate by processing image data in subsegments corresponding to less than the entire image, such as an ink-jet printer. (Note that as used herein, the term “pass” refers to the movement of the print head involved in printing one continuous band or region of the image, or a fraction thereof, across the image, even if the print head technically makes more than one traverse over this area, such as may occur with some interleaving techniques.) The tracking number is detected and identified by exploiting the behavior of sums of a large number of random variables, based on the approach outlined in U.S. Pat. No. 5,689,587, herein incorporated by reference.
Specifically, the data-embedding technique alters characteristic parameter values at a set of pseudo-random locations in the host image chosen for each bit in a manner that markedly changes the expectation value of some linear combination of mathematical functions of the values at that set of locations. Each bit in the embedded string is recoverable from a test image by calculating an experimental value of a linear combination of a large number of instances of the functions and comparing the experimental value with the expectation value of the sum for the unaltered host image.
Regions are preferably defined in the image that each serve as the embedding zone for one bit; or, several bits may be embedded in each zone, due to the orthogonality of bits embedded using this technique. In general, different types of zones are defined, each type receiving a distinct data content. The dimensions of the zones are preferably large enough to accommodate the alterations to the image without degrading the image but small enough so that at least one of each type of zone will fall entirely on the host image regardless of the position of the grid defining the zones over the image. Such placement considerations can be resolved by Nyquist theory, as is well known in the art. Repeating a zone type in the image allows the decoder to identify the bits encoded therein with greater certainty.
For each bit, the embedding is done by first randomly selecting a set of locations in one of the embedding zones, for example by associating locations in the zone with members of a series of pseudo-random numbers. The locations in each set are partitioned in the general case into first and second groups. To encode one bit value, the host image is then altered by increasing the values of a characteristic parameter at locations belonging to the first group and decreasing the values of the same characteristic parameter at locations belonging to the second group; to encode the other bit value, the first group parameter values are decreased and the second group parameter values are increased. The increment by which the parameter value at any location in the subset is altered may be adapted to minimize the visibility of the encoding; for example, alteration at some locations may be waived, effectively receiving an encoding depth of zero. For digitally encoded images, the locations correspond to patches (i. e., groupings) of adjacent pixels. These changes are executed by a printing system so as to embed a bit string identifying the source of the printed document. In a preferred embodiment, the encoding operations are performed by the printer itself. In another preferred embodiment, a single pass of the printer embeds at least one of each type of zone.
In a preferred embodiment, at least one of the bits is encoded to a greater certainty than the other bits in the string, for example, by using a larger number of locations or a greater alteration to the parameter values for encoding it. One bit alone may serve as this marker; or each zone may contain its own marker and function as a tag indicating its zone type. The higher certainty of th
Bender Walter
Gruhl Daniel
Au Amelia
Johnson Timothy M.
Massachusetts Institute of Technology
Testa Hurwitz & Thibeault LLP
LandOfFree
Method and apparatus for multi-bit zoned data hiding in... 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 apparatus for multi-bit zoned data hiding in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for multi-bit zoned data hiding in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494219