基于游程編碼的QR碼圖像識別

侯阿臨， 馮 源， 焦松林， 郭云飛， 王樂樂

（1.長春工業大學計算機科學與工程學院，吉林長春 130012; 2.長春大學計算機科學技術學院，吉林長春 130021）

0 引 言

近幾年，隨著世界經濟的迅猛發展，條形碼的應用越來越廣泛。特別是在票據條碼印刷、食品藥品條碼印刷方面一維條碼越來越難以滿足要求。一維條碼由于對計算機網絡、后臺數據庫過分依賴而很難進行深入的推廣應用。QR碼即快速反應的意思，來自英文“Quick Response”的縮寫[1]。QR碼比傳統的條碼能存儲更多的信息，不再需要像掃描傳統條碼一樣直線對準掃描器。使用紅外光增強攝像頭取代了這方面的工作，直接對相機采集到的圖像中QR碼圖像進行軟件識別，所以降低了對反射角度的要求。然而QR碼作為二維條碼的一種，它具有高密度、大容量糾錯能力強等特點，能高效地體現出漢字的特點，因此在我國有廣泛的應用前景[2]。在實際應用中要對QR碼圖像進行采集、存儲、識別、檢測等工作，其中的過程引入一定規模的噪聲，使之應用有了一定的限制，尤其給圖像的識別造成了一定的難度。二維條碼的識別是集機器視覺和模式識別、圖像處理技術于一體的智能系統，是一個重要的研究課題。我們對QR碼圖像識別的預處理技術進行深入研究，通過改進濾波技術、增加定位塊檢測和定位校正等關鍵技術，有效提高二維條碼譯碼的實用性、可靠性。

文中以工業相機采集的QR碼圖像為例，討論QR碼的圖像處理與識別方法。

1 QR碼的圖像處理

QR碼是由日本Denso公司于1994年9月研制的一種矩陣二維條碼符號，每個QR碼符號由正方形模塊組成的一個正方形陣列構成，由編碼區域和包括尋像圖形、定位圖形和校正圖形等功能圖形組成，其符號大小由版本決定。QR碼符號共有40種版本，分別為版本1、版本2…版本40[3]。版本l的規格為21模塊×21模塊，版本2的規格為25模塊×25模塊，依此類推，每一版本比前一版本每一邊增加4個模塊，直到版本40，其規格為177模塊×177模塊（模塊指每一個黑色或白色小正方形）[4]。

每個QR碼都是由正方形模塊組成的一個正方形陣列構成，分為編碼區和功能區，功能區不能用于數據編碼，符號的周圍為空白區[5]。QR碼的結構如圖1所示。

圖1 QR碼結構

1.1 QR碼圖像處理的軟件流程圖

在過去的幾年里，學者們對QR碼已經進行了很多研究，但是在速度上的提高不是很大。文中根據QR碼圖形特點，結合圖像的定位方法，提出一種快速檢測QR碼的算法。

QR碼圖像處理流程主要包括圖像的尋像圖形檢測、圖像定位以及識別圖像，如圖2所示。

圖2 QR碼圖像處理流程

1.2 圖像的采集

QR碼圖像如圖3所示。

圖3 QR碼圖像

在圖像處理過程中，圖像的采集是首要的步驟。文中采用工業用單色攝像頭對QR碼圖像進行采集，采集到QR碼圖像為二維灰度圖像，見圖3（a）。

1.3 圖像的二值化

圖像的二值化關鍵在于閾值的選取。二值化閾值方法主要有直方圖雙峰法、微分直方圖法、最大類間方差法。在文中的QR碼識別系統中，采集原圖像后，做出直方圖，再將直方圖經過平滑后，呈現出明顯的雙峰特性[6]。這樣，使用簡單的直方圖雙峰法就可以快速地確定圖像的二值化閾值，處理結果見圖3（b）。

1.4 游程編碼——形成圖形組件

游程編碼是將信源符號中的相同字符轉換成一個計數字段，再加上一個重復字符標志。這種方法對于二值圖像最為有效，所以在這里采用游程編碼這種方法。將圖像轉化為一串串由黑白相間的像素組成的碼流，相鄰行的碼流間有關聯的碼流劃分為同一個組件，從頭掃描圖像，這樣掃描下去，有關聯即為同一組件，這樣就把整個圖像的所有組成圖形顯示出來，而且速度較快。

1.5 濾波

做QR碼圖像的直方圖，即x軸方向投影，將邊緣處投影點數小于整幅圖像像素點數1%的部分用濾波器濾除掉，以得到一幅去噪后的圖像，便于下一步定位尋像圖形。

1.6 位置探測圖形

圖形本身的特征信息有一種包含關系在里面，圖形中心小塊與整個尋像圖形之比為9∶49，將符合此特征的區域確定為尋像圖形。找到尋像圖形以后，按此規則繼續找到余下的2個尋像圖形，3個尋像圖形位置的確定就完成了整個QR碼圖像的定位，根據校正圖形和定位圖形建立取樣網格[7]。A點為左結合點，B點為右結合點，兩點間的距離一定。

位置探測圖形如圖4所示。

圖4 位置探測圖形掃描

2 QR碼的解碼

由于在QR碼符號中可能存在污損，導致數據讀取錯誤，因此在譯碼前，對得到的數據需進行糾錯，有了糾錯，大大提高了QR碼的可識讀性。通常QR碼采用 Reed2 Solomon對數據進行糾錯。Reed2 Solomon碼是一種擴展的非二進制BCH碼，在伽羅華域中進行運算[8]。

QR碼解碼基本流程大致有以下幾個步驟:

1）識讀格式。先進行格式的提取，再提取版本信息，最后提取識別糾錯等級和掩模圖形。

2）去掩模。用掩模圖形對矩陣中的編碼區域進行異或處理[9]。

3）碼字提取。從數據矩陣中，按照數據模板的排列方式，將0，1數據提取出來，得到數據碼字流和糾錯碼字流，便于下一步進行RS糾錯。

4）RS糾錯。確定符號碼字，并根據符號版本和糾錯等級需求，將碼字序列重新按塊排列。應用檢測和糾錯譯碼程序，糾正替代錯誤與拒讀錯誤，直到規定的糾錯容量。接著重新組配數據塊序列，恢復原始信息的位流，并將數據流分成若干塊，對每一段譯碼[10]。二進制譯碼算法只需要找出錯誤位置，在這里主要使用BM迭代算法，迭代過程表見表1。

表1 迭代過程表

以下舉例說明此算法。

表1中σ（i）為錯誤位置多項式，di為i+1與i步之間的差值，Li為σ（i）的次數。BM算法能夠快速根據伴隨多項式s求出錯誤位置多項式。當位置多項式根為α5，α14，那么說明發生錯誤位置為α14，α5，即錯誤發生在x14和x5上面。

5）數據解碼:對糾錯后的數據按照使用的模式信息進行解碼，得出數據字符并輸出結果。

QR碼圖像識別如圖5所示。

圖5 QR碼圖像識別

3 結 語

通過對圖像的濾波、二值化、編碼等進行圖像預處理，將游程編碼方法用于二值化的圖像，進行QR碼圖像中組件圖形的選取，從實質上解決了圖像處理的速度問題，也提高了圖像處理的質量，正是由于速度的提高，使其在工程現場的應用成為可能，在條形碼檢測領域具有實用價值。

[1] Daniel Walsh，Adrian E Raftery.Accurate and efficient curve detection in images:the importance sampling Hough transform[J].Pattern Recognition，2002，35（7）:1421-1431.

[2] 陳媛媛，施鵬飛.二維條形碼的識別及應用[J].測控技術，2006，25（12）:17-19.

[3] 萬菁.二維條碼的編解碼及系統實現[D]:[碩士學位論文].上海:上海交通大學，2007.

[4] 王新梅，肖國鎮.糾錯碼原理與方法[M].西安:西安電子科技大學出版社，2001.

[5] 國家質量技術監督局.快速響應矩陣碼 GB/T 18284-2000[S].北京:中國標準出版社，2001.

[6] 章毓晉.圖像處理與分析[M].北京:清華大學出版社，1999.

[7] 劉東，高西全.QR碼圖像處理及識別算法的研究[J].信息技術，2004，28（1）:61-62.

[8] 葉情貴，劉宇懷.RS碼糾錯算法的軟件實現[J].華東師范大學學報:自然科學版，2005（4）:98-101.

[9] 尚曉航.網絡系統管理:WINDOWS 2003篇[M].北京:人民郵電出版社，2006.

[10] 張球英.二維條碼-QR code研究及應用[D]:[碩士學位論文].石家莊:華北工學院，2003.