劉烽杰，蔡 明

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引言

QR 碼又稱快速響應(yīng)矩陣碼，是一種最常用的二維碼。如今，掃碼軟件通過智能手機(jī)自帶的攝像頭便可輕松掃出QR 碼信息，但這僅限于平面上的QR碼。當(dāng)條碼被粘貼或打印在圓柱面上時(shí)，由于無法檢測到探測圖形，識別困難。

本文的研究背景是實(shí)現(xiàn)校園的自主導(dǎo)游，QR 碼粘貼于白色柱面上，背景相對清晰。平面QR 碼的校正首先是獲取到3 個(gè)位置探測圖形，然后根據(jù)坐標(biāo)判斷旋轉(zhuǎn)角度來確定方位。柱面QR 碼在三維空間產(chǎn)生了畸變，導(dǎo)致無法準(zhǔn)確定位探測圖形，因此采用傳統(tǒng)識別方法行不通。文獻(xiàn)［1］利用探測圖形的特征進(jìn)行定位，接著利用逐像素映射還原算法重構(gòu)QR碼，但必須保證獲得的初始圖像為正投影圖像，且三維空間的畸變程度不能太大。文獻(xiàn)［2］利用探測圖形具有相同的重心來定位，雖然在畸變較大的場合下仍適用，但也必須滿足正投影的要求。而在實(shí)際掃描時(shí)，圖像往往在二維空間也產(chǎn)生了畸變，因而很難滿足正投影的要求。

考慮到此刻柱面QR 碼環(huán)境的特殊性(背景清晰)，根據(jù)幾何學(xué)中輔助線的理念(即輔助線是在原圖基礎(chǔ)上所作的具有極大價(jià)值的直線或線段)，提出了在QR 碼外部加一個(gè)平行于4 條輪廓的黑色輔助矩形，利用它進(jìn)行平面的校正。接著利用定位圖形重心相同的特征獲取到定位圖形坐標(biāo)，再應(yīng)用直線最佳逼近法獲取4 條輪廓。之后進(jìn)行區(qū)域分割還原進(jìn)行三維圖像的校正，形成標(biāo)準(zhǔn)的QR 碼圖像。

1 二維空間校正及條碼定位

QR 碼是由深淺正方形模塊組成的一個(gè)正方形陣列，主要包括功能區(qū)域和編碼區(qū)域［3］。功能區(qū)域由探測圖形、分隔符、定位圖形和校正圖形等組成。其中位置探測圖形位于3 個(gè)邊角，用于快速定位QR碼在原圖中的位置。

如圖1 所示，L 為一根水平穿過平面探測圖形和柱面探測圖形的直線。其中，平面探測圖形從左往右具有固定的比例1∶1∶3∶1∶1。由QR 碼的編碼規(guī)則可知，出現(xiàn)如探測圖形特征的區(qū)域基本不可能［3］，因此通過查找類似比例的區(qū)域來確定探測圖形是可行的。傳統(tǒng)的識別算法一般是在獲取到探測圖形的基礎(chǔ)上，利用Hough 變換將圖像旋轉(zhuǎn)至水平，再用雙線性變換和雙線性插值算法校正幾何形變。在此基礎(chǔ)上經(jīng)傅立葉濾波得到比較精確的條碼模塊，最后提取碼字信息［4］。對圓柱面而言，畸變程度不大時(shí)，該比例尚明顯。當(dāng)畸變程度較大時(shí)，從圖1 可以看出，比例發(fā)生了改變，導(dǎo)致通過獲取探測圖形來識別QR 碼的方案行不通，再加上二維平面上的畸變，使得柱面QR 碼的識別更加不易。為了準(zhǔn)確識別，必須先將畸變的QR 碼進(jìn)行平面的校正，在這基礎(chǔ)上，才能再次進(jìn)行三維空間的校正。經(jīng)過思考，可以通過添加輔助矩形來達(dá)到這一目的。

圖1 平面及柱面定位圖形比較

1.1 二維幾何校正

對添加了輔助矩形的QR 碼(見圖2)校正，具體步驟如下［5］:1)利用Hough 變換提取出該矩形，求得4 個(gè)頂點(diǎn)坐標(biāo)。因?yàn)镠ough 變換不僅可以用于直線的提取，對于曲線同樣適用［6］。2)對圖像做幾何運(yùn)算校正失真，并旋轉(zhuǎn)至水平。在做幾何運(yùn)算時(shí)，首先進(jìn)行空間變換，描述每個(gè)像素如何從初始位置轉(zhuǎn)換至終止位置，同時(shí)還要進(jìn)行灰度級插值，因?yàn)樵谝话闱闆r下，輸入圖像的位置坐標(biāo)為整數(shù)，經(jīng)過運(yùn)算，輸出圖像的坐標(biāo)往往為非整數(shù)。因此，這里采用雙線性插值算法，即對每一個(gè)目標(biāo)像素設(shè)置坐標(biāo)，通過反向變換來得到浮點(diǎn)坐標(biāo)(i +u，j +v)。其中i，j 均為非負(fù)整數(shù);u，v 為［0，1)區(qū)間的浮點(diǎn)數(shù)。設(shè)這個(gè)像素的值為f(i+u，j+v)，則該值可由原圖像中坐標(biāo)為(i，j)、(i+1，j)、(i，j+1)、(i+1，j +1)所對應(yīng)的周圍4 個(gè)像素的值決定，即:

其中f(i，j)表示原圖像(i，j)處的像素值。以此類推，得到平面校正后的圖像(見圖3)，即正投影圖像。

圖2 添加輔助矩形的QR 碼

圖3 平面校正后的QR 碼

1.2 定位圖形定位

在利用輔助矩形實(shí)現(xiàn)了柱面QR 碼的平面校正后，得到的相當(dāng)于正投影的圖像。此刻，如果畸變程度比較大，采用符號特征定位顯然不行。從圖3 可以看出，在掃描后，3 個(gè)探測圖形具有很明顯的特征，即重心相同。因此，抓住這一點(diǎn)來確定探測圖形的坐標(biāo)。探測圖形的重心可以通過式(1)計(jì)算得出［7］:

式中:gx和gy分別代表重心點(diǎn)的x，y 坐標(biāo);f(x，y)是(x，y)點(diǎn)處的灰度值。在輪廓圖像中取邏輯值0 或1，式(1)可以簡化為:

1.3 條碼邊界提取

QR 碼與其他條碼不同的是它不存在起始符和終止符，因此要直接掃描得到條碼邊界是不可能的。多數(shù)文獻(xiàn)中采用Hough 變換來提取，但無論是應(yīng)用于整幅圖案還是隔行應(yīng)用，都是比較浪費(fèi)CPU 資源的。本文在已知定位圖形坐標(biāo)的基礎(chǔ)上，采用直線最佳逼近法獲取條碼的輪廓［8］，如圖4 所示，具體算法如下:

1)設(shè)1.2 節(jié)中所獲得的3 個(gè)定位圖形的重心分別為P1，P2，P3。過任意2 點(diǎn)作直線，共得到3 條直線(圖中直線P1P2，P1P3和P2P3)。

2)使3 條直線分別向遠(yuǎn)離另一個(gè)點(diǎn)的方向移動(dòng)(如圖中P1P2向上移動(dòng)，箭頭代表移動(dòng)方向)，每次偏移2 個(gè)像素，求出各條直線掃描圖像得到的波形。根據(jù)掃描線所得波形進(jìn)行對比、判斷。在到達(dá)邊界時(shí)來回掃描，微調(diào)直線斜率，得到最佳逼近直線。

3)移動(dòng)過程中，由于直線P2P3無法得到最佳逼近效果而被拋棄，因此獲得PAPB和PAPC兩條直線。接著分別作過點(diǎn)P2平行于P1P3的直線和過點(diǎn)P3平行于P1P2的直線，使直線向箭頭標(biāo)識方向進(jìn)行掃描，從而得到另外2 條邊界直線。圖中PAPB，PAPC，PCPD，PBPD這4 根直線即為QR 碼輪廓，PA，PB，PC，PD為4 個(gè)頂點(diǎn)。

圖4 直線最佳逼近法示意圖

2 三維空間校正

利用輔助矩形進(jìn)行平面矯正以及直線最佳逼近法提取出邊界后，得到的圖像仍為長方形(如圖5 所示，其中AC ＞AB，由于主視圖太長，這里簡化)，需再次對圖像進(jìn)行三維空間的校正。校正的關(guān)鍵在于如何將長方形校正為正方形［9］。從圖中可以得到公式(2)和公式(3):

聯(lián)合式(2)、式(3)可得:sin(α)=n ×α/m，其中m和n 的值經(jīng)過圖像檢測可以直接求得，α 的值一定在0至π/2 之間，并且是唯一的，可通過二分法求得α 的近似值。得到α 后，根據(jù)式(2)可求得R 的值為m/2α。

圖5 區(qū)域還原算法示意圖

由于QR 碼的特征比較簡單，當(dāng)畸變不是很大時(shí)，沒必要采取逐個(gè)像素映射還原的方法，采用區(qū)域分割還原法即可［10］。根據(jù)獲取到的n/m 的比例，把提取出的QR 碼圖像以中線為基準(zhǔn)分割成n 等分，分割結(jié)果如下:

圖5 是將QR 圖像分割成4 等分的示例，其余分割類似。采用區(qū)域還原就是將每一個(gè)區(qū)域進(jìn)行不同程度的拉伸。這里以區(qū)域3 為例說明，如圖有EF=n/4，sin(β)=EF/R，半徑R 在之前已經(jīng)求過了，所以可以很容易求出β，此時(shí)弧長GH=R×β。對于區(qū)域3，區(qū)域還原就是將EF 拉伸到弧長GH。對于其他3 個(gè)區(qū)域同樣可以求得拉伸后的各自的長度。最后采用圖像處理函數(shù)分別進(jìn)行拉伸即可獲得校正后的圖像。

3 算法的實(shí)現(xiàn)

得到二維及三維校正后的圖像后，還需要對圖像進(jìn)行二值化處理，其關(guān)鍵點(diǎn)是確定二值化的閾值，最大類間方差法在一般情況下能較好地解決該問題［11］。該方法將采集圖像分為物體類和背景類，當(dāng)2類間的灰度值方差取最大值時(shí)，對應(yīng)的灰度值為二值化閾值。最后，使用文獻(xiàn)［12］提出的一種基于圖像熵的Otsu 改進(jìn)算法，縮短計(jì)算時(shí)間，并使分割后的圖像更加細(xì)膩，得到的標(biāo)準(zhǔn)QR 碼圖像如圖6 所示。

圖6 校正后的圖像

最后使用Google 提供的ZXing 開源類庫在Android 平臺上實(shí)現(xiàn)了圓柱面QR 碼識別軟件［13］，使用安卓手機(jī)自帶的攝像頭完成拍攝及識別。流程圖如圖7 所示。

圖7 柱面QR 碼識別流程

4 結(jié)束語

本文通過幾何學(xué)中添加輔助線的理念，站在平面幾何的角度上提出了在QR 碼外側(cè)添加輔助矩形，利用它進(jìn)行平面的校正，獲取到正投影圖像，對之后進(jìn)行區(qū)域還原做好鋪墊。當(dāng)然本文所研究QR 碼的場合是比較特殊的，即QR 碼背景相對清晰，適宜添加輔助矩形而不影響其它內(nèi)容。在三維校正時(shí)，又站在三維立體幾何的角度上采用了效率相對較高的區(qū)域還原算法，而沒有采用逐個(gè)像素重構(gòu)，畢竟一個(gè)一個(gè)像素重新繪制是比較耗時(shí)的。最后在Android 平臺上進(jìn)行實(shí)現(xiàn)。

［1］Li Xiaochao，Shi Zhifeng，Guo Donghui.Reconstruct argorithm of 2D barcode for reading the QR code on cylindrical surface［C］// International Conference on Anti-Counterfeiting，Security and Identification(ASID 2013).2013:178-182.

［2］史志鋒.基于三維透視變換的圓柱面QR 碼識別方法［J］.現(xiàn)代電子技術(shù)，2014，37(8):16-18.

［3］GB/T18284，中華人民共和國國家標(biāo)準(zhǔn)—快速響應(yīng)矩陣碼(QR Code)［S］.

［4］張名，張建立.基于符號特征的QR 碼識別算法［J］.計(jì)算機(jī)工程，2011，37(4):278-280.

［5］劉宏偉，嚴(yán)研.快速響應(yīng)碼的識別和解碼［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2006，26(6):1560-1562.

［6］岡薩雷斯.數(shù)字圖像處理［M］.第2 版.北京:電子工業(yè)出版社，2007.

［7］谷口慶治.數(shù)字圖像處理—應(yīng)用篇［M］.北京:科學(xué)出版社，2002.

［8］杜秀偉，章兢，翟景瞳.基于輪廓特征的快速響應(yīng)碼定位與提取方法［J］.電子技術(shù)應(yīng)用，2009，35(6):47-49.

［9］劉慧娟.一種快速響應(yīng)碼圖形的分割和校正方法［J］.電子測量與儀器學(xué)報(bào)，2006(1):32-36.

［10］司國東，陳仲.柱面二維碼識別算法的設(shè)計(jì)與實(shí)現(xiàn)［J］.現(xiàn)代計(jì)算機(jī)(中旬刊)，2013(8):25-27.

［11］Otsu N.Athreshold selection method from gray-level histograms［J］.IEEE Trans.on Systems Man and Cybernetics，1979，9(1):62-66.

［12］肖超云，朱偉興.基于Otsu 準(zhǔn)則及圖像熵的閾值分割算法［J］.計(jì)算機(jī)工程，2007，33(14):188-189.

［13］陳二陽，雷霖.QR 條碼圖像識別及解碼技術(shù)的實(shí)現(xiàn)［J］.電視技術(shù)，2013，37(7):16-19.