基于最大連通區(qū)域的QR碼提取和校正方法

龍清清，宋夫華

LONG Qingqing , SONG Fuhua

中國計量學(xué)院 機(jī)電工程學(xué)院,杭州 310018

College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018,China

1 引言

QR(Quick Response) 碼[1]是由日本Denso公司于1994年9月研制的一種矩陣式二維條碼，也是最早可以對中文漢字進(jìn)行編碼的條碼。由其具有比一維條碼信息密度高，容量大，全方位識讀，保密防偽性強(qiáng)，糾錯能力強(qiáng)，超高速響應(yīng)，可離線應(yīng)用的便攜式數(shù)據(jù)庫等的優(yōu)點，因此近年來在國內(nèi)外得到了快速發(fā)展并廣泛應(yīng)用于身份驗證，物流管理，安全防偽，票務(wù)流通，電子商務(wù)等諸多領(lǐng)域[2]，其符號如圖1所示。

目前，使用數(shù)碼拍攝設(shè)備識別 QR碼日益興盛，通常將拍攝包含QR碼的圖像使用軟件對圖像進(jìn)行識別[3]，問題在于軟件如何對QR碼進(jìn)行識別，則需考慮以下幾個因素：

⑴ 拍攝設(shè)備本身分辨率大小影響圖像質(zhì)量

⑵ QR碼在圖像中的位置不固定且處于各種不同的背景中

⑶ 拍攝角度，距離以及光照的不同會使QR碼有旋轉(zhuǎn)，放大，拉伸或扭曲等變形

因此 QR碼的識別首先要確定符號在圖像中的位置，將符號從背景中提取出來，再進(jìn)行幾何失真校正并使用譯碼規(guī)則讀取數(shù)據(jù)。而傳統(tǒng)的提取方法是根據(jù)QR碼的編碼規(guī)則采用尋像圖形的黑白模塊比例(即1:1:3:1:1)來定位QR碼，由于此種提取方法依賴尋像圖形，當(dāng)尋像圖形有破損、污漬和光照不均等噪聲時，此時的定位效果就會受到很大的影響，因此本文采用最大連通區(qū)域來快速定位目標(biāo)區(qū)域。

圖1 QR碼符號

2 QR碼的提取和校正

QR碼的提取[4]是二維條碼識別過程中最基本的步驟，它是指將QR碼區(qū)域從實際圖像的背景中分割開來，然后以提取后的圖像單獨做研究的方法。由于拍照所獲得的圖像不可避免的會引入噪聲，則需對提取的區(qū)域進(jìn)行濾噪和幾何失真校正。其步驟如圖2所示：

圖2 QR碼提取和校正步驟

2.1 QR碼的提取

由圖2可知QR碼的提取分為三個步驟。第一步是邊緣檢測[5]，其基本思想是：首先利用邊緣增強(qiáng)算子突出圖像中的局部邊緣，然后定義像素的邊緣強(qiáng)度，通過設(shè)置閾值的方法提取邊緣點集。由于 sobel算子對灰度漸變和噪聲較多的圖像處理效果較好，因此此處采用sobel算子檢測。

第二步是卷積濾波，其基本思想是：通過卷積核圍繞自己的核心元素順時針轉(zhuǎn)180度，移動卷積核的中心元素，使它位于輸入圖像待處理像素的正上方，在旋轉(zhuǎn)后的卷積核中，將輸入圖像的像素值作為權(quán)重對應(yīng)相乘，然后將上一步各個結(jié)果的和作為該輸入像素對應(yīng)的輸出像素。設(shè)卷積核矩陣有M ×N個元素，每個元素的值分別是Ki,j，當(dāng)卷積核的中心(cm,cn)位于圖像矩陣的(x,y)位置（像素灰度值為gy,x）時，則經(jīng)過卷積濾波后，該像素的灰度值將變?yōu)椋?/p>

本文以火車票為例，如圖3(a)所示，通過卷積濾波得到結(jié)果如圖3(b)所示。

第三步是采用本文提出的最大連通區(qū)域算法來標(biāo)記QR碼的最大連通區(qū)域。區(qū)域標(biāo)記是指把唯一的標(biāo)號賦給圖像各像素區(qū)域，但相同像素值根據(jù)鄰域數(shù)不同而被區(qū)別標(biāo)記為不同的區(qū)域。而區(qū)域連通是指在一副二值圖像中，任意一點加上其n個鄰域點，按照從上到下且從左到右的順序，以非0則為連通區(qū)域的規(guī)則且從1開始整數(shù)遞增順序標(biāo)記各連通區(qū)域。在二維圖像中有 4鄰域與 8鄰域，三維圖像中則有6,16,26鄰域，如何求標(biāo)記的所有區(qū)域中最大連通區(qū)域，本文采用最簡單也最自然的區(qū)域?qū)傩苑ǎ好娣e。它由區(qū)域包含的像素個數(shù)給出。為了得到區(qū)域的實際大小，需要考慮每個像素的實際面積，如式（2）所示的矩陣及其8連通區(qū)域。

針對實際圖像采用上下左右以及其45度角方向的8鄰域進(jìn)行標(biāo)記。由于QR碼是由多個正方形小模塊所組成的一個正方形陣列，當(dāng)存在偏斜或凸起時呈四邊形，因此總可用求得的最大連通區(qū)域的最值行與最值列構(gòu)成正方形，將此正方形區(qū)域放大，即可快速鎖定 QR碼所在區(qū)域，如圖 3(c)所示。

2.2 QR碼的校正

QR碼的校正分為四個步驟。第一步先對所獲得的 QR碼區(qū)域使用亮度調(diào)節(jié)以消除光照不均，此外，在濾噪過程中由于中值濾波在一定條件下可以克服線性濾波器如最小均方濾波和均值濾波等導(dǎo)致的圖像細(xì)節(jié)模糊，能夠在消除噪聲的同時保護(hù)圖像的邊緣，因此采用3*3的方形中值濾波窗口效果比較好。其中二維序列{Xij}中值濾波表達(dá)式如式（3）所示，其中A為濾波窗口：

第二步是通過閉運算來凸顯最大連通區(qū)域的輪廓。先膨脹后腐蝕的過程稱為閉運算，它具有填充物體內(nèi)細(xì)小空洞，連接鄰近物體，在不明顯改變物體面積的情況下平滑其邊界的作用。圖像X關(guān)于結(jié)構(gòu)元素S的閉運算記為X·S,閉運算定義為：

閉運算對于結(jié)構(gòu)的平移不具有不變性，閉運算是一種遞增變換，它是正向擴(kuò)張運算，即：

由于QR碼本身是正方形，因此采用正方形形態(tài)學(xué)算子做閉運算較好。

在對圖像二值化時，其閾值的選取方法有全局閾值和局部閾值法，通過實驗對比得出使用 Ostu最大類間方差法效果較好。它的基本思想是將圖像的直方圖在某一閾值處分割成兩組，以暫定的閾值使用循環(huán)遍歷法使被分成的兩組間方差最大來確定閾值。效果如圖3(d)所示。

圖3 火車票QR碼的提取及檢測結(jié)果

第三步是利用Hough變換[6]檢測最大連通區(qū)域的四條邊線。Hough變換的原理是利用圖像全局特性將邊緣像素連接起來組成區(qū)域封閉邊界，其具體算法如下：

直線y=mx+b可用極坐標(biāo)表示為ρ=xcos(θ)+ysin(θ)，其中(θ,ρ)定義了一個從原點到線上最近點的向量，這個向量與該直線垂直。同理將圖像空間中的每一點(xi,yi)映射到Hough空間中的一組累加器A(θi,ρi)，滿足上式的每一點，將使對應(yīng)的所有累加器中的值加 1，如果圖像包含一條直線，則有一個對應(yīng)的累加器會出現(xiàn)局部最大值；通過檢測Hough空間中的局部最大值，可以確定與該條直線對應(yīng)的一對參數(shù)(θ,ρ)，從而把該直線檢測出來。如圖4(a)所示的位于直線b=mx+y上的三個點，將其映射到b-m參數(shù)空間則為經(jīng)過同一點的三條直線，如圖4(b)所示。

圖4 Hough變換的圖像空間與參數(shù)空間

圖5所示為使用Hough變換檢測火車票最大連通區(qū)域里四條邊所對應(yīng)的峰值點。

最后一步是圖像的幾何變換。它指將圖像幾何操作后，內(nèi)部結(jié)構(gòu)比例等發(fā)生變化，但整體布局與形狀沒有改變。在二維圖像中，變換形式有仿射，投影，自定義函數(shù)等方式。在文獻(xiàn)[7]中運用Hough變換檢測到的最長直線的傾角來校正圖像，然而對于受損為四邊形的圖像校正效果是很差的。本文采用投影變換[8]的方法對圖像進(jìn)行幾何變換，投影變換是將一種地圖投影點的坐標(biāo)變換為另一種地圖投影點坐標(biāo)的過程。由于投影變換需要四對控制點，本文以Hough變換檢測到的四邊形的四個交點為控制點，選取左上角控制點為基點，以任意兩點距離為邊長構(gòu)造正方形并取其四個頂點作為校正后圖形的頂點，進(jìn)而得到兩個空間的映射關(guān)系，完成坐標(biāo)值的變換。其中可將控制點坐標(biāo)變換表示為：

其中(x',y')為變換后的坐標(biāo)值，k1,.....k8為變換矩陣。相應(yīng)位置的灰度值則使用雙線性插值[9]恢復(fù)，若變換后的某點(x',y')在原圖中對應(yīng)(x,y)位置處的四鄰域坐標(biāo)為：

其相應(yīng)灰度值為：

則(x',y')處的灰度值可用式(7)表示，其圖形關(guān)系見圖6所示。

通過坐標(biāo)變換和雙線性插值變換的結(jié)果如圖7所示：

圖6 雙線性插值示意圖

圖7 最大連通區(qū)域的校正圖像

3 實驗結(jié)果及分析

為了驗證本算法的有效性，本文使用800萬像素的三星手機(jī)和130萬像素的聯(lián)想手機(jī)在不同角度，不同光照，不同背景下拍攝的共90張質(zhì)量不同的QR碼進(jìn)行了實驗，在內(nèi)存為4G的pc機(jī)上使用matlab仿真[10]，實驗結(jié)果顯示其提取平均用時在200ms內(nèi)，校正平均用時在300ms內(nèi)。總耗時在500ms內(nèi)，識別效率可達(dá)81%，其識別速度和效率較高，統(tǒng)計結(jié)果如表1所示。

表1 不同像素手機(jī)QR碼識別時間

通過實驗得出，不同像素的手機(jī)拍攝的QR碼所進(jìn)行的識別效率各有不同，高像素的識別效率可達(dá) 91%，其提取和校正總平均用時在540ms左右，而低像素的識別效率卻只有 70%，但提取和校正平均用時卻在420ms左右。實驗結(jié)果表明本文提出的算法能夠快速有效定位QR碼區(qū)域，同時也說明了高像素手機(jī)能夠提高識讀效率。

4 結(jié)論

本文研究了快速響應(yīng)碼的提取和校正方法，針對受到背景干擾，形變的QR碼，提出了一種基于最大連通區(qū)域的快速提取方法，并借助QR碼本身結(jié)構(gòu)的特性使用投影變換對QR碼進(jìn)行了校正。通過大量實驗表明，本文提出的QR碼圖像提取與校正方法能夠快速定位條碼區(qū)域，解決了QR碼受到背景干擾以及自身形變難于定位和校正的問題，滿足了實際應(yīng)用的需要。

[1]中國物品編碼中心,QR碼技術(shù)與應(yīng)用.北京,中國計量學(xué)院出社,2007:188-225.

[2]許統(tǒng),手機(jī)QR碼在國內(nèi)的發(fā)展及應(yīng)用,四川師范大學(xué)圖書館,2011,19(3):63-69

[3]Satoshi Ono,Shigeru Nakayama,Two-Dimensional Barcode Decoration Based on Real-Coded Genetic Algorithm.IEEE Evolutionary Computation,2008,1068-1073

[4]Yu Fang,Yue Peng,The Design And Implementation Of Two-Dimensional Barcode Identification In Smartphone.IEEE Computer Application and System Modeling,2010,635-637

[5]Milan Sonka,Vaclav Hlavac,Roger Boyle 圖像處理,分析與機(jī)器視覺(第三版).北京,清華大學(xué)出版社,79-175,470-493

[6]劉桂雄,申柏華,馮云慶,等,基于改進(jìn)的Hough變換圖像分割方法.光學(xué)精密工程,2002.10(3):258-260

[7]武莎莎,姚敏,趙敏,基于Hough變換的二維條碼圖像傾斜校正研究.淮陽工學(xué)院學(xué)報,2002.10(3):55-56

[8]劉慧娟,一種快速響應(yīng)碼圖像的分割和校正方法.電子測量與儀器學(xué)報,2006.20(1):34-35

[9]劉寧忠,楊靜寧,基于投影算法的二維條碼識別.計算機(jī)工程,2002.28(9):32-34

[10]楊杰,數(shù)字圖像處理及MATLAB實現(xiàn).北京,電子工業(yè)出版社, 2010:47-169.