Blog
Chapter 3. Barcode scanning algorithm: localization and decode
Understanding the barcode reader technology can be complex. So, let’s simplify it. The barcode reader software scans the entire width of a barcode image to identify a barcode. Once it scans a barcode, it decodes it and presents the encoded information.
Step 1: Identify a Region Where the Barcode is Present
Step 2: Extracting the Encoded Information From the Barcode
How Barcode Scanners Work
How to Decode 1D Barcodes
Upon initiating a scan, the scanner searches for any barcode to detect its type. A barcode reader scans the entire width of an image trying to identify whether there are barcode candidates — black/white patterns. Once a barcode is identified, the barcode API has regions of interest to detect.
Decoding is then initiated. In this step, the barcode scanner tries to understand the encoded information. It counts and compares image pixels to match start and end identifiers. Then, it interprets patterns between the start and end identifiers based on that code type’s specifications to unravel the encoded data.
How to Decode 2D Barcodes
Similarly to 1D barcodes, upon initiating a scan, the scanner tries to find a barcode. As mentioned, different barcode symbologies have different recognition patterns.
In the decoding step, the barcode reader API tries to interpret patterns of the black and white modules based on that code type’s specifications. These specifications are all standardized. Besides the barcode information, which is typically a combination of numeral and characters, a 2D barcode usually contains redundant data. The software is then able to read and decode the data value. The encoded value is built like stacks of codewords.
Advanced Localization Methods
There are three localization methods:
- Connected Blocks
- Statistics
- Line Segment
Each method has unique advantages and disadvantages. A well-designed barcode scanner needs to balance the trade-off between speed and accuracy.
Connected Blocks [Connected Components Labeling]
The first localization method is through identifying connected components in an image.
Step 1. Connect adjacent pixels
This method looks for a cluster of pixels connected together. It groups image pixels into components based on intensity and connectivity.
- Pixels in a connected component share similar pixel intensity values
- Pixels in a connected component are in some way connected with each other.
Example:
Step 2. Look for finder patterns
Once all the components in an image are identified, it then looks for known barcode patterns to filter the barcode locations. For instance, QR codes are characterized by a distinct square target in three of the four corners. Each square target in the corner consists of two blocks: a solid square in the middle of a hollow outer square. The cross-sectional thickness of the outer square, the gap and the width of the solid center square has the ratio of 1:1:3.
Step 3. Identify barcode regions based on finder patterns
Once the three distinct squares are located, edges of the barcode need to be determined along with, grouping the three corner square targets to the same barcode, consider special cases where a square is missing or partially damaged etc. Once the barcode regions are identified based on barcode patterns, the rest of the space is filtered out.
Advantages and drawbacks
The main advantage of this method is speed and low processing power required. Its drawback is the high susceptibility to damages on the barcode. For instance, if a pen marks across a 1D barcode horizontally, the separated bars are now one connected block and destroys the recognizable 1D pattern.
Statistics
The main advantage of this localization method is identifying barcodes in blurred images. If an arbitrary region in a binarized image is selected to calculate the ratio between black and white pixels, we can conclude that a particular region is likely to contain a barcode or not. Once a region is concluded to contain a barcode, it then further refines the barcode regions for barcode locations by searching for known barcode patterns.
Line Segment
As the name suggests this method looks for straight lines in an image and then filters out the barcode regions by matching the lines to known barcode patterns. This method works well for damaged barcodes. As a trade-off, it requires additional computation than the connected blocks method.
This post is a part of the series: Best Practices for Maximizing Barcode Reader Technology.
Chapter 01 Where are barcodes used
Chapter 02 Character set encoded in barcodes
Chapter 03 Barcode scanning algorithm: localization and decode
Chapter 04 Developer tip: improve barcode recognition rates
Chapter 05 Developer tip: improve barcode recognition speed
Chapter 06 Technical considerations when choosing a barcode SDK