GB2265237A - Producing and reading a machine-optically-readable code - Google Patents

Abstract

An apparatus for generating and scanning a machine readable binary code includes a central processing unit which receives an electronic executable binary code and generates an optically machine readable binary code in response thereto. The optically machine readable binary code includes data formed as a matrix in the language of the electronic executable binary code. The central processing unit directly converts the internal electronic executable binary code to a visual binary code without the use of a look up table. The apparatus also reverses the process, scanning a machine optically readable binary code formed in the electronic executable binary code into the electronic executable binary code without the use of a look up table. The apparatus during the scanning process performs a binary search technique to identify the machine optically readable binary code. <IMAGE>

Description

APPARATUS FOR PRODUCING AND SCANNING A MACHINE OPTICALLY READABLE BINARY CODE AND METHOD FOR READING AND PRODUCING THEREOF BACKGROUND OF THE INVENTION This invention relates to an apparatus for generating and scanning a binary code which is optically readable by a machine, and in particular, to a binary code which optically represents an electronic executable binary code which may be operated upon by the apparatus without the benefit of a look up table and a method for scanning such a code.

Optically readable codes are known in the art. One such code is formed as a "checker board" symbol that represents information in the form of black and white squares. Each square contained within the checker board matrix is of equal size to every other square. Furthermore, the squares contained within the matrix are utilized to generate a unique symbol as a combination of light and dark squares. This symbol is formed through a random number generator as known in European Patent Application No. 0278740.

This code has not been satisfactory. The code acts merely as visual fingerprint to be matched by a computer to a corresponding symbol. No binary data is stored within the symbol.

Accordingly, the user of the code must store information somewhere besides the visual symbol. Additionally, since each symbol is generated by permutation of a first binary pattern, the visual symbol must be translated before it is in a machine understandable language. Therefore, the machines which read these codes must first translate the code from the language of the optical code, such as a bar code or the permutated code discussed above, to a machine executable language such as ASCII binary language. This is done utilizing a look up table stored within the machine.

Similarly, when generating the prior art optical code, the internal language of the machine must be converted utilizing a look up table into the corresponding translated optical code. This translated optical code is then printed. Such an apparatus suffers from the disadvantage that it requires excess memory for storing the look up table and utilizes real time to translate between optical code language and machine executable electronic language.

Accordingly, it is desirable to provide an apparatus for generating and reading a machine optically readable binary code visually representing the machine electronic executable binary code without the use of a look up table and a method for reading and producing thereof which overcomes the shortcomings of the prior art devices described above.

SUMMARY OF THE INVENTION Generally speaking in accordance with the invention, an apparatus for executing operations on an electronic binary code, includes a central processing unit for receiving the electronic executable binary code and generating an optically machine readable binary code in response to the received electronic executable binary code. The optically machine readable binary code includes data formed as a matrix, the matrix being formed as a plurality of visual data cells, the data cells printed in the language of the electronic executable binary code. The central processing unit is therefore free of a character look-up table for use in generating the optically machine readable binary code.

The apparatus includes an optical scanner for scanning a machine optically readable binary code. The central processing unit receives an optically machine readable binary code formed in the electronic executable binary code. The machine optically readable binary code is formed as a matrix, the matrix being formed as a plurality of visual data cells which are printed in the language of the electronic executable binary data code. The central processing unit converts the visual binary code to an electronic executable electronic binary code. The central processing unit converts the visual binary representation of said binary code free of a look up table. The apparatus performs a binary search technique to identify the machine optically readable binary code.

One aspect of this invention is to provide an apparatus for producing a symbol which directly encodes the computer electronic binary code as a machine optically readable binary code.

Yet another aspect of this invention is to provide an apparatus for generating and scanning an optically readable binary code in which said code is formed as data cells and a subset of the data cells represent a binary character.

BRIEF DESCRIPTION OF THE DRAWINGS For a fuller understanding of the invention, reference is had to the following description, taken in connection with the accompanying drawings, in which: Figs. la and lb depict two binary codes in accordance with the invention; of different sizes, but containing the same information; Figs. 2a - 2d illustrate the arrangement of data within the perimeter of the binary code in accordance with the invention; Figs. 3a - 3d illustrate the redundant formation of visual cells within the matrix in accordance with the invention; Fig. 4 is a block diagram of an apparatus for generating and scanning the code in accordance with the invention; and Fig. 5 is a flowchart depicting the process for reading the binary code.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Reference is made to Fig. la, wherein a binary code generated by a CPU or the like (see FIG. 4), generally indicated as a matrix 10, constructed in accordance with the invention is presented. Binary code matrix 10 has a perimeter 11 formed by intersecting sides 12 formed of solid lines and intersecting perimeter sides 14 formed of dark perimeter squares 16 and light perimeter squares 18 in an alternating pattern. Data, generally indicated as 19, is stored within perimeter 11 of matrix 10 in binary form by visual cells which may be either relatively dark or light. Therefore each visual cell has a binary value (0, 1 i.e.

light, dark) and a subset of these visual cells form binary data or characters.

Data 19 is stored within the perimeter of matrix 10 by converting each binary character of an internal computer binary code to be stored directly into a visual binary code represented by dark and light squares corresponding to ones and zeros of binary information representing the binary character. Accordingly, a letter or number represented by the binary code 0001 in the internal executable electronic binary language of the CPU may be represented by a string of visual data cells, each cell containing either a dark square or light square. The data representing 0001 internally to the CPU would appear as a series of three light data cells and one dark data cell in the optical code. For example, the numbers 0 through 9 are stored within matrix 10 as a pattern of light cells 20 and dark cells 22.

By way of example a CPU may operate utilizing the US ASCII internal computer language. Binary representation of the one hundred twenty-eight (128) US-ASCII letters, numbers and symbols (used by way of example of alphanumeric data) requires eight binary bits, or in the case of matrix 10, eight visual squares or cells to represent a character since the internal binary language of the computer is directly converted to the visual cells of matrix 10 in a one to one correspondence without the benefit of a look up table.

However, by defining the maximum range of characters that may appear at each position of the input string, it is possible to suppress those binary bits which contain information redundant and common to the entire range of characters thereby compressing the required number of visual squares required to represent a single character to less than eight.

In one embodiment, in which only the letters A through D are anticipated to appear in the first position of an input string to be operated on by a CPU, only two visual squares are required to reflect the four possible binary bit configurations.

Where the presence of a dark cell is indicated by "D" and the light cell is indicated by "L," the letter A would be represented as LD.

The letter B would be represented as DL, the letter C as DD and the letter D as LL; all represented by using only two cells or bits of binary information either electronic or visual. Similarly, if in a second character position of the input string it is known that only numeric values from 0 through 9 will appear, only four visual cells need be reserved to accommodate the ten possible binary variations for forming this character. Accordingly, in the above embodiment, a total of six visual squares or cells need be reserved to reflect the two characters of encoded information rather than the sixteen cells of the US-ASCII system.

The size of the square and the number of cells contained within the perimeter of the square are determined from the code perimeter 11. Solid lines 12 indicate the physical size of matrix 10.

For ease of explanation a square matrix 10 having equal sides 12 is presented. However any parallelogram, such as a rectangle, having an area computable by length and height may be used.

Side 14 indicates the density or number of cells 20, 22 contained within matrix 10. The number of alternating squares 16, 18 beginning with first light square 18 adjacent each perimeter line 12, corresponds to the square root of the number of visual cells 20, 22 contained within the perimeter of matrix 10 rounded up to the nearest number. In this example the square adjacent perimeter line 12 is a light square 18, however, in a matrix having a different number of cells 20, 22 contained therein side 14 may begin with a dark square 16 to obtain an appropriate value for the number of alternating squares 16, 18.

In an exemplary embodiment, the numerals 0 through 9 are internally compressed to thirty six binary holders. The internally compressed electronic binary code is then encoded within matrix 10 utilizing thirty-six visual cells 20, 22 and being encased in a matrix 10 having a perimeter side 14 containing six alternating dark squares 16 and light squares 18. By providing a perimeter which indicates the matrix size as well as the number of visual cells contained within matrix 10 and in binary form, a binary code matrix 10 is provided which, as will be discussed below, is recognizable and identifiable by a scanning computer regardless of physical size or information density.Additionally, by producing a cell in which light visual cells correspond to the internal binary 0 and dark cells correspond to internal binary 1 of an electronic internal binary computer code, the visual matrix 10 is in the internal binary computer code printed in the internal language of the computer, i.e. in US-ASCII, ISO or the like.

By comparison, a matrix 10A depicted in Fig. lb contains the same information in the same format as matrix 10 and has a perimeter lla but at a smaller scale having smaller perimeter sides 12a and 14a. Accordingly, physical size of the code may be unlimited. By providing a format for indicating to the scanning computer the size and density of the matrix in machine readable form, machine readability of a variety of different size and information density binary codes by a single optical scanner computer system is possible. In exemplary embodiments, the physical size may range from one-tenth of an inch square to seven inches square, but is limited only by the ability of the user's print device to create the selected size.

Reference is now also made to Figs. 2a through 2d in which the arrangement of visual cells 22 within matrix 10 is depicted, like elements from Fig. la being assigned like reference numerals. A character may be represented by dark visual cells 22a, 22b, 22c, 22d and 22e. Visual cells 22a through 22e may be situated in a variety of patterns within matrix 10. Visual cells 22 may be in serial order in one corner of matrix 10 (Fig. 2a), visual cells 22 may be scattered about in each corner of matrix 10 (Fig. 2b), visual cells 22 may be in reverse serial order in a corner of matrix 10 (Fig. 2c) or they may be randomly distributed within matrix 10 (Fig. 2d). Each matrix 10 may be keyed to a specific visual cell placement depending upon the needs of each specific user.This enables a user to have patterns which are readable by either all users of a binary code, or only by specific users of the binary code, as for example, in top secret verification facilities. A key 23 for determining which pattern is used, is encoded in visual cells contained within perimeter 11 of matrix 10 at a known reference position within matrix 10. For example, key visual cell 23 may be a certain distance from the intersection of solid lines 12. Additionally, a mixture of both public and secret patterns may be present within the same structure to enable the general public to read part of what is contained within the matrix 10 and only certain sections of the public to read what is contained within the rest of matrix 10. In a preferred embodiment, there are 256 pattern variations for situating visual cells 22, 23 within matrix 10.

Data 19 may also be stored more than once providing the redundancy in the information as encoded within matrix 10. The redundancy may range from a factor of no redundancy to 400% redundancy. Furthermore, as illustrated in Figs. 3a - 3d the redundancy need not be in the same pattern as the root cells.

Visual cells A, B, C, D are positioned within matrix 10 a plurality of times. The root cell, shown by the darker letters, may be replicated in a mirror image (Figs. 3a, 3b, 3c) or in a random pattern (Fig. 3d) as long as identical visual cells such as A, A are not adjacent each other. Accordingly, through redundancy the code is not lost if a portion of the matrix is destroyed or deformed during normal transit or use.

Matrix 10 may be read by the apparatus of Fig. 4. The visual image of matrix 10, along with it's surrounding area, is captured by an optical scanner 24 which converts the visual image into a series of electronic impulses. Scanner 24 may be a light sensitive electronic array, optical CCD camera, linear array scanner, laser reader adapted for two dimensional scanning or the like.

The electronic impulses produced by scanner 24 are transmitted to a digitizer 26 which converts these electronic impulses directly into a series of binary data bits in the electronic executable binary language of the computer corresponding to the scanned image assigning them a value of 0 or 1 depending upon whether the scanned visual cell is light or dark. Each visual cell is assigned a binary numeric value based upon the strength of light sensed by optical scanner 24. Visual cells which are absolute black and absolute white are assigned the highest and lowest values respectively, while shades in between are assigned incremental values forming an electronic image of the scanned matrix 10. Accordingly, the visual image is converted directly into an electronic binary bit stream in a CPU useable language without the use of a look up table or other translation. This image is transmitted to a central processing unit of a computer 28 ("CPU") which stores a bit mapped image of matrix 10 and a part of its surrounding area as a reference within its memory.

Matrix 10 is not always scanned in a readily discernable orientation relative to scanner 24. Accordingly, CPU 28 conducts a binary search to locate the encoded pattern and determine the orientation of matrix 10 as stored in CPU 28. The uniqueness of perimeter 11 of matrix 10 affords a reference point. Each matrix 10 contains two solid dark sides 12. CPU 28 searches for either solid dark side 12 and upon finding it searches for the intersection of the dark sides 12. By locating the corner at which sides 12 intersect, CPU 28 identifies the specific location of matrix 10 regardless of size or orientation within the scanned visual field. CPU 28 then measures the length of each solid black line 12 stored within its memory and the angle at which lines 12 intersect. CPU 28 then calculates where the opposite corner of matrix 10 is located.By utilizing the length and angle of intersection of sides 12, matrix 10 is always recognizable even though it may have been subjected to substantial linear deformation during the digitizing process as long as the binary image remains a parallelogram. Additionally, the uniqueness of perimeter 11 allows CPU 28 to differentiate matrix 10 from other symbols or images within the scan field.

Reference is now made to Fig. 5 in which a flowchart for reading and decoding matrix 10 is provided. Once the four corners of matrix 10 have been identified, CPU 28 counts the alternating dark and light squares 16, 18 of perimeter sides 14 in accordance with a step 100. As sides 14 are of an identical construction, one side 14 is used as a check against the second side 14 to validate the information contained therein in step 102. In step 104, CPU 28 calculates the product of the number of squares contained in each side 14 and determines the density of cells contained within matrix 10. By calculating the angle of the matrix, the matrix size and the matrix density, CPU 28 can calculate the position of each visual cell 20, 22 relative to the intersecting lines 12 in accordance with a step 106. Thus, the center of each visual cell 20, 22 can be determined.CPU 28 now knows the physical size of the pattern to be decoded, the total number of visual cells or their electronic equivalent stored as data 19 and the location of the center of each visual cell 20, 22 in relation to the four corners of matrix 10. Since physical size and cell density of matrix 10 are calculated values rather than predefined, CPU 28 may recognize and decode a matrix 10 of any physical size or density.

The pattern of data 19 is operated upon by first identifying the pattern distribution key in accordance with step 108. The distribution key will always be stored as a number of visual cells located at a specific position relative to the corners of matrix 10. Accordingly, in step 110, once the orientation of matrix 10 is determined by CPU 28, CPU 28 retrieves from its bit mapped image of matrix 10 the electronic binary code equivalent of the visually encoded key cells. Upon decoding of these key cells, as in step 112, CPU 28 is informed which of the 256 cell distribution patterns was employed to encode data 19 within matrix 10.In accordance with step 114 once the distribution pattern is determined, CPU 28 will reunite the appropriate binary data cells to re-form the- binary character strings in the internal binary computer code corresponding to the internal electronic executable binary character strings originally input for encoding. Since each visual cell and its electronic binary equivalent are strung together to form binary characters the CPU 28 may now operate directly on the reformed binary code. It is noted that one of the 256 possible distribution patterns is no distribution at all so that the code is stored directly as binary character strings and no reformation (step 114) is required.

CPU 28 operates on instructions and data stored as an electronic executable binary code such as US-ASCII, ISO or the like. To generate matrix 10, CPU 28 must reverse the process and first convert the 0, 1 internal electronic binary code of the computer language directly to the dark/light visual cells 20, 22 of matrix 10 in a direct one to one correspondence, i.e. without the use of a look up table. CPU 28 calculates the maximum number of character variations expected at each position of the input electronic binary character string and then determines the minimum number of binary data cells required to encode that number of variations. The compression process varies depending on the type of input character anticipated.For instance, if it is known that only numerics will appear at a given input location, the eight bit binary numbers can be compressed to 3.32 visual cells; if all alphabetic characters are anticipated, an eight bit binary letter can be compressed to 4.75 visual cells; or, if the input character could be either alphabetic or numeric the compression algorithms reduce each input character from eight binary bits to 5.21 visual cells.

Further, the system may make use of the available "partial" cells. For example, the first alphanumeric character will require six visual cells (smallest integer 2 5.21) while the second alphanumeric character will require only five (10.42 cells 6 for the first character = 4.42 rounded to 5). This allows for the enhanced binary compression as described above and thereby further reduces the necessary density of matrix 10. If it were known as in Fig. la, that the ten characters to be input were to be all numeric (0 through 9), CPU 28 would determine through use of the compression algorithm that the number of potential binary variations could be accommodated by thirty-four (34) visual cells rather than eighty (80) visual cells as would be otherwise supposed.

The user then inputs into CPU 28 the type of visual cell distribution within matrix 10 desired. The amount of desired redundancy is then input into CPU 28 ranging from no redundancy to as high as 400% repetition of the pattern. CPU 28 analyzes the pattern of the root visual cell to be encoded and positions the redundant data cells farthest from the root cell to achieve the highest probability of survival of at least one cell in the event of destruction of a part of matrix 10 (Figs. 3a, 3b, 3c, 3d). The number of visual cells required for the encoded data is then computed and added to the number of visual cells required as distribution key cells to determine the density of matrix 10. The square root of this total is then determined to establish the number of squares required to form sides 14 of perimeter 11 of matrix 10. Finally, the user desired physical size of matrix 10 is input to determine the length of sides 12 of matrix 10. Upon calculation of all these values, CPU 28 causes a printer 30 to produce the newly generated matrix 10 as a visual binary code. The visual binary code of matrix 10 is the originally input US-ASCII electronic executable binary code data originally operated on by CPU 28 in visual form.

By providing an optically machine readable two dimensional binary code having an identifiable perimeter allowing binary search techniques and the matrix formed in the internal binary computer language, an apparatus which operates without a look up table is provided.

Binary languages are used by way of example. By utilizing different shades of light or dark, or by using colors, machine optically readable code may be printed in a non-binary computer language.

It will thus be seen that the objects set forth above, among those made apparent from the preceding description, are additionally attained and, since certain changes may be made in carrying out the above process and in the construction set forth without departing from the spirit and scope of the invention, it is intended that all matter contained in the above description and shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

It is also to be understood that the following claims are intended to cover all of the generic and specific features of the invention herein described and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween.

Claims (14)

1. An apparatus for executing operations on an internal electronic executable language binary code, comprises means for receiving said internal electronic binary computer language and means for generating an optically machine readable binary code in response to the received electronic executable binary computer language, said optically machine readable binary code comprising data formed as a matrix, said matrix being formed as a plurality of visual data cells, said visual data cells being in the electronic executable binary computer language, said receiving means and generating means being free of a character look-up table.

2. The apparatus of claim 1, wherein a subset of data cells represents a single binary character, said data cells representing more than one set of binary characters.

3. The apparatus of claim 1, wherein a subset of said visual data cells represents a single binary character, and the number of data cells required to visually represent said single binary character is less than eight.

4. The apparatus of claim 1, wherein said electronic executable binary code comprises a bit stream, each bit being of one of two states, each of the visual data cells being in one of two states corresponding to the two states of said bit stream.

5. A method for forming a machine optically readable binary code having data formed as a matrix, said data being formed as visual data cells formed as a data string in an electronic binary computer code, comprising the steps of: receiving said electronic executable binary computer language as a data string of electronic ones and zeros; and directly converting said electronic executable binary computer language from an electronic binary data string of ones and zeros to a binary string of light and dark visual data cells in a matrix which visually represent said string of ones and zeros without reference to a look up table.

6. The method of forming a machine optically readable binary code of claim 5,-wherein a subset of said visual data cells represent a single binary character.

7. The method for forming a machine optically readable binary code of claim 6, further comprising the step of defining a maximum range of binary characters that may appear at each position within said data string and suppressing said ones and zeros which are common to the entire range of binary characters and then calculating the minimum number of data cells required to visually represent a maximum number of binary variations for representing said binary characters.

8. An apparatus for scanning a machine optically readable binary code, comprising means for receiving an optically machine readable binary code, said machine optically readable binary code being formed as a matrix in an electronic executable binary computer language, said matrix bring formed as a plurality of visual data cells, said visual data cells visually representing the electronic executable binary computer language, conversion means for converting said visual data cells into an electronic executable binary computer language, said conversion means converting said visual cells free of a look up table.

9. The apparatus of claim 8, wherein a subset of said visual data cells represent a single binary character, said data cells representing more than one set of binary characters.

10. The apparatus of claim 8, wherein a subset of said visual data cells represent a single binary character, the number of data cells required to visually represent said single binary character being less than eight.

11. A method for determining the location and orientation of a machine optically readable code having an identifiable perimeter comprising the steps of: scanning said code and a surrounding area of said code; converting said scanned image into a digitized image; and conducting a binary search of said digitized image to locate said identifiable perimeter.

12. The method of claim 8, wherein said identifiable perimeter includes at least a first solid line and a second solid line, said first solid line intersecting said second solid line forming a first corner.

13. The method of claim 9, further comprising the steps of measuring the length of said first solid line, measuring the length of said second solid line, measuring the angle at which said first solid line intersects said second solid line, and calculating the position of a second corner of said code on said perimeter opposite said first corner.

14. The method of claim 10, wherein said machine optically readable code is formed as a plurality of visual data cells, and further including the steps of calculating the position of each visual data cell relative to said identifiable perimeter and calculating the position of the center of each visual data cells.