1. 中国科学技术大学微电子学院, 合肥 230027;
2. 中国科学技术大学信息科学技术学院, 合肥 230027
2018年3月21日 收稿; 2018年5月22日 收修改稿
基金项目: 国家自然科学基金（61472380）资助
通信作者: 黄鲁, E-mail:luhuang@ustc.edu.cn
摘要: 基于数字图像处理技术实现一维条形码的快速定位。对输入的灰度图进行边缘检测和二值化等图像处理，通过数学形态学处理得到条形码候选区域，并利用梯度特征提取候选区域的边缘线；最后利用条形码条空的平行性对边缘线区域进行筛选，定位条形码区域。本文算法在WWU Muenster和ArTe-Lab条码图片数据集上进行测试，实验表明，本算法比现有的算法更快，因此，更适合部署在实时应用上。
关键词: 图像处理梯度特征边缘线提取条形码定位
1D barcode fast localization technology based on image processing
JI Qinqin1, HUANG Lu2
1. College of Microelectronics, University of Science and Technology of China, Hefei 230027, China;
2. School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China
Abstract: In this paper we demonstrate the implementation of the fast localization of 1D-barcode based on digital image processing techniques. First, we conduct the edge detection and binary quantization on the input image. Then, we use digital morphological processing to obtain the candidate region of the barcode and adopt the gradient feature to extract the edge line of the region. Finally, we select the area of the barcode by utilizing the fact that the blank areas are parallel to each other. The algorithm is tested on two barcode data sets:WWU Muenster and ArTe-Lab. The results show that our algorithm is faster than the existing algorithms and therefore is more suitable for real-time applications.
Keywords: image processinggradient featureedge line extractionbarcode localization
条形码技术具有简单方便、高效准确、经济实用等优点，它在人们的日常生产生活中获得广泛的应用。条形码作为一种通用的商品包装标签，通常印刷在商品或印刷品上。目前，识别一维条形码主要依靠激光扫描仪，激光扫描仪不仅需要人工对准条形码区域才能保证解码率，且对条形码质量要求很高。而使用图像处理的方式可以识别具有一定质量缺陷的条形码，提高条码应用的效率。目前市场上已经出现基于图像处理的条码识别设备，但价格昂贵，因此，研究并开发更加经济高效的类似产品具有很大的商业价值。
图像处理的方法主要有两个步骤，即条形码定位和条码识别，本文只讨论条形码定位的实现技术。
国内外研究人员在条形码定位领域一直没有停止研究的脚步：文献[1]将图像划分成32×32的小块，分析每一块图像的所有骨架的平行性确定其为条形码子区域，再将所有子区域组合成条形码区域，实验表明所提取的条码区域受条纹背景干扰。Gallo和Manduchi[2]提出一种快速检测条形码区域的方法，该方法计算每一个像素的直方图梯度，并使用滤波器和全局二值化分割条形码区域，但该方法不适用于倾斜条形码的定位。文献[3-4]提出基于形态学的方法，获取的条形码区域会因为噪声区域的影响而改变。文献[5-6]使用Hough变换寻找条形码区域，当条码背景有明显的平行线时，该方法并不适用。
本文实现的条形码区域定位方法适用于倾斜、扭曲、具有明显平行线等复杂背景的条形码图像。
1 条形码特性本文以具有代表性的EAN-13条形码作为研究对象，如图 1。EAN-13条形码由59个“条”和“空”组成，每个条或空是1、2、3或4倍单位元素宽度。条空黑白相间、宽窄不等、分布间隔有限且互相平行，具有明显的单方向纹理特征。
Fig. 1
 | Download: JPG larger image |
| 图 1 EAN-13条码 Fig. 1 EAN-13 barcode 图 1 EAN-13条码 Fig. 1 EAN-13 barcode --> | |
2 条形码定位本文算法主要由2个部分组成：图像分割[7]、区域边缘线提取。对输入图像先用Sobel算子边缘检测，突出条形码区域并减弱背景区域的影响，二值化后的图像经过数学形态学处理进一步消除背景区域，分割图像得到多个条形码候选区域；最后通过提取候选区域的边缘线进行平行性分析定位条形码区域，其原理框图如图 2所示。
Fig. 2
 | Download: JPG larger image |
| 图 2 原理框图 Fig. 2 Block diagram 图 2 原理框图 Fig. 2 Block diagram --> | |
2.1 边缘检测与大津法二值化图 3展示每个步骤的具体中间结果(图片经过裁剪且保留主要部分)。
Fig. 3
 | Download: JPG larger image |
| 图 3 条形码区域定位具体步骤图 Fig. 3 Intermediate results for each step 图 3 条形码区域定位具体步骤图 Fig. 3 Intermediate results for each step --> | |
假设图 3中的灰度图(640×480)用f(x, y)表示，因为条形码信息主要分布在水平方向上，所以可用f(x, y)的水平梯度图与垂直梯度图的差值图作为Sobel边缘检测图，以减弱背景区域的干扰。式(1)中的D(x, y)即为所求的边缘图。
| $\begin{align} & D\left( x, y \right)=\left| \left( \begin{array}{*{35}{l}} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1 \\\end{array} \right)f\left( x, y \right) \right|- \\ & \ \ \ \ \ \ \ \ \left| \left( \begin{array}{*{35}{l}} -1 & -2 & -1 \\ 0 & 0 & 0 \\ +1 & +2 & +1 \\\end{array} \right)f\left( x, y \right) \right|. \\ \end{align}$ | (1) |
| $f\left( x, y \right)=\left\{ \begin{align} & 0, f\left( x, y \right)\ge T \\ & 1, f\left( x, y \right)<T. \\ \end{align} \right.$ | (2) |
商品条形码具有标准尺寸，条码区域的长为37.29mm，宽为26.26mm，允许的放大倍数是0.8~2.0，是具有一定长宽比且条空排列间隔有限的矩形，长宽比约在1.4左右。因此，本文所选取的结构元素形状为矩形，通过对大量不同背景的条码图像进行分割，结果表明当结构元素长宽比选取为1.5且腐蚀与膨胀次数比为2:3可以将条形码分割到一个区域中。同时，我们也在WWW Muenster①和ArTe-Lab②这两个标准的一维条码数据集上进行测试，条码在一个区域中的正确率分别为94.8%和99.8%。
① http://cvpr.uni-muenster.de/research/barcode/Database.
② http://artelab.dista.uninsubria.it/download.
2.3 边缘线提取边缘线是条形码区域黑白的分界线且为单像素宽度，在分界处的像素值变化范围在该像素领域最大，因此，若一个像素在该像素领域内梯度最大或最小，则认为其为分界点，所有的分界点构成边缘线。具体步骤如下：
1) 假设条形码候选区域为h(x, y)，定义一个与h(x, y)同尺寸类型的图像H(x, y)，将其像素值全置为0。从左到右扫描h(x, y)，记当前像素点的像素梯度Δp，梯度幅值Ip。
2) 考虑以像素p为中心的一个长度为r的单像素线段，这条线上有r个像素点。
3) 如果同时满足以下两个条件则将H(x, y)中(px, py)处的像素值置1。
a) Ip大于阈值T1(用大津法计算的h(x, y)的阈值)。
b) r－1个像素点的梯度均大于或者小于Δp。
4) 重复步骤1)、2)、3)直至h(x, y)中的像素被扫描完。
5) 扫描H(x, y)，计算每根边缘线长度L，用long表示最长边缘线的长度。条形码区域中的数字区域是一些较短且无规律的边缘线，需要尽可能地保留条码条空区域的边缘线，以便于利用条空平行性筛选目标区域。因此，保留
2.4 定位目标区域目标区域的边缘线具有一定的长度且相互平行，背景区域的边缘线长度较短且无规律。用椭圆拟合的方法获得条码候选区域的边缘线倾斜角(与水平x的夹角)，如表 1所示。
Table 1
 表 1 区域边缘线角度值Table 1 Angles of area edge lines
| 表 1 区域边缘线角度值Table 1 Angles of area edge lines |
基于以下两点：
1) 理论上条形码区域的边缘线数是60根，但模糊受损的条码区域边缘线数跟理论值会有差距，差距的大小受模糊受损程度影响。
2) 扭曲形变的条形码的边缘线并不全是平行的。因此，目标区域必须同时满足以下两个条件：
a) 边缘线数大于5；
b) 与相邻边缘线的倾斜角相差在2°内的边缘线总数超过总边缘数的3/4。
否则，认为此区域不是目标区域，如果所有的条形码候选区域都不满足上述两个条件，则这张图片不包含条形码区域。
3 实验及结果分析我们使用2个公开的一维条形码图片数据集进行算法性能测试：由文献[9]提供的WWU Muenster条码数据集和文献[10]提供的ArTe-Lab条码数据集。ArTe-Lab条码数据集包括365张640×480的EAN图片。WWU Muenster条码数据集包含由N95手机拍摄的1055张EAN和UPC-A条形码图片，Zamberletti等[10]和Creusot与Munawar[11]仅使用其中的595张图片，数据集的具体细节如表 2所示。
Table 2
表 2 数据集细节Table 2 Datasets details
| 表 2 数据集细节Table 2 Datasets details |
我们的算法与文献[10-11]提出的方法进行比较，结果如表 3所示。在ArTe-Lab条码数据集中定位条码区域的正确率为90.1%，在Muenster条码数据集中的正确率为97.8%，对比于文献[10]的方法分别提高10%和15%左右且略高于文献[11]的方法。
Table 3
表 3 不同条形码区域定位算法的比较结果Table 3 Comparison of the results among different barcode localization algorithms
| 表 3 不同条形码区域定位算法的比较结果Table 3 Comparison of the results among different barcode localization algorithms | ||||||||||||||||
图 4为我们的方法与文献[10-11]的方法对Arte-Lab中同一张图片的条形码区域定位效果。
Fig. 4
 | Download: JPG larger image |
| 图 4 对Arte-Lab中一张条码图片的定位结果 Fig. 4 Localization result for a picture in Arte-Lab 图 4 对Arte-Lab中一张条码图片的定位结果 Fig. 4 Localization result for a picture in Arte-Lab --> | |
图 5展示对模糊、条纹背景等复杂情况的条码图片的实验结果，图片均是在自然光照下摄像头采集的640×480像素且经过裁剪保留主要区域的灰度图。
Fig. 5
 | Download: JPG larger image |
| 图 5 复杂图像背景下的条码定位 Fig. 5 Barcode localization in complex image background 图 5 复杂图像背景下的条码定位 Fig. 5 Barcode localization in complex image background --> | |
我们以60帧/s左右的速度运行640×480图像。在表 4中，文献[10]和文献[11]是运用OpenCV库C++实现的运行在Intel i7 CPU的单线程上@3.33GHz，本文给出的结果同样是运用OpenCV库C++实现，运行在Intel i5 CPU的单线程上@3.40GHz。相比于文献[10-11]的方法，我们的算法具有更高的实时性。
Table 4
表 4 平均运行时间Table 4 Average computing time
| 表 4 平均运行时间Table 4 Average computing time | ||||||||||||||||
4 结语本文所提出的条形码定位算法简单高效，适用于倾斜、形变、模糊等不同情况的条码图像。通过与现有算法进行比较，结果表明我们的算法具有非常高的实时性，在主频1.2GHz的树莓派ARM7嵌入式系统上定位时间为0.29 s。
参考文献
| [1] | Chai D, Hock F. Locating and decoding ean-13 barcodes from images captured by digital cameras[C]//Information, Communications and Signal Processing, 2005 Fifth International Conference on. Thailand Bangkok: IEEE, 2005: 1595-1599. |
| [2] | Gallo O, Manduchi R. Reading 1d barcodes with mobile phones using deformable templates[J]. IEEE transactions on pattern analysis and machine intelligence, 2011, 33(9): 1834-1843. Doi:10.1109/TPAMI.2010.229 |
| [3] | Katona M, Nyul L G. A novel method for accurate and efficient barcode detection with morphological operations[C]//Signal Image Technology and Internet Based Systems (SITIS), 2012 Eighth International Conference on. Italy Naples: IEEE, 2012: 307-314. |
| [4] | Lin D T, Lin M C, Huang K Y. Real-time automatic recognition of omnidirectional multiple barcodes and DSP implementation[J]. Machine Vision and Applications, 2011, 22(2): 409-419. Doi:10.1007/s00138-010-0299-3 |
| [5] | Bodnar P, Nyul L G. Improving barcode detection with combination of simple detectors[C]// Signal Image Technology and Internet Based Systems (SITIS), 2012 Eighth International Conference on. Italy Naples: IEEE, 2012: 300-306. |
| [6] | Zamberletti A, Gallo I, Albertini S, et al. Neural 1d barcode detection using the Hough transform[J]. Information and Media Technologies, 2015, 10(1): 157-165. |
| [7] | Tang M, Ma S D. Enhancement and segmentation of images in computer vision[J]. Journal of the Graduate School of the Chinese Academy of Sciences, 2004, 21(1): 140-143. |
| [8] | Otus N. A threshold selection method from gray-level histograms[J]. IEEE Transactions on systems, man and cybernetics, 1979, 9(1): 62-66. Doi:10.1109/TSMC.1979.4310076 |
| [9] | Wachenfeld S, Terlunen S, Jiang X. Robust recognition of 1-d barcodes using camera phones[C]//Pattern Recognition, 2008 19th ICPR International Conference on. USA Tampa: IEEE, 2008: 1-4. |
| [10] | Zamberletti A, Gallo I, Albertini S. Robust angle invariant 1d barcode detection[C]//Pattern Recognition (ACPR), 2013 2nd IAPR Asian Conference on. Japan Naha: IEEE, 2013: 160-164. |
| [11] | Creusot C, Munawar A. Real-time barcode detection in the wild[C]//Applications of Computer Vision (WACV), 2015 IEEE Winter Conference on. USA Waikoloa: IEEE, 2015: 239-245. |
