DPM码快速定位关键技术研究

刘　志，洪梅芳

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)



DPM码快速定位关键技术研究

刘志，洪梅芳

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

摘要：直接零件标识(DPM)技术是实现产品标识的重要手段，以DM二维条码进行标识.由于DPM码是用激光标记在金属表面的点阵，在识别过程中会受到工况、光照等限制，存在高光、模糊甚至畸变等情况，导致条码定位困难.采用同态滤波和机器学习相结合的方法来增强图像实现条码区域快速初步定位.针对点阵二维条码的特殊性，提出一种基于投影的方向性L型拟合法，实现DataMatrix条码的L型定位符的精准拟合；利用基于改进扫描线算法的凸包算法实现条码的快速、准确定位.实验表明：与原有的关键技术相比，改进后的关键技术可以得到更好的效果，使得条码识别效果得到提高.

关键词：DPM条码；机器学习；L型拟合法；凸包算法

直接零件标识(Direct part marking,DPM)技术是实现产品标识的重要手段，并且以编码容量大、密度高和纠错能力强的DataMatrix二维条码进行标识.研究的DPM条码是用激光标记在金属表面的点阵Data Matrix二维条码,由于环境光照、金属纹理等原因，采集到的DPM条码图像普遍存在对比度低、多噪声干扰、背景复杂、模糊以及条码畸变等情况，使得直接使用成熟的算法识别DPM条码难以满足准确性要求[1].

目前适用于复杂背景、低对比度以及形变DPM图像的识别算法较少，王娟等[2]提出了一种改进的最小核同值区域角点检测和半监督近邻传播聚类算法相结合的方法来定位复杂背景下的DPM条码，该算法是以角点检测为基础进行定位的，但是对于背景中干扰角点较多图像的定位效果不佳，且无法对二维条码进行精确定位；刘志等[3]提出一种DPM二维条码识别算法，该算法速度快，但是仅仅适合背景简单的情况；郝云峰等[4]提出一种基于机器学习和级联过滤器联立的方法滤除背景区域，结合二维条码的几何性质检测候选区域，利用聚类法包络二维条码区域.该方法虽然可以较准确的定位出条码区域，但是速度不快，而且不能精确地定位出条码.针对以上问题，提出了一些改进的解决方法.利用机器学习和同态滤波相结合的方法解决了条码的初步定位问题；提出了基于投影的方向性L型拟合，增强了点阵DM二维条码向标准DM条码转换的效果；利用凸包算法结合改进的扫描线算法实现条码的精确定位.

1基于同态滤波和机器学习的条码初步定位

DPM码的初步定位是二维条码识别的首要步骤.在实际情况中，含有二维条码的图片往往存在高光、阴影、旋转，甚至是透视形变.目前，二维条码初步定位方法主要分为几何方法定位和纹理分析定位，几何方法定位是利用二维条码特有的几何形态，采用边缘提取、几何检测等数字图像分析方法来检测，而纹理分析定位是基于目标区域和背景区域纹理的基础上，利用特定的纹理特征训练出分类器，继而将二维条码进行初步定位[5].王翠艳等[6]提出了利用梯度投影法来初步定位二维条码.该方法主要是根据背景区域的灰度级变化平缓，条码区域灰度级变化剧烈的特点来定位二维条码的候选区域，但是对于存在高光、透视形变等问题的图片，会产生条码初步定位区域不完整，导致条码信息缺失.郝云峰等[4]出了使用机器学习和自适应SpatialBoost算法相结合的方法来定位二维条码，但是由于该方法最终采用聚类的方法来初步拟合条码区域，这将会大大降低条码定位速度.针对这些情况，提出了一种同态滤波与机器学习相结合的方法来初步定位二维条码，该方法包括了训练和实验两个阶段[7].

1.1　训练阶段

将输入的图片进行同态滤波处理，将图片分割成图片子块，对每一个图片子块提取多分辨率直方图(Fmrh)特征和局部二值模式(Flbp)特征，对特征利用AdaBoost算法训练出一个二维条码检测器.该检测器以图片子块的多分辨率直方图特征和局部二值模式特征作为输入向量，输出子块的分类结果.

1) 局部二值模式(Flbp)特征.这是一种灰度无关和旋转无关的纹理特征，对于每一个像素点的局部二值特征值计算方法为

(1)

其中：gi(i=0，1，…，8)为gc八邻域内的像素点，且从gc右侧开始按逆时针方向排列.在对图片子块中每一个像素点计算出局部二值特征值之后，我们最终使用特征值的直方图作为一个图片子块的局部二值模式特征.

2) 多分辨率直方图(Fmrh)特征.这种特征计算方便且对噪声鲁棒，并且能提取图像纹理的空间信息.具体过程为，先计算子块图像I0在多个分辨率下的图像I1，I2，…,Ii-1，对每个图像，再计算灰度直方图向量h0，h1，…，hn-1，最后，将各个相邻直方图向量的差连接为一个向量，即Fmrh=[h1-h0,…,hi-1-hi-2]，作为多分辨率直方图特征.在实验中，使用了3个图像分辨率(包括原图像).

3) 二维条码检测器.AdaBoost算法是一种迭代算法，其核心思想是对同一个训练集训练出不同的分类器，这些一般为弱分类器，然后将这些弱分类器线性组合成一个强分类器，其公式为

(2)

其中：X为输入向量，即从图片子块提取出的特征向量；Y为分类结果，0表示背景子块；1表示目标子块；∂t为合并系数；H(x)为训练出的条码检测器，它是若干个弱分类器ht(x)的线性组合.

1.2　实验阶段

Step 1将图片进行同态滤波处理，再进行图片子块分割，并将每个子块放入二维条码检测器中，最后每个子块会得到一个标志来标识它是属于目标子块还是背景子块.

Step 2在分类结束之后，提出一个纠错操作，即将每一块周围有大于等于4块目标子块的背景子块标识为目标子块,通过找到最大的目标连通区域来快速初步定位二维条码的位置.

图1(a)中经过以上两个步骤的操作，可以得到如图1(b)所示的效果,条码的大致区域可以被初步定位.

图1　DPM条码初步定位Fig.1　The image of primary location of DPM barcode

2基于投影的L型拟合

对于普通的DM条码，由于它具有明显的L型特征，所以在二值化操作之后可以根据L型标志来定位.由于研究的是点阵的DM条码，点阵DM条码的两条实边和两条虚边没有太大的差异，所以不能直接使用标准DM码的方法进行定位.文献[3]提出了利用形态学变换来拟合L型定位标志的方法，这种方法对于图像清晰且简单的条码是可以的，但是对于畸变或者有缺陷的条码图片会产生一些问题，对此提出了一种改进的L型拟合方法.

2.1　传统的条码L型特征拟合

传统的条码L型特征拟合方法直接采用形态学变换来拟合L型定位边，具体步骤如下：

Step 1对二值化之后的图像进行膨胀操作，具体表达式为

(3)

Step 2对膨胀之后的图片进行腐蚀操作，具体表达式为

(4)

先膨胀后腐蚀的形态学变换可以将原来的点阵二维条码拟合成标准的DM二维条码，但是由于膨胀腐蚀操作都是在水平和垂直方向进行的，所以会造成拟合后的图片存在比较严重的锯齿形状，如图2所示，使得之后的L型定位更加困难.

图2　一般L型拟合效果Fig.2　Result of normal L shape fitting

2.2　基于投影的条码L型特征拟合

点阵的Data Matrix二维条码是由黑白点组成的，二值化后在某两个相互垂直方向的投影会有明显规律，据此可获得图像中二维条码的两个主方向，然后通过方向性形态学变换拟合DM码L型边缘，具体方法如下：

1) 计算二值化后的图像，在0°，30°，45°，60°这4个方向的投影，具体计算式为

(5)

其中：f(x,y)为点(x,y)处的灰度值；x的范围为w+h/tanθ，w为图像的宽度,h为图像的高度.为了方便计算，采用图3中模板的角度α,β,γ分别模拟60°，45°，30°进行投影.

图3　30°，45°，60°的投影模板Fig.3　Templet projection of 30 degree, 45degree and 60 degree

2) 确定DM主方向.对于图4中的两张二值化后的条码图片，分别统计图中黑色像素点在0°和45°方向的投影，可以得到图5，6中所对应的数据统计结果.

由图4～6可以看出，在DM码主方向上的投影有3个规律：有效投影峰值应该是大于平均投影峰值(除去最大的投影峰值)的峰值；有效投影峰值之间有着近乎相等的间隔，因此，这些峰值之间距离的方差理应取得最小，在理想状态下应该为0；有效峰值数量应该近似等于点阵DM码实边上的黑点的个数.

图4　二值化图像Fig.4　Binary image

图5　X轴的投影统计Fig.5　Projection statistics on the X axis

图6　与X轴逆时针成45度方向距离上的投影统计Fig.6　Projection statistics on the axis with 45 degree counterclockwise to the X axis

根据DM码主方向投影的特征，定义变量p，a，D分别表示有效峰值，有效峰值之间距离平均值以及有效峰值之间距离的方差，即

(6)

(7)

其中：L为某一方向轴上有效峰值p所在的位置点；n为有效峰值的数量.

根据上一步得到DM的主方向，对图像进行方向明确性的形态学变换.从表1可以看出：改进后的L型拟合，可以取得比较好的效果.

3基于长度自适应扫描线算法的凸包定位

对L型拟合后的条码进行精确的定位，首先需要进行L型所在的两条“实边”的定位，然后再进行两条“虚边”的定位.常用的定位算法有Hough变换检测直线方法[8],而Hough变换虽然准确率高，但是变换计算复杂，耗时长，所以应选取更快的凸包算法[10].鲁剑等[10]提出了基于扫描线算法的凸包定位，这种方法对于标准的DM码可以取得较好地定位效果.但是对于点阵DPM码，会产生一定的问题,对此，提出了一种改进的方法.

表1一般L型拟合效果与改进后L型拟合结果比较

Table 1The comparison of normal L shape fitting and changed L shape fitting

二值化图片一般拟合效果改进后拟合效果

3.1　基于扫描线算法的凸包定位

基于扫描线算法的凸包定位的主要思路是首先通过凸包算法找到DM的两条实边，然后通过扫描线算法找到另外两条虚边，具体如下：

1) 找出最大连通区域，并利用凸包算法找到最大连通区域中的凸包点集.

2) 从凸包点集中找出二维条码的两条实边.由于理想状态下二维条码两条实边构成的夹角为90°，依托这个条件在对凸包点集中的点进行筛选，最终得到L型定位边.

3) 根据两条实边和平行四边形法则可以获取另外两条虚边的大致位置.之后，再利用扫描线算法，选出两个方向上能量最大时的两条边.

这种方法对于标准的DM码是可行的.因为标准扫描线算法是基于标准DM码的特性设定的，即标准DM码的虚边是由处于同一直线上等距直线段构成的.而对于点阵DPM码，由于L型拟合之后不能达到标准的平行四边形，普遍存在形变或者缺口，不一定能满足标准DM码特性，所以会造成虚边定位偏离问题，如图7所示，使得最终解码失败.

图7　传统方法定位结果Fig.7　Accurate location result of traditional method

3.2　基于长度自适应扫描线算法的凸包定位

标准扫描线算法的关键是根据标准DM虚边的特性定义能量公式E(l)=a(l)/D(l)，其中，a(l)为直线l上的梯度和，D(l)为直线l中线段的方差.当直线l为DM码虚边定位符所在直线时，a(l)取值最大，D(l)取值最小，能量E(l)最大.

根据能量公式可以发现：标准扫描线算法是通过直线的梯度和与直线线段的方差来判断该直线是否是虚边，并没有考虑别的问题.DPM码的虚边定位偏离问题本质是在其他方向上找到了一条满足标准扫描线算法的直线.所以，只要在方向上对其添加一定的约束就可以解决这类问题了.

利用凸包算法实现两条实边的定位之后，我们可以获得两条实边的长度和斜率.由于标准DM码是一个平行四边形，对边的长度和斜率在理想情况下应该一致.根据这个条件，提出了一种结合长度自适应扫描线算法的凸包定位算法，即在进行直线能量计算的同时，还需要根据L型定位边对其进行一个边长的约束，从而使得定位更加准确，具体描述如下：

1) 根据凸包算法得到的两条实边，计算出各自的长度.

2) 对于标准的DM条码，对边的长度应相等.而对于点阵拟合而来的DM条码的对边也应近似相等.所以对于每条虚边，在传统扫描线算法的基础上添加了自适应的长度约束，即

0.9L<=l<=1.1L

(8)

其中：l为虚边长度；L为与扫描边平行的实边的长度.

经实验验证，改进后的方法可以解决图7的定位问题，改进结果如图8所示.

图8　改进后算法定位结果Fig.8　Accurate location result of changed algorithm

4实验

选取了100张含有DM码、大小为640×480像素的图片，其中50张作为训练图片，50张作为测试图片.为了验证算法的有效性，用于测试的图像包含了高光、模糊以及畸变等情况.在VS2010软件平台和CPU为3.0 Hz,内存为4 G的硬件平台下进行实验.将图片划分成25×25像素的子图块，对50张实验图片进行训练实验，获取一个条码分类器并在该条码分类器基础上进行实验，图9，10为典型的条码图片定位过程及结果.

图9　DPM条码定位过程例图1Fig.9　Example 3 of DPM barcode location process

图9是含有高光的条码图片，图10是模糊且含有一定背景的条码图片.从图9，10可以看出：图9(a，b)和图10(a，b)中，同态滤波和机器学习相结合的初步定位方法在去除高光、背景等干扰的同时还可以较为准确地定位条码所在区域；图9(d，e)和图10(d，e)中，方向性L型拟合法可以使得点阵条码在二值化后拟合成比较标准的DM条码；图9(f)和图10(f)中，基于长度自适应扫描线算法的凸包定位可以精确定位条码.

图10　DPM条码定位过程例图2Fig.10　Example 2 of DPM barcode location process

5结论

针对DPM二维条码图像，结合了同态滤波和机器学习的方法来解决图像对比度低、高光等问题，实现条码的初步定位.根据二维条码在不同方向上的投影差异，提出了一种改进的L型拟合方法，使得拟合效果显著提高，且有助于条码的精确定位；利用基于长度自适应扫描线算法的凸包定位完成条码的精确定位.实验结果表明，以上算法的改进可以增强DPM码的识别效果.

参考文献：

[1]李娟,苏冠群,刘丽梅.DPM技术标准化发展探析[J].标准科学,2009(10):32-35.

[2]王娟,王萍.直接零件标志条码区域定位算法[J].计算机辅助设计与图形学学报,2014,26(7):1159-1166.

[3]刘志,单冰,郑河荣.直接零件标记的二维条码定位方法[J].计算机系统应用,2014,23(11):111-115.

[4]郝云峰,戚飞虎,蒋人杰.一种新的基于机器学习的2维条形码检测算法[J].中国图象图形学报,2007,12(10):1873-1876.

[5]王伟,何卫平,雷蕾,等.复杂金属背景下二维条码区域的快速定位[J].天津大学学报(自然科学与工程技术版),2013,46(6):531-538.

[6]王翠艳,张建超.标刻在金属零件上的二维条码识别[J].计算机应用,2012,32(11):3210-3213.

[7]肖俊,宋寿鹏,丁丽娟.空域同态滤波算法研究[J].中国图象图形学报,2008,13(12):2302-2306.

[8]王伟,何卫平,雷蕾,等.污染及多视角下DataMatrix码精确定位[J].计算机辅助设计与图形学学报,2013,25(9):1345-1353.

[9]LEONG L K, YUE W. Extraction of 2d barcode using keypoint selection and line detection[C]//Paisarn Muneesawang: Advances in Multimedia Information Processing-PCM 2009. Heidelberg Berlin: Springer,2009:826-835.

[10]鲁剑,刘志.基于改进凸包算法的移动端条码图像定位与校正[J].浙江工业大学学报,2010,38(6):661-665.

(责任编辑：刘岩)

Research on the key technologies of rapid positioning on DPM barcode

LIU Zhi, HONG Meifang

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:Direct Part Marking technology is an important means to achieve product identification, in which the Data Matrix Barcode is used to identify product. DPM barcode is marked on a mental surface by laser, so the positioning process will be subject to the bad condition which may lead to high light, blurred or distorted. The method of combination of homomorphic filtering and machine learning is used to enhance the image and implement the initial positioning of the barcode area. For the dotted barcode, a projection-based directionality L shape fitting method is proposed, which can make an accurate fitting for L shape. An improved line scanning algorithm based convex hull algorithm is used to realize the accurate positioning of barcode. Experiments show that compared with the existing key technologies, the improved key technologies can achieve better recognition result fro barcode.

Keywords:DPM barcode; machine learning; L shape fitting; convex hull algorithm

中图分类号：TP391

文献标志码：A

文章编号：1006-4303(2016)01-0028-06

作者简介：刘志(1969—)，女，辽宁沈阳人，教授，博士，硕士生导师，研究方向为图形图像处理技术，E-mail：lzhi@zjut.edu.cn.

基金项目：国家自然科学基金资助项目(61272304);浙江省自然科学基金资助项目(LY16F020033);浙江省科技厅公益项目(2012C21046)

收稿日期：2015-09-18