約束聚類算法的多目標QR碼定位識別方法

王 華 趙偉甫 張 爽 高金剛 劉孝峰

1(長春工業大學機電工程學院 吉林 長春 130012) 2(長春工程學院機電工程學院 吉林 長春 130012) 3(中車長春軌道客車股份有限公司工業規劃發展部 吉林 長春 130062)

0 引 言

在高鐵列車輪對智能選配系統中,輪對零部件的各種尺寸銘牌信息作為選配數據支持,需要將這三種零部件的信息錄入選配系統中。為了快速地錄入信息,可以依據其信息生成一個二維碼,使用解碼軟件將解碼到的信息存入系統中。以車輪為例,二維碼上記錄著車輪的型號、生產廠家、材質、輪孔和車輪直徑等信息。如圖1所示,將QR碼貼在車輪表面上,位于車輪上方的相機拍攝包含QR碼的圖片,將解碼出的信息上傳到智能選配系統中,便于后續的輪對選配。

圖1 粘貼位置

在日常生活中,QR碼常常貼于平整位置,可以很方便獲取QR碼信息。在工業領域,QR碼貼于曲面環境中,但是存在著多種復雜因素,對讀取二維碼造成了干擾。文獻[1]研究了復雜背景下的DPM二維碼的圖像預處理,提出了自適應多閾值分割出二維碼所在區域,信息保有率超過90%。文獻[3]研究了一種貼于柱面的二維碼生成新方法,依據二維條碼和柱形條碼的映射關系,對不同半徑,生成了尺寸不同的二維碼。從實驗結論可以看出,曲率達到一定程度后條碼的識別率下降,待曲率超過0.62時條碼不能被識別。文獻[5]研究了在距離、角度、光線、背景等不同的情況下對多個二維碼提取,二維碼貼于墻壁上,識別率受到上述條件的影響,在90%～98%之間。

為了解決QR碼在曲面環境讀取時間長,讀取率不高的問題,將托盤上的所有貨物對應的QR碼貼到一張卡片上,只要讀取到平面上多目標QR碼的信息即可?；诖吮疚奶岢隽硕嗄繕薗R碼定位識別方法,圖2所示為本文算法的流程,該算法有效解決了托盤承載的貨物數量和讀取到的QR碼數量不一致的問題,能夠保證進入立體倉庫的所有貨物的信息全部錄入智能選配系統中。

圖2 算法流程

1 圖像預處理

1.1 圖像二值化

采用OTSU算法確定圖像二值化分割閾值,圖3所示為OTSU算法二值化的圖像[1]。該方法又稱作最大類間方差法,使得背景與前景的類間方差最大。假設前景、背景兩類像素的均值為m1、m2,圖像全局均值為mG。同時圖像中像素被分為C1和C2類的概率分別為P1、P2。k為要求的理想灰度值[2-3],則有:

(1)

(2)

p1×m1+p2×m2=mG

(3)

p1+p2=1

(4)

類間方差表達式為:

σ2=p1(m1-mG)2+p2(m2-mG)2

(5)

對式(5)化簡,可得:

σ2=p1p2(m1-m2)2

(6)

化簡得:

(7)

遍歷所有的灰度值i∈[0,255],使得式(7)最大的灰度值就是OTSU閾值;將大于該閾值的像素點設置為白色,小于該閾值的設置為黑色。對采集到的圖片多次進行OTSU閾值處理,求出的平均灰度值128作為閾值對圖像進行分割。

圖3 OTSU算法二值化

1.2 QR碼探測圖案提取

QR碼中含有3個探測定位圖案,如圖4所示,探測定位圖案由重疊的同心的正方形組成[4],1、2、3為其在QR碼圖案中的位置。

圖4 位置探測圖案

國內外研究學者常利用背景很少出現的長度比例1∶1∶3∶1∶1旋轉不變性來對QR碼定位,無論從什么方向角度掃描該探測圖案,該區域的長度比例是不變的。按行檢測定位探測圖案的步驟如圖5所示,逐行掃描,比較前一像素點與后一像素點相差是否為0,將差值相同的像素點的個數放入矩陣N中,查看是否有近似滿足比例的矩陣片段,將其標出。同理,按照列檢測也可以得到垂直方向的滿足該比例的區域[5]。

圖5 定位探測圖案步驟

如圖6所示,以單個QR碼為例,可以看到滿足該比例的區域不只是位置探測圖案區域,橢圓處標識QR碼內部區域也存在該比例,基于此提出了去除偽探測區域算法。

圖6 滿足比例的區域

2 去除偽探測區域

QR Code的國際標準規定,位置探測區域與數據區由寬度為一個白色模塊的分割符隔開。為了進一步確認該交點是否為位置探測區域的重心,引入了重心確認算法[6],將逐行逐列掃描后獲得的中點坐標重合的點記為重心坐標,依據QR碼探測圖案中三塊區域的面積比近似為9∶25∶49,判斷的步驟[9]如圖7(a)所示,去除后的重心坐標如圖7(b)所示。

(a)

(b)圖7 重心確認

3 位置探測圖案中心點聚類

經過去除偽位置探測區域后,得到每個位置探測圖案的重心坐標,其位置探測圖案個數計為K,則QR碼個數為K/3。需要對獲取的所有坐標點進行聚類,劃分出只屬于同一個QR碼的3個位置探測圖案的重心坐標。

3.1 聚類算法

聚類思想是數據分析的核心,其核心思想是發現數據中有相同或相似屬性的信息,使得這些信息分別聚為不同類別的簇,并使得相同簇中的對象之間的相似度高,而不同簇之間以及不同簇間對象的相似度低[7]。

使用傳統的K-means算法是基于樣本點距離初始點最小劃分出不同的簇,隨著迭代次數的變化,聚類算法劃分的簇中各個樣本點的數量、種類會有差異。而且傳統的K-means算法受聚類中心的個數以及初始聚類中心坐標影響。如圖8所示,每個坐標點代表位置探測圖案的重心,應用聚類的思想把這些重心劃分為具有QR碼特征的感興趣區域。因此,本文針對K-means聚類算法存在的缺陷,提出了新的求初始聚類中心的方法。

圖8 理想的感興趣區域

3.2 初始聚類中心及簇樣本點選擇

三個位置探測圖案的重心連線近似為等腰直角三角形,考慮QR碼會發生幾何形變失真,對使用的QR碼旋轉多個角度拍攝,計算出三個探測圖案重心之間的平均距離作為約束,定義直角邊的約束范圍在[130,135],定義斜邊的約束范圍在[180,185]。由此提出了基于距離約束的初始聚類中心,具體處理步驟如下:

(1) 以y=max{y1,y2,…,yn}逼近二維碼區域,如果此時只有一個點與直線重合,記錄該重合點與其余各點的距離和滿足直角邊與斜邊約束范圍內的兩個點,開始向下搜索下一個重合點,轉步驟(3);若此時有多個點與直線重合,轉步驟(2)。

(2) 記錄這些點的距離,將在約束范圍內的點取其中一點,依據約束范圍搜索第三個點,轉步驟(3);若這些點的距離不在同一約束范圍內,依據約束搜索各自的重心點。

(3) 將滿足為一簇的移除點集,繼續逼近其余二維碼區域,重復上述步驟直到確定K個簇。

本文算法主要從初始點的選擇以及簇的個數改進,首先簇的個數設置為K/3,然后利用直線搜索算法對初始點進行選取,按照事先定義好的距離約束對點集進行聚類,這樣能夠在更少的迭代次數內得到最優的聚類中心,如算法1所示。

算法1初始聚類中心選擇算法

輸入:位置探測圖案中心點坐標數組X、Y。

輸出:初始聚類中心點。

1．While(length(X)!=0)

2． y=max{y1,y2,y3,…}

//直線方程

3． m=find(Y==y)

//索引

4． n=length(m)

//數量

5．for 1 to n:

//計算這幾個點是否屬于同簇

6． points=(X(m(n)),y);

7．endfor

8．Distance=CalculateThisDistance(points);

//計算各自的點距

9．If(Distance?Constraint)

//不在同一簇

10．{

11．For 1 to n

12．Distance=CalculateDistanceTo(X(m(n)),y);

//統計這些點與其余點的距離

13．if(distance in self.Distance∈Constraint)

14． {

//坐標相加

15．X-Center=X(m(n))+X.searched_point_

first+X.searched_point_second;

16．Y-Center=y+Y.searched_point_first+

Y.searched_point_second;

17． }

18． RemoveThisPoints();

19．endfor

20．}

21．Else(Distance∈Constraint)

22．{

//假設有兩個點X(m(n)),X(m(n-1))在同一約束范圍內;

23． Distance=

CalculateDistanceTo(X(m(n)),y,X(m(n-1)),y);

24．if(distance in self.Distance∈Constraint)

25． {

26．X-Center=X(m(n))+X(m(n-1))+

X.searched_point_first;

27．Y-Center=2y+Y.searched_point_first;

28． }

29． RemoveThisPoints();

30．}

31．endwhile

3.3 K-means聚類算法

每一簇中a(x1,y2)、b(x2,y2)和c(x3,y3)三個成員坐標,通過式(8)求出其質心坐標μ1(x,y)作為初始點。

x=x1+x2+x3/3

y=y1+y2+y3/3

(8)

求出K個質心坐標,將其作為新的聚類中心進行聚類。具體步驟如下:

(1) 將距離某個聚類中心距離近的3個樣本點歸類到該聚類中心,將樣本全部歸類完畢后得到K個簇。

(2) 計算每個簇的質心作為新的聚類中心。

(3) 重復步驟(1)和步驟(2),通過式(9)計算出此時的損失函數,直到損失函數趨于穩定值。損失函數定義為K個簇中每個樣本點到其質心的平方和。實驗表明,迭代10次后,若e不改變,說明聚類中心不在大范圍移動。如圖9所示,矩形方塊內的中心點坐標即為求出的聚類中心點。

(9)

式中:k是聚類中心的個數;x是第i個聚類樣本中的點;Ci是第i個聚類樣本中的點的集合;μi是第i聚類樣本的聚類中心點。

圖9 聚類中心點

3.4 單個QR碼分割

以單個QR碼的三個位置探測圖案的重心為參考點,向外擴10個單位模塊寬度U,以此從多目標QR碼中分割出多幅單QR碼圖像。 使用的QR碼的位置探測圖案是由7×7模塊組成的,其模塊寬度通過式(10)求出[8]。

(10)

式中:S為位置探測圖案面積;U為模塊寬度。

4 實驗結果與分析

為驗證本文算法流程,使用某軌道交通企業提供的10 mm×10 mm,12 mm×12 mm,15 mm×15 mm的二維碼進行測試,將同一尺寸的二維碼貼在一張卡片上,1 628像素×1 236像素的工業相機位于其上方拍攝,10 mm×10 mm測試樣張如圖10所示。對測試樣張進行上述處理,并使用Zxing對分割出的QR碼進行解碼。

圖10 測試樣張

表1 二維碼識別結果

實驗表明,采用平面上多個QR碼一起識別,其準確率相比于在曲面上識別QR碼識別率要高。而且對不同尺寸的二維碼識別結果進行分析,尺寸在12 mm×12 mm的識別效果要優于其他兩種尺寸,識別率為96.7%?？傮w來說在采集到的100幅圖像中,能夠全部識別出所有二維碼的副數達到96幅。測試過程中發現,有些圖像中存在漏檢現象的原因有:某些位置的QR碼印刷模糊、二維碼畸變嚴重等問題,將上述環境優化后,能夠達到全部識別的要求。

5 結 語

本文就某軌道客車制造企業中高鐵列車輪對智能選配系統使用的QR碼應用情況展開了研究。針對多目標QR碼定位問題,提出了以約束聚類算法為核心的定位算法,能夠有效地對圖像中多目標QR碼進行定位與識別。

傳統的聚類算法以距離最小為約束,容易受到噪聲點的干擾,不但其聚類結果容易受初始聚類點的影響,而且需要事先給定聚類個數。本文提出了基于約束的初始聚類中心的選擇算法,對初始點和簇數的選擇進行改進。事先給定簇個數k,并以最大y值為掃描起點,逐行掃描探測圖案重心,以距離約束選擇該簇的點集,并且根據其點集坐標求該三點的質心坐標作為初始聚類中心,以聚類算法損失函數為參考變量,使聚類結果達到最優,從而分割出單幅二維碼圖像。