基于轮廓特征的快速响应码定位与提取方法
2009-07-13
作者：杜秀伟，章 兢，翟景瞳
摘 要： 针对传统方法对低分辨率无自动对焦功能摄像头拍摄的QR码图像进行定位提取成功率低的缺点，提出了一种新的QR码定位与提取方法。该方法利用QR码寻像图形轮廓上的特征进行条码定位，然后利用直线最佳逼近法进行边界轮廓的寻找，找出四条边界，最后利用平面坐标变换法将条码图像旋转至水平，形成标准QR码图像，从而完成QR码图像的提取。
关键词： 快速响应码；轮廓；提取
二维条码由于其在纵横两个方向上都有信息表示，所以其信息容量大、可靠性高、保密防伪性好。因此比一维条码的应用领域更广[1-2]。QR码作为二维条码的一种，是日本Denso公司于1994年研制的矩阵式二维条码[3]，其全称为快速响应矩阵码。它不仅具有其他二维条码的优点，还具有360°全方位，超高速识读等优点。尤其是它用13 bit压缩方式表示中国汉字，比其他二维条码表示汉字的效率高20%，从而使QR码成为非常适合在中国运用的二维条码。
随着QR码的广泛应用，如何对QR码进行快速有效的提取和识别成为研究的热点。本文针对当前主要QR码定位提取算法对边界比较模糊、图像定位提取成功率低的缺点，提出了一种基于轮廓特征的QR码定位提取算法，并详细介绍了算法及QR码定位提取的全过程。
1 QR码符号结构及图像定位提取算法
1.1 QR码符号结构
QR码符号是由正方形模块堆叠而成的正方形阵列码，它由编码区域及包括寻像图形、分隔符、定位图形和校正图形在内的功能图形组成，如图1所示。
QR码符号共有40个版本。版本1的规格为21模块×21模块，以后每个版本比前一个版本每边多4个模块。根据纠错等级的不同，QR码各版本所能存储的输入容量也不相同，最多可以存储1 817个汉字，或2 953个ASCII码[1]。
1.2 QR码图像定位及提取算法
对于QR码的提取与识别，目前所采用的方法一般是利用直线按行扫描整个图像，根据扫描波形进行匹配，然后利用Hough变换寻找图像的边界，找到边界后确定条码图像的4个顶点，利用平面坐标变换将图像旋转到水平，最后利用标准的RS纠错算法对图像数据进行纠错解码[4]。该方法对于标准条码图像或者变形极其轻微的图像识别成功率比较高。但是由于无自动对焦图像获取设备获取到的图像边界特别模糊，寻像图形深浅模块比例也严重失调，采用以上方法无法提取到条码图像，从而无法进行识别[5]。针对以上这种情况，本文提出一种基于轮廓特征的QR码图像定位与提取方法。
2 基于轮廓特征的QR码定位与提取
本方法根据QR码轮廓上的特性，对图像特征进行定性分析来定位寻像图形；然后采用直线的最佳逼近方法寻找条码边界，通过平面坐标变换将条码图像变换到水平，而得到标准的QR码图像；最后用标准RS纠错算法对条码数据进行纠错并解码得到图像中的信息。本文研究的重点为条码图像的提取，图2为条码提取的程序流程。
2.1 图像预处理
图像预处理是图像识别的关键步骤之一，因为摄像头获取图像时存在固有的质量问题，会引入不同程度的椒盐噪声或者毛刺噪声，条码在使用过程中可能会被污染等。图像预处理分为图像色彩空间变换、中值滤波与图像二值化3个步骤。图像色彩空间变换将彩色图像变换成256色的灰度图像，去除了部分冗余信息，减少图像滤波的运算量。中值滤波是图像识别中最有效的滤波算法，被处理的图像中每个像素经过滤波以后其像素值等于这个像素点及其周围临域各个像素点的中值[6]。该算法的优势在于它既可以滤除椒盐噪声，同时还可以有效地保留图像的边缘特征，有利于图像识别。图像二值化将灰度图像变换成为二值图像，因为条码本身为深浅模块堆叠而成，所以最后要将图像变换成二值图像才便于处理。
2.2 基于轮廓特征的QR码定位
QR Code在感观上很容易定位，因为其4个角上有3个回字形的寻像图案。按照编码规则，该回字形图案的比例为：深色-浅色-深色-浅色-深色，比值为1：1：3：1：1，肉眼很难判断这个比例，但其轮廓特征却很明显。在图像获取设备获取的图像中，由于边缘模糊，很难得到标准条码那样的比例，所以依据一维特征模板匹配[4]的方法进行寻像图像定位，成功率不高。在此提出一种基于轮廓特征的寻像图形定位方法。
2.2.1 寻像图形定位方法
根据寻像图形特点，其轮廓面积SContour与外接矩形面积SBoundrect之比等于1。图3为条码图像发生倾斜时图像轮廓示意图。
阴影部分为倾斜的寻像图形的轮廓，a、b为平行四边形的边长和高。已知b
当条码倾斜角度在0°～10°之间变化时，Ratio的值在0.85和1之间变化，而其他任何一个轮廓都不是规则的，一般会远小于这个值。
寻像图形的另外一个特征就是轮廓内部还包含一个深色的轮廓。在上一步搜索成功以后需要判断轮廓内部是否包含一个深色的轮廓。如果有，则说明搜索成功。
在具体编程时，为了提高提高运算速度和识别率，可以适当做一些限制：
#define MIN_AREA(7*7)
//寻像图形轮廓的最小面积
#define MIN_AREA_RATIO 0.65
//轮廓与外接矩形的面积比的最小值
2.2.2 具体寻像步骤
(1)在图像中搜寻所有闭合轮廓，并存于链表中。
(2)计算各轮廓面积和外接矩形面积之比，抽取轮廓面积大于MIN_AREA，且比值大于等于MIN_AREA_RATIO的轮廓，并存于新的链表中。
(3)在新的存储轮廓的链表中继续搜索内部包含闭合轮廓的图形，并记录各个图形的顶点。
(4)统计符合上述要求的轮廓数量。如果恰巧等于3，则搜索成功，返回3个闭合轮廓的顶点坐标；否则失败。
2.3 寻找条码边界轮廓
寻像图形找到以后就知道条码的位置了，但是要想获得条码数据，还要确定条码的外围轮廓。本文采用直线最佳逼近法得到条码的轮廓。由于QR Code是典型的矩阵型条码，标准QR Code轮廓是一个标准的正方形，当拍摄图像发生变形时，轮廓可能会变成一个普通的四边形。可以根据其边界特点来寻找其轮廓。多数论文中采用Hough变换来提取直线，但是寻像图形找到后已经大约可以知道边界线的斜率和大致位置，采用Hough变换，无论是应用于整幅图像还是隔行应用，都比较浪费CPU资源。可以采用直线的最佳逼近法来寻找条码的轮廓，其算法如下：
(1)求取3个寻像图形的中心坐标。用3个坐标任意两个点做1条直线，一共做3条直线。设3个坐标点的坐标分别为(x0，y0)，(x1，y1)，(x2，y2)，3条直线的方程如下所示：
(2)使直线向远离另一个点的方向移动，每次向外偏移2个像素，即在原来方程的基础上加一个偏移量δ(δ=±2)，然后求出各条直线扫描图像所得的波形。根据各条扫描线所得波形进行对比，进行判断。在到达边界时反复来回扫描，并微调直线斜率，以得到最佳逼近直线。
(3)在移动过程中，由于一条直线始终无法得到最佳逼近效果而被抛弃，剩下2条直线。做过第三点且平行于前两个点所决定直线的直线，向远离此直线的方向进行扫描，以得到剩余两条边界直线。最终得到4条直线，围成一个闭合的四边形。得到四边形4个顶点P1′，P2′，P3′，P4′。
2.4 图像坐标变换
将寻像图形进行排序，对图形进行旋转，并依据双线性内插[3]公式（3）进行平面坐标变换，使图形转至水平。
其中：S(x，y)为变换前图像上的像素值，T(x，y)为变换后的像素点。公式中有8个未知系数，可以通过变换前四个顶点P1′，P2′，P3′，P4′与变换后的正方形4个顶点P1，P2，P3，P4联立求得。通过计算版本，再利用公式(3)将条码图像变成模块像素为1x1的标准图形。至此就可以依据标准的解码算法，进行数据解码了。图4(a)为待处理QR码图像，图4(b)为经过处理提取得到的QR码图像。
3 实验及结论
为了验证本算法的有效性，用130万像素的普通无自动对焦功能的摄像头，拍摄30张QR码图像。采用传统算法进行图像提取时，只有21张图像可以检测到寻像图形，其中17张图像可以寻找到边界轮廓，并可以成功进行有效的条码图像提取；而采用本文介绍的条码图像提取算法，有27张图片可以成功检测到寻像图形，其中27张均可以找到边界轮廓并提取到有效条码图像，1张图像变换后与原图不相符。其成功率远远高于传统的QR码提取算法。
参考文献
[1] AMPER R I，GARNER D，JORDAN G，et al.A barcodescanner aid for visually-impaired people.18th annual international conference of the IEEE engineering in medicine and biology society[C]，IEEE，1996.
[2] ISO/IEC 18004：2006.Information technology-automatic identification and data capture techniques-QR Code 2005 bar code symbology specification[S].2006.
[3] 陈丹晖，刘红编.条码技术与应用[M].北京：化学工业出版社，2006.
[4] 刘慧娟.快速响应码图像的全方位识别[J].仪器仪表学报，2006，27(4)：376-379.
[5] 明安龙，马华东，赵庆鹏.散焦模糊的畸变QR barcode图像复原技术[J].计算机辅助设计与图形学报，2007，19(8)：
1080-1084.
[6] 冈萨雷斯.数字图像处理，第二版.北京：电子工业出版社，2006.