Method and apparatus for data hiding in printed images

Abstract

A technique for embedding a mark in an a printed image allows its interpretation by an inexpensive printing system. Values of a characteristic parameter 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.

What is claimed is:  
     
       1. A method of embedding a mark in a host image comprised of points, each point having a parameter value, the method comprising the steps of: 
       a. defining in the host image at least one thread of contiguous points, the thread having a length and width;  
       b. creating an altered image by, for each at least one thread, altering parameter values in the thread so as to embed the mark, the thread in the altered image being digitizable to an electronic format so that the embedded mark is interpretable by a printer responsive to the mark, the width of the thread being sufficiently small to be printed by the printer in one pass, thereby containing the embedded mark so as to allow the printer to detect the mark during the one pass, the printer requiring at least two passes to print the altered image.  
     
     
       2. The method of  claim 1  wherein the mark comprises a bit string. 
     
     
       3. The method of  claim 2  further comprising the step of identifying regions within the at least one thread, the step of creating an altered image comprising, for each at least one thread, within each of a plurality of the regions, altering parameter values so as to embed a bit, the plurality of bits embedded in the plurality of regions constituting the bit string. 
     
     
       4. The method of  claim 1  wherein the host image constitutes a bill of currency. 
     
     
       5. The method of  claim 1  wherein the host image constitutes a security document. 
     
     
       6. The method of  claim 1  wherein the host image constitutes an identification document. 
     
     
       7. The method of  claim 1  wherein the printing system responds to the mark by refusing to print the altered image. 
     
     
       8. The method of  claim 1  wherein the at least one thread comprises a plurality of threads, the threads being oriented differently from one another in the image. 
     
     
       9. The method of  claim 3  wherein the step of creating an altered image comprises altering parameter values according to a direct-sequence spread-spectrum technique. 
     
     
       10. The method of  claim 1  wherein the step of creating an altered image comprises altering parameter values according to a patchwork technique. 
     
     
       11. The method of  claim 1  wherein the step of creating an altered image comprises altering parameter values using a feature size on the order of greater than {fraction (1/10)}″. 
     
     
       12. A method for processing data in an electronic format representing a digitized test image to be printed in order to determine whether the digitized test image, electronically encoded as points, each point having a parameter value, contains a mark embedded according to the method of  claim 1 , the method comprising the steps of: 
       a. defining in the digitized test image a test area having a width, the width of the test area being sufficiently small to be printed by a printer in one pass, thereby allowing the printer to determine, during the one pass, whether the test image includes the embedded mark, the printer requiring at least two passes to print the test image; and  
       b. generating from the parameter values in the test area an indication of whether the test image contains the mark.  
     
     
       13. The method of  claim 12  wherein the mark is a bit string, the step of generating an indication of whether the test image contains the bit string comprising generating, for at least one bit in the string, a respective indication of whether the test image contains the respective bit and generating the indication of whether the test image contains the bit string from the respective indication. 
     
     
       14. The method of  claim 13  wherein indication of whether the test image contains the bit string is based on fewer than all of the bits embedded in the host image. 
     
     
       15. The method of  claim 13  wherein the at least one thread has a plurality of regions identified therein, the parameter values within each region having been altered so as to embed at least one bit, the plurality of bits embedded in the plurality of regions constituting the embedded bit string, the step of generating an indication of whether the test image contains the embedded string comprising generating, for each of a plurality of the regions, a respective indication of whether the test image contains the at least one bit and generating the indication of whether the test image contains the bit string from the respective indications. 
     
     
       16. The method of  claim 12  wherein the indication of whether the test image contains the mark is used by a printing system to determine whether the image is printed. 
     
     
       17. A printing system for processing data in an electronic format representing a digitized test image, encoded as points, each point having a parameter value, and optionally printing the digitized test image according to whether the data contains a mark of interest, the mark being encoded according to the method defined in  claim 1 , the printing system comprising: 
       a. a printer;  
       b. means for defining in the digitized test image a test area having a width, the width of the test area being sufficiently small to be printed by the printer in one pass, thereby allowing the printer to determine, during the one pass, whether the text image includes the embedded mark. the printer requiring at least two passes to print the altered image; and  
       c. means for generating from parameter values in the digitized test image thread an indication of whether the digitized test image contains the mark of interest.  
     
     
       18. The printing system of  claim 17  further comprising control means configured to refuse to print the test image according to the indication of whether the test image contains the mark of interest. 
     
     
       19. The printing system of  claim 17  wherein the means for generating an indication of whether the test image contains the mark of interest resides in the printer. 
     
     
       20. An image created by embedding a mark in a host image comprised of points according to the method of  claim 1 . 
     
     
       21. An apparatus for embedding a mark in an electronically encoded image, the apparatus comprising: 
       a. a computer memory for storing the image as an ordered set of pixels, each pixel having a pixel parameter value;  
       b. means for defining in a host image at least one digitized thread of contiguous points, the thread having a length and width; and  
       c. means for creating an altered image by, for each at least one digitized thread, altering parameter values so as to embed the mark in an electronic format, so that the embedded mark is interpretable by a printer responsive to the mark, the width of the thread being sufficiently small to be printed by the printer in one pass, thereby allowing the printer to determine, during the one pass, whether the text image includes the embedded mark, the printer requiring at least two passes to print the altered image.  
     
     
       22. An apparatus for determining whether a digitized test image to be printed by a printer, the test image being electronically encoded as points, each point having a parameter value, contains a mark [data] embedded according to the method of  claim 1 , the apparatus comprising: 
       a. a printer;  
       b. means for defining in the digitized test image a test area having a width, the width of the test area being sufficiently small to be printed by the printer in one pass thereby allowing the printer to determine, during the one pass, whether the test image includes the embedded mark, the printer requiring at least two passes to print the test image; and  
       c. means for generating from the parameter values a respective indication of whether the test area contains the mark.  
     
     
       23. The method of  claim 1  wherein parameter values of some points in the thread are not altered, based on expected visual perceptibility. 
     
     
       24. The method of  claim 12  wherein the mark is a bit string, the step of generating an indication of whether the test image contains the bit string comprising generating, for a plurality of bits in the string, a respective indication of whether the test image contains the respective bit and generating the indication of whether the test image contains the bit string from the respective indications. 
     
     
       25. The method of  claim 1  wherein parameter values are changed by an amount, the amount varying based on expected visual perceptibility.