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