畸变Data Matrix码图像的倾斜校正算法研究

关博熠　董静薇　马晓峰　徐博

摘要：针对Data Matrix码倾斜校正中需要多次旋转的问题，本文提出了一种畸变二维码倾斜校正方法。首先使用LoG算子对二值化后的图像进行边缘检测，再基于Data Matrix码的结构特征，通过Hough变换有效快速地确定定位符“L”所在的位置，并将“L”型交点用两条向量表示。然后通过向量叉乘计算出Data Matrix码的旋转角度、确定旋转方向，只需一次旋转即可实现倾斜校正。本文算法节省了Data Matrix码在图像恢复过程中所需的时间和工作量。

关键词：

Data Matrix码；倾斜校正；LoG算子；Hough变换；向量叉乘

DOI：10.15938/j.jhust.2018.05.017

中图分类号： TP751.1

文献标志码： A

文章编号： 1007-2683（2018）05-0100-06

Research on Tilt Correction Algorithms of Destorted Data Matrix Code Image

GUAN Boyi，DONG Jingwei，MA Xiaofeng，XU Bo

（School of Measurement and Control Technology and Communications Engineering， Harbin University of Science and Technology，

The Higher Educational Key Laboratory for Measuring and Control Technology and Instrumentations of Heilongjiang Province， Harbin University of Science and Technology Harbin 150080， China）

Abstract：Aiming at the problem of multiple rotations in the tilting correction of Data Matrix code， a tilt correction method for distorted 2D code is proposed in this paper. First， the LoG operator is used to detect the edge of the binary image， and then based on the structural features of the Data Matrix code， the location of the locator “L” is quickly determined by the Hough transform， and the “L” intersection point is expressed with two vectors. By vector cross product the rotation angle of Data Matrix code is calculated and the direction of rotation is determined then. So， only one rotation is needed to achieve tilt correction. This algorithm saves the time and workload of Data Matrix code in the process of image restoration.

Keywords：data matrix code； tilt Correction； LoG operator； hough transform； vector crossproduct

0引言

二維条码技术，近年来已成为计算机领域的热门研究方向，广泛流通于商品流通领域，电子商务领域以及公共信息领域[1]。国际上常用的二维条码有PDF417，QR code，Data Matrix码等[2]。相比于一维码，二维码技术更为先进和科学，不仅多了纠错功能，而且信息的密度有了大幅度的提高，并且能够进行双向信息的承载[3-4]。Data Matrix码的尺寸可任意调整，大多数条码的大小与编入的资料量有着绝对关系，但Data Matrix码的尺寸与其编入的资料量却相互独立，因此它的尺寸较有弹性[5]，目前它的最小尺寸是所有条码中最小的，尤其适用于小零件标识，并且可以直接印在实体上；因而被广泛应用于标识集成电路、药品等小件物品以及制造业的流水线生产过程，因此，对Data Matrix码的研究有着极为重要的现实意义[6]。

二维条码的识读过程是整个二维码识别系统的重要组成部分[7-8]，二维条码的倾斜会导致二维条码在符号字符提取时被错误分割，从而影响符号字符提取的效果，因此，需要对拍摄过程中产生畸变的二维条码进行倾斜校正，以便于之后二维条码的正确分割。杜志俊运用Sobel算子进行边缘检测，Hough变换检测直线并确定斜率，最后通过旋转公式对二维码进行旋转[9-10]；姚林昌等提出了一种Data Matrix码的快速识别方法，通过形状因子检测出矩形，定位边界，得到旋转角度，再通过放射变化恢复出原始Data Matrix码[3]；随后，车怡提出了一种通用于一维码和二维码的倾斜校正算法，找到图像的顶点坐标，确定条码图像的四条边所在直线，并通过数学方法得到条码的中心坐标，所有直线的方差所构成的集合中，找到方差最小的直线，计算斜率，得到旋转角度β，再将中心坐标作为参考系的原点，并得到四个顶点在变换之后的坐标，整体旋转β角度恢复出原始坐标。这些方法都没有考虑到Data Matrix码的特性。传统的二维条码倾斜校正算法，只是将图像由倾斜的不规则四边形旋转成标准的矩形，无法保证Data Matrix码的定位符“L”位于整个条码的左下角位置，即正方向向上。为之后的识别带来一定障碍[4]。因此，本文基于Data Matrix码的结构特性，在确保定位符“L”位于条码左下角的基础下，对其进行倾斜校正，便于之后的字符分割和条码识别。

1Data Matrix码的倾斜校正描述

Data Matrix码的图形可分为定位符号和数据区两部分，如图1所示。

Data Matrix码的定位符号是由两条实现边组成的“L”形和与其相对的两条虚边组成；数据区是由1/0模块组成的矩形。为了减少Data Matrix码在识别过程中消耗的时间，提高识别效率，首先需要对采集到的Data Matrix码图像进行预处理操作其中包括图像的灰度化，二值化以及图像滤波，之后对图像进行边缘检测和直线检测，对Data Matrix码定位符“L”进行定位、并判定倾斜角度和旋转方向，最后旋转Data Matrix条码图像，进行Data Matrix码的倾斜校正，为之后的识别条码和读取数据信息做好准备工作。

2本文的Data Matrix码的倾斜校正算法

传统的算法大都是先利用Sobel算子对图像进行边缘检测，再利用Hough变换确定直线，进而求出倾斜角，但是由于Data Matrix码的图像是标准矩形，传统算法只能保证让它恢复成矩形，并不能保证定位符“L”位于图形左下端。若经过传统算法倾斜校正后定位符“L”并未旋转至图形左下端，则需要重新计算倾斜角，这不仅会增加识读过程的工作量，而且对Data Matrix码的识别造成一定困难。而本文所用的算法是在用LoG算子进行边缘检测之后，首先确定定位符“L”的位置，再通过向量叉乘的方法计算Data Matrix码的旋转角度，确定旋转方向。这样，经过一次旋转后就可以得到标准的Data Matrix码，减少了倾斜校正的工作量。

21边缘检测

通用的边缘检测算子有Prewitt、Sobel、Roberts和Canny等等，这些算子都是利用求导来计算边缘特征的[11]。Prewitt算子是Sobel算子的基础，效果不如Sobel算子；Roberts算子不能抑制噪声；Canny算子虽然处理效果好，去噪能力强，但是计算量较大，在图像处理时所用时间过长[12-13]。因此，选择Sobel算子和LoG算子效果较好，因为他们能同时满足对图像规则边缘的检测以及实时性的要求，但是Sobel算子检测的边缘较粗，并非各向同性而且定位不够精确，得到的图像有时会有一定程度的断开[14-15]；LoG算子先对原始平滑图像进行平滑处理，最大程度的抑制噪声，之后再提取边缘，得到的图像效果更好，而且它是各向同性的，用LoG算子处理后的图像具有较高的清晰度并且具有连贯性[16-17]。因此，本文选用LoG算子进行边缘检测结果如图2所示。其中图2（a）为原图，图2（b）为二值化后的图像，对二值化后的Data Matrix码的边缘检测结果如图2（c）。

22Hough变换检测直线

在对二值化后的Data Matrix码图像利用LoG算子进行边缘检测后，需要进行直线检测来确定定位符“L”的位置。通过Hough变换检测和定位直线是非常有效和常用的方法，它利用图像的全局特征直接检测目标轮廓[18-19]。Hough变换能对已知形状的目标进行检测，受噪声影响非常小，具有很强的抗干扰能力，并且允许待检测边界的不连续，且可以并行处理，并且不会受图像中直线走向的局限，因而鲁棒性较好[20]。使用Hough变换检测Data Matrix码“L”型边界，有显著效果。

Hough变换的基本原理，就是在参数空间和图像空间之间建立起“线-点”的对偶性，然后根据这种对偶性，将图像空间中直线检测问题转化为参数空间中点的检测问题。

假定二维数字图像用直角坐标系表示，对于图像上的一条直线，可用斜截式表示为

y=kx+b

其中：k为该直线的斜率；b为该直线在纵轴Y轴上的截距，如图3所示。相应的，这条参数的直线方程可以表示为

ρ=xcosθ+ysinθ

其中：θ为该直线的垂线与X轴的夹角；ρ为该直线到远点的距离。这种方法使直线的Hough空间可以限制在一个有限的范围内，因而使得计算可行[9]。

由图3可以看出，这条直线在ρ-θ平面中表示成一点（ρ，θ），而直线上的每一个点，在ρ-θ平面中都为一条直线。对于每一个θ值，对图像上的非零（黑色）像素点用公式ρ=xcosθ+ysinθ进行计算，然后在（ρ，θ）的一个计数矩阵P中进行累加。由于X-Y平面上同一条直线上所有的点均满足共线关系，在经过Hough变换后，由X-Y平面中直线上的点转换到ρ-θ参数空间中的一簇正弦曲线都会相交于一点。因此，（ρ，θ）矩阵中必然存在一个峰值，这个峰值处就对应着X-Y平面中的最长直线，即：Data Matrix 码的定位符“L”所在的直线。

Hough变换检测直线的方法如下：

1）设定合适的（ρ，θ）的值，为计数矩阵P分配内存空间，初始化时计数矩阵P中的所有元素均置0。

2）将θ每一个可能的取值带入ρ=xcosθ+ysinθ中计算对应ρ的值，对图像作Hough变换，并在计数矩阵P中相对应的元素处计数值加1，将结果存入计数矩阵P中。

3）设定阈值，即：阈值大于某个数时认为此处存在直线。再找出计数矩阵P中最大累加值所以应的点，那么这个点就对应X-Y平面中的最长直线，根据Data Matrix码的结构特征可以判断，这条直线就是定位符“L”的边缘线之一，运用相同的方法，可得到定位符“L”的另一条边缘线所在直线。

通过Hough变换的直线检结果如图4，其中图4（a）为计数矩阵P中的两个峰值点，图4（b）为检测到Data Matrix码的定位符“L”所在位置。

23Data Matrix码旋转算法

通过普通电子设备采集到的Data Matrix碼通常具有一定程度的倾斜，将 Data Matrix码旋转还原成原始的二维条码形状，并非简单地将条码图像旋转至水平位置，而是需要将Data Matrix码的定位符“L”旋转至它的左下方位置。因此，本文采用向量叉乘的方法计算Data Matrix码的旋转角度。该方法通过 Data Matrix码的“L”型探测图形的端点构成两个向量。利用这个特征，仅用一次旋转，就可以将Data Matrix码的定位符“L”旋转至 Data Matrix码的左下方位置。

Data Matrix码的正确旋转角度具体方法如下：

通过Hough变换检测直线，可以得到定位符“L”3个端点的坐标（xi，yi）（i=1，2，3），分别用两个向量表示Data Matrix码的定位符“L”的两条边，将两条边的交点，作为两个向量的起点。两个向量分别可以表示为：u=[x1-x3，y1-y3，0]，v=[x2-x3，y2-y3，0]，则它们的叉积为：w=u×v=[0，0，（x1-x3）（y2-y3）-（x2-x3）（y1-y3）]。

若（x1-x3）（y2-y3）-（x2-x3）（y1-y3）>0，则按照图5（a）的情況将Data Matrix码旋转θ1角度。

若（x1-x3）（y2-y3）-（x2-x3）（y1-y3）<0，则按照图5（b）的情况将Data Matrix码旋转θ2角度。

根据定位后的结果，可以得到Data Matrix码的倾斜角度θ，将θ带入图像旋转公式中：

x′y′=cosθsinθ-sinθcosθxy

其中：θ为旋转角度；θ绕基准点旋转，逆时针为正，顺时针为负；x，y代表旋转前像素的坐标值；x′，y′代表旋转后映射图像所对应像素的坐标值。

24条码校正

在条码图像旋转之前，图像上所采集到的坐标值均为整数，而旋转后的图像通过某种变换之后，会得到一些浮点型的坐标值，从而导致旋转后的图像产生几何失真现象。因此本文在变换过程中采用双线性插值法对旋转后的二维码插值，消除旋转后带来的毛刺及空白点。该方法利用待求像素四个相邻点的灰度在两个方向上作线性插值。设（x′+u，y′+v）为变换后的坐标，其中x′、y′为变换后的坐标中所对应的整数部分，u、v为变换后的小数部分。变换后的坐标所对应像素点的值f（x′+u，y′+v）可由原图中没有变换的像素点以及这个像素点周围的其他3个像素点的值来决定，这4个点的坐标分别为（x′，y′）、（x′，y′+1）、（x′+1，y′+1）、（x′+1，y′），待求像素灰度值的计算如下式：

f（x′+u，y′+v）=（1-u）（1-v）f（x′，y′）+v（1-u）f（x′，y′+1）+u（1-v）f（x′+1，y′）+uvf（x′+1，y′+1）

最终得到复原的Data Matrix码如图6所示：

3验证与结果分析

为了验证本文所提出的倾斜校正算法的可行性与正确性，用普通电子设备随机拍摄若干张Data Matrix码图像，并选择几张具有代表性的Data Matrix码图像，将它们用传统的倾斜校正算法和本文的倾斜校正算法做对比，得到二维码复原图像。实验结果如图7所示。

Data Matrix码的倾斜有上述4种情况，从图7中可看出，运用传统的倾斜校正算法，只能够将Data Matrix码旋转成标准的矩形，而不能保证定位符“L”位于图像左下方，那么就需要继续进行旋转角度的计算与图形旋转，增加了条码识别过程中的工作量和正确校正所需的时间。而运用本文提出的算法，通过对定位符“L”的两条边进行向量叉乘来确定旋转方向和旋转角度，有效防止了上述情况的发生，仅需一次旋转便得到了标准的Data Matrix码图像，节省了工作量，进而提高了Data Matrix码识别的效率。

4结论

探测图形“L”是Data Matrix码的独特结构特征，本文设计了一种基于Data Matrix码这种结构特征的倾斜校正方法。为确保定位符“L”旋转后位于图像左下方，在利用Hough变换检测出定位符“L”后，将定位符“L”的两条边用向量表示后，利用向量叉乘得到旋转角度，确定旋转方向，仅需经过一次旋转就可以得到标准的Data Matrix码图像。这种方法避免了将Data Matrix码进行倾斜校正之后定位符“L”没有处于正确的位置上而需要重新计算倾斜角度并多次进行旋转校正的不足，减少了Data Matrix码识别过程的工作量，提高了识读效率，并为之后字符的正确分割打下基础，可作为Data Matrix码的一种专用倾斜校正方法。

参 考 文 献：

[1]郭淑君 字符二维码识别系统的设计与实现[D]. 吉林： 吉林大学：1-2

[2]Data Matrix码 360百科[DB/OL]. http：//baikesocom/doc/3495444-3677259html ，20160930

[3]姚林昌， 白瑞林， 钱勇， 等 一种Data Matrix条码的快速识别方法[J]. 计算机应用研究， 2011， 28 （11）： 4368-4388

[4]陈春林 基于Android移动终端的二维码识别技术实现与应用研究[D]. 广州：广东工业大学， 2015： 31

[5]蒋凌志 基于Data Matrix 二维条码结构特征的图形校正[J]. 计算机系统应用， 2011， 2（5）：195

[6]王员云， 曾凤生 基于图像处理的手机二维码识别的研究[J]. 乐山师范学院学报， 2015（8）：33-36

[7]李志浩 探索二维码识别在防伪系统中的应用[J]. 电子制作， 2015（5）：80

[8]李雅静 Data Matrix二维条码图像识别的算法研究与实现[D]. 北京： 北京交通大学， 2009： 37

[9]姬飞飞 条码识别技术及其应用[D]. 哈尔滨： 哈尔滨工程大学， 2012： 24-26

[10]车怡 基于图像处理技术的条形码识别系统的研究[D]. 北京： 华北电力大学， 2014：28-30

[11]CIARDIELLO G，SCAFUR G，DEGRANDI MAn Experimental System for Office Document Handling and Text Recognition[C]// Proc International Conference on Pattern Recognition， 2008 ：739-743

[12]RALEVIC N M， DRAZIC S， OBRADOVIC RThe Hough Transformation of Rectangle[C]// Intelligent Systems and Informatics， 2008：1-4

[13]杜志俊 PDF417二维条形码的读取和识别技术[D]. 长沙： 中南大学， 2009： 35-36

[14]邓白云 二维码图像倾斜校正中的算法研究综述[J]. 工业控制计算机， 2016， 29（2）： 77-79

[15]徐向美 车牌自动识别系统中的倾斜校正研究[J]. 科技广场， 2015（2）：12-15

[16]吴丽丽 基于Sobel算子和Radon变换的车牌倾斜校正方法[J]. 计算机应用， 2013， 33（S1）：220-222

[17]TRASER Courtney J， HOFFMAN Leslie A， SEIFERT Mark F， et al Investigating the Use of Quick Response Codes in the Gross Anatomy Laboratory[J]. Anatomical Sciences Education，2014，8（5）：421-428

[18]KARTHIKA M， JAMES A A Novel Approach for Document Image Binarization Using Bitplane Slicing[J]. Procedia Technology， 2015（19）： 758-765

[19]AGGARWAL K， BHAMRAH M S， RYAIT H S The Identification of Liver Cirrhosis with Modified LBP Grayscaling and Otsu Binarization[J].SpringerPlus， 2016， 5（1）： 1

[20]盛曉亮， 刘振基， 喻文， 等 一种基于二维码识别的车载辅助系统设计与实现[J]. 电子制作， 2015（15）：83-84

（编辑：温泽宇）