一種失真或旋轉QR碼的定位算法

趙健雄 費樹岷

摘要：為了解決傳統算法QR碼定位中出現QR碼失真，或旋轉時出現較弱魯棒性的現象，提出一種新型QR碼自適應定位算法。在算法研究過程中，首先使用自適應閾值算法解決不均勻照明的影響，在此基礎上提出一種基于輪廓跟蹤與輪廓篩選的定位方法。實驗結果表明，與傳統QR碼定位算法相比，該算法定位準確率提高了30%，且定位速度提升了17%，可見該定位算法能夠很好地應用于QR碼定位。

關鍵詞：QR碼本地化;輪廓跟蹤;回轉;失真

DOI：10.11907/rjdk.182922開放科學（資源服務）標識碼（OSID）：中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）010-0086-04

0引言

與1D條形碼相比，2D條形碼在兩個方向上記錄數據。由于其具有高數據壓縮性及高可靠性的特點，以及較強的糾錯能力，被廣泛應用于許多領域。QR碼代表快速響應代碼，由Denso于1994年提出，之后被廣泛用于編碼超鏈接或加密識別。

如圖1所示，QR碼是由黑白方塊組成的矩陣，稱為模塊。每個QR碼具有3個用于檢測位置與旋轉的取景器圖案（FIP）。另外，每個OR碼包含兩個定時模式（TP）、一定數量的對準模式（AP）和數據區域。詳細信息可參閱2000年12月28日發布的QR碼國家標準。

旨在快速、準確識別QR碼的設計算法已成為當前的研究熱點。大多數識別算法利用QR碼形態特征，如文獻[7]中提出的定位方法。利用FIP中黑白像素比例1：1：3：1：1的原理，可以通過霍夫變換得到條形碼邊界線與頂點位置，該算法很常見且較為成熟，但也存在一些缺陷。當QR碼旋轉45°或失真時，文獻[9]提出的算法無法很好地工作，而文獻[10]提出的算法對嵌入式系統而言，計算復雜度太高。同時，當圖像中QR碼比例較小時，文獻[11]中算法效果不佳。因此，本文提出一種基于輪廓跟蹤與輪廓篩選的失真或旋轉QR碼定位方法。

1QR碼本地化

本地化是QR碼識別的關鍵步驟，準確性是本地化的重要評價指標。本文提出方法基于輪廓跟蹤和輪廓篩選獲得FIP輪廓，并在定位之前，通過文獻[12]提出的自適應閾值算法對圖像進行預處理以獲得二值圖像。

1.1輪廓跟蹤

在本文中輪廓是指對象的封閉輪廓。關于輪廓跟蹤有多種算法，例如OpenCV中的cvFindContours函數，但其對于嵌入式系統而言過于復雜。本文提出的算法基于。cv-FindContours函數與Suzuki提出的輪廓跟蹤算法，但對QR碼進行了改進。該方法具有低時間與空間復雜性。

掃描后找到輪廓，圖2（a）是輸入圖像，圖2（b）表示算法1跟蹤的輪廓。

輸入：已經過預處理的二進制圖像。設輸入圖像為F={f_ij}，f_ij表示位于（x，y）的像素值。算法簡要步驟如下：

輸出：圖像中的所有輪廓。

（1）初始化：將圖像的最外圍像素設為0，并將最初的NBD設為1。

（2）用電視光柵掃描圖像，如果f_ij-1=0且f_ij=1，則確定像素（i，j）是輪廓起點，轉到步驟（3）。

（3）從起點（i，j）增加NBD，（i_o，j_o）←（i，j），（i₂，j₂）←（i，j-1），跟蹤檢測到的輪廓，可通過以下子步驟完成：①從（i₂，j₂）開始，順時針觀察（i，j）附近像素并找到非零像素。設（i₁，j₁）是第一個找到的非零像素，如果未找到非零像素，則轉到步驟（2）;②（i₂，j₂）←（i₂₁，j₁）←（i₃，j₃）←（i₀，j₀），f_i3，j3=NBD。保存（i₃，j₃）作為輪廓的一個點;③從逆時針順序像素的下一個元素（i₂，j₂）開始，檢查（i₃，j₃）附近像素，將第一個非零像素點置為（i₄，j₄）;④f_i3，j3=NBD，并將（i₃，j₃）保存為輪廓點;⑤如果（i₄，j₄）=（i₀，j₀）和（i₃，j₃）=（i₁，j₁）（回到起點），則回到步驟（2），否則，（i₂，j₂）←（i₃，j₃），（i₃，j₃）←（i₄，j₄），轉到步驟③。

1.2輪廓篩選

QR碼輪廓篩選是一個特殊過程。經過大量的重復測試與分析，本文提出一種新型算法，該算法由一些基于QR碼中FIPs圖形特征的有序濾波器準則組成。

在跟蹤輪廓之后，獲得包括背景和QR碼的所有輪廓。每個輪廓表示為C_i，j是輪廓序列號。每個輪廓長度表示為T_i，并且所有點表示為p_ij。根據獲得的信息，可通過計算獲得更多信息，該信息有助于獲取FIP和QR碼的位置。每個輪廓都有自己的最小水平包圍矩形。遍歷輪廓C_i的所有點P_ij（j∈1，2…T_i）以獲得單坐標軸中的最大和最小像素，并保存為：真x_max、x_min、y_max、y_min通過以下方法計算每個輪廓最小水平包圍矩形的長寬比：R=X_max-X_min/y_max-y_min。在無噪聲和失真的理想情況下，FIP輪廓長寬比為1。

FIP的最小輪廓是3*3模塊的輪廓。因此，FIPs輪廓長度應滿足一定要求（T_i>T）。即使保留短輪廓，也難以在后續步驟中進行識別。

FIP的輪廓是3個正方形，理想情況下其中心相同。計算輪廓C_i的中心M_i，如果輪廓中心與其它兩個輪廓重疊，則將該輪廓標記為FIP的輪廓。

實際上，由于環境、圖像分辨率、旋轉和透視畸變的影響，FIP輪廓參數可能不能完全符合上述標準。因此，相關標準應該允許一些容差，以適應由于各種條件導致的不精確性。

定義1（比率標準）：當且僅當1-Ei<1+E時，輪廓的最小水平包圍矩形長寬比滿足長度標準。

例如，E=0.2意味著最大允許比率差異為20%。

定義2（長度標準）：輪廓滿足長度標準，T_i>T，其中T_i表示閉合輪廓中的像素數。

定義3（重疊標準）：輪廓滿足重疊標準。

Dist（M_i-M_j）i-M_k）

設M_i、M_j為兩個輪廓的中心像素，Dist（M_i-M_j）表示兩點距離，參數d應允許小的變化。

在算法2中，F_i是輪廓C_i的標志，如果輪廓不滿足標準，則F_i將被設置為-1。第1-3行對應初始化，F_i初始化為0，第4-11行對應于比率與長度標準，如果輪廓不滿足相應公差標準，則將標志設置為-1。第12-18行的遍歷是算法主要部分，其中輪廓被篩選之前將檢查輪廓中心是否重疊，篩選的輪廓將被添加到輸出列表中。

具體輪廓篩選算法如下：

1.循環遍歷C_i

2.創建一個標志F_i并將其初始化為0

3.結束

4.循環遍歷C_i

5.如果R_i不滿足比率標準和公差E

6.將-1分配給F_i

7.結束

8.如果T_i不滿足長度標準，則

9.將-1分配給F_i.

10.結束

11.結束

12.循環遍歷C_i

13.如果F_i≠-1

14.如果真M_i滿足重疊標準，則

15.將1分配給F_i，并將C_i添加到輸小列表

16.結束

17.結束

18.結束

圖3（a）-圖3（c）顯示了算法2中不同濾波器標準的輪廓。在分析與計算FIP輪廓信息后，將獲得頂點位置、版本及其它信息以幫助識別。

經過大量640*480圖像的測試與分析后，將參數設置為E=0.2，d=3，以獲得最低失敗率（誤識別或無法識別）。

2 QR碼本地化表現

為了評估本文提出方法的魯棒性和準確性，從分辨率、旋轉角度和畸變角度比較與分析不同測試集效果。

2.1圖像分辨率變化

測試裝置1-3的圖像分辨率分別為320*240、640*480和960*1280，每組有60個圖像，并且每個圖像包含版本1-6中的完整QR碼。

相對誤差E=（|AoA|+|BoB|+|C_oC|）/3，其中A、B、C是本文方法得到FIPs附近OR碼的3個頂點，A_o＼B_o、C_o是手動獲得的頂點，|AoA|表示兩點距離。設E表示每組相對誤差平均值。

圖4顯示了不同圖像分辨率下的檢測率與檢測誤差平均值，可以看出檢測率很高，且誤差率較低。

2.2旋轉與失真角度變化

圖5、圖6為對復雜背景中QR碼旋轉或失真時的性能分析，因為QR碼的條件在實踐中是變化的，穩健性對于定位方法非常重要。圖5表明QR碼旋轉角度很少影響定位效果，旋轉角度范圍為0°-150°，步長為30°，還分析了透視畸變對定位的影響，透視畸變范圍為0°-35°，步長為5°。圖6顯示了不同QR碼失真角度對定位性能產生的不同影響。當失真小于20°時，該方法效果很好，但當角度為35°時，因失真太嚴重而導致無法檢測。

2.3QR碼本地化案例

當QR碼旋轉角度約為45°時，文獻[14]中提出的方法將無法發揮作用，因為在水平和垂直掃描中，比率滿足1：1：3：1：1的情況很少。本文提出方法在理論上不受旋轉影響，旋轉或扭曲的QR碼示例如圖7所示，圖中紅線為FIP輪廓。

通過霍夫變換檢測邊界線和頂點位置將受到背景干擾。圖7中的QR碼即使在嚴重扭曲、旋轉或具有復雜背景的情況下，都可通過本文提出的算法進行定位，

3結語

當QR碼出現旋轉、失真或背景復雜情況時，提高圖像定位性能具有重要意義，以便更好地進行QR碼識別。本文提出的定位算法具有對復雜背景、旋轉和失真的魯棒性。通過自適應閾值算法獲得二值圖像的定位預處理方法結合了全局閾值和局部閾值的最佳值。定位算法基于QR碼中FIP_s的幾何特征，通過輪廓跟蹤與輪廓篩選得到準確位置。測試結果表明，當QR碼隨機旋轉并在20°角度內扭曲時，該方法是健壯且精確的，但當QR碼嚴重扭曲時，定位可能是傾斜的，需要對圖片進行預處理，可以在檢測之前使用圖像去噪方法或超分辨率方法恢復劣化圖像。