1D (one-dimensional) barcodes can only encode digital data and have been used for the past two decades in product transportation and tracking, system security, supermarkets, and more. With 2D (two-dimensional) barcodes, the data is encoded as 2D symbols both horizontally and vertically, as shown in Figure 1 below.
2D symbols can contain much more data than 1D symbols. 2D barcode solutions can provide greater information density than traditional 1D barcodes, especially for applications that need to encode precise information rather than simple code information.
Some applications of 2D barcode technology include product labeling, product information tracking and inspection, mobile security, immigration inspection services, healthcare, and e-commerce.
Figure 1: Example of a 2D barcode
Many 2D barcode algorithms exist today, which has spawned a range of applications using different barcode technologies. Generally speaking, there are two types of 2D barcodes: 1) Stacked 2D barcodes such as PDF417 and Code 49, 2) Matrix barcodes such as QR codes and Data Matrix.In this article, we are limited to discussing data matrix barcode technology.
2D Data Matrix Barcode Technology
2D Data Matrix barcodes consist of black and white modules arranged in a square or rectangle, as shown in Figure 1. The encoded data bits are mapped to a region consisting of black and white modules (or cells), called the data region.For details on the different types of encoding schemes supported by 2D Data Matrix barcodes, see References.
The data area is surrounded by an anchor graphic (the bottom and left side of the anchor graphic contains only black modules, while the upper and right side of the anchor graphic consists of alternating white and black modules). Data Matrix 2D barcodes support multiple data areas separated by rank graphics to accommodate more data information.
There are two versions of the data matrix, one based on cyclic redundancy check (CRC) and convolutional error correction, and the other based on Reed Solomon (RS) error correction. There is no difference between CRC-based and RS-based data matrix decoding for scanning, reading, and extracting data bits. After extracting the data bits, CRC-based decoding differs from RS-based decoding paths because of their different interleaving and error correction methods.
Figure 2: 2D barcode scanner block diagram and DSP processing core
Here we consider the decoding of emerging RS-code based 2D data matrix barcodes on a small form factor Blackfin processor. A block diagram of a 2D barcode scanner connected to a DSP processor via a PPI-DMA channel is shown in Figure 2 above.
Implementing barcodes on small form factor DSPs
The sensor scans the barcode and transmits the pixel data to the DSP through a parallel port interface (PPI). After that, the DSP processor processes the image pixels and extracts the data bits corresponding to the black and white blocks in the data area, and then performs error correction. The process of extracting data bits from a specific data area of a scanned 2D barcode is shown in the flowchart shown in Figure 3 below.
Figure 3: Flowchart for extracting data bits from a 2D data matrix symbol
We treat 2D Data Matrix barcodes as M x N images (usually QVGA or VGA images) and process them. The camera’s CMOS sensor captures the image and transmits the image pixels to the DSP for processing.
The question now is, how much memory is needed to hold the images during processing? For example, taking VGA (ie 640×480) as an example, we need about 300 kB of data memory to save the captured image. The size of a processor core depends on the amount of memory it contains.
Especially L1 high-speed memory, which takes up more silicon area and has a higher overall cost. Therefore, most processors contain very limited L1 memory.
On the other hand, L2 or L3 memory usually has a larger capacity, occupies a smaller area, and costs less. However, they are slower and require data transfers to and from the processor’s working memory (L1) via DMA.
Next we will discuss the implementation of Data Matrix 2D barcodes using two different processors in the Blackfin family, one with 16 kB of L1 and larger L2/L3 memory, and the other with only 16 kB of L1 memory.
For processors with L2 and L3 memory, the captured image is transferred to L2 memory via DMA and PPI interface. The data bits extracted from the 2D barcode are then processed by simultaneously moving a small number of image pixels from L2 to L1 memory. In this case, we use another DMA for data transfer between L1 and L2, and the overall decoding is simple and not complicated.
On the other hand, if there is only a small amount of L1 memory, and no L2/L3 memory, the problem is quite tricky. In this case, we do more scans of the same barcode and transfer the region of interest (ROI) to the L1 memory for processing via the appropriately set PPI-DMA channel.
Although this system is complex to set up, its cost and size are small compared to the previous example. Next, we’ll discuss techniques for decoding 2D Data Matrix barcodes using the two processor instances mentioned above.
Implemented with L2 memory
In this case, all scanned images are read into L2 memory via the PPI-DMA channel, and another memory DMA is used to process them by accessing part of the image in L2. As shown in Figure 4(a) below.
Figure 4: 2D barcode decoding with small form factor Blackfin processor,
(a) with L2/L3 and L1 memory, (b) with only L1 memory.
Using OmniVision CMOS VGA sensor, we get pixel data and control signals, HREF (horizontal reference output), VSYNC (vertical sync output) and PCLK (pixel clock output) row by row. The PPI-DMA channel reads pixels into L2 memory at a clock rate of 27 MHz. In this case, the DMA setup is simple because we read the entire image in a single scan.
We basically follow the flowchart shown in Figure 3 above to extract the data bits from the Data Matrix barcode module. If there are any orientations in the scanned image, we can correct the orientation and bias because we have the full image in L2 memory.
Now, let’s assume that the image is scanned correctly without any orientation and bias. First, we move the top rows and right columns of the Data Matrix barcode positioning pattern from L2 into L1 memory. After measuring the average height and width of the modules in the positioning graphic, we mark the midpoints of all the top and right modules of the positioning graphic, and store the x and y coordinate values of the pixel positions of the midpoints in memory for later use. No L2 or L3 memory When there is no L2/L3 memory, we read the image directly into L1 memory.Due to limited L1 memory space, we once
Read the entire image directly into L1 memory. As shown in Figure 4(b) above.
In this case, we scan the image multiple times for barcode decoding. Using the PPI delay and PPI count registers, the top rows and right columns of pixels located in the graphics module are read into L1 memory in one scan. More DMA programming is required in this case because we need to read the selected image pixels from the scanner output into L1 memory via the PPI-DMA channel. We find the size of the positioning graphics module and its midpoint position coordinates and store it for future use.
When the image has a slight orientation or deviation, we read multiple rows of pixels to correct the orientation or deviation. Here, we do image processing line by line because we don’t have the full image. Extracting Data Bits from Data Matrix Barcodes We follow the second half of the flowchart (shown earlier in Figure 3) to extract bit information from the Data Matrix Barcode Black and White modules.
Here, we assume that the data matrix contains a single data area consisting of black and white modules. We know that with the coordinates of the midpoint of the positioning graphics module, we can easily obtain the center points of all modules as the intersecting horizontal lines (perpendicular to the left positioning graphics).
It also locates the midpoint position and vertical line of the module on the right side of the graphic (perpendicular to the bottom edge of the positioning graphic and by positioning the midpoint position of the top block of the graphic). We can’t draw all these lines to identify intersections because we don’t have the full picture in L1 memory.
However, we can obtain the intersection by scanning one row at a time (using the y-coordinate of the midpoint of the module on the right of the positioning graph as the row index), and comparing the current row and column index with the x-coordinate of the midpoint of the module on the upper side of the positioning graph.
If both are the same, then it is the intersection, otherwise we continue to scan the line. Using this process, we scan the intersection of the modules and find the value of the pixel at that location.
We decode the bit as 0 if the pixel value is greater than 128 (i.e. light colors), or as 1 if the pixel value is less than 128. In the same way, we can extract all the bits of the data matrix barcode data area.
For processors with L2 memory, we move the row of pixels corresponding to the y-coordinate of the point in the module to the right of the positioning graph from L2 into L1 memory. While we are processing the current pixel row, use DMA to move the next pixel row. However, when using processors without L2 memory, we have to do real-time data extraction. At this point, the PPI-DMA fills the L1 memory with the next row of data, and we have to finish processing the current row (do basic data bit fetching).
Matrix barcodes use 2D interleaved data bits. After extracting the data bits from the data region module, we perform deinterleaving to obtain the data bits of the error correction codeword.For details on 2D data bit interleaving, see References.
We use a precomputed lookup table for deinterleaving. Since Data Matrix barcodes support data fields of different sizes, the size and table cells of the de-interleaving look-up table are also different. It is not possible to keep lookup tables of all sizes in a small size processor. However, if the data matrix size is known in a given application, we only need to store the specific deinterleaving lookup table. After deinterleaving, the data bits are formed into codewords in byte format, which are input to the RS decoder.
barcode error correction
The emerging ECC-200 data matrix barcode uses RS (N, K) codes to correct errors and omissions of deinterleaved bits. The RS (N, K) code can correct up to (NK)/2 errors or up to (NK) omissions (if no errors exist). The Galois domain used in this application is GF(28). Data Matrix barcodes use different RS codeword lengths for different data field sizes. For example, a 14×14 data area barcode uses RS(24, 12) code for error correction, and a 16×16 data area barcode uses RS(32, 18) code. The complexity of the RS decoder depends on the size of the data area. As the length of the RS codeword increases, the memory needs to store all the RS decoding work buffers.
To implement the RS decoder efficiently, we use lookup tables for Galois domain computations. The same Galois field log and antilog lookup tables are used to decode all RS codeword lengths, so field cells are also GF(28). We need about 2 kB of L1 memory to store the log and antilog lookup tables.
Data Matrix Barcode Decoding Complexity
2D barcode decoding has two parts: 1) image processing, 2) barcode decoding. If the captured image is not properly aligned with the decoded area, we may need to perform image rotation, bias correction, etc. to align the image with the decoded area.
In this case, the complexity of the image processing stage is greater than the actual barcode decoding. In this post, we assume that the image is aligned with the decoded region. The decoding complexity (in terms of cycles and memory) of a data matrix barcode depends on the size of the data symbols. If the data symbol size is large, with multiple large data regions in each symbol, then we need more memory to hold the image’s line pixels and RS working buffer. The amount of data that needs to be processed per unit time also increases with the size of the data area. For a VGA image with a 16×16 data area per Data Matrix barcode symbol, we would need approximately 6kB of data memory and 4kB of Blackfin program memory. The approximate number of cycles to run a single module on a BF53x core is as follows:
Module size and quantity: 7,200
Data Bit Extraction: 2,000 cycles
Deinterleaving and Packing: 600
RS decoding: 7,000 cycles
Summary of this article
This article discusses DataMatrix 2D barcode decoding on the small form factor Blackfin processor. It also explains the different ways to decode 2D barcodes with or without high latency L2 memory. The complexity of RS-based data matrix 2D barcode decoding is analyzed, and the memory and cycles required to decode a single 16×16 data symbol in a VGA image using BF53x processors are estimated.