一種復雜背景下QR 碼校正方法

孔慶鑫，潘衛(wèi)清，戴恩文，沈艷婷

（1.浙江科技學院機械與能源工程學院，杭州310023；2.浙江科技學院理學院，杭州310023；3.中國科學院上海光學精密機械研究所，上海201800；4.浙江科技學院理學院，杭州310023）

0 引言

快速響應（QR）碼信息存儲量大，抗損性強，在各個領域中得到廣泛應用。但其屬于高密度條形碼，在圖像采集過程中，光學系統(tǒng)點擴展函數會使碼圖像的邊緣出現重疊和模糊[1]。一般來說，二維碼檢測的研究大多是基于提高采集圖像的質量或確定二維碼的準確輪廓。例如，在文獻[2]中Liu Y.使用基于移動端的圖像處理系統(tǒng)，將二維碼二值化、定位、分割和解碼。文獻[3]中，使用二維碼設計了一種涉密信息的屏幕-攝像頭傳輸系統(tǒng)，將需要加密的信息流按照二維碼容量分割存儲入若干張二維碼中，利用攝像頭采集二維碼圖像進行解碼和解密信息，實現了網絡隔離的情況下的數據傳輸。但其在圖像定位算法上仍有欠缺，在復雜環(huán)境下的定位精度較低，無法滿足大批量動態(tài)二維碼流的快速定位解碼。文獻[5]提出了一種基于相關匹配的QR 碼識別辦法，使用曲面幾何自適應分割圖像，利用Hough 變換和控制點變換校正失真，最后用模板對QR 碼進行相關匹配。但Hough 變換法要求圖像周圍無其他直線干擾，極易產生誤差，且無法處理圖像畸變問題[6]。文獻[7]運用形態(tài)學算法解決了二維碼附著在不規(guī)則表面引起的圖像扭曲失真問題，但當QR 碼的旋轉角度過大時無法確定頂點的順序。

本文為提高QR 碼在復雜背景下定位及校正精度，使其能更好應用于屏幕-攝像頭二維碼通信中。根據QR 碼自帶結構特點，提出了一種在已知版本號下的快速識別方法。

1 圖像預處理

對采集到的含有QR 碼的圖像預處理效果是能否正確檢測二維碼的關鍵，通常使用手機或電腦設備抓拍的圖像存在陰影、反光、圖像旋轉或幾何失真等問題。為了盡可能保存圖像信息，減少背景和噪聲的干擾，使用最大類間方差法對圖像進行二值化處理。給出兩類的類間方差公式：

為了得到圖像分割的最佳閾值，必須使類間方差達到最大，即令t=arg maxσ2。二值化后圖像效果如圖1 所示。

圖1 二值化

由于屏幕-攝像頭通信CMOS 攝像頭成像會產生動態(tài)條紋干擾，均值濾波會造成圖像邊緣模糊，不合適用于QR 碼圖像處理。中值濾波會刪除原始圖像中細線等細節(jié)，對QR 碼圖像的影響較小。中值濾波可以有效處理攝像頭拍攝屏幕顯示器引起的像素條紋問題。本文中使用3×3 鄰域中值濾波。

2 QR碼定位

在基于二維碼的屏幕-攝像頭通信通信系統(tǒng)中，將會處理大量的二維碼數據流，對二維碼四個頂點坐標的精確度要求較高，傳統(tǒng)的二維碼頂點坐標求取方法存在一定的缺陷。根據二維碼的符號結構，本文首先設計了一個簡單的算法找到二維碼頂點坐標，使用回字位置探測圖形高效準確地定位二維碼位置。在定位二維碼位置后，通過透視變換和重采樣來恢復扭曲失真的圖像，通過Reed-Solomom 誤差修正算法得到糾錯后的數據。實驗表明，在該算法在復雜背景下有較好的效果。

2.1 定位符特征

由于QR 碼符號的特殊性[1]，因此，我們可以檢測出定位探針圖形A、B、C 之間的距離關系，最終可以確定位置檢測圖形。如圖2（a）所示，二維碼符號的位置模式包括三個位置檢測圖形，分別位于左上角、右上角和左下角。從圖2（b）可以看出，當一條水平線L 與垂直線H 通過檢測圖形中心時，從左到右均是基于深、淺，它們按1:1:3:1:1 的比例逐一出現，具有不同的旋轉角度。而這一比例的圖形特征檢測不隨二維碼圖像的大小和旋轉而改變，因此可以利用這一特征來尋找回字定位圖形的位置。

圖2 QR碼符號特征

2.2 定位算法

（1）掃描圖像的每一行，并保存黑白模塊的長度。

（2）記錄每一個具有連續(xù)5 個像素顏色的行，計算并提取它的比例。

（3）檢查比例是否符合1:1:3:1:1，且第一個像素模塊為黑色。

（4）如果c 正確，則找到回字定位中心位置，即中間的黑色塊，保存該列連續(xù)的黑白模塊長度，最后對列重復步驟b、c。

（5）在列查找過程中再次檢查回字中心位置，如果該中心點符合行查找模式中誤差范圍，保存新的中心點位置，反之，檢查下一行。對所有符合比例的行、列值進行求和取平均，即理論上回字中心位置，由于圖像可能出現模糊、變形等因素，出于容錯考慮，上下各8個像素值所有符合搜索比例的點進行存儲。

2.3 使用K-means對候選點集群聚類

運用K-means 聚類算法對回字定位點候選集群進行聚類，選取與整體差異最小點作為初始聚類中心，據此實現特征點匹配可大大降低計算維度。對存儲的候選點通過無監(jiān)督學習的方式，進行K-means 聚類，得到3 個搜獲集群，從中選擇出三個點，即三個回字中心位置。以下為K-means 算法步驟：

（1）為待聚類的點S=x1,x2,x3…xn尋找聚類中心u1,u2,u3…uk。

（2）利用誤差平方和準則函數作為聚類準則，計算每個點到聚類中心的距離，將每個點聚類到離該點最近的聚類中去。

（3）計算每個聚類Cj中所有點的坐標均值uj

（4）將這個平均值uj作為新的聚類中心反復執(zhí)行（2）、（3），直到聚類中心不再進行大范圍移動或者聚類次數達到要求為止。

通過上述聚類算法，相似程度較高的項目被分配到同一類中。聚類算法的執(zhí)行過程較為耗時，但可以離線進行，因此并不影響算法實時性。

2.4 判斷回字定位點順序

使用三點之間向量點積算法判斷出三個回字定位點的順序。下面用偽代碼表示：

此處可知三個點順序如圖3 所示。

圖3 QR碼回字探測圖形順序圖

2.5 尋找校正圖形

在找到二維碼的三個回字定位圖形后，需要檢測二維碼的校正圖形，完成二維碼的精確定位。相比回字定位標志，校正圖形更加難以定位，單一水平與垂直檢測會產生極大誤差。本文對傳統(tǒng)校正圖形定位方法做了改進。將校正圖形最外部黑色正方形作為分隔符，改為水平、豎直搜索內部符合1:1:1 比例的圖形。在已知三個定位圖形坐標及順序的情況下，估計出校正圖形中心理論位置，在對角搜索算法下，取與理論距離最近的候選點作為實際校正圖形中心坐標。

在找不到校正圖形，或版本1 的QR 碼不存在校正圖形的情況下，本文根據二維碼的設計特點，設計了理論求解二維碼4 個頂點位置的算法。

（1）計 算A 點 到B，C 兩 點 的 歸 一 化 向 量二維碼中心坐標

（2）計算得三個回字定位坐標各自距離，記dist_AC，dist_AB。得各自方向上每個格子所占像素個數為cell_width=dist/（module-7）。

（3）求取扭曲圖像中定位圖形之間的最大距離，dist_max=max（dist_AC，dist_AB）。

（4）回字定位符A 的四個頂點坐標求法如下所示。

B，C 兩點同樣用以上辦法求出。位置順序如圖4所示。

（5）由于版本1 的QR 碼不存在校正圖形，且需要在無法找到校正圖形的情況下精確定位右下角坐標，不能直接用校正圖形推出最后一點坐標時，以下給出該坐標求取方法。

圖4 探測圖形頂點順序圖

3 QR碼校正

在三個回字定位坐標及校正圖形均正確找到的情況下，可以根據二維碼設計標準推測出圖像的四個頂點，然后通過逆投影變換將扭曲失真圖像進行校正，如圖5 所示。

圖5 逆投影變換

設（x，y）為原始圖像上二維碼坐標，（u，v）為投影變換后的校正坐標，a，b，c，d，e，f，g，h 為公式中待解的8 個參數，將至少4 點代入公式中求解上述參數，這里在已知二維碼版本號的前提下，可以選取三個回字定位中心坐標和校正圖形中心坐標進行校正。

整理后得到：

將 二維 碼 扭曲 失真 坐 標(x0,y0)、(x1,,y1)，(x2,y2)，(x3,,y3)和校正頂點(u0,v0)、(u1,,v1)，(u2,v2)，(u3,,v3)代入投影公式中，再將原始QR 二維碼圖形轉換到一個正方形內，設正方形邊長為W，轉換后4 個頂點坐標可以分別取(0,0)、(w,0)，(w,w)，(0,w) ，將以上4 點坐標代入（4）式中解得：

校正結果如圖6 所示。

圖6 QR碼校正示意圖

4 實驗結果與分析

4.1 復雜背景下的定位結果

為了驗證本文算法性能，利用Intel Core i5-7500CPU @3.2GHz 計算機，使用MATLAB 2017a 軟件上實現本文算法，并測試運行速度及復雜背景下的識別情況。

本文算法以文獻[13]中形態(tài)學和Hough 變換算法對圖像的處理結果說明精度對圖像處理的影響。該算法通過形態(tài)學圖像處理與邊緣檢測得到QR 碼邊緣圖像，然后通過Hough 變換找到QR 碼頂點。如圖7（b）所示，但經過圖像放大，QR 碼邊緣存在間隙，如果直接建立采樣網絡解碼，會造成部分采樣點信息錯誤，由于QR 自身的糾錯機制，在不超過糾錯等級的前提下并不影響信息解讀，但是單張QR 碼容量有限，使用更低的糾錯等級就可以存儲相對更多的信息。如果定位精度低，會降低對QR 碼最大容納信息量。

圖7 文獻[13]中定位算法

使用本文算法定位二維碼效果如圖8。

圖8 本文定位算法效果圖

4.2 算法識別正確率

一般情況下，攝像頭分辨率越高，圖片細節(jié)信息更加豐富，有利于條碼識別，但信息量越大，處理速度會更慢。本次實驗使用目前手機通用960×544 像素普通攝像頭對QR 碼進行采集。拍攝角度分別為上、下、左、右四個方向上與桌面呈現30°-90°各200 幅，鏡頭距離10-20cm 變化，模擬QR 碼的幾何失真，共采集800 幅圖。

表1 實驗數據統(tǒng)計結果

比較傳統(tǒng)算法和本文提出的QR 碼定位識別算法，在識別時間上與國標算法略快，但在識別率上有較大幅度提升。當找不到校正圖形時，通過算法可以有效推測出坐標位置。相較于文獻[8]中掃描辦法，從圖像右下角向內掃描時，QR 碼邊界像素在底部聚集較密集，導致邊緣兩條直線相交于QR 碼內，而非邊緣頂點，因此算法無法找到對應頂點。本文在掃描時進行K-means 聚類剔除冗余點，能夠有效較低冗余點對定位精度的影響，從而可以將扭曲失真二維碼進行亞像素級校正。整個算法在相對較短的時間內達到了較高的識別率，在嵌入式設備、手機移動端均可以滿足實時性要求。

4.3 不同算法性能比較

本文使用文獻[11]中的實驗條件，分別測試QR 碼在旋轉與角度失真情況下的定位正確率。如圖9（a）中，旋轉角度0°～150°，步長30°，圖9（b）透視畸變0°～35°，步長5°。

圖9 旋轉與失真角度下誤差對比

從實驗結果來看，本文算法可以忽略旋轉帶來的影響，35°以內的透視畸變均可保持90%以上正確率，為后續(xù)解碼提供保障。對比文獻[11]中使用輪廓追蹤，當透視角度過大后，不同角度的回字定位點輪廓的最小水平包圍矩形長寬比會發(fā)生變化，其參數為實驗調整數據，無法滿足數量較大且情況不同的二維碼數據流采集校正要求，在實驗條件下其透視畸變角度大于10°后校正正確率處于90%以下，已不具備解碼條件。

同樣在文獻[12]的實驗條件下，比較QR 碼定位算法的正確率及運行速度。實驗結果如圖10 所示，相比于文獻[12]中使用七個方向對定位點進行掃描，使用歐氏距離計算距離誤差來剔除冗余點，本文算法只采用兩個方向掃描定位點，然后使用K-means 聚類剔除冗余點，可以離線進行，計算量更低，且定位更加精準，更適合與屏幕-攝像頭通信中對大量二維碼數據流的處理。如圖8 所示，本文算法具有更快的運行時間和更高的QR 碼校正成功率。

圖10 本算法與文獻[12]算法對比

5 結語

針對使用動態(tài)二維碼的屏幕攝像頭通信方式，本文設計了一種抗復雜環(huán)境的QR 快速定位校正辦法，能夠有效地對QR 碼進行定位和校正，提高了識別速度，在校正算法上實現了亞像素級別的圖像校正，使得發(fā)送端傳輸的QR 碼可以在低容錯版本的情況下保持相對較高的有效信息存儲，下一步工作是進一步簡化算法，開發(fā)基于二維碼的屏幕攝像頭的通信系統(tǒng)，實現信息的高速傳輸。