Self-registering spread-spectrum barcode method

• US 20020179717A1
• Filed: 05/30/2001
• Published: 12/05/2002
• Est. Priority Date: 05/30/2001
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Cummings, Eric B., Even, William R. Jr.
• Granted Patent: US 6,814,289 B2
• Time in Patent Office: Days
• US Class Current: 235/462.25
• 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/1473 error correction

Abstract

A novel spread spectrum barcode methodology is disclosed that allows a barcode to be read in its entirety even when a significant fraction or majority of the barcode is obscured. The barcode methodology makes use of registration or clocking information that is distributed along with the encoded user data across the barcode image. This registration information allows for the barcode image to be corrected for imaging distortion such as zoom, rotation, tilt, curvature, and perspective.

Claims

1. A method of recording and printing user data on a printed medium, comprising the steps of:

a. encoding the user data to form an encoded user data array A;

b. modulating user data array A using a two-dimensional pseudo-random kernel K_m, to form a modulated data array E;

c. formatting data array E to produce a pixel-based two-dimensional barcode array B; and

d. printing barcode array B onto said portion of the printed medium,

wherein the recorded and printed user data is distributed evenly across said portion of the printed medium.

2. The method of claim 1, wherein the user data is encoded so that user data array A additionally comprises a fiducial signature.

3. The method of claim 2, wherein the fiducial signature comprises a recognizable signature texture and a signature pattern.

4. The method of claim 1, further comprising step (e) superimposing onto barcode array B a formatted version of a two-dimensional signature array C.

5. The method of claim 4, wherein in step (a), the user data is encoded so as to have a signature texture incorporated therein, and further wherein signature array C contains a signature pattern bitmap modulated using a two-dimensional pseudo-random kernel K_c.

6. The method of claim 5, wherein the two-dimensional kernels K_m and K_c are the same.

7. The method of claim 4, wherein signature array C comprises a signature texture array modulated using two-dimensional pseudo-random kernel K_c.

8. The method of claim 4, wherein in step (a) the user data is encoded so as to have a signature pattern incorporated therein, and further wherein, signature array C contains a signature texture modulated using a two-dimensional pseudo-random kernel K_c.

10. The method of claim 1, further comprising in combination with step (c) formatting and superimposing onto formatted data array E a second two-dimensional modulated data array E′

, wherein data array E′

is produced by modulating a second data set with a second two-dimensional pseudo-random kernel, K′

_m and barcode array B is produced by the superimposition of formatted data array E′

onto formatted data array E.

11. A readable barcode made using the method of claim 1.

12. A readable barcode made using the method of claim 2.

13. A readable barcode made using the method of claim 4.

14. The readable barcode of claim 13, wherein up to approximately 80% of the barcode has been obfuscated.

15. The readable barcode of claim 14, wherein the obfuscation is caused by overlaid text or graphics.

16. The readable barcode of claim 14, wherein the obfuscation is caused by damage or partial destruction of the printed medium.

17. A method of reading user data stored on a printed medium according to the method of claim 1, comprising;

a. scanning barcode array B to obtain data array E;

b. demodulating data array E with a two-dimensional pseudo-random kernel K_d that is related to K_m, to obtain user data array A;

c. decoding user data array A to obtain the encoded user data.

18. A method of reading user data stored on a printed medium according to the method of claim 2, comprising;

a. scanning barcode array B to obtain an uncorrected version of data array E;

b. demodulating data array E with a two-dimensional pseudo-random kernel K_d that is related to two-dimensional pseudo-random kernel K_m, to obtain an uncorrected version of user data array A;

c. transforming the uncorrected version of user data array A using the fiducial signature contained therein to produce a corrected version of user data array A; and

d. decoding the corrected version of user data array A to obtain the encoded user data.

19. A method of reading user data stored on a printed medium according to the method of claim 4, comprising;

a. scanning barcode array B to obtain a raw scan;

b. demodulating the raw scan with a two-dimensional pseudo-random kernel K_c that is not related to two-dimensional pseudo-random kernel K_m, to obtain an uncorrected version of signature array C;

c. transforming the raw scan using the uncorrected version of signature array C to obtain a corrected version of data array E;

d. demodulating the corrected version of data array E with a two-dimensional pseudo-random kernel K_d that is related to two-dimensional pseudo-random kernel K_m, to produce a corrected version of user data array A; and

e. decoding the corrected version of user data array A to obtain the encoded user data.

20. The method of claim 19, wherein steps (a) through (c) are performed iteratively on subsections of barcode array B and signature array C contains a signature texture and a signature pattern.

21. A method of reading user data stored on the barcode of claim 14 comprising the steps of

a. scanning barcode array B to obtain a raw scan;

b. thresholding the raw scan;

c. demodulating the thresheld raw scan with a two-dimensional pseudo-random kernel K_c that is not related to two-dimensional pseudo-random kernel K_m, to obtain an uncorrected version of signature array C;

d. transforming the raw scan using the uncorrected version of signature array C to obtain a corrected version of data array E;

e. demodulating the corrected version of data array E with a two-dimensional pseudo-random kernel K_d that is related to two-dimensional pseudo-random kernel K_m but not related to two-dimensional pseudo-random kernel K_c, producing a corrected version of user data array A; and

c. decoding the corrected version of user data array A to obtain the encoded user data.

22. The method of claim 21, further comprising iteratively repeating step (c) on subsections of barcode array B and signature array C contains a signature texture and a signature pattern.

9. The method of claim 9, wherein two-dimensional pseudo-random kernels K_c and K_m are the same.