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

龍清清，宋夫華

LONG Qingqing , SONG Fuhua

中國計量學院 機電工程學院,杭州 310018

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

1 引言

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

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

⑴ 拍攝設備本身分辨率大小影響圖像質量

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

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

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

圖1 QR碼符號

2 QR碼的提取和校正

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

圖2 QR碼提取和校正步驟

2.1 QR碼的提取

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

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

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

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

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

2.2 QR碼的校正

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

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

閉運算對于結構的平移不具有不變性，閉運算是一種遞增變換，它是正向擴張運算，即：

由于QR碼本身是正方形，因此采用正方形形態學算子做閉運算較好。

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

圖3 火車票QR碼的提取及檢測結果

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

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

圖4 Hough變換的圖像空間與參數空間

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

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

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

其相應灰度值為：

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

通過坐標變換和雙線性插值變換的結果如圖7所示：

圖6 雙線性插值示意圖

圖7 最大連通區域的校正圖像

3 實驗結果及分析

為了驗證本算法的有效性，本文使用800萬像素的三星手機和130萬像素的聯想手機在不同角度，不同光照，不同背景下拍攝的共90張質量不同的QR碼進行了實驗，在內存為4G的pc機上使用matlab仿真[10]，實驗結果顯示其提取平均用時在200ms內，校正平均用時在300ms內?？偤臅r在500ms內，識別效率可達81%，其識別速度和效率較高，統計結果如表1所示。

表1 不同像素手機QR碼識別時間

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

4 結論

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

[1]中國物品編碼中心,QR碼技術與應用.北京,中國計量學院出社,2007:188-225.

[2]許統,手機QR碼在國內的發展及應用,四川師范大學圖書館,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 圖像處理,分析與機器視覺(第三版).北京,清華大學出版社,79-175,470-493

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

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

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

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

[10]楊杰,數字圖像處理及MATLAB實現.北京,電子工業出版社, 2010:47-169.