Bad Read Recovery: The Art of Second Chances in Barcode Decoding |
Executive Summary |
This article provides a comprehensive exploration of bad read recovery and retry logic in barcode reading systems. We examine how modern decoders handle scans that fail on the first attempt by adapting parameters, combining data from multiple scans, and using iterative correction algorithms to salvage information from damaged or poorly printed symbols. Rather than focusing on abstract theory, we ground every concept in concrete design examples and real patent disclosures from industry leaders including Symbol Technologies, Microscan Systems, and Datalogic. We explore the fundamental types of scanning errors, the use of multiple scan data to identify and correct erroneous characters, the iterative correction process between two distorted images, and the practical implementation of symbol reconstruction in commercial products. The article covers both the theoretical underpinnings and the practical implementation details that make bad read recovery an essential part of reliable barcode reading systems. The closing summary synthesizes the key lessons and offers practical guidance for anyone designing or selecting retry logic for barcode reading applications. |
|
Chapter 1: The Challenge of the Failed Read |
In an ideal world, every barcode scan would be perfect. The laser would sweep cleanly across the symbol, the photodetector would capture pristine reflections, and the digitizer would produce a flawless pulse train. The decoder would then compare this pulse train to its reference patterns and produce the correct data on the first attempt. |
But the world is far from ideal. Barcodes are printed on low-resolution dot-matrix printers, smudged by fingers, torn by handling, and partially obscured by labels or creases. The scanner may be tilted, the barcode may be damaged, or the ambient light may create reflections that confuse the photodetector. In these cases, the decoder may be unable to decode the barcode from a single scan. |
A patent from Symbol Technologies explains the challenge: 'Difficulties associated with the inability to read a bar code symbol or the erroneous reading of a bar code symbol are especially common in applications involving relatively long bar code messages, i.e., bar code symbols having numerous elements. As the length of the message increases, the number of elements and characters increases, thereby raising the likelihood that distortion will be introduced at some point during the scan'. |
The solution is bad read recovery---a set of techniques that allow the reader to salvage information from failed scans. These techniques range from simple retries with adjusted parameters to sophisticated algorithms that combine data from multiple scans to reconstruct a readable symbol. The goal is to convert a failed read into a successful one without requiring human intervention. |
|
Chapter 2: Understanding the Types of Decoding Errors |
Before we can recover from a bad read, we must understand the types of errors that can occur. The Symbol Technologies patent identifies four primary types of distortion that can prevent accurate decoding: |
Split or Divide Error: A single element is erroneously detected as multiple elements. For example, a wide bar may be misinterpreted as a pair of narrow bars surrounding a narrow space. This typically occurs when a printing defect or electrical noise creates a false transition within a single element. |
Merge Error: Multiple elements are erroneously detected as a single element. For example, a narrow bar, a narrow space, and another narrow bar may be misinterpreted as one wide bar. This occurs when a transition is missed due to noise or poor contrast. |
Single Element Misread or Edge Shift: The width of a given element is misrepresented without altering the total number of elements. A wide element may be misread as a narrow element, or vice versa. This changes the character value without changing the element count. |
Dual Element Misread: Two adjacent elements are misread, with one element's width being swapped with the other. This is less common but can occur when the edge between two elements is ambiguous. |
These errors are not random---they are often correlated with the specific characteristics of the damaged portion of the barcode. This correlation is the key to recovery: if one scan fails due to a defect in one location, another scan may fail in a different location, and by combining the two, the decoder can reconstruct the complete symbol. |
|
Chapter 3: The Concept of Illegitimate Characters |
A fundamental concept in bad read recovery is the distinction between legitimate and illegitimate characters. A legitimate character is one that is recognized by the barcode symbology being used. An illegitimate character is any pattern of elements that does not correspond to a valid character in that symbology. |
When a decoder encounters an illegitimate character, it has encountered an error. In traditional decoders, this would cause the entire scan to be discarded. The Symbol Technologies patent explains: 'Upon registering a decode failure, conventional bar code readers discard the entire distorted raw digital image and repeat the entire process... until a scan is produced which is sufficiently free from distortion such that the decoder can match legitimate character image(s) with the raw digital image'. |
The innovation of bad read recovery is to treat these illegitimate characters as valuable information rather than garbage. By analyzing the positions and characteristics of the illegitimate characters across multiple scans, the decoder can identify which portions of the symbol are reliable and which need correction. |
|
Chapter 4: Reading a Bar Code from Multiple Scans |
The key insight behind multi-scan decoding is that while each scan may be partially corrupted, the corrupted portions are unlikely to be the same in every scan. By combining information from multiple scans, the decoder can assemble a complete, correct representation of the barcode. |
The Symbol Technologies patent describes a method where representations from a plurality of scans are stored. One representation is then corrected, or improved, using another representation. An attempt is made to decode the corrected representation to produce a legitimate character. If the decoding attempt is not successful, further corrections are made in order to provide a representation which may be decoded. |
The process works as follows: After each scan, the decoder stores the decoded characters and the raw digital image. If a decode failure occurs, the decoder does not discard the partial data. Instead, it saves the partially decoded message and the raw distorted digital image. When a second scan provides another partial decode, the decoder compares the two partial decodes to identify which characters are consistent across both scans. |
If a character is decoded identically in both scans, it is considered reliable. If the same character position is decoded differently, it is marked as uncertain. The decoder then attempts to correct the uncertain characters using information from the reliable characters in the other scan. |
|
Chapter 5: The Iterative Correction Process |
The multi-scan decoding method is iterative---the correction is applied repeatedly, toggling between the two scans, until the entire symbol is decoded or it becomes clear that further correction is impossible. |
The Symbol Technologies patent describes this iterative process in detail: 'The decoder continues to toggle back and forth correcting each scan using information from the other scan until the entire symbol is decoded or a non-correctable failure occurs'. |
The process starts with two partial scans, each of which has decoded a different portion of the symbol. The decoder identifies the scan with the longer decoded sequence and classifies it as 'relatively clear' and the other as 'relatively distorted.' It then attempts to correct the defective character element(s) of the relatively distorted scan based on the digital image of the relatively clear scan. |
If the element correction succeeds, the decoder then corrects the message containing the corrected elements and continues decoding the next characters. If another decode failure occurs, the decoder performs a toggling process and replaces the originally received scan data with its corresponding corrected scan data, treating the corrected scan data as any other unsuccessful scan data. |
This iterative process continues until the entire symbol is decoded or a non-correctable failure is detected. The patent notes that three instances of non-correctable failure can occur: if a character is reached which cannot be decoded from either raw digital image, one of the scans must be discarded and a new scan sought. |
|
Chapter 6: The Datalogic Error Identification Method |
Datalogic developed an alternative approach to handling decoding errors that focuses on identifying the type of error and adjusting the synchronization mechanism. This method, described in a patent, checks whether the width of a character being examined is smaller or greater than the estimated width. |
If the character width is smaller than the estimated width, this indicates that split-type errors have taken place---elements with widths smaller than the original ones have been introduced. If the character width is greater than the estimated width, this indicates merge-type errors. |
Once the type of error has been recognized, the process tries to pass over the error-containing zone. If the error is of the split-type, the two following elements are acquired and their relative width is added to the character being examined. If the error is of the merge-type, the width of the two last elements is subtracted from the character being examined. |
This approach allows the decoder to re-synchronize at the beginning of a new decodable character, effectively skipping over the damaged portion of the symbol. The patent notes that if the re-synchronization fails after a given number of tries, the acquired data is stored and the analysis of the same scanning but read in the opposite direction is attempted, obtaining a new string of partly decoded data. |
|
Chapter 7: Combining Data from Opposite Directions |
A particularly powerful technique in bad read recovery is to scan the same barcode in both directions and combine the data from both scans. Because the scan direction determines which elements are read first, errors that affect the beginning of the symbol in one direction may affect the end of the symbol in the other direction. |
The Datalogic patent describes combining strings obtained from code scanning in one direction and the opposite direction as 'two different strings.' The combination algorithm follows specific rules: if a decoded character and an unknown character are found in the same position, the value of the decoded character is stored. If two decoded characters are found with different associated error coefficients, the character with the lower error value is stored. |
This approach leverages the fact that different scanning angles can make different portions of the barcode readable. By combining data from multiple scanning lines and directions, the decoder can reconstruct a complete symbol even when no single scan captures the entire symbol clearly. |
|
Chapter 8: Symbol Reconstruction in Commercial Products |
Microscan Systems has commercialized the concept of bad read recovery under the name 'Symbol Reconstruction.' This technology allows scanners to rebuild data from damaged or poorly positioned symbols by 'stepping through' the elements in multiple stages and combining the successfully decoded regions into completed symbol data output. |
The technology addresses several common challenges in industrial environments: damaged symbols, partially covered symbols, poorly printed symbols, and variation of label placement. Labels containing linear symbols can be torn, partially obscured, overprinted, or underprinted due to variations in print mechanisms. |
The Symbol Reconstruction methodology uses an algorithm that pieces together discontinuous symbol data from multiple scan lines. The illustration in the white paper shows scan lines intersecting symbol elements at an angle, demonstrating how the algorithm reconstructs data from tilted symbols. Reconstruction of damaged symbols is achieved similarly---by combining multiple small, undamaged and decodable 'chunks' of symbol data into a single, continuous data string. |
The technology is particularly effective for rotated symbols. In some packaging applications, operators may have little or no control over label placement, leading to unexpected symbol orientations. Symbol reconstruction allows the scanner to decode tilted symbols that would otherwise result in No Reads. |
|
Chapter 9: Configurable Reconstruction Parameters |
Microscan's Symbol Reconstruction technology includes configurable parameters that allow the user to control the trade-off between decoding success and processing time. These parameters include Redundancy (Low, Medium, or High) and Effort (Minimum, Medium, or Maximum). |
The purpose of the Redundancy check is to ensure that the symbol has been decoded correctly. If the application is using high quality symbols, the Low setting provides satisfactory redundancy checking. A higher level of redundancy ensures greater data integrity but may also require a higher level of effort to decode. |
The Effort parameter determines the amount of time the system will spend identifying candidate symbols and the amount of processing applied in reconstructing and decoding those symbols. A higher effort level may slow decode performance as the scanner runs through all options for reconstructing and decoding the symbol. |
These parameters allow system integrators to optimize the scanner for their specific application requirements---prioritizing speed for high-throughput applications or prioritizing reliability for applications where every barcode must be read correctly. |
|
Chapter 10: The Boundary Box and Symbol Identification |
A patent from a barcode reader manufacturer describes a method for reconstructing damaged barcodes that begins by creating a fictional rectangular 'boundary box' around the barcode. The boundary box has fictional two-dimensional Cartesian coordinates that are stored for later use. |
Once the boundary box has been created, the symbology that governs the barcode is verified. The type of symbology is determined by examining the start and stop symbols contained in the barcode. The start and stop symbols are compared with numerous start/stop symbols of symbologies stored in memory, and once a match is found, the symbology type and its characteristics are stored. |
From the X-dimension value (the nominal width of the narrow bars and spaces), the boundary box coordinates, and the number of symbols in the barcode, the processing unit calculates a ratio defining the number of symbols in the barcode. The barcode is then divided into numerous scanning lines or sampling lines. |
This structured approach provides the decoder with a framework within which to operate. The boundary box defines the extent of the symbol, the symbology defines the rules, and the scan lines define the data to be analyzed. |
|
Chapter 11: Reconstructing Damaged Symbols |
The reconstruction process for damaged symbols begins by analyzing each individual symbol within the barcode. The decoder calculates the length of the symbol (the sum of black bar and white space element widths) and compares it to the expected length for a symbol in that symbology. |
If the difference between the actual length and the expected length is less than a fixed tolerance value, the decoder attempts to decode the symbol using the decoding function. If the decoding is successful, the character represented by the decoded symbol is stored. |
If the absolute value of the difference between the actual length and the expected length is greater than the tolerance value, the symbol is assumed to be damaged, and an attempt is made to reconstruct the damaged symbol. The reconstruction process involves analyzing multiple scanning lines and combining information from the portions of the symbol that are decodable. |
The patent notes that the acceptable tolerance should be determined based on 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. |
|
Chapter 12: The Stitching Algorithm |
The stitching algorithm is a key component of the symbol reconstruction process. It combines data from multiple scans to form a complete representation of the barcode symbol. |
The Datalogic patent describes a stitching algorithm that combines strings from two scans. The current string (from the first scan) is stored in a buffer and subject to a set of heuristic check rules to reject poorly reliable characters. The partial data are then stored in a buffer intended for containing, position by position, the characters acquired from preceding scans and the error coefficients associated with them. |
When a character that had previously appeared in the same position has to be stored, the updating of the error coefficients is performed by calculating an arithmetical mean between the error coefficient associated with the just classified character and the error coefficient associated with the same character in the same position, updated as at the preceding scanning. |
By initializing the updated error coefficients with the maximum value, an error value is obtained that keeps track, not only of the reliability of the classified characters, but also of the frequency with which the character has been decoded in the same position. The greater the frequency, the more reliable the character. |
|
Chapter 13: Consolidated Data and Validation |
The stitching algorithm maintains a buffer of consolidated data that is updated as new scans are processed. The consolidated data is filled, scanning after scanning, with reliable data, privileging those that have appeared most recently in each position. |
This criterion is justified by two observations. First, if the validation try of data has already been made with a negative result, it is useful to replace the data with the latest novelties before trying again the validation. Second, in case of non-decoding of a label, if the code reading device is of a manual type, the user is led to shift instinctively the reader along the width of the code in the less altered zones of the label. |
When the consolidated buffer contains a complete string of characters that are all decoded, a validation try is performed. If this gives a positive result, the decoding process has succeeded. In the contrary case, a second validation try is performed using a third string of decoded characters, choosing for each position the datum that has been decoded in preceding scans and to which the lowest updated error coefficient is associated. |
|
Chapter 14: The Barcode Reader as a Learning System |
The bad read recovery techniques described in the patents effectively turn the barcode reader into a learning system. Each scan provides information about the barcode, even if the scan is not fully decodable. The reader accumulates this information over multiple scans and uses it to improve its understanding of the barcode. |
The consolidation buffer is the repository of this accumulated knowledge. It stores not only the decoded characters but also the error coefficients associated with each character. These error coefficients represent the confidence the decoder has in each character. Over time, the buffer builds a more reliable picture of the barcode than any single scan could provide. |
The learning nature of the system is particularly evident in the treatment of the error coefficients. An arithmetical mean is calculated between the error coefficient associated with the just classified character and the error coefficient associated with the same character in the same position from previous scans. This means that characters that are consistently decoded in the same way across multiple scans become more trusted, while characters that vary from scan to scan are treated with more skepticism. |
This learning process is automatic, requiring no user intervention. The reader simply processes scans as they are presented, accumulating data until the entire barcode can be decoded or until it becomes clear that further scans will not help. |
|
Chapter 15: Handling Dot Matrix and Low-Resolution Barcodes |
One of the most challenging scenarios for barcode reading is the dot matrix barcode, which is printed using a dot matrix printer. These barcodes have low resolution and often suffer from printing defects that make them difficult to decode. |
The Symbol Technologies patent specifically addresses this challenge: 'Additionally, the bar codes may be printed in a dot matrix style in which case the ability to read the bar codes depends on the resolution of the print. Using conventional methods of decoding, such bar code symbols are often unreadable since readings thereof do not result in valid characters'. |
A SIAM News article on barcode decoding provides a vivid example of the problem: 'The authors visited their local warehouse in the Spanish province of Asturias, which receives about 1.5 million orders every month. The order forms are usually printed on low-resolution dot-matrix printers; doctors' sprawling signatures frequently cover at least part of the barcodes. The automated scanner was able to decode only 50% of the orders, forcing human intervention 750,000 times a month'. |
The multi-scan approach is particularly effective for dot matrix barcodes because the defects are typically localized. One scan may be corrupted in one area, while another scan is corrupted in a different area. By combining information from multiple scans, the decoder can overcome the individual defects and reconstruct the complete symbol. |
|
Chapter 16: The Deblurring Challenge |
Another significant challenge in barcode reading is blurring, which occurs when the barcode is moved relative to the scanner during the scan. Blurring spreads the edges of the bars, making them appear wider and softer than they actually are. |
The SIAM News article describes the mathematical model of the blurring process: 'The ideal barcode signal \( u \) is a one-dimensional 0-1 step signal; the signal \( u_0 \) received by a scanner is a noisy, blurred version of \( u \). The goal is to recover \( u \), given \( u_0 \)'. |
The article notes that standard commercial decoding techniques are based on classic edge detectors that use only local information and would have difficulty decoding blurred signals. A global approach that minimizes total-variation energy can be more effective, but it is too slow for practical use in most applications. |
The challenge of deblurring is particularly relevant to bad read recovery because blurring is not a random error---it is a systematic distortion that affects the entire symbol. However, by combining information from multiple scans with different degrees of blurring, the decoder can sometimes reconstruct a clearer version of the symbol. |
|
Chapter 17: Retry Logic as Part of System Design |
Bad read recovery does not exist in isolation---it is part of a larger system design that includes the hardware, the decoder, and the user interface. The retry logic must be coordinated with the hardware to ensure that the scanner continues to operate efficiently even during the recovery process. |
The Datalogic patent emphasizes the importance of the retry logic in the overall system: 'If the validation try gives a negative result, acquisition of a third string and reiteration of steps are performed' . The retry logic is designed to be efficient, minimizing the number of scans needed to decode the barcode. |
The patent claims that 'in case of heavily deteriorated labels, the decoding of the bar code symbol can be obtained by carrying out two only scandings, with a marked saving of time, calculation resources and therefore costs' . |
The retry logic must also be coordinated with the user interface. If the reader is unable to decode the barcode after a certain number of retries, it should provide feedback to the user indicating that the scan has failed and perhaps suggesting corrective action. |
|
Chapter 18: Summary --- Bad Read Recovery in Perspective |
Bad read recovery is an essential capability for modern barcode reading systems. It transforms failed scans from wasted efforts into valuable data that can be combined to decode symbols that would be unreadable using traditional single-scan methods. |
We have examined how different companies and technologies have approached the challenges of bad read recovery: |
Symbol Technologies developed an error correcting method that stores representations of bar code symbols from multiple scans and iteratively corrects them using data from other scans. The method identifies split and merge errors, saves partially decoded messages, and toggles between scans until the entire symbol is decoded. |
Datalogic developed a process that identifies the type of error (split or merge) and adjusts the synchronization mechanism accordingly. The method re-synchronizes by adding or subtracting elements to match the estimated character width, and combines data from scanning in both directions. |
Microscan Systems commercialized Symbol Reconstruction technology that pieces together discontinuous symbol data from multiple scan lines. The technology addresses damaged symbols, rotated symbols, and low aspect ratio symbols, with configurable redundancy and effort parameters. |
A barcode reader patent describes a method using a boundary box, symbology verification, and X-dimension calculation to reconstruct damaged symbols. The method calculates the expected length of each symbol and compares it to the actual length, using a tolerance value to determine when reconstruction is needed. |
|
The key lessons from our exploration are: |
Failed scans contain valuable information. Even when a scan cannot be fully decoded, the partially decoded data can be combined with data from other scans to reconstruct the complete symbol. |
Different scans fail in different ways. A defect that corrupts one scan may not affect another scan, and by combining data from multiple scans, the decoder can overcome the individual defects. |
Iterative correction is powerful. The decoder can toggle between two or more partial scans, correcting one scan based on information from the other, until the entire symbol is decoded. |
Error identification is the first step in recovery. By determining whether an error is a split-type or merge-type error, the decoder can choose the appropriate correction strategy. |
Symbol reconstruction is a practical reality. Commercial products implement symbol reconstruction techniques to decode damaged, tilted, and partially obscured symbols in industrial environments. |
Configurable parameters allow trade-offs. Redundancy and effort parameters allow the system integrator to optimize the decoder for speed or reliability, depending on the application requirements. |
The learning buffer accumulates knowledge. Data from multiple scans is stored and consolidated, with error coefficients tracking the reliability of each character. |
In the end, bad read recovery is a testament to the power of intelligent signal processing in barcode reading. It transforms the scanner from a simple digitizer into a sophisticated system that learns from its failures and adapts to the challenges of the real world. The art of bad read recovery lies in the careful balance of speed, reliability, and computational efficiency, creating a reader that can decode even the most challenging barcodes without requiring human intervention. |
cs@easiersoft.com