Method and apparatus for hiding data for halftone images

Abstract

We propose methods for generating a halftone image, in which each pixel takes one of two tone values. The generated image contains hidden data, which is present at data storage pixels chosen using a pseudo-random number generator. In a first case, the data is hidden within an existing halftone image by reversing the tone value at certain of the data storage pixels, and at pixels neighbouring the data storage pixels. In a second case, the halftone image is generated from a grey-scale image, and data is hidden during this conversion process.

1 .- 21 . (canceled) 
     
     
         22 . A method of embedding data in a halftone image, the method comprising:
 designating, by a computing device, a pixel to be toggled in accordance with a data bit to be embedded;   determining, by the computing device, a connection of a first pixel to a first set of adjacent pixels, wherein the first pixel is in proximity to the designated pixel and wherein the first pixel has a tone value different than the designated pixel prior to the designated pixel being toggled;   determining, by the computing device, a connection of a second pixel to a second set of adjacent pixels, wherein the second pixel is in proximity to the designated pixel and wherein the second pixel has a tone value different than the designated pixel prior to the designated pixel being toggled;   comparing, by the computing device, the connection of the first pixel with the connection of the second pixel; and   toggling, by the computing device, the first pixel if the connection of the first pixel is greater than the connection of the second pixel.   
     
     
         23 . The method of  claim 22 , wherein, the tone value of the first pixel prior to toggling is a substantially same tone value as the adjacent pixels of the first set. 
     
     
         24 . The method of  claim 22 , wherein determining, by the computing device, the connection of the first pixel or the second pixel comprises, for a central pixel, evaluating, by the computing device, a number and proximity of the adjacent pixels to the central pixel. 
     
     
         25 . The method of  claim 24 , wherein determining, by the computing device, the connection of the first pixel or the second pixel further comprises weighing, by the computing device, connection values higher for adjacent pixels which are closer to a center of the central pixel. 
     
     
         26 . The method of  claim 22 , further comprising, if the connection of the first and the second pixel are equal, selecting, by the computing device, the first pixel or the second pixel for toggling based on whether the first pixel or the second pixel is closer to a center of the designated pixel. 
     
     
         27 . The method of  claim 22  wherein a location of the designated pixel is determined by a pseudo-random number generator and a seed. 
     
     
         28 . An apparatus for embedding data in an image including a plurality of pixels, comprising:
 means for toggling a tone value of a plurality of designated pixels of the image in accordance with associated binary data;   means for, for a designated pixel out of the plurality of designated pixels, determining a connection of a first pixel to a first set of adjacent pixels, wherein the adjacent pixels of the first set are in proximity to the designated pixel and which have a tone value different than the designated pixel;   means for determining a connection of a second pixel to a second set of adjacent pixels, wherein the adjacent pixels of the second set are in proximity to the designated pixel and which have a tone value different than the designated pixel;   means for comparing the connection of the first pixel with the connection of the second pixel; and   means for toggling the first pixel if the connection of the first pixel is greater than the connection of the second pixel.   
     
     
         29 . The apparatus of  claim 28 , wherein the means for determining the connection of the first pixel comprises means for, for a central pixel, evaluating a number and proximity of the adjacent pixels to the central pixel. 
     
     
         30 . The apparatus of  claim 29 , wherein the means for determining the connection of the first pixel further comprises means for weighing connection values higher for adjacent pixels which are closer to a center of the central pixel. 
     
     
         31 . The apparatus of  claim 28  wherein the apparatus is at least one of a printer, fax machine or copier. 
     
     
         32 . An article of manufacture comprising:
 a non-transitory computer-readable storage medium; and   computer-executable instructions stored on the computer-readable storage medium and configured to enable a computing device, in response to execution of the instructions by the computing device, to:
 designate a pixel to be toggled in accordance with a data bit to be embedded; 
 determine a connection of a first pixel to a first set of adjacent pixels, wherein the first pixel is in proximity to the designated pixel and wherein the first pixel has a tone value different than the designated pixel; 
 determine a connection of a second pixel to a second set of adjacent pixels, wherein the second pixel is in proximity to the designated pixel and wherein the second pixel has a tone value different than the designated pixel; 
 compare the connection of the first pixel with the connection of the second pixel; and 
 toggle the first pixel if the connection of the first pixel is greater than connection of the second pixel. 
   
     
     
         33 . The article of manufacture of  claim 32 , wherein determine the connection of the first pixel or the second pixel comprises, for a central pixel, evaluate a number and proximity of the adjacent pixels to the central pixel. 
     
     
         34 . The article of manufacture of  claim 33 , wherein determine the connection of the first pixel or the second pixel further comprises weigh connection values higher for adjacent pixels which are closer to the center of the central pixel. 
     
     
         35 . A method of recovering hidden data from an image, comprising:
 using, by a computing device, a seed and a random-number generator to generate a location of N pseudo-random pixels in the image;   extracting intensity values, by the computing device, from the N pseudo-random pixels, wherein an intensity value of at least one of the N pseudo-random pixels was embedded in the image by:
 designating a pixel to be toggled in accordance with a data bit to be embedded; 
 determining a connection of a first pixel to a first set of adjacent pixels, wherein the first pixel is in proximity to the designated pixel and wherein the first pixel has a tone value different than the designated pixel prior to the designated pixel being toggled; 
 determining a connection of a second pixel to a second set of adjacent pixels, wherein the second pixel is in proximity to the designated pixel and wherein the second pixel has a tone value different than the designated pixel prior to the designated pixel being toggled; 
 comparing the connection of the first pixel with the connection of the second pixel; and 
 toggling the first pixel if the connection of the first pixel is greater than connection of the second pixel. 
   
     
     
         36 . The method of  claim 35 , wherein the image is a half-tone image. 
     
     
         37 . The method of  claim 35 , further comprising, applying by the computing device, an inverse of an operation such as including re-ordering, padding, scrambling, encryption, transformation, source coding or compression, or error correction operation, to the extracted intensity values. 
     
     
         38 . An apparatus, comprising:
 a device, configured to:
 apply a key to generate a location of N pseudo-random pixels in an image; 
 extract intensity values from the N pseudo-random pixels, wherein an intensity value of at least one of the N pseudo-random pixels was embedded in the image by:
 designation of a pixel to be toggled in accordance with a data bit to be embedded; 
 determination of a connection of a first pixel to a first set of adjacent pixels, wherein the first pixel is in proximity to the designated pixel and wherein the first pixel has a tone value different than the designated pixel prior to the designated pixel being toggled; 
 determination of a connection of a second pixel to a second set of adjacent pixels, wherein the second pixel is in proximity to the designated pixel and wherein the second pixel has a tone value different than the designated pixel prior to the designated pixel being toggled; 
 comparison of the connection of the first pixel with the connection of the second pixel; and 
 toggle of the first pixel if the connection of the first pixel is greater than connection of the second pixel. 
 
   
     
     
         39 . The apparatus of  claim 38 , wherein the apparatus is further configured to apply an inverse of an operation selected from a group including re-ordering, padding, scrambling, encrypting, transforming, source coding or compressing, or error correcting, to the extracted intensity values. 
     
     
         40 . The apparatus of  claim 39 , wherein the apparatus comprises a printer or a fax machine.