王雄華，張 昕＋，朱同林

（1.華南農(nóng)業(yè)大學(xué) 理學(xué)院，廣東 廣州510642；2.華南農(nóng)業(yè)大學(xué) 圖像圖形研究中心，廣東 廣州510642）

0 引 言

在實際應(yīng)用中，通過手機、攝像機等設(shè)備采集快速響應(yīng)碼 （QR code）［1，2］圖像信息時，往往會存在光照不均勻、幾何形變等情況，給快速響應(yīng)碼的識別帶來不便。因此，如何快速有效地提取和識別QR 碼成為人們研究的熱點。目前已有很多針對QR 碼圖像不同特性的校正方法，如張名等［3］、陳威兵等［4］利用位置探測圖形特性進行頂點定位及校正，熊用等［5］提出的基于相關(guān)匹配的QR 碼校正方法，以及文獻 ［6－8］給出的條碼校正識別方法等。通過實驗發(fā)現(xiàn)，在條碼識別應(yīng)用中，這些校正方法要么在對頂點定位時存在明顯的局限性，要么校正所需時間過長，無法滿足其實時性的需求。針對條碼識讀對識別成功率和解碼時間等的特殊要求，本文提出一種低復(fù)雜度的頂點尋址算法，

1 QR 碼圖像特征及應(yīng)用

1.1 QR 碼特征

QR 碼符號是由正方形模塊堆疊而成的正方形陣列碼，它由編碼區(qū)域以及包括位置探測圖形、分隔符、定位圖形和校正圖形的功能圖形組成，條碼四周有分隔空白區(qū)，如圖1所示。

圖1 QR 碼結(jié)構(gòu)

1.2 圖像特征的應(yīng)用

（1）在實際應(yīng)用中，QR 碼圖像四周為一定間距的分隔空白區(qū)域。從空白區(qū)域自外向內(nèi)進行行掃描，能快速尋找到QR 碼邊界的黑色像素點；

（2）3個 “回”字型位置探測圖形分別位于QR 碼圖像的左上、右上和左下位置，通過手機、攝像機等采集QR碼圖像時，發(fā)生一定的幾何形變，3 個位置探測圖形在圖像中的相對位置不發(fā)生變化；

（3）位置探測圖形與編碼區(qū)域之間存在一定間距的分隔符，即位置探測圖形與編碼區(qū)域之間沒有相鄰拼接的黑色像素點。

2 圖像二值化

在QR 碼識讀應(yīng)用中，能否通過對圖像二值化來獲取正確的條碼黑白模塊序列信息是譯碼正確與否的重要組成部分，因此圖像的二值化效果將直接影響到其能否成功識讀解碼。對圖像的二值化首先需要確定閾值的大小，最為常見且有效的全局閾值處理方法是Otsu算法。但手機、攝像機等設(shè)備在采集QR 碼圖像時，容易受外界環(huán)境影響而發(fā)生光照不均勻現(xiàn)象。這時該方法在背景照明不均勻時有可能失效［10］。本文采用灰度圖像形態(tài)學(xué)法和Otsu算法相結(jié)合，從而完成QR 碼圖像的二值化。

二值化具體步驟如下：①首先對圖像進行灰度轉(zhuǎn)換，得到灰度圖像；②對灰度圖像進行閉運算操作；③將閉運算后的圖像減去原灰度圖，即做底帽變換；④采用Otsu算法對底帽變換后的圖像二值化。

二值化效果如圖2所示。圖2 （a）為原圖，圖2 （b）為直接采用Otsu算法處理后的二值化圖，圖2 （c）為采用灰度圖像形態(tài)學(xué)法和Otsu算法處理后的二值化圖。從圖2可知，采用灰度圖像形態(tài)學(xué)法和Otsu算法相結(jié)合，其二值化效果更好。

圖2 二值化對比效果

3 QR 碼頂點獲取

對條碼進行幾何校正，首先需要獲取失真QR 碼圖像的4個頂點坐標。實際應(yīng)用中，在采集QR 碼圖像時，一般情況下，條碼的水平傾斜角不會過大，即發(fā)生幾何形變時，3個位置探測圖形在圖像中的相對位置不發(fā)生變化。在行掃描進行頂點尋址過程中引入冗余點剔除，能有效地降低冗余點對頂點定位造成的影響，從而準確獲取QR 碼左上、右上和左下頂點。另外，由于位置探測圖形與編碼區(qū)域之間沒有相鄰拼接的黑色像素點，通過對邊界黑色像素點的等間隔抽樣，構(gòu)造像素點斜率偏離度容錯處理判斷，可以快速找到第4個頂點坐標。

3.1 快速獲取3個頂點

按先后順序分別從QR 碼分隔空白區(qū)域的正上，正左，正下，正右，左上，左下，右上7 個方向出發(fā)，由外向內(nèi)進行直線掃描。當直線與QR 碼出現(xiàn)至少一個交點時，掃描結(jié)束，依次可得到第1，2，…，7 條掃描直線。基于點線相交關(guān)系，在7 個方向上，掃描直線與幾何失真的QR碼有3種出現(xiàn)交點的相交情況，如圖3所示。

圖3 掃描直線與QR 碼相交

3種相交情況分別為：圖 （a）情況代表QR 碼發(fā)生順時針偏轉(zhuǎn)；圖 （b）情況代表發(fā)生逆時針偏轉(zhuǎn)；圖 （c）情況代表QR 碼無明顯偏轉(zhuǎn)。

當掃描直線與幾何失真的QR 碼相交屬于第 （a）種或第 （b）種情況時，有且僅有一個交點；當相交屬于第 （c）種情況時，保留第一個交點和最后一個交點。7 個方向掃描結(jié)束后，最多可以得到14個交點。

在實際圖像應(yīng)用中，當掃描直線與失真QR 碼邊界的斜率較接近或發(fā)生像素偏移時，掃描時圖3第 （a）種與第（b）種情況也會出現(xiàn)多個交點 （如圖4所示），當出現(xiàn)交點個數(shù)大于等于2時，保留兩個交點 （第一個交點和最后一個交點），并對這兩個交點進行冗余點判斷與剔除。

圖4 相交點放大

冗余點剔除過程 （redundant－point－elimination）如下：

（1）當從正上方向掃描時，存在圖5兩種保留兩個交點且其中一個是冗余點的情況；

圖5 正上掃描兩個交點情況

在圖5 （a）和圖5 （b）中，從正上方向掃描結(jié)束時，保留第一個和最后一個頂點，其中一個頂點是冗余點，通過距離最短可剔除該冗余點，圖6 （a）和圖6 （b）為相應(yīng)的距離，其中A，B和C分別為圖中的角點坐標。由距離判斷，A到K1的距離L1小于A 到K2的距離L2，圖6 （a）中可剔除冗余點K2；同理圖6 （b）中可剔除冗余點K3。

同理，正左，正下與正右方向類似。

圖6 位置探測圖形距離

（2）當從左上方向掃描時，只存在圖7一種保留兩個交點的情況。

圖7 左上掃描兩個交點情況

在圖7中，從左上方向掃描結(jié)束時，保留第一個和最后一個頂點，通過以下規(guī)則進行冗余點判斷與剔除：①如果兩個交點與相鄰第1或第2條掃描線的其中一條掃描直線有且僅有一個相交點，則保留該相交點坐標，另一不相交的點坐標剔除；②如果兩個交點與相鄰第1和第2條掃描線均存在相交點，則保留兩個交點坐標；③如果兩個交點與相鄰第1和第2條掃描線均無相交點，保留兩個交點坐標。同理，左下和右上方向類似。

由前文的介紹可知傳統(tǒng)校正算法在進行頂點定位時，要么存在較明顯的局限性，要么定位所需的時間太長不能滿足實時性需求。綜合考慮條碼校正時頂點定位精確度和實時性的需求，本文基于冗余點剔除過程，提出如下的Find3Vertices算法，用于獲取條碼左上、右上和左下頂點，具體步驟如下：

步驟1 按先后次序分別從QR 碼空白區(qū)域的7個方向出發(fā)，由外向內(nèi)進行直線掃描，當與QR 碼出現(xiàn)至少一個交點時，掃描結(jié)束。

步驟2 當從正上方向掃描結(jié)束時，若掃描直線與QR碼只有一個交點，則保留該點坐標；若與QR 碼存在多個交點，保留第一個和最后一個交點。同理保留正左、正下和正右方向的交點。

步驟3 當從左上方向掃描結(jié)束時，若掃描直線與QR碼只有一個交點，則保留該點坐標；若與QR 碼存在多個交點，則采用本文提出的冗余點剔除過程 （2）選擇性保留交點。同理保留左下和右上方向的交點。

步驟4 記步驟2 和步驟3 保留的所有交點為P（xi，yi），i＝1，2，…，k。分別計算P（xi，yi）和圖6中角點坐標A（0，0）的距離，與A 距離最近的交點即為左上頂點P1。同理與角點B（0，n），C（m，0）距離最短的交點記為P2，P3。（注：圖像大小為m（n））。

步驟5 輸出頂點坐標P1，P2，P3，則程序結(jié)束。

圖8為采用Find3Vertices算法獲取9種典型情形的頂點坐標的QR 碼圖像。

9種典型情形分別為：圖8 （a）順時針小角度偏轉(zhuǎn)，采集角度方向偏右；圖8 （b）順時針較大角度偏轉(zhuǎn)，采集角度方向偏下；圖8 （c）順時針小角度偏轉(zhuǎn)，采集角度方向偏左；圖8 （d）順時針小角度偏轉(zhuǎn)，采集角度方向偏上；圖8 （e）無明顯偏轉(zhuǎn)，采集角度方向偏左；圖8 （f）逆時針小角度偏轉(zhuǎn)，采集角度方向偏上；圖8 （g）逆時針小角度偏轉(zhuǎn)，采集角度方向偏下；圖8 （h）逆時針小角度偏轉(zhuǎn)，采集角度方向偏左；圖8 （i）逆時針較大角度偏轉(zhuǎn)，采集角度方向偏右。

3.2 第四個頂點獲取

在QR 碼中，由于QR 碼右下方屬于編碼區(qū)域，那么在編碼時，右下角的第四個頂點可能會出現(xiàn)不存在的情況，因此無法采用本文的Find3Vertices算法獲取。

圖8 Find3Vertices算法頂點獲取

而在QR 碼右上方和左下方均存在一個 “回”字型位置探測圖形，發(fā)生幾何形變時，該位置探測圖形的邊界仍保持近似直線?；谏衔囊勋@取的右上頂點坐標P2和左下頂點坐標P3，通過對邊界黑色像素點等間隔抽樣和像素點斜率偏離度容錯處理判斷，采用最小二乘法來獲取第四個頂點坐標P4。

FindtheForthVertex算法步驟如下：

步驟1 采用Find3Vertices算法獲取QR 碼右上頂點P2（xB，yB）和左下頂點P3（xC，yC）。

步驟2 以P2為基準點，從P2右方的分隔空白區(qū)域出發(fā)，往下隔5行進行由外向內(nèi)的水平掃描，當與QR 碼邊界的第一個黑色像素點Pi（xi，yi）相交時，掃描結(jié)束，并將坐標Pi存入數(shù)組V。

步驟3 計算斜率L＝ （yi－yB）／ （xi－xB）。

步驟4 以Pi為基準點，往下隔5行繼續(xù)進行水平掃描，當與邊界的第一個黑色像素點Pi＋1（xi＋1，yi＋1）相交時，掃描結(jié)束。

步驟5 計算斜率L1＝ （yi＋1－yi）／ （xi＋1－xi）。

步驟6 如果偏離度｜L1－L｜≤0.5，則Pi＋1加入數(shù)組V，重置Pi＝Pi＋1，L＝L1，返回步驟4。否則輸出數(shù)組V。

步驟7 同理，以P3為基準點，可求取QR 碼下方邊界黑色像素點數(shù)組W。在計算斜率時，由于其分母會出現(xiàn)0的情況，這里先對像素點做90°旋轉(zhuǎn)，即計算斜率的倒數(shù)1／L2。

步驟8 分別對數(shù)組V 和W 采用最小二乘法求取直線方程，輸出兩條直線方程的相交點P4，則程序結(jié)束。

圖9為采用FindtheForthVertex算法獲取圖8所示情形的第4個頂點坐標的QR 碼圖像。

圖9 FindtheForthVertex算法頂點獲取

4 QR 碼校正實現(xiàn)

本文采用逆投影變換對幾何失真的QR 碼進行坐標變換，變換公式如式 （1）所示

其中，（X，Y）為幾何失真的QR 碼坐標，（x，y）為校正后的正方形圖像坐標。將失真圖像中的4 個頂點P1，P2，P3和P4還原成正方形圖像頂點P1’，P2’，P3’和P4’，整理可得

式 （2）中k0～k7未知參數(shù)可從上述方程組聯(lián)合求解得到，從而實現(xiàn)從不規(guī)則四邊形到正方形的坐標變換校正。

但由于式 （1）中計算得到的 （X，Y）一般不是整數(shù)，即校正后QR 碼在原失真圖像中所對應(yīng)的像素其坐標不是整數(shù)。而計算機只保存整數(shù)坐標的圖像像素值，這會導(dǎo)致校正后的坐標在原圖中，也無法獲取準確的灰度值。這時需要采用灰度插值。常見插值方法有最鄰近插值，雙線性插值和雙三次內(nèi)插。本文折中采取雙線性插值完成圖像的像素值填充，如圖10 （b）所示。

從圖10 （b）可看出，校正后的QR 碼邊緣存在較明顯的鋸齒化，不利于信息準確提取。由于QR 碼模塊規(guī)模一般至少為3×3像素單位，故這里構(gòu)造光滑算子邊長為3的方形結(jié)構(gòu)元，依次采用數(shù)學(xué)形態(tài)學(xué)法的開運算和閉運算對圖像進行邊緣平滑［10］，得到最終的校正圖像，如圖10（c）所示。

圖10 校正效果

5 實驗結(jié)果與分析

為了使實驗更加具有普遍性，本文采用較為廣泛的聊天攝像頭 （30萬像素）進行條碼圖像采集。本次實驗共采集到480幅分辨率為640×480的QR 碼圖像，其中拍攝角度方向偏上、偏下、偏左和偏右分別120 幅，實驗環(huán)境設(shè)計如下：①條碼模塊像素點規(guī)模變化，采用模塊像素點分別為3×3，5×5的QR 碼；②條碼模塊數(shù)變化，采用模塊數(shù)分別為21×21，25×25，…，49×49等8種常見的QR碼；③光照不均勻變化，采用偏亮和偏暗的光照環(huán)境。在AMD Athlon X2 2.80GHz的計算機上對收集的QR 碼圖像，采用本文算法在Matlab軟件上進行校正測試。實驗數(shù)據(jù)見表1。

表1 實驗數(shù)據(jù)統(tǒng)計結(jié)果

傳統(tǒng)算法在對QR 碼進行識別定位時，一般采用Hough變換進行邊緣檢測或者基于位置探測圖形中1∶1∶3∶1∶1的深淺模塊交替排列特征進行頂點定位。由于QR碼邊界不連續(xù)，采用Hough變換檢測邊緣往往誤差較大，另外，Hough變換直線檢測法屬于窮盡式搜索，難于滿足QR 碼識別實時性的要求。而當采集裝置與條碼平面的相對角度過大時，在位置探測圖形中，深淺模塊1∶1∶3∶1∶1交替排列的特征也無法得到保證。

相比較于傳統(tǒng)算法，本文算法在對QR 碼進行頂點定位時，避免了Hough變換等高運算量方法，從QR 碼的圖像特征出發(fā)，提出一種低復(fù)雜度的頂點尋址算法，能準確獲取到失真圖像的頂點坐標，經(jīng)過校正與譯碼處理，平均識別成功率達92.9%，平均處理時間為1.58s，遠高于國標QR 碼校正檢測方法71%的平均成功率［5］。其中部分圖像無法正確識別的主要原因有：①由于拍攝QR 碼時距離過近，圖像出現(xiàn)模糊重疊現(xiàn)象，導(dǎo)致部分信息丟失；②在強光下，曝光過度的QR 碼圖像二值化不能達到很好的效果，導(dǎo)致頂點尋址時無法準確定位。

圖11為采用本文算法校正的部分QR 碼圖像。

圖11 校正效果

6 結(jié)束語

針對采集QR 碼圖像發(fā)生光照不均勻、幾何形變等情況，提出了一種校正算法，能夠有效地克服各種明暗光照影響問題，快速獲取到失真條碼的頂點，使整個算法能夠在相對短的時間內(nèi)達到較高的校正識別成功率。通過對實際QR 碼圖像的測試不難看出，該算法抗環(huán)境干擾能力較強，在進行行掃描時引入冗余點剔除過程，能有效降低冗余點對頂點定位造成的影響，同時結(jié)合邊界像素點間隔抽樣和斜率偏離度容錯處理，對不同拍攝角度方向的圖像都能取得較好的頂點定位，為后續(xù)的QR 碼校正及識讀提供保障。同時該算法校正所需的時間較短，滿足了QR 碼識讀應(yīng)用對實時性的需求，因此可應(yīng)用到包括嵌入式、手持式終端設(shè)備等的條碼識讀應(yīng)用中。

［1］XU Ling，JIANG Xinzhi，ZHANG Jie.The design and imple－mentation of mobile QR code identification system ［J］.Journal of Computer Application，2012，32 （5）：1474－1476 （in Chinese）.［徐玲，蔣欣志，張杰.手機二維碼識別系統(tǒng)的設(shè)計與實現(xiàn) ［J］.計算機應(yīng)用.2012，32 （5）：1474－1476.］

［2］LIU Ningzhong，SU Jun，SUN Han.Industrial control environment QR Code detection and recognition algorithm ［J］.Journal of Electronic，2011，39 （10）：2459－2463 （in Chinese）.［劉寧鐘，蘇軍，孫涵.工業(yè)控制環(huán)境中QR Code的檢測和識別算法 ［J］.電子學(xué)報，2011，39 （10）：2459－2463.］

［3］Chen Changsheng，Alex C Kot，Yang Huijuan.A two－stage quality measure for mobile phone captured 2D barcode images［J］.Pattern Recognition，2013，46 （9）：2588－2598.

［4］ZHANG Ming，ZHENG Jianli.QR code recognition algorithm based on the characteristics of symbols ［J］.Computer Engineering，2011，37 （4）：278－280 （in Chinese）.［張名，鄭建立.基于符號特征的QR 碼識別算法 ［J］.計算機工程，2011，37 （4）：278－280.］

［5］CHEN Weibing，YANG Gaobo，F(xiàn)ENG Lu.A complexity image preprocessing methods of QR code［J］.Journal of Hunan University，2012，39 （10）：93－97 （in Chinese）.［陳威兵，楊高波，馮璐.一種QR 碼識別的低復(fù)雜度圖像預(yù)處理方法 ［J］.湖南大學(xué)學(xué)報 （自然科學(xué)版），2012，39 （10）：93－97.］

［6］XIONG Yong，WANG Lucai，AI Qionglong.QR code identi－fication method based on correlation matching ［J］.Chinese Journal of Scientific Instrument，2011，32 （3）：571－576 （in Chinese）.［熊用，汪魯才，艾瓊龍.基于相關(guān)匹配的QR 碼識別方法 ［J］.儀器儀表學(xué)報，2011，32 （3）：571－576.］

［7］SUN Ming，F(xiàn)U Longsheng，YANG Xinting，et al.Automatic recognition of QR code image analysis method ［J］.Journal of University of Electronic Science and Technology，2009，38（6）：1017－1020 （in Chinese）.［孫明，傅隆生，楊信廷，等.用于QR 碼自動識別的圖像分析方法 ［J］.電子科技大學(xué)學(xué)報.2009，38 （6）：1017－1020.］

［8］YANG Jiali，GAO Meifeng.A QR code pretreatment method［J］.Computer Engineering，2011，37 （2）：218－220 （in Chinese）.［楊佳麗，高美鳳.一種QR 碼預(yù)處理方法 ［J］.計算機工程，2011，37 （2）：218－220.］

［9］Wu Bangzheng，Zhong Shangping.A distortion rectification method for distorted QR code images based on self－adapting structural element［C］／／8th International Conference on Wireless Communications，Networking and Mobile Computing，2012：1－6.

［10］Gonzalez Woods.Digital image processing ［M］.3rd ed.RUAN Qiuqi，RUAN Yuzhi，transl.Beijing：Publishing House of Electronics Industry，2011 （in Chinese）. ［岡薩雷斯.數(shù)字圖像處理 ［M］.3 版.阮秋奇，阮宇智，譯.北京：電子工業(yè)出版社，2011.］