基于改進CORDIC算法的QR碼快速檢測硬件實現(xiàn)方法*

陳榮軍 ，于永興 ，鐘秀媚 ，謝舜道 ，趙慧民 ，譚洪舟

(1.廣東技術(shù)師范大學(xué) 計算機科學(xué)學(xué)院，廣東 廣州 510665；2.中山大學(xué) 電子與信息工程學(xué)院，廣東 廣州 510006)

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，二維條碼作為物聯(lián)網(wǎng)的入口有了越來越多的應(yīng)用場景。二維條碼具有信息密度大、糾錯能力強、可表示多種信息、可加密及制作成本低等優(yōu)點[1]，目前常用的二維條碼有QR碼、Data Matrix碼、PDF417碼等，其中QR碼(快速響應(yīng)碼)具有高密度、高可靠性以及可全方位快速識別等特點，因此廣泛應(yīng)用于生產(chǎn)流通、交通物流、質(zhì)量追蹤、電子商務(wù)等領(lǐng)域[2]。

在二維條碼研究領(lǐng)域，國內(nèi)外學(xué)者提出了多種掃描譯碼方法[3-7]，其中最常用的二維碼掃描方法是通過攝像頭獲取圖像緩存到存儲器，再由CPU或DSP讀取圖像數(shù)據(jù)進行圖像處理和譯碼，這種通過軟件進行二維碼掃描譯碼的方法需要占用總線時間長、譯碼速度慢，不適用于快速二維碼的識別應(yīng)用中。針對高速運動過程中二維條碼識別，文獻[3]提出了一種基于Halcon的XLD邊緣檢測識碼方法，該方法雖然提高了條碼定位過程的速度和準(zhǔn)確性；但是對檢測設(shè)備和檢測環(huán)境有一定的要求。文獻[4]設(shè)計了一種基于DM642的嵌入式平臺，用于QR碼的檢測，但識別系統(tǒng)的檢測過程較為復(fù)雜，并且需要額外的視頻解碼芯片，識別結(jié)果不能及時在PC端顯示。文獻[5]提出了一種基于游程編碼的QR碼快速檢測方法，但算法的檢測過程較為繁瑣，只能在毫秒級的時間內(nèi)定位到QR碼，實時性還有待提升，并且在低分辨率QR碼的檢測定位中表現(xiàn)不好。在文獻[6]中，提出了一種基于面向梯度直方圖(HOG)特征和支持向量機(SVM)分類器相結(jié)合的QR碼識別算法，但算法的復(fù)雜性較高，程序運行需要耗費較多的資源，因此在測試設(shè)備上仿真時，QR碼的檢測過程要超過1 s。文獻[7]中提出了一種基于Hough變換的矩碼檢測算法，該方法計算成本低、精度高，但QR碼檢測成功率與參數(shù)設(shè)置有關(guān)，且算法只是對拍攝到的整幅圖像進行邊緣提取，而沒有將檢測出的QR碼進行校正。

為了解決QR碼檢測譯碼速度慢、占用資源多等問題，本文基于FPGA和改進型CORDIC算法提出了一種純硬件實現(xiàn)的QR碼快速定位和校正提取的方法，該方法采用純硬件實現(xiàn)，直接對獲取的圖像數(shù)據(jù)流進行圖像預(yù)處理和快速Q(mào)R碼定位，可以極大地提高QR碼檢測速率，并且由于該方法采用CORDIC算法對QR碼圖像進行旋轉(zhuǎn)校正和提取，通過移位和加法器代替乘/除法器，因此可以大大減少硬件資源。

1 CORDIC算法的改進

1.1 CORDIC算法基本原理

CORDIC算法最早是1959年由VOLDER J E提出[8]，非常適用于FPGA實現(xiàn)[9]。CORDIC算法的基本思想是通過一組預(yù)先定義的基本角度集的逐次旋轉(zhuǎn)來逼近期望角度，其原理圖如圖1所示。

圖1 CORDIC算法原理

在圖1中，平面內(nèi)的初始向量q0(x0，y0)，逆時針旋轉(zhuǎn)β 角度后得到向量qn(x0，y0)，則q0與qn的關(guān)系可以寫成式(1)的矩陣形式：

假設(shè)β 是由連續(xù)n個滿足級數(shù)收斂的基本角度αi通過旋轉(zhuǎn)疊加而成的，即：

其中，ρi=1表示逆時針旋轉(zhuǎn)，ρi=-1表示順時針旋轉(zhuǎn)。由于在計算機中，角度計算過程都是按照二進制的形式，因此每次旋轉(zhuǎn)的基本角度可以取αi=arctan(2-i)，i=0，1，2，3，4，…，將式(2)代入式(1)可得：

環(huán)形坐標(biāo)旋轉(zhuǎn)的CORDIC算法包括兩種模式：旋轉(zhuǎn)模式(Rotation Mode，RM)和矢量模式(Vector Mode，VM)，RM模式用于給定旋轉(zhuǎn)角度值和向量長度求解相應(yīng)的正余弦值，VM模式用于給定向量坐標(biāo)求解向量長度及其與橫坐標(biāo)的夾角[10]。

1.2 改進CORDIC算法

傳統(tǒng)的CORDIC算法只需要通過移位和加法操作即可以實現(xiàn)復(fù)雜函數(shù)的求解，硬件復(fù)雜度低，當(dāng)?shù)螖?shù)足夠多時，可以達到較高的精度。級數(shù)收斂到99.88°[11]，故算法可表示的旋轉(zhuǎn)角度范圍為(-99.88°，99.88°)，不能覆蓋到整個圓周(-180°，180°)，因此需要對其進行擴展[12]。

文獻[13]提出了一種在傳統(tǒng)CORDIC算法基礎(chǔ)上增加兩級初次迭代的改進措施，方法原理簡單，易于實現(xiàn)，但由于增加了兩級初次迭代，使資源耗費增加。文獻[14]提出了一種新的基于CORDIC算法的反正切函數(shù)的FPGA計算方法，通過將算法的設(shè)計與FPGA設(shè)備的資源相適應(yīng)的方式，節(jié)省了由于Z路徑迭代運算引起的損耗，但電路面積和輸出時延仍較大。

CORDIC算法的迭代次數(shù)與每次迭代的角度如表1所示。

由表1可知，CORDIC算法表示的范圍與精度與迭代次數(shù)有關(guān)，當(dāng)i減小時，αi增大，可表示的范圍增大；當(dāng)i增大時，迭代角度αi減小，其可表示的精度越高；特別地，當(dāng)i=0時，對應(yīng)的角度為45°，i增加時，arctanαi逐漸減小，由于180°-99.88°=80.12°，當(dāng)i=-3時，α-3=82.875°＞80.12°，并且小于99.88°，因此可以增加一級i=-3以擴展旋轉(zhuǎn)角度范圍，且不會造成中間有無法逼近的角度，這是因為，即當(dāng)?shù)谝淮涡D(zhuǎn)82.875°后，可以由后面的迭代進行填充。

表1 級數(shù)收斂角度值

因此，設(shè)計采用一種在初始階段增加一次角度為α-3=arctan(23)的迭代的改進方法，相比于其他的改進方法，只需要在傳統(tǒng)算法基礎(chǔ)上添加一級流水線，使得該模塊能夠表示的角度達到360°內(nèi)的任意角。其原理簡單直觀，改進型CORDIC算法模塊的流水線如圖2所示。

圖2 CORDIC改進算法流水線

2 QR碼圖像檢測

QR碼圖像的檢測過程主要包括QR碼快速定位和校正提取兩大部分。

QR碼快速定位與校正提取的系統(tǒng)框圖如圖3所示。其中QR碼快速定位是在傳輸過程中直接對獲取的圖像數(shù)據(jù)流進行預(yù)處理和快速定位；然后采用改進型CORDIC算法對QR碼圖像進行旋轉(zhuǎn)校正和提取。

圖3 QR碼快速定位與校正提取

系統(tǒng)原理如圖4所示，在獲取圖像數(shù)據(jù)流的過程中對QR碼進行行列掃描，獲取到黑白條紋滿足1:1:3:1:1的點的位置信息，在一幀圖像的場同步期間對掃描點進行篩選，得到QR碼的位置信息，若篩選完成，則在定位到QR碼后進行校正提取。

圖4 QR碼快速定位與提取校正原理

2.1 QR碼快速定位方法設(shè)計

QR碼的快速定位即是找出其位置探測圖形的中心點坐標(biāo)及其尺寸信息。QR碼定位算法有很多：基于局部特征的定位方法[15]、基于最小二乘的定位方法[16]、基于邊緣檢測的定位方法[17]、基于凸包及最小面積外接矩形定位方法[18]等，這些檢測方法都較為復(fù)雜，不適于通過硬件實現(xiàn)。本設(shè)計采用的是基于QR碼圖像特征的快速定位方法，該方法識別率高，算法簡單，易于實現(xiàn)。

如圖5所示，QR碼是由深色、淺色正方形模塊排列成的一個正方形陣列，其中位置探測圖形位于符號的3個邊角，用于快速定位QR碼在原圖像中的位置，每個位置探測圖形由深色、淺色模塊按照1:1:3:1:1交替排列而成，該比例具有水平不變性[19]。

圖5 QR碼及其位置探測圖形

QR碼快速定位的原理如圖6所示。首先從攝像頭中獲取圖像數(shù)據(jù)流，對該原始圖像數(shù)據(jù)流進行格式轉(zhuǎn)換，將每個像素點的RGB轉(zhuǎn)換為灰度值，并將灰度化后的圖像數(shù)據(jù)流傳輸?shù)较乱患壎祷K。采用基于雙線性插值的局部二值化方法進行圖像二值化，計算出每幀圖像的二值化閾值，通過插值對下一幀圖像的每個像素點的灰度值進行判斷，得到二值化后的0/1數(shù)據(jù)流。由于該二值化方法是采用前一幀圖像的閾值來判斷下一幀圖像的灰度值，因此要求相鄰兩幀圖像之間的變化不能太大。二值化后的0/1序列一方面輸入到行掃描模塊中，檢測黑白條紋滿足1:1:3:1:1的線段；另一方面順序存入BUFFER中，用于將逐行輸入的數(shù)據(jù)流轉(zhuǎn)換成逐列輸出到列掃描模塊和用于提取二維碼圖像方塊。當(dāng)一幀二值圖像數(shù)據(jù)流到來時，進行逐行掃描，檢測1:1:3:1:1的線段，同時對存入BUFFER中的前一幀圖像數(shù)據(jù)按列輸出進行逐列掃描。可以看出，行/列掃描是分別針對前后兩幀數(shù)據(jù)進行檢測得到的結(jié)果，因此這也是必須基于獲取的圖像前后兩幀變化不大的情況才成立的。對行列掃描得到的兩組黑白條紋滿足1:1:3:1:1的線段坐標(biāo)及其對應(yīng)的黑白條紋平均單位寬度進行比對，如果行掃描得到的某個點的坐標(biāo)和寬度與列掃描得到的某個點的坐標(biāo)和寬度在允許范圍內(nèi)相等，則認為該點行列都滿足1:1:3:1:1關(guān)系。由于實際獲取的圖像可能會存在離焦模糊、上幾級模塊中設(shè)置了允許誤差等原因，導(dǎo)致掃描得到的點分散在周圍，因此需要將這些分散的鄰近點合并成一個點，再對合并后的點進行檢測，判斷出滿足等腰直角關(guān)系的3個點即為QR碼的3個位置探測圖形中心點。

圖6 QR碼快速定位流程圖

2.2 QR碼校正提取方法設(shè)計

由于在現(xiàn)實生活中，攝像頭獲取到的二維碼圖像大多不是完全端正的，具有一定的旋轉(zhuǎn)偏角，因此需要對二維碼圖像進行旋轉(zhuǎn)校正。本設(shè)計采用改進型CORDIC算法對QR碼圖像進行旋轉(zhuǎn)校正和提取。

首先根據(jù)QR碼快速定位模塊獲取到QR碼3個位置探測圖形的中心點坐標(biāo)q1(x1，y1)、q2(x2，y2)、q3(x3，y3)，然后將左上角和右上角位置探測圖形中心點構(gòu)成的向量q1q2(x2-x1，y2-y1)輸入到VM模式下的CORDIC模塊中，可以得到QR碼的旋轉(zhuǎn)角度β 和長度為l的向量q1q2。接著以左上角位置探測圖形的中心為坐標(biāo)原點，將QR碼旋轉(zhuǎn)校正后的每個點的坐標(biāo)(xi，yi)和旋轉(zhuǎn)角度β 輸入到RM模式下的CORDIC模塊中，可以得到QR碼旋轉(zhuǎn)校正后的每個點所對應(yīng)的原圖像坐標(biāo)(xo，yo)，從緩沖中讀取出坐標(biāo)(xo，yo)對應(yīng)的值0/1存儲到相應(yīng)存儲空間中即可提取出旋轉(zhuǎn)校正后的QR碼圖像，原理如圖7所示。

圖7 QR碼圖像旋轉(zhuǎn)校正

CORDIC算法可以通過設(shè)計成流水線的形式實現(xiàn)，對于N級流水線只有在其運作的第一輪會有N個時鐘周期的延遲，而后每個時鐘周期可以輸出一個有效值。本文將CORDIC算法運用于求圖像旋轉(zhuǎn)角度和圖像旋轉(zhuǎn)，因此這里需要兩次使用到CORDIC模塊，但圖像旋轉(zhuǎn)前必須先進行旋轉(zhuǎn)角度的確定，因此總共會有2N個時鐘周期的延時。由于CORDIC算法的VM模式和RM模式只存在每次迭代的符號判斷的差別，因此兩次的CORDIC運算可以通過同一條流水線實現(xiàn)，這樣可以節(jié)省一半的資源。

采集到的圖像分辨率的大小為640×480，當(dāng)CORDIC算法的迭代次數(shù)為9級(包括i=-3一級)時，旋轉(zhuǎn)精度可達到0.4476°，能滿足實際應(yīng)用的需要[20]，迭代次數(shù)確定后，此時校正因子也確定：K=1.992 4×10-4。在流水線的最后一級進行校正相比于在每一級校正不僅可以節(jié)約資源，而且可以提高精度，這是因為每一級的校正因子都小于1，導(dǎo)致每次校正后的結(jié)果都會變小，由于寄存器中的數(shù)位是有限的，每次校正后其精度會變小。校正采用移位和加法操作代替乘法器，可以進一步節(jié)省資源。

3 實驗仿真

在Quartus II 10.0環(huán)境下，采用Altera公司提供的Cyclone IVE FPGA芯片和500萬像素的MT9P001攝像頭，將設(shè)計的模塊進行綜合編譯，生成下載文件，配置到實驗板上進行驗證，驗證平臺使用的是友晶公司提供的DE2_115實驗板。

3.1 實驗內(nèi)容與過程

本設(shè)計主要包括了QR碼快速定位和QR碼的校正提取兩大部分。其中QR碼的快速定位包括以下幾個模塊：圖像獲取、圖像灰度化、二值化等預(yù)處理；QR碼校正與提取部分采用CORDIC算法對QR碼圖像進行旋轉(zhuǎn)校正和提取。

首先在PC上通過MATLAB對該設(shè)計進行仿真，驗證算法的可行性和有效性。其后，采用Verilog/VHDL硬件描述語言進行硬件設(shè)計，并對設(shè)計進行ModelSim仿真和實際下載驗證。

3.2 實驗結(jié)果

通過實驗測試可知，QR碼快速定位與校正提取模塊消耗的資源為3 272個邏輯單元，整個模塊的最高時鐘頻率可以達到267.95 MHz，該系統(tǒng)可以實時地檢測出QR碼的3個位置探測圖形的中心點坐標(biāo)并顯示在屏幕上，使QR碼經(jīng)過旋轉(zhuǎn)校正后，可以在微秒級的時間內(nèi)提取出QR碼圖形，如圖8所示。

圖8 實驗結(jié)果

驗證結(jié)果表明，該設(shè)計能實時地跟蹤定位到QR碼并將其校正提取出來。

4 結(jié)論

相比于采用軟件實現(xiàn)的QR碼定位校正的系統(tǒng)而言，本文設(shè)計的實時的QR碼定位及校正的硬件實現(xiàn)方法可以極快速準(zhǔn)確地定位并截取出QR碼圖像方塊，為后續(xù)的譯碼環(huán)節(jié)提供方便，大大提高了QR碼掃描譯碼的速度；同時采用改進型CORDIC算法實現(xiàn)了圖像的旋轉(zhuǎn)校正，極大地節(jié)省了硬件資源，提高了系統(tǒng)的時鐘頻率。而且系統(tǒng)還可以進一步地擴展，添加對其他類型的碼的檢測定位等。