2D Barcode Decoding Implementation on Low Footprint DSPs - Embedded.com

2D Barcode Decoding Implementation on Low Footprint DSPs

This “Product How-To” article focuses how to use a certain product in an embedded system and is written by a company representative.

Barcodes are traditionally used to encode the key alpha-numeric information in symbol terms so that the digital systems can scan and read the information without feeding the information to the digital system every time.

The 1D (one-dimensional) barcodes, which can only encode numeric data, played a major role in the last two decades in applications such as, product shipping and tracking, system security, supermarkets, etc. With 2D (two-dimensional) barcodes, the data are encoded in both the horizontal and vertical directions of the 2D symbol as shown in Figure 1 below .

The amount of data that can be contained in a single 2D symbol is significantly greater than that stored in a 1D symbol. 2D barcode solutions provide greater information density than conventional 1D barcodes particularly for applications that require encoding of explicit information rather than simple code information.

A few applications of 2D barcode technology include product labeling, product information tracking and checking, mobile security, immigration check services, healthcare, e-commerce, etc.

Figure 1: An example of a 2D barcode

Many 2D barcode algorithms are available today which has resulted in a range of applications adopting different barcode technologies. In general, there are two types of 2D barcodes: 1) stacked 2D barcodes such as PDF417 and Code 49, and 2) matrix bar codes such as QR code and data matrix. In this article, we restrict our discussion to data matrix barcode technology [2].

2D Data Matrix Barcode Technology
A 2D Data Matrix barcode consists of black and white modules arranged in either a square or rectangular pattern as shown in Figure 1. The encoded data bits that are mapped to a region of black and white modules (or cells) is called a data region. For more details on different types of encoding schemes supported by 2D Data Matrix barcodes, refer [2].

The data region is surrounded by a finder pattern (the bottom and left hand sides of finder pattern contain only dark modules, whereas the top and right hand sides of finder pattern are comprised of alternative white and dark modules). The Data Matrix 2D barcode allows multiple data regions separated by the alignment patterns to hold more data information.

There are two versions of Data Matrix, one is based on the cyclic redundancy check (CRC) and convolutional error correction, and the other is based on Reed-Solomon (RS) error correction. With respect to scanning, reading, and extracting the data bits, there is no difference between CRC-based and RS-based Data Matrix decoding.

After extracting the data bits, the CRC-based decoding follows one path and the RS-based decoding follows another path, as the interleaving and error correction methods are different for the two cases.

Figure 2: Block diagram of 2D barcode scanner and processing DSP core

Here we consider the emerging RS code-based 2D Data Matrix barcode decoding on a low footprint Blackfin processor. The block diagram of a 2D barcode scanner connected to the DSP processor through the PPI-DMA channel is shown in Figure 2, above .

Barcode Implementation on Low Footprint DSPs
A sensor scans the barcode and transfers the pixel data to the DSP through the parallel port interface (PPI). The DSP processor then processes the image pixels and extracts the data bits that correspond to dark and white modules of the data region and then performs error correction. The procedure for extracting the data bits from a particular data region of scanned 2D barcode is described with the flow chart diagram shown in Figure 3 below .

Figure 3: Flow chart diagram for extracting data bits from 2D Data matrix symbol

We treat the 2D Data Matrix barcode as an image of size M x N (usually it is a QVGA or VGA image) and process it. The camera's CMOS sensor captures the image and transfers the image pixels to the DSP for processing.

Now, the question is how much memory is needed to hold the image during the processing? For example, in the case of VGA (i.e. 640×480), we require about 300 kB of data memory to hold the captured image. The footprint of the processor core depends on the amount of memory it has on it.

Especially in the case of Level 1 (L1) high speed memory which occupies more silicon space and has a higher overall cost. For this reason, most processors used are comprised of very limited L1 memory.

On the other hand, the level 2 (L2) or level 3 (L3) memory usually have a large capacity, occupy less space, and cost less. However, they are slow and require DMA to transfer data to/from the processor's working memory (L1).

Following we discuss the Data Matrix 2D barcode implementation on two different processors in the Blackfin family, one with 16 kB of L1 along with huge L2/L3 memory and the other is with only 16 kB of L1 memory.

For the processor with L2 or L3 memory, the captured image is transferred to L2 through DMA and the PPI interface. The image is then processed for extracting the data bits from 2D barcode by bringing small amounts of image pixels from L2 to L1 at a time. In this case, we use another DMA to transfer the data to/from L1 from/to L2 and the overall decoding is simple and less complex.

On the other hand, if only a small amount of L1 memory is available and no L2/L3 memory is present, then the problem is really tricky. In this case, we scan more than once the same barcode and transfer the region of interest (ROI) to L1 memory for processing with the proper programming of the PPI-DMA channel.

Though this system is complex to program, its cost and footprint is less when compared to the previous example. Next, we will discuss the techniques to decode 2D Data Matrix barcode using the two processor examples above.

Implementation With L2 Memory
In this case, the scanned total image is read to the L2 memory through the PPI-DMA channel and the image is processed by accessing portions of the image from L2, using another Memory-DMA. This is illustrated in Figure 4 (a) below .

Figure 4: 2D barcode decoding on low footprint Blackfin, (a) with L2/L3 and L1 memory and, (b) with only L1 memory

Using an OmniVision CMOS VGA sensor [3], we get row-by-row pixel data along with control signals, HREF (horizontal reference output), VSYNC (vertical sync output) and PCLK (pixel clock output). The PPI-DMA channel reads the pixels at a 27 MHz clock rate to L2 memory. In this case, the DMA programming is simplified, as we are reading the entire image in a single scan.

We basically follow the flow chart shown in Figure 3 earlier to extract the data bits from the modules of Data Matrix barcode. If any orientation is present in the scanned image, we can correct the orientation and the offset, as we have a full image available in the L2 memory.

For now, we assume that the image is properly scanned without any orientation and offsets. First, we get the top few rows and right few columns of the image belonging to finder pattern of Data Matrix barcode to L1 memory from L2.

After measuring the average width and height of modules of finder pattern, we mark the mid-point positions for all top and right modules of finder pattern and store the x and y coordinate values of mid-point pixel positions in memory for future purposes.

Without L2 or L3 Memory
In the absence of L2/L3 memory, we read the image directly to the L1 memory. As L1 memory size is very limited, we cannot read the entire image to L1 at one time directly. This is illustrated in Figure 4 (b) above .

In this case, we scan the image more than once for the barcode decoding. Using the PPI delay and PPI count registers, few rows and columns of the top and right hand side finder pattern module pixels are read to the L1 memory in one scan.

The DMA programming is more involved in this case as we need to get the selected image pixels through the PPI-DMA channel to L1 memory from the scanner output. We find the size and midpoint position coordinates of finder pattern modules and store in the memory for future purpose.

In the case of images with slight orientation or offsets, we bring more than one row of pixels to correct the orientation or offset. Here, we process the images on an individual row basis as we don't have the full image at hand.

Data Bits Extraction from Data Matrix Barcode
We follow the second half of flow chart (shown in Figure 3 earlier ) to extract the bits information from Data Matrix barcode black and white modules.

Here, we assume that the Data Matrix contains a single data region with black and white modules. As we know, with the midpoint position coordinates of finder pattern modules, we can easily obtain all the modules center points as the intersection of horizontal lines (perpendicular to left hand side finder pattern).

It also passes through the finder pattern right hand side modules' mid-point positions and vertical lines (perpendicular to bottom side finder pattern and passing through the finder pattern top side modules' mid-point positions). We cannot draw all these lines to mark the points of intersection as we don't have the entire image in the L1 memory.

However, we can get the points of intersection by scanning one row at a time (using the finder pattern right hand side module midpoint y-coordinate as the row index), and comparing the current row column index with the finder pattern top side module mid-point x-coordinate.

If both are the same, then that is the point of intersection, otherwise we continue scanning the row. Using this process, we scan for the points of intersection in a module, and find the value of the pixel at that position.

If the pixel value is greater than 128 (i.e. light color), we decode the bit as '0', or if pixel value is less than 128, we decode the bit as '1'. In the same way, we can extract all the bits of the Data Matrix barcode data region.

For the processor with L2 memory, we move the pixel row corresponding to the finder pattern right hand side module midpoint y-coordinate to L1 memory from L2. We always move the next pixel row using DMA when we processing the current pixel row.

But, in the case of processor without L2 memory, we must perform the data extraction in real time. By the time the PPI-DMA fills the next row of data in L1-memory, we must finish the processing (basically extracting the data bits) of the current row.

2D De-interleaving
Data Matrix barcode uses 2D interleaving of the data bits. After extracting the bits from modules of the data region, we perform de-interleaving to obtain the data bits of the error correction codeword. For more details on 2D interleaving of data bits, refer [2].

We perform de-interleaving using the pre-computed look-up tables. Since the Data Matrix barcode supports various sizes of data regions, the de-interleaving look-up tables size and table elements also vary. It is not possible to store the look-up tables for all sizes on a low footprint processor.

However, if the data matrix size is known in advance for a given application, we store only that particular de-interleaving look-up table. After de-interleaving, the bits are packed into bytes to form the codeword input to the RS decoder.

Barcode Error Correction
The emerging ECC-200 type Data Matrix barcode uses RS (N, K) codes for correcting errors and erasures in the de-interleaved bits. The RS (N, K) code can correct up to (N-K)/2 errors or up to (N-K) erasures (if no errors present). The Galois field used in this application is GF(28).

The Data Matrix barcode uses different RS codeword lengths for different data region sizes. For example, a 14×14 size data region barcode uses RS(24, 12) code for error correction, whereas the 16×16 size data region barcode uses RS(32, 18) code. Depending on the size of data region, the complexity of RS decoder varies. As the length of the RS codeword increases, the memory required to store all RS decoder working buffers also increases.

To efficiently implement an RS decoder, we use look-up tables to perform Galois field arithmetic. The same Galois field log and antilog look-up tables are used for decoding of all RS codeword lengths, as the resulting field elements also belong to GF(28). We require about 2 kB of L1 memory to store both log and antilog look-up tables.

Data Matrix Barcode Decoding Complexity
There are two parts in decoding the 2D barcode: 1) image processing and 2) barcode decoding. If the captured image is not properly aligned to the decoding region, then we may need to perform image rotation, offset correct, etc. to get proper alignment of the image to the decoding region.

In this case, the complexity of image processing step is more when compared to actual barcode decoding. In this article, we assumed that the image is properly aligned with the decoding region.

The decoding complexity (in terms of cycles and memory) of Data Matrix barcode depends on the data symbol size. If the data symbol size is larger and contains multiple larger data regions per symbol, then we require more memory to hold few image row pixels and to hold the RS working buffers. The amount of data needed to be processed per unit time also increases with the data region size.

In the case of a VGA image with one 16×16 data region per Data Matrix barcode symbol, we require about 6 kB data memory and 4 kB program memory of the Blackfin. Approximate cycle counts to run individual blocks on the BF53x core are given below:

Modules size and count: 7200
Data bits extraction: 2000 cycles
De-interleave and Packing: 600
RS Decoding: 7000 cycles

Conclusion
The decoding of Data Matrix 2D barcode on the low footprint Blackfin processor is discussed. Different approaches to decode 2D barcode with and without high latency L2 memory are explained. The complexity of RS-based Data Matrix 2D barcode decoding is analyzed, and the memory and cycle counts required to decode a single 16×16 data symbol present in a VGA image on BF53x processor is estimated.

Hazarathaiah Malepati joined Analog Devices in 2003, where he is currently working on embedded algorithm software development for the Blackfin family of processors. From 2000 to 2003, he worked as a research engineer in HIRP (HFCL-IISc research program), Bangalore, India. He has a masters in industrial electronics from KREC, Surathkal.

Yosi Stein serves as DSP principal system architect/advanced technologies manager, working in the Digital Media Technology Center on the development of broadband communication and image compression enhanced instruction set for Analog Devices' fixed-point DSP family. Yosi holds a B.S.c in electrical engineering from Technion–Israel Institute of Technology.

References
[1] ADSP-BF53x, “Blackfin DSP Hardware Reference Manual”, 2009.
[2] ISO/IEC, “Information Technology-Automatic Identification and Data Capture Techniques-Data Matrix Bar code Symbology Specification”, Sep 2006.
[3] OmniVision, “CMOS VGA CameraChip Sensor with OmniPixel3-HS Technology”, Product Specification Data Sheet, Jul 2008.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.