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

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

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

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

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

條碼定位；條碼識(shí)別；游程編碼

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

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

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

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

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

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

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

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

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

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

圖3

圖4

圖5

圖6

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

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

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

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

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

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

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

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

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

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

2.1 正向條碼定位

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

算法1：

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

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

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

(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)志符，條空條。

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

2.2 反向條碼定位

由EAN-13條形碼的編碼規(guī)則可知，對(duì)于反向的條碼，只要把算法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)對(duì)反向條形碼的定位。更進(jìn)一步，只是把算法1的條件（3）修改，條件（5）不變。則，新算法即可以定位正向條碼也可以定位反向條碼。然而，由于有些條形碼在印刷時(shí)，背景與左右空白區(qū)域沒(méi)有區(qū)分，如圖6所示。所以并不能以此來(lái)判斷條碼的方向。上述算法旨在說(shuō)明，用此方法也可以定位到一個(gè)反向的條碼。條碼方向的確定在3.3節(jié)討論。

表3 條碼譯碼表

圖7

3.條碼識(shí)別

3.1 模塊寬度的計(jì)算

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

3.2 條空寬度歸一化

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

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

3.3 條碼方向的確定

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

3.4 前置碼的確定

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

3.5 條碼譯碼

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

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

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

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

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

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

[4]沈庭芝.數(shù)字圖像處理及模式識(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ì)算機(jī)應(yīng)用。