Encoding data in color images using patterned color modulated image regions

• US 5,946,414 A
• Filed: 08/28/1998
• Issued: 08/31/1999
• Est. Priority Date: 08/28/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Tong, Xin, Cass, Todd A.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US09/162,119
• Time in Patent Office: 368 Days
• Field of Search: 382/100, 382/162, 382/183, 235/454, 235/462, 235/465, 235/469, 235/494
• US Class Current: 382/183
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32309 in colour image data
• CPC Class Codes: H04N 2201/3261 of multimedia information, e.g. a sound signal
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

Message values included in a set of valid message values that constitute a coding scheme are each encoded in an image region, called an encoded signal block, composed of a spatially arranged pattern of colored sub-regions. The colored sub-regions have color values produced by modulating a reference color value by a color change quantity expressed as a color space direction in a multi-dimensional color space such that the average color of all of the sub-region colors is the reference color. There is a unique pattern of color-modulated sub-regions for each valid message value in the coding scheme. In one embodiment, the color space direction is computed to be simultaneously detectable by a digital image capture device such as a scanner and substantially imperceptible to a human viewer, so that the embedded data represented by the pattern of color modulations are visually imperceptible in the encoded signal block. When the reference color is determined to be the average color of an image region in an original color image, the encoded signal block may replace the image region in the original image, producing an encoded image version of the original image having little or no image degradation. In this case, the original image colors become carriers of the encoded data. Signal blocks may be arranged to encode data in only one dimension in an image, which allows for less complex decoding algorithms, or in a two dimensional array or grid-like structure, which allows for a high encoded data density rate.

Claims

1. A method for operating a processor-controlled machine to produce an output color image having at least one message data item indicating data encoded therein;

the machine including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the machine;

the processor being connected to the memory device for accessing and executing the instruction data stored therein;

the method comprising;

obtaining a message data item indicating a message value;

the message value being one of an expected set of valid message values in a predetermined coding scheme;

selecting a modulation pattern data structure representing the message value of the message data item;

a selected modulation pattern data structure being one of a plurality of modulation pattern data structures each uniquely representing one of the valid message values in the coding scheme;

each modulation pattern data structure defining size dimensions of an output signal block color image and including at least two different data values spatially arranged in a pattern indicating image locations in the output signal block color image of at least two colors produced by applying a color difference quantity to an unspecified reference color;

obtaining an output color value as the unspecified reference color;

obtaining the color difference quantity using the output color value;

producing an output signal block color image using the output color value, the color difference quantity and the selected modulation pattern data structure;

the output signal block color image having size dimensions indicated by the modulation pattern data structure and including a spatially arranged pattern of color modulated image regions having color values produced by modulating the output color value by the color difference quantity subject to a requirement that the output color value be an average color of all of the color values of the color modulated image regions; and

producing an output color image including the output signal block color image as an image region therein.

2. The method of claim 1 for operating a processor-controlled machine to produce an output color image wherein

obtaining the color difference quantity includes using the output color value to compute, in a multi-dimensional color space, a color space direction and associated color modulation magnitude that together define an additive change in the output color value;

the at least two different data values spatially arranged in the modulation pattern data structure indicate scaling data; and

modulating the output color value by the color difference quantity includes generating the color values of the spatially arranged pattern of color modulated image regions by varying the output color value by the additive change scaled by the scaling data.

3. The method of claim 2 wherein the color difference quantity is a single color space direction and associated color modulation magnitude for all image locations in the output signal block color image;

the color space direction and associated color modulation magnitude being computed so that the color values of the color modulated image regions included in the output signal block color image are simultaneously capable of being detected by a digital image capture device and are visually substantially imperceptible to a human viewer of the output signal block color image;

the spatially arranged pattern of color modulated image regions in the output signal block color image thereby being substantially imperceptible to the human viewer.

4. The method of claim 2 wherein the output color image is a gray scale image, the output color value is a color included in a set of gray scale colors that ranges from black to gray to white, and the color difference quantity is a single color space direction and associated color modulation magnitude indicating the set of gray scale colors;

the color values of the color modulated image regions included in the output signal block color image thereby all being included in the set of gray scale colors.

5. The method of claim 2 wherein the color difference quantity is a function of an image location in the modulation pattern data structure such that the color space direction and associated color modulation magnitude applied to the output color value varies by image location in the output signal block color image, subject to a requirement that the output color value is an average color of all of the color values of the color modulated image regions in the output signal block color image.

6. The method of claim 1 for operating a processor-controlled machine to produce an output color image further including, when the message data item indicates plural message values, and after encoding a first one of the plural message values to produce a first output signal block color image,

repeating, for each remaining message value of the plural message values, the selecting, obtaining and producing the output signal block color image steps to produce plural additional output signal block color images;

wherein producing each of the plural output signal block color images includes using, as a color difference quantity, one of a plurality of orthogonal color space directions and associated color modulation magnitudes occurring in a multi-dimensional color space;

each orthogonal color space direction and associated magnitude together defining an additive change in the output color value; and

additively combining the first and the plural additional output signal block color images to produce a combined output signal block color image encoding the plural message values in the output color image.

7. The method of claim 6 wherein a total number of message values that may be encoded in a single output signal block color image is a function of a total number of modulation pattern data structures and a total number of orthogonal color space directions and associated color modulation magnitudes computed using the output color value.

8. The method of claim 1 for operating a processor-controlled machine to produce an output color image wherein obtaining the color difference quantity includes assigning as the color difference quantity a predetermined color space direction and associated color modulation magnitude in a multi-dimensional color space that together define a fixed, predetermined additive change in the output color value;

wherein the at least two different data values spatially arranged in the modulation pattern data structure indicate scaling data; and

wherein modulating the output color value by the color difference quantity includes generating the color values of the spatially arranged pattern of color modulated image regions by varying the output color value by the fixed, predetermined additive change scaled by the scaling data.

9. The method of claim 1 for operating a processor-controlled machine to produce an output color image wherein the plurality of output signal block color images are arranged in the output color image in a two-dimensional array.

10. The method of claim 1 for operating a processor-controlled machine to produce an output color image wherein the plurality of output signal block color images are arranged in the output color image so that data is encoded only in a single dimension thereof.

11. The method of claim 1 for operating a processor-controlled machine to produce an output color image wherein the output color image is generated as a plurality of output signal block color images each having data encoded therein.

12. The method of claim 1 for operating a processor-controlled machine to produce an output color image further including receiving an input color image;

and wherein obtaining an output color value as the unspecified reference color includes obtaining the output color value from an image region of the input color image.

13. The method of claim 12 wherein the output color image is a version of the input color image having data encoded therein;

and wherein producing the output color image including the output signal block color image includes replacing the image region of the input color image with the output signal block color image.

14. The method of claim 1 for operating a processor-controlled machine to produce an output color image wherein the predetermined coding scheme is a binary coding scheme composed of two valid message values;

the plurality of modulation pattern data structures including at most first and second modulation pattern data structures each representing one of the two valid message values.

15. A method for operating a processor-controlled machine to produce an output color image having at least one message data item indicating data encoded therein;

the machine including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the machine;

the processor being connected to the memory device for accessing and executing the instruction data stored therein;

the method comprising;

obtaining a message data item indicating a message value;

the message value being one of an expected set of valid message values in a predetermined coding scheme;

selecting a signal block data structure representing the message value of the message data item;

a selected signal block data structure being one of a plurality of signal block data structures each uniquely representing one of the valid message values in the coding scheme;

each signal block data structure defining size dimensions of an output signal block color image and including data indicating a predetermined color space direction and associated color modulation magnitude in a multi-dimensional color space specifying a color difference quantity;

each signal block data structure further including scaling data indicating a spatially arranged modulation pattern specifying image locations in the output signal block color image of scaled color difference quantities produced by applying the scaling data to the predetermined color space direction and associated color modulation magnitude;

obtaining an output color value;

producing an output signal block color image using the output color value and the selected signal block data structure indicating the predetermined color space direction and the modulation pattern;

the output signal block color image having a spatially arranged pattern of color modulated image regions each having a color value produced by modulating the output color value by the color space direction and the associated color modulation magnitude according to the scaling data indicating the modulation pattern, subject to a requirement that the output color value be an average color of all of the color values of the color modulated image regions; and

producing an output color image including the output signal block color image as an image region therein.

16. A method for operating a processor-controlled machine to encode a plurality of message data items in an encoded color image version of an input color image so that the message data items are visually substantially imperceptible to a human viewer;

the machine including a processor and a memory device for storing data;

the data stored in the memory device including instruction data the processor executes to operate the machine;

the processor being connected to the memory device for accessing and executing the instruction data stored therein;

the method comprising;

receiving an input color image data structure including a plurality of subregions;

obtaining a plurality of ordered message data items having a predetermined order and each indicating a message value;

the message value being one of an expected set of valid message values in a predetermined coding scheme;

for each ordered message data item, in the predetermined order thereof, producing an output signal block color image, including

selecting a signal block data structure representing the message value of the message data item;

a selected signal block data structure being one of a plurality of signal block data structures each uniquely representing one of the valid message values in the coding scheme;

each signal block data structure defining size dimensions of an output signal block color image and including variable data a color difference quantity;

each signal block data structure further including scaling data indicating a spatially arranged modulation pattern specifying image locations in the output signal block color image of scaled color difference quantities produced by applying the scaling data to the color difference quantity;

determining an input color value of one of the subregions of the input color image;

obtaining the color difference quantity using the input color value;

producing an output signal block color image using the input color value, the color difference quantity and the selected signal block data structure;

the output signal block color image having a spatially arranged pattern of color modulated image regions each having a color value produced by modulating the input color value by the color difference quantity according to the scaling data indicating the modulation pattern, subject to a requirement that the input color value be an average color of all of the color values of the color modulated image regions; and

replacing the subregion in the input color image with the output signal block color image;

the encoded color image version of the input color image being produced by replacing the subregions of the input color image with the output signal block color images in the predetermined order of the ordered message data items;

the encoded color image being perceived by a human viewer to be substantially identical in appearance to the original color image.

17. The method of claim 16 for operating a processor-controlled machine to encode a plurality of message data items in an encoded color image version of an input color image wherein

obtaining the color difference quantity includes using the input color value to compute, in a multi-dimensional color space, a color space direction and color modulation magnitude that together define an additive change in the input color value;

the at least two different data values spatially arranged in the modulation pattern data structure indicate scaling data; and

modulating the input color value by the color difference quantity includes generating the color values of the spatially arranged pattern of color modulated image regions by varying the input color value by the additive change scaled by the scaling data.

18. The method of claim 16 for operating a processor-controlled machine to encode a plurality of message data items in an encoded color image version of an input color image wherein the plurality of output signal block color images are arranged in the encoded color image in a two-dimensional array.

19. The method of claim 16 for operating a processor-controlled machine to encode a plurality of message data items in an encoded color image version of an input color image wherein the plurality of output signal block color images are arranged in the encoded color image so that data is encoded only in a single dimension thereof.

20. An article of manufacture for use in a machine that includes a memory device for storing data;

a storage medium access device for accessing a medium that stores data; and

a processor connected for accessing the data stored in the memory device and for receiving data from the storage medium access device;

the article comprising;

a data storage medium that can be accessed by the storage medium access device when the article is used in the machine; and

data stored in the data storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine;

the stored data comprising instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, obtaining at least one message data item indicating a message value;

the message value being one of an expected set of valid message values in a predetermined coding scheme;

the processor, further in executing the instructions, selecting a modulation pattern data structure representing the message value of the at least one message data item;

a selected modulation pattern data structure being one of a plurality of modulation pattern data structures each uniquely representing one of the valid message values in the coding scheme;

each modulation pattern data structure defining size dimensions of an output signal block color image and including at least two different data values spatially arranged in a pattern indicating image locations of at least two colors produced by applying a color difference quantity to an unspecified reference color in the output signal block color image;

the processor, further in executing the instructions, obtaining an output color value as the unspecified reference color;

the processor, still further in executing the instructions, obtaining the color difference quantity using the output color value;

the processor, further in executing the instructions, producing an output signal block color image using the output color value, the color difference quantity and the selected modulation pattern data structure;

the output signal block color image having a spatially arranged pattern of image regions having color values produced by modulating the output color value by the color difference quantity subject to a requirement that the output color value be an average color of all of the color values of the color modulated image regions;

the processor, still further in executing the instructions, producing an encoded color image including the output signal block color image as an image region therein.