山東大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 山東工藝美術(shù)學(xué)院公共課教學(xué)部 姜 亮

基于游程編碼思想的條碼定位與識別方法

山東大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 山東工藝美術(shù)學(xué)院公共課教學(xué)部 姜 亮

在復(fù)雜背景中的定位條碼是圖像式條碼識別系統(tǒng)中的一個關(guān)鍵步驟，如何在復(fù)雜的背景中快速、自動地檢測出條形碼是研究的主要內(nèi)容。首先介紹了條型碼的編碼結(jié)構(gòu)。然后提出了一種基于游程編碼思想的條碼定位與識別方法。最后通過給出相關(guān)實(shí)驗結(jié)果驗證了算法的可行性和實(shí)用性。

條碼定位；條碼識別；游程編碼

隨著智能手機(jī)的普及，研究利用數(shù)字圖像處理方法實(shí)現(xiàn)條形碼的定位和識別具有重要的理論意義和實(shí)際價值。將條形碼區(qū)域從整幅圖像中定位提取出來，為下一步的譯碼識別提供良好前提，是首要的一步。定位條形碼區(qū)域要求準(zhǔn)確快速，是條形碼圖像處理識別系統(tǒng)的重要環(huán)節(jié)。一維條形碼廣泛應(yīng)用于商品流通領(lǐng)域，最具有代表性的是EAN-13商品條形碼。

1.EAN-13商品條碼的的編碼規(guī)則

1.1 EAN-13商品條碼的符號結(jié)構(gòu)

EAN-13商品條碼由左側(cè)空白區(qū)、起始符、左側(cè)數(shù)據(jù)符、中間分隔符、右側(cè)數(shù)據(jù)符、校驗符、終止符、右側(cè)空白區(qū)和供人識別字符組成。如圖1和圖2所示。

1.2 EAN-13商品條碼字符集的二進(jìn)制和符號表示

商品條碼采用模塊組合法進(jìn)行編碼，組成條形碼符號的基本單位稱為模塊。每個條碼字符由2個“條”(bar)和2個“空”(space)組成。每個“條”或“空”由1～4個模塊組成，每個條碼字符的總模塊數(shù)為7。

圖1 EAN－13商品條碼的符號結(jié)構(gòu)

圖2 EAN－13商品條碼符號構(gòu)成示意圖

表1 商品條碼字符集的二進(jìn)制表示

表2 左側(cè)數(shù)據(jù)符商品條碼字符集的選用原則

圖3

圖4

圖5

圖6

EAN-13商品條碼字符集可表示0～9共10個阿拉伯?dāng)?shù)字符號，每個數(shù)字字符對應(yīng)3種編碼形式，即左側(cè)數(shù)據(jù)符奇排列A子集、左側(cè)數(shù)據(jù)符偶排列B子集以及右側(cè)數(shù)據(jù)符偶排列C子集。10個數(shù)字有30種編碼。這里的“奇”或“偶”是指所含二進(jìn)制“l(fā)”的個數(shù)為偶數(shù)或奇數(shù)。商品條碼字符集的二進(jìn)制表示如表1所示。

1.3 EAN-13商品條碼的數(shù)據(jù)符

前置碼不包括在左側(cè)數(shù)據(jù)符內(nèi)，不用條碼字符表示。我國的國別識別碼為690，因此前置碼為6。左側(cè)數(shù)據(jù)符選用A，B子集進(jìn)行二進(jìn)制表示，且取決于前置碼的數(shù)值，見表2。右側(cè)數(shù)據(jù)符及校驗符均用C子集表示。

2.基于游程編碼思想的條碼定位方法

一維條形碼的特點(diǎn)是由平行的黑白條按一定規(guī)則組成，黑條可簡稱為條，白條可簡稱為空，理想條形碼圖像中黑白邊界明顯，具有很強(qiáng)的邊緣特性?；跅l形碼的這種構(gòu)成特點(diǎn)，本文提出一種基于游程編碼思想的條碼定位方法。

通過觀察二值化圖像，我們可以發(fā)現(xiàn)，條碼所在的行有一個顯著的特征是，在一個固定的寬度內(nèi)，像素點(diǎn)會頻繁的從黑點(diǎn)變成白點(diǎn)，從白點(diǎn)變成黑點(diǎn)，這樣的變化次數(shù)很多。根據(jù)EAN-l3條碼的編碼規(guī)則我們可以知道，每個EAN-l3條碼都是由30個寬窄不同的黑條組成，那么在條碼所在的區(qū)域，黑白變化次數(shù)應(yīng)該是60次。在二值化圖像中，僅存在兩種編碼0和1，用以表示圖像信息。0表示黑色像素點(diǎn)，1表示白色像素點(diǎn)。這樣可以大大節(jié)省存儲空間。如圖3所示。

雖然像素點(diǎn)被存儲為0或1，節(jié)省了大量的存儲空間。但是，以此方式存儲的圖像，并不能方便的獲得相鄰多個黑（或白）像素點(diǎn)的個數(shù)，也即條和空的寬度。為了方便定位條碼區(qū)域，以及方便計算條碼的條和空的寬度?；谟纬叹幋a思想，我們對二值化圖像重新編碼，如圖4所示。

在此編碼方式下，連續(xù)相鄰的n個白色像素點(diǎn)存儲為一個負(fù)整數(shù)-n。連續(xù)相鄰的m個黑色像素點(diǎn)，存儲為一個正整數(shù)m。由此，對于一個高為H，寬為W的二值化圖像f(x，y)，可以創(chuàng)建一個二維數(shù)組存儲重新編碼后的圖像。此二維數(shù)組的高是H，寬為W/2+1：

政府部門宜進(jìn)一步推動對“河長制”相關(guān)信息公開建設(shè)的規(guī)范化工作的落實(shí)，加大“河長制”信息建設(shè)投入，盡快理清河流水系對應(yīng)的行政區(qū)劃和上下級河長。同時，規(guī)劃制度實(shí)施目標(biāo)、時間進(jìn)度、完成指標(biāo)等必要信息在政府政務(wù)信息公開門戶上的定期定時公開，保證社會公眾對制度實(shí)施相關(guān)情況的知情與監(jiān)督，確?！昂娱L制”工作的更加有效的開展。

二維數(shù)組A[W/2+1,H]中每一行的第一個元素，存儲當(dāng)前行的編碼個數(shù)，也即條和空的個數(shù)。

2.1 正向條碼定位

由EAN-13條碼的編碼規(guī)則可知，對于一個掃描行，至少會有60次的黑白變化。那么對于掃描行中是否含有條碼信息的判斷，就等同于判斷該掃描行中第i個元素S[i]是否是左側(cè)空白區(qū)。掃描行數(shù)據(jù)存儲在數(shù)組S[W/2+1]中，S[0]存放該掃描行編碼個數(shù)。判斷條件如下：

算法1：

(1)S[0]＞60，該掃描行包含多于60次的黑白變化

(2)S[i]＜0，是白色空白區(qū)域

(3)abs(S[i])＞10*S[i+1]，左側(cè)空白區(qū)域的寬度大于10倍的第一個條的寬度

(4)S[i+1]，S[i+2]，S[i+3]寬度比例是1:1:1。也即起始標(biāo)志符，條空條。

(6)S[i+57]，S[i+58]，S[i+59]寬度比例是1:1:1。也即結(jié)束標(biāo)志符，條空條。

滿足以上六個條件，即可判斷S[i]就是左側(cè)空白區(qū)域。

2.2 反向條碼定位

由EAN-13條形碼的編碼規(guī)則可知，對于反向的條碼，只要把算法1條件（3）abs(S[i])＞10*S[i+1]

改為：abs(S[i])＞6*S[i+1]

把條件（5）abs(S[i+60])＞6*S[i+59]

改為：abs(S[i+60])＞10*S[i+59]

即可實(shí)現(xiàn)對反向條形碼的定位。更進(jìn)一步，只是把算法1的條件（3）修改，條件（5）不變。則，新算法即可以定位正向條碼也可以定位反向條碼。然而，由于有些條形碼在印刷時，背景與左右空白區(qū)域沒有區(qū)分，如圖6所示。所以并不能以此來判斷條碼的方向。上述算法旨在說明，用此方法也可以定位到一個反向的條碼。條碼方向的確定在3.3節(jié)討論。

表3 條碼譯碼表

圖7

3.條碼識別

3.1 模塊寬度的計算

由EAN-13條形碼的編碼規(guī)則可以知道，一個條或者空的寬度可以是1、2、3、4個模塊寬度，條碼從起始符到結(jié)束符總計95個模塊。若i是左側(cè)空白區(qū)的下標(biāo)，則i+1是第一個條的下標(biāo)，i+59是最后一個條的下標(biāo)。那么，在S[i]確定存儲的是左側(cè)空白區(qū)域后，可以用下面方法求得模塊的平均寬度：

3.2 條空寬度歸一化

由EAN-13條形碼的編碼規(guī)則可以知道，一個數(shù)字字符由2個條和2個空，共計7個模塊組成。一個條或者空可由1個、2個、3個或4個模塊組成。設(shè)表示一個條空的寬度，也即黑（或白）色像素點(diǎn)的個數(shù)。w為正整數(shù)，代表條。w為負(fù)整數(shù)，代表空。表示模塊的平均寬度。那么w中包含模塊的個數(shù)，也即，條空的歸一化結(jié)果wg可由下式確定：

條碼的條空寬度歸一化后，有八個可能的取值。分別是-1，-2，-3，-4，1，2，3和4，八個整數(shù)。正值表示條，負(fù)值表示空。絕對值表示條（或空）包含的模塊的個數(shù)。

3.3 條碼方向的確定

為了能夠正確解碼條形碼，在解碼工作之前，首先應(yīng)該進(jìn)行條碼方向的判別。EAN-13的起始字符和終止字符的編碼結(jié)構(gòu)相同，都是條空條。所以，不能通過起始符和終止符來判斷條碼的方向。由條碼的編碼結(jié)構(gòu)可知，在EAN-13條形碼中，右側(cè)數(shù)據(jù)均由C子集編碼，而C子集是偶排列。也即，右側(cè)字符數(shù)據(jù)的編碼，含有黑色模塊的個數(shù)都是偶數(shù)。而左側(cè)數(shù)據(jù)，有A子集也有B子集編碼。以此性質(zhì)，即可判斷條形碼的方向。通過觀察表2可以知道，左側(cè)第一字符的編碼都為A子集，是奇排列；右側(cè)最后一個字符，也即校驗碼的編碼是C子集，是偶排列。因此，通過判斷掃描到的第一個字符采用的是奇排列還是偶排列就可以確定條碼的方向。如果第一個字符是奇排列，條碼方式就是正方向；否則，就是反方向。設(shè)wg1、wg2、wg3、wg4分別表示第一個字符的四個條和空?？梢灾溃瑆g1是第一個空，wg2是第一個條，wg3是第二個空，wg4是第二個條。且，wg1和wg3是負(fù)整數(shù)，表示空。wg2和wg4是正整數(shù)，表示條。那么，wg2+wg4的和是奇數(shù)，條碼就是正方向；是偶數(shù)，就是反方向。

3.4 前置碼的確定

在EAN-13的編碼中并不包含對前置碼的編碼。觀察表2可以看到，前置碼和左側(cè)數(shù)據(jù)的字符集編碼是一一對應(yīng)的關(guān)系?？梢哉f，前置碼決定了左側(cè)數(shù)據(jù)區(qū)的每個字符采用A子集還是B子集進(jìn)行編碼。反過來也可以說，左側(cè)數(shù)據(jù)區(qū)字符編碼的奇偶排列順序，決定了前置碼。比如，如果某個條形碼的左側(cè)數(shù)據(jù)區(qū)的編碼是：奇偶偶偶奇奇，那么前置碼就是6。

3.5 條碼譯碼

經(jīng)由條碼的條空寬度歸一化到-1，-2，-3，-4，1，2，3和4八個整數(shù)后，創(chuàng)建譯碼表，表3所示。譯碼工作通過查詢此表即可實(shí)現(xiàn)。例如：某個字符的四個條空寬度分別是，-3，1，-2和1，經(jīng)查表可知，這個字符是“8”。

4.實(shí)驗結(jié)果分析

仿真實(shí)驗使用VC++ Express 2008和OpenCV開發(fā)平臺。實(shí)驗表明，本文算法效果良好。對于光照不均勻，輕微模糊，及傾斜角在正負(fù)25度內(nèi)的條碼圖像，都能正確識別。如圖7所示。

[1]中國標(biāo)準(zhǔn)出版社.條碼國家標(biāo)準(zhǔn)匯編[M].北京:中國標(biāo)準(zhǔn)出版社,2004.

[2]陸宗騏.C/C++圖像處理編程[M].北京:清華大學(xué)出版社,2005.

[3]蘇彥華.VC++數(shù)字圖像識別技術(shù)典型案例[M].北京:人民郵電出版社,2004

[4]沈庭芝.數(shù)字圖像處理及模式識別[M].北京:北京理工大學(xué)出版社,1998.

It is a critical step in image-type barcode recognition system that to automatically locate the barcode in complex background，the main point of this paper is to detect the barcodes in complex background quickly and automatically.First the paper introduces bar code structure.Then，an effective and rapid algorithm was proposed to localize and recognize barcode based on runlength coding.Finally，the feasibility of the algorithm is conf i rmed through relevant experimental results.

barcode localization；barcode recognition；run-length coding

姜亮（1980—），男，研究生，研究方向：計算機(jī)應(yīng)用。