在线工博会

在小尺寸DSP上实现2D条形码解码
Hazarathaiah Malepati
为节省流量,手机版未显示文章中的图片,请点击此处浏览网页版
条形码一般被用于将关键的字母数字信息转换为数字系统能够扫描和读取的符号信息,而无需每次都要将信息录入数字系统。
1D(一维)条形码只能对数字数据进行编码,在过去二十年中主要用于产品运输和追踪、系统安全、超市等场合。使用2D(二维)条形码,数据在水平和垂直方向被编码为2D符号,如下图1所示。

(图片)

图1:2D条形码示例

2D符号所能包含的数据量远大于1D符号。2D条形码解决方案可比传统1D条形码提供更大的信息密度,特别是对于那些需要对精密信息而不是简单的码信息进行编码的应用。
2D条形码技术的一些应用包括产品标签、产品信息追踪和检验、移动安全、出入境检查服务、医疗保健和电子商务等。
如今存在很多2D条形码算法,这催生出采用不同条形码技术的一系列应用。一般来说,有两种类型的2D条形码:1) 堆叠式2D条形码,例如PDF417和Code 49,2) 矩阵式条形码,例如QR码和数据矩阵。在这篇文章中,我们仅限于讨论数据矩阵式条形码技术[2]。
2D数据矩阵式条形码技术
2D数据矩阵式条形码包括在正方形或长方形中排列的黑色和白色模块,如图1所示。编码数据位映射到黑色和白色模块(或单元)组成的区域,称为数据区域。关于2D数据矩阵式条形码所支持的不同类型的编码方案的详细信息,请参见参考文献[2]。
数据区域由定位图形包围(定位图形的底部和左侧只包含黑色模块,而定位图形的上部和右侧由交替的白色和黑色模块组成)。数据矩阵2D条形码支持由排位图形分隔的多个数据区域,从而能容纳更多数据信息。
有两种版本的数据矩阵,一种是基于循环冗余校验(CRC)和卷积纠错,另一种是基于里德所罗门(RS)纠错。对于扫描、读取和提取数据位,基于CRC与基于RS的数据矩阵解码没有区别。

(图片)

图2:2D条形码扫描器框图和DSP处理内核

提取数据位之后,基于CRC的解码与基于RS的解码路径不同,因为它们的交织和纠错方法不同。
这里我们考虑在小尺寸Blackfin处理器上对新兴的基于RS码的2D数据矩阵式条形码进行解码。通过PPI-DMA通道连接到DSP处理器的2D条形码扫描器的框图如上面图2所示。
在小尺寸DSP上实现条形码
传感器对条形码进行扫描并将像素数据通过并行端口接口(PPI)传输给DSP。之后,DSP处理器处理图像像素并提取数据区域中黑色和白色模块对应的数据位,然后进行纠错。从扫描的2D条形码的特定数据区域提取数据位的过程如下面图3所示的流程图。

(图片)

图3:从2D数据矩阵符号提取数据位的流程图

我们将2D数据矩阵式条形码看做大小为M x N的图像(通常是QVGA或VGA图像)并进行处理。相机的CMOS传感器捕获图像并将图像像素传输给DSP进行处理。
现在的问题是,需要多大的存储器来保存处理过程中的图像?例如,以VGA(即640x480)为例,我们需要大约300 kB的数据存储器来保存捕获到的图像。处理器内核的尺寸取决于其包含的存储器的数量。
特别是L1高速存储器,它占用更多的硅面积,总成本也更高。因此,大多数处理器包含非常有限的L1存储器。
另一方面,L2或L3存储器通常有较大的容量,占用较小的面积,成本也较低。然而,它们速度较慢,需要通过DMA与处理器的工作存储器(L1)进行数据传输。
接下来我们将讨论用Blackfin系列的两款不同处理器实现数据矩阵2D条形码在,其中一款具有16 kB的L1和较大L2/L3存储器,另一款只有16 kB的L1存储器。
对于带有L2和L3存储器的处理器,捕获的图像通过DMA和PPI接口传输到L2存储器。然后通过将少量图像像素同时从L2移动到L1存储器,来对2D条形码中提取的数据位进行处理。在这种情况下,我们使用另一个DMA进行L1和L2之间的数据传输,整体解码很简单也不复杂。
在另一方面,如果仅有少量的L1存储器,并且没有L2/L3存储器,那么问题就相当棘手。在这种情况下,我们对同样的条形码要进行更多的扫描,并将目标区域(ROI)通过适当设置的PPI-DMA通道传输到L1存储器进行处理。
虽然这个系统设置起来很复杂,但其成本和尺寸与前一个例子相比要小。接下来,我们将讨论使用上面提到的两个处理器实例对2D数据矩阵式条形码进行解码的技术。
用L2存储器实施
在这种情况下,经扫描的所有图像通过PPI-DMA通道被读入L2存储器,采用另一个存储器DMA通过访问L2中的部分图像对其进行处理。如下图4(a)所示。

(图片)

图4:用小尺寸Blackfin处理器进行2D条形码解码
(a)具有L2/L3和L1存储器,(b)仅有L1存储器。

采用OmniVision CMOS VGA传感器[3],我们逐行获得像素数据和控制信号、HREF(水平基准输出)、VSYNC(垂直同步输出)和PCLK(像素时钟输出)。PPI-DMA通道以27 MHz时钟速率将像素读入L2存储器。在这种情况下,DMA设置很简单,因为我们在单次扫描中读取整个图像。
我们基本上遵循上面图3所示的流程图来从数据矩阵式条形码模块中提取数据位。如果在扫描的图像中存在任何方向,我们能够纠正方向和偏差,因为我们在L2存储器中有全部图像。
现在,我们假设图像被正确扫描,没有任何方向和偏差。首先,我们将数据矩阵式条形码定位图形的顶部几行和右边几列从L2移入L1存储器。
在测量定位图形中模块的平均高度和宽度后,我们为定位图形所有顶部和右边模块的中点做标记,将中点像素位置的x和y坐标值存入存储器,留作以后使用。
无L2或L3存储器
无L2/L3存储器时,我们直接将图像读入L1存储器。由于L1存储器空间有限,我们一次直接读取整个图像到L1存储器中。如上图4(b)所示。
在这种情况下,进行条形码解码时我们要多次扫描图像。使用PPI延迟和PPI计数寄存器,定位图形模块像素的顶部几行和右边几列在一次扫描中被读入L1存储器。
在这种情况下需要更多地DMA编程,因为我们需要从扫描器输出将所选的图像像素通过PPI-DMA通道读入L1存储器。我们找到定位图形模块的大小及其中点位置坐标,并将其存储起来为将来使用。
在图像有细微方向或偏离时,我们读取多行像素来纠正方向或偏差。这里,我们逐行进行图像处理,因为我们没有完整的图像。
从数据矩阵式条形码中提取数据位
我们遵循下半部分流程图(如之前图3所示),从数据矩阵式条形码黑色和白色模块中提取位信息。
这里,我们假设数据矩阵包含有黑色和白色模块组成的单一数据区域。我们知道,有了定位图形模块的中点位置坐标,我们能很容易地获得所有模块中心点作为相交叉的水平线(与左侧定位图形垂直)。
它也通过定位图形右侧模块的中点位置和垂直线(与定位图形下边垂直并通过定位图形的上边模块的中点位置)。我们不能画出所有这些线来标识交叉点,因为我们在L1存储器中没有完整的图像。
然而,我们可以通过一次扫描一行的方式来获得交叉点(使用定位图形右侧模块中点的y坐标作为行索引),将当前行列索引与定位图形上边模块中点x坐标进行比较。
如果两者相同,那么就是交叉点,否则我们继续扫描这一行。采用这一过程,我们扫描模块的交叉点,并找到该位置像素的值。
如果像素值大于128(即浅色),我们将该位解码为0,或者如果像素值小于128,我们将该位解码为1。采用同样的方式,我们能提取数据矩阵式条形码数据区域的所有位。
对于具有L2存储器的处理器,我们将与定位图形右侧模块中点y坐标对应的像素行从L2移入L1存储器。当我们正在处理当前像素行时,使用DMA来移动下一像素行。
但是,在使用无L2存储器的处理器时,我们必须进行实时数据提取。此时,PPI-DMA将下一行数据填入L1存储器,我们必须完成对当前行的处理(进行基本的数据位提取)。
2D解交织
据矩阵式条形码使用2D交织的数据位。从数据区域模块中提取数据位后,我们执行解交织来获得纠错码字的数据位。关于2D数据位交织的详细信息,请参见参考文献[2]。
我们用预计算查找表来进行解交织。由于数据矩阵式条形码支持不同尺寸的数据区域,因此解交错查找表的大小和表单元也不同。不可能在小尺寸处理器中保存所有尺寸的查找表。
然而,如果在预先给定的应用中数据矩阵大小是已知的,我们只需要存储特定解交织查找表。解交织后,数据位按字节格式形成码字,输入RS解码器。
条形码纠错
新兴的ECC-200型数据矩阵式条形码使用RS (N, K)码来纠正解交织位的错误和遗漏。 RS (N, K)码可以纠正最多(N-K)/2个错误或者最多(N-K)个遗漏(如果不存在错误)。在这个应用中使用的Galois域是GF(28)。
对于不同数据区域大小,数据矩阵式条形码使用不同的RS码字长度。例如,14x14大小的数据区域条形码使用RS(24, 12)码来纠错,16x16大小的数据区域条形码使用RS(32, 18)码。RS解码器的复杂度取决于数据区域的大小。随着RS码字长度的增加,存储器需要存储的所有RS解码工作缓冲区也要增加。
为了高效地实施RS解码器,我们使用查找表来进行Galois域计算。对所有RS码字长度进行解码时使用相同的Galois域对数和反对数查找表,因此域单元也属于GF(28)。我们需要大约2 kB的L1存储器来存储对数和反对数查找表。
数据矩阵式条形码解码复杂度
2D条形码解码有两个部分:1) 图像处理,2)条形码解码。如果捕捉的图像与解码区域没有适当对齐,我们可能需要进行图像旋转、偏差纠正等,来使图像与解码区域对齐。
在这种情况下,图像处理阶段的复杂度比实际条形码解码要大。在这篇文章中,我们假设图像与解码区域是对齐的。
数据矩阵式条形码的解码复杂度(在周期和存储器方面)取决于数据符号的大小。如果数据符号尺寸较大,每个符号中包含多个较大的数据区域,那么我们需要更多的存储器来保存图像的行像素和RS工作缓冲。每单位时间需要处理的数据量也随着数据区域的尺寸而增加。
以每个数据矩阵式条形码符号具有16x16数据区域的VGA图像为例,我们需要大约6kB数据存储器和4kB的Blackfin程序存储器。BF53x内核上运行单个模块的近似周期数如下:
模块尺寸和数量:7,200
数据位提取: 2,000个周期
解交织和封包:600
RS解码:7,000个周期
本文小结
本文讨论了在小尺寸Blackfin处理器上进行数据矩阵2D条形码解码。同时解释了使用或不使用高延迟L2存储器对2D条形码进行解码的不同方法。分析了基于RS的数据矩阵2D条形码解码的复杂度,并估算了使用BF53x处理器对VGA图像中单个16x16数据符号进行解码所需的存储器和周期数。
Hazarathaiah Malepati于2003年加入ADI公司,目前从事Blackfin系列处理器的嵌入式算法软件开发工作。2000年至2003年,他担任印度班加罗尔HIRP(HFCL-IISc研究计划)的研究工程师。他拥有印度KREC Surathkal工业电子硕士学位。
Yosi Stein担任DSP首席系统架构师兼高级技术经理,在数字媒体技术中心工作,负责为ADI定点DSP系列开发宽带通信和图像压缩增强指令集。他拥有以色列理工学院电气工程学士学位。
参考文献
[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. 10/12/2010


电脑版 客户端 关于我们
佳工机电网 - 机电行业首选网站