Variable formatting of digital data into a pattern

• US 6,176,427 B1
• Filed: 08/23/1999
• Issued: 01/23/2001
• Est. Priority Date: 03/01/1996
• Status: Expired due to Term

• Current Assignee: Kaldren LLC (IP Edge LLC)
• Original Assignee: Cobblestone Software, Inc.
• Inventors: Antognini, Thomas Charles, Antognini, Walter Gerard
• Primary Examiner(s): LE, THIEN MINH
• Application Number:
  US09/382,173
• Time in Patent Office: 519 Days
• Field of Search: 235/494, 235/456, 235/432, 235/462.1, 235/462.11, 235/462.09, 235/462.07, 235/462.04, 235/454
• US Class Current: 235/454
• CPC Class Codes: G06K 1/121 by printing code marks applying code marks to labels B65C9/46; marking or coding completed packages B65B61/26
• CPC Class Codes: G06K 1/123 for colour code marks
• CPC Class Codes: G06K 1/126 by photographic or thermographic registration recording apparatus for measuring instruments G01D15/00
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 19/06046 Constructional details
• CPC Class Codes: G06K 2019/06225 using wavelength selection, e.g. colour code
• CPC Class Codes: G06K 7/0166 by means of clock-signals derived from the code marks, e.g. self-clocking code
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06K 7/1473 error correction
• CPC Class Codes: G06K 7/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code

Abstract

A method of formatting digital data and a method of decoding the formatted digital data. User selectable format parameters vary the dimensions and other attributes of spots and the cells containing those spots as well as other features which the formatting process formats into a pattern. A method of encoding the formatted digital data using these format parameters allows for encoding a substrate optimally for any given printer or scanner. One embodiment provides for markers to facilitate determination of cell locations. In one embodiment the decoding process achieves a pyramid gain of knowledge by locating a landmark (801), which is located in a known position relative to a metasector (802), which contains information about the encoding process used to encode the main body of data (803), which the decoding process decodes to recover the original digital data. Further embodiments include encryption, transmission by facsimile, inclusion of human readable information, and automatic launches of computer files.

Claims

1. A method of decoding digital data values formatted into a pattern comprising the steps of:

determining the locations of cells in a first grouping of contiguous cells where the grouping of contiguous cells contains digital data indicating information concerning the formatting of a plurality of the remaining cells in said pattern,

deriving from said first grouping of contiguous cells said information concerning the formatting of a pattern of a plurality of the remaining cells in said pattern, where the deriving comprises extracting digital data from each cell wherein each cell contains at least one bit of data where one logical state is expressed by the presence in the cell of a spot with one set of attributes and at least one other logical state is expressed by the absence from the cell of a spot with the same set of attributes as a spot the presence of which expresses the first logical state,

determining the locations of said plurality of the remaining cells in said pattern, where said step of determining locations is performed by reference to and use of at least some of said information concerning the formatting of a plurality of the remaining cells in said pattern,

deriving digital data values from said plurality of the remaining cells in said pattern where the deriving comprises extracting digital data from each cell wherein each cell contains at least one bit of data where one logical state is expressed by the presence of a spot with one set of attributes and at least one other logical state is expressed by the absence from the cell of a spot with the same set of attributes as a spot the presence of which expresses the first logical state, whereby digital data is recovered from said pattern.

2. The method of decoding of claim 1 where the cells of said first grouping of contiguous cells are formatted into a plurality of contiguous rows and a plurality of contiguous columns and the cells of said plurality of the remaining cells in said pattern are formatted into a plurality of contiguous rows and a plurality of contiguous columns and where at least one series of markers borders on at least one side of said first grouping of contiguous cells and on at least one side of said plurality of the remaining cells in said pattern and where the steps of determining locations of cells in said pattern is performed by reference to and use of the markers.

3. The method of decoding of claim 2 where all cells are formatted into groupings of contiguous cells and encoded onto a substrate and each grouping of contiguous cells is formatted into a plurality of contiguous rows and a plurality of contiguous columns, and where series of markers border each grouping of contiguous cells on at least two sides, and where a known number of rows exists between the top of each marker and the top of the next marker displaced vertically, and where a known number of columns exists between the left side of each marker and the left side of the next marker displaced horizontally, and where determining locations of cells on the digitally encoded substrate is performed by reference to and use of said series of markers comprising the steps, applied for each grouping of cells between markers, of:

locating a first marker bordering a first grouping of contiguous cells,

determining the vertical coordinate of the top of said first marker,

locating a second marker being the nearest marker displaced vertically from said first marker,

determining the distance from the top of said first marker to the top of the first row of spots,

locating a third marker being the nearest marker displaced horizontally from said first marker,

determining the height of each spot,

determining the lines through the centers of each of the rows of cells by determining the distance from the top of said first marker to the top of said second marker, dividing that distance by the number of rows of cells known to exist between markers, and for each of the known number of rows, adding to said vertical coordinate of the top of said first marker the sum of one-half the height of each spot plus the distance from the top of said first marker to the top of the spots in the first row, plus, for each row of cells, the product from multiplying the result of the division by the number of rows said each row of cells is vertically displaced from the first row of cells,

determining the lines through the centers of each of the columns of cells by determining the lines through the centers of the rightmost and leftmost columns of cells located between said first marker and said third markers, determining the horizontal coordinate of the line through the center of the leftmost column of cells, determining the distance between the lines through the centers of the rightmost and leftmost columns of cells between said first marker and said third marker, dividing that distance by the result derived by subtracting one from the number of columns known to exist between markers, and, for each column, multiplying the result of that division by the number of columns that said each column is horizontally displaced from the leftmost column, and adding that product to the horizontal coordinate of the line through the center of the leftmost column of cells, and

for each cell, determining the location of the cell to be the intersection of the lines through the centers of the cell'"'"'s corresponding row and column.

4. The method of decoding of claim 2 where all cells are formatted into groupings of contiguous cells and encoded onto a substrate and where each grouping of contiguous cells is formatted into a plurality of contiguous rows and a plurality of contiguous columns, and where series of markers border said each grouping of contiguous cells on at least two sides, and where,

for said each grouping of contiguous cells,

a known number of printer pixels separates the markers from the edges of possible spots,

a known number of rows exists between the top of each marker and the top of the next marker displaced vertically,

a known number of columns exists between the right side of each marker and the left side of the next marker displaced horizontally,

each cell has the same height and width,

each spot has the same height and width,

the vertical printer pixel coordinates for the top of a marker and the top of the spots in the nearest row are equal,

and where said first grouping of contiguous cells contains information concerning the encoding of the remaining cells on the digitally encoded substrate where the information includes,

the marker, spot, and cell widths and heights measured in printer pixels,

the value of the known number of printer pixels that horizontally separates the markers from the edges of possible spots in the nearest columns,

the value of said known number of rows,

the value of said known number of columns,

and where the method of decoding further comprises creating an image of the digitally encoded substrate where the various parts of said image can be measured in image pixels and the locations of the various parts can be referenced by horizontal and vertical image pixel coordinates, and where the steps of locating cells on the digitally encoded substrate, applied for each grouping of contiguous cells located between markers, comprise:

locating a first marker bordering a first grouping of contiguous cells,

determining the image pixel coordinates of the center of said first marker,

determining the image pixel coordinates of the top of said first marker,

locating a second marker being the nearest marker displaced vertically from said first marker,

determining the image pixel coordinates of the center of said second marker,

locating a third marker being the nearest marker displaced horizontally from said first marker,

determining the line through the center of each of the rows of cells between said first marker and said second marker by;

determining the distance in image pixels from the center of said first marker to the center of said second marker,

determining the printer pixels vertically separating the centers of said first marker and said second marker by multiplying the value for the known number of rows by the printer pixel cell height,

determining for each of the known number of rows the printer pixel vertical distance from the center of said first marker to the line through the center of the row by subtracting one-half of the printer pixel marker height from the sum of one-half the printer pixel spot height plus the product derived from multiplying the printer pixel cell height by the number of rows that the row is displaced from the top row between said first marker and said second marker,

determining for each of said known number of rows a ratio of printer pixels that the line through the center of that row is vertically displaced from the center of said first marker to said printer pixels vertically separating the centers of said first marker and said second marker,

for each row, adding to the vertical image pixel coordinate of the center of said first marker the product from multiplying the distance in image pixels from the center of said first marker to the center of said second marker by said ratio of printer pixels that the line through the center of that row is vertically displaced from the center of said first marker to said printer pixels vertically separating the centers of said first marker and said second marker,

determining the lines through the centers of each of the columns of cells by

determining the distance in image pixels from the center of said first marker to the center of said third marker,

determining the printer pixels horizontally separating the centers of said first marker and said third marker by determining the sum of the printer pixel marker width, plus the known printer pixel distance horizontally separating said first marker and the nearest edges of possible spots in the nearest column to the right of said first column, plus the printer pixel spot width, plus the product derived from multiplying the cell width by the result derived from reducing by one said value for said known number of columns, plus the known printer pixel distance horizontally separating said third marker and the nearest edges of possible spots in the nearest column to the left of said third marker,

determining for each of the known number of columns the printer pixel horizontal distance from the center of said first marker to the line through the center of the column by determining the sum of half the printer pixel marker width, plus the known printer pixel distance horizontally separating said first marker and the nearest edges of possible spots in the nearest column to the right of said first marker, plus half the printer pixel spot width, plus the product derived from multiplying the printer pixel cell width by the number of columns that the column is horizontally displaced from the nearest column to the right of said first marker,

determining for each of said known number of columns a ratio of printer pixels that the line through the center of that column is horizontally displaced from the center of said first marker to said printer pixels horizontally separating the centers of said first marker and said third marker,

for each column, adding to the horizontal image pixel coordinate of the center of said first marker the product from multiplying the distance in image pixels from the center of said first marker to the center of said third marker by said ratio of printer pixels that the line through the center of that column is horizontally displaced from the center of said first marker to said printer pixels horizontally separating the centers of said first marker and said third marker, and for each cell, determining the location of the cell to be the intersection of the lines through the center of the cell'"'"'s corresponding row and column.

5. The method of decoding of claim 1 wherein said pattern is encoded on a substrate and where said substrate further comprises a landmark and wherein the steps of the method of decoding further comprise an initial step of locating said landmark and wherein the step of determining the locations of said first grouping of contiguous cells is performed by reference to the location of said landmark.

6. The method of decoding of claim 1 done in accordance with the DEDS program.

7. The method of decoding of claim 1 wherein said digital data values are encoded onto a plurality of substrates and wherein said method of decoding further comprises a step of locating each of the groupings of cells on each of said plurality of substrates wherein the steps of determining the locations of cells and deriving digital data values are then applied to each of the groupings of cells on each of said plurality of substrates.

8. The method of decoding of claim 7 further comprising creating a series of images of the groupings of cells from said plurality of digitally encoded substrates wherein the steps of determining the locations of cells and deriving digital data values are then applied to each of the series of images of said plurality of digitally encoded substrates.

9. A method of decoding digital data values from a pattern, the method comprising:

determining formatting information concerning a plurality of first cells contained in a first portion of the pattern from a first feature contained in a second portion of the pattern;

determining the locations of the first cells; and

deriving digital data values from the cells by using the formatting information provided by the first feature.

10. The method of decoding of claim 9, wherein the first feature does not comprise a grouping of cells.

11. The method of decoding of claim 9, wherein the first feature is a marking having dimensions, and wherein the step of determining formatting information comprises determining formatting information based at least in part on an aspect of the marking other than its dimensions.

12. The method of decoding of claim 11 wherein the step of determining formatting information comprises determining formatting information based entirely on an aspect of the marking other than its dimensions.

13. The method of decoding of claim 9 wherein the first feature comprises a grouping of second cells containing digital data, and wherein the step of determining formatting information comprises determining formatting information by deriving the digital data from the second cells.

14. The method of decoding of claim 13 wherein the second cells of the first feature are contiguous.

15. The method of decoding of claim 13 wherein each of a plurality of the first and second cells contain at least one bit of data in which at least one logical state is expressed by the presence of a spot having one set of attributes, and wherein the steps of deriving digital data from the first and second cells comprises determining whether each cell contains a spot having the one set of attributes.

16. The method of decoding of claim 13 wherein the pattern further comprises a second feature, the method further comprising using the second feature to locate the pattern and the location of the first feature.

18. The method of decoding of claim 9, wherein the data is formatted into a series of data values arranged in a pattern, the pattern comprising a plurality of spaces formatted into a plurality of subgroupings of contiguous spaces, the pattern further comprising at least a second series of markers near each of at least two subgroupings of spaces, where the method of decoding comprises:

locating said second series of markers;

locating at least one second marker within the second series of markers; and

locating at least one of said spaces from each of at least two subgroupings of spaces at least in part from the location of the at least one second marker.

19. The method of decoding of claim 18 wherein each of the at least two subgroupings of contiguous spaces is formatted into a plurality of rows and a plurality of columns and wherein a series of markers is located in between each of said subgroupings, and wherein the step of locating at least one space in each of said at least two subgroupings of contiguous spaces comprises:

determining a theoretical line running horizontally from at least one marker in said series of markers;

determining a theoretical distance that each of said spaces should be vertically removed from such theoretical line;

determining a theoretical distance that each of said spaces should be horizontally removed from the marker; and

determining the location of each of said spaces as being the location that is vertically removed from the theoretical line by the distance so determined and horizontally removed from the marker by the distance so determined.

20. The method of decoding of claim 19 wherein all subgroupings of contiguous spaces are formatted into a plurality of rows and a plurality of columns and where a series of markers is located in between each of said subgroupings, and wherein the step of locating a space is applied to each space.

21. The method of decoding of claim 18 wherein the location of at least one of said spaces from each of at least two subgroupings of spaces is at least in part determined from the locations of a plurality of markers of said at least one series of markers.

22. The method of decoding of claim 18 wherein the pattern comprises a plurality of series of markers wherein a series of markers is near each subgrouping of spaces, and wherein the step of locating the space comprises determining the location of at least one marker in each of a plurality of series of markers.

23. The method of decoding of claim 22 wherein each subgrouping of spaces has a series of markers near each of a plurality of sides of said subgrouping and where the step of locating the space comprises determining the location of one marker in each of two series of markers.

17. A method of decoding data wherein the data is formatted into a series of data values arranged in a pattern, the pattern comprising a plurality of spaces and at least one series of markers located between at least two of said spaces, the method comprising:

locating at least one series of markers;

locating at least one marker within the located series of markers; and

locating at least two of said spaces at least in part from the location of the at least one marker.

24. A method of decoding digital data values formatted into a pattern of spaces wherein the presence of a spot in a space represents at least one logical state, the method comprising:

(a) determining the dimensions of each of a plurality of spots;

(b) determining the expected center of each of a plurality of possible spots at least in part by reference to the information determined in step (a); and

(c) determining the presence or absence of spots in at least some spaces by at least in part determining whether a spot exists at the expected center of each of said plurality of possible spots as determined by step (b).

25. The method of decoding data of claim 24 wherein the step of determining the presence or absence of spots comprises determining the presence or absence of spots in each of a grouping of spaces.

26. A method of decoding digital data from a pattern wherein the pattern comprises a plurality of spaces at least some of which can contain a spot that represents at least one bit of said digital data, and wherein at least one way in which digital data is encoded within said pattern is by the presence in at least one space of a spot with at least one attribute different from at least one attribute of the space, such method comprising:

(a) determining the at least one attribute of at least one space of a spot which might be contained within the at least one space; and

(b) decoding at least one bit of data using information obtained in step (a).

27. The method of decoding digital data of claim 26 wherein the at least one attribute is height and wherein the step of decoding at least one bit of data comprises decoding data when the height of the spot is less than the height of the space.

28. The method of decoding digital data of claim 26 wherein the at least one attribute is width and wherein the step of decoding at least one bit of data comprises decoding data when the width of the spot is less than the width of the space.

29. The method of decoding digital data of claim 26 where each of the plurality of spaces can contain a spot, all spots in said plurality of spaces have at least one common attribute, and all of said plurality of spaces have at least one common attribute, and wherein the step of decoding at least one bit of data comprises decoding the data based on the common attribute.

30. The method of decoding data of claim 29 wherein the common attributes of said spots and spaces is height and wherein the height of the spots differ from the height of the spaces.

31. The method of decoding data of claim 29 where the common attributes of said spots and spaces is width and wherein the width of the spots differs from the width of the spaces.

32. The method of decoding digital data of claim 26 wherein at least one feature of the pattern is used in the step of determining at least one attribute of at least one space and of the spot which that space might contain.

33. The method of decoding of claim 32 where the feature comprises a first grouping of contiguous spaces wherein that grouping of contiguous spaces contains digital information concerning the parameters of a plurality of remaining spaces and the spots which those spaces might contain.

34. The method of decoding of claim 26 wherein an attribute is capable of being one of a plurality of possible attributes and where the step of determining at least one attribute comprises selecting at least one of said plurality of possible attributes.

35. A method of decoding data from a pattern at least some of which pattern contains a plurality of spaces formatted in a plurality of subgroupings of contiguous spaces, each subgrouping formatted in a plurality of rows and a plurality of columns, and wherein a series of markers is encoded in said pattern, the method comprising:

locating a first marker; and

using said first marker as a clocking mechanism for at least two subgroupings of spaces.

36. The method of decoding of claim 35 wherein the pattern further comprises a landmark, the method further comprising locating said plurality of subgroupings by reference to the landmark.

37. The method of decoding of claim 35 wherein the pattern comprises a first grouping of contiguous spaces containing digital information concerning the formatting of a plurality of remaining spaces in said pattern, the method comprising:

deriving from said first grouping the digital information contained therein; and

deriving digital data from the remaining spaces by using at least some of the digital information derived from said first grouping.

38. The method of decoding of claim 35 wherein the pattern contains a first grouping of contiguous spaces containing digital information concerning the formatting of at least one marker in said pattern, the method comprising:

deriving from said first grouping the digital information contained therein; and

locating said first marker by using at least some of the digital information derived from said first grouping.