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

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

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

0 引言

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

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

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

1 CORDIC算法的改進

1.1 CORDIC算法基本原理

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

圖1 CORDIC算法原理

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

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

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

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

1.2 改進CORDIC算法

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

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

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

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

表1 級數收斂角度值

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

圖2 CORDIC改進算法流水線

2 QR碼圖像檢測

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

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

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

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

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

2.1 QR碼快速定位方法設計

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

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

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

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

圖6 QR碼快速定位流程圖

2.2 QR碼校正提取方法設計

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

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

圖7 QR碼圖像旋轉校正

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

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

3 實驗仿真

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

3.1 實驗內容與過程

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

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

3.2 實驗結果

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

圖8 實驗結果

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

4 結論

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