System and method for embedding of a two dimensional code with an image

• US 9,865,027 B2
• Filed: 05/01/2015
• Issued: 01/09/2018
• Est. Priority Date: 05/09/2014
• Status: Active Grant

• Current Assignee: Graphiclead LLC
• Original Assignee: Graphiclead LLC
• Inventors: Arce, Gonzalo R., Garateguy, Gonzalo J., Lau, Daniel L.
• Primary Examiner(s): MOYER, ANDREW M
• Application Number:
  US14/701,822
• Publication Number:
  US 20150324946A1
• Time in Patent Office: 984 Days
• Field of Search: 382100, 382294
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 19/06103 the marking being embedded in a human recognizable image, e.g. a company logo with an embedded two-dimensional code
• CPC Class Codes: G06T 1/0007 Image acquisition
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G06T 5/75 Unsharp masking

Abstract

Disclosed are a method and apparatus for embedding a graphic image representation into a two dimensional matrix code by modifying the characteristic values of individual pixels in the image according the values of a provided two dimensional matrix code image. The modified character pixel values are determined using an optimization procedure that minimizes a visual distortion with respect to the original graphic image representation while maintaining the value of a probability of error model below a specified limit.

Claims

1. A method for generating an embedded image comprising a two dimensional code image embedded within a graphic image, the method comprising the steps of:

obtaining, by a processor, the graphic image, wherein the graphic image is represented as a matrix with M rows and N columns of pixels, each pixel having a respective value from a range of values and row and column coordinates within the M by N matrix;

obtaining the two dimensional code image, wherein the two dimensional code is represented as a matrix with M rows and N columns of pixels, each two dimensional code image pixel having either a first value or a second value and row and column coordinates within the M by N matrix;

subdividing the M by N graphic image matrix into sub-blocks of m rows and n columns of pixels, where m is less than M and n is less than N;

subdividing the M by N two dimensional code image matrix into sub-blocks of m rows and n columns of pixels;

where m is less than M and n is less than N, wherein each sub-block of the two dimensional code corresponds to a sub-block of the graphic image having an identical pixel row and column coordinates as the two dimensional code sub-block;

applying, in each graphic image sub-block, a first filter to identify a graphic image center region having a plurality of central pixels around a center pixel of the respective graphic image sub-block;

identifying pixels in each graphic image sub-block by applying a second filter to surrounding pixels outside the center region of each graphic image sub-block for luminance value modification, wherein each identified pixel corresponds to a pixel in a sub-block of the two dimensional code with an identical pixel row and column coordinates;

modifying luminance values of central pixels in the center region and the identified pixels surrounding the center region in each graphic image sub-block based on a probability of detection model related to the obtained two dimensional code image; and

for each sub-block of the two dimensional code, replacing pixel values in the two dimensional code sub-block with the modified pixel luminance values of the identical pixel row and column coordinate from the graphic image sub-block.

2. The method of claim 1, wherein the step of identify pixels in each graphic image sub-block for luminance value modification by applying the filter, comprises:

storing the results of the application of the first filter to each graphic image sub-blocks of the plurality of graphic image sub-blocks in memory;

storing the results of the application of the second filter to each graphic image sub-blocks of the plurality of graphic image sub-blocks in memory.

3. The method of claim 1, further comprising:

determining an optimal value for modifying the identified pixel luminance values based on a cost function, wherein the cost function calculates distortion of the embedded image; and

based on a selected probability of detection error model, optimizing image characteristic parameters used in the modifying of the identified pixel luminance values.

4. A method for encoding data in a graphic image, the method comprising the steps of:

receiving, by a processor, data to encode;

generating a QR code from the data, wherein the generated QR code is represented as a QR code matrix with M rows and N columns and where each element of the QR code matrix is one of two unique values;

obtaining the graphic image;

generating a graphic image matrix with M rows and N columns where each element of the graphic image matrix has a value;

dividing the QR code matrix and the graphic image matrix into sub-blocks of m rows and n columns of elements, where m is less than M and n is less than N;

wherein each graphic image sub-block includes a sub-set of element values inside a center region having a plurality of central elements around a center element, and a subset of elements around the center region, and for each graphic image sub-block;

modifying a sub-set of element values inside a center region of a graphic image sub-block of the graphic image matrix based upon the element values of QR code elements in a QR code sub-block with the same element rows and columns as the center region of the graphic image sub-block, wherein the center region includes a plurality of central pixels around a center pixel of the respective graphic image sub-block;

modifying a sub-set of element values of the elements of the graphic image sub-block other than the elements inside the center region of the graphic image sub-block;

defining a sub-set of elements in a corresponding QR code sub-block of the QR code matrix; and

replacing element values of the defined sub-set of elements in the corresponding sub-block of the QR code matrix with the modified element values of the graphic image matrix sub-block.

5. The method of claim 4, wherein the graphic image is a gray-scale image having a single scalar value for each element in the M by N matrix.

6. The method of claim 4, wherein:

the graphic image is a color image composed of a red, green, and blue scalar value for each element in the M by N matrix; and

the modified element values of each of the graphic image matrix sub-blocks include modified red, green and blue scalar values.

7. The method of claim 4, wherein the graphic image is a binary image composed of elements having only two possible values in the M by N matrix.

8. The method of claim 4, wherein the center region of each of the sub-blocks of m rows and n columns of the graphic image matrix is a square matrix of d rows and d columns where d<

m and d<

n.

9. The method of claim 4, wherein the modifying comprises:

distributing the modified sub-set of elements in the image matrix within the sub-block of m rows and n columns based on a location determined according to a predetermined ordering stored in a data storage.

10. The method of claim 4, further comprising:

minimizing a cost function to derive the modified sub-set of element values of the graphic image matrix inside each graphic image sub-block.

21. The method of claim 6, further comprising:

optimizing red, green and blue scalar values based on a cost function and a target luminance for a color space of the graphic image to obtain the modified red, green and blue scalar values.

11. A system for encoding data in a graphic image, the system comprising:

a data storage;

at least one user interface;

a network interface; and

a processor, coupled to the data storage, the at least one user interface and the network interface, wherein the processor is programmed with machine-readable instructions for controlling the system to perform functions, including functions to;

receive, via the at least one user interface, data in a message for encoding;

generate a QR code from the data, wherein the generated QR code is represented as a QR code matrix with M rows and N columns and where each element of the QR code matrix is one of two unique values;

obtain a graphic image;

generate from the obtained graphic image a graphic image matrix with M rows and N columns where each element of the graphic image matrix has a value;

divide the QR code matrix and the graphic image matrix into sub-blocks of m rows and n columns of elements, where m is less than M and n is less than N;

wherein each graphic image sub-block includes a sub-set of element values inside a center region having a plurality of central elements around a center element, and a subset of elements around the center region, and for each graphic image sub-block;

modify a sub-set of element values inside a center region of a graphic image subblock of the graphic image matrix based upon the element values of QR code elements in a QR code sub-block with the same element rows and columns as the center region of the graphic image sub-block;

modifying a sub-set of element values of the elements of the graphic image sub-block other than the elements inside the center region of the graphic image sub-block;

define a sub-set of elements in a corresponding QR code sub-block of the QR code matrix; and

replace element values of the defined sub-set of elements in the corresponding sub-block of the QR code matrix with the modified element values of the graphic image matrix sub-block.

12. The system of claim 11, wherein the machine-readable instructions for controlling the system to perform the function of modifying the sub-set of element values in each of the graphic image sub-blocks further comprises instructions for performing a function to:

minimize a cost function to derive the modified sub-set of element values of the graphic image matrix inside each graphic image sub-block.

13. The system of claim 11, wherein the machine-readable instructions for controlling the system to perform the function of modifying the sub-set of element values of the graphic image sub-block other than the elements inside the center region of the graphic image sub-block further comprises instructions for performing a function to:

impose a constraint on a probability of decoding error to derive the modified sub-set of element values of the graphic image matrix inside each graphic image sub-block.

14. The system of claim 13, wherein the constraint on the probability of decoding error is derived from application of a priority mask.

15. The system of claim 14, wherein the processor is further programmed with machine-readable instructions for controlling the system to perform functions to:

receive the priority mask via the at least one user interface.

16. The system of claim 14, wherein the processor is further programmed with machine-readable instructions for controlling the system to perform functions to:

derive the priority mask from the obtained graphic image.

17. The system of claim 11, wherein the machine-readable instructions for controlling the system to perform the function of modifying the sub-set of element values for each of the graphic image sub-blocks further comprises instructions for performing functions to:

apply a priority mask centered on each of the QR code sub-blocks and each of the graphic image sub-blocks;

based on the results of the applied priority mask, derive a probability of decoding error as a function of n parameters;

identify elements in each graphic image sub-block for modification, wherein the identification includes a unique coordinate location and value of each element in the respective graphic image sub-block for modification.

18. The system of claim 17, wherein:

the probability of decoding error is composed as a linear combination of two components;

a probability of detection error is defined as the probability of incorrectly detecting the value of the center elements of a QR code; and

a probability of binarization error is defined as the probability of incorrectly detecting any element of the QR code matrix at the decoder; and

the processor is further configured to control the system to perform functions, including functions to;

derive a cost function based on a probability of decoding error; and

determine an optimal value of the modified element values of each of the graphic image matrix sub-blocks based on the results of the cost function.

19. The system of claim 18, wherein the machine-readable instructions for controlling the system to perform the function of modifying the sub-set of element values for each of the graphic image sub-blocks further comprises instructions for performing functions to:

optimize color space luminance values for the sub-set of elements of each of the graphic image sub-blocks based on the cost function and a target luminance for a color space of the graphic image.

20. The system of claim 11, wherein the user interface is selected from a group consisting of a keyboard, keypad, a mouse, a touchpad, a trackball, cursor direction keys, a touchscreen, a display device, and a monitor.

22. A system for encoding data in a graphic image, the system comprising:

a data storage;

at least one user interface selected from a group consisting of a keyboard, keypad, a mouse, a touchpad, a trackball, cursor direction keys, a touchscreen, a display device, and

a monitor;

a network interface; and

a processor, coupled to the data storage, the at least one user interface and the network interface, wherein the processor is programmed with machine-readable instructions for controlling the system to perform functions, including functions to;

receive, via the at least one user interface, data in a message for encoding;

generate a QR code from the data, wherein the generated QR code is represented as a QR code matrix with M rows and N columns and where each element of the QR code matrix is one of two unique values;

obtain a graphic image;

generate from the obtained graphic image a graphic image matrix with M rows and N columns where each element of the graphic image matrix has a value;

divide the QR code matrix and the graphic image matrix into sub-blocks of m rows and n columns of elements, where m is less than M and n is less than N;

wherein each graphic image sub-block includes a sub-set of element values inside a center region having a plurality of central elements around a center element, and a subset of elements around the center region, and for each graphic image sub-block;

modify a sub-set of element values inside a center region of a graphic image subblock of the graphic image matrix based upon the element values of QR code elements in a QR code sub-block with the same element rows and columns as the center region of the graphic image sub-block;

modifying a sub-set of element values of the elements of the graphic image sub-block other than the elements inside the center region of the graphic image sub-block;

define a sub-set of elements in a corresponding QR code sub-block of the QR code matrix; and

replace element values of the defined sub-set of elements in the corresponding sub-block of the QR code matrix with the modified element values of the graphic image matrix sub-block.