Facsimile and static presentation processing – Static presentation processing – Data corruption – power interruption – or print prevention
Reexamination Certificate
1998-04-15
2002-06-25
Garcia, Gabriel (Department: 2724)
Facsimile and static presentation processing
Static presentation processing
Data corruption, power interruption, or print prevention
C382S100000
Reexamination Certificate
active
06411392
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to steganography. More particularly, this invention relates to techniques for embedding a mark in a still image so that the bit string is detectable 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.
In the United States, this problem has been addressed with respect to currency counterfeiting through laws and import restrictions with the result that most color photocopiers have a circuit that applies simple feature recognition techniques to the image being photocopied to detect when a bill is being reproduced, and refuses to complete the task. The complexity of this task, its specificity to the features of a single type of bill, and the variations among different denominations all make this circuit easy to circumvent.
The proliferation of inexpensive color scanning and printing technology for personal computers in recent years has presented treasury departments with a new challenge. For example, an inexpensive system including a 720×720 DPI 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 to enable a printing system including an ink-jet printer to discern when it is printing a security document. A requirement of any data embedded in the document to this end would be that it not adversely affect image quality. At the same time, the data should be decodable without extensive or expensive computational resources, since the goal would be ultimately to integrate the decoder 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 determine when it is processing a scanned version of a security document in a manner that would allow it to refuse to reproduce the document differs fundamentally from the analogous problem for a photocopier. An ink-jet printer handles data for only a small number of lines, corresponding to one or two traverses 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.
Furthermore, the scan-print sequence used in falsifying documents with these consumer devices subjects the document to be reproduced to nonlinear modifications not necessarily introduced by photocopying. Such modifications are first introduced into a document to be reproduced during the creation of its RGB representation during scanning. The resulting scanned image is characterized by one resolution and, generally, some translation and rotation with respect to the origin of the print field. This digitized image may then be intentionally modified by a counterfeiter intending to obscure any embedded marking using specialized software. Finally, further nonlinear modifications are introduced during printing by an ink-jet printer in the form of spatial resolution lost to dithering in order to enhance the color depth obtainable from the four to seven ink colors in its palette.
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; is 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 preventing and 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; the size and scale of the reproduction is fixed. On the other hand, there is no reason, from the point of view of a forger, not to print out a falsified document oriented 45 degrees from the paper's edges or at some arbitrary position on the page, especially if such a simple alteration will allow a fraud to escape detection by the printer.
SUMMARY OF THE INVENTION
The invention embeds a mark in a host image in a manner that allows its interpretation by a printing system that operates by processing image data in subsegments corresponding to less than the entire image, such as an ink-jet printer. Specifically, values of a characteristic parameter, such as luminance and/or chrominance, are altered in a portion of the host image confined to a thread, i.e. a region of contiguous points in the image, small enough to be included in the print space treated by the printer in a single pass of the printing head. (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, across the image, or a fraction thereof, even if the print head technically makes more than one traverse over this area, such as may occur with some interleaving techniques.) This configuration allows an inexpensive printer, for example, to be programmed to determine whether a specific mark has been encoded in a test image. Thus it can refuse or continue to print the image accordingly, without having specifically to recognize the document (for example, as a $20 bill) or its class (for example, as United States currency).
Preferably, the encoding is repeated in several threads in the image, in varying orientations, thereby minimizing the probability that detection of the mark will be circumvented simply by changing the orientation at which the bill is scanned or printed. The number of repetitions and their orientations necessary to maintain the integrity of the system depends on the geometry of the image, the width of the threads and the width of the printhead.
The invention is not limited to any particular encoding algorithm or internal thread substructure. Space-domain, spread-spectrum techniques, well known in the art, and the statistical approach (“Patchwork”) outlined in U.S. Pat. No. 5,689,587, herein incorporated by reference, are two types of methods useful for documents such as are the targets of counterfeiters, owing to the lack of resealing anticipated during illicit reproduction of these documents. However, virtually any technique compatible with the reduced accuracy of encoding—resulting from the small encoding area for an individual bit—can be used. In particular, the technique should return all possible bit values with equal probability when analyzing an unencoded region. The properties of a host document will influence the optimum encoding algorithm for a given document.
For example, the engraving on a bill of United States currency effectively camouflages alterations introduced by spread-spectrum types of encoding techniques. Thus, in a preferred embodiment, a thread is an elongated area of the host image subdivided into several regions, in each one of which a single bit is encoded by altering characteristic parameter values using conventional one-dimensional direct-sequence spread-spectrum techniques, as are well known in the art. Such techniques incorporate the data in the pixel d
Bender Walter
Gruhl Daniel
Garcia Gabriel
Massachusetts Institute of Technology
Poon King Y.
Testa Hurwitz & Thibeault LLP
LandOfFree
Method and apparatus for data hiding in printed images 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 data hiding in printed images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for data hiding in printed images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2954664