《金陵科技学院学报》：高形变二维码识别算法设计与实现

第30卷第3期 金陵科技学院学报 Vol.30.No.3 2014年9月 JOURNAL OF JINLING INSTITUTE OF TECHNOLOGY Sep.,2014 高形变二维码识别算法设计与实现 于继明12，徐楠12，陈硕1 (1.金陵科技学院智能科学与控制工程学院，江苏南京211169： 2.江苏省信息分析工程实验室，江苏南京211169) 摘要：针对QR(Quick Response)二维码在高偏离拍摄角度下难以识别的问题，设计一种在高偏离拍摄角度下 正确识别的算法。该算法通过对图像二值化处理、形态学处理、边缘检测、Hough变换和射影几何变换5个步 骤，实现对图像的高准确率识别，使用java语言环境和移动终瑞的android环境下对算法进行仿真与算法验证， 并实现了通过扫描或读取二维码图像来写入、查找信息等操作。 关键词：QR二维码：图像识别算法：线性形变 中图分类号：TP393 文献标识码：A 文章编号：1672-755X(2014)03-0014-05 A Recognition Algorithm for Highly Deformed Two-Dimensional Code YU Ji-ming12,XU Nan'.2,CHEN Shuo (1.Jingling Institute of Technology,Nanjing 211169,China: 2.The Information Analysis Engineering Laboratory of Jiangsu Province,Nanjing 211169,China) Abstract:A recognition algorithm at a highly deviated shooting angle is proposed,which can solve the puzzle of identification for QR (Quick Response)two-dimensional code in case of high-angle shooting deviation from itself.The image can be recognized with high accuracy through the method with five procedures to process the image,i.e.,binarization processing, morphological processing,edge detection,Hough transformation and projective geometry trans- formation.Then the algorithm has been simulated and evaluated by using java language envi- ronment and android mobile terminal.By scanning or reading two-dimensional code image,the i- dentification function can be realized with the algorithm. Key words:QR two-dimensional code;image recognition algorithm;linear deformation 各种各样的二维码自诞生开始迅速成为了信息技术领域最实用和有效的成果之一，已经渗透到人民 生活和国民经济的各个领域中。不论在商品零售、制造业等领域，还是在供应链管理、电子商务和现代物 流等各个环节，二维码已经扮演了不可或缺的重要角色]。为了实现对二维码的识别，人们使用图像采集 设备（如数码相机、激光扫描器、面阵CCD等成像设备），得到含有二维码的图像，然后经过定位（预处理、 定位、角度纠正和特征值提取)、分割和解码3个步骤实现对二维码的识别。现在广泛使用的二维码识别 算法具有快速识别的特性，但对于高偏离拍摄角度的识别，这些算法不能快速有效地得出解码结果。当偏 收稿日期：2014-0911 基金项目：金陵科技学院博士启动基金“基于物联网应用的智能校园路灯系统研究”：金陵科技学院2013年省级大学 生科技创新项目“智能苗床系统研究”(201313573010) 作者简介：于继明(1976一)，男，河南省罗山人，副教授，博士，CCF会员(E200038613M),主要从事物联网应用技术 研究。 ?1994-2015 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

第３０卷 第３期 ２０１４年９月 金 陵 科 技 学 院 学 报 ＪＯＵＲＮＡＬＯＦＪＩＮＬＩＮＧＩＮＳＴＩＴＵＴＥＯＦＴＥＣＨＮＯＬＯＧＹ Ｖｏｌ．３０，Ｎｏ．３ Ｓｅｐ．，２０１４ 高形变二维码识别算法设计与实现 于继明１，２，徐 楠１，２，陈 硕１ （１．金陵科技学院智能科学与控制工程学院，江苏 南京 ２１１１６９； ２．江苏省信息分析工程实验室，江苏 南京 ２１１１６９） 摘 要：针对 ＱＲ（ＱｕｉｃｋＲｅｓｐｏｎｓｅ）二维码在高偏离拍摄角度下难以识别的问题，设计一种在高偏离拍摄角度下 正确识别的算法。该算法通过对图像二值化处理、形 态 学 处 理、边 缘 检 测、Ｈｏｕｇｈ变换和射影几何变换５个步 骤，实现对图像的高准确率识别，使用ｊａｖａ语言环境和移动终端的ａｎｄｒｏｉｄ环境下对算法进行仿真与算法验证， 并实现了通过扫描或读取二维码图像来写入、查找信息等操作。 关键词：ＱＲ二维码；图像识别算法；线性形变 中图分类号：ＴＰ３９３ 文献标识码：Ａ 文章编号：１６７２－７５５Ｘ（２０１４）０３－００１４－０５ 收稿日期：２０１４－０９－１１ 基金项目：金陵科技学院博士启动基金“基于物联网应用的智能校园路灯系统研究”；金陵科技学院２０１３年省级大学 生科技创新项目“智能苗床系统研究”（２０１３１３５７３０１０） 作者简介：于继明（１９７６－），男，河 南 省罗 山 人，副 教 授，博 士，ＣＣＦ会员（Ｅ２０００３８６１３Ｍ），主要从事物联网应用技术 研究。 ＡＲｅｃｏｇｎｉｔｉｏｎＡｌｇｏｒｉｔｈｍｆｏｒＨｉｇｈｌｙＤｅｆｏｒｍｅｄＴｗｏ－ＤｉｍｅｎｓｉｏｎａｌＣｏｄｅ ＹＵＪｉ－ｍｉｎｇ１，２，ＸＵ Ｎａｎ１，２，ＣＨＥＮＳｈｕｏ （１．ＪｉｎｇｌｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ２１１１６９，Ｃｈｉｎａ； ２．ＴｈｅＩｎｆｏｒｍａｔｉｏｎＡｎａｌｙｓｉｓＥｎｇｉｎｅｅｒｉｎｇＬａｂｏｒａｔｏｒｙｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅ，Ｎａｎｊｉｎｇ２１１１６９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｒｅｃｏｇｎｉｔｉｏｎａｌｇｏｒｉｔｈｍａｔａｈｉｇｈｌｙｄｅｖｉａｔｅｄｓｈｏｏｔｉｎｇａｎｇｌｅｉｓｐｒｏｐｏｓｅｄ，ｗｈｉｃｈｃａｎ ｓｏｌｖｅｔｈｅｐｕｚｚｌｅｏｆｉｄｅｎｔｉｆｉｃａｔｉｏｎｆｏｒＱＲ （Ｑｕｉｃｋ Ｒｅｓｐｏｎｓｅ）ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｃｏｄｅｉｎｃａｓｅｏｆ ｈｉｇｈ－ａｎｇｌｅｓｈｏｏｔｉｎｇｄｅｖｉａｔｉｏｎｆｒｏｍｉｔｓｅｌｆ．Ｔｈｅｉｍａｇｅｃａｎｂｅｒｅｃｏｇｎｉｚｅｄ ｗｉｔｈｈｉｇｈａｃｃｕｒａｃｙ ｔｈｒｏｕｇｈｔｈｅｍｅｔｈｏｄｗｉｔｈｆｉｖｅｐｒｏｃｅｄｕｒｅｓｔｏｐｒｏｃｅｓｓｔｈｅｉｍａｇｅ，ｉ．ｅ．，ｂｉｎａｒｉｚａｔｉｏｎｐｒｏｃｅｓｓｉｎｇ， ｍｏｒｐｈｏｌｏｇｉｃａｌｐｒｏｃｅｓｓｉｎｇ，ｅｄｇｅｄｅｔｅｃｔｉｏｎ，Ｈｏｕｇｈｔｒａｎｓｆｏｒｍａｔｉｏｎａｎｄｐｒｏｊｅｃｔｉｖｅｇｅｏｍｅｔｒｙｔｒａｎｓ－ ｆｏｒｍａｔｉｏｎ．Ｔｈｅｎｔｈｅａｌｇｏｒｉｔｈｍｈａｓｂｅｅｎｓｉｍｕｌａｔｅｄａｎｄｅｖａｌｕａｔｅｄｂｙｕｓｉｎｇｊａｖａｌａｎｇｕａｇｅｅｎｖｉ－ ｒｏｎｍｅｎｔａｎｄａｎｄｒｏｉｄｍｏｂｉｌｅｔｅｒｍｉｎａｌ．Ｂｙｓｃａｎｎｉｎｇｏｒｒｅａｄｉｎｇｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｃｏｄｅｉｍａｇｅ，ｔｈｅｉ－ ｄｅｎｔｉｆｉｃａｔｉｏｎｆｕｎｃｔｉｏｎｃａｎｂｅｒｅａｌｉｚｅｄｗｉｔｈｔｈｅａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ＱＲｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｃｏｄｅ；ｉｍａｇｅｒｅｃｏｇｎｉｔｉｏｎａｌｇｏｒｉｔｈｍ；ｌｉｎｅａｒｄｅｆｏｒｍａｔｉｏｎ 各种各样的二维码自诞生开始迅速成为了信息技术领域最实用和有效的成果之一，已经渗透到人民 生活和国民经济的各个领域中。不论在商品零售、制造业等领域，还是在供应链管理、电子商务和现代物 流等各个环节，二维码已经扮演了不可或缺的重要角色［１］。为了实现对二维码的识别，人们使用图像采集 设备（如数码相机、激光扫描器、面阵 ＣＣＤ等成像设备），得到含有二维码的图像，然后经过定位（预处理、 定位、角度纠正和特征值提取）、分割和解码３个步骤实现对二维码的识别。现在广泛使用的二维码识别 算法具有快速识别的特性，但对于高偏离拍摄角度的识别，这些算法不能快速有效地得出解码结果。当偏

第3期 于继明，等：高形变二维码识别算法设计与实现 15 离角度较大、焦距较小时，图形的形变不仅仅只是普通的缩放，还会是旋转形变或仿射形变了。因此，研究 与设计高形变角度下的二维码图形识别算法具有重要的意义。 1QR二维码介绍及常用算法 11QR二维码原理 QR二维码是Denso Wave于1994年在丰田公司发明，是一种矩阵式的二维码符号。QR二维码不 仅具有识别扫描速度快、信息容量较大、可靠性较高、成本较低的特性， 它还可表示汉字及图像等多种文字信息，并且其保密防伪性强，使用也 很方便。诞生初期主要在中、日、韩地区发展，后迅速传至欧美地区。 QR二维码符号共有40种版本规格，分别为版本1一40。版本1的规格 为21×21个模块，版本2为25×25个模块，以此类推，每1版本符号总 是比前1版本每边增加4个模块，一直到版本40，版本40的规格为177 ×177个模块。图1为版本2的示意图(25×25个模块)。 二维码的编码过程包括：1)数据采样计算，确定待编码信息的符号 类型（包括中文、英文等），按照相应的字符集编码规则分别转换成对应 字符或数字。2)选择一个纠错等级L到H,一般情况下，纠错等级越高 其真实数据的容量越小。3)数据编码，将所有的数据字符转换为位流， 图1版本2的QR码 每8位一个码字成为一组，所有数据最终转化的整体构成一个数据的码 Fig 1 QR code for version 2 字序列。4)纠错编码，将码字序列分块，并根据纠错等级和分块的码 字，产生对应的纠错码字，并把纠错码字加入到数据码字序列的后面。5)构造最终数据阵列，按次序放入 分块中，按规定把数据分块，将码字模块、定位图像、探测图形、分隔符依次放入矩阵中。 1.2QR二维码识别中的基本算法 12.1图像二值化算法图像二值化是指用通过研究图像的灰度分布来研究灰度图像的一种图像数据 处理手段，设定某一阈值或为若干区域设定若干阈值，将灰度图像的每个像素点划分成大于阈值的像素点 集、小于阈值的像素点集两个部分。每个像素点的值要么是0，要么是255。二值化操作之后，图像将呈现 出鲜明的黑白效果。 12.2边缘检测算法物体的边缘是指以局部特征不连续性出现的部分，是区分不同区域的重要参数。 传统的边缘检测（如一介边缘算子）利用了边缘是图像灰度变化最剧烈的特点，对图像各个像素点求导数 或者二阶导数来确定边缘点集。常用的边缘提取梯度算子有：Robert算子，Sobel算子，Prewitt算 子等。 边缘检测算法是基础的图像分割算法，是进行各种几何变换、特征提取的首要工作，边缘检测算法为 各种图像分割需求提供了较好的支持，对于本身就是黑白图像、灰度又不是很连续的二维码图像而言，上 述算法均能够取得非常好的边缘检测效果。从边缘检测的时间复杂度上看，每一种边缘检测算法都具有 较好的时间效率和空间效率，在进行图像处理时，边缘检测算法一般不会成为影响整个程序运行速度的 瓶颈。 2高偏离角度的二维码识别算法设计 从识别算法的角度，二维码识别算法应当满足以下需求：1)二维码图像的高效二值化处理：2)能够 有效地定位到二维码所在的大概区域，排除与识别信息无关的图像区域；3)能够实现对任意拍摄角度的 图像的正则复原操作，复原结果应当尽量减小与原图像的误差：4)将复原的图像使用二维码转码包进行 转码。识别过程见图2。 21二值化处理算法设计 在二值化处理过程中，针对QR二维码的特性，采用最大类间方差的方法处理。首先获取原图像的灰 ?1994-2015 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

第３期 于继明，等：高形变二维码识别算法设计与实现 离角度较大、焦距较小时，图形的形变不仅仅只是普通的缩放，还会是旋转形变或仿射形变了。因此，研究 与设计高形变角度下的二维码图形识别算法具有重要的意义。 １ ＱＲ二维码介绍及常用算法 １．１ ＱＲ二维码原理 ＱＲ二维码是 ＤｅｎｓｏＷａｖｅ于１９９４年在丰田公司发明，是一种矩阵式的二维码符号。ＱＲ 二维码不 图１ 版本２的 ＱＲ码 Ｆｉｇ．１ ＱＲｃｏｄｅｆｏｒｖｅｒｓｉｏｎ２ 仅具有识别扫描速度快、信息容量较大、可靠性较高、成本较低的特性， 它还可表示汉字及图像等多种文字信息，并且其保密防伪性强，使用也 很方便。诞生 初 期 主 要 在 中、日、韩 地 区 发 展，后 迅 速 传 至 欧 美 地 区。 ＱＲ二维码符号共有４０种版本规格，分别为版本１－４０。版本１的规格 为２１×２１个模块，版本２为２５×２５个模块，以此类推，每１版本符号总 是比前１版本每边增加４个模块，一直到版本４０，版本４０的规格为１７７ ×１７７个模块。图１为版本２的示意图（２５×２５个模块）。 二维码的编码过程包括：１）数据采样计算，确定待编码信息的符号 类型（包括中文、英文等），按照相应的字符集编码规则分别转换成对应 字符或数字。２）选择一个纠错等级 Ｌ到 Ｈ，一般情况下，纠错等级越高 其真实数据的容量越小。３）数据编码，将所有的数据字符转换为位流， 每８位一个码字成为一组，所有数据最终转化的整体构成一个数据的码 字序列。４）纠错编 码，将 码 字 序 列 分 块，并 根 据 纠 错 等 级 和 分 块 的 码 字，产生对应的纠错码字，并把纠错码字加入到数据码字序列的后面。５）构造最终数据阵列，按次序放入 分块中，按规定把数据分块，将码字模块、定位图像、探测图形、分隔符依次放入矩阵中。 １．２ ＱＲ二维码识别中的基本算法 １．２．１ 图像二值化算法 图像二值化是指用通过研究图像的灰度分布来研究灰度图像的一种图像数据 处理手段，设定某一阈值或为若干区域设定若干阈值，将灰度图像的每个像素点划分成大于阈值的像素点 集、小于阈值的像素点集两个部分。每个像素点的值要么是０，要么是２５５。二值化操作之后，图像将呈现 出鲜明的黑白效果。 １．２．２ 边缘检测算法 物体的边缘是指以局部特征不连续性出现的部分，是区分不同区域的重要参数。 传统的边缘检测（如一介边缘算子）利用了边缘是图像灰度变化最剧烈的特点，对图像各个像素点求导数 或者 二 阶 导 数 来 确 定 边 缘 点 集。常 用 的 边 缘 提 取 梯 度 算 子 有：Ｒｏｂｅｒｔ算 子，Ｓｏｂｅｌ算 子，Ｐｒｅｗｉｔｔ算 子等［２］。 边缘检测算法是基础的图像分割算法，是进行各种几何变换、特征提取的首要工作，边缘检测算法为 各种图像分割需求提供了较好的支持，对于本身就是黑白图像、灰度又不是很连续的二维码图像而言，上 述算法均能够取得非常好的边缘检测效果。从边缘检测的时间复杂度上看，每一种边缘检测算法都具有 较好的时间效率和空间效率，在进行图像处理时，边缘检测算法一般不会成为影响整个程序运行速度的 瓶颈。 ２ 高偏离角度的二维码识别算法设计 从识别算法的角度，二维码识别算法应当满足以下需求：１）二维码图像的高效二值化处理；２）能够 有效地定位到二维码所在的大概区域，排除与识别信息无关的图像区域；３）能够实现对任意拍摄角度的 图像的正则复原操作，复原结果应当尽量减小与原图像的误差；４）将复原的图像使用二维码转码包进行 转码。识别过程见图２。 ２．１ 二值化处理算法设计 在二值化处理过程中，针对 ＱＲ二维码的特性，采用最大类间方差的方法处理。首先获取原图像的灰 ５１

16 金陵科技学院学报 第30卷 度直方图，数学描述为记录灰度为i的像素点的数目为c:(i= 开始○ 0,1,2,.255)。对某一阈值T,将原图像分为两类（背景与 使取图像☑ 前景)，计算阈值T下的类间方差值，类间方差计算公式为 (T)=6(ho-u)2+(出-u)2… (1) 二值化处理 其中， 形态学渲染 255 Ci 边缘检测 i0 -T Hough变换 Ci 射彤变换 让阈值T在灰度可行域内变化，使得方差σ(T)最大的T 取样转码 为最优解。该算法描述如下： 1)计算原图像的灰度直方图，记为c:(i=0,1,2,..255) 结束 ,灰度阅值迭代初始值为T=0,阈值初值为。=一1，最佳阈 图2识别算法流程 值初值记为T。=0。 Fig.2 The procedure of recognition algorithm 2)按照式(1)计算给定阈值T下的类间方差。(T),若σ(T)>,则将T。值设为T。 3)若T未达到灰度上限，则T增加灰度值，返回2)：否则执行下一步。 经过上述3步，得到T。即为最佳阈值。 22图像形态学渲染 为了使二维码区域能够凸显出来，需要二维码区域进行一次腐蚀、膨胀的操作。QR二维码的编码规 则具有均匀分布的特点，可以各个像素点的周围圆周点集作为膨胀因子，获得较好的膨胀效果；本算法取 对前景点集A以B作为膨胀元素，膨胀操作为[冈 A⊕B={X|Bx∩A≠☑，X∈A}… (2) 其中Bx={X+了|Y∈B},结合QR码的图像特点，取膨胀因子B={X1X1?+X22=p},对 于膨胀因子B而言，可以采用圆的参数方程迭代的方式来计算它的点集，具体算法步骤如下： 1)取定半径参数R,角度离散尺度D。-一&0，初始选代角度a=0: 2)由X=R。cos(a)和Y=R。sin(a)计算点(X,Y),把该点加入到B中； 3)角度α增加一个离散尺度，返回2)继续计算，直到离散尺度值全部迭代完毕。 23边缘检测算法 为了纠正偏离角度的图片，需对原图像进行射影几何变换。取4个点（任意3点不共线）的坐标值，使 用最为简单的一阶边缘算子来计算边缘。某点的梯度E(x,y)定义为 E(x,y)=|E(x+1,y)-E(x,y)+E(x,y+1)-E(x,y)|… (3) 按照式(3)进行迭代，对每个像素点的梯度判断是否为0确定边缘点集。 24 Hough变换算法 根据边缘检测算法取得边缘后，只能够以直线相交的方法来计算4个顶点。应用Hough变换，可将 边缘点集映射到直线参数空间，通过计算参数空间的极值取得直线的参数坐标值。 对边缘点集中的点X=(x,y),应用直线的相距式p=xcos0+ysi0中的参数，绘制直线对应于参数 空间的曲线，将曲线离散化（离散尺度取忍0，参数范围为日∈[0，）)，并将曲线上的点与该点对应的二 维数组的值累加1次。具体步骤如下： 1)初始化参数空间PSpace(i,j)(全部为0)，0∈[0，π)，p∈[-√r十y,√x十y],再将p增 ?1994-2015 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

金 陵 科 技 学 院 学 报 第３０卷 图２ 识别算法流程 Ｆｉｇ．２ Ｔｈｅｐｒｏｃｅｄｕｒｅｏｆｒｅｃｏｇｎｉｔｉｏｎａｌｇｏｒｉｔｈｍ 度直方图，数学描述为记录灰度为ｉ的像素点的数目为ｃｉ（ｉ＝ ０，１，２，．．．２５５）。对某一阈值Ｔ ，将原图像分为两类（背景与 前景），计算阈值Ｔ 下的类间方差值，类间方差计算公式为 σ（Ｔ）＝ ｗ０ （μ０ －μ）２ ＋ｗ１ （μ１ －μ）２…… （１） 其中， ｗ０ ＝ ∑ Ｔ ｉ＝０ ｃｉ ∑ ２５５ ｉ＝０ ｃｉ ，ｗ１ ＝ ∑ ２５５ ｉ＝Ｔ＋１ ｃｉ ∑ ２５５ ｉ＝０ ｃｉ ，μ０ ＝ ∑ Ｔ ｉ＝０ ｉｃｉ ∑ ２５５ ｉ＝０ ｃｉ ，μ１ ＝ ∑ ２５５ ｉ＝Ｔ＋１ ｉｃｉ ∑ ２５５ ｉ＝０ ｃｉ ，μ＝ ∑ ２５５ ｉ＝０ ｉｃｉ ∑ ２５５ ｉ＝０ ｃｉ 让阈值Ｔ 在灰度可行域内变化，使得方差σ（Ｔ）最大的Ｔ 为最优解。该算法描述如下： １）计算原图像的灰度直方图，记为ｃｉ（ｉ＝０，１，２，．．．２５５） ，灰度阈值迭代初始值为Ｔ＝０，阈值初值为σ０ ＝－１，最佳阈 值初值记为Ｔ０ ＝０。 ２）按照式（１）计算给定阈值Ｔ 下的类间方差σ（Ｔ），若σ（Ｔ）＞σ０ ，则将Ｔ０ 值设为Ｔ 。 ３）若Ｔ 未达到灰度上限，则Ｔ 增加灰度值，返回２）；否则执行下一步。 经过上述３步，得到Ｔ０ 即为最佳阈值。 ２．２ 图像形态学渲染 为了使二维码区域能够凸显出来，需要二维码区域进行一次腐蚀、膨胀的操作。ＱＲ 二维码的编码规 则具有均匀分布的特点，可以各个像素点的周围圆周点集作为膨胀因子，获得较好的膨胀效果；本算法取 对前景点集Ａ 以Ｂ 作为膨胀元素，膨胀操作为［２］ Ａ Ｂ ＝ ｛Ｘ → ｜ＢＸ ∩Ａ ≠ ，Ｘ → ∈Ａ｝…… （２） 其中ＢＸ ＝ ｛Ｘ → ＋Ｙ → ｜Ｙ → ∈Ｂ｝，结合 ＱＲ码的图像特点，取膨胀因子Ｂ ＝ ｛Ｘ → ｜Ｘ１ ２ ＋Ｘ２ ２ ＝ρ ２｝，对 于膨胀因子Ｂ 而言，可以采用圆的参数方程迭代的方式来计算它的点集，具体算法步骤如下： １）取定半径参数Ｒ０ ，角度离散尺度 Ｄ０ ＝ π １８０，初始迭代角度α＝０； ２）由 Ｘ ＝Ｒ０ｃｏｓ（α）和Ｙ ＝Ｒ０ｓｉｎ（α）计算点 （Ｘ，Ｙ），把该点加入到Ｂ 中； ３）角度α增加一个离散尺度，返回２）继续计算，直到离散尺度值全部迭代完毕。 ２．３ 边缘检测算法 为了纠正偏离角度的图片，需对原图像进行射影几何变换。取４个点（任意３点不共线）的坐标值，使 用最为简单的一阶边缘算子来计算边缘。某点的梯度Ｅ（ｘ，ｙ）定义为 Ｅ（ｘ，ｙ）＝ Ｅ（ｘ＋１，ｙ）－Ｅ（ｘ，ｙ）＋Ｅ（ｘ，ｙ＋１）－Ｅ（ｘ，ｙ） …… （３） 按照式（３）进行迭代，对每个像素点的梯度判断是否为０确定边缘点集。 ２．４ Ｈｏｕｇｈ变换算法 根据边缘检测算法取得边缘后，只能够以直线相交的方法来计算４个顶点。应用 Ｈｏｕｇｈ变换，可将 边缘点集映射到直线参数空间，通过计算参数空间的极值取得直线的参数坐标值。 对边缘点集中的点 Ｘ → ＝ （ｘ，ｙ），应用直线的相距式ρ＝ｘｃｏｓθ＋ｙｓｉｎθ中的参数，绘制直线对应于参数 空间的曲线，将曲线离散化（离散尺度取 π １８０，参数范围为θ∈ ［０，π）），并将曲线上的点与该点对应的二 维数组的值累加１次。具体步骤如下： １）初始化参数空间ＰＳｐａｃｅ（ｉ，ｊ）（全部为０），θ∈ ［０，π），ρ∈ ［－ ｘ２ ｍ ＋ｙ２ 槡 ｍ ， ｘ２ ｍ ＋ｙ２ 槡 ｍ ］，再将ρ增 ６１

第3期 于继明，等：高形变二维码识别算法设计与实现 17 加一个√x十y值，使之落在正数区间范围； 2)对边缘点集中的每一个点P(x,),带入p=xcos0+sin0,步长为忍0,0在[0，)中离散变化， 得到180个点： 3)将步骤2)得到的点全部四舍五入取整数，绘制到参数空间中。 在实际处理图像时，每条直线在图像中可能凸显的并不明显，有可能出现两对比较相近的参数表示的 实际上是同一直线，为解决这一问题，在选择了某个极大值对应的参数后，应当屏蔽这些点。实际操作时 将屏蔽点的值设为小于0来做屏蔽处理。 Hough变换结束后，为了能够在射影变换中使得4个交点与4个正则目标点一一对应，需要求解4 线在图像面内的交点以及交点的时钟顺序。求交点的算法步骤如下： 1)对4条直线的参数两两运算，记录图像内交点，可得到4个交点： 2)对于已经求得的4个交点pi,p2,p,p:,计算pp2与pp向量积的模长，pp2×pp= x2一x一y =M,p1p:与1p=M2,若M与M异号，说明线段p1p与p2p:相交，否则选择 xs-x1 ys-y1 其他点替换p点，直到M·M2<0为止； 3)经过步骤2)操作的点p,2,p,p:即为时钟序，当p1p2与pp向量积的带方向模长大于0时为 逆时钟序，当pp2与p:p:向量积小于0时为顺时钟序。 25射影变换算法 对于平面π的4个点(，，，)（齐次坐标）到平面x的4个点(，，，)确定一个射影变 换的充要条件是云，云和了广的任意3点不共线，且射影变换矩阵表达式为1： H=(,,agg,多)》 Pr Pa Ps (4) 其中p=(》1,p-(,,)式 应用式(4)，对于平面上的4个点，求解射影变换距离H,对于目标平面（正则）上的每一个点p= (x,y),计算H1P是否为图像平面的前景点，如果是，就将目标平面这一点设置为前景点，否则设置为 背景点。应用本步骤可对图像进行校正。 3模块设计与仿真实现 31模块关系图 本算法在Eclipse环境实现，根据图2流程，设计模块之间调用关系见图3。 Recognition Binary Morpholog Edge Search Hough Projective Location Matrix Segment Point Set Segment Set 图3模块调用关系 Fig.3 Module call ?1994-2015 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

第３期 于继明，等：高形变二维码识别算法设计与实现 加一个 ｘ２ ｍ ＋ｙ２ 槡 ｍ 值，使之落在正数区间范围； ２）对边缘点集中的每一个点Ｐ（ｘ，ｙ），带入ρ＝ｘｃｏｓθ＋ｙｓｉｎθ，步长为 π １８０，θ在 ［０，π）中离散变化， 得到１８０个点； ３）将步骤２）得到的点全部四舍五入取整数，绘制到参数空间中。 在实际处理图像时，每条直线在图像中可能凸显的并不明显，有可能出现两对比较相近的参数表示的 实际上是同一直线，为解决这一问题，在选择了某个极大值对应的参数后，应当屏蔽这些点。实际操作时 将屏蔽点的值设为小于０来做屏蔽处理。 Ｈｏｕｇｈ变换结束后，为了能够在射影变换中使得４个交点与４个正则目标点一一对应，需要求解４ 线在图像面内的交点以及交点的时钟顺序。求交点的算法步骤如下： １）对４条直线的参数两两运算，记录图像内交点，可得到４个交点； ２）对于已 经 求 得 的 ４ 个 交 点 ｐ →１，ｐ →２，ｐ →３，ｐ →４ ，计 算 ｐ１ｐ→２ 与 ｐ１ｐ→３ 向 量 积 的 模 长，ｐ１ｐ→２ ×ｐ１ｐ→３ ＝ ｘ２ －ｘ１ ｙ２ －ｙ１ ｘ３ －ｘ１ ｙ３ －ｙ１ ＝Ｍ１ ，ｐ１ｐ→４ 与ｐ１ｐ→３ ＝ Ｍ２ ，若 Ｍ１ 与 Ｍ２ 异号，说明线段ｐ１ｐ３ 与ｐ２ｐ４ 相交，否则选择 其他点替换ｐ３ 点，直到 Ｍ１·Ｍ２ ＜０为止； ３）经过步骤２）操作的点ｐ →１，ｐ →２，ｐ →３，ｐ →４ 即为时钟序，当ｐ１ｐ→２ 与ｐ１ｐ→３ 向量积的带方向模长大于０时为 逆时钟序，当ｐ１ｐ→２ 与ｐ１ｐ→３ 向量积小于０时为顺时钟序。 ２．５ 射影变换算法 对于平面π的４个点 （ｘ→１，ｘ→２，ｘ→３，ｘ→４）（齐次坐标）到平面π′的４个点 （ｘ′→１，ｘ′→２，ｘ′→３，ｘ′→４）确定一个射影变 换的充要条件是ｘ→１，ｘ→２，ｘ→３，ｘ→４ 和ｘ′→１，ｘ′→２，ｘ′→３，ｘ′→４ 的任意３点不共线，且射影变换矩阵表达式为［３－６］： Ｈ ＝ （ｘ′→１，ｘ′→２，ｘ′→３）ｄｉａｇ（ ｐ′１ ｐ１ ， ｐ′２ ｐ２ ， ｐ′３ ｐ３ ）（ｘ→１，ｘ→２，ｘ→３）－１ 其中ｐ ＝ （ｘ→１，ｘ→２，ｘ→３）－１ｘ→４，ｐ′ ＝ （ｘ′→１，ｘ′→２，ｘ′→３）－１ｘ′→４ …… （４） 应用式（４），对于平面上 的４个 点，求解射影变换距离 Ｈ，对 于 目标 平 面（正 则）上 的 每 一 个 点 ｐ → ＝ （ｘ，ｙ）Ｔ ，计算 Ｈ－１ Ｐ → 是否为图像平面的前景点，如果是，就将目标平面这一点设置为前景点，否则设置为 背景点。应用本步骤可对图像进行校正。 ３ 模块设计与仿真实现 ３．１ 模块关系图 本算法在 Ｅｃｌｉｐｓｅ环境实现，根据图２流程，设计模块之间调用关系见图３。 图３ 模块调用关系 Ｆｉｇ．３ Ｍｏｄｕｌｅｃａｌｌ ７１

18 金陵科技学院学报 第30卷 其中，Binary实现二值化功能，Edge Search实现边缘检测功能，Hough实现Hough变换。 32算法仿真结果 为了验证算法的正确性，取得普通形变二维码图形与高度形变图形进行识别比较。正常情况下，普通 形变时图形的识别结果见图4。 ▣▣ 图4变通形变识别测试结果 Fig.4 The recognition test results of flexible deformation 当获取的图形高度形变时，如图5所示，采用本算法流程，得到较理想结果，如图6所示。 州 回 ▣5®N 图5高度形变图像 图6高度形变图像识别结果 Fig.5 Highly deformed image Fig.6 The recognition results of highly deformed image 通过实例测试可以看出，对高度形变的图像，高形变二维码识别算法具有良好的识别结果，能够完成 传统识别算法难以完成的识别工作，提高了识别准确率与识别能力。 4结语 传统二维码识别算法能够在一个比较小的偏离角度下正确识别，但是对高度形变图形，却难以正确识 别。本算法对Q【二维码设计了识别过程，对图像处理算法给出了实现原理，并编码进行算法实现，验证 算法的正确性与识别能力。实验结果显示，使用本算法对非仿射变换的线性射影进行变换，能够弥补识别 率低的缺陷，实现更高的识别能力。 参考文献： [1]中国物品编码中心.二维条码技术与应用[M门.北京：中国计量出版社，2007 [2]Rafael C.Gonzalez..数字图像处理[M们.阮秋琦，译.2版.北京：电子工业出版社，2007 [3]吴朝福.计算机视觉中的数学方法[M门.北京：电子工业出版社，2011 [4]肖翔，刘晓明，王云柯.QR码图像的矫正与定位方法研究[].计算机科学，2007,23(2)：18-20 [5]谷晓琳，黄明，戚海英.基于遗传算法的二维QR码图像识别[J].大连铁道学院学报，2005,12(3)：35-38 [6]刘宁钟，杨静宇.基于傅里叶变换的二维条码识别[J].中国图像图形学报，2011,18(2)：45一46 (责任编辑：马金玉) ?1994-2015 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

金 陵 科 技 学 院 学 报 第３０卷 其中，Ｂｉｎａｒｙ实现二值化功能，ＥｄｇｅＳｅａｒｃｈ实现边缘检测功能，Ｈｏｕｇｈ实现 Ｈｏｕｇｈ变换。 ３．２ 算法仿真结果 为了验证算法的正确性，取得普通形变二维码图形与高度形变图形进行识别比较。正常情况下，普通 形变时图形的识别结果见图４。 图４ 变通形变识别测试结果 Ｆｉｇ．４ Ｔｈｅｒｅｃｏｇｎｉｔｉｏｎｔｅｓｔｒｅｓｕｌｔｓｏｆｆｌｅｘｉｂｌｅｄｅｆｏｒｍａｔｉｏｎ 当获取的图形高度形变时，如图５所示，采用本算法流程，得到较理想结果，如图６所示。 图５ 高度形变图像 Ｆｉｇ．５ Ｈｉｇｈｌｙｄｅｆｏｒｍｅｄｉｍａｇｅ 图６ 高度形变图像识别结果 Ｆｉｇ．６ Ｔｈｅｒｅｃｏｇｎｉｔｉｏｎｒｅｓｕｌｔｓｏｆｈｉｇｈｌｙｄｅｆｏｒｍｅｄｉｍａｇｅ 通过实例测试可以看出，对高度形变的图像，高形变二维码识别算法具有良好的识别结果，能够完成 传统识别算法难以完成的识别工作，提高了识别准确率与识别能力。 ４ 结 语 传统二维码识别算法能够在一个比较小的偏离角度下正确识别，但是对高度形变图形，却难以正确识 别。本算法对 ＱＲ二维码设计了识别过程，对图像处理算法给出了实现原理，并编码进行算法实现，验证 算法的正确性与识别能力。实验结果显示，使用本算法对非仿射变换的线性射影进行变换，能够弥补识别 率低的缺陷，实现更高的识别能力。 参考文献： ［１］中国物品编码中心．二维条码技术与应用 ［Ｍ］．北京：中国计量出版社，２００７ ［２］ＲａｆａｅｌＣ．Ｇｏｎｚａｌｅｚ．数字图像处理［Ｍ］．阮秋琦，译．２版．北京：电子工业出版社，２００７ ［３］吴朝福．计算机视觉中的数学方法［Ｍ］．北京：电子工业出版社，２０１１ ［４］肖翔，刘晓明，王云柯．ＱＲ 码图像的矫正与定位方法研究［Ｊ］．计算机科学，２００７，２３（２）：１８－２０ ［５］谷晓琳，黄明，戚海英．基于遗传算法的二维 ＱＲ 码图像识别［Ｊ］．大连铁道学院学报，２００５，１２（３）：３５－３８ ［６］刘宁钟，杨静宇．基于傅里叶变换的二维条码识别 ［Ｊ］．中国图像图形学报，２０１１，１８（２）：４５－４６ （责任编辑：马金玉） ８１