复杂金属背景下二维条码区域的快速定位

王 伟，何卫平，雷 蕾，林清松

复杂金属背景下二维条码区域的快速定位

王 伟，何卫平，雷 蕾，林清松

(西北工业大学机电学院，西安 710072)

目前二维条码定位一般使用几何方法或纹理分析方法，其鲁棒性或实时性较差，尤其是在金属材质表面．针对传统二维条码定位方法的不足，提出了基于机器学习和级联过滤器联立的方法滤除背景区域，结合二维条码的几何性质检测候选区域，然后利用聚类生长法包络二维条码区域．实验结果表明：与传统算法相比，本文的算法对于各种复杂金属背景上的二维条码定位具有很高的鲁棒性与实时性，利用训练后的级联分类器和连通区域判决器，平均定位准确率可达到97%，并且处理时间控制在700,ms以内，对金属零件上二维码信息的可靠获取具有重要价值．

二维条码；金属背景；机器学习；级联检测；聚类生长

直接零件标识(direct part marking，DPM)技术是一种可直接在产品的表面形成包括文字、符号或图案等形式的永久标识技术．由于Data Matrix条码(简称DM码)编码容量大、密度高、纠错能力强，所以多选用DM码作为产品的二维条码永久标识[1]．本文中DPM生成的二维条码符号直接标记在金属零件或加工刀具表面，在零件或刀具的全生命周期管理中，二维条码起着至关重要的作用，是区分零件或刀具的唯一标识，但由于金属本身具有纹理性、低对比度背景、易反光及光照不均、可能具有曲面弧度和易受污染等特点，所以与背景简单的印刷品上二维条码定位相比，金属背景上的二维条码定位要复杂得多．

目前二维条形码的定位主要分为硬件辅助定位法与软件检测法．其中硬件辅助定位法如日本Cognex Corp出产的手持式Dataman750和封闭式读码器MATRIX2000，都是先利用辅助线或定位点预定位条码区域，然后提取条码数据，这样虽然准确率较高，但由于加入了人工因素，不可能运用于二维条码自动识读领域．软件检测法主要分为几何方法定位和纹理分析定位两类，几何方法定位是利用二维条码特有的几何形态，采用边缘提取、几何检测等[2-3]数字图像分析方法来检测，优点是速度快、精度高，但如果背景过于复杂，几何定位将会很容易误检．纹理分析定位是基于目标区域和背景区域纹理的基础上，利用特定的纹理特征训练出分类器，继而将二维条码区域提取出来[4-6]．优点是鲁棒性强，缺点是处理速度慢，很难做到实时应用．

针对目前二维条码检测算法的缺点，笔者提出基于机器学习与级联过滤器联立方法来检测定位二维条形码区域．机器学习包括目标子窗口学习和背景子窗口学习两类；级联过滤器由粗到精地利用机器学习的结果逐级过滤背景子窗口，并结合目标连通区域的几何性质进行判决，在每级过滤后检测是否出现潜在的目标区域，以此加快检测速度．可做到背景简单质量好的二维条码图像过滤级数少，速度快；背景复杂质量差的二维条码图像过滤级数多，检测细致．最后利用圆形聚类生长确定条码区域．

1 级联纹理特征分类器

不同的金属零件具有不同的背景纹理，如图1所示是几种常见的干扰背景．由于污染或纹理干扰严重，通过几何定位法无法定位到码区，所以采用纹理描述的方式区分背景与目标码区．

图1 金属零件上的DM码Fig1 Data matrix on metal parts

二维条码在图像中的位置与大小是未知的，对于大小与位置未知的目标检测，Viola等[7]提出使用的窗口滑动法，Fritz等[8]提出了一种基于兴趣点的物体检测方法，但这些方法都面临着巨大的计算量．本文中没用采用传统的目标检测法，而通过预划分原图像为若干子窗口，采用经过学习过的纹理特征分类器逐级过滤背景区域，并逐渐集中到目标区域，从而降低计算复杂度．

由于二维条码在图像中旋转角度是不定的，还存在自然光下光照条件不同，所以选取的纹理分类特征应首先满足大小、旋转与光照无关，针对传统的灰度直方图特征与边缘直方图特征进行改进，既保留了这两个特征的低计算复杂度，又满足了这3个无关性．由于局部二值特征本身就是大小、旋转与光照无关的，同时具有较高的描述精度与较低的计算复杂度，所以采纳为其中的一级特征．一般认为级联分类器是由粗到精地定位到目标区域[9]，为了达到较快的处理速度，按计算复杂度与描述精度从低到高特征排序：灰度直方图特征→局部二值特征→边缘直方图特征，顺序依次过滤背景子模块．

将整幅图像平均划分成p×q个子窗口，每个子窗口记为Gi,j(i=0,1,…,p-1;j=0,1,…,q -1)；然后级联分析每个子窗口的灰度直方图、局部二值特征和边缘方向直方图3个特征．

1.1 灰度直方图特征

在纹理特征中，灰度直方图特征是一个相对较简单的特征．它只能描述灰度的整体分布，无法描述像素之间的关联，所以描述的精确度较低．但它是大小无关且旋转无关的，并且算法简单速度快，所以选取它作为第1级判决算子．但是传统的灰度直方图特征是光照相关的，同时由韦伯-费可纳法则可知通常情况下，人眼对灰度级的分辨约为十几到几十个灰度级[10]，所以模仿人眼降低图像分辨率，利用16灰度级统一化各子窗口的灰度值分布范围，从而做到光照无关，简化计算．算法为

式中maxpi,j和minpi,j分别为子窗口Gi,j中的最大和最小像素值，判断maxpi,j-min pi,j是否小于16，若小于16则认为该子窗口过于平滑，将其置为背景区域，否则将该子窗口置为16区间{Areai}1i5=0，即

将,ijG中的像素值根据其所处的区间重置为

重置完后，由于每个子窗口的灰度值分布范围都为(0，15)，并且每个子窗口都属于小区域范围，理论上小区域范围光照近似是均衡的，所以可认为重置后的整体图像光照无关．统计重置之后的各子窗口灰度直方图，记为{Pi}1i=50．采用灰度直方图的均值μ、方差σ2、偏度S和熵E作为直方图的统计特征，实验表明，这4个特征能够很好地表现出直方图的分布特点，对于待判决子窗口Gi,j，改进的直方图特征用特征向量Histi,j表示为

1.2 局部二值模式特征

局部二值模式特征是Ojala等[11]提出的，该特征计算复杂度低、描述能力强、不受图片明暗程度的影响，也不受旋转的影响，并且此特征主要描述小区域内像素与像素之间的关联，所以本文中选取局部二模式特征作为第2级级联．图2是一个像素的3 3×邻域关系示意．中心像素与其8邻域像素的关系可以用联合分布来表示，即

由于只保留了正负号，所以该特征是灰度无关的．

图2 3×3邻域Fig.2 3×3 neighborhood of pixel

将联合分布唯一地对应一个数字，即

可以看出，LBP8共有28个取值，这么多的取值多是由于旋转差异造成的，为了达到旋转无关，需要对仅存在旋转差异的分布进行旋转归一化，即

式中ROR(LBP8,i)算子是将LBP8顺时针旋转i个单位．

旋转归一化后，LBP8ri减少为36个值，为进一步减少特征的取值范围，提高特征的泛化能力，将某些分布归成一类，即

其中

这样就将该特征的取值范围限制为(0,9)．然后统计每个候选目标子窗口,ijG的局部二值模式特征，得到局部二值模式特征的直方图,LPij，即

式中：LBP8riu2[i]代表子窗口Gi,j中LBP8riu2=i的像素的数量；sizeof( Gi,j)代表Gi,j中像素的总数量．

1.3 边缘梯度方向直方图判决

灰度直方图和局部二值模式都是对图像灰度值纹理分布的一种描述，而事实上对于二维条码图像来说，边缘信息是更重要的一种纹理，因为DM码区域就是由相互垂直的边缘组成，所以选取边缘直方图作为最后一级判决．由于边缘梯度方向直方图具有光照变化不敏感性、大小尺度无关性及具有较高的描述能力，已被广泛地用到人脸识别[12]、手势识别[13]及车牌识别中．但传统的边缘直方图对角度旋转是敏感的，结合DM码的特征，对边缘直方图进行位移统一化，从而做到了边缘直方图旋转无关化．

(1) 为了准确地定位边缘，排除空白区域，先用BOM算法求取原图像的灰度边缘，即

式中：A是原图像；1A是灰度边缘图像；⊕为灰度膨胀；Θ为灰度腐蚀；g为结构元素．(2) 定义边缘强度函数(,)g x y为

式中gx(x,y)和gy(x,y)分别是x和y方向上的梯度．

定义边缘方向函数为

候选目标子窗口,ijG的方向区间累计梯度强度函数定义为

为了减少计算复杂度，将梯度方向区间减少为16个，即t∈[0,15]，代表16个区间，实际表明对于边缘方向较集中的DM码，16个区间已足够精确描述；δ (θ(x, y)-t )函数定义为

(3) 根据主方向平移而达到无关化原边缘直方图．DM码的边缘是由两个相互垂直的主方向组成，所以主方向应当是16方向区间中最大的那一个区间，通过相邻3区间加权求出主方向区间，即

式中%为取余运算，由于区间0的前一区间为区间15，区间15的后一区间为区间0，所以区间t的前一区间与后一区间分别用(t+15)%16与(t+17)%16表示．

(4) 将网格的16区间边缘梯度平移至将最大边缘方向区间处于第5个区间，并归一化．这样就做到了旋转无关化，并得到新的16区间边缘梯度直方图．对于待判决子窗口Gi,j，旋转无关化的16区间边缘直方图特征向量为

1.4 基于SVM机器学习训练特征分类器

3个纹理特征分类事实上都是二类分类问题，即将划分网格判决为目标区域和背景区域，所以可以通过智能机器学习的方法训练3个特征分类器．目前基于智能学习的方法通常包含人工神经网络、模糊推理及支持向量机(SVM)等．由于输入纹理特征数量庞大，如果选择神经网络将需要大量的神经元和权值，同时由于样本采集不易，所选的各种复杂金属背景及二维条码样本图像数量有限，因此有必要选取一种支持小样本理论并解决高维数风险的智能学习算法．SVM是建立在统计学习理论基础上的一种机器学习方法，它基于结构风险最小化原则，较好地解决了小样本、非线性、高维数及局部极小点等实际问题，克服了人工神经网络易陷入局部极小点的缺点，因此采用SVM作为分类工具．

从m幅含有生锈腐蚀背景、高反光背景、金属纹理干扰背景与磨损划痕背景的训练图像中选取n/2个属于背景区域网格及n/2个属于二维条码区域的网格，并求取它们3个级联纹理特征，得到灰度直方图特征集合、局部二值模式特征集合和边缘直方图特征集合．这里以为例说明SVM对分类器训练的实现．

式中：K (Histi,Histj)=φ(Histi)·φ(Histj)是核函数；nsv是支持向量的个数，对于非线性支持向量机，常用的核函数有多项式核、高斯径向基函数、多层感知器等．本文采用的是高斯径向基函数，即

利用SVM把输入图像分为背景类网格与目标类网格，解出的支持向量也有两类：背景类支持向量和目标类支持向量．因此具有适合于小样本的特点，利用有限的样本，就可以得到性能优良的分类器．

2 通判决DM码连通区域

上述的3个级联判决器都是对单个子窗口进行判决的，如果在某级判决后，出现了一个可认为是目标区域的性质良好的连通区域，但只是因为未通过所有的级联检测而将其作为待定区域，这样做会有两个弊端：①增加运算成本，增加算法运算时间；②可能破坏存在的优良的目标连通区域，因为后续级联算法很有可能将其中的目标区域子窗口判决为背景区域.

基于上述问题，在每一级判决后都会检测存在的子窗口连通域，根据DM码的几何性质判断是否为候选DM码区域．与前面所述纹理特征判决结合，可以做到既具有几何分析法的精确又兼备纹理分析法的鲁棒．为此创造性地提出了3个判断子窗口连通域的几何性质：类圆度、边缘方向直方图双峰度和主方向对比．它们3个之间的关系如图3所示．

图3 分类器检测目标连通域Fig.3 Process of locating DM code

若某个连通域为可能的目标区域，则首先需要保证其优良的几何性质．DM码在图像中呈现的是正方形区域，由于存在各种旋转角度，所以不能直接以正方形几何性质判定．代替以类圆度进行几何性质判决，即连通域以小于某个阈值的类圆形式聚集，就可判定其为潜在目标区域而进行后续判决．首先设图像内存在连通域R，包含n个子窗口，首先求取连通域的质心(x', y')，其中x'=∑x/ n，y'= ∑y/ n且(x, y)∈R．类圆度就是指连通域的形状和圆形的相似程度，在几何上表示为圆心(质心)到边缘的距离的差异程度，其中标准圆差异为0，距离等于圆的半径．差异越大表明连通域聚集度越差、形状越不规则，或过长或过扁．

设连通域R的边缘为R，求取质心到R的最短和最长距离，即

并得到边缘到质心的距离集合

然后设圆半径为r，计算边缘点到圆周上距离的平均误差最小值

设对应的圆半径为rbest，并将此圆记为最佳包络圆，记为Cbest．判断类圆度误差与半径之比是否小于某个阈值：eR=Ebest/rbest＜T1．若小于则判定为类圆的连通域，否则判定为待检测区域．

2.2 边缘直方图双峰特征

在通过连通区域几何性质判定后，需要更严格和精确地判决以证明该连通区域是目标连通域．根据DM码的性质，最明显的特征就是其由相互垂直的直线边缘组成，所以理论上DM码区域的边缘直方图应该呈现一种“双峰”的形态．利用峰度计算刻画这对双峰．同第1.3节中算法一样，首先求取连通域中每个子窗口的边缘梯度方向直方图H(i,j)(t)，然后计算连通域R的整体边缘直方图为

根据HR(t)的主方向旋转平移边缘方向直方图，使主方向处于第5个区间，并归一化，得到HR(t)．理论上两个主方向的夹角近似于90°，即另一主方向应处在第13个区间附近，简化的双峰平均峰度值为

式中设gR＞T2为可能的目标区域．

党派分布方面（表1），125篇优质推文中，中国民主同盟发布最多，共40篇，占32%；其次是中国民主建国会26篇，占20.8%，中国农工民主党20篇，占16%，中国民主促进会15篇，占12%，中国国民党革命委员会10篇，占8%，中国致公党8篇，占6.4%，九三学社6篇，占4.8%；台湾民主自治同盟没有优质推文进入榜单。

2.3 主方向对比

单凭一个峰度特征无法判定连通区域是否为目标区域，因为有的污染区域可能会有一定的方向性，例如图1(c)，由于存在条纹状纹理污染，所以背景区域边缘直方图的峰度值也会很大．所以又引入主方向对比特征．根据DM码有两个相互垂直的主方向，并且强度相当，如果两个主方向对比在某个范围之内则有可能是目标区域，主方向对比为

设T3＜cR＜T4时，为可能的目标区域．

2.4 聚类生长

假如连通域R通过了类圆度判决、边缘直方图双峰特征判决与直方图对比判决，就确定其为候选DM码区域．由于判决比较严格，连通域R很有可能只占整个DM码的一部分，所以通过8个方向圆形聚类生长法确定整个DM码区域，算法如下．

(1) 根据第2.1节中确定的连通域R的最佳包络圆Cbest，以子窗口的1/4宽度为单位，分别以方向集的8个方向生长．

(2) 设θ方向生长后的包络圆为Cθ'，计算区域Cbest与Cθ'-Cbest的16区间边缘梯度方向直方图，并求取欧式距离，即

(3) Dθ'=min{Dθ}所对应的生长方向θ'设为最佳生长方向．如果区域Cθ'-Cbest的边缘方向主方向与区域Cbest的边缘方向主方向差异小于或等于1个区间，并且此区域的双峰平均峰度值gCθ'-Cbest＞T2，主方向对比T3＜cCθ'-Cbest＜T4，则向方向θ'做一个单位的圆生长，否则停止生长．

(4) 重复生长，直到不满足生长条件停止生长为止．至此所包络的区域认为是DM码区域．

3 实验结果

选取80幅含有DM码、大小为640× 480像素图像，分别包括生锈腐蚀金属背景、高光金属背景、磨损金属背景与纹理干扰金属背景等．在Visual Studio 2005软件平台，内存1,G、CPU 3.0,GHz硬件平台下进行实验验证．将图像划分为25× 25个子窗口，对这80幅图像进行大量实验，取得类圆度、双峰特征与主方向对比的联合经验阈值，eR＜0.24、gR＞0.75与0.56＜cR＜1.8时，实验在此联合阈值下样本的正确率可达到95%以上．图4～图7为典型复杂金属背景上DM码采用本文算法定位过程及结果．

图4 生锈腐蚀金属背景上DM码定位例图Fig.4 Examples of DM code location under rusty metal background

3.1 生锈腐蚀金属背景上DM码定位实例

聚类生长结果如图4(e)所示，处理时间为576,ms．由于生锈腐蚀背景较为复杂，本实例通过3步级联判决才最终定位到DM码区域．各级联连通域判决数据如表1所示．

表1 实例1各级联连通域判决数据Tab.1 Connect region data of each layer for example 1

3.2 高光金属背景上DM码定位实例

聚类生长结果如图5(d)所示，处理时间为306,ms，各级联连通域判决数据如表2所示．

图5 高光金属背景上DM码定位例图Fig.5 Examples of DM code location under high light metal background

表2 实例2各级联连通域判决数据Tab.2 Connect region data of each layer for example 2

3.3 磨损划痕金属上DM码定位实例

聚类生长结果如图6(d)所示，处理时间为290,ms，各级联连通域判决数据如表3所示．

图6 磨损划痕金属背景上的DM码定位例图Fig.6 Examples of DM code location under scratch interference metal background

表3 实例3各级连联通域判决数据Tab.3 Connect region data of each layer for example 3

3.4 纹理干扰金属上DM码定位实例

聚类生长结果如图7(d)所示，处理时间为296,ms，各级联连通域判决数据如表4所示．

图7 金属纹理干扰背景上的DM码定位例图Fig.7 Examples of DM code location under strong metallic texture interference background

上述4个实例由于各种污染，或是条码边界被遮盖、磨损掉，或是各种复杂背景干扰，传统的几何分析方法都是无法定位的，纹理分析方法可以定位，但是处理时间普遍都超过3,s，耗时过长．

表4 实例4各级联连通域判决数据Tab.4 Connect region data of each layer for example 4

3.5 统计分析

对于选取的这80幅图像，统计本文算法与传统算法对于复杂金属背景上二维条码定位效果对比，如表5所示．

表5 本文算法与现有算法效果对比Tab.5 Comparison between of results proposed algorithm and existing algorithm

如表5所示，本文算法与传统几何分析方法相差并不大，但准确率上传统几何分析方法远远达不到要求．虽然在定位准确率上本文方法与传统纹理分析方法相比并不具有太多优势，但本文方法的处理时间远远优于传统纹理分析方法，可做到实时应用．

对于不同类型的污染，本文统计结果如表6所示．

表6 对4种不同类型金属背景DM码定位结果统计Tab.6 Statistical results of DM location under four different metal backgrounds

大量的实验表明，本文算法适用于大多数金属背景下二维条码图像，并能够很好地将条码从背景中分离出来．

4 结 语

利用机器学习与级联过滤器结合的方法过滤背景区域，利用二维条码的边缘几何性质确定目标区域，既达到了传统几何定位法的精度，又具有纹理分析法的鲁棒性．同时，由于级联过滤器的引入使算法处理时间大大缩短，可以做到实时应用，有很大的工业应用价值．

参考文献：

［1］ International Organization for Standardization. ISO/IEC 16022—2006 Information Technology Automatic Identification and Data Capture Techniques-Data Matrix Bar Code Symbology Specification[S]. Geneva：International Organization for Standardization，2006.

［2］ Amould S，Awcock G J，Thomas R. Remote barcode localization using mathematical morphology [C]// Seventh International Conference on Image Processing and Its Applications．Manchester，UK，1999：642-646.

［3］ Viard-Gaudin C，Normand N，Barba D. A bar code location algorithm using a two-dimensional approach [C]// Proceedings of the 2nd International Conference on Document Analysis and Recognition. Tsukuba，Japan，1993：45-48.

［4］ Jain A K，Chen Y. Bar code localization using texture analysis [C]// Proceedings of the 2nd International Conference on Document Analysis and Recognition. Tsukuba，Japan，1993：41-44.

［5］ Alec C C，Lo C C，Hsieh K H. Neural networks and Fourier descriptors for part positioning using bar code features in material handling systems [J]. Computers and Industrial Engineering，1997，32(2)：467-476．

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

Hao Yunfeng，Qi Feihu，Jiang Renjie. A novel machine learning based algorithm to detect data matrix [J]. Journal of Image and Graphics，2007，12(17)：1873-1876 (in Chinese).

［7］ Viola P，Jones M J. Robust real-time face detection[J]. International Journal of Computer Vision，2004，57(2)：137-154.

［8］ Fritz M，Leibe B，Caputo B，et al. Integration representative and discriminant models for object category detection [C]// Tenth IEEE International Conference on Computer Vision，ICCV 2005. Beijing，China，2005：1363-1370.

［9］ Huang Chang，Al Haizhou，Wu Bo ，et al. Boosting nested cascade detector for multiview face detection[C]// Proceedings of the 17th International Conference on Pattern Recognition，ICPR 2004. Beijing，China，2004：415-418．

［10］ 张 晓，白廷柱，罗 霄，等. 基于人眼视觉灰阶特性的红外图像映射显示研究[J]. 红外技术，2008，30(4)：225-229.

Zhang Xiao，Bai Tingzhu，Luo Xiao，et al. IR image mapping based on human visual gray-scale properties[J]. Infrared Technology，2008，30(4)：225-229(in Chinese).

［11］ Ojala T，Pietikainen M，Maenpaa T. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(7)：971-987.

［12］ Levi K，Weiss Y. Learning object detection from a small number of examples：The importance of good features [C]// Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，CVPR 2004. Washington，USA，2004：53-60.

［13］ 孙丽娟，张立材. 基于边缘梯度方向直方图的静态手语识别[J]. 微电子学与计算机，2010，27(3)：148-153.

Sun Lijuan，Zhang Licai. Static sign language recognition based on edge gradient direction histogram[J]. Microelectronics and Computer，2010，27(3)：148-153(in Chinese).

Speedy Location of 2D Barcode Region Under Complicated Metal Background

Wang Wei，He Weiping，Lei Lei，Lin Qingsong
(School of Mechatronics，Northwestern Polytechnical University，Xi’an 710072，China)

Current detection algorithms include geometric method and texture analysis method. In locating 2D code under various material backgrounds, especially under metal background, geometric method is characterized by poor robustness and texture analysis method by slow processing speed. To solve the drawbacks mentioned above，the integration of machine learning method into cascade filter method is proposed in this paper to filter background areas, then the geometric properties of 2D barcode are used to detect candidate target area, and finally clustering growth method is employed to envelope 2D barcode region. The experiments reveal that, compared with traditional methods, the method proposed in this paper has achieved higher detection rate with better robustness. With the trained cascade classifier and the connected region classifier, the average positioning accuracy of 97% can be achieved and the processing time can be controlled within 700,ms, which has a great value in obtaining reliable information of 2D barcode on metal parts.

two-dimensional bar code；metal background；machine learning；cascade detection；clustering growth

TP391.41

A

0493-2137(2013)06-0531-08

DOI 10.11784/tdxb20130611

2011-11-04；

2012-03-01.

国防基础科研计划资助项目(A2720110011)；国家自然科学基金资助项目(51275419).

王 伟（1984— ），男，博士研究生，879322584@qq.com.

何卫平，weiping@nwpu.edu.cn.