高速智能相机一维条码的自适应快速定位

宋昀岑 ， 赵 津 ，2， 陈 伟 ，2， 叶玉堂

（1.电子科技大学 现代光电测控及仪器实验室（摩米实验室），四川 成都 610054；2.成都术有科技有限公司 四川 成都 610054）

随着现代科技的高速发展，一些高新工业生产领域因为读取效率较慢、读取区域小、人力消耗大等问题，无法采用激光条码扫描仪，必须采用基于图像的高速智能相机条码解读方案。而该方案的关键就是如何解决快速和全方位定位的问题。

高速智能相机作为一种功能强大性价比高的新兴视觉设备，在高新工业生产中应用范围日益广泛。高速智能相机内置DSP（Digital Signal Processer）完成数据处理操作，其灵巧的体积更便于安装和与其他设备结合工作，且硬件成本大幅降低。又因为条码技术在工业生产线的广泛应用，高新生产领域对高速智能相机条码解读方案的需求日益强烈。然而，实际应用中条码图像往往和复杂背景结合一起，很多时候还会出现条码倾斜、破损的情况，由此造成的条码定位失败不但影响智能相机条码读取效率，还会导致读码失败给生产线造成不可预知的后果。 因此，需要提出一种能自适应条码定位，还能保证在智能相机能高效运转的新方法。而所谓的“自适应”即是能自动适应复杂背景、倾角变化、条码缺损测试条件的变化。

对于常见的在PC（personal computer）端完成的条码定位算法，国内外很多学者都从事过这方面的研究。Gallo O[1]提出基于条码区域轮廓的定位算法，这类方法效率比较高但是无法应对条码缺损的情况；另外，很多文献[2-7]提出了基于空域中条码图片的纹理分析，分别根据子区域的对比度、方向边缘强度、线性尺度、梯度特征和角点特征等多种特征定位条码区域，这类方法对图片的适应力较强，但在智能相机上不能实现数据的连续读取，降低了图片的读取和处理效率，不适用于内存和缓存容量都非常小的智能相机。

文中提出一种应用于高速智能相机一维条码的自适应[8]快速定位算法。通过基于DSP的快速区域分析算法得到图片中各个联通区域及其区域特征，由条码模块筛选、排除复杂背景得到条码的大致区域，最后进行条码区域扫描定位，修补条码破损区域找到精确的条码区域边界点。本文算法应用于高速智能相机的一维条码解读模块中，解决了复杂背景中倾斜条码、破损条码的快速定位问题。另外，算法中将基于DSP的快速区域分析算法应用于高速智能相机，在国内还未见报道。

1 条码定位算法

1.1 基于DSP的快速区域分析算法

由于DSP本身效率限制，为压缩处理时间，本文使用基于DSP的快速区域分析算法进行图像联通区域分析。

传统处理方式要先将图像转为二值化图像，游程算法通过判断二值化图像灰度值是否为零进行区域分析。本文算法，通过直接判断图像灰度值与已知二值化阈值的关系进行区域分析，省去一次对全图的读取，至少能节省30%的连通区域分析处理时间。另外，不同于其他的条码定位算法，本文算法连续读取图像信息，为后续的优化处理提供便利。

传统游程算法处理结果是得到每个连通区域的点，对连通区域分析是通过对每个区域中的点进行统计计算处理，乘除运算以及浮点值运算多、运算量大。而DSP进行乘除运算和浮点值运算消耗时间较长，不适用上述方法。本文算法直接利用游程算法中的游程进行统计计算，而不用点的信息计算，从而免去许多不必要的步骤，利用公式减少乘除运算和浮点值运算，具体算法改进如下所述。

利用游程算法顺序读取全图得到所有游程数量num；游程行号数组 r，r[i]（i=1，2…）即是第 i个游程的列号；游程起始列号数组 cs，cs[i]（i=1，2…）即是第 i个游程首行号；游程终止列号数组 ce，ce[i]（i=1，2…）即是第 i个游程尾行号；游程区域标记数组 l，l[i]（i=1，2…）即是第 i个游程所属的联通区域编号；假定目标游程为黑色，背景为白色，上述部分数据如图1所示。由上述参数不用再次扫描整张图片就可以得到后面算法需要的每个连通区域的形态学特征：面积、重心、长轴长、短轴长、长轴与图像X轴的夹角。

图1 游程及其数据表示Fig.1 Run-length code and its data representation

面积为联通区域中点的个数，可以通过面积特征进行初步筛选，筛去大部分不相关区域，比如复杂背景中数量巨大的小噪点以及与条码单元面积大小不一致的区域。重心是联通区域中所有点的平均坐标位置，是后面计算的中间数据。面积和重心由公式（1）～（3）计算得到，其中 s[i]为第 i个连通区域的面积，gx[i]和gy[i]代表第i个连通区域的重心位置（i=1，2，3…）。

长轴长和短轴长是与联通区域标准二阶中心距相同的椭圆的长轴长和短轴长。对于联通区域是否符合条码单元的长条形即是以长短轴长度比例为判断标准。计算公式如下，其中maxl[i]为第i个连通区域的长轴长，minl[i]代表第i个连通区域的短轴长（i=1、2、3…），xx[i]、xy[i]、yy[i]分别是 i点行号的平方、i点行号和列号的乘积、i点列号的平方，点由图2所示流程图和公式（4）～（6）得到：

图2 数据计算流程图Fig.2 Data and calculation flowchart

α为长轴与图像X轴的夹角，即是长轴方向和图片X轴的夹角，等同于条码区域竖边与图像X轴的夹角，由公式（9）得到。一维条码的单元是平行整齐排列，故可以根据夹角对初步筛选的联通区域进行分组为下一步定位做准备。

1.2 条码模块筛选

为排除图像中的复杂背景区域，减少DSP处理信息量，我们对得到的连通区域进行筛选。由于一维条码区域形态学特征明显，是由数十条黑色长条矩形组成，且矩形的长度相等、长边相互平行。文中为区域长宽比（长轴长和短轴长的比例）、区域面积 2个特征值引入 3 个阈值 Tr、Tmins、Tmaxs， 阈值的大小决定于一维条码类型、图像分辨率等因素。如果某个联通区域Ai是条码的一个单元，那么这区域的长轴短轴长度、面积应满足条件：

经过上述筛选，可以得到符合条码单元形态特征的联通区域

。

然后，将其按照长轴与图像X轴的夹角α[i]分组，即α相同的分为一组，找出其中连通区域最多的组，作为条码元素的联通区域组，排除复杂背景区域得到条码大致区域以进行下一步精确定位操作。

1.3 条码区域扫描定位

一维条码是由一组规则排列的条、空单元及其对应字符组成，用以表示一定的信息。相对背景区域，条码区域具有明显的形态学特征，由长度相同的细长条、空单元相间整齐排列，在左右边缘都有一个静区，即规定宽度的空白区域。

根据以上特点，从条码单元组中选出长轴长最大的单元，认为是最完整的条码单元；选出最小的单元短轴长，假设为一个模块的宽度。然后进行扫描定位，具体算法如下所述。

1）在最长单元的长轴方向以重心为中心均匀取n（本文中n为5）个扫描点。其中第一点和最后一点是该单元长轴方向上的两端点。

2）从每个扫描点出发向垂直于单元长轴的左右两个方向进行扫描，如图3白色箭头所示。

扫描遇到阈值分割处的点记录下来为A，该阈值分割点是条码的条、空单元边缘点。在遇到下一个阈值分割点B时，判断AB距离，若是大于最小宽度的N倍，便停止继续扫描并将A记录下来为边界点之一；若是小于最小宽度的N倍，将B点记做A点，继续扫描，直到找到满足条件的边界点。如果到达图像边界还没找到满足条件的点，将扫描方向上的图像边界点上一个阈值分割点记录为条码边界点。其中N的大小是表征条码静区与条码最小单元宽度的比值，取决于条码的类型。

3）在找到两个方向共10个扫描边界点以后，利用投影法分别求出两个方向的最远点，记为条码区域左右两边的边界点；取最长条码模块长轴两端的点，记为条码区域上下两边的边界点。

图3 扫描方向示意图Fig.3 diagram of scanning direction

4）根据4个边界点以及条码模块与X轴的夹角，可得到条码区域4条边界线，分别求交点即可得到条码区域定位点。

2 结果与分析

2.1 不同图片的定位效果

本文选取了100幅具有各种复杂背景、条码破损情况的一维条码图像进行测试，DSP处理平台为ADIBF 537嵌入式平台，图像分辨率从512×512到1 024×786不等，均能正确检测出条码的位置，没有出现漏检和误检的现象。

图4为其中一幅条码区域破损图像的定位过程与结果。 原图为交叉 25码，分辨率为 1024×786，取 Tr为 6，N为6，Tmins为 50，Tmaxs为 300。 （a）为原始灰度图；（b）中灰色标记区域为筛选得到的条码单元（联通区域）；（c）中位于中间的黑色点为最长单元上的5个扫描点，边界上的黑色点即是扫描得到的十个边界点；（d）中4个黑点为经过筛选后得到的条码区域4条边上的最优边界点；（e）为条码区域最终定位结果图。

图4 缺陷条码定位Fig.4 Localization of defective barcode

图5为其中一幅复杂背景下的条码图像定位结果。原图中除了倾斜条码，还有表格和大量文字。由图5（b）黑色线条框出的定位结果可以看出，本文算法可以很好的定位出复杂背景下的条码区域。

图5 复杂背景下条码定位Fig.5 Barcode localization in complex background

2.2 不同图片的处理速度

文中对于不同分辨率的3幅图像分别采用传统游程法和改进游程法进行定位处理所需时间进行了对比，其对比结果如表1所示，改进游程法相对于传统游程法的处理速度上提高了61%～68%不等。

文中对于3种分辨率的多幅图像采用基于DSP的改进游程法完成条码定位，对每种分辨率的多幅图像定位时间取平均值如表2所示，对于80万像素的图片，可以达到平均66.79ms/幅的处理速度。目前还没有DSP平台上的一维条码定位算法处理速度高于本文处理速度的报道。

表1 传统游程区域分析法与基于DSP的快速区域分析算法处理时间对比Tab.1 Comparison of execution time between traditional runlength code region analysism ethod and DSP-based quick region analysism ethod

表2 基于DSP的改进游程法的条码定位处理时间Tab.2 Execution time of DSP-based imp roved run-length codem ethod

3 结 论

文中根据DSP运算的特点，利用一维条码的形态学特征，提出一种基于DSP的快速区域分析算法，能够快速而有效定位出复杂背景中倾斜和残缺的条码区域。有别于传统算法，本文算法全过程不使用二值化图像，减少至少一次DSP对全图的计算与存储，唯一一次DSP进行的全图操作为顺序读取，有利于DSP后期优化处理，大大提升了处理速度。在对大量图片进行测试的结果表明，该方法可以全部正确地提取出复杂背景和倾斜、缺损情况下的条码区域，对于80万像素的图片可以达到平均66ms/幅的处理速度。康耐视公司产品对于48万像素的图片在同等情况下的处理速度最快为45ms/幅。该方法对于工业生产线上在线嵌入式平台条码检测具有广泛的实际应用价值。

[1]GALLO O，MANDUCHI R.Reading 1d barcodes with mobile phones using deformable templates [J].Pattern Analysis and Machine Intelligence， IEEE Transactions on，2011， 33（9）:1834-1843.

[2]WU Xinsheng， QIAO Lianzhi， DENG Jun.A New Method for Bar Code Localization and Recognition[C]//Image and Signal Processing， 2009. CISP'09. 2nd International Congress on.IEEE，2009:1-6.

[3]刘宁钟.复杂背景中条码检测定位技术的研究[J].南京航空航天大学学报，2005， 37（1）:65-69.LIU Ning-zhong.Detection and localization of bar code in complicated background[J].Journal of Nanjing University of Aeronautics&Astronautics，2005，37（1）:65-69.

[4]GALLO O，MANDUCHI R.Reading challenging barcodes with cameras[C]//Applications of Computer Vision （WACV），2009Workshop on.IEEE，2009:1-6.

[5] Chen Yang， Yang Zhaoxuan， Bai Zhuofu， et al.Simultaneous real-time segmentation of diversified barcode symbols in complex background[C]//Intelligent Networks and Intelligent Systems，2008.ICINIS'08.First International Conference on.IEEE，2008:527-530.

[6]KUTIYANAWALA A，QIXiaojun，Tian Jiandong.A simple and efficient approach to barcode localization [C]//Information， Communications and Signal Processing， 2009.ICICS 2009.7th International Conference on.IEEE，2009:1-5.

[7]WACHENFELD S， TERLUNEN S， JIANG Xiaoyi.Robust 1-D barcode recognition on camera phones and mobile product information display[M].Mobile Multimedia Processing.Springer Berlin Heidelberg，2010:53-69.

[8]赵志伟，陈学有，潘琼.采用特征值法和Prony法相结合的PSS自适应控制[J].陕西电力，2012（6）：49-52，62.ZHAO Zhi-wei，CHEN Xue-you，PANQiong.Adaptive control of PSS based on eigen value analysis and prony analysis[J].Shaanxi Electric Power，2012（6）：49-52，62.