基于改进CORDIC算法的QR码快速检测硬件实现方法*

陈荣军 ，于永兴 ，钟秀媚 ，谢舜道 ，赵慧民 ，谭洪舟

(1.广东技术师范大学 计算机科学学院，广东 广州 510665；2.中山大学 电子与信息工程学院，广东 广州 510006)

0 引言

随着物联网技术的不断发展，二维条码作为物联网的入口有了越来越多的应用场景。二维条码具有信息密度大、纠错能力强、可表示多种信息、可加密及制作成本低等优点[1]，目前常用的二维条码有QR码、Data Matrix码、PDF417码等，其中QR码(快速响应码)具有高密度、高可靠性以及可全方位快速识别等特点，因此广泛应用于生产流通、交通物流、质量追踪、电子商务等领域[2]。

在二维条码研究领域，国内外学者提出了多种扫描译码方法[3-7]，其中最常用的二维码扫描方法是通过摄像头获取图像缓存到存储器，再由CPU或DSP读取图像数据进行图像处理和译码，这种通过软件进行二维码扫描译码的方法需要占用总线时间长、译码速度慢，不适用于快速二维码的识别应用中。针对高速运动过程中二维条码识别，文献[3]提出了一种基于Halcon的XLD边缘检测识码方法，该方法虽然提高了条码定位过程的速度和准确性；但是对检测设备和检测环境有一定的要求。文献[4]设计了一种基于DM642的嵌入式平台，用于QR码的检测，但识别系统的检测过程较为复杂，并且需要额外的视频解码芯片，识别结果不能及时在PC端显示。文献[5]提出了一种基于游程编码的QR码快速检测方法，但算法的检测过程较为繁琐，只能在毫秒级的时间内定位到QR码，实时性还有待提升，并且在低分辨率QR码的检测定位中表现不好。在文献[6]中，提出了一种基于面向梯度直方图(HOG)特征和支持向量机(SVM)分类器相结合的QR码识别算法，但算法的复杂性较高，程序运行需要耗费较多的资源，因此在测试设备上仿真时，QR码的检测过程要超过1 s。文献[7]中提出了一种基于Hough变换的矩码检测算法，该方法计算成本低、精度高，但QR码检测成功率与参数设置有关，且算法只是对拍摄到的整幅图像进行边缘提取，而没有将检测出的QR码进行校正。

为了解决QR码检测译码速度慢、占用资源多等问题，本文基于FPGA和改进型CORDIC算法提出了一种纯硬件实现的QR码快速定位和校正提取的方法，该方法采用纯硬件实现，直接对获取的图像数据流进行图像预处理和快速QR码定位，可以极大地提高QR码检测速率，并且由于该方法采用CORDIC算法对QR码图像进行旋转校正和提取，通过移位和加法器代替乘/除法器，因此可以大大减少硬件资源。

1 CORDIC算法的改进

1.1 CORDIC算法基本原理

CORDIC算法最早是1959年由VOLDER J E提出[8]，非常适用于FPGA实现[9]。CORDIC算法的基本思想是通过一组预先定义的基本角度集的逐次旋转来逼近期望角度，其原理图如图1所示。

图1 CORDIC算法原理

在图1中，平面内的初始向量q0(x0，y0)，逆时针旋转β 角度后得到向量qn(x0，y0)，则q0与qn的关系可以写成式(1)的矩阵形式：

假设β 是由连续n个满足级数收敛的基本角度αi通过旋转叠加而成的，即：

其中，ρi=1表示逆时针旋转，ρi=-1表示顺时针旋转。由于在计算机中，角度计算过程都是按照二进制的形式，因此每次旋转的基本角度可以取αi=arctan(2-i)，i=0，1，2，3，4，…，将式(2)代入式(1)可得：

环形坐标旋转的CORDIC算法包括两种模式：旋转模式(Rotation Mode，RM)和矢量模式(Vector Mode，VM)，RM模式用于给定旋转角度值和向量长度求解相应的正余弦值，VM模式用于给定向量坐标求解向量长度及其与横坐标的夹角[10]。

1.2 改进CORDIC算法

传统的CORDIC算法只需要通过移位和加法操作即可以实现复杂函数的求解，硬件复杂度低，当迭代次数足够多时，可以达到较高的精度。级数收敛到99.88°[11]，故算法可表示的旋转角度范围为(-99.88°，99.88°)，不能覆盖到整个圆周(-180°，180°)，因此需要对其进行扩展[12]。

文献[13]提出了一种在传统CORDIC算法基础上增加两级初次迭代的改进措施，方法原理简单，易于实现，但由于增加了两级初次迭代，使资源耗费增加。文献[14]提出了一种新的基于CORDIC算法的反正切函数的FPGA计算方法，通过将算法的设计与FPGA设备的资源相适应的方式，节省了由于Z路径迭代运算引起的损耗，但电路面积和输出时延仍较大。

CORDIC算法的迭代次数与每次迭代的角度如表1所示。

由表1可知，CORDIC算法表示的范围与精度与迭代次数有关，当i减小时，αi增大，可表示的范围增大；当i增大时，迭代角度αi减小，其可表示的精度越高；特别地，当i=0时，对应的角度为45°，i增加时，arctanαi逐渐减小，由于180°-99.88°=80.12°，当i=-3时，α-3=82.875°＞80.12°，并且小于99.88°，因此可以增加一级i=-3以扩展旋转角度范围，且不会造成中间有无法逼近的角度，这是因为，即当第一次旋转82.875°后，可以由后面的迭代进行填充。

表1 级数收敛角度值

因此，设计采用一种在初始阶段增加一次角度为α-3=arctan(23)的迭代的改进方法，相比于其他的改进方法，只需要在传统算法基础上添加一级流水线，使得该模块能够表示的角度达到360°内的任意角。其原理简单直观，改进型CORDIC算法模块的流水线如图2所示。

图2 CORDIC改进算法流水线

2 QR码图像检测

QR码图像的检测过程主要包括QR码快速定位和校正提取两大部分。

QR码快速定位与校正提取的系统框图如图3所示。其中QR码快速定位是在传输过程中直接对获取的图像数据流进行预处理和快速定位；然后采用改进型CORDIC算法对QR码图像进行旋转校正和提取。

图3 QR码快速定位与校正提取

系统原理如图4所示，在获取图像数据流的过程中对QR码进行行列扫描，获取到黑白条纹满足1:1:3:1:1的点的位置信息，在一帧图像的场同步期间对扫描点进行筛选，得到QR码的位置信息，若筛选完成，则在定位到QR码后进行校正提取。

图4 QR码快速定位与提取校正原理

2.1 QR码快速定位方法设计

QR码的快速定位即是找出其位置探测图形的中心点坐标及其尺寸信息。QR码定位算法有很多：基于局部特征的定位方法[15]、基于最小二乘的定位方法[16]、基于边缘检测的定位方法[17]、基于凸包及最小面积外接矩形定位方法[18]等，这些检测方法都较为复杂，不适于通过硬件实现。本设计采用的是基于QR码图像特征的快速定位方法，该方法识别率高，算法简单，易于实现。

如图5所示，QR码是由深色、浅色正方形模块排列成的一个正方形阵列，其中位置探测图形位于符号的3个边角，用于快速定位QR码在原图像中的位置，每个位置探测图形由深色、浅色模块按照1:1:3:1:1交替排列而成，该比例具有水平不变性[19]。

图5 QR码及其位置探测图形

QR码快速定位的原理如图6所示。首先从摄像头中获取图像数据流，对该原始图像数据流进行格式转换，将每个像素点的RGB转换为灰度值，并将灰度化后的图像数据流传输到下一级二值化模块。采用基于双线性插值的局部二值化方法进行图像二值化，计算出每帧图像的二值化阈值，通过插值对下一帧图像的每个像素点的灰度值进行判断，得到二值化后的0/1数据流。由于该二值化方法是采用前一帧图像的阈值来判断下一帧图像的灰度值，因此要求相邻两帧图像之间的变化不能太大。二值化后的0/1序列一方面输入到行扫描模块中，检测黑白条纹满足1:1:3:1:1的线段；另一方面顺序存入BUFFER中，用于将逐行输入的数据流转换成逐列输出到列扫描模块和用于提取二维码图像方块。当一帧二值图像数据流到来时，进行逐行扫描，检测1:1:3:1:1的线段，同时对存入BUFFER中的前一帧图像数据按列输出进行逐列扫描。可以看出，行/列扫描是分别针对前后两帧数据进行检测得到的结果，因此这也是必须基于获取的图像前后两帧变化不大的情况才成立的。对行列扫描得到的两组黑白条纹满足1:1:3:1:1的线段坐标及其对应的黑白条纹平均单位宽度进行比对，如果行扫描得到的某个点的坐标和宽度与列扫描得到的某个点的坐标和宽度在允许范围内相等，则认为该点行列都满足1:1:3:1:1关系。由于实际获取的图像可能会存在离焦模糊、上几级模块中设置了允许误差等原因，导致扫描得到的点分散在周围，因此需要将这些分散的邻近点合并成一个点，再对合并后的点进行检测，判断出满足等腰直角关系的3个点即为QR码的3个位置探测图形中心点。

图6 QR码快速定位流程图

2.2 QR码校正提取方法设计

由于在现实生活中，摄像头获取到的二维码图像大多不是完全端正的，具有一定的旋转偏角，因此需要对二维码图像进行旋转校正。本设计采用改进型CORDIC算法对QR码图像进行旋转校正和提取。

首先根据QR码快速定位模块获取到QR码3个位置探测图形的中心点坐标q1(x1，y1)、q2(x2，y2)、q3(x3，y3)，然后将左上角和右上角位置探测图形中心点构成的向量q1q2(x2-x1，y2-y1)输入到VM模式下的CORDIC模块中，可以得到QR码的旋转角度β 和长度为l的向量q1q2。接着以左上角位置探测图形的中心为坐标原点，将QR码旋转校正后的每个点的坐标(xi，yi)和旋转角度β 输入到RM模式下的CORDIC模块中，可以得到QR码旋转校正后的每个点所对应的原图像坐标(xo，yo)，从缓冲中读取出坐标(xo，yo)对应的值0/1存储到相应存储空间中即可提取出旋转校正后的QR码图像，原理如图7所示。

图7 QR码图像旋转校正

CORDIC算法可以通过设计成流水线的形式实现，对于N级流水线只有在其运作的第一轮会有N个时钟周期的延迟，而后每个时钟周期可以输出一个有效值。本文将CORDIC算法运用于求图像旋转角度和图像旋转，因此这里需要两次使用到CORDIC模块，但图像旋转前必须先进行旋转角度的确定，因此总共会有2N个时钟周期的延时。由于CORDIC算法的VM模式和RM模式只存在每次迭代的符号判断的差别，因此两次的CORDIC运算可以通过同一条流水线实现，这样可以节省一半的资源。

采集到的图像分辨率的大小为640×480，当CORDIC算法的迭代次数为9级(包括i=-3一级)时，旋转精度可达到0.4476°，能满足实际应用的需要[20]，迭代次数确定后，此时校正因子也确定：K=1.992 4×10-4。在流水线的最后一级进行校正相比于在每一级校正不仅可以节约资源，而且可以提高精度，这是因为每一级的校正因子都小于1，导致每次校正后的结果都会变小，由于寄存器中的数位是有限的，每次校正后其精度会变小。校正采用移位和加法操作代替乘法器，可以进一步节省资源。

3 实验仿真

在Quartus II 10.0环境下，采用Altera公司提供的Cyclone IVE FPGA芯片和500万像素的MT9P001摄像头，将设计的模块进行综合编译，生成下载文件，配置到实验板上进行验证，验证平台使用的是友晶公司提供的DE2_115实验板。

3.1 实验内容与过程

本设计主要包括了QR码快速定位和QR码的校正提取两大部分。其中QR码的快速定位包括以下几个模块：图像获取、图像灰度化、二值化等预处理；QR码校正与提取部分采用CORDIC算法对QR码图像进行旋转校正和提取。

首先在PC上通过MATLAB对该设计进行仿真，验证算法的可行性和有效性。其后，采用Verilog/VHDL硬件描述语言进行硬件设计，并对设计进行ModelSim仿真和实际下载验证。

3.2 实验结果

通过实验测试可知，QR码快速定位与校正提取模块消耗的资源为3 272个逻辑单元，整个模块的最高时钟频率可以达到267.95 MHz，该系统可以实时地检测出QR码的3个位置探测图形的中心点坐标并显示在屏幕上，使QR码经过旋转校正后，可以在微秒级的时间内提取出QR码图形，如图8所示。

图8 实验结果

验证结果表明，该设计能实时地跟踪定位到QR码并将其校正提取出来。

4 结论

相比于采用软件实现的QR码定位校正的系统而言，本文设计的实时的QR码定位及校正的硬件实现方法可以极快速准确地定位并截取出QR码图像方块，为后续的译码环节提供方便，大大提高了QR码扫描译码的速度；同时采用改进型CORDIC算法实现了图像的旋转校正，极大地节省了硬件资源，提高了系统的时钟频率。而且系统还可以进一步地扩展，添加对其他类型的码的检测定位等。