基于DM642的手机QR码检测与识别①

陈存弟,刘金清,施文灶,邓淑敏,周晓童,吴庆祥

(福建师范大学 光电与信息工程学院 医学光电科学与技术教育部重点实验室,福州 350007)

条码扫描枪是一种嵌入式平台二维码识别系统[1]产品,整体主要由摄像头与MCU组成,软件主要依靠图像处理技术与QR码解码标准来实现.QR码解码的解码标准已经固定不变,而由于摄像头获取的QR码图片,其周围环境复杂多变,还受电子元器件的影响导致图片中含有椒盐噪声,且倾斜角度与畸变程度的不确定性给2D条码的识别带来极大的挑战性,因此图像处理的运用是解决该问题的关键技术,同时这些关键技术是国内外学者研究的热点.

1 QR码的简介

QR(Quick Response)码是由日本的Denso-Wave公司发明,能存储的信息容量大,编码生成的输出码面积小,能全方位识读且识读速度高,可表示图像及多种文字信息,如中国汉字和日本汉字.QR码的结构如图1所示,主要由功能图形和编码区组成.其中功能图形主要用于QR码的定位,而编码区主要用于存储编码数据和纠错信息.位置探测图形由黑白黑三个矩形组成,横竖方向黑白间隔比例为 1：1：3：1：1,通常利用这个比例关系来定位QR码[2,3];定位图形由黑白交替的小模块组成,始于深色模块且终于深色模块,通常用于QR码的采样;校正图形由三个黑白矩形镶嵌组成,类似于位置探测图形,但横竖黑白间隔比例为1,通常用于QR码的定位与采样;编码区格式信息主要由格式信息、版本信息、数据和纠错码字组成,在解码前首先要获取格式信息和版本信息来确定QR码中存储的数据类型和纠错级别及其采用的掩膜图形,格式信息与版本信息均出现两次,因为这两块信息的正确获取是决定着解码正确的关键因素.QR码编码过程如图2所示.

图1 QR码结构图

QR码的解码过程即是编码流程的反向过程,由于解码过程中首先要获取格式信息和版本信息,而这两个信息又是基于QR采样得到的比特流来运算得到,故引入图像处理技术.

图2 QR码的编码流程图

2 QR码定位

2.1 基于位置探测图形定位QR码

传统的定位方法通常是基于位置探测图形的1：1：3：1：1 关系来定位 QR 码,如图 3(a)所示,这是基于位置探测图形的比例关系定位完全正确的结果,该图形只是稍微倾斜且透视效果不明显,所以定位结果较好,而图3(b),(c)均无法定位,图3(b)在水平方向上定位良好,但由于垂直方向受摄像头成像的原因,由原先的3D立体图形经投影投射成2D平面图像上,之间在投射的过程由于摄像头与QR图片有倾斜角而产生了透视效果,所以在图像平面上的二维码呈现梯形,与摄像头距离大的两个位置探测图形上下行之间距离被慢慢压缩得很小,所以导致垂直方向的比例关系没能定位到位置探测图形.图3(c)中的QR码倾斜趋近于45度且由于透视的原因导致定位失败.

图 3 定位结果 (上：灰度图,下：定位图)

2.2 基于轮廓提取的方法定位QR码

观察位置探测图形,可以发现是由3个镶嵌的并且宽度为一定比例的矩形组成,3个矩形边宽由外向内的比例关系为7：5：3;对QR码二值图取反后可以发现位置探测图形最外矩形框和最内的矩形框为深色,本文的定位算法正是根据这两个深色块的轮廓关系和轮廓之间的面积比例为49：9关系来达到准确定位.

2.2.1 图像预处理

图像传感器获取的图片经常带有椒盐噪声,而中值滤波是滤除该噪声的关键技术.本文的轮廓提取是基于二值图来获取,故需对灰度图二值化处理.由于QR码的拍摄环境复杂多变且易受光照影响,使用单一的阈值难以达到良好的分割效果,观察整个QR码可以发现其整体是由浅色模块和深色模块组成,所以采用局部阈值代替全局阈值二值化能达到预期的效果.尽管文献[4]应用改进的Niblack局部二值化算法能消除光照不均的图片并获得较好的结果,但具有局限性强,步骤复杂和分类不精确等缺点.本文同样是采用局部二值化的思想分割图像,首先对整幅图像分成多个小矩形,然后在每个小矩形中使用Otsu算法求出相应的阈值来分割图像.对分割后的图像取反处理,并进入轮廓提取步骤.

2.2.2 轮廓提取

目前轮廓提取[5,6]的方法有基于连通域的方法,基于形态学的开闭运算方法,也有基于Snake的主动轮廓线模型(Active Contour Model).本文轮廓提取有外轮廓和内轮廓的区分,并且将其组织成两层的层级,内轮廓也称为次轮廓.顶层是连通域区域的外围边界,而次轮廓是洞的内层边界.在QR码定位过程中,首先寻找具有两层轮廓关系的连通域C1,计算C1的最小矩形左上角坐标Ptl1和右下角坐标Pbr1.再在这个连通域内寻找只有顶层而没有次层的连通域C2,计算C2的最小矩形左上角坐标Ptl2和右下角坐标Pbr2,且满足公式(1),则初步确定C1和C2两块区域组合成的镶嵌区域为位置探测图形,接着统计C1和C2两个轮廓区域内含有的坐标点数作为面积A1和A2,且满足公式(2),则精确确定为位置探测图形.

定位结果如图4所示,图4(a)表示原图;图4(b)是中值滤波后的结果,原图中的椒盐噪声,即是散布在图像表面的黑点.已经消除干净;图4(c)是局部二值化后取反的结果,可以看出三个位置探测图形的黑白矩形与原来图形恰好相反,基于二值化取反后的图像获取内外两个矩形轮廓的嵌套关系,再根据两个轮廓的面积比例关系定位QR码,得到图4(d)的结果.

图4 QR码定位结果

3 QR码校正

3.1 逼近QR码边界

QR码校正是正确采样的关键步骤.本文获取的QR码的图片来自于扫码设备拍摄手机上的QR码,故得到的图片不存在扭曲的情况,而主要问题是图片产生倾斜与透视效果,解决这两个问题需要准确获取QR码的4个角点,通过逆透视算法和倾斜校正算法来校正二维码.通常校正二维码的方法主要基于形态学和Hough变换[7]的的方法,但是形态学与Hough变换方法需要运行时间过长且不好定性控制,也不利于嵌入式平台上的应用.本文寻找QR码的4个角点的方法是采用直线逼近四条边的方法,通过计算四条边的斜截式联立成方程组来求取4个角点.

QR码的3个位置探测图形定位正确后,根据公式(3)分别计算3个位置探测图形的中心坐标.通过欧拉公式计算每两个中心坐标的距离,并找出距离之差的绝对值最小的两条线所相交的中心确定为QR码左上角位置探测图形,设该图形的中心坐标为交叉点I1,剩下的两个中心点I2和I3分别是左下角和右上角位置探测图形的的中心坐标,根据公式(4)计算I2与I1,I3与I1的斜截式.

因为QR码在拍摄时可能产生360度旋转角,所以原来标准正向QR码的3个位置探测图形被不定向的旋转,本文规定中心坐标为的位置探测图形与I1的位置探测图形为同一竖向关系,规定中心坐标为I3的位置探测图形与的位置探测图形为同一横向关系.如图5(a)所示,可以用斜截式表示的直线来区分这个关系,若斜率L12.k<0,则说明I1与I2是同一竖向关系,若斜率L13.k≥0,则说明I1与I3属于横向关系,然后对L12平移到I3点并求出经过I3的斜截式L3(k,b),对L13平移到I2点并求出经过I2的斜截式L2(k,b).如图5(a)所示,根据公式(5),(6)计算二值化图像Fbw的水平差分图Fh和垂直差分图Fv.依据L13向左和向右遍历Fh找到位置探测图形I1和I3的最外部轮廓的左右点,分别用P1l,P1r,P3l,P3r表示遍历到的端点坐标;再依据L2遍历Fh找到位置探测图形I2的左右端点P21和P2r,同样的依据L12和L3遍历Fv位置探测图形I1,I2和I3的上下端点,分别用P1u,P1d,P2u,P2d,P3u和P3d表示.如图5(b)所示,接着用具有竖直关系的左端点求取经过左端点和右端点的直线,同样的具有横向关系的端点求取经过上端点和下端点的直线.至此,QR码的两条边界已经得到.

图5 位置探测图形边界端点连接图

上面的步骤处理完毕后,只要再找到QR码其余的两条边,便可以求解出四条边的相交点作为QR码的第四个角点.而QR码只有3个位置探测图形,所以无法再根据位置探测图形找到另外的两条边界线,本文采用直线逼近的方法来找到其余两条边界,基本思想是QR码在编码生成过程中,其周围会多出浅色的空白区,在二值化且取反后的图像中呈现黑色,而QR码二值化取反后凸显的白色块与黑色空白区有明显的边界,正是依据这个明显的边界,不断调整斜截式直线来逼近边界.具体过程如下,以图6所示的QR码为例,说明逼近过程,在代码实现过程中还应考虑不同角度拍摄下的QR码来做出相应的处理：

(1) 首先求得经过位置探测图形的QR码对角线Lc.根据前面求得的上下和左右直线可以求得交叉位置探测图形的的四个角点,再判断I2与I3连成的直线和I1位置探测图形的对角线的交点是否在QR码图形区域内来确定最终的QR码对角线.

(2) 求竖直方向经过点P3r且与L3平行的直线L4.平移L3直线,使其经过P3r点.

(3) 计算Lc与L4的交点Pc4,并统计在Fbw中Pc4到P3r线段的白像素个数.

① 如果统计到的白像素个数少于设定的阈值Tmin,则判断为L4向外偏离QR码的边界,此时应该向QR码的内部区域重新调整交点,直到白像素个数少于Tmin则停止调整并记下交点坐标Plr.

② 如果统计到的白像素个数多于设定的阈值Tmax,则判断为L4往内偏,此时应该向QR码的空白区域重新调整交点,直到白像素个数首次多于设定的Tmax则停止调整并记下交点坐标Plr.

求横向经过点P2d且与L2平行的直线L5.

(4) 平移L2直线,使其经过P2d点.

(5) 计 算Lc与L5的 交 点Pc5,并统计在Fbw中Pc5到P2d线段的白像素个数.类似于(3).

(6) 计算QR码四条外边界相交的四个角点.首先计 算 点Plr和P3r的斜 截 式,再计 算Pud和P2d的 斜截 式,以此作为逼近QR码的另外两条边界线.联系前面找到的横向边界线和竖向边界线,对找到的四条QR码边界线联立成方程组计算出相应的角点.设计算得到的四个角点为 {Ptl,Ptr,Pbl,Pbrl}.

本文设置的外偏阈值为40个像素,即一旦检测到斜截式经过的白色点数少于40,则说明该直线往外偏.内偏阈值为50个像素,即一旦斜截式经过的白点大于50则说明该直线是内偏.如图6所示,图6(a)显示的是步骤(1)找到QR码对角线的结果;图6(b)显示的是步骤(2)和(4)的结果,红线表示偏离QR码边界线的情况,一条往内偏,一条往外偏;图6(c)显示的是步骤(3)和(5)的结果,图6(d)显示的是4条边逼近结果图,并标出了QR码的4个角点.

图6 边界逼近与角点运算结果

3.2 逆透视变换与倾斜校正

在QR码识别中,图像处理技术的最终目标是正确采样 QR 码的深浅模块,分别用‘1’和‘0’表示.而在采样之前,扫描枪获取QR码图片总会出现不定程度的透视结果和倾斜结果,这就要求在采样前必须进行逆透视变换和倾斜校正处理.

3.2.1 逆透视变换

逆透视变换[6,8]实际上是将原来图像上的坐标映射到另一个图像的坐标上,同时原来坐标上的像素值也映射到另一个图像对应的坐标上.

透视变换过程中需要知道四个坐标点,经过联立方程组,求解出方程组中的系数,同样的逆透视变换也需要求出方程组中的系数.原图像中QR码的四个角点坐标为要将这四个角点坐标映射到宽为width,高为height的视平面上,而QR码是一个宽和高相等的正方形,所以QR码角点对应在视平面上的坐标为：

本文对二值化后的图像Ibw做逆透视变换,映射到视平面图像为Ip.根据公式(7)计算出映射的相关系数

展开(7)式得到8个线性方程组成的方程组,转换方程组为矩阵表达示(8),此时求解系数即是求出(8)式的未知解,本文使用列主元高斯消去法求解该线性方程组.

求解得到ci系数后,说明可以根据这些系数建立原图和目标图的坐标映射关系,即是目标图的每个坐标映射到原图像的坐标中,并复制原图像的像素值在目标图像中.所以还需要根据式(9)(10)计算目标图坐标映射到原图的坐标,像素值的对应采用双线性插值法.

逆透视变换后得到一个宽和高相等的图像,但是三个位置探测图形有可能不总分布在左上角,左下角,右上角,所以逆透视变换后的图像还需要进行旋转,旋转的角度有90度,180度和270度三种情况.逆透视变换和旋转校正的结果如图7所示：图7(a)是逼近QR码四条边的结果,通过四条边的斜截式计算出QR码在原图上的角点坐标;图7(b)是灰度图逆透视变换到另一个视平面上的灰度图像;图7(c)是对逆透视变换后的图像顺时针旋转180度校正后的图像.

图7 逆透视变换与旋转校正图

4 QR码采样

QR码图像采样是图像处理最后的步骤.一个完整的QR码图像由两种正方形的小模块组成,一种是代表‘1’的深色小模块,一种是代表‘0’的浅色小模块,而图像采样的实际意义是读取QR码上的深浅色小模块的‘10’值保存在一个二维数组中,以便于后面的解码.

本文的采样方法主要依据RQ码中定位图形的深浅小模块交替变化特性来建立采样网络,对得到的网络求每个小格的中心个像素均值,如果阈值大于140,说明该网格对应的小模块是浅色模块,对应的值用‘0’表示;如果阈值小于140,说明该网格对应的小模块是深色模块,对应的值用‘1’表示.本文的采样步骤如下：

(1) 二值化旋转后的灰度图像.为了避免光照亮度不均匀的情况,二值化依然是采用局部二值化的方法,对QR码图像划分成 2×2的四个子图,再对每个子图采用大津法二值化得到图像Ibw.

(2) 根据第3节找出的QR码位置探测图形的角点,计算Ibw中三个位置探测图形的平均宽度,并除以7,得到每个小模块的平均宽度pw.

(3) 遍历横向网格线.

① 首先定位到左上角位置探测图形的中间行并向右遍历有深浅跳变的边界则划竖线,中间比例宽度为3的正方形根据平均宽度划上3条竖线,直到扫描到这个位置探测图形的最右边界线,转向寻找位置探测图形右下角点向上的行作为遍历起点.

② 从这点开始,向右扫描每列遇到的深浅边界或者浅深边界,则在该列划上竖直线,直到遍历到右上角位置探测图形的边界,则转向①,直到的右边界.

(4) 遍历竖向网格线.

① 首先定位到左上角位置探测图形的中间列并向下遍历有深浅跳变的边界则划横线,中间比例宽度为3的正方形则根据划上3条横线,直到扫描到这个位置探测图形的最下边界线,转向寻找位置探测图形右下角点向左的列作为遍历起点.

② 从这点开始,向下扫描每行遇到的深浅边界或者浅深边界,则在该行划上横线,直到遍历到左下角位置探测图形的边界,则转向①,直到的下边界.

(5) 统计每个小网格的深浅值.由上到下,左到右遍历整个网格,计算每个网格中心个像素的均值,如果阈值大于140,则定义该网格值为‘0’;如果阈值小于140,则定义该网格 值为‘1’,遍历完成后得到整个QR码的二维矩阵.

结果如图8所示.左上角位置探测图形的右下角两个红点分别表示右下角向上行的右遍历起点和向左列的下遍历起点,右上角和左下角红点表示由该点开始向位置探测图形的中间点向右或向下遍历边界.QR码总共有40个版本,图8(a)(b)(c)分别是版本2,4和6.

图8 采样网格

5 基于DM642的QR码识别系统的设计

5.1 系统构成

硬件平台选用以DM642[9]为核心处理器的开发板,主要用到开发板外围器件有4路视频端口,256 M SDRAM能存储多达32帧图像,8-32位Flash,10-100 M以太网口,板上JTAG仿真接口.DM642是TI公司C6000系列高性能数字媒体处理器,时钟频率高达720 MHz,本文设置时钟频率为600 MHz,处理能力为4800 MIPS.开发环境是CCS2.2,编程语言是C/C++.

5.2 硬件系统的设计

(1)如图9所示,硬件系统框架设计

(2)如图10所示,基于BIOS/DSP的系统软件框图

图10 软件系统框图

如图9所示,本系统硬件以DM642为核心,辅以视频解码外设芯片.图像采集由摄像头采集大小为720×576的视频信号,经视频解码器A/D转换为YUV信号,由EDMA搬运QR图像交予DM642进行相应的解码处理,处理后得到的识别数据存在SDRAM中,最后将识别结果用串口传上PC端显示.

5.3 系统代码移植

本文算法先在PC环境下调用计算机视觉Opencv函数库在VS下仿真,实验效果达到预期的要求后再移植到DSP.代码的移植可以分为QR图像处理和QR解码两大部分.针对图像处理的移植,EMCV是一个适合DM64x系列DSP上运行的计算机视觉库,提供了与Opencv完全一致的函数接口,移植EMCV能够把Opencv中少量的算法移植到DSP,EMCV中与图像相关的数据结构(IplImage)和轮廓提取算法(cvFindContours)是本文的移植重点,而透视变换算法,旋转算法和网格采样算法均转成C代码直接移植到DSP,还有EMCV中与QR识别不相关的代码则裁剪掉.针对QR解码算法,引用libdecodeqr解码库,将其转成纯C代码后再移植到DSP中处理,因为转成C代码后移植在DSP嵌入式平台上运行能极大提高运行速度,且能确保与图像处理的代码一致是C代码,易于代码管理,同时裁剪EMCV能使整个系统的软件更加简介,还减少程序存储空间的负担.

6 总结

本文基于DM642嵌入式平台实现了RQ码的识别过程.首先基于位置探测图形的轮廓嵌套特性实现QR码的定位,接着以直线逼近的方法计算QR码4条边的斜截式,根据4条斜截式计算出QR码的4个角点并做逆透视变换和倾斜校正处理,进而对倾斜校正后的QR图片基于定位图形来划分网格得到每个小模块,然后计算出每个小模块代表的深浅值来生成要解码用的二维矩阵.本文算法的模拟环境是微软的visual studio 2010平台,采集的样本类型是的图像,总共200张不同倾斜角度和透视畸变的样本,样本类型如图11所示.本文定义的识别正确率为QR解码后成功解码的张数,引用libdecodeqr解码库,测试了所有不同版本的样本,识别率为92.5%.

图11 手机QR码样本图

1 于俊伟,刘楠.基于嵌入式Linux的二维码识别系统.计算机光盘软件与应用,2012,(17)：99-100.

2 张民,郑建立.基于符号特征的QR码识别算法.计算机工程,2011,37(4)：278-280.

3 Chen CS,Kot AC,Yang HJ.A two-stage quality measure for mobile phone captured 2D barcode images.Pattern Recognition,2013,46(9)：2588-2598.[doi：10.1016/j.patcog.2013.01.031]

4 黄宏博,穆志纯.基于图像处理的复杂条件下手机二维码识别.北京信息科技大学学报,2011,26(5)：40-44.

5 Suzuki S,Abe K.Topological structural analysis of digitized binary images by border following.Computer Vision,Graphics,and Image Processing,1985,30(1)：32-46.[doi：10.1016/0734-189X(85)90016-7]

6 Sun AD,Sun Y,Liu CX.The QR-code reorganization in illegible snapshots taken by mobile phone.Proceedings of the 5th International Conference on Computational Science and its Applications.Kuala Lampur,Malaysia.2007.532-538.

7 卫晋伟,戴曙光,穆平安.基于形态学和Hough变换的QR码校正与定位方法.电脑与信息技术,2010,18(6)：32-35.

8 熊用,汪鲁才,艾琼龙.基于相关匹配的QR码识别方法.仪器仪表学报,2011,32(3)：571-576.

9 Texas Instruments.TMS320DM642 video/imaging fixedpoint digital signal processor.Texas：Texas Instruments,2005.