Clock free two-dimensional barcode and method for printing and reading the same

Claim 1

A method of encoding information for printing on a printed medium, comprising the steps of: converting said information into a data stream having a sequence of "0" and "1" characters representing data bits; mapping the data stream to produce a digital two-dimensional bitmap of rows and columns having predetermined vacant bit locations; adding a digital block identifier at each of said predetermined vacant bit locations, each said digital block identifier having a predetermined number of block identifier bits and value to permit the number of rows or columns between the digital block identifiers to be identified; formatting said digital two-dimensional bitmap to produce a pixel based two-dimensional bitmap having data pixels and block identifier pixels; and printing the formatted bitmap onto said printed medium.

Claim 2

A method of encoding information for printing on a printed medium, comprising the steps of: converting said information into a data stream having a sequence of "0" and "1" characters representing data bits; mapping the data stream to produce a digital two-dimensional bitmap of rows and columns having predetermined vacant bit locations; adding a digital block identifier at each of said predetermined vacant bit locations, each said digital block identifier having a predetermined number of block identifier bits and value to permit the number of rows or columns between the digital block identifiers to be identified; formatting said digital two-dimensional bitmap to produce a pixel based two-dimensional bitmap having data pixels and block identifier pixels; and printing the formatted bitmap onto said printed medium.

Claim 3

A method of encoding information for printing on a printed medium, comprising the steps of: converting said information into a data stream having a sequence of "0" and "1" characters representing data bits; randomizing said data stream to produce approximately an equal number of "0" and "1" characters in said data stream; mapping the randomized data stream to produce a digital two-dimensional bitmap of rows and columns having predetermined vacant bit locations; adding a digital block identifier at each of said predetermined vacant bit locations, each said digital block identifier having a predetermined number of block identifier bits and value to permit the number of rows or columns between the digital block identifiers to be identified; formatting said digital two-dimensional bitmap to produce a pixel based two-dimensional bitmap having data pixels and block identifier pixels; and printing the formatted bitmap onto said printed medium.

Claim 4

A method of encoding information for printing on a printed medium, comprising the steps of: converting said information into a data stream having a sequence of "0" and "1" characters representing data bits; randomizing said data stream to produce approximately an equal number of "0" and "1" characters in said data stream; mapping the randomized data stream to produce a digital two-dimensional bitmap of rows and columns having predetermined vacant bit locations; adding a digital block identifier at each of said predetermined vacant bit locations, each said digital block identifier having a predetermined number of block identifier bits and value to permit the number of rows or columns between the digital block identifiers to be identified; formatting said digital two-dimensional bitmap to produce a pixel based two-dimensional bitmap having data pixels and block identifier pixels; and printing the formatted bitmap onto said printed medium.

Claim 5

The method as in one of claims 1 or 2, further comprising the step of compressing said information.

Claim 12

A method of decoding information printed on a printed medium in the form of rows and columns of data pixels representing predetermined information, said data pixels being either a first or a second color, comprising the steps of: reading said information from said printed medium; determining the number of horizontal and vertical edges in each respective row and column of pixels; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; and reading out binary data located at the intersection of each row center line and column center line to produce a signal representative of the encoded information printed on said printed medium.

Claim 13

A method of decoding information printed on a printed medium in the form of rows and columns of data pixels representing predetermined information, said data pixels being either a first or a second color, comprising the steps of: reading said information from said printed medium; determining the number of horizontal and vertical edges in each respective row and column of pixels; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; and reading out binary data located at the intersection of each row center line and column center line to produce a signal representative of the encoded information printed on said printed medium.

Claim 14

A method of decoding randomized information printed on a printed medium in the form of rows and columns of data pixels representing predetermined information, said data pixels being either a first or a second color, comprising the steps of: reading said information from said printed medium; determining the number of horizontal and vertical edges in each respective row and column of pixels; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; reading out binary data located at the intersection of each row center line and column center line to produce a randomized signal representative of the encoded information printed on said printed medium; and derandomizing said randomized signal to decode the randomized information printed on the medium.

Claim 15

A method of decoding randomized information printed on a printed medium in the form of rows and columns of data pixels representing predetermined information, said data pixels being either a first or a second color, comprising the steps of: reading said information from said printed medium; determining the number of horizontal and vertical edges in each respective row and column of pixels; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; reading out binary data located at the intersection of each row center line and column center line to produce a randomized signal representative of the encoded information printed on said printed medium; and derandomizing said randomized signal to decode the randomized information printed on the medium.

Claim 16

A method of decoding information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of data pixels representing a proportional number of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, comprising the steps of: reading said bitmap from said printed medium; reading out binary data from said data pixels and block identifier pixels to produce a two-dimensional digital array representing said bitmap having a selected number of said encoded data bits separated by said block identifier bits; determining each said plurality of block identifier bits by selecting data bits representing substantially the same said predetermined value; counting the number of bits of said encoded data bits between each said block identifier bits; deleting bits of said encoded data bits in excess of said proportional number of encoded data bits between each said block identifier bits; and adding digital bits to said encoded data bits between each said block identifier bits when the number of said encoded data bits is less than said proportional number, so as to decode the information printed on the printed medium.

Claim 17

A method of decoding information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of data pixels representing a proportional number of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, comprising the steps of: reading said bitmap from said printed medium; reading out binary data from said data pixels and block identifier pixels to produce a two-dimensional digital array representing said bitmap having a selected number of said encoded data bits separated by said block identifier bits; determining each said plurality of block identifier bits by selecting data bits representing substantially the same said predetermined value; counting the number of bits of said encoded data bits between each said block identifier bits; deleting bits of said encoded data bits in excess of said proportional number of encoded data bits between each said block identifier bits; and adding digital bits to said encoded data bits between each said block identifier bits when the number of said encoded data bits is less than said proportional number, so as to decode the information printed on the printed medium.

Claim 19

A method of decoding information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of columns of data pixels representing a proportional number of columns of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, comprising the steps of: reading said bitmap from said printed medium; reading out binary data from said data pixels and block identifier pixels to produce a two-dimensional digital array representing said bitmap having rows of said encoded data bits separated by said block identifier bits; determining each said plurality of block identifier bits by selecting the column having bits representing substantially the same said predetermined value; counting the number of columns of said encoded data bits between each column having said block identifier bits; deleting columns of said encoded data bits in excess of said proportional number of columns of encoded data bits between each said column having block identifier bits; and adding columns of digital bits between each said column having block identifier bits when the number of said columns of said encoded data bits is less than said proportional number, so as to decode the information printed on the printed medium.

Claim 20

A method of decoding information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of columns of data pixels representing a proportional number of columns of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, comprising the steps of: reading said bitmap from said printed medium; reading out binary data from said data pixels and block identifier pixels to produce a two-dimensional digital array representing said bitmap having rows of said encoded data bits separated by said block identifier bits; determining each said plurality of block identifier bits by selecting the column having bits representing substantially the same said predetermined value; counting the number of columns of said encoded data bits between each column having said block identifier bits; deleting columns of said encoded data bits in excess of said proportional number of columns of encoded data bits between each said column having block identifier bits; and adding columns of digital bits between each said column having block identifier bits when the number of said columns of said encoded data bits is less than said proportional number, so as to decode the information printed on the printed medium.

Claim 21

A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of rows of data pixels representing a proportional number of rows of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, comprising the steps of: reading said bitmap from said printed medium; determining the number of horizontal and vertical edges in each respective row and column of said bitmap; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; reading out binary data located at the intersection of each row center line and column center line to produce a two-dimensional digital array representing said bitmap having rows of said encoded data bits and block identifier bits; determining each said plurality of block identifier bits by selecting the bits representing substantially the same said predetermined value; counting the number of rows of said encoded data bits between each row having said block identifier bits; deleting rows of said encoded data bits in excess of said proportional number of rows of encoded data bits between each said row having block identifier bits; adding rows of digital bits between each said row having block identifier bits when the number of said rows of said encoded data bits is less than said proportional number; and derandomizing said digital representation of said bitmap, so as to decode the information printed on the printed medium.

Claim 22

A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of rows of data pixels representing a proportional number of rows of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, comprising the steps of: reading said bitmap from said printed medium; determining the number of horizontal and vertical edges in each respective row and column of said bitmap; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; reading out binary data located at the intersection of each row center line and column center line to produce a two-dimensional digital array representing said bitmap having rows of said encoded data bits and block identifier bits; determining each said plurality of block identifier bits by selecting the bits representing substantially the same said predetermined value; counting the number of rows of said encoded data bits between each row having said block identifier bits; deleting rows of said encoded data bits in excess of said proportional number of rows of encoded data bits between each said row having block identifier bits; adding rows of digital bits between each said row having block identifier bits when the number of said rows of said encoded data bits is less than said proportional number; and derandomizing said digital representation of said bitmap, so as to decode the information printed on the printed medium.

Claim 23

A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of data pixels representing a proportional number of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, said printed medium further having printed textual information, said encoded information having at least one vertical or horizontal deskewing strip adjacent thereto, comprising the steps of: reading said textual information and said bitmap from said printed medium; formatting said textual information and said bitmap to a pixel based grayscale representation; setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color to determine the threshold bitmap; locating said threshold bitmap; deskewing said bitmap so that said at least one vertical or horizontal deskewing strip is shifted substantially vertically or horizontally, respectively; determining the number of horizontal and vertical edges in each respective row and column of said bitmap; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; reading out binary data located at the intersection of each row center line and column center line to produce a two-dimensional digital representation of said bitmap having a selected number of said encoded data bits and block identifier bits; determining each said plurality of block identifier bits by selecting data bits representing substantially the same said predetermined value; counting the number of bits of said encoded data bits between each said block identifier bits; deleting bits of said encoded data bits in excess of said proportional number of encoded data bits between each said block identifier bits; adding bits of digital bits to said encoded data bits between each block identifier bits when the number of said encoded data bits is less than said proportional number; derandomizing said digital representation of said bitmap; and error-correcting the derandomized digital representation to produce a substantially error-free signal representative of the encoded information printed on said printed medium.

Claim 24

A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each predetermined number of data pixels representing a proportional number of said encoded data bits being separated by a plurality of block identifier pixels representing block identifier bits having a predetermined value, each of said data and block identifier pixels being either a first or second color, said printed medium further having printed textual information, said encoded information having at least one vertical or horizontal deskewing strip adjacent thereto, comprising the steps of: reading said textual information and said bitmap from said printed medium; formatting said textual information and said bitmap to a pixel based grayscale representation; setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color to determine the threshold bitmap; locating said threshold bitmap; deskewing said bitmap so that said at least one vertical or horizontal deskewing strip is shifted substantially vertically or horizontally, respectively; determining the number of horizontal and vertical edges in each respective row and column of said bitmap; determining the row center lines from the local minima in the horizontal edge counts; determining the column center lines from the local minima in the vertical edge counts; reading out binary data located at the intersection of each row center line and column center line to produce a two-dimensional digital representation of said bitmap having a selected number of said encoded data bits and block identifier bits; determining each said plurality of block identifier bits by selecting data bits representing substantially the same said predetermined value; counting the number of bits of said encoded data bits between each said block identifier bits; deleting bits of said encoded data bits in excess of said proportional number of encoded data bits between each said block identifier bits; adding bits of digital bits to said encoded data bits between each block identifier bits when the number of said encoded data bits is less than said proportional number; derandomizing said digital representation of said bitmap; and error-correcting the derandomized digital representation to produce a substantially error-free signal representative of the encoded information printed on said printed medium.

Claim 25

The method as in one of claims 10, 11, 15 or 16, wherein said step of determining the number of edges includes determining the color of two pixels adjacent to a selected pixel and declaring an edge when the two adjacent pixels are of different colors.

Claim 27

The method as in one of claims 13-15, wherein said step of deleting rows or columns includes selecting which excess rows or columns to delete by selecting the rows or columns having substantially the same digital data as their adjacent rows or columns and wherein said step of adding rows or columns includes adding rows or columns of random data.

Claim 28

The method as in one of claims 14 or 15, wherein said step of adding digital rows or columns further includes, selecting where the added rows or columns are added by determining the position where the adjacent row to each row center line has the maximum hamming distance to said row center line and adding a digital row or column comprised of random data at said position.

Claim 29

The method as in one of claims 12, 15, 16 or 17, wherein said randomized information being randomized bit-by-bit.