劉　志，洪梅芳

(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

?

DPM碼快速定位關(guān)鍵技術(shù)研究

劉志，洪梅芳

(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

摘要：直接零件標(biāo)識(DPM)技術(shù)是實現(xiàn)產(chǎn)品標(biāo)識的重要手段，以DM二維條碼進(jìn)行標(biāo)識.由于DPM碼是用激光標(biāo)記在金屬表面的點陣，在識別過程中會受到工況、光照等限制，存在高光、模糊甚至畸變等情況，導(dǎo)致條碼定位困難.采用同態(tài)濾波和機(jī)器學(xué)習(xí)相結(jié)合的方法來增強(qiáng)圖像實現(xiàn)條碼區(qū)域快速初步定位.針對點陣二維條碼的特殊性，提出一種基于投影的方向性L型擬合法，實現(xiàn)DataMatrix條碼的L型定位符的精準(zhǔn)擬合；利用基于改進(jìn)掃描線算法的凸包算法實現(xiàn)條碼的快速、準(zhǔn)確定位.實驗表明：與原有的關(guān)鍵技術(shù)相比，改進(jìn)后的關(guān)鍵技術(shù)可以得到更好的效果，使得條碼識別效果得到提高.

關(guān)鍵詞：DPM條碼；機(jī)器學(xué)習(xí)；L型擬合法；凸包算法

直接零件標(biāo)識(Direct part marking,DPM)技術(shù)是實現(xiàn)產(chǎn)品標(biāo)識的重要手段，并且以編碼容量大、密度高和糾錯能力強(qiáng)的DataMatrix二維條碼進(jìn)行標(biāo)識.研究的DPM條碼是用激光標(biāo)記在金屬表面的點陣Data Matrix二維條碼,由于環(huán)境光照、金屬紋理等原因，采集到的DPM條碼圖像普遍存在對比度低、多噪聲干擾、背景復(fù)雜、模糊以及條碼畸變等情況，使得直接使用成熟的算法識別DPM條碼難以滿足準(zhǔn)確性要求[1].

目前適用于復(fù)雜背景、低對比度以及形變DPM圖像的識別算法較少，王娟等[2]提出了一種改進(jìn)的最小核同值區(qū)域角點檢測和半監(jiān)督近鄰傳播聚類算法相結(jié)合的方法來定位復(fù)雜背景下的DPM條碼，該算法是以角點檢測為基礎(chǔ)進(jìn)行定位的，但是對于背景中干擾角點較多圖像的定位效果不佳，且無法對二維條碼進(jìn)行精確定位；劉志等[3]提出一種DPM二維條碼識別算法，該算法速度快，但是僅僅適合背景簡單的情況；郝云峰等[4]提出一種基于機(jī)器學(xué)習(xí)和級聯(lián)過濾器聯(lián)立的方法濾除背景區(qū)域，結(jié)合二維條碼的幾何性質(zhì)檢測候選區(qū)域，利用聚類法包絡(luò)二維條碼區(qū)域.該方法雖然可以較準(zhǔn)確的定位出條碼區(qū)域，但是速度不快，而且不能精確地定位出條碼.針對以上問題，提出了一些改進(jìn)的解決方法.利用機(jī)器學(xué)習(xí)和同態(tài)濾波相結(jié)合的方法解決了條碼的初步定位問題；提出了基于投影的方向性L型擬合，增強(qiáng)了點陣DM二維條碼向標(biāo)準(zhǔn)DM條碼轉(zhuǎn)換的效果；利用凸包算法結(jié)合改進(jìn)的掃描線算法實現(xiàn)條碼的精確定位.

1基于同態(tài)濾波和機(jī)器學(xué)習(xí)的條碼初步定位

DPM碼的初步定位是二維條碼識別的首要步驟.在實際情況中，含有二維條碼的圖片往往存在高光、陰影、旋轉(zhuǎn)，甚至是透視形變.目前，二維條碼初步定位方法主要分為幾何方法定位和紋理分析定位，幾何方法定位是利用二維條碼特有的幾何形態(tài)，采用邊緣提取、幾何檢測等數(shù)字圖像分析方法來檢測，而紋理分析定位是基于目標(biāo)區(qū)域和背景區(qū)域紋理的基礎(chǔ)上，利用特定的紋理特征訓(xùn)練出分類器，繼而將二維條碼進(jìn)行初步定位[5].王翠艷等[6]提出了利用梯度投影法來初步定位二維條碼.該方法主要是根據(jù)背景區(qū)域的灰度級變化平緩，條碼區(qū)域灰度級變化劇烈的特點來定位二維條碼的候選區(qū)域，但是對于存在高光、透視形變等問題的圖片，會產(chǎn)生條碼初步定位區(qū)域不完整，導(dǎo)致條碼信息缺失.郝云峰等[4]出了使用機(jī)器學(xué)習(xí)和自適應(yīng)SpatialBoost算法相結(jié)合的方法來定位二維條碼，但是由于該方法最終采用聚類的方法來初步擬合條碼區(qū)域，這將會大大降低條碼定位速度.針對這些情況，提出了一種同態(tài)濾波與機(jī)器學(xué)習(xí)相結(jié)合的方法來初步定位二維條碼，該方法包括了訓(xùn)練和實驗兩個階段[7].

1.1　訓(xùn)練階段

將輸入的圖片進(jìn)行同態(tài)濾波處理，將圖片分割成圖片子塊，對每一個圖片子塊提取多分辨率直方圖(Fmrh)特征和局部二值模式(Flbp)特征，對特征利用AdaBoost算法訓(xùn)練出一個二維條碼檢測器.該檢測器以圖片子塊的多分辨率直方圖特征和局部二值模式特征作為輸入向量，輸出子塊的分類結(jié)果.

1) 局部二值模式(Flbp)特征.這是一種灰度無關(guān)和旋轉(zhuǎn)無關(guān)的紋理特征，對于每一個像素點的局部二值特征值計算方法為

(1)

其中：gi(i=0，1，…，8)為gc八鄰域內(nèi)的像素點，且從gc右側(cè)開始按逆時針方向排列.在對圖片子塊中每一個像素點計算出局部二值特征值之后，我們最終使用特征值的直方圖作為一個圖片子塊的局部二值模式特征.

2) 多分辨率直方圖(Fmrh)特征.這種特征計算方便且對噪聲魯棒，并且能提取圖像紋理的空間信息.具體過程為，先計算子塊圖像I0在多個分辨率下的圖像I1，I2，…,Ii-1，對每個圖像，再計算灰度直方圖向量h0，h1，…，hn-1，最后，將各個相鄰直方圖向量的差連接為一個向量，即Fmrh=[h1-h0,…,hi-1-hi-2]，作為多分辨率直方圖特征.在實驗中，使用了3個圖像分辨率(包括原圖像).

3) 二維條碼檢測器.AdaBoost算法是一種迭代算法，其核心思想是對同一個訓(xùn)練集訓(xùn)練出不同的分類器，這些一般為弱分類器，然后將這些弱分類器線性組合成一個強(qiáng)分類器，其公式為

(2)

其中：X為輸入向量，即從圖片子塊提取出的特征向量；Y為分類結(jié)果，0表示背景子塊；1表示目標(biāo)子塊；?t為合并系數(shù)；H(x)為訓(xùn)練出的條碼檢測器，它是若干個弱分類器ht(x)的線性組合.

1.2　實驗階段

Step 1將圖片進(jìn)行同態(tài)濾波處理，再進(jìn)行圖片子塊分割，并將每個子塊放入二維條碼檢測器中，最后每個子塊會得到一個標(biāo)志來標(biāo)識它是屬于目標(biāo)子塊還是背景子塊.

Step 2在分類結(jié)束之后，提出一個糾錯操作，即將每一塊周圍有大于等于4塊目標(biāo)子塊的背景子塊標(biāo)識為目標(biāo)子塊,通過找到最大的目標(biāo)連通區(qū)域來快速初步定位二維條碼的位置.

圖1(a)中經(jīng)過以上兩個步驟的操作，可以得到如圖1(b)所示的效果,條碼的大致區(qū)域可以被初步定位.

圖1　DPM條碼初步定位Fig.1　The image of primary location of DPM barcode

2基于投影的L型擬合

對于普通的DM條碼，由于它具有明顯的L型特征，所以在二值化操作之后可以根據(jù)L型標(biāo)志來定位.由于研究的是點陣的DM條碼，點陣DM條碼的兩條實邊和兩條虛邊沒有太大的差異，所以不能直接使用標(biāo)準(zhǔn)DM碼的方法進(jìn)行定位.文獻(xiàn)[3]提出了利用形態(tài)學(xué)變換來擬合L型定位標(biāo)志的方法，這種方法對于圖像清晰且簡單的條碼是可以的，但是對于畸變或者有缺陷的條碼圖片會產(chǎn)生一些問題，對此提出了一種改進(jìn)的L型擬合方法.

2.1　傳統(tǒng)的條碼L型特征擬合

傳統(tǒng)的條碼L型特征擬合方法直接采用形態(tài)學(xué)變換來擬合L型定位邊，具體步驟如下：

Step 1對二值化之后的圖像進(jìn)行膨脹操作，具體表達(dá)式為

(3)

Step 2對膨脹之后的圖片進(jìn)行腐蝕操作，具體表達(dá)式為

(4)

先膨脹后腐蝕的形態(tài)學(xué)變換可以將原來的點陣二維條碼擬合成標(biāo)準(zhǔn)的DM二維條碼，但是由于膨脹腐蝕操作都是在水平和垂直方向進(jìn)行的，所以會造成擬合后的圖片存在比較嚴(yán)重的鋸齒形狀，如圖2所示，使得之后的L型定位更加困難.

圖2　一般L型擬合效果Fig.2　Result of normal L shape fitting

2.2　基于投影的條碼L型特征擬合

點陣的Data Matrix二維條碼是由黑白點組成的，二值化后在某兩個相互垂直方向的投影會有明顯規(guī)律，據(jù)此可獲得圖像中二維條碼的兩個主方向，然后通過方向性形態(tài)學(xué)變換擬合DM碼L型邊緣，具體方法如下：

1) 計算二值化后的圖像，在0°，30°，45°，60°這4個方向的投影，具體計算式為

(5)

其中：f(x,y)為點(x,y)處的灰度值；x的范圍為w+h/tanθ，w為圖像的寬度,h為圖像的高度.為了方便計算，采用圖3中模板的角度α,β,γ分別模擬60°，45°，30°進(jìn)行投影.

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

2) 確定DM主方向.對于圖4中的兩張二值化后的條碼圖片，分別統(tǒng)計圖中黑色像素點在0°和45°方向的投影，可以得到圖5，6中所對應(yīng)的數(shù)據(jù)統(tǒng)計結(jié)果.

由圖4～6可以看出，在DM碼主方向上的投影有3個規(guī)律：有效投影峰值應(yīng)該是大于平均投影峰值(除去最大的投影峰值)的峰值；有效投影峰值之間有著近乎相等的間隔，因此，這些峰值之間距離的方差理應(yīng)取得最小，在理想狀態(tài)下應(yīng)該為0；有效峰值數(shù)量應(yīng)該近似等于點陣DM碼實邊上的黑點的個數(shù).

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

圖5　X軸的投影統(tǒng)計Fig.5　Projection statistics on the X axis

圖6　與X軸逆時針成45度方向距離上的投影統(tǒng)計Fig.6　Projection statistics on the axis with 45 degree counterclockwise to the X axis

根據(jù)DM碼主方向投影的特征，定義變量p，a，D分別表示有效峰值，有效峰值之間距離平均值以及有效峰值之間距離的方差，即

(6)

(7)

其中：L為某一方向軸上有效峰值p所在的位置點；n為有效峰值的數(shù)量.

根據(jù)上一步得到DM的主方向，對圖像進(jìn)行方向明確性的形態(tài)學(xué)變換.從表1可以看出：改進(jìn)后的L型擬合，可以取得比較好的效果.

3基于長度自適應(yīng)掃描線算法的凸包定位

對L型擬合后的條碼進(jìn)行精確的定位，首先需要進(jìn)行L型所在的兩條“實邊”的定位，然后再進(jìn)行兩條“虛邊”的定位.常用的定位算法有Hough變換檢測直線方法[8],而Hough變換雖然準(zhǔn)確率高，但是變換計算復(fù)雜，耗時長，所以應(yīng)選取更快的凸包算法[10].魯劍等[10]提出了基于掃描線算法的凸包定位，這種方法對于標(biāo)準(zhǔn)的DM碼可以取得較好地定位效果.但是對于點陣DPM碼，會產(chǎn)生一定的問題,對此，提出了一種改進(jìn)的方法.

表1一般L型擬合效果與改進(jìn)后L型擬合結(jié)果比較

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

二值化圖片一般擬合效果改進(jìn)后擬合效果

3.1　基于掃描線算法的凸包定位

基于掃描線算法的凸包定位的主要思路是首先通過凸包算法找到DM的兩條實邊，然后通過掃描線算法找到另外兩條虛邊，具體如下：

1) 找出最大連通區(qū)域，并利用凸包算法找到最大連通區(qū)域中的凸包點集.

2) 從凸包點集中找出二維條碼的兩條實邊.由于理想狀態(tài)下二維條碼兩條實邊構(gòu)成的夾角為90°，依托這個條件在對凸包點集中的點進(jìn)行篩選，最終得到L型定位邊.

3) 根據(jù)兩條實邊和平行四邊形法則可以獲取另外兩條虛邊的大致位置.之后，再利用掃描線算法，選出兩個方向上能量最大時的兩條邊.

這種方法對于標(biāo)準(zhǔn)的DM碼是可行的.因為標(biāo)準(zhǔn)掃描線算法是基于標(biāo)準(zhǔn)DM碼的特性設(shè)定的，即標(biāo)準(zhǔn)DM碼的虛邊是由處于同一直線上等距直線段構(gòu)成的.而對于點陣DPM碼，由于L型擬合之后不能達(dá)到標(biāo)準(zhǔn)的平行四邊形，普遍存在形變或者缺口，不一定能滿足標(biāo)準(zhǔn)DM碼特性，所以會造成虛邊定位偏離問題，如圖7所示，使得最終解碼失敗.

圖7　傳統(tǒng)方法定位結(jié)果Fig.7　Accurate location result of traditional method

3.2　基于長度自適應(yīng)掃描線算法的凸包定位

標(biāo)準(zhǔn)掃描線算法的關(guān)鍵是根據(jù)標(biāo)準(zhǔn)DM虛邊的特性定義能量公式E(l)=a(l)/D(l)，其中，a(l)為直線l上的梯度和，D(l)為直線l中線段的方差.當(dāng)直線l為DM碼虛邊定位符所在直線時，a(l)取值最大，D(l)取值最小，能量E(l)最大.

根據(jù)能量公式可以發(fā)現(xiàn)：標(biāo)準(zhǔn)掃描線算法是通過直線的梯度和與直線線段的方差來判斷該直線是否是虛邊，并沒有考慮別的問題.DPM碼的虛邊定位偏離問題本質(zhì)是在其他方向上找到了一條滿足標(biāo)準(zhǔn)掃描線算法的直線.所以，只要在方向上對其添加一定的約束就可以解決這類問題了.

利用凸包算法實現(xiàn)兩條實邊的定位之后，我們可以獲得兩條實邊的長度和斜率.由于標(biāo)準(zhǔn)DM碼是一個平行四邊形，對邊的長度和斜率在理想情況下應(yīng)該一致.根據(jù)這個條件，提出了一種結(jié)合長度自適應(yīng)掃描線算法的凸包定位算法，即在進(jìn)行直線能量計算的同時，還需要根據(jù)L型定位邊對其進(jìn)行一個邊長的約束，從而使得定位更加準(zhǔn)確，具體描述如下：

1) 根據(jù)凸包算法得到的兩條實邊，計算出各自的長度.

2) 對于標(biāo)準(zhǔn)的DM條碼，對邊的長度應(yīng)相等.而對于點陣擬合而來的DM條碼的對邊也應(yīng)近似相等.所以對于每條虛邊，在傳統(tǒng)掃描線算法的基礎(chǔ)上添加了自適應(yīng)的長度約束，即

0.9L<=l<=1.1L

(8)

其中：l為虛邊長度；L為與掃描邊平行的實邊的長度.

經(jīng)實驗驗證，改進(jìn)后的方法可以解決圖7的定位問題，改進(jìn)結(jié)果如圖8所示.

圖8　改進(jìn)后算法定位結(jié)果Fig.8　Accurate location result of changed algorithm

4實驗

選取了100張含有DM碼、大小為640×480像素的圖片，其中50張作為訓(xùn)練圖片，50張作為測試圖片.為了驗證算法的有效性，用于測試的圖像包含了高光、模糊以及畸變等情況.在VS2010軟件平臺和CPU為3.0 Hz,內(nèi)存為4 G的硬件平臺下進(jìn)行實驗.將圖片劃分成25×25像素的子圖塊，對50張實驗圖片進(jìn)行訓(xùn)練實驗，獲取一個條碼分類器并在該條碼分類器基礎(chǔ)上進(jìn)行實驗，圖9，10為典型的條碼圖片定位過程及結(jié)果.

圖9　DPM條碼定位過程例圖1Fig.9　Example 3 of DPM barcode location process

圖9是含有高光的條碼圖片，圖10是模糊且含有一定背景的條碼圖片.從圖9，10可以看出：圖9(a，b)和圖10(a，b)中，同態(tài)濾波和機(jī)器學(xué)習(xí)相結(jié)合的初步定位方法在去除高光、背景等干擾的同時還可以較為準(zhǔn)確地定位條碼所在區(qū)域；圖9(d，e)和圖10(d，e)中，方向性L型擬合法可以使得點陣條碼在二值化后擬合成比較標(biāo)準(zhǔn)的DM條碼；圖9(f)和圖10(f)中，基于長度自適應(yīng)掃描線算法的凸包定位可以精確定位條碼.

圖10　DPM條碼定位過程例圖2Fig.10　Example 2 of DPM barcode location process

5結(jié)論

針對DPM二維條碼圖像，結(jié)合了同態(tài)濾波和機(jī)器學(xué)習(xí)的方法來解決圖像對比度低、高光等問題，實現(xiàn)條碼的初步定位.根據(jù)二維條碼在不同方向上的投影差異，提出了一種改進(jìn)的L型擬合方法，使得擬合效果顯著提高，且有助于條碼的精確定位；利用基于長度自適應(yīng)掃描線算法的凸包定位完成條碼的精確定位.實驗結(jié)果表明，以上算法的改進(jìn)可以增強(qiáng)DPM碼的識別效果.

參考文獻(xiàn)：

[1]李娟,蘇冠群,劉麗梅.DPM技術(shù)標(biāo)準(zhǔn)化發(fā)展探析[J].標(biāo)準(zhǔn)科學(xué),2009(10):32-35.

[2]王娟,王萍.直接零件標(biāo)志條碼區(qū)域定位算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2014,26(7):1159-1166.

[3]劉志,單冰,鄭河榮.直接零件標(biāo)記的二維條碼定位方法[J].計算機(jī)系統(tǒng)應(yīng)用,2014,23(11):111-115.

[4]郝云峰,戚飛虎,蔣人杰.一種新的基于機(jī)器學(xué)習(xí)的2維條形碼檢測算法[J].中國圖象圖形學(xué)報,2007,12(10):1873-1876.

[5]王偉,何衛(wèi)平,雷蕾,等.復(fù)雜金屬背景下二維條碼區(qū)域的快速定位[J].天津大學(xué)學(xué)報(自然科學(xué)與工程技術(shù)版),2013,46(6):531-538.

[6]王翠艷,張建超.標(biāo)刻在金屬零件上的二維條碼識別[J].計算機(jī)應(yīng)用,2012,32(11):3210-3213.

[7]肖俊,宋壽鵬,丁麗娟.空域同態(tài)濾波算法研究[J].中國圖象圖形學(xué)報,2008,13(12):2302-2306.

[8]王偉,何衛(wèi)平,雷蕾,等.污染及多視角下DataMatrix碼精確定位[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,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ìn)凸包算法的移動端條碼圖像定位與校正[J].浙江工業(yè)大學(xué)學(xué)報,2010,38(6):661-665.

(責(zé)任編輯：劉巖)

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

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-4303(2016)01-0028-06

作者簡介：劉志(1969—)，女，遼寧沈陽人，教授，博士，碩士生導(dǎo)師，研究方向為圖形圖像處理技術(shù)，E-mail：lzhi@zjut.edu.cn.

基金項目：國家自然科學(xué)基金資助項目(61272304);浙江省自然科學(xué)基金資助項目(LY16F020033);浙江省科技廳公益項目(2012C21046)

收稿日期：2015-09-18