基于亞像素的快速響應矩陣碼的圖像定位算法

曹 琨，張姍姍

(河南牧業(yè)經濟學院計算機應用系，河南鄭州450044)

隨著信息技術的迅速發(fā)展，二維碼技術也得到了蓬勃發(fā)展，相對于一維碼技術，其具有信息容量大、可靠性高、成本低、糾錯能力強等優(yōu)點，可以表示數(shù)字、字母、漢字和圖像等信息，在電子商務、工業(yè)生產、物流管理以及公共安全等領域等得到了成功應用［1-3］。

根據(jù)結構，二維碼分為兩種:堆疊式和矩陣式。堆疊式二維碼由多行一維條碼堆疊而成，以PDF417為代表［4］;矩陣式二維碼的符號是矩陣，信息分布在矩形內，采用像素點的黑白對信息進行描述，如快速響應矩陣(Quick Response Code，QR)［5］。1994年，日本Denso公司研制出了QR碼，其不僅具有一維碼和其他二維碼的優(yōu)點，而且具有可以表示漢字、圖像、防偽性強等特點，成為當前主流的二維碼［6］。2000年，我國制定了《快速響應矩陣碼》國家標準，可以表示中國漢字，拓寬了QR碼的應用范圍［7］。在QR碼實際應用中，必須對QR碼進行正確識別，而 QR碼的定位是 QR碼識別的基礎［8］。針對QR碼的定位問題，國內外的研究機構和學者進行了大量、深入的探索，提出許多有效的QR碼定位算法，主要分為基于輪廓查找的定位算法、基于圓角檢索的定位算法和非線性定位算法3類［9］。輪廓查找的定位算法根據(jù)QR碼的圖像特點，搜索圖像的輪廓確定QR碼的位置，其對光照變化、噪聲比較敏感［10］;基于圓角檢索的定位算法主要包括Hough變換定位算法和圖形位置定位算法［11-12］，它們利用QR碼的位置探測圖形來實現(xiàn)QR碼定位的位置，但當QR碼發(fā)生較大的畸變時，定位準確率比較低;非線性定位算法將QR碼定位看作是一種分類問題，首先提取QR碼的特征，然后采用非線性分類能力強的神經網絡、支持向量機對訓練樣本進行學習，構建QR碼的分類器，從而采用建立的分類器對待定位的QR碼進行定位，但是其定位性能與分類器參數(shù)密切相關［13-14］。

針對當前QR碼定位算法存在的不足，為了獲得更加理想的QR碼定位結果，提出一種基于亞像素的QR碼定位算法，并采用仿真實驗對其有效性和可靠性進行測試。實驗結果表明，相于當前經典的QR碼定位算法，基于亞像素的QR碼定位算法不僅提高了QR碼的定位精度，而且加快了QR碼的定位速度，可以滿足QR碼的實際應用需求。

1 QR碼簡介

1．1 QR碼的結構

QR碼通常由一個正方形陣列構成，它劃分為兩部分:編碼區(qū)域和功能圖形。編碼區(qū)域主要由數(shù)據(jù)碼字、糾錯碼字、版本信息等組成;功能圖形由尋像圖形、分割符、定位圖形和校正圖形等組成，它不用于數(shù)據(jù)編碼，符號四周為空白區(qū)，具體如圖1所示。尋像圖形包括3個位置探測圖形，它們分布于QR碼的3個角上，主要用于確定QR碼符號圖像的位置。QR碼版本有40種規(guī)格，4個糾錯等級，可以對7 089個數(shù)字或者4 296個字母數(shù)字進行編碼，最高糾錯等級為30%碼字。在QR碼的譯碼過程中，3個位置探測圖形的中心坐標起著十分重要的作用［15］。

圖1 QR碼的符號示例

1．2 QR碼的特征

在實際應用中，采集到的QR碼具有如下特征:

1)采集到的QR碼圖像的水平與的垂直比例固定為1∶1，且圖像的主體為QR碼。

2)QR碼一般用于商品包裝，并且包括了大量與QR碼無關的內容，因此QR碼的圖像背景十分復雜。

3)由于拍攝過程中的角度以及距離影響，得到的QR碼存在一定的傾斜與畸變。

4)由于外界因素的影響，QR碼圖像包括一定的噪聲。

2 傳統(tǒng)QR定位算法以及存在的不足

2．1 傳統(tǒng)QR定位算法

當前QR碼定位算法基于紋理、頻域和機器學算法進行定位，通常直接采用位置探測圖形實現(xiàn)定位，以文獻［15］的QR碼定位算法為例，QR碼定位的步驟如下:

1)采用專門QR碼圖像采集設備，收集QR碼圖像。

2)由于圖像一般包含噪聲數(shù)據(jù)，為此采用小波變換對QR碼圖像進行去噪處理，提高QR碼圖像的質量。

3)采用大類間類差算法對QR碼圖像進行二值化處理，使QR碼與背景圖像之間的差異盡可能大。

4)利用形態(tài)學算法消除背景圖像的無用信息，便于QR碼圖像分割。

5)采用Max-Min差分以及相關邊緣檢測算法，提取QR碼的目標邊緣。

6)利用Hough變換定位算法尋找QR碼的4條邊界，對QR碼的候選位置進行初步定位。

7)根據(jù)3個位置探測圖形來確定QR碼的位置和方向，實現(xiàn)QR碼的候選位置精確定位。

2．2 存在的不足

隨著QR碼的應用領域的不斷增加，由于外界環(huán)境以及一些不可克服的因素影響，采集的QR碼圖像的分辨率低，而且QR碼存在傾斜、畸變、幾何失真，導致QR碼的3個位置探測圖形的水平與垂直比例不能滿足1∶1的關系，同時黑白塊的比不符合3∶1∶1的關系，這樣使QR碼的定位失敗，難以實現(xiàn)精確定位。具體如圖2所示。

圖2 采集的不同QR圖像

3 本文的QR碼定位算法

3．1 QR碼圖像的灰度化處理

隨著電子器件的不斷成熟，現(xiàn)在圖像采集的設備得到QR碼圖像均為彩色圖像，彩色圖像包含的信息理大，需要存儲空間較大，影響QR碼圖像定位的效率，而在實際QR碼的有效信息是黑白的，因此，為了加快QR碼定位的速度，對彩色QR碼圖像進行灰度化處理，當前灰度化處理方法很多，本文采用加權平均值法進行QR碼圖像灰度化。利用人眼對各個顏色分量的敏感程度不一樣，將各個分量賦予一定的權值，取3個分量的加權平均作為灰度圖像相應像素的灰度值，模型化表示如下

對圖3a中的彩色QR碼圖像進行灰色度化，得到的結果如圖3b所示。

圖3 采集的不同QR圖像

3．2 QR碼圖像的去噪處理

小波是函數(shù)空間L2(R)中，滿足所謂的“容許條件”的函數(shù)，對任意信號函數(shù)f(t)∈L2(R)，連續(xù)小波變換定義為

離散小波變換中時間仍為連續(xù)變量，將尺度參數(shù)和平移參數(shù)離散化，得到分析小波

離散小波變換定義為

小波分析最主要的特點是自動變焦、多尺度分析，被稱為數(shù)學分析的“顯微鏡”，因此利用小波變換實現(xiàn)頻率選擇和多尺度分解，可起到抑制背景噪聲，消除散焦影響和增強目標的作用，信號的分解公式為

式(5)為低頻信號的分解過程，第i級低頻信號Ai，k分解得第i+1級離散低頻信號Ai+1，k，h為低通濾波器;式(6)為高頻信號的分解過程，第i級高頻信號 Di，k分解得第 i+1級離散高頻信號Di+1，k，g為高通濾波器。利用小波變換去除高頻噪聲保留低頻信號。

3．3 邊緣點粗定位

首先采用Otsu閾值分割算法對圖像的QR碼進行分割，設一幅圖像的QR碼灰度值范圍為0～L，定義灰度為i的像素個數(shù)為ni，像素總數(shù)為N，則必有

假設存在一個閾值T，圖像函數(shù)f(x，y)中的像素被T分為 C1和C2類，即

式中:fmin和fmax分別為圖像f(x，y)中灰度的最小值與最大值。

那么C1部分的分布概率p1、灰度均值μ1和方差計算如下

采用相同的方式計出C2的分布概率p2，灰度均值μ2，方差，定義類間方差和類內方差，有

閾值T1將QR碼像分成兩類D1和D2，兩類的灰度均值μ1和μ2，兩類的相對距離值d

找出使兩類的相對距離d最大的閾值Th，即為最優(yōu)分割閾值，從而將QR碼圖像從背景中分割出來。

3．4 亞像素的精確定位

QR碼的圖像的周圍具有一定的空白區(qū)域，它們與3個位置探測圖形具有邊緣效應，因此采用亞像素的精確定位步驟如下:

1)對左上角頂點位置坐標，以及左下角和右上角的頂點位置坐標。

2)根據(jù)QR碼四周為空白區(qū)，通過右上角頂點和左下角頂點的邊界掃描線確定右下角的頂點位置坐標。

3)通過逐個找描述QR碼的亞像素點實現(xiàn)QR碼的精確定位。

3．5 本文QR碼定位算法的工作步驟

1)對圖像進行灰度化，去噪聲等預處理操作。

2)采用Otsu閾值分割算法對圖像中的QR碼進行粗定位。

3)對粗定位結果進行幾何校正與旋轉。

4)采用亞像素對3個位置探測圖形的中心和方向進行確定，從而實現(xiàn)圖像中的QR碼進行精定位。

綜合上述可知，本文提出的QR碼圖像的定位算法工作流程如圖4所示。

4 仿真實驗

4．1 仿真環(huán)境

為了測試本文提出的QR碼定位算法的有效性和優(yōu)越性，在 Intel 4核 2.8 GHz CPU，內存為 4 Gbyte，Windows XP Professional操作系統(tǒng)，采用VC++實現(xiàn)仿真實驗。為了實驗結果更具說服力，選擇文獻［16］的QR碼定位算法進行對比實驗，采用不同字符數(shù)量和不同分辨率的圖像集對它們的定位正確率進行對比分析。

圖4 本文QR碼定位算法的工作流程

4．2 結果與分析

4.2.1 定位結果的視覺效果比較

本文算法與文獻［16］算法的QR碼定位結果如圖5和圖6所示。對圖5和圖6進行的結果進行比較，可以清楚看出，本文算法的定位結果更優(yōu)，可以對QR碼實現(xiàn)準確定位，對比結果初步證明了本文算法的有效性和優(yōu)越性。

圖5 本文算法的QR碼定位結果

圖6 文獻［16］算法的QR碼定位結果

4.2.2 算法的識別正確比較

為了客觀、準確全面衡量本文算法的性能，分別采用不同字符數(shù)量QR碼圖像和不同分辨率的QR碼圖像進行測試，本文算法與文獻［16］算法對QR圖像集定位正確率分別如圖7a和7b所示。從圖7a可知，隨著隨字符數(shù)量的增加，文獻［16］算法的QR碼的定位正確率出現(xiàn)大幅度的波動，而且呈單調遞減趨勢，而本文算法與字符數(shù)量變化的關系不太大，QR碼定位正確率的變化比較平衡，而且不是呈現(xiàn)明顯的遞減趨勢;從圖7b可以看出，隨分辨率的增大，本文算法與文獻［16］算法的QR碼定位正確率也不是呈單調遞增趨勢，而是呈波動性的遞增趨勢，但是在相同條件下，本文算法的QR碼定位正確率要高于文獻［16］算法，結果表明，本文算法較好地解決了當前QR碼定位算法存在的不足，提高了QR碼定位的準確性，定位結果更加可靠。

圖7 本文算法與對比算法的QR碼定位正確率對比

4.2.3 不同算法的定位效率對比

在實際應用中，QR碼的定位速度是評價定位算法的重要指標，本文采用平均定位時間作為定位速度的評價標準，本文算法與文獻［16］算法對圖書QR碼和火車票QR碼的實驗結果如圖8所示。從圖8可知，相對于文獻［16］算法，本文算法的平均定位時間最短，提高了QR碼定位的效率，可以滿足QR碼定位的在線需求，具有更高的實際應用價值。

圖8 本文算法與對比算法的QR碼定位效率對比

5 結束語

針對當前QR碼定位算法的不足，以獲得更高的QR碼定位正確率為目標，提出一種基于亞像素的QR碼圖像定位算法，并通過具體的仿真實驗對算法的性能進行測試。實驗結果表明，相對于當前經典的QR碼定位算法，基于亞像素的QR碼圖像定位算法提高了QR碼的定位正確率，而且加快了QR碼的定位速度，證明了本文算法的有效性，具有一定于實際的應用價值。

［1］李媛，李紅星，張益農.二維編解碼技術研究與應用［J］.北京聯(lián)合大學學報:自然科學版，2007，21(4):10-14.

［2］劉云龍，呂韜，曾晉，等.基于android手機的加密QR二維碼識別系統(tǒng)［J］.軟件，2012，33(4):34-36.

［3］張文愛，呂韜.物料數(shù)據(jù)加密QR碼識別系統(tǒng)的實現(xiàn)［J］.電子技術應用，2012，38(4):117-119.

［4］解龍，杜艷平，程明智，等.基于加密QR二維碼的商品包裝防偽技術［J］.北京印刷學院學報，2013(4):16-20.

［5］楊佳麗，高美鳳.一種QR碼的預處理方法［J］.計算機工程，2011，37(2):218-220.

［6］劉家昕，劉家朋，趙宇明.基于邊緣增強的二維碼區(qū)域快速檢測定位方法［J］. 計算機工程，2012，38(12):136-138.

［7］劉寧鐘，蘇軍，孫涵.工業(yè)控制環(huán)境中QR Code的檢測和識別算法［J］. 電子學報，2011，39(10):2459-2463.

［8］陽建華，鄭瑩娜.一種復雜條件下的QR碼圖像預處理算法［J］.科學技術與工程，2014，14(2):1671-1815.

［9］陳二陽.QR條碼圖像識別及解碼技術的實現(xiàn)［J］.電視技術，2013，37(7):16-19.

［10］熊用，汪魯才.基于相關匹配的QR碼識別方法［J］.儀器儀表學報，2011，32(3):571-576.

［11］陳杰.QR碼圖像預處理技術研究［J］.溫州大學學報:自然科學版，2010，31(6):16-23.

［12］余強，裴頌文，吳百鋒，等.基于圓檢測的二維條碼定位方法［J］. 計算機應用與軟件，2008，25(12):109-112.

［13］陳威兵，楊高波，馮璐.一種QR碼識別的低復雜度圖像預處理方法［J］.湖南大學學報:自然科學版，2012，39(10):93-97.

［14］衛(wèi)晉偉，戴曙光，穆平安.基于形態(tài)學和Hough變換的QR碼矯正與定位方法［J］.電腦與信息技術，2010，18(6):32-36.

［15］孫明，傅隆生，楊信廷，等.用于QR碼自動識讀的圖像分析方法［J］. 電子科技大學學報，2009，38(6):1017-1020.

［16］肖翔，劉曉明，王云柯.QR碼圖像的矯正與定位方法研究［J］.計算機科學，2007，34(11):217-219.