結(jié)合列邊緣提取的PDF417 條碼檢測方法

汪魯才，劉 鑫，易錫年

湖南師范大學(xué) 工學(xué)院，長沙410081

1 前言

二維條碼（2-dimensional bar-code）PDF417 作為一種新的信息存儲和傳遞技術(shù)，經(jīng)過若干年的發(fā)展，已廣泛應(yīng)用于國防、公共安全、交通運(yùn)輸、醫(yī)療保健、工業(yè)、商業(yè)、金融、海關(guān)及政府管理等領(lǐng)域。而近年來?xiàng)l碼的識別設(shè)備已由光筆、激光、線陣CCDS 發(fā)展到第四代的圖像，使用數(shù)字?jǐn)z相機(jī)、攝相頭等來采集和獲取二維條碼圖像，并利用數(shù)字圖像處理技術(shù)對條碼進(jìn)行識別，已成為國內(nèi)外發(fā)展的主流。然而實(shí)際應(yīng)用中所采集的條碼圖像背景復(fù)雜，往往會伴有出現(xiàn)文字、數(shù)字、表格等，且有著不同程度噪聲污染，若對條碼定位和分割不夠準(zhǔn)確，將直接影響到后續(xù)的識別和解碼工作。

針對上述問題，專家學(xué)者們進(jìn)行了大量研究探索，并提出了許多有效的算法。文獻(xiàn)[1]提出基于小波紋理分析的檢測方法；文獻(xiàn)[2]提出了一種基于數(shù)學(xué)形態(tài)學(xué)運(yùn)算和Canny 邊緣檢測的定位算法；文獻(xiàn)[3]提出一種基于支持向量機(jī)的條碼檢測方法；文獻(xiàn)[4]提出了一種利用角點(diǎn)特征來篩選一維條碼區(qū)域的方法，由于PDF417 條碼中指示符模塊分布不連貫，以及類似紋理的干擾，如：英文文字直接使用會導(dǎo)致提取不完整；文獻(xiàn)[5]提出一種子區(qū)域多特征的方法來篩選條碼區(qū)域，但對于和PDF417 條碼內(nèi)部區(qū)域有著相似的邊緣強(qiáng)度和線性尺度的文字區(qū)域區(qū)分度不高；文獻(xiàn)[6]提出一種基于邊緣方向特征的數(shù)據(jù)矩陣碼定位方法，但是無法區(qū)分背景紋理中的文字和表格區(qū)域。

本文在上述成果的基礎(chǔ)上，提出針對PDF417 二維條碼的檢測提取方法。首先分析條碼本身的結(jié)構(gòu)特點(diǎn)；其次采用子區(qū)域多特征分析法[5]來提取感興趣的區(qū)域；最后在這些區(qū)域存在的連通域中，將條碼定位并提取出來。

2 PDF417 碼的結(jié)構(gòu)特征分析

由圖1 可知PDF417 的條碼結(jié)構(gòu)特點(diǎn)：條碼由指示符和數(shù)據(jù)字符組成，指示符中起始符和終止符由寬度比例特定的黑白條空按特定方向排列而成[7]，各條空邊緣相互平行。除起始符和終止符外，條碼每列字符都以黑條開始白空結(jié)束，各列字符之間形成明顯的邊緣，這些邊緣與起始符、終止符的條空邊緣有著相同的長度和斜率。因此只要在包含條碼的候選區(qū)域中確定條碼起始符和終止符，并提取出邊緣像素梯度方向信息來標(biāo)注強(qiáng)邊緣，就能夠定位條碼在圖像中的準(zhǔn)確位置。

圖1 PDF417 條碼

3 子區(qū)域特征

對于條碼圖像背景往往十分復(fù)雜的情況，將采集到的圖像按網(wǎng)格狀分隔成大小相等的若干個(gè)子區(qū)域，有利于分析起始模塊、終止模塊區(qū)別于其他背景紋理的區(qū)域特征，并利用區(qū)域特征對候選子區(qū)域進(jìn)行篩選合并，達(dá)到定位目標(biāo)區(qū)域的目的。

3.1 梯度方向特征

由于條碼起始符與終止符由一組排列整齊的條空組成，該區(qū)域梯度方向直方圖上會有高能單峰值出現(xiàn)[8]，因此可用這個(gè)特性來區(qū)分背景中除直線外的其他紋理。

子區(qū)域中像素的梯度向量的模和方向分別定義為：

其中，GH和Gv分別由圖像與以下兩個(gè)掩膜卷積運(yùn)算得到：

構(gòu)造用于表達(dá)θ 值的直方圖H ，橫坐標(biāo)表示角度，縱坐標(biāo)表示該方向像素的數(shù)目。對該直方圖的θ 值域進(jìn)行量化，將梯度直方圖的范圍定為0°～360°，考慮到圖像存在畸變，為了不漏掉近似平行的列邊緣，量度為每10°一柱，總共36 柱。對區(qū)域內(nèi)梯度幅值大于設(shè)定閾值Gm（取圖像的梯度均方根值）的像素點(diǎn)統(tǒng)計(jì)方向直方圖，通過對比直方圖中各峰值的能量比Tp來判斷該區(qū)域的梯度是否具有單一的方向性。

3.2 角點(diǎn)特征

由于PDF417 條碼的起始符和終止符有著類似一維條碼且不同于其他字符的獨(dú)特結(jié)構(gòu)，可采用角點(diǎn)特征[4]來區(qū)分條碼中不同的字符區(qū)域。

Harris 角點(diǎn)檢測算法[9]是一種基于信號的點(diǎn)特征提取算子，這里認(rèn)為只要對于一個(gè)向任意方向發(fā)生微小移動就能引起灰度值大幅變化的點(diǎn)即為角點(diǎn)。算法如下：

（1）計(jì)算子區(qū)域內(nèi)像素點(diǎn)在水平和垂直方向上的梯度Ix、Iy，并得到矩陣M ：

（2）使用離散二維零均值高斯函數(shù)Gs在原圖像上進(jìn)行卷積濾波，得到新的矩陣M ：

（3）角點(diǎn)響應(yīng)函數(shù)定義為：

其中k 為經(jīng)驗(yàn)值，取值為0.04。

（4）選取鄰域內(nèi)R 大于某個(gè)閾值的局部極大值點(diǎn)，設(shè)為角點(diǎn)。

3.3 梯度特征

由于條碼起始符和終止符的灰度在梯度方向上呈規(guī)律性跳變，利用該特征可以很好地區(qū)分灰度跳變頻率低的直線和明暗邊界區(qū)域。

4 子區(qū)域特征分析

圖2 為條碼區(qū)域與其他常見紋理區(qū)域的梯度方向直方圖和角點(diǎn)分布圖。

圖2 特征分析圖

圖2 中第一列從上往下依次為：條碼起始符邊緣區(qū)域；起始符內(nèi)部區(qū)域；條碼數(shù)據(jù)字符邊緣區(qū)域；條碼數(shù)據(jù)字符內(nèi)部區(qū)域一。第二列從上往下依次為：條碼數(shù)據(jù)字符內(nèi)部區(qū)域二；直線區(qū)域；漢字區(qū)域；表格區(qū)域。第三列從上往下依次為：英文區(qū)域；數(shù)字區(qū)域；公式區(qū)域；圖案區(qū)域。

結(jié)合圖2 與梯度特征分析，對比其他紋理區(qū)域，包含有指示符或終止符的子區(qū)域符合以下準(zhǔn)則：

（1）直方圖呈單一尖峰狀分布。

（2）區(qū)域內(nèi)角點(diǎn)數(shù)為零；若不為零須呈線性分布且直線方向與梯度主方向大體一致。

（3）梯度主方向軸上灰度跳變較為頻繁。

5 條碼定位提取算法

上述準(zhǔn)則為基礎(chǔ)制定條碼定位算法，圖3為算法流程圖。

圖3 算法流程圖

5.1 條碼候選區(qū)域的生成

PDF417 條碼由黑白條空模塊堆疊而成，其區(qū)域內(nèi)有著明顯的黑白對比反差，在這里將所采集到的圖像分為若干個(gè)大小相等的子區(qū)域，計(jì)算子區(qū)域的對比度[5]。對于對比度大于一定閾值tc（閾值的大小取決于子區(qū)域的大小、圖像分辨率等因素）的區(qū)域保留為候選子區(qū)域，將這些子區(qū)域按照8 鄰接原則合并生成一組候選連通域，其中某個(gè)區(qū)域被認(rèn)為包含有PDF417 條碼，按序抽取候選區(qū)域執(zhí)行后續(xù)子區(qū)域篩選。

5.2 子區(qū)域篩選

（1）梯度方向特征區(qū)分。計(jì)算各子區(qū)域的梯度方向直方圖，設(shè)置直方圖中主、輔峰的能量比閾值tp，對能量比Tp≥tp的子區(qū)域予以保留，以此濾除梯度方向不具單一性的背景區(qū)域（如漢字區(qū)域、表格區(qū)域、英文區(qū)域、數(shù)字區(qū)域、公式區(qū)域、圖案區(qū)域等以及一些條碼內(nèi)部區(qū)域），保留有單一直線區(qū)域和條碼部分組成區(qū)域（其中圖2 第一列第三個(gè)示例為一種特殊情況，一些條碼數(shù)據(jù)字符邊緣處的直方圖分布符合該步驟篩選要求）。最后，將各保留區(qū)域子塊的主峰值θp保留進(jìn)峰值矩陣Mθ。

（2）角點(diǎn)特征區(qū)分。針對上步保留的子區(qū)域，計(jì)算和統(tǒng)計(jì)其內(nèi)的角點(diǎn)數(shù)以及對呈線性分布的角點(diǎn)區(qū)域使用霍夫變換，查看角點(diǎn)數(shù)是否為零或直線方向角是否與梯度方向一致，對滿足條件的子區(qū)域予以保留?？膳懦喜襟E遺留下的條碼內(nèi)部區(qū)域和條碼數(shù)據(jù)字符邊緣區(qū)域（圖2 第一列第三個(gè)示例因角點(diǎn)直線方向與梯度主方向相差較大，在這一步得到排除）。

（3）梯度特征區(qū)分。在梯度方向上進(jìn)行灰度梯度跳變掃描。按照峰值方向矩陣Mθ中各子區(qū)域的梯度主方向值，將具體掃描角度量化為0～7 共8 個(gè)方向（如圖4 所示）。方向角在內(nèi)為0方向；在內(nèi)為1方向；內(nèi)為2 方向；依次類推。

掃描具體過程為：選取子區(qū)域中心像素點(diǎn)，以及4 條邊界的中點(diǎn)，按上述掃描方向和相反方向在區(qū)域內(nèi)掃描該直線上的像素。設(shè)上述所形成的3 條掃描線中的第i 條(1 ≤i ≤3)掃描線上，第j 個(gè)像素的灰度值為，其量化值定義為：

其中，tostu為對子區(qū)域求得的大津閾值。統(tǒng)計(jì)第i 條掃描線上像素量化值的跳變次數(shù)，記為Ji，若存在Ji多于4 次（排除單一直線子區(qū)域和明暗邊界區(qū)域的最小取值）的情況，認(rèn)為該子區(qū)域符合目標(biāo)區(qū)域的梯度特征，予以保留。

圖4 量化方向圖

5.3 標(biāo)注列分隔線和定位條碼

經(jīng)過上述3 個(gè)特征的篩選而保留下的子區(qū)域則被認(rèn)為包含有目標(biāo)模塊。統(tǒng)計(jì)區(qū)域子塊的梯度主方向角，出現(xiàn)次數(shù)最多的方向角即為條碼的列邊緣的梯度方向，記為θ′p。標(biāo)記該子區(qū)域所存在的連通域，認(rèn)為該區(qū)域包含有完整的PDF417 條碼。若篩選過程中沒有找到全部符合上述3 個(gè)特征的子區(qū)域，則選擇下一個(gè)連通域重復(fù)子區(qū)域篩選。

標(biāo)注所標(biāo)記連通域內(nèi)所有具有梯度方向?yàn)棣取鋚的邊緣像素，標(biāo)注準(zhǔn)則為：

其中，θ 為邊緣像素的梯度方向角。這些標(biāo)注的像素組成一系列連通分量，刪除長度較短的噪聲，即可得到列與列之間的分隔邊界。

細(xì)化保留的連通分量，取細(xì)化連通分量的端點(diǎn)進(jìn)行霍夫變換，得到條碼圖像的上下邊界方程，通過邊界方程連接各點(diǎn)即得條碼上下邊緣，結(jié)合上步所標(biāo)記的連通域和各字符列邊緣，最終完成對條碼的定位。

6 定位算法仿真

圖5 以一個(gè)郵政快遞封面的例子，分步驟顯示了條碼的檢測定位過程。其中區(qū)域子塊大小為30×30，Tc為90，Tp為3.0。

圖5 條碼的檢測提取過程圖

圖6為條碼檢測結(jié)果對比。其中圖6（a）為單一使用梯度方向特征檢測的結(jié)果，雖然利用梯度方向特征可以排除大部分背景紋理區(qū)域，但是無法排除某些條碼數(shù)據(jù)字符區(qū)域以及直線、明暗邊界區(qū)域；圖6（b）為單一使用角點(diǎn)特征檢測的結(jié)果，利用角點(diǎn)特征能有效地濾除條碼內(nèi)部數(shù)據(jù)區(qū)域和文字區(qū)域，但對于紋理特征相似的某些英文文字、數(shù)字以及前述線型區(qū)域無法徹底排除，且PDF417 條碼的起始符和終止符分布不連貫，單一使用將導(dǎo)致提取出的條碼區(qū)域不完整；圖6（c）為文獻(xiàn)[5]方法的檢測結(jié)果，由于PDF417 條碼內(nèi)部區(qū)域的邊緣強(qiáng)度和線性尺度類似于文字區(qū)域，該方法對以上兩種紋理區(qū)分度不高；圖6（d）為本文算法的檢測結(jié)果，通過多特征相結(jié)合的算法可以有效濾除大部分背景區(qū)域，并能夠較為準(zhǔn)確地定位條碼區(qū)域。

圖6 條碼檢測結(jié)果對比圖

7 實(shí)驗(yàn)結(jié)果分析和結(jié)論

本文使用上述方法，用MATLAB.R2007a 環(huán)境編程，對50 幅條碼圖片（其中包括郵政信封、快遞封面、機(jī)票以及自定義背景圖片）進(jìn)行實(shí)驗(yàn)。除去一幅褶皺變形嚴(yán)重以及一幅印刷問題導(dǎo)致條碼部位無法識別外，其他均能夠成功定位。圖7 顯示了幾種不同背景下，以及帶有傾斜、污漬等干擾情況下的檢測結(jié)果。

圖7 實(shí)驗(yàn)結(jié)果

該檢測方法通過對比分析區(qū)域子塊的梯度方向特征來剔除復(fù)雜背景區(qū)域的干擾，采用角點(diǎn)特征進(jìn)一步去除可能影響到列邊緣梯度方向取值的條碼部分組成區(qū)域，后續(xù)結(jié)合梯度特征篩選出目標(biāo)模塊，確定包含條碼的連通域并提取邊緣梯度方向信息，標(biāo)注條碼列邊緣，在背景中實(shí)現(xiàn)條碼圖像的準(zhǔn)確定位。實(shí)驗(yàn)結(jié)果表明，對于復(fù)雜背景，條碼位置、傾斜度未知以及污漬干擾的情況，該檢測方法具有良好的效果，后續(xù)完成幾何失真矯正，能夠?yàn)橐院蟮淖R別解碼工作打下良好的基礎(chǔ)。

[1] 呂佩卓，賴曉錚，賴聲禮.基于小波多分辨率分析的PDF417 定位算法[J].自動化學(xué)報(bào)，2008，34（5）：597-600.

[2] 劉發(fā)耀，殷建平，李寬，等.復(fù)雜背景下PDF417條碼定位研究[J].計(jì)算機(jī)工程與科學(xué)，2010，32（6）：55-57.

[3] Leong L K，Wang Y.Extraction of 2D barcode using keypoint selection and line detection[C]//Proceedings of the 10th Pacific Rim Conference on Multimedia，Bangkok，Thailand，2009.

[4] 王霞玲，呂岳，文穎.復(fù)雜背景和非均勻光照環(huán)境下的條碼自動定位和識別[J].智能系統(tǒng)學(xué)報(bào)，2010（1）：35-40.

[5] 劉寧鐘.復(fù)雜背景中條碼檢測定位技術(shù)的研究[J].南京航空航天大學(xué)學(xué)報(bào)，2005，37（1）：1-4.

[6] 高阿曼，何衛(wèi)平，雷蕾，等.數(shù)據(jù)矩陣碼檢測定位技術(shù)研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009（19）：4532-4535.

[7] 中國物品編碼中心.GB/T17172—1997 四一七條碼[S].北京：中國標(biāo)準(zhǔn)出版社，1997.

[8] Ottaviani E，Pavan A，Bottazzi M，et al.A common image processing framework for 2D barcode reading[C]//Proceedings of the 17th International Conference on Image Processing and Its Applications，1999：652-655.

[9] Bellavia F，Tegolo D，Valenti C，et al.Improving Harris corner selection strategy[J].Computer Vision，2011，5（2）：87-96.