快速響應矩陣碼的多級閾值化方法

(1.濟南大學 信息工程學院， 山東 濟南 250022； 2.北京理工大學 計算機系， 北京 100081； 3.昆明理工大學， 云南 昆明 650093)

摘 要：為適應在不同光照、不同尺寸、不同灰度下快速響應矩陣碼圖像的二值化處理，提出了一種集全局閾值、局部閾值和多級閾值化的二值化算法。實驗結(jié)果表明，該算法性能優(yōu)越，明顯地提高了條碼的識別率，可以滿足實時場景下條碼的譯碼應用。 

關鍵詞： 快速響應矩陣碼； 二值化； 閾值 

中圖法分類號： TP391文獻標識碼： A

文章編號： 1001 3695(2006)08 0177 03



Multi level Threshold Method of Quick Response Code



LIU Yue 1，2 ， LIU Ming ye2， SHANG Zhen hong3

(1.School of Information Engineering， Jinan University， Jinan Shandong 250022，China; 2.Dept. of Computer， Beijing Institute of Techno logy ， Beijing 100081， China; 3.Kunming University of Science Technology， Kunming Yunnan 650093， China）

Abstract: In order to adapt quick response code image to various sizes and gray level values， as well as different lighting sources， a novel multi level thresholding method is developed， which locates the accurate finder pattern and integrates local threshold method with global threshold. It can achieve higher recognization rate of high density bar code， and is applicable to real world scene image.

Key words: Quick Response Code; Binarization; Threshold

條碼是一種采集速度快、成本低、可靠性強的自動識別技術。相對一維條碼，二維條碼具有信息密度高、容量大、糾錯能力強，可以表示數(shù)字、字母、漢字、圖像等信息的優(yōu)點。在符號中出現(xiàn)少量污損時，二維條碼經(jīng)過糾錯可得到正確的原始信息。因此二維條碼廣泛應用于交通管理、物流管理、身份驗證、電子商務等領域[1]。二維條碼按照結(jié)構(gòu)可分為堆積式和矩陣式兩類。堆積式二維條碼以DF417條碼為代表，由多行一維條碼堆積形成。矩陣式二維條碼符號是矩形，信息分布在矩形內(nèi)，以像素點的黑白來表示信息，如快速響應矩陣碼。快速響應矩陣碼（Quick Response Code，QR Code或QR碼）是Denso公司于1994年開發(fā)的二維條碼，具有全方位超高速識讀的特性。我國于2000年制定了等效國家標準《快速響應矩陣碼》[2] ，可以高效表示中國漢字，這種其他二維條碼無法比擬的優(yōu)勢，推動了QR碼在中國的推廣和應用。

目前我國在二維條碼領域有兩個國家標準，即有關PDF417和QR Code。由于這兩種二維條碼都是國外研制的，其條碼的識讀設備和軟件均需要花費大量資金購買。在研究方面，大量學者對PDF417進行了深入研究[3]，而QR Code是矩陣式二維條碼，有關QR Code識讀的研究在國內(nèi)外文獻較少。如何快速有效地識讀是一個值得研究的問題。QR碼的識別方法不同于一維條碼，根據(jù)編碼區(qū)域外的功能圖形來定位符號，決定其尺寸和方位。QR碼的信息容量是最大的，二維條碼的信息密度越高，識讀難度越大，受周圍光照影響也越大，因此如何快速準確地識讀矩陣式二維條碼成為一個值得研究的問題。

閾值選取是二維條碼正確識別的基礎。條碼的廣泛應用要求對條碼的識別要適應不同的環(huán)境，如不同光照、不同視角、不同采集設備、條碼的污損、噪聲等。這使得采用一種方法對所有環(huán)境下的條碼進行準確的二值化很困難。通過數(shù)據(jù)采集裝置獲得條碼圖像后，先進行二值化，然后定位三個探測圖形，根據(jù)探測圖形，確定版本、傾斜角度，確定采樣網(wǎng)格，進行采樣譯碼。在整個譯碼過程中，二值化是成功譯碼的前提，直接關系到能否正確識讀。本文對QR碼進行了簡單介紹，針對光線差、不均勻光照、淡色等情況提出了一種多級閾值選取的二值化算法，通過這種方法可以對不同情況下的條碼進行快速準確的二值化，并通過實驗和比較進行驗證。

1 QR Code簡介

QR碼由正方形模塊排列于正方形圖形中，包括位于符號三個角上的探測圖形，它可以幫助確定符號的位置、尺寸和傾斜度。QR碼有40個版本，四個糾錯等級，可以對7 089個數(shù)字或者4 296個字母數(shù)字進行編碼，最高糾錯等級為30%碼字。輸入數(shù)據(jù)經(jīng)過數(shù)據(jù)編碼為數(shù)據(jù)碼字，產(chǎn)生糾錯碼字，將功能圖形與碼字序列一起放入矩陣，選擇掩模圖形對編碼區(qū)域掩模后，加入版本和格式信息，構(gòu)成符號。如圖1所示，編碼內(nèi)容為Quick Response Code，版本是2，糾錯等級為L。功能圖形由探測圖形、分割符、定位圖形和校正圖形等組成，功能圖形不用于數(shù)據(jù)編碼，符號的四周為空白區(qū)。在條碼的譯碼過程中，三個探測圖形中心坐標的定位起非常重要的作用。

2 QR碼的二值化

2.1 現(xiàn)有圖像二值化算法

在國內(nèi)外的圖像處理實踐中，二值化方法很多[4～6]。不同的圖像二值化方法各有特點，對于同一幅圖像處理效果也不同。二值化方法可以分為全局和局部二值化方法。全局二值化方法根據(jù)某種規(guī)則、統(tǒng)計或推理來自動計算閾值，如判別分析法、類別方差法、熵法等。其核心思想是采用試探法，逐步選擇閾值，使二值分割滿足某種評判規(guī)則。局部閾值算法是將原始圖像分成若干子塊，對每一塊分別采用一種全局閾值方法計算其分割閾值。這種方法減少了由于光照不均勻變化所帶來的圖像不同部分灰度的變化影響。

2.2 QR碼的全局二值化處理

全局二值化方法，如協(xié)相關矩陣、圖像二維熵二值化等，這類方法雖然兼顧了圖像整體和局部的特征，但由于模型復雜、計算量大、不適于在嵌入式系統(tǒng)中運行。

全局閾值分割的最大缺點是對整幅圖像采用單一閾值，當光照不均勻時采用單一閾值進行分割。閾值選取大，會造成把部分背景像素分割到條碼部分，產(chǎn)生二值化錯誤，如圖2(a)所示；閾值選取小，造成部分條碼像素分割到背景中，產(chǎn)生過分，如圖2(b)所示，導致部分探測圖形比例失調(diào)（探測圖形是黑白相間的三層，橫向或縱向掃描要滿足黑白比例 1∶ 1∶ 3∶ 1∶ 1 的比例），定位失敗，而探測圖形的準確定位是QR碼正確譯碼的前提。 

2.3 QR碼的局部二值化

為克服全局閾值分割時造成的問題，將圖像分成 n塊子圖像，然后對n 塊子圖像局部采用全局閾值的方法進行分割。這種方法可以減輕整幅圖像內(nèi)條碼和背景灰度不均勻變化帶來的影響。但也存在一定缺陷，如分塊子區(qū)域的確定是人為事先決定的，不是依據(jù)條碼本身灰度的不均勻性，導致塊間分割不連續(xù)性，如果塊間正好在探測圖形中，則影響相鄰塊間模塊寬度，使得探測圖形比例失調(diào)，如圖3所示。

2.4 已有QR Code二值化方法

QR Code標準中提供了一種取最大和最小極值的均值作為閾值的全局閾值方法[2]。此方法對光照不均勻和光源照明較暗，灰度直方圖并不呈現(xiàn)雙峰時，處理效果不理想。Ohbuchi等人[7]在研究QR Code識讀預處理部分時采用了全局閾值方法。它將320×240分辨率的條碼圖像，中心60×60的方形區(qū)域分成九塊，分別計算直方圖，然后在每一塊內(nèi)按照像素灰度值排序，塊內(nèi)閾值取排序后灰度的中值，最后定義所有區(qū)域閾值的最小值作為整幅圖像的閾值。Ohbuchi算法存在兩個問題：①此方法的前提是條碼圖像必須位于攝入圖像中心，這樣最后得出的全局閾值才能較好地對圖像進行二值化。如果條碼符號在整個圖像的某一個角上，則此算法失敗。②這種方法容易產(chǎn)生過分現(xiàn)象，將部分條碼圖像分割為背景，導致后面譯碼失敗。

3 多級閾值化算法描述

3.1 多級閾值算法

鑒于采用全局閾值、局部閾值均不能很好地解決條碼在多種光照情況下的二值化問題，提出一種多級閾值自適應二值化的方法。對于灰度條碼圖像，計算其直方圖，為了去除噪聲干擾，對直方圖進行中值濾波，分析直方圖的峰值特性。如果得到明顯雙峰的直方圖，取雙峰間的波谷最低值或平坦波谷的中間值作為全局閾值，對條碼圖像進行二值化，避免對普通圖像采用復雜的閾值算法帶來無意義的時間和空間消耗。但是實際攝入的圖像有一部分是直方圖呈現(xiàn)單峰或者三峰的特征，說明圖像處于光照弱、光照強、背景復雜或者光照不均勻等情況。對于直方圖是單峰，并且單峰區(qū)域位于低灰度區(qū)，則認為條碼處于弱光下，反之條碼處于強光下，采取二次閾值選取的處理方式。如果直方圖呈現(xiàn)三峰狀態(tài)，說明條碼處于光照不均勻或背景復雜的情況，采用局部閾值進行二值化。

之所以不對所有條碼都進行分塊局部閾值選取，原因有兩個：①分塊局部閾值算法時間消耗大，對于直方圖雙峰和光照偏強弱的圖像沒有必要采用局部閾值。②對于普通光照下條碼進行分塊局部閾值時，容易產(chǎn)生過分，同模塊塊間不同寬度導致條碼定位失敗（圖3）。綜上所述，集全局閾值和局部閾值結(jié)合的多級閾值方法綜合了全局閾值和局部閾值兩種算法的優(yōu)點，既能滿足普通光照下條碼譯碼的快速實時性，又能滿足特殊光照下條碼譯碼的正確性。

3.2 算法描述

(1)將獲取的彩色條碼圖像轉(zhuǎn)換為灰度圖像， 并進行平滑處理。

(2)計算直方圖，根據(jù)直方圖判斷峰值。如果為雙峰，取雙峰間的波谷為閾值進行全局二值化，轉(zhuǎn)(5)執(zhí)行；否則，繼續(xù)。 

(3)如果為單峰，圖像處于低灰度區(qū)域，取灰度值最高和最低極值的10%，求均值得到閾值 T1，在最低灰度與T1之間對灰度圖像再次求閾值，得到閾值T2，取兩次均值 T_low =（T1+T2）/2作為全局閾值，對圖像進行二值化。如果單峰在高灰度區(qū)范圍內(nèi)，在最高灰度與 T1之間對灰度圖像再次求閾值，得到閾值T3，取兩次均值T_high =（T1＋T 3）/2作為全局閾值，對圖像進行二值化，轉(zhuǎn)(5)執(zhí)行。

(4)如果為三峰，將圖像分成 m×n 塊，每一塊內(nèi)根據(jù)極值得到閾值 Tj（j=0，1，…，m×n） 進行二值化，定位三個探測圖像。 

(5)開始執(zhí)行條碼方位的確定、版本譯碼，根據(jù)校正圖形確定采樣網(wǎng)格、糾錯、數(shù)據(jù)碼字譯碼。

4 實驗和比較

為擴大條碼應用范圍，不是通過條碼專用識讀器進行的圖像采集，而是采用廣泛普及的帶攝像頭手機（30萬像素）作為采集設備，使它具有更普遍的實際意義。在不同光照、不同距離、不同視角的情況下采集了70個彩色條碼圖像。圖像的分辨率為640×480，分為普通光照、弱光照明、強光照明、不均勻光照、聚焦模糊幾類。

實驗對Otsu算法，Ohbuchi算法，QR標準給出的二值化算法與本文提出的多級閾值等四種算法進行了二值化比較，如圖4所示。

Ohbuchi算法根據(jù)分辨率采用了圖像中心點周圍120×120的區(qū)域分為九塊進行排序后取閾值的最小值作為全局閾值進行二值化。由圖4可以看出，多級閾值方法適用于多種光照情況，而其他三種算法在光照不均勻時二值化均存在較大偏差。采用多級閾值化方法，譯碼成功率達到99.9%。所有算法的成功識別率和執(zhí)行時間比較如表1所示。算法的時間測量是在微機上進行的，配置為Intel 400MHzCPU，128MB內(nèi)存。這些實驗結(jié)果表明本算法可以應用在不同強度的光照，不均勻光照下對QR條碼的正確二值化。

5 結(jié)論

本文針對矩陣式QR碼譯碼提出了一種集全局閾值和局部閾值自適應的多級閾值化算法，由于兼顧了圖像在不同光照情況下的各種可能和實時性要求，可以很好實現(xiàn)圖像的二值分割，其模型簡單、閾值選擇容易、處理速度快、空間占用少。此算法優(yōu)于現(xiàn)有的全局和局部閾值算法，對QR碼實時譯碼應用提供了一種快速可行的識別方法。由于源代碼在開發(fā)過程中考慮嵌入式系統(tǒng)要求，對于移植到嵌入式系統(tǒng)中帶來了很大便利，而且在算法中盡量避免浮點運算，在移植前后時間耗費不會有太大差異。

參考文獻：

[1] 矯云起，張成海. 二維條碼技術[M]. 北京：中國物價出版社，1996.

[2] GB/T18284 2000. 中華人民共和國國家標準——快速響應矩陣碼(QR Code)[S].國家質(zhì)量技術監(jiān)督局發(fā)布.

[3] 劉寧鐘，楊靜宇.基于傅里葉變換的二維條碼識別[J]. 中國圖像圖形學報，2003， 8(8):877-882.

[4] 盛業(yè)華，郭達志. 基于圖像集合運算的礦圖掃描圖像二值化方法[J].中國圖像圖形學報，1998， 3(12):1015-1019.

[5] Andreas E Savakis.Adaptive Document Image Thresholding Using Foreground and Background Clustering[C]. International Conference on Image Processing (ICIP)， 1998.785-789. 

[6] Akio Shio. Adaptive Document Image Thresholding Using Foreground and Background Clustering[C].Conference on Computer Vision and Pattern Recognition， 1989.632-637.

[7] Ohbuchi E， Hanaizumi H， Hock L A. Barcode Readers Using the Camera Device in Mobile Phones[C]. Proceedings of the 2004 International Conference on Cyberworlds， 2004.260-265. 

作者簡介： 劉悅(1970 )，女，講師，博士研究生，研究方向為自動識別、圖像處理；劉明業(yè)(1934 )，教授，博導，研究方向為自動識別、EDA； 尚振宏(1976 )， 博士，研究方向為圖像處理。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。