Abstract:
A bar code reading system capable of reconstructing irregularly damaged bar codes includes an input device such as an omnidirectional or CCD scanner, processors for determining whether the bar code symbol has been damaged, and a decoder. The scanner initially scans the bar code to determine the symbology that governs the bar code. Once the symbology has been obtained, an expected length for each symbol can be calculated. The scanner then individually scans each symbol and compares the symbol&#39;s length to its expected length. If the lengths differ by a significant amount, the symbol is assumed to be damaged and information about the elements of each symbol are stored in memory. The scanner then scans in a reverse direction and stores information about the symbol in memory. A processor then determines all of the possible permutations of element widths from the stored information. Each permutation is checked against all possible decoded symbols until a single, decodable symbol is found.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a bar code reading system for reconstructing bar codes that have been damaged by wrinkles, crumples, creases, or by similar types of irregular damage. In particular, a scanner scans bar codes to determine whether symbols in the bar code are damaged. If the symbol is damaged, the reading system reconstructs the damaged symbol by calculating the possible permutations of black bar and white space elements to arrive at a single, decodable symbol. 
     2. Background 
     It is increasingly commonplace within industry to utilize bar code symbols printed on objects in order to identify the objects and convey information regarding the objects. A conventional bar code symbol comprises a pattern of vertical bars of various widths separated by spaces of various widths. The modulated widths of the bar and space elements can be interpreted by an electro-optical imaging system that converts the symbols into an electrical signal, which is then decoded to provide an alphanumeric representation of the bar code symbol. Bar code symbology of this nature are commonly used in various applications, such as inventory control, point of sale identification, or logistical tracking systems. 
     The electro-optical imaging system typically uses light from a light source that is scanned across the bar code field. Since the bar code symbology is often disposed on the object to be identified, it is desirable for the reader to be included in a hand-held or portable device so that the reader can be brought to the object. The operator can physically move the light source across the bar code field, such as by use of a light pen. Alternatively a bar code reader may include movable mirrors that automatically articulate light from a laser back and forth at a high rate to scan across the bar code field. The operator would normally be provided with a feedback signal, such as an audible tone, that alerts the operator as to the successful completion of a bar code reading operation. 
     Alternatively, electro-optical imaging systems can convert the entire bar code symbol into pixel information that is deciphered into the alphanumeric information represented by the symbol. Such imaging systems typically utilize charge-coupled device (CCD) technology to convert the optical information from the bar code symbol into an electrical signal representation of the symbol. CCD-based electro-optical imaging systems are preferable over laser-based imaging systems since the CCD does not require any moving elements, and is further adaptable to image advanced types of symbologies, such as two-dimensional codes, that could not be easily collected by an articulated laser. An image of the bar code symbol is optically transferred to a linear or two-dimensional array of multiple adjacent photodiodes that comprise the CCD device, with each one of the photodiodes defining a distinct picture element (or pixel) of the array. The CCD array is scanned electrically by activating the individual photodiodes in a sequential manner. 
     A successful bar code scan depends upon the clarity of the bar code symbol. A clean symbol can be scanned and decoded with little difficulty. A damaged bar code, however, poses problems for bar code scanners. When a bar code is wrinkled or crumpled, elements within a particular bar code symbol become displaced or hidden altogether. As a result, the bar code scanning operation may require several attempts before a successful scan is made, if a scan is even possible. Certain types of damage may render the bar code symbol completely unreadable by a conventional bar code reader. 
     Bar code symbol damage can be classified into two different types: regular damage and irregular damage. Regular damage can be defined as any kind of damage that merely obstructs the information encoded in the symbol but does not corrupt the flat surface of the bar code label. Examples of regular damage would include dirt, dust or grease that covers the bar code symbol. Regular damage can often be decoded by applying an alignment of partial successive scans. 
     Irregular damage obstructs the encoded information and corrupts the actual bar code label surface. The corruption of the surface can be described as a non-linear transformation of the bar-code surface. Examples of irregular damage are wrinkles, crumples, creases, and the like. 
     Irregular damage to bar codes on items slated for inventory or sale can economically harm a business that relies upon a bar code system. Particularly, damaged bar codes often cannot be read by a conventional bar code reader. The inability of the bar code reader to successfully read the damaged bar code results in the manual input of the information sought to be stored. The likelihood of error increases when significant amounts of encoded information must be input by hand. In addition, repeated manual input of information can lead to serious productivity losses and, consequently, lost profit for businesses that utilize bar code readers. 
     Moreover, more deleterious consequences can occur. For instance, a bar code reader can misread the damaged symbol and, in turn, input incorrect information. That error can be compounded when large quantities of a particular item are sold or inventoried based upon a single misread bar code. Once again, productivity losses occur once the error has been found and the correct information must be input by hand. 
     For the foregoing reasons, there is a need for a bar code reading system capable of reading irregularly damaged bar codes. More particularly, there is a need for a bar code reading system that can reconstruct a bar code symbol that has been damaged by wrinkles, crumples, creases, or the like. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to a device that satisfies the need for a bar code reading system capable of reconstructing symbols in a bar code that have been irregularly damaged by wrinkles, crumples, or creases. 
     In a preferred embodiment, the bar code reading system of the present invention reads bar codes having at least one symbol, each symbol having a combination of black bars and white spaces of varying widths. The reader employs an input device that is capable of scanning or sampling a bar code in at least two directions. During an initial scan, a processor determines the type of symbology by reading the start and stop symbols of the bar code. From the symbology information, the processor can determine the X-dimension for each symbol, an expected length for each symbol, and the number of symbols in the bar code. The scanner then begins scanning or sampling, from a first direction, each symbol in the bar code, beginning with the first symbol. The length of the bar code symbol is compared to the expected length of the symbol. The symbol is acceptable for decoding if the difference between the expected length and the actual length fall within a predetermined toleration value. If the symbol cannot be decoded, a sequence of widths of each element in the symbol is constructed. From there, the bar code is scanned or sampled from the opposite side and on a different scan/sampling line. Each symbol is decoded up to the damaged bar code symbol and a reverse sequence of widths of each element in the damaged symbol is constructed. A set is then provided having all possible combinations of elements from the determined sequences of elements. If only one possible symbol exists in that set, that symbol is decoded. If no symbols or more than one symbol exist in that set, the symbol is re-scanned on a different sampling line. The process of re-scanning is repeated until the intersection of the set contains a single, decodable symbol. 
     A more complete understanding of the bar code reading system will be afforded to those skilled in the art, as well as a realization of additional advantages and objects thereof, by a consideration of the following detailed description of the preferred embodiment. Reference will be made to the appended sheets of drawings which will first be described briefly. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a representation of a bar code damaged by a wrinkle. 
     FIG. 2 is a block diagram of the reading system of the present invention. 
     FIG. 3 is a flow chart diagramming the operation of the present invention. 
     FIG. 4 is a representation of a bar code divided into plural scanning lines. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     FIG. 1 shows an example of a damaged bar code 101 having four symbols representing the characters &#34;C&#34;, &#34;O&#34;, &#34;D&#34;, and &#34;E&#34;, as well as a start symbol and a stop symbol at the beginning and end of the bar code, respectively. A crease 10 traverses the symbol representing the &#34;O&#34; character. Throughout this detailed description, we assume that only the crease 110 exists, although the reading system of the present invention is capable of reading and decoding bar codes having numerous creases and other irregular damage. In addition, the bar code 101 shown in FIG. 1 is meant to be demonstrative only and is not restricted to the rules of any particular symbology. Indeed, in the present invention, a bar code governed by any symbology may be used so long as that symbology can be determined by scanning the bar code or sampling a digitized image of the bar code. 
     It is assumed, however, that the bar code 101 belongs to a particular symbology. In that symbology, any character from the bar code alphabet, ALP, where ALP={alp j  }, is symbolized by a combination of black bars and/or white spaces. Each black bar or white space is termed an &#34;element&#34; and each black bar element and each white space element has a particular width b and w, respectively. If we let S j  be a sequence of widths of black bars and white spaces of a symbol j from the alphabet ALP, then S j  is determined as follows: 
     
         S.sub.j ={b.sub.1.sup.j, w.sub.1.sup.j, b.sub.2.sup.j, w.sub.2.sup.j, . . . , b.sub.n.sup.j, w.sub.n.sup.j }                          (1) 
    
     The sum of black bar and white space element widths C for a symbol j can then be calculated by the following equation: ##EQU1## For every symbol representing a character in the alphabet ALP, C is a constant value. Thus, if the symbology is known, the length of each symbol (i.e., an &#34;expected length&#34;) in the bar code can be calculated. 
     When a prior art device attempts to scan the damaged bar code 101, the scanning line 115 passes horizontally across the bar code 101. The crease 110, however, shifts certain elements in the &#34;O&#34; symbol leftward. In addition, the elements of each character following the &#34;O&#34; character are similarly moved leftward. When the bar code 101 is scanned, the scanner of the prior art device expects each symbol to have the constant width C, where C is determined from Equation (2). Since the bar code is damaged, the width of each bar code symbol, from &#34;O&#34; until the end of the bar code, is seemingly altered. Consequently, the &#34;O&#34; symbol and the remaining &#34;altered&#34; bar code symbols cannot be read or decoded. 
     The elements of a bar code reading system 120 are shown in FIG. 2. The reading system 120 includes an input device 130 such as a scanner or charge-coupled device, a processing unit 150, a display 170, a decoder 140, a user interface 157, permanent memory storage such as a read-only memory (&#34;ROM&#34;) 180, and a temporary memory storage such as a random-access memory (&#34;RAM&#34;) 181. Information or data that must be stored during execution of the instructions (as described below) is stored in addresses contained in RAM 181. Information or data that will be utilized during each scan or sample is permanently stored in ROM 180. 
     If a scanner is utilized as the input device 130, the scanner may be hand-held or fixed. In either case, the input device 130 should be a moving beam device capable of providing omnidirectional scanning. In other words, the scanner 130 can produce a series of straight or curved scanning lines of varying directions in the form of a starburst, a lissajous pattern, or other multiangle arrangement and project those lines at the bar code. For example, the Intermec Janus scanner is suitable for this purpose, although any similar omnidirectional scanner may also be utilized. 
     Alternatively, a CCD scanner may be used as the input device 130. If a CCD scanner is employed, the entire image of the bar code 101 is transferred. A digitized image of the bar code 101 is formed and each line of pixels in the digitized image is sampled as described herein. The terms &#34;sample&#34; and &#34;scan&#34;, however, are used interchangeably throughout this discussion. 
     The display 170 may be a liquid crystal display, LED display, or video display terminal, although other display devices may be used. The display 170 is utilized to provide information to the user of the system. Display information usually includes information encoded in the symbol, results of a scan, and diagnostic and system information. The user interface 157 may be a keypad or other similar input device. 
     The operation of the reading system will now be described. FIG. 3 shows a series of instructions that are executed by the processing unit 150. These instructions are stored in ROM 180. When the bar code 101 is scanned or an image of the bar code is sampled, the scanner 130 initially passes a scanning line (actually a continuous series of scanning spots) across the bar code 101. Alternatively, if a CCD scanner is used, an initial sample of the bar code 101 is taken. In a first step 210, when the scanning or sampling line passes over the bar code 101, a fictional rectangular &#34;boundary box&#34; is created around the bar code. The boundary box has fictional two-dimensional cartesian coordinates in x and y directions with respect to the flat surface of the bar code 101. These coordinates are stored in RAM 181 for later use. 
     Once the boundary box has been created, in step 211, the symbology that governs the bar code 101 is verified. In the reading system of the present invention, a bar code governed by any symbology may be used. Many different types of symbologies are known in the art, such as Universal Product Code (&#34;UPC&#34;), Codabar, and Code 128. The type of symbology can be determined by examining the start and stop symbols contained in the bar code 101. The terms &#34;start symbol&#34; and &#34;stop symbol&#34;, as used herein, refer generally to beginning and end symbols that are typically used by most symbologies. For instance, the start and stop symbols of a UPC bar code are left and right guard patterns. The start and stop symbols in the bar code 101 are then compared with the numerous start/stop symbols of symbologies stored in ROM 180. Once a match has been found, the symbology type, along with information particular to that symbology, is stored in RAM 181. 
     If the symbology type of a bar code is known, many other characteristics of the bar code may later be determined. Thus, in addition to storing the symbology type in RAM 181, the processing unit stores an X-dimension value X, for that symbology in step 212. The X-dimension value is the nominal width dimension of the narrow bars and spaces in a bar code symbol and is constant for each symbology. In addition, for most symbologies, the number of symbol elements in each bar code is fixed. Both the X-dimension and the number of symbols in the bar code are stored in RAM 181. 
     From the X-dimension value, the boundary box coordinates, and the number of symbols in the bar code, the processing unit 150, in step 213, calculates a ratio H defining the number of symbols in the bar code 101, as follows: ##EQU2## where dist is the length of the bar code, as determined from the boundary box coordinates, X is the X-dimension for the verified symbology, and n is the number of elements in each symbol for the verified symbology. The value H is then stored in RAM 181. 
     In step 214, the processing unit 150 next divides the bar code 101 into numerous scanning lines for an omnidirectional scanner or sampling lines for a CCD scanner. For purposes of this description, the number of scanning or sampling lines is equal to k, where k is a predetermined number that depends upon the height of the boundary box. FIG. 4 illustrates how the bar code can be broken down into numerous scanning lines. The processing unit 150 stores the number k in RAM 181 for later use. In step 215, the actual scan line number r (usually 1) is chosen, and a predetermined scan shift q is read from ROM 180 into RAM 181. The scan shift determines the number of scanning lines to which the scanner 130 will shift during a subsequent scan, as determined below. For greater precision, q can be decreased to a lower value. 
     The actual decoding and reconstruction process of the bar code 101 then proceeds by analyzing each individual symbol within the bar code. The symbol to be decoded j is initialized to 1 and the reading system scans the jth symbol from the left, which is the start symbol. The scanner 130 passes a scanning line over the start symbol in a left-to-right direction. Each element of the bar code symbol is stored in RAM 181. In a next step 216, the processing unit 150 calculates a length D of `n` pairs of black bars and white spaces, in accordance with Equation (1), where C, the expected length of the symbol, is replaced by D, the actual length of the symbol. 
     In step 217, the processing unit 150 then computes the absolute value of the difference between D and C. If the absolute value is less than a fixed tolerance value V the decoder attempts to decode the symbol. If the absolute value of the difference between D and C is greater than V, the symbol is assumed to be damaged, and an attempt is made to reconstruct the damaged symbol. 
     The acceptable tolerance V is a fixed value that is pre-coded into ROM 180, although the reader 130 can be designed such that V is determined during a scan by the user via the user interface 157 in step 214. In either event, V should be determined based upon numerous parameters, including the total number of elements in a symbol, the size of the X-dimension in pixels, and the angular distortion of the scanner 130. 
     As stated above, if the absolute value of the difference between D and C is less than the tolerance value V the decoder 140, in step 218, attempts to decode the symbol by applying the decoding function F(S j ), for the jth symbol, where: 
     
         F(S.sub.j).di-elect cons.{alp.sub.j }                      (4) 
    
     if S j  is a legal combination of bars and spaces within the symbology as determined by the symbology verifier. If the decoding is successful, the character represented by the decoded symbol is stored in RAM 180. In step 219, the processing unit 150 then checks to determine whether j, the number for the decoded symbol, is less than H, the total number of symbols in the bar code as determined by Equation (3). If j is less than H, the processing unit 150 increments the value of j and repeats the decoding process by returning to step 216 and calculating the length D for the next symbol. If j equals H, the processing unit 150 assumes that the last symbol has been decoded and terminates the scan in step 220. 
     Assuming that the reading system has decoded all symbols up to a symbol u the reading system may eventually reach a point where the absolute value of the difference between D u  and C is greater than the allowed tolerance value V. The processing unit 150 has calculated the sum D u , as follows: ##EQU3## As with C, D u  includes pairs of black bars and white spaces within the symbol. Because the absolute value exceeds the toleration value, the reading system assumes that the symbol is damaged and begins the process to reconstruct the damaged symbol u. 
     The process of reconstructing the symbol begins when the processing unit 150 constructs the sequence S u , as follows: 
     
         S.sub.u ={b.sub.1.sup.u, w.sub.1.sup.u, b.sub.2.sup.u, w.sub.2.sup.u, . . . , b.sub.n.sup.u, w.sub.n.sup.u }                          (6) 
    
     In step 221, the processing unit 150 attempts to find undamaged elements within the symbol from the sequence S u . For the first x pairs of elements of the symbol u, having the sum D x   u  (as determined by Equation (2)), where D x   u  &lt;C, the processing unit 150 assumes that those first x pairs of elements are undamaged. Accordingly, the microprocessor stores the first x pairs in RAM 181. 
     Having identified the symbol u as damaged, the scanner 130 is instructed, in step 222, to scan from the right side of the bar code. Scanning line 115 begins with the right-most symbol and scans across the bar code to the left. In addition, scanning takes place on a lower scanning line having a number (1+q), where q is the predetermined scan shift. 
     On the 1+q th  scanning line, the scanner 130 attempts to decode all symbols from the right side of the bar code until it reaches symbol number H-u (counting from the right side of the bar code), where H is the number of symbols in the entire bar code as determined from Equation (3). As before, the absolute value of the difference between D (for each symbol) and C is compared to the tolerance value. 
     Once the H-u th  symbol is reached, the processing unit 150 creates a reverse sequence of elements from the right side of the symbol in step 223, as follows: 
     
         S.sub.H-u ={b.sub.1.sup.H-u, w.sub.1.sup.H-u, b.sub.2.sup.H-u, w.sub.2.sup.H-u, . . . , b.sub.n.sup.H-u, b.sub.n.sup.H-u }(7) 
    
     This sequence is constructed in accordance with the previous assumption that non-damaged elements exist on the right side of the bar code symbol. 
     After constructing the sequence, S j , the processing unit 150 constructs the set SC j , in step 224, where: 
     
         SC.sub.j ={sc.sub.i }, j=1, . . . , P                      (8) 
    
     The set SC j  consists of all possible combinations of elements from sequences obtained from Equations (6) and (7). The set includes the first y pairs of elements from Equation 6 and the last n-y pairs of elements from Equation 7, where y≦x, and ##EQU4## The value ae is an acceptance error that indicates how close the sums calculated in Equation (9) should be to our constant width value, C, for each symbol. As with the tolerance value, V, the value ae can be placed into ROM 180 during construction of the reader or can be determined at run-time by the user via the user interface 157. 
     Next, in step 225, the processing unit 150 constructs the set DSC 1 , containing all of the possible decodable combinations from the set SC 1 . DSC 1  is constructed based upon the following equation: 
     
         DSC.sub.1 ={sc.sub.1 : F(sc.sub.i).di-elect cons.ALP}      (10) 
    
     This set includes all of the decodable combinations from the set SC 1 . Thus, all undamaged elements from different sampling lines are fused to reconstruct the damaged symbol. 
     In step 226, the processing unit calculates the number of elements in the set DSC 1 . If the set DSC 1  is the null set or if the set includes more than one element, the processing unit 150 assumes that the symbol u is undecodable based upon sampling lines 1 and 1+q. The process is then repeated by returning to step 216 and scanning the symbol from the left side and right sides for sampling lines r and r+q. 
     If the set DSC 1  has no elements, the processing unit 150 executes step 230. In step 230, a new sampling line r and shift q is chosen, j is initialized to zero, and the unit returns to step 216. 
     If the set DSC 1  includes more than one element, the processing unit 150 executes step 227 and attempts to find the intersection of DSj for various sampling lines. Thus, in step 228, the processing unit 150 calculates a number K equal to the number of intersection elements in the set. In step 229, the processing unit either terminates the scan if K=1 or goes to step 216 if K is greater than 1. 
     Having thus described a preferred embodiment of a reading system, it should be apparent to those skilled in the art that certain advantages of the within system have been achieved. It should also be appreciated that various modifications, adaptations, and alternative embodiments thereof may be made within the scope and spirit of the present invention. For example, a microprocessor has been illustrated, but it should be apparent that the inventive concepts described above would be equally applicable to a host computer, digital signal processor (&#34;DSP&#34;), application-specific integrated circuit (&#34;ASIC&#34;), or discrete logic circuits. The invention is further defined by the following claims.