产品设计原理：在小尺寸DSP上实 2D条形码解码
2011-08-03
作者：Hazarathaiah Malepati,Yosi Stein
条形码一般被用于将关键的字母数字信息转换为数字系统能够扫描和读取的符号信息，而无需每次都要将信息录入数字系统。
1D（一维）条形码只能对数字数据进行编码，在过去二十年中主要用于产品运输和追踪、系统安全、超市等场合。使用 2D（二维）条形码，数据在水平和垂直方向被编码为 2D 符号，如下图 1 所示。
2D 符号所能包含的数据量远大于 1D 符号。2D 条形码解决方案可比传统 1D 条形码提供更大的信息密度，特别是对于那些需要对精密信息而不是简单的码信息进行编码的应用。
2D 条形码技术的一些应用包括产品标签、产品信息追踪和检验、移动安全、出入境检查服务、医疗保健和电子商务等。
图 1：2D 条形码示例
如今存在很多 2D 条形码算法，这催生出采用不同条形码技术的一系列应用。一般来说，有两种类型的 2D 条形码：1) 堆叠式 2D 条形码，例如 PDF417 和 Code 49，2) 矩阵式条形码，例如 QR 码和数据矩阵。在这篇文章中，我们仅限于讨论数据矩阵式条形码技术[2]。
2D 数据矩阵式条形码技术
2D 数据矩阵式条形码包括在正方形或长方形中排列的黑色和白色模块，如图 1 所示。编码数据位映射到黑色和白色模块(或单元)组成的区域，称为数据区域。关于 2D 数据矩阵式条形码所支持的不同类型的编码方案的详细信息，请参见参考文献[2]。
数据区域由定位图形包围（定位图形的底部和左侧只包含黑色模块，而定位图形的上部和右侧由交替的白色和黑色模块组成）。数据矩阵 2D 条形码支持由排位图形分隔的多个数据区域，从而能容纳更多数据信息。
有两种版本的数据矩阵，一种是基于循环冗余校验(CRC)和卷积纠错，另一种是基于里德所罗门(RS)纠错。对于扫描、读取和提取数据位，基于 CRC 与基于 RS 的数据矩阵解码没有区别。提取数据位之后，基于 CRC 的解码与基于 RS 的解码路径不同，因为它们的交织和纠错方法不同。
图 2：2D 条形码扫描器框图和 DSP 处理内核
这里我们考虑在小尺寸 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 数据符号进行解码所需的存储器和周期数。
本站内容除特别声明的原创文章之外，转载内容只为传递更多信息，并不代表本网站赞同其观点。转载的所有的文章、图片、音/视频文件等资料的版权归版权所有权人所有。本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如涉及作品内容、版权和其它问题，请及时通过电子邮件或电话通知我们，以便迅速采取适当措施，避免给双方造成不必要的经济损失。联系电话：010-82306118；邮箱：aet@chinaaet.com。