畸變Data Matrix碼圖像的傾斜校正算法研究

關博熠　董靜薇　馬曉峰　徐博

摘要：針對Data Matrix碼傾斜校正中需要多次旋轉的問題，本文提出了一種畸變二維碼傾斜校正方法。首先使用LoG算子對二值化后的圖像進行邊緣檢測，再基于Data Matrix碼的結構特征，通過Hough變換有效快速地確定定位符“L”所在的位置，并將“L”型交點用兩條向量表示。然后通過向量叉乘計算出Data Matrix碼的旋轉角度、確定旋轉方向，只需一次旋轉即可實現(xiàn)傾斜校正。本文算法節(jié)省了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碼的尺寸可任意調(diào)整，大多數(shù)條碼的大小與編入的資料量有著絕對關系，但Data Matrix碼的尺寸與其編入的資料量卻相互獨立，因此它的尺寸較有彈性[5]，目前它的最小尺寸是所有條碼中最小的，尤其適用于小零件標識，并且可以直接印在實體上；因而被廣泛應用于標識集成電路、藥品等小件物品以及制造業(yè)的流水線生產(chǎn)過程，因此，對Data Matrix碼的研究有著極為重要的現(xiàn)實意義[6]。

二維條碼的識讀過程是整個二維碼識別系統(tǒng)的重要組成部分[7-8]，二維條碼的傾斜會導致二維條碼在符號字符提取時被錯誤分割，從而影響符號字符提取的效果，因此，需要對拍攝過程中產(chǎn)生畸變的二維條碼進行傾斜校正，以便于之后二維條碼的正確分割。杜志俊運用Sobel算子進行邊緣檢測，Hough變換檢測直線并確定斜率，最后通過旋轉公式對二維碼進行旋轉[9-10]；姚林昌等提出了一種Data Matrix碼的快速識別方法，通過形狀因子檢測出矩形，定位邊界，得到旋轉角度，再通過放射變化恢復出原始Data Matrix碼[3]；隨后，車怡提出了一種通用于一維碼和二維碼的傾斜校正算法，找到圖像的頂點坐標，確定條碼圖像的四條邊所在直線，并通過數(shù)學方法得到條碼的中心坐標，所有直線的方差所構成的集合中，找到方差最小的直線，計算斜率，得到旋轉角度β，再將中心坐標作為參考系的原點，并得到四個頂點在變換之后的坐標，整體旋轉β角度恢復出原始坐標。這些方法都沒有考慮到Data Matrix碼的特性。傳統(tǒng)的二維條碼傾斜校正算法，只是將圖像由傾斜的不規(guī)則四邊形旋轉成標準的矩形，無法保證Data Matrix碼的定位符“L”位于整個條碼的左下角位置，即正方向向上。為之后的識別帶來一定障礙[4]。因此，本文基于Data Matrix碼的結構特性，在確保定位符“L”位于條碼左下角的基礎下，對其進行傾斜校正，便于之后的字符分割和條碼識別。

1Data Matrix碼的傾斜校正描述

Data Matrix碼的圖形可分為定位符號和數(shù)據(jù)區(qū)兩部分，如圖1所示。

Data Matrix碼的定位符號是由兩條實現(xiàn)邊組成的“L”形和與其相對的兩條虛邊組成；數(shù)據(jù)區(qū)是由1/0模塊組成的矩形。為了減少Data Matrix碼在識別過程中消耗的時間，提高識別效率，首先需要對采集到的Data Matrix碼圖像進行預處理操作其中包括圖像的灰度化，二值化以及圖像濾波，之后對圖像進行邊緣檢測和直線檢測，對Data Matrix碼定位符“L”進行定位、并判定傾斜角度和旋轉方向，最后旋轉Data Matrix條碼圖像，進行Data Matrix碼的傾斜校正，為之后的識別條碼和讀取數(shù)據(jù)信息做好準備工作。

2本文的Data Matrix碼的傾斜校正算法

傳統(tǒng)的算法大都是先利用Sobel算子對圖像進行邊緣檢測，再利用Hough變換確定直線，進而求出傾斜角，但是由于Data Matrix碼的圖像是標準矩形，傳統(tǒng)算法只能保證讓它恢復成矩形，并不能保證定位符“L”位于圖形左下端。若經(jīng)過傳統(tǒng)算法傾斜校正后定位符“L”并未旋轉至圖形左下端，則需要重新計算傾斜角，這不僅會增加識讀過程的工作量，而且對Data Matrix碼的識別造成一定困難。而本文所用的算法是在用LoG算子進行邊緣檢測之后，首先確定定位符“L”的位置，再通過向量叉乘的方法計算Data Matrix碼的旋轉角度，確定旋轉方向。這樣，經(jīng)過一次旋轉后就可以得到標準的Data Matrix碼，減少了傾斜校正的工作量。

21邊緣檢測

通用的邊緣檢測算子有Prewitt、Sobel、Roberts和Canny等等，這些算子都是利用求導來計算邊緣特征的[11]。Prewitt算子是Sobel算子的基礎，效果不如Sobel算子；Roberts算子不能抑制噪聲；Canny算子雖然處理效果好，去噪能力強，但是計算量較大，在圖像處理時所用時間過長[12-13]。因此，選擇Sobel算子和LoG算子效果較好，因為他們能同時滿足對圖像規(guī)則邊緣的檢測以及實時性的要求，但是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變換能對已知形狀的目標進行檢測，受噪聲影響非常小，具有很強的抗干擾能力，并且允許待檢測邊界的不連續(xù)，且可以并行處理，并且不會受圖像中直線走向的局限，因而魯棒性較好[20]。使用Hough變換檢測Data Matrix碼“L”型邊界，有顯著效果。

Hough變換的基本原理，就是在參數(shù)空間和圖像空間之間建立起“線-點”的對偶性，然后根據(jù)這種對偶性，將圖像空間中直線檢測問題轉化為參數(shù)空間中點的檢測問題。

假定二維數(shù)字圖像用直角坐標系表示，對于圖像上的一條直線，可用斜截式表示為

y=kx+b

其中：k為該直線的斜率；b為該直線在縱軸Y軸上的截距，如圖3所示。相應的，這條參數(shù)的直線方程可以表示為

ρ=xcosθ+ysinθ

其中：θ為該直線的垂線與X軸的夾角；ρ為該直線到遠點的距離。這種方法使直線的Hough空間可以限制在一個有限的范圍內(nèi)，因而使得計算可行[9]。

由圖3可以看出，這條直線在ρ-θ平面中表示成一點（ρ，θ），而直線上的每一個點，在ρ-θ平面中都為一條直線。對于每一個θ值，對圖像上的非零（黑色）像素點用公式ρ=xcosθ+ysinθ進行計算，然后在（ρ，θ）的一個計數(shù)矩陣P中進行累加。由于X-Y平面上同一條直線上所有的點均滿足共線關系，在經(jīng)過Hough變換后，由X-Y平面中直線上的點轉換到ρ-θ參數(shù)空間中的一簇正弦曲線都會相交于一點。因此，（ρ，θ）矩陣中必然存在一個峰值，這個峰值處就對應著X-Y平面中的最長直線，即：Data Matrix 碼的定位符“L”所在的直線。

Hough變換檢測直線的方法如下：

1）設定合適的（ρ，θ）的值，為計數(shù)矩陣P分配內(nèi)存空間，初始化時計數(shù)矩陣P中的所有元素均置0。

2）將θ每一個可能的取值帶入ρ=xcosθ+ysinθ中計算對應ρ的值，對圖像作Hough變換，并在計數(shù)矩陣P中相對應的元素處計數(shù)值加1，將結果存入計數(shù)矩陣P中。

3）設定閾值，即：閾值大于某個數(shù)時認為此處存在直線。再找出計數(shù)矩陣P中最大累加值所以應的點，那么這個點就對應X-Y平面中的最長直線，根據(jù)Data Matrix碼的結構特征可以判斷，這條直線就是定位符“L”的邊緣線之一，運用相同的方法，可得到定位符“L”的另一條邊緣線所在直線。

通過Hough變換的直線檢結果如圖4，其中圖4（a）為計數(shù)矩陣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角度。

根據(jù)定位后的結果，可以得到Data Matrix碼的傾斜角度θ，將θ帶入圖像旋轉公式中：

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

其中：θ為旋轉角度；θ繞基準點旋轉，逆時針為正，順時針為負；x，y代表旋轉前像素的坐標值；x′，y′代表旋轉后映射圖像所對應像素的坐標值。

24條碼校正

在條碼圖像旋轉之前，圖像上所采集到的坐標值均為整數(shù)，而旋轉后的圖像通過某種變換之后，會得到一些浮點型的坐標值，從而導致旋轉后的圖像產(chǎn)生幾何失真現(xiàn)象。因此本文在變換過程中采用雙線性插值法對旋轉后的二維碼插值，消除旋轉后帶來的毛刺及空白點。該方法利用待求像素四個相鄰點的灰度在兩個方向上作線性插值。設（x′+u，y′+v）為變換后的坐標，其中x′、y′為變換后的坐標中所對應的整數(shù)部分，u、v為變換后的小數(shù)部分。變換后的坐標所對應像素點的值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碼圖像，將它們用傳統(tǒng)的傾斜校正算法和本文的傾斜校正算法做對比，得到二維碼復原圖像。實驗結果如圖7所示。

Data Matrix碼的傾斜有上述4種情況，從圖7中可看出，運用傳統(tǒng)的傾斜校正算法，只能夠?qū)ata Matrix碼旋轉成標準的矩形，而不能保證定位符“L”位于圖像左下方，那么就需要繼續(xù)進行旋轉角度的計算與圖形旋轉，增加了條碼識別過程中的工作量和正確校正所需的時間。而運用本文提出的算法，通過對定位符“L”的兩條邊進行向量叉乘來確定旋轉方向和旋轉角度，有效防止了上述情況的發(fā)生，僅需一次旋轉便得到了標準的Data Matrix碼圖像，節(jié)省了工作量，進而提高了Data Matrix碼識別的效率。

4結論

探測圖形“L”是Data Matrix碼的獨特結構特征，本文設計了一種基于Data Matrix碼這種結構特征的傾斜校正方法。為確保定位符“L”旋轉后位于圖像左下方，在利用Hough變換檢測出定位符“L”后，將定位符“L”的兩條邊用向量表示后，利用向量叉乘得到旋轉角度，確定旋轉方向，僅需經(jīng)過一次旋轉就可以得到標準的Data Matrix碼圖像。這種方法避免了將Data Matrix碼進行傾斜校正之后定位符“L”沒有處于正確的位置上而需要重新計算傾斜角度并多次進行旋轉校正的不足，減少了Data Matrix碼識別過程的工作量，提高了識讀效率，并為之后字符的正確分割打下基礎，可作為Data Matrix碼的一種專用傾斜校正方法。

參 考 文 獻：

[1]郭淑君 字符二維碼識別系統(tǒng)的設計與實現(xiàn)[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移動終端的二維碼識別技術實現(xiàn)與應用研究[D]. 廣州：廣東工業(yè)大學， 2015： 31

[5]蔣凌志 基于Data Matrix 二維條碼結構特征的圖形校正[J]. 計算機系統(tǒng)應用， 2011， 2（5）：195

[6]王員云， 曾鳳生 基于圖像處理的手機二維碼識別的研究[J]. 樂山師范學院學報， 2015（8）：33-36

[7]李志浩 探索二維碼識別在防偽系統(tǒng)中的應用[J]. 電子制作， 2015（5）：80

[8]李雅靜 Data Matrix二維條碼圖像識別的算法研究與實現(xiàn)[D]. 北京： 北京交通大學， 2009： 37

[9]姬飛飛 條碼識別技術及其應用[D]. 哈爾濱： 哈爾濱工程大學， 2012： 24-26

[10]車怡 基于圖像處理技術的條形碼識別系統(tǒng)的研究[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]. 工業(yè)控制計算機， 2016， 29（2）： 77-79

[15]徐向美 車牌自動識別系統(tǒng)中的傾斜校正研究[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]盛曉亮， 劉振基， 喻文， 等 一種基于二維碼識別的車載輔助系統(tǒng)設計與實現(xiàn)[J]. 電子制作， 2015（15）：83-84

（編輯：溫澤宇）