Decoding data from patterned color modulated image regions in a color image

• US 6,141,441 A
• Filed: 09/28/1998
• Issued: 10/31/2000
• Est. Priority Date: 09/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): Au, Amelia
• Assistant Examiner(s): Wu, Jingge
• Application Number:
  US09/162,257
• Time in Patent Office: 764 Days
• Field of Search: 382/166, 382/167, 382/232, 382/183, 382/233, 235/469, 235/494
• US Class Current: 382/166
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking

Abstract

A technique for decoding message data that has been encoded into a printed color image locates small image regions called signal cells that carry the encoded message. Each signal cell is composed of a spatial pattern of colored subregions that collectively have an overall average color. The colors of the subregions are defined as changes (modulations) to the average color in one or more directions in a multi-dimensional color space. The decoding technique uses a set of valid signal blocks, each of which is a unique pattern of color modulated subregions. There is a valid signal block for each valid message value defined in the coding scheme. The decoding operation first locates the positions of the signal cells in the acquired image and then subtracts the local average color of each signal cell from the cell to produce a received signal block. Then the decoding operation determines which valid signal block each received signal block is by comparing each valid signal block to a received signal block. One implementation of the decoding technique decodes signal cells that have been arranged in the acquired image in a 2D array by synchronizing an imaginary grid-like structure with the most likely position of all of the signal cells. In one embodiment, a color space direction is selected for the color modulations that results in the differently colored subregions of a signal cell being substantially imperceptible to a human viewer, thus making the pattern that carries the message substantially imperceptible in an encoded image.

Claims

1. A method for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image;

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 acquired color image including a plurality of image regions therein;

each image region, referred to as a received signal cell, encoding a message value included in a set of valid unique message values in a predetermined coding scheme;

each received signal cell including a plurality of subregions having at least two different colors spatially arranged in a pattern therein;

the at least two different colors of the received signal cell having an average color value thereof;

determining an image location in the acquired image of each received signal cell using a set of valid signal block data structures;

each signal block data structure representing and being uniquely paired with one of the valid message values in the coding scheme;

each signal block data structure defining size dimensions of a received signal cell and including variable data indicating a color difference quantity;

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

for each received signal cell identified by location in the acquired image, decoding the received signal cell including,

computing the average color value of the received signal cell;

computing a color difference quantity for the average color value and updating the variable data indicating the color difference quantity in each valid signal block data structure to produce updated valid signal block data structures;

subtracting the average color value from the received signal cell to produce a received signal block data structure;

the received signal block data structure indicating color difference quantities between each of the at least two different colors and the average color value;

determining which one of the plurality of updated valid signal block data structures is substantially identical to the received signal block data structure; and

storing the message value paired with the updated signal block data structure determined to be substantially identical to the received signal block data structure.

2. The method of claim 1 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein

the color difference quantity is a color space direction and associated color modulation magnitude in a multi-dimensional color space that, when applied to the average color value of a received signal cell, produces the at least two different colors spatially arranged in the pattern of subregions therein;

and

computing the color difference quantity for the average color value includes computing the color space direction and associated color modulation magnitude in the multi-dimensional color space subject to a requirement that the at least two different colors of the subregions in a received signal cell are simultaneously capable of being detected by a digital image capture device and visually have an overall appearance to a human viewer of the average color value in the acquired color image such that the at least two different colors in the received signal cell are substantially imperceptible.

3. The method of claim 2 wherein the color difference quantity is a plurality of orthogonal color space directions in a multi-dimensional color space each having an associated color modulation magnitude;

and wherein computing the color difference quantity for the average color value includes computing each of the plurality of orthogonal color space directions and associated color modulation magnitudes;

each orthogonal color space direction and associated color modulation magnitude being computed subject to the requirement that the at least two different colors of the subregions in a received signal cell are simultaneously capable of being detected by a digital image capture device and visually have an overall appearance to a human viewer of the average color value in the acquired color image such that the at least two different colors in the received signal cell are substantially imperceptible.

4. The method of claim 1 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein

the plurality of received signal cells encoding message values in the acquired color image is spatially arranged in a plurality of ordered rows and columns having the form of a two-dimensional array;

and

determining the image locations of the received signal cells in the acquired image includes determining a most likely set of image locations that collectively identify locations of all received signal cells in the two-dimensional array that are included in the set of valid signal block data structures.

5. The method of claim 4 wherein determining the most likely set of image locations that collectively identify all of the received signal cells includes

defining a hypothetical grid-like structure having size dimensions and spacing indicating size dimensions and spacing of the plurality of received signal cells arranged in the two-dimensional array;

the hypothetical grid-like structure including a set of grid-cell locations each of which identifies an expected location of a received signal cell; and

determining a grid location of the hypothetical grid-like structure in the acquired image in which the set of grid-cell locations indicates a maximum number of signal block data structures included in the set of valid signal block data structures;

the set of grid-cell locations being the most likely set of image locations that collectively identify all of the received signal cells.

6. The method of claim 1 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein

the plurality of received signal cells encoding message values in the acquired color image are spatially arranged therein in a one-dimensional array;

and

determining the image locations of the received signal cells in the acquired image includes determining a most likely set of image locations that collectively identify locations of all received signal cells in the one-dimensional array that are included in the set of valid signal block data structures.

7. A method for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image;

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 acquired color image including a plurality of image regions therein;

each image region, referred to as a received signal cell, encoding a message value included in a set of valid unique message values in a predetermined coding scheme;

each received signal cell including a plurality of subregions having at least two different colors spatially arranged in a pattern therein;

the at least two different colors of the received signal cell having an average color value thereof;

determining an image location in the acquired image of each received signal cell using a plurality of valid modulation pattern data structures;

each modulation pattern data structure representing and being uniquely paired with one of the valid message values in the coding scheme;

each modulation pattern data structure defining size dimensions of a received signal cell and including scaling data indicating a spatially arranged modulation pattern specifying image locations in a received signal cell of scaled color difference quantities produced by applying the scaling data to the color difference quantity; and

for each received signal cell identified by location in the acquired image, decoding the received signal cell including,

computing the average color value of the received signal cell;

computing a color difference quantity for the average color value;

subtracting the average color value from the received signal cell to produce a received signal block data structure indicating color difference quantities between each of the at least two different colors and the average color value;

determining which one of the plurality of valid modulation pattern data structures is substantially identical to the received signal block data structure after adjusting one of either the received signal block or the plurality of valid modulation pattern data structures by the color difference quantity; and

storing the message value paired with the modulation pattern data structure determined to be substantially identical to the received signal block data structure.

8. The method of claim 7 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein

the plurality of received signal cells encoding message values in the acquired color image is spatially arranged in a plurality of ordered rows and columns having the form of a two-dimensional array;

and

determining the image locations of the received signal cells in the acquired image using the plurality of valid modulation pattern data structures includes determining a most likely set of image locations that collectively identify locations of all received signal cells in the two-dimensional array that are included in the set of valid modulation pattern data structures.

9. A method for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image;

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 acquired color image including a plurality of image regions therein;

each image region, referred to as a received signal cell, encoding a message value included in a set of valid unique message values in a predetermined coding scheme;

each received signal cell including a plurality of subregions having at least two different colors spatially arranged in a pattern therein;

the at least two different colors of the received signal cell having an average color value thereof;

determining an image location in the acquired image of each received signal cell using a set of valid signal block data structures;

each signal block data structure representing and being uniquely paired with one of the valid message values in the coding scheme;

each signal block data structure defining size dimensions of a received signal cell and including data indicating a predetermined color space direction and associated color modulation magnitude in a multi-dimensional color space collectively indicating a color difference quantity;

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

for each received signal cell identified by location in the acquired image, decoding the received signal cell including,

computing the average color value of the received signal cell and subtracting the average color value from the received signal cell to produce a received signal block data structure;

the received signal block data structure indicating color difference quantities between each of the at least two different colors and the average color value;

determining which one of the plurality of valid signal block data structures is substantially identical to the received signal block data structure; and

storing the message value paired with the signal block data structure determined to be substantially identical to the received signal block data structure.

10. The method of claim 9 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein

the plurality of received signal cells encoding message values in the acquired color image is spatially arranged in a plurality of ordered rows and columns having the form of a two-dimensional array;

and

determining the image locations of the received signal cells in the acquired image using the plurality of valid signal block data structures includes determining a most likely set of image locations that collectively identify locations of all received signal cells in the two-dimensional array that are included in the set of valid signal block data structures.

11. The method of claim 9 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein each received signal cell has a known average color value identical to the average color value of all other image regions encoding message values;

the at least two different colors of each received signal cell having the known average color value thereof; and

wherein computing the average color value of each received signal cell includes using the known average color value.

12. The method of claim 9 for operating a processor-controlled machine to decode a plurality of message values encoded in an acquired color image wherein the acquired color image is a gray scale image including only color values included in a set of gray scale color values that ranges from black to gray to white;

and wherein the predetermined color space direction indicates the set of gray scale color values in the multi-dimensional color space.

13. 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, receiving an acquired color image including a plurality of image regions therein;

each image region, referred to as a received signal cell, encoding a message value included in a set of valid unique message values in a predetermined coding scheme;

each received signal cell including a plurality of subregions having at least two different colors spatially arranged in a pattern therein;

the at least two different colors of the received signal cell having an average color value thereof;

the processor, further in executing the instructions, determining an image location in the acquired image of each received signal cell using a plurality of signal block data structures;

each signal block data structure representing and being uniquely paired with one of the valid message values in the coding scheme;

each signal block data structure defining size dimensions of a received signal cell and including variable data indicating a color difference quantity;

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

the processor, still further in executing the instructions, for each received signal cell identified by location in the acquired image, decoding the received signal cell including,

computing the average color value of the received signal cell;

computing a color difference quantity for the average color value and updating the variable data indicating the color difference quantity in each valid signal block data structure to produce updated valid signal block data structures;

subtracting the average color value from the received signal cell to produce a received signal block data structure;

the received signal block data structure indicating color difference quantities between each of the at least two different colors and the average color value;

determining which one of the plurality of updated signal block data structures is substantially identical to the received signal block data structure; and

storing the message value paired with the updated signal block data structure determined to be substantially identical to the received signal block data structure.