一種失真或旋轉(zhuǎn)QR碼的定位算法

趙健雄 費(fèi)樹岷

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

關(guān)鍵詞：QR碼本地化;輪廓跟蹤;回轉(zhuǎn);失真

DOI：10.11907/rjdk.182922開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2019）010-0086-04

0引言

與1D條形碼相比，2D條形碼在兩個(gè)方向上記錄數(shù)據(jù)。由于其具有高數(shù)據(jù)壓縮性及高可靠性的特點(diǎn)，以及較強(qiáng)的糾錯(cuò)能力，被廣泛應(yīng)用于許多領(lǐng)域。QR碼代表快速響應(yīng)代碼，由Denso于1994年提出，之后被廣泛用于編碼超鏈接或加密識別。

如圖1所示，QR碼是由黑白方塊組成的矩陣，稱為模塊。每個(gè)QR碼具有3個(gè)用于檢測位置與旋轉(zhuǎn)的取景器圖案（FIP）。另外，每個(gè)OR碼包含兩個(gè)定時(shí)模式（TP）、一定數(shù)量的對準(zhǔn)模式（AP）和數(shù)據(jù)區(qū)域。詳細(xì)信息可參閱2000年12月28日發(fā)布的QR碼國家標(biāo)準(zhǔn)。

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

1QR碼本地化

本地化是QR碼識別的關(guān)鍵步驟，準(zhǔn)確性是本地化的重要評價(jià)指標(biāo)。本文提出方法基于輪廓跟蹤和輪廓篩選獲得FIP輪廓，并在定位之前，通過文獻(xiàn)[12]提出的自適應(yīng)閾值算法對圖像進(jìn)行預(yù)處理以獲得二值圖像。

1.1輪廓跟蹤

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

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

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

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

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

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

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

1.2輪廓篩選

QR碼輪廓篩選是一個(gè)特殊過程。經(jīng)過大量的重復(fù)測試與分析，本文提出一種新型算法，該算法由一些基于QR碼中FIPs圖形特征的有序?yàn)V波器準(zhǔn)則組成。

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

FIP的最小輪廓是3*3模塊的輪廓。因此，F(xiàn)IPs輪廓長度應(yīng)滿足一定要求（T_i>T）。即使保留短輪廓，也難以在后續(xù)步驟中進(jìn)行識別。

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

實(shí)際上，由于環(huán)境、圖像分辨率、旋轉(zhuǎn)和透視畸變的影響，F(xiàn)IP輪廓參數(shù)可能不能完全符合上述標(biāo)準(zhǔn)。因此，相關(guān)標(biāo)準(zhǔn)應(yīng)該允許一些容差，以適應(yīng)由于各種條件導(dǎo)致的不精確性。

定義1（比率標(biāo)準(zhǔn)）：當(dāng)且僅當(dāng)1-Ei<1+E時(shí)，輪廓的最小水平包圍矩形長寬比滿足長度標(biāo)準(zhǔn)。

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

定義2（長度標(biāo)準(zhǔn)）：輪廓滿足長度標(biāo)準(zhǔn)，T_i>T，其中T_i表示閉合輪廓中的像素?cái)?shù)。

定義3（重疊標(biāo)準(zhǔn)）：輪廓滿足重疊標(biāo)準(zhǔn)。

Dist（M_i-M_j）i-M_k）

設(shè)M_i、M_j為兩個(gè)輪廓的中心像素，Dist（M_i-M_j）表示兩點(diǎn)距離，參數(shù)d應(yīng)允許小的變化。

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

具體輪廓篩選算法如下：

1.循環(huán)遍歷C_i

2.創(chuàng)建一個(gè)標(biāo)志F_i并將其初始化為0

3.結(jié)束

4.循環(huán)遍歷C_i

5.如果R_i不滿足比率標(biāo)準(zhǔn)和公差E

6.將-1分配給F_i

7.結(jié)束

8.如果T_i不滿足長度標(biāo)準(zhǔn)，則

9.將-1分配給F_i.

10.結(jié)束

11.結(jié)束

12.循環(huán)遍歷C_i

13.如果F_i≠-1

14.如果真M_i滿足重疊標(biāo)準(zhǔn)，則

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

16.結(jié)束

17.結(jié)束

18.結(jié)束

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

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

2 QR碼本地化表現(xiàn)

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

2.1圖像分辨率變化

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

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

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

2.2旋轉(zhuǎn)與失真角度變化

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

2.3QR碼本地化案例

當(dāng)QR碼旋轉(zhuǎn)角度約為45°時(shí)，文獻(xiàn)[14]中提出的方法將無法發(fā)揮作用，因?yàn)樵谒胶痛怪睊呙柚?，比率滿足1：1：3：1：1的情況很少。本文提出方法在理論上不受旋轉(zhuǎn)影響，旋轉(zhuǎn)或扭曲的QR碼示例如圖7所示，圖中紅線為FIP輪廓。

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

3結(jié)語

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