Method and Apparatus for Dynamically Segmenting a Bar Code

This invention relates to a system for optically scanning a bar code and processing the data obtained to more accurately identify the symbols comprising the bar code. More specifically, it relates to a method and apparatus for segmenting the bar code into individual bars for recognition by determining the most likely actual separation of bars located nominally at a fixed pitch.

Various apparatus and methods for optically recognizing characters, including bar codes, have existed for many years. This invention concerns recognition of a bar code comprising a two-dimensional set of vertical bars of predetermined lengths that are nominally spaced at predetermined horizontal intervals. The space occupied by one bar plus the space between the adjacent bar is referred to as the bar pitch, and it is typically fixed. An example of such a bar code is disclosed in U.S. Pat. No. 4,408,121, which is incorporated herein by reference.

The bar code is "read" or deciphered by an optical scanner which converts the optical information, i.e. picture elements or Pels, into electrical data pulses that may be processed by a computer or the like. Since the two dimension bar code is particularly useful in marking bank checks, it is desirable to be able to read the code at high speed using typical bank check data processing equipment. However, the accuracy of high speed reading may be compromised due to irregularities in either the bar code itself or the equipment used to scan the bar code or both. For example, bar code errors may include irregular horizontal spacing between vertical bars, top to bottom skew, tilt, partial obliteration of one or more bars, and other stray marks in the vicinity of the bar.

The equipment used to decipher the bar code typically transports the document bearing the code, such as a bank check, through a field monitored by a scanner that discriminates between the individual bars and a contrasting background to generate scan lines of elements of image data representing either a bar image Pel or a space image Pel. The document usually passes through the scanner field at a high rate of speed that is coordinated to the rate at which the scanner generates the lines of image data and to the fixed bar pitch or the width of the spaces between the individual adjacent bars. Problems arise when documents move through the scanner field at different velocities, with a skewed orientation, or at a nonconstant velocity. This causes the bar code to be out of alignment with the scanner field, and the scanner may sense a nonconstant pitch, inducing errors.

This invention provides a method and apparatus for reading a two-dimensional bar code and dynamically segmenting it into individual bars on a real time basis as it is read. The segmentation is done on a bar-to-bar basis, and may be adjusted for an individual bar as necessary. Thus, it functions over a wide range of bar widths and bar spacings, provided the bars are printed at a nominally fixed pitch, and it accomodates variations within a single bar code, variations from one bar code to another bar code, and variations in different bar reading equipment without degrading accuracy.

The method and apparatus locate the bar data, including any starting symbol, and isolate it from the space or background data. This is accomplished by scanning the bar code and creating a profile vector or data word having elements based upon the amount of image data, i.e. the number of bar image pels, as opposed to space or background image pels, in each scan. The created vector is then compared with a stored set of vector models representing various bar image data location possibilities. The model matching the created vector defines how the scan image data is to be processed so that only those selected scan lines of image data corresponding to the best available bar image scan data are sent to the recognition logic. Those scan lines of image data corresponding to a space image scan or a mispositioned bar scan or noise are disregarded and do not go to the recognition logic. This is done on a bar-to-bar basis and compensates for the problems noted earlier. The method and apparatus may also be employed to locate and normalize a start position represented by a special field mark in the code, i.e. an oversized starting symbol, as well as to find individual bars for recognition.

Thus, it is an object of the present invention to provide a method and apparatus for accurately reading a two-dimensional bar code having bars located nominally at fixed pitch intervals, including any starting symbols.

It is a further object of the present invention to eliminate errors in deciphering a two-dimensional bar code that arise from variations in bar pitch or a mispositioned bar scan or noise.

It is a still further object of the present invention to select the image data most accurately representing the bar code and to disregard other image data and space scan data.

It is a still further object of the present invention to provide a method and apparatus to dynamically segment a bar code on a real time basis as the bar code is scanned at high speed.

The method and apparatus of this invention is a system for reading a two-dimensional bar code having bars located nominally at predetermined pitch increments. The bar code is scanned at predetermined increments to produce lines of elements of image data or pels. Each data element is either a first or second state to reflect either a bar image or a space image. From the scan lines of image data, a profile vector is generated having individual data elements (binary scan signals) which represent the likelihood that a respective scan line of image data contains bar image data or space image data. A selected number of scan lines containing bar image data are transferred to the recognition means, and those not meeting the predetermined criteria, i.e., those likely representing a space image or bar image errors, are disregarded and not sent to the recognition means.

The selection of scan lines of image data to be transferred to the recognition means is preferably accomplished by the use of a look-up table accessed by the profile vector. The look-up table includes stored sets of vector models which define which of the scan lines of image data comprising the presented vector contain the most reliable bar image data. After selected scan lines of image data have been transferred to the recognition means, a succeeding vector is constructed from the succeeding binary scan signals and the process is repeated as often as required until the end of the bar code is reached.

FIG. 1 is a schematic block diagram illustrating a system for reading a two-dimensional bar code according to the present invention.

FIG. 2 is an enlarged illustration of a representative two-dimensional bar code.

FIG. 3 illustrates typical scan lines of elements of image data produced by scanning the two-dimensional bar code of FIG. 2.

FIG. 4 illustrates the scan counts corresponding to the scan lines of image data of FIG. 3.

FIG. 5 illustrates the binary scan signals comprising the profile vectors corresponding to the scan counts of FIG. 4.

FIG. 6 illustrates those scan lines of image data from FIG. 3 transferred to recognition means and those scan lines disregarded or skipped.

FIG. 7 is a schematic block diagram illustrating a logic system for implementation of the present invention.

Referring to FIGS. 1 and 2, a record or document 1, such as a bank check, includes a two-dimensional bar code 2 at a predetermined location, such as the lower left corner. An optical scanner 3, as is well known in the art, scans that portion of the document intended to display the bar code with optically sensitive apparatus 4 that can distinguish between a bar and a space, or background. In the present invention, the code is vertically scanned to detect image data of either a first or a second state to provide a digitized data stream reflecting either a bar image scan or a space image scan.

The digital data generated by the scanner is provided to the profile generation and transfer means 5 and forms the basis for the generation of a profile vector element representing the likelihood that a scan line of image data contains bar image data. Those scan lines meeting predetermined criteria are deemed most representative of a bar image scan and are transferred to the recognition means 6, and those scan lines not meeting the predetermined criteria are deemed less likely to represent a bar image scan and are disregarded or skipped 7 as representing a space image scan, even though they may contain a significant number of bits of bar image data.

FIG. 2 illustrates an enlargement of a typical two-dimensional bar code comprising a number of bars located nominally at predetermined pitch increments. Each bar has a predetermined length, position and orientation representative of the information to be conveyed. The bars are localized in a predetermined zone 10 that corresponds to the field read by the scanner 3, 4. The bars are printed to contrast with the background 11 so that the scanner may discriminate between them. The bars 13-19 are printed at a nominally fixed pitch, meaning that the distance 12 of a bar width and the adjacent bar-to-bar space is nominally fixed.

A starting symbol 13, which is longer than the other symbols, is typically provided at the edge of the bar code that first enters the field of the scanner. Such a starting symbol identifies the first element of a bar code, assists in defining the boundaries of the zone that contains the bar code, initiates the collection of data representing the profile of the bar image data, and assists in normalizing the shape, size and location of the bars comprising the bar code.

Errors in printing the bar code may include irregular horizontal spacing between vertical bars, top to bottom skew, tilt, partial obliteration of one or more of the bars, and stray marks in the vicinity of the bar. These errors are illustrated by way of example in FIG. 2. By comparison, perfectly formed bars would be illustrated as regularly spaced and parallel rectangles with straight sides and right angle corners. An example of a bar code suitable for use with the present invention is disclosed in U.S. Pat. No. 4,408,121.

Referring to FIG. 3, scan lines numbered 0001 through 0046 correspond to the elements of image data generated by scanning the bar code of FIG. 2. These scan lines are typical of the information that would be provided to the profile generation and transfer means 5. Those areas for which the scanner detected a bar image are represented by the presence of a digit 0 through 7, and those areas representing a space image are blank. The scan lines are generated as the bar code passes through the scanner field.

Referring to FIG. 4, for each scan line of image data generated by the scanner, a count is accumulated reflecting the number of bits of bar image data, i.e. picture elements representing bar data or bar pels, as represented by one of the digits 0 through 7. For instance, reading vertically downward from FIG. 3 to FIG. 4, for scan line number 0001, 12 bar image pels were detected, and for scan number 0002, 25 bar image pels were detected. The scan counts are generated as the scan lines are presented to the counter means.

The count of the number of bar image pels for each scan line is provided to decision logic to determine the likelihood that the associated scan line of image data represents a bar image scan or a space image scan. (Reference to a space image scan includes an image scan containing insufficient bar image data to reliably be deemed to represent bar image data.) According to predeterminable criteria, a binary scan signal, i.e. a 1 or a 0, is assigned and these signals are sequentially stored in a register in a location which corresponds to its respective scan line of image data. The register thus represents a profile of the bar image data from the scans. For instance, referring to FIG. 5 and reading vertically downward from FIGS. 3 and 4, scan line number 0003 is assigned a 1 because its count of 31 bar image pels represents a bar image scan, and scan line number 0016 is assigned a 0 because its count of 2 bar image pels represents a space image scan. A more detailed description of the decision logic for generation of the profile is provided in connection with FIG. 7.

Using the profile, a profile vector comprising the eleven sequential binary scan signals for one bar pitch (i.e., one nominal bar width plus one nominal bar space) plus one additional bar width is designated. Based upon the nominally known pitch, this comprises the adjacent binary scan signals for four bar image scans plus three space image scans plus four bar image scans, for a total of eleven scans, and this is designated profile vector A in FIG. 5.

The designated profile vector is compared to a programmable logic array having predetermined criteria, as may be contained in a look-up table. According to the present invention, the first four scan lines of image data corresponding to the first four binary scan signals of the profile vector element are assumed to represent bar image data, and the programmable logic array will provide an output indicating how many of the succeeding scan lines following the first four are disregarded or skipped to get to the next scan lines likely to represent bar image data. For instance, for profile vector A the first four scan lines are designated as representing image data, and the next four scan lines are disregarded to get to the following scan lines of data most likely to represent the following bar image scan, namely the last three binary scan signals of profile vector A.

Those scan lines of image data meeting the predetermined criteria are deemed representative of a bar image scan and are presented to the recognition means. Those scan lines of image data not meeting the predetermined criteria are deemed representative of a space image scan and are disregarded. In the present example, scan lines 0002-0005 are presented to the recognition logic and scan lines 0006-0009 are disregarded. Scan line 0001 is disregarded as the initial scan line of image data as a part of the start bar or first bar normalization process. This may be done in any manner well known in the art, and is typically tailored to the characteristics of each start bar for each bar code.

After the scan lines of elements of image data and space data have been transferred or skipped, a second eleven element profile vector is constructed to the original complement of one bar pitch plus one additional bar width, with the retained elements from the preceding profile vector element comprising the initial elements of the succeeding profile vector, as profile vector B illustrates in FIG. 5. Specifically, scan lines 0002-0005 were deemed representative of a bar image scan and were transferred to recognition means, scan lines 0006-0009 were deemed representative of a space image scan and were disregarded, and scan lines 0010-0012 were retained to complete the profile vector complement of one bar pitch plus one additional bar width. Profile vector B therefore begins with scan line 0010 and extends through and including scan line 0020.

Profile vector B is presented to the programmed logic array as described earlier. The first four scan lines 0010-0013 are automatically designated representative of bar image data and are transferred to the recognition means, and scan lines 0014-0016 are disregarded as being representative of a space image scan. Scan lines 0017-0020 are retained for construction of profile vector element C. Successive profile vectors C, D, E, F, etc. are constructed and compared to the predetermined criteria as required until the end of the bar code has been reached. If the profile vector element does not meet any of the predetermined criteria, the decision on the number of lines of image data to be disregarded defaults to the nominal bar pitch, which in the present example is three lines.

The following table identifies those scan lines to be disregarded or skipped for each profile vector presented to the programmed logic array:

To initiate the generation of a profile of the scan image date, as illustrated in FIG. 5, the starting symbol is recognized and normalized. It is recognized by first recognizing a scan that is likely to include image data rather than noise or background data, and then determining whether the image data represents a bar image or a starting symbol. Specifically, the preferred embodiment looks first for an enabling scan containing at least 14 bar image pels, followed by at least one of the three succeeding scans having at least 24 bar image pels. Having confirmed the presence of a start bar, its width is determined and the collection of the binary scan signals to generate the profile of the image data is initiated. The start bar width is defined by incrementing a start bar counter by one step for the enabling scan and one step for each of the succeeding scans having at least 20 bar image pels. The collection of binary scan signals to form the profile of the image data begins with the enabling scan for the start bar.

The number of steps in the start bar counter is used to select which binary scan signal shall be used to initiate the first profile vector. Specifically, one binary scan signal is bypassed for every other step counted beyond four. If the start bar counter has five or six counts, one line of image data is skipped and the profile begins with scan number 0002. If the count is seven or eight, two lines of image data are skipped and the profile begins with scan number 0003. ln the illustrated embodiment, the enabling scan is scan number 0002, because it is the first scan line having at least 14 bar image pels, and scan numbers 0003-0005 are the succeeding scan lines having at least 20 bar image pels. Thus, the start bar comprises scan lines 0002-0005, with scan number 0001 being skipped, and the first profile vector begins with scan number 0002.

Referring to FIG. 7, the digitized data stream of scan lines of elements of image data from the scanner 20 is provided in timed sequence to the bit counter 21 to count the number of bar image pels detected in the scan line presented. This information represents the scan counts identified in FIG. 4. The scan count is provided to two fixed value comparators 22, 23 and register 30. The first comparator 22 determines whether the scan count exceeds a predetermined value X, as might happen for a start bar, and if so, its output signal represents that a scan line contains sufficient bar image pels to be designated as a bar image scan. Similarly, the second comparator 23 determines whether the scan count is less than a predetermined value Y, which identifies the scan line as having insufficient bar image pels to constitute a bar image scan, and it is designated as a space image scan, even though it may contain several bar image elements. The values X and Y may be set as necessary or desirable to, for instance, automatically identify a start symbol or eliminate noise.

The output of comparator 22 is provided to selector 24 and exclusive OR gate 25. Selector 24 presents the appropriate scan signal logic 1 to selector 26 and the output of the exclusive OR gate 25 causes selector 26 to gate the logic 1 signal through to represent the binary scan signal 1 on line 27 for the associated scan line.

The output of comparator 23 is provided to exclusive OR gate 25. In the absence of an output from comparator 22, selector 24 provides a logic 0 which is gated through the selector 26 to appear as a logic 0 on line 27, representing a space image scan.

The output from bit counter 21 is also provided to the previous value register 30. If neither of the criteria for the two comparators 22, 23 are satisfied, the binary scan signal for the scan line under consideration is provided by comparing the present scan count to the scan count for an adjacent scan line. Specifically, the scan count from the previous scan line is stored in previous value means register 30, and a constant Z is subtracted from this previous scan count in substractor 31 to provide an adjusted scan count on line 32. The adjusted count is compared to the current scan count provided via line 33 to comparator 34. The output of comparator 34 is a logic 1 if the current scan count is equal to or greater than the adjusted previous scan count, and it is a logic 0 otherwise. This scan signal is provided to selector 26 and is gated through to line 27 in the absence of a signal from exclusive OR gate 25. Each of the scan counts are sequentially processed in this manner and may be provided to a serial to parallel shift register 28 to form the various profile vectors A-F as illustrated in FIG. 5.

The profile vectors, as completed, are fed in parallel to the programmed logic 30. Those scan lines meeting predetermined criteria representative of a bar image scan are presented to the recognition logic and those scan lines not meeting the predetermined criteria are disregarded. This is accomplished as described earlier by providing the scan lines of image data representing the first portion of the profile vector to the recognition logic, disregarding those scan lines of image data from the middle portion of the profile vector, and utilizing the scan lines of data from the last portion of the profile vector to construct the initial portion of the following profile vector.

The present invention may be implemented in real time on a bar-to-bar basis which adjusts for gradual changes in the bar code as the document is scanned. Advantages include the ability to update the bar code segmentation on an individual bar-to-bar basis as required, the ability to function over a wide range of bar widths and lengths, the ability to accommodate automatic scanning equipment where the document transport speeds vary from machine to machine, the ability to recognize a starting symbol and the ability to easily modify the decoding information utilized in the look-up tables, programmed logic, or automatic bar and space comparators.

Those skilled in the art will recognize that various modifications, additions and deletions can be made to the particular embodiment shown having had the benefit of the present teachings without departing from the scope of the invention.