Generating and decoding graphical bar codes

• US 6,722,567 B2
• Filed: 06/07/2001
• Issued: 04/20/2004
• Est. Priority Date: 06/07/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Yen, Jonathan, Levy, Avraham, Shaked, Doron
• Primary Examiner(s): Frech, Karl D.
• Assistant Examiner(s): Labaze, Edwyn
• Application Number:
  US09/877,516
• Publication Number:
  US 20030047612A1
• Time in Patent Office: 1,048 Days
• Field of Search: 235/462.01, 235/462.25, 235/462.27, 235/462.05, 235/468, 235/494, 235/375, 235/456, 235/469, 382/222, 382/217, 382/317, 382/183, 382/100, 382/168, 382/287, 382/298, 382/170, 382/218
• US Class Current: 235/462.01
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1417 2D bar codes

Abstract

Systems and methods for automatically generating and decoding a graphical bar code (i.e., an image that contains inconspicuous graphical modulations that encode embedded information) are described. In one aspect, an invertible graphical operation is applied between regions of a base image and information-encoding graphical templates that are selected from a predefined template set to produce a graphical bar code with regions from which graphical templates are recoverable by applying an inverse graphical operation between graphical bar code regions and corresponding base image regions. In another aspect, an invertible graphical operation is applied between regions of a graphical bar code and corresponding regions of a base image to produce a set of measurement blocks, and information-encoding graphical templates corresponding to the set of measurement blocks with the highest estimated probability is selected from a predefined template set.

Claims

1. A method of generating a graphical bar code, comprising:

applying an invertible graphical operation between regions of a base image and information-encoding graphical templates selected from a predefined template set to produce a graphical bar code with regions from which graphical templates are recoverable by applying an inverse graphical operation between graphical bar code regions and corresponding base image regions.

2. The method of claim 1, wherein the invertible graphical operation corresponds to an exclusive OR (XOR) operation.

3. The method of claim 2, further comprising applying XOR operations between the graphical bar code regions and corresponding base image regions to produce the graphical templates.

4. The method of claim 1, wherein each of the base image regions and the graphical templates has a same number of pixels.

5. The method of claim 4, wherein each of the base image regions and the graphical templates has a common pixel layout.

6. The method of claim 5, wherein the common pixel layout corresponds to a rectangular pixel array.

7. The method of claim 1, wherein each graphical template comprises a pattern of bright and dark pixels.

8. The method of claim 7, wherein the number of bright pixels is greater than the number of dark pixels.

9. The method of claim 7, wherein each pixel location within the predefined template set has an equal probability of being a dark pixel.

10. The method of claim 1, wherein the invertible graphical operation is applied between an ordered sequence of base image regions and a sequence of graphical templates ordered to substantially preserve local dark dot density uniformity across a concatenation of the ordered sequence of graphical templates.

11. The method of claim 1, wherein the invertible graphical operation is applied between respective sub-regions of the base image and respective graphical templates.

12. The method of claim 11, wherein the invertible graphical operation is applied between a predetermined sequence of base image sub-regions and an information-encoding sequence of graphical templates.

13. The method of claim 12, wherein the information-encoding sequence of graphical templates is recoverable by applying the inverse graphical operation between respective sub-regions of the graphical bar code and respective sub-regions of the base image ordered in accordance with the predetermined base image sub-region sequence.

14. A computer program residing on a computer-readable medium and comprising computer-readable instructions for causing a computer to:

apply an invertible graphical operation between regions of a base image and information-encoding graphical templates selected from a predefined template set to produce a graphical bar code with regions from which graphical templates are recoverable by applying an inverse graphical operation between graphical bar code regions and corresponding base image regions.

15. A method of decoding a graphical bar code, comprising:

applying an invertible graphical operation between regions of a graphical bar code and corresponding regions of a base image to produce a set of measurement blocks; and

selecting from a predefined template set information-encoding graphical templates corresponding to the set of measurement blocks with the highest estimated probability.

16. The method of claim 15, wherein the invertible graphical operation corresponds to an XOR operation.

17. The method of claim 15, further comprising computing pixel value probabilities for each of the measurement blocks.

18. The method of claim 17, wherein pixel value probabilities are computed for a given measurement block based upon a weighted average of gray value measurements over the given measurement block.

19. The method of claim 18, wherein the weighted average of gray values is computed by fitting a mask to dot locations over the given measurement block.

20. The method of claim 19, wherein the mask has a truncated Gaussian profile.

21. The method of claim 18, further comprising estimating parameters of probability distributions fit to a histogram of the weighted average of gray value measurements.

22. The method of claim 21, wherein the probability distributions are asymmetric Laplacian distributions.

23. A computer program residing on a computer-readable medium and comprising computer-readable instructions for causing a computer to:

apply an invertible graphical operation between regions of a graphical bar code and corresponding regions of a base image to produce a set of measurement blocks; and

select from a predefined template set information-encoding graphical templates corresponding to the set of measurement blocks with the highest estimated probability.