約束聚類算法的多目標(biāo)QR碼定位識(shí)別方法

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

1(長春工業(yè)大學(xué)機(jī)電工程學(xué)院 吉林 長春 130012) 2(長春工程學(xué)院機(jī)電工程學(xué)院 吉林 長春 130012) 3(中車長春軌道客車股份有限公司工業(yè)規(guī)劃發(fā)展部 吉林 長春 130062)

0 引 言

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

圖1 粘貼位置

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

為了解決QR碼在曲面環(huán)境讀取時(shí)間長,讀取率不高的問題,將托盤上的所有貨物對(duì)應(yīng)的QR碼貼到一張卡片上,只要讀取到平面上多目標(biāo)QR碼的信息即可。基于此本文提出了多目標(biāo)QR碼定位識(shí)別方法,圖2所示為本文算法的流程,該算法有效解決了托盤承載的貨物數(shù)量和讀取到的QR碼數(shù)量不一致的問題,能夠保證進(jìn)入立體倉庫的所有貨物的信息全部錄入智能選配系統(tǒng)中。

圖2 算法流程

1 圖像預(yù)處理

1.1 圖像二值化

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

(1)

(2)

p1×m1+p2×m2=mG

(3)

p1+p2=1

(4)

類間方差表達(dá)式為:

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

(5)

對(duì)式(5)化簡(jiǎn),可得:

σ2=p1p2(m1-m2)2

(6)

化簡(jiǎn)得:

(7)

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

圖3 OTSU算法二值化

1.2 QR碼探測(cè)圖案提取

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

圖4 位置探測(cè)圖案

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

圖5 定位探測(cè)圖案步驟

如圖6所示,以單個(gè)QR碼為例,可以看到滿足該比例的區(qū)域不只是位置探測(cè)圖案區(qū)域,橢圓處標(biāo)識(shí)QR碼內(nèi)部區(qū)域也存在該比例,基于此提出了去除偽探測(cè)區(qū)域算法。

圖6 滿足比例的區(qū)域

2 去除偽探測(cè)區(qū)域

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

(a)

(b)圖7 重心確認(rèn)

3 位置探測(cè)圖案中心點(diǎn)聚類

經(jīng)過去除偽位置探測(cè)區(qū)域后,得到每個(gè)位置探測(cè)圖案的重心坐標(biāo),其位置探測(cè)圖案?jìng)€(gè)數(shù)計(jì)為K,則QR碼個(gè)數(shù)為K/3。需要對(duì)獲取的所有坐標(biāo)點(diǎn)進(jìn)行聚類,劃分出只屬于同一個(gè)QR碼的3個(gè)位置探測(cè)圖案的重心坐標(biāo)。

3.1 聚類算法

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

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

圖8 理想的感興趣區(qū)域

3.2 初始聚類中心及簇樣本點(diǎn)選擇

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

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

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

(3) 將滿足為一簇的移除點(diǎn)集,繼續(xù)逼近其余二維碼區(qū)域,重復(fù)上述步驟直到確定K個(gè)簇。

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

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

輸入:位置探測(cè)圖案中心點(diǎn)坐標(biāo)數(shù)組X、Y。

輸出:初始聚類中心點(diǎn)。

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

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

//直線方程

3． m=find(Y==y)

//索引

4． n=length(m)

//數(shù)量

5．for 1 to n:

//計(jì)算這幾個(gè)點(diǎn)是否屬于同簇

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

7．endfor

8．Distance=CalculateThisDistance(points);

//計(jì)算各自的點(diǎn)距

9．If(Distance?Constraint)

//不在同一簇

10．{

11．For 1 to n

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

//統(tǒng)計(jì)這些點(diǎn)與其余點(diǎn)的距離

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

14． {

//坐標(biāo)相加

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．{

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

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)三個(gè)成員坐標(biāo),通過式(8)求出其質(zhì)心坐標(biāo)μ1(x,y)作為初始點(diǎn)。

x=x1+x2+x3/3

y=y1+y2+y3/3

(8)

求出K個(gè)質(zhì)心坐標(biāo),將其作為新的聚類中心進(jìn)行聚類。具體步驟如下:

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

(2) 計(jì)算每個(gè)簇的質(zhì)心作為新的聚類中心。

(3) 重復(fù)步驟(1)和步驟(2),通過式(9)計(jì)算出此時(shí)的損失函數(shù),直到損失函數(shù)趨于穩(wěn)定值。損失函數(shù)定義為K個(gè)簇中每個(gè)樣本點(diǎn)到其質(zhì)心的平方和。實(shí)驗(yàn)表明,迭代10次后,若e不改變,說明聚類中心不在大范圍移動(dòng)。如圖9所示,矩形方塊內(nèi)的中心點(diǎn)坐標(biāo)即為求出的聚類中心點(diǎn)。

(9)

式中:k是聚類中心的個(gè)數(shù);x是第i個(gè)聚類樣本中的點(diǎn);Ci是第i個(gè)聚類樣本中的點(diǎn)的集合;μi是第i聚類樣本的聚類中心點(diǎn)。

圖9 聚類中心點(diǎn)

3.4 單個(gè)QR碼分割

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

(10)

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖10 測(cè)試樣張

表1 二維碼識(shí)別結(jié)果

實(shí)驗(yàn)表明,采用平面上多個(gè)QR碼一起識(shí)別,其準(zhǔn)確率相比于在曲面上識(shí)別QR碼識(shí)別率要高。而且對(duì)不同尺寸的二維碼識(shí)別結(jié)果進(jìn)行分析,尺寸在12 mm×12 mm的識(shí)別效果要優(yōu)于其他兩種尺寸,識(shí)別率為96.7%。總體來說在采集到的100幅圖像中,能夠全部識(shí)別出所有二維碼的副數(shù)達(dá)到96幅。測(cè)試過程中發(fā)現(xiàn),有些圖像中存在漏檢現(xiàn)象的原因有:某些位置的QR碼印刷模糊、二維碼畸變嚴(yán)重等問題,將上述環(huán)境優(yōu)化后,能夠達(dá)到全部識(shí)別的要求。

5 結(jié) 語

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

傳統(tǒng)的聚類算法以距離最小為約束,容易受到噪聲點(diǎn)的干擾,不但其聚類結(jié)果容易受初始聚類點(diǎn)的影響,而且需要事先給定聚類個(gè)數(shù)。本文提出了基于約束的初始聚類中心的選擇算法,對(duì)初始點(diǎn)和簇?cái)?shù)的選擇進(jìn)行改進(jìn)。事先給定簇個(gè)數(shù)k,并以最大y值為掃描起點(diǎn),逐行掃描探測(cè)圖案重心,以距離約束選擇該簇的點(diǎn)集,并且根據(jù)其點(diǎn)集坐標(biāo)求該三點(diǎn)的質(zhì)心坐標(biāo)作為初始聚類中心,以聚類算法損失函數(shù)為參考變量,使聚類結(jié)果達(dá)到最優(yōu),從而分割出單幅二維碼圖像。