Speed Compensation: The Art of Correcting for Unsteady Hands |
Executive Summary |
This article provides a comprehensive exploration of speed compensation techniques in barcode decoding. We examine how decoders correct for the inevitable variations in scanning speed that occur when a barcode is read by hand, ensuring that the measured widths of bars and spaces accurately reflect their physical dimensions. Rather than focusing on abstract theory, we ground every concept in concrete design examples and real patent disclosures from industry leaders including Pitney Bowes Inc., Symbol Technologies, and others. We explore the fundamental challenge of variable scan speed, the use of dynamic thresholds that track the signal, the application of moving averages, the fitting of spot-speed profiles, and the practical implementation of these techniques in real-world decoders. The article covers both the theoretical underpinnings and the practical trade-offs in designing speed compensation algorithms. The closing summary synthesizes the key lessons and offers practical guidance for anyone implementing barcode decoding systems. |
|
Chapter 1: The Challenge of the Unsteady Hand |
A barcode reader measures widths. It shines a light on the barcode, captures the reflected light, and measures how long it takes for the scanning spot to cross each bar and space. These time measurements are converted to width measurements, and from these widths, the decoder extracts the data. |
The fundamental assumption is that the scanning speed is constant. If the speed is constant, then the time taken to cross a bar is directly proportional to its physical width. A narrow bar takes a short time; a wide bar takes a long time. The decoder can simply compare the measured times to determine which elements are narrow and which are wide. |
The problem is that the scanning speed is rarely constant. When a user waves a handheld scanner across a barcode, the speed varies significantly. The hand accelerates at the start of the scan, may decelerate near the end, and may jitter in between. These speed variations distort the time measurements, making narrow bars appear wide and wide bars appear narrow. |
A patent from Symbol Technologies explains the challenge: 'If a scanning system determines time domain widths of elements, i.e., how long it takes the spot to cross the elements, elements that are spatially equal will produce inconsistent time domain widths if the speed varies. Variation in spot speed may be sufficient to cause a decode failure, which is an inability to decode, or a misdecode, which is an incorrect determination.' The patent further notes that 'a speed change of 25% from the start to the finish of a character will make bars at the end of the character appear 25% narrower than bars at the start, enough of a difference to affect the decoding.' |
Speed compensation is the set of techniques that correct for these variations, allowing the decoder to accurately measure the physical widths of the bars and spaces despite the unsteady hand of the user. |
|
Chapter 2: The Nature of Speed Variation |
Understanding the sources and characteristics of speed variation is the first step in compensating for it. There are several distinct causes of speed variation in barcode scanning. |
Handheld wand scanners are the most obvious source. When a user manually moves a wand across a barcode, the speed is typically zero at the start, accelerates quickly, and may decelerate near the end. The user's hand is not a precision motion control system, and the speed profile can vary significantly from one scan to the next. The Symbol Technologies patent notes that 'the spot speed varies due to manual motion. Typically, the spot accelerates quickly then slows down.' |
Oscillating mirror scanners found in fixed-position laser scanners have their own speed profile. The motor that oscillates the mirror causes the spot speed to increase and then decrease, creating a profile which is generally sinusoidal. This variation is predictable but still requires compensation. |
Curved surfaces add another dimension to the challenge. If the barcode is applied to a curved object, the speed of the spot crossing it can vary depending on the degree of curvature. The Symbol Technologies patent notes that 'if the code is applied to a curved object, the speed of the spot crossing it can vary depending on the degree of curvature.' |
The key challenge is that speed variation can occur within a single character. As the Symbol Technologies patent explains, 'while speed variation from character to character is not a significant difficulty, speed variation within a character is a problem.' A 25% speed change from the start to the finish of a character is sufficient to cause decoding errors. |
|
Chapter 3: The Pitney Bowes Dynamic Threshold Approach |
Pitney Bowes Inc. developed a practical method for speed compensation that dynamically adjusts the threshold used to distinguish between narrow and wide elements. This method, described in U.S. Patent 5,708,261, uses the indicators from previously decoded elements to establish a current threshold. |
The method starts with the known start character of a Code 39 barcode. The decoder keeps an indicator (a time measurement) for the first element of the start character, and decodes it as a narrow element. It then establishes a threshold value based on this indicator for use in decoding subsequent elements. |
As the decoder processes each element, it keeps an indicator of the time taken to illuminate that element. It then adjusts the threshold value based on changes in the indicators for the most recent two elements that have been decoded as narrow type. The patent describes several variations: 'The current threshold value is adjusted by setting it equal to the average of the indicators for the last two narrow elements times the decode factor.' Alternatively, 'the current threshold value is adjusted by multiplying it by the ratio of the indicator for the most recent narrow element over the indicator for the previous narrow element.' |
This dynamic threshold approach allows the decoder to track changes in scanning speed. If the speed increases, the indicators for narrow elements decrease, and the threshold is adjusted downward. If the speed decreases, the indicators increase, and the threshold is adjusted upward. The threshold 'tracks' the speed, maintaining the correct decision boundary between narrow and wide elements. |
|
Chapter 4: The Symbol Technologies Spot-Speed Profile Approach |
Symbol Technologies developed a more sophisticated speed compensation method that fits a speed profile to the scan data. This method, described in U.S. Patent 5,369,260, uses the average speed across individual characters to determine a spot-speed profile. |
The method works as follows. The decoder first measures the average spot speed across each character in the barcode. It then fits a speed profile to these average speed data points. The key innovation is that the curve is not forced to pass through every data point. Instead, the data points are treated as 'experimental approximations with random errors, and a curve is fit between the data points, rather than through them.' |
The speed profile consists of one or more straight line segments, each representing an interval with assumed constant acceleration. Each segment is typically two to four characters in length, depending on the density of the barcode symbol. The segments may be slightly disjoint. |
Once the speed profile is determined, it is used to 'normalize' the scan data. The raw time measurements are adjusted to what they would have been if the speed had been constant. This normalized data is then passed to the decoder. |
The patent notes that this approach avoids a common pitfall: 'the curve is not forced to pass through every data point. In this way, a spot-speed profile is derived that does not incorrectly attribute, to speed variation, errors due to other sources, e.g., random edge errors from printing.' |
|
Chapter 5: The Moving Average Approach |
A more practical and widely used approach to speed compensation is the moving average. Instead of trying to fit a complex speed profile, the moving average method continuously updates the estimated module width based on recent measurements. |
The BCB patent describes this approach in detail: 'A selected minimum number of modules is divided into one or more associated pairs of elements... in order to calculate Z, in a directional moving average process... a fresh calculation for Z is made for each line.' Z is the average timing count per module---the fundamental unit of measurement in the barcode. |
The moving average works by maintaining a sliding window of recent measurements. For each new element, the decoder calculates a new Z by averaging the measurements in the window. This Z is then used to decode the next element. The window slides forward, dropping the oldest measurement and adding the newest. |
The BCB patent explains that there are two selectable variables for the moving average: a selected minimum number of modules, or a selected constant number of pairs of elements. The average number of timing counts per module, Z, may thus be calculated for each edge of the data elements. |
A developer on an 8052 microcontroller forum described the practical experience with moving averages: 'When I had to write a bar code decoder I started with what you suggested but quickly found that very few scans are of such a uniform velocity to make that approach work. Turns out you have to calculate the average length of bars and spaces many times throughout the scan. What you end up with is a sliding average that represents the average width of the previous and next 5 (or some other magic number) bars and spaces. And even then you have to be ready to handle minor printing errors that distort the bars, etc.' |
|
Chapter 6: The Median as a More Accurate Reference |
The BCB patent notes that the median of selected prior Z values can be used as a more accurate reference than the average. The median is less sensitive to outliers, making it more robust to noise and printing defects. |
The patent explains: 'The median of a selected number of prior calculated Z's may be selected for use as the operational Z, a more accurate reference yardstick distance, or local average, with which to measure a sample distance.' |
The use of the median is a refinement of the moving average approach. Instead of simply averaging the last N measurements, the decoder sorts the measurements and takes the middle value. This provides a more stable reference, particularly when some of the measurements are corrupted by noise or printing defects. |
The patent also mentions other averaging possibilities, including the mode, the geometric mean, and the quadratic mean. Each has its own strengths and weaknesses, and the choice depends on the specific application. |
|
Chapter 7: Practical Implementation in Low-Cost Microcontrollers |
Speed compensation must be implemented in the microcontroller that is the heart of the barcode reader. The algorithm must be efficient enough to run in real-time, with minimal memory and processing overhead. |
A developer on the 8052 microcontroller forum described a practical implementation: 'The secret with a bar code decoder is i expect is to find the average length of the long and short marks and spaces and with a bar code you know the format is such that the first two and last two symbols are always short so you can allow for variations in the speed between different'swipes' and variations during each 'swipe' which I expect would be small.' |
The developer notes that the start and stop patterns are particularly valuable for speed compensation: 'you know the format is such that the first two and last two symbols are always short.' This provides a known reference that can be used to calibrate the module width estimate at both ends of the barcode. |
The moving average approach is particularly well-suited to low-cost microcontrollers because it requires only a small buffer of recent measurements and simple arithmetic operations. No complex curve fitting or floating-point calculations are required. |
Chapter 8: The Pitney Bowes Inserter Application |
The Pitney Bowes patent provides a specific application example: an inserter system for mail processing. In this system, control information is read from a control document by a bar code scanner, and the speed compensation ensures reliable decoding despite the variable speed of the documents moving through the system. |
The patent explains that inserter systems 'capable of generating over 10,000 mail pieces per hour' require reliable bar code reading. The control document contains 'a bar code and other information that is specific to a particular addressee.' The bar code contains 'control information for instructing the downstream modules as to how to assemble a particular mail piece.' |
The speed compensation method is essential because the document speed may vary as it moves through the inserter. The dynamic threshold approach ensures that the decoder can still distinguish between narrow and wide elements, even when the speed varies. |
This application demonstrates that speed compensation is not just for handheld scanners. It is also important for automated systems where the speed of the barcode past the reader may vary. |
|
Chapter 9: Edge-to-Similar-Edge Measurements |
Another technique for speed compensation is to use edge-to-similar-edge measurements. Instead of measuring individual bar and space widths, the decoder measures the distance between similar edges (e.g., the distance between the leading edge of one bar and the leading edge of the next bar). |
The Symbol Technologies patent notes that for continuous codes (e.g., UPC, Code 128, Interleaved 2 of 5), 'segments preferably use edge-to-similar-edge measurements.' This approach is more robust to speed variation because it measures the combined width of a bar and a space, rather than the individual widths. |
The BCB patent also emphasizes the power of edge-to-edge measurements: 'Edge-to-edge refers a particular strength that makes them less sensitive to uniform ink spread or shrink.' Edge-to-edge measurements are also less sensitive to threshold shifts, as the leading edges of bars are well-defined. |
Edge-to-similar-edge measurements are particularly useful for speed compensation because the combined width of a bar and a space is less affected by speed variation than the individual widths. If the speed varies, both the bar and the space measurements are affected proportionally, but their sum is more stable. |
Chapter 10: The Challenge of Ink Spread |
Ink spread is a printing defect that can cause the measured widths of bars and spaces to deviate from their ideal values. Ink spread occurs when the ink spreads beyond the intended boundaries of the bar, making the bar wider and the adjacent space narrower. |
Ink spread can be confused with speed variation if the decoder is not careful. The Symbol Technologies patent emphasizes that the speed profile 'is not forced to pass through every data point' to avoid 'incorrectly attributing, to speed variation, errors due to other sources, e.g., random edge errors from printing.' |
The BCB patent also addresses ink spread, noting that 'edge-to-edge measurements make them less sensitive to uniform ink spread or shrink.' By measuring the combined width of a bar and a space, the effect of ink spread is partially canceled: if the bar is wider due to ink spread, the adjacent space is narrower by the same amount. |
Edge-to-edge measurements are particularly valuable for speed compensation because they are robust to both speed variation and ink spread. This makes the decoder more reliable in the face of real-world imperfections. |
|
Chapter 11: Acceleration Compensation |
Speed variation is not just about constant speed changes. It can also involve acceleration---changes in speed within a character. The Symbol Technologies patent addresses acceleration compensation by using a speed profile that has non-zero acceleration within at least some of the characters. |
The patent describes the process: 'average spot speeds across individual characters are determined, and a speed profile is fit to these average spot speed data points.' The speed profile 'consists of a plurality of straight line segments,' where 'each straight line segment represents an interval with assumed constant acceleration.' |
If the speed is accelerating, the measured widths of elements at the end of the character will be narrower than those at the beginning. The speed profile accounts for this by adjusting the normalization factor across the character. |
The acceleration compensation is particularly important for short characters, where the speed change within the character is significant relative to the total duration. A 25% speed change from the start to the finish of a character can cause decoding errors if not compensated. |
Chapter 12: The Moving Average and (n,k) Codes |
The BCB patent explains how the moving average approach is particularly well-suited to (n,k) codes, where each character has a fixed number of modules. In these codes, the module width can be calculated from the total duration of each character. |
The patent notes that '(n, k) codewords have a (fixed) pitch, applicants characterize such codes as directly character by character self-clocking.' This means that the decoder can calculate the module width for each character and use it to decode the next character. |
The BCB approach extends this concept: 'The average number of timing counts per module, Z, is first calculated in BCB using a known n from a given (fixed) BCB start pattern or stop pattern convention... and thereafter the number of modules per individual element is decoded one element at a time, continuously, from one end of the symbol to the other, element by element.' |
The moving average is a natural fit for this continuous decoding approach, as it allows the module width estimate to be updated continuously as the scan progresses. |
|
Chapter 13: The Multi-Edge Reference Technique |
The BCB patent describes a 'multi-edge reference technique' that uses multiple edges to calculate a more accurate module width estimate. This technique involves calculating the module width from multiple pairs of elements and combining them. |
The patent explains: 'a more accurate Z for calculations may be had using applicants' various 'multi-edge' reference techniques which involve different types of averages, including, for example, the arithmetic mean and the median.' |
The multi-edge technique is particularly valuable for noisy signals. By averaging across multiple edges, the decoder reduces the impact of individual measurement errors. The median is especially robust, as it is unaffected by outliers. |
The patent also describes using the mode, the geometric mean, and the quadratic mean as alternatives. The choice depends on the characteristics of the signal and the application requirements. |
Chapter 14: The Role of Start and Stop Patterns |
Start and stop patterns play a crucial role in speed compensation. They provide known reference points that the decoder can use to calibrate the module width estimate. |
The Pitney Bowes patent uses the start character to establish the initial threshold: 'keeping an indicator of an amount of time that a light source from a scanner system illuminates a selected element from the first character, establishing a current threshold value based upon the selected element indicator.' |
The Symbol Technologies patent uses the start and stop patterns to determine the speed profile: 'preferably, average spot speeds across individual characters are determined, and a speed profile is fit to these average spot speed data points.' The start and stop patterns provide known reference points at the beginning and end of the symbol. |
The BCB patent uses the start and stop patterns to calculate the initial module width: 'Z is first calculated in BCB using a known n from a given (fixed) BCB start pattern or stop pattern convention.' |
In all cases, the start and stop patterns provide the anchor points that the decoder needs to establish the initial reference for speed compensation. |
|
Chapter 15: The Character Gap in Discrete Codes |
In discrete symbologies like Code 39, there is a small gap between characters called the character gap. This gap is typically a narrow space that separates the characters. |
The character gap is important for speed compensation because it provides a known reference point. The gap is always a narrow space, so the decoder can use it to check the module width estimate. |
The Pitney Bowes patent includes the character gap in the decoding process: 'each character must be separated by a character gap.' The decoder measures the character gap and uses it to validate the decoding of the surrounding characters. |
If the module width estimate is off, the measured gap will be inconsistent with the expected gap. The decoder can use this inconsistency to correct the module width estimate. |
Chapter 16: Low Resolution and Degraded Images |
The challenge of speed compensation is even greater for image-based decoders, where the barcode is captured by a camera and processed in software. The image may be low resolution, out of focus, or distorted. |
A patent from the University of California describes a method for decoding bar code images using multi-order feature vectors that addresses the challenges of low resolution and degraded images. The method uses a 'set of bar width information estimates' that are 'representative of the width of an interval between two edge transitions in the bar code symbol.' |
The patent notes that 'hard thresholding techniques often produce errors when the normalized width value being thresholded falls near the edge of a thresholding range. This is particularly the case when low resolution images are used as the basis for calculating the normalized widths.' |
The multi-order approach is a sophisticated form of speed compensation that uses multiple measurements (first-order, second-order, etc.) to create a more robust estimate of the element widths. |
|
Chapter 17: Moving Averages as Low-Pass Filters |
A patent from a Japanese inventor describes the use of a moving average circuit as a low-pass filter to smooth the input signal and eliminate noise. The moving average circuit is used to calculate the module width estimate by averaging recent measurements. |
The patent explains: 'The moving average circuit basically has a function of a low-pass filter and thus has a characteristic of eliminating noise such as small frequency components to smooth a waveform.' |
The moving average is implemented as a digital filter with a variable sampling width. The sampling width can be changed to adapt to the frequency characteristics of the input data: 'Changing the moving average sampling width means changing the frequency characteristics of a filter in accordance with the frequency component of the input data.' |
This approach is particularly effective for speed compensation because it smooths out the measurement noise while tracking the underlying changes in speed. |
Chapter 18: The Weighted Moving Average |
A refinement of the moving average approach is the weighted moving average, where recent measurements are given more weight than older measurements. This allows the decoder to respond more quickly to changes in speed. |
The Japanese patent describes the weighted moving average method: 'employment of a weighted moving average method... enables removal of external factors included in the waveform of the input data, for example, a gradient and so on.' |
The weighted moving average allows the decoder to track speed changes more closely, reducing the lag between the actual speed and the estimated module width. This is particularly important for fast scans where the speed changes rapidly. |
The patent also describes a function for changing the weighted amount of the weighted moving average, allowing the decoder to adapt to different scanning conditions. |
|
Chapter 19: The Forced Reset Function |
A practical challenge in speed compensation is the effect of noise spikes. A noise spike can cause the digitized signal to remain high for an extended period, distorting the width measurement. |
The Japanese patent describes a forced reset function that addresses this problem: 'a function of forcibly dropping to the low level after a lapse of a fixed period is added. This eliminates the influence of noise on the detection data.' |
The forced reset function works by detecting when the digitized signal has remained high for too long. When this happens, the function forces the signal low, preventing the noise spike from corrupting the width measurements. |
This function is particularly important for speed compensation because a noise spike can cause the decoder to misestimate the module width, leading to decoding errors. |
Chapter 20: The Practical Realities of Handheld Scanning |
A developer on the 8052 microcontroller forum provided practical insights into the challenges of handheld scanning: 'When I had to write a bar code decoder I started with what you suggested but quickly found that very few scans are of such a uniform velocity to make that approach work. Turns out you have to calculate the average length of bars and spaces many times throughout the scan.' |
The developer notes that 'you have to be ready to handle minor printing errors that distort the bars, etc.' This is a key insight: speed compensation must be robust to both speed variation and printing errors. |
The developer also notes that the start and stop patterns are particularly valuable: 'you know the format is such that the first two and last two symbols are always short.' This provides a known reference that can be used to calibrate the module width estimate. |
The practical lesson is that speed compensation is essential for handheld scanning. Without it, the decoding success rate would be unacceptably low. |
|
Chapter 21: The Error of Misinterpreting Speed Variation |
A key insight from the Symbol Technologies patent is that speed variation can be misinterpreted as printing errors. If the decoder assumes that the speed is constant and encounters a measurement that is inconsistent with the expected pattern, it may incorrectly attribute the inconsistency to a printing defect. |
The patent notes that 'the error introduced by spot-speed variation combined with other errors, such as printing defects or ambient light, may also cause failure or misdecode, even if the error from spot speed is tolerable.' |
The speed profile approach avoids this by treating the data points as 'experimental approximations with random errors, and a curve is fit between the data points, rather than through them.' This prevents the decoder from incorrectly attributing speed variation to printing errors. |
This is a subtle but important point: speed compensation is not just about correcting the measurements; it is also about correctly identifying the source of errors. |
Chapter 22: The Processing Time Trade-off |
The choice of speed compensation technique involves a trade-off between accuracy and processing time. More sophisticated techniques, like the speed profile approach, provide better accuracy but require more processing. |
The Symbol Technologies patent notes that 'the processor time required for such polynomial curve fitting is substantial, and could make real time processing more difficult.' This is why the patent recommends using straight line segments rather than polynomial curves: 'the segments may be slightly disjoint.' |
The moving average approach provides a good balance between accuracy and processing time. It requires only a small buffer of recent measurements and simple arithmetic operations, making it suitable for low-cost microcontrollers. |
The choice of technique depends on the application requirements. For high-speed applications where processing time is critical, the moving average approach may be preferable. For applications where accuracy is paramount, the speed profile approach may be justified. |
|
Chapter 23: The Future of Speed Compensation |
The future of speed compensation in barcode decoding is likely to involve more sophisticated algorithms and greater integration with the digital imaging pipeline. As image sensors become more capable and microcontrollers become more powerful, the trend is toward software-based decoding with advanced signal processing. |
The multi-order feature vector approach described in the University of California patent is one example of this trend. By using multiple orders of measurements (first-order, second-order, etc.), the decoder can create a more robust estimate of the element widths. |
Machine learning techniques may also be applied to speed compensation. By training a neural network on a large dataset of scans with known speed profiles, the decoder could learn to correct for speed variation more accurately than with hand-crafted algorithms. |
However, the fundamental principles described in this article---dynamic thresholds, moving averages, and speed profile fitting---will remain relevant for the foreseeable future. |
|
Chapter 24: Summary --- Speed Compensation in Perspective |
Speed compensation is an essential technique in barcode decoding, allowing the decoder to correct for the inevitable variations in scanning speed that occur in real-world use. Without speed compensation, the decoder would be unable to reliably distinguish between narrow and wide elements, leading to decode failures and misdecodes. |
We have examined how different companies and technologies have approached the challenge of speed compensation: |
Pitney Bowes Inc. developed a dynamic threshold approach that uses the indicators from previously decoded narrow elements to adjust the threshold for decoding subsequent elements. This method tracks changes in scanning speed and maintains the correct decision boundary. |
Symbol Technologies developed a speed profile approach that fits a curve to the average spot speeds across individual characters. The curve is not forced to pass through every data point, avoiding the misinterpretation of printing errors as speed variation. The speed profile is used to normalize the scan data. |
The BCB patent describes a moving average approach that continuously updates the module width estimate based on recent measurements. The moving average is particularly well-suited to (n,k) codes and provides a good balance between accuracy and processing time. |
The Japanese patent describes the use of moving averages as low-pass filters, with weighted moving averages providing faster response to speed changes. The forced reset function eliminates the effect of noise spikes. |
The University of California patent describes a multi-order feature vector approach that uses multiple measurements to create a robust estimate of the element widths, addressing the challenges of low resolution and degraded images. |
|
The key lessons from our exploration are: |
Speed variation is a fundamental challenge in barcode decoding. It can cause narrow bars to appear wide and wide bars to appear narrow, leading to decode failures. |
Dynamic thresholds track changes in speed. By continuously updating the threshold used to distinguish between narrow and wide elements, the decoder can maintain accurate decoding despite speed variation. |
Moving averages provide a practical solution. By maintaining a sliding window of recent measurements, the decoder can estimate the current module width and adapt to speed changes. |
Speed profiles provide a more sophisticated solution. By fitting a curve to the speed data, the decoder can correct for both constant speed changes and acceleration. |
Start and stop patterns provide the anchor points. The known pattern of the start and stop characters allows the decoder to calibrate the module width estimate. |
Edge-to-similar-edge measurements are more robust. Measuring the combined width of a bar and a space reduces the impact of both speed variation and ink spread. |
The choice of technique depends on the application. The moving average approach is well-suited to low-cost microcontrollers, while the speed profile approach may be justified for high-accuracy applications. |
In the end, speed compensation is a testament to the ingenuity of engineers who have developed elegant solutions to a difficult problem. The art of speed compensation lies in the careful balance of accuracy, robustness, and efficiency, creating a decoder that can handle the unsteady hands of real-world users. |
cs@easiersoft.com