Distortion resistant double-data correcting color transition barcode and method of generating and using same

• US 6,070,805 A
• Filed: 04/08/1998
• Issued: 06/06/2000
• Est. Priority Date: 04/08/1997
• Status: Expired due to Term

• Current Assignee: Zebra Technologies Corporation
• Original Assignee: Zebra Technologies Corporation
• Inventors: Hohberger, Clive, Kaufman, Jeffrey R.
• Primary Examiner(s): LE, THIEN MINH
• Application Number:
  US09/057,415
• Time in Patent Office: 790 Days
• Field of Search: 235/494, 235/462.04, 235/462.07, 235/462.1, 235/462.01, 235/469
• US Class Current: 235/494
• CPC Class Codes: G06K 19/06028 using bar codes
• CPC Class Codes: G06K 2019/06225 using wavelength selection, e.g. colour code
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence

Abstract

A color barcode symbology is disclosed that can be accurately decoded despite severe distortions, misreads or altered symbols. This disclosed barcode is a color transition barcode having linear growth properties designed to resist the single or combined effects of: scaling distortions, perspective distortions, shear distortions, and wave distortions of both the uniform and non-uniform type distributed across the barcode'"'"'s vertical or horizontal axis. This color barcode symbology is also resistant to missing symbols and altered symbols while offering, high security, error checking, and double error correcting capability.

Claims

1. A barcode for representing encoded data and being capable of being scanned by a barcode reader, said barcode comprising:

a plurality of columns, each column being formed from a plurality of cells, and each column representing a raw value,

each said cell in each said column having a color associated therewith, said color being either from a first set of colors of from a second set of colors, each said color within each said color set having a value assigned thereto,

wherein in each said column, said cells are from either the first set of colors or said second set of colors,

wherein adjacent columns are not formed from the same set of colors, and

wherein continuous cells in each said cell column are not formed from said same color within said set of colors.

2. A barcode as defined in claim 1, wherein a raw value of each said column is computed by:

##EQU4## wherein n is the first position of the cells in the column, n(t) is the total number of cells in the cell column, k is position of the cell within the column and CellValue(k) is the value of a cell placed in position k.

3. A barcode as defined in claim 2, wherein said raw value of each said column is correlated to a data value, a Reed-Soloman value or a miscellaneous value, said data value, said Reed-Soloman value or said miscellaneous value representing said data encoded within said barcode.

4. A barcode as defined in claim 1, wherein said first set of colors are red, green and blue.

5. A barcode as defined in claim 4, wherein the color red has a value of 0, the color green has a value of 1, and the color blue has a value of 2.

6. A barcode as defined in claim 1, wherein said first set of colors are additive colors.

7. A barcode as defined in claim 1, wherein said first set of colors are cyan, magenta and yellow.

8. A barcode as defined in claim 7, wherein the color cyan has a value of 0, the color magenta has a value of 1, and the color yellow has a value of 2.

9. A barcode as defined in claim 1, wherein said first set of colors are subtractive colors.

10. A barcode as defined in claim 1, wherein said first set of colors are red, green and blue and said first set of colors are cyan, magenta and yellow.

11. A barcode as defined in claim 10, wherein the color red has a value of 0, the color green has a value of 1, and the color blue has a value of 2 and the color cyan has a value of 0, the color magenta has a value of 1, and the color yellow has a value of 2.

12. A barcode as defined in claim 1, wherein each said column is one cell wide by eight cells long.

13. A barcode as defined in claim 1, wherein ninety-four columns are provided.

14. A barcode as defined in claim 13, wherein the first forty-seven columns represent data values and the second forty-seven columns represent Reed-Solomon check-digit values.

15. A barcode as defined in claim 14, further including twelve columns for representing information of the structure of the barcode.

16. A barcode as defined in claim 1, wherein said columns which represent data have first and last columns, and further including finder columns adjacent to said first and last columns.

17. A barcode as defined in claim 16, wherein said finder columns are black in color.

18. A barcode as defined in claim 1, wherein said first column in said barcode being formed from one of said first or second sets of active colors and said last column in said barcode being formed from the other of said first or second sets of active colors.

19. A method of reading a barcode formed in accordance with claim 1, wherein each said column has a top cell and a bottom cell, said method comprising the steps of:

(a) providing a barcode reader;

(b) locating the top cell of the column to be decoded using said barcode reader;

(c) scanning from said top cell toward the bottom of said column to be decoded until all of said cells in said column to be decoded have been traversed;

(d) storing the color of each cell in said column to be decoded in an array;

(e) repeating steps (a) through (d) for each column to be decoded until said each column has been decoded;

(f) converting each array into a raw value; and

(g) correlating said raw value to a data value, a Reed-Soloman value or a miscellaneous value, said data value, said Reed-Soloman value or said miscellaneous value representing said data encoded within said barcode.

20. A method in accordance with claim 19, wherein said barcode has first and last columns and a plurality of columns therebetween, and wherein said columns are decoded in order from first to last.

21. A method in accordance with claim 19, wherein in step (f), said array is converting into said raw value number by using the formula:

##EQU5## wherein n is the first position of the cells in the column, n(t) is the total number of cells in the cell column, k is position of the cell within the column and CellValue(k) is the value of a cell placed in position k.

22. A method in accordance with claim 19, wherein step (c) is performed by:

(c1) determining the color of said top cell;

(c2) scanning downwardly from said top cell to the cell proximate thereto using a predetermined scan angle until the cell proximate to said top cell is scanned;

(c3) determining the color of the next-scanned cell;

(c4) determining whether the color of the next-scanned cell is in the same set of colors as said top cell,

(c5) wherein if the color of the next-scanned cell is not in the same set of colors as said top cell, changing the scan angle and scanning the another cell proximate to said top cell and determining whether the color of this last-scanned cell is in the same set of colors as the top cell;

(c6) wherein if the color of the next-scanned cell is in the same set of colors as said top cell, the last-scanned cell is in the column and thereafter scanning downwardly therefrom using said predetermined scan angle to the cell proximate thereto;

(c7) scanning and determining the color of the last-scanned cell;

(c8) determining whether the color of the last-scanned cell is in the same set of colors as said previously-scanned cell,

(c9) wherein if the color of the last-scanned cell is not in the same set of colors as said previously-scanned cell, changing the scan angle and scanning another cell proximate to said previously-scanned cell and determining whether the color of this last-scanned cell is in the same set of colors as the previously-scanned cell;

(c10) wherein if the color of the last-scanned cell is in the same set of colors as said previously-scanned cell, said last-scanned cell is the next cell in said column and thereafter, repeating steps (c6)-(c9) until the end of the column being scanned is reached.

23. A method in accordance with claim 19, wherein said barcode further includes a vertical finder pattern adjacent to said first column and a horizontal finder pattern said top cell of each said column, and wherein the top cell of the first column is located by using said barcode reader to locate said vertical finder pattern and said horizontal finder pattern;

scanning said barcode to find the top right, bottom right and bottom left corners of said barcode to define the size of said barcode, approximating the position of said top cell of said first column using the size of said barcode.

24. A method in accordance with claim 23, wherein a center point of said top cell of said first column is approximated using said approximate size and shape of said top cell of said first column.

25. A method in accordance with claim 19, wherein if the barcode is damaged and said steps (a) through (g) cannot decode the entire length of one of said columns, the values obtained using steps (a) through (g) are saved in said array and the following steps are carried out to decode each column which have not been decoded by steps (a) through (g):

(h) locating the bottom cell of said column which has not been decoded using said barcode reader;

(i) scanning toward the top of said column which has not been decoded until all of said cells in said column which has not been decoded have been traversed and decoded;

(j) storing the color of each cell in said column which has not been decoded in said array; and

(k) converting said array into a number which represents the data encoded within said barcode.

26. A method in accordance with claim 25, wherein step (i) is performed by:

(i1) determining the color of said bottom cell;

(i2) scanning upwardly from said bottom cell to the cell proximate thereto using a predetermined scan angle until the cell proximate to said bottom cell is scanned;

(i3) determining the color of the next-scanned cell;

(i4) determining whether the color of the next-scanned cell is in the same set of colors as said bottom cell,

(i5) wherein if the color of the next-scanned cell is not in the same set of colors as said bottom cell, changing the scan angle and scanning the another cell proximate to said bottom cell and determining whether the color of this last-scanned cell is in the same set of colors as the bottom cell;

(i6) wherein if the color of the next-scanned cell is in the same set of colors as said bottom cell, said next-scanned cell is in the column being scanned and thereafter scanning upwardly therefrom using said predetermined scan angle to the cell proximate thereto;

(i7) scanning and determining the color of the last-scanned cell;

(i8) determining whether the color of the last-scanned cell is in the same set of colors as said previously-scanned cell,

(i9) wherein if the color of the last-scanned cell is not in the same set of colors as said previously-scanned cell, changing the scan angle and scanning another cell proximate to said previously-scanned cell and determining whether the color of this last-scanned cell is in the same set of colors as the previously-scanned cell;

(i10) wherein if the color of the last-scanned cell is in the same set of colors as said previously-scanned cell, said last-scanned cell is the next cell in said column and thereafter, repeating steps (i7)-(i9) until the end of the column being scanned is reached.

27. A barcode as defined in claim 1, wherein each said column has top and bottom cells, said top and bottom cells being of different colors within said set of colors from which said cells in said column are formed.

28. A barcode as defined in claim 27, wherein a raw value of each said column is computed by:

##EQU6## wherein n is the first position of the cells in the column, n(t) is the total number of cells in the cell column, k is position of the cell within the column and CellValue(k) is the value of a cell placed in position k.

29. A barcode as defined in claim 28, wherein said raw value of each said column is correlated to a data value, a Reed-Soloman value or a miscellaneous value, said data value, said Reed-Soloman value or said miscellaneous value representing said data encoded within said barcode.

30. A method of reading a barcode formed in accordance with claim 27, wherein each said column has a top cell and a bottom cell, said method comprising the steps of:

(a) providing a barcode reader;

(b) locating the top cell of the column to be decoded using said barcode reader;

(c) scanning from said top cell toward the bottom of said column to be decoded until all of said cells in said column to be decoded have been traversed;

(d) storing the color of each cell in said column to be decoded in an array;

(e) repeating steps (a) through (d) for each column to be decoded until said each column has been decoded;

(f) converting each array into a raw value; and

(g) correlating said raw value to a data value, a Reed-Soloman value or a miscellaneous value, said data value, said Reed-Soloman value or said miscellaneous value representing said data encoded within said barcode.

31. A method in accordance with claim 30, wherein said barcode has first and last columns and a plurality of columns therebetween, and wherein said columns are decoded in order from first to last.

32. A method in accordance with claim 30, wherein in step (f), said array is converting into said raw value number by using the formula:

##EQU7## wherein n is the first position of the cells in the column, n(t) is the total number of cells in the cell column, k is position of the cell within the column and CellValue(k) is the value of a cell placed in position k.

33. A method in accordance with claim 30, wherein step (c) is performed by:

(c1) determining the color of said top cell;

(c2) scanning downwardly from said top cell to the cell proximate thereto using a predetermined scan angle until the cell proximate to said top cell is scanned;

(c3) determining the color of the next-scanned cell;

(c4) determining whether the color of the next-scanned cell is in the same set of colors as said top cell, (c5) wherein if the color of the next-scanned cell is not in the same set of colors as said top cell, changing the scan angle and scanning the another cell proximate to said top cell and determining whether the color of this last-scanned cell is in the same set of colors as the top cell;

(c6) wherein if the color of the next-scanned cell is in the same set of colors as said top cell, the last-scanned cell is in the column and thereafter scanning downwardly therefrom using said predetermined scan angle to the cell proximate thereto;

(c7) scanning and determining the color of the last-scanned cell;

(c8) determining whether the color of the last-scanned cell is in the same set of colors as said previously-scanned cell,

(c9) wherein if the color of the last-scanned cell is not in the same set of colors as said previously-scanned cell, changing the scan angle and scanning another cell proximate to said previously-scanned cell and determining whether the color of this last-scanned cell is in the same set of colors as the previously-scanned cell;

(c10) wherein if the color of the last-scanned cell is in the same set of colors as said previously-scanned cell, said last-scanned cell is the next cell in said column and thereafter, repeating steps (c6)-(c9) until the end of the column being scanned is reached.

34. A method in accordance with claim 30, wherein said barcode further includes a vertical finder pattern adjacent to said first column and a horizontal finder pattern said top cell of each said column, and wherein the top cell of the first column is located by using said barcode reader to locate said vertical finder pattern and said horizontal finder pattern;

scanning said barcode to find the top right, bottom right and bottom left corners of said barcode to define the size of said barcode, approximating the position of said top cell of said first column using the size of said barcode.

35. A method in accordance with claim 34, wherein a center point of said top cell of said first column is approximated using said approximate size and shape of said top cell of said first column.

36. A method in accordance with claim 30, wherein if the barcode is damaged and said steps (a) through (g) cannot decode the entire length of one of said columns, the values obtained using steps (a) through (g) are saved in said array and the following steps are carried out to decode each column which have not been decoded by steps (a) through (g):

(h) locating the bottom cell of said column which has not been decoded using said barcode reader;

(i) scanning toward the top of said column which has not been decoded until all of said cells in said column which has not been decoded have been traversed and decoded;

(j) storing the color of each cell in said column which has not been decoded in said array; and

(k) converting said array into a number which represents the data encoded within said barcode.

37. A method in accordance with claim 36, wherein step (i) is performed by:

(i1) determining the color of said bottom cell;

(i2) scanning upwardly from said bottom cell to the cell proximate thereto using a predetermined scan angle until the cell proximate to said bottom cell is scanned;

(i3) determining the color of the next-scanned cell;

(i4) determining whether the color of the next-scanned cell is in the same set of colors as said bottom cell,

(i5) wherein if the color of the next-scanned cell is not in the same set of colors as said bottom cell, changing the scan angle and scanning the another cell proximate to said bottom cell and determining whether the color of this last-scanned cell is in the same set of colors as the bottom cell;

(i6) wherein if the color of the next-scanned cell is in the same set of colors as said bottom cell, said next-scanned cell is in the column being scanned and thereafter scanning upwardly therefrom using said predetermined scan angle to the cell proximate thereto;

(i7) scanning and determining the color of the last-scanned cell;

(i8) determining whether the color of the last-scanned cell is in the same set of colors as said previously-scanned cell,

(i9) wherein if the color of the last-scanned cell is not in the same set of colors as said previously-scanned cell, changing the scan angle and scanning another cell proximate to said previously-scanned cell and determining whether the color of this last-scanned cell is in the same set of colors as the previously-scanned cell;

(i10) wherein if the color of the last-scanned cell is in the same set of colors as said previously-scanned cell, said last-scanned cell is the next cell in said column and thereafter, repeating steps (i7)-(i9) until the end of the column being scanned is reached.

38. A method of encoding data into a barcode which can be read by a barcode reader, said method comprising the steps of:

(a) forming a numerical table of a valid set, said valid set being formed by forming arrays in accordance with the following;

(a1) providing a first set of colors;

(a2) assigning values to each of said colors within said first set;

(a3) providing a plurality of arrays of said values assigned to said first set, wherein continuous numbers in each said array are not the same;

(a4) providing a second set of colors;

(a5) assigning values to each of said colors within said second set;

(a6) providing a plurality of arrays of said values assigned to said second set, wherein continuous numbers in each said array are not the same;

(b) choosing predetermined ones of said valid set to represent data to be encoded within said barcode;

(c) correlating said predetermined ones of said valid set to the colors which are represented by the values within each valid set;

(c) forming said barcode by placing a plurality of columns adjacent to each other, each said column being formed from one of said valid sets of available color schemes.

39. A method in accordance with claim 38, wherein step (a6) further includes wherein the first number and the last number in each said array are not the same.

40. A method in accordance with claim 38, wherein said valid set is further limited by using a genetic algorithm to obtain an active set and wherein values from said active set are used to form said barcode.