卡片文本傾角提取的聚類方法

劉 昶，王玉晗，孫維廣

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110159)

利用光電技術(shù)對(duì)卡片打印質(zhì)量進(jìn)行檢測(cè)時(shí)，由于客觀條件的限制和人為因素的影響，所拍攝的卡片圖像一般會(huì)存在一定程度的傾斜，因此需要事先提取圖像的傾斜角度，將圖像校正后再用于質(zhì)量檢測(cè)。

目前文本傾斜角度提取方法有很多，主要包括投影法[1]、Hough變換法[2-5]、基于Fourier變換的方法[6]、最近鄰連通域的方法[7-10]和基于Radon變換的方法[10]等。其中投影法是通過(guò)改變投影角度，將圖像中的文字向不同的方向投影，根據(jù)投影圖像的統(tǒng)計(jì)特征求得文本的傾斜角度。由于投影法需要向不同方向投影，所以通常計(jì)算量較大，時(shí)間復(fù)雜度較高[1]。Hough變換是最常用的文本傾斜角度檢測(cè)方法，通過(guò)對(duì)文本在0度到180度之間的所有角度進(jìn)行Hough變換，用一種啟發(fā)式方法測(cè)量每一個(gè)角度累加器數(shù)值的變化率，將最大變化率對(duì)應(yīng)的角度作為圖像的傾斜角度[3]。文獻(xiàn)[4]在Hough變換的基礎(chǔ)上加了Canny邊緣檢測(cè)，降低了Hough變換算法的時(shí)間復(fù)雜度，但該方法需要先計(jì)算出圖像傾斜的大致范圍?；贔ourier變換的方法是對(duì)文本圖像上所有像素點(diǎn)作Fourier變換，利用Fourier變換空間密度最大的特性求得傾斜角度，該方法計(jì)算量較大[6]。最近鄰連通域的方法是通過(guò)N個(gè)連通區(qū)域中心的K個(gè)最近鄰點(diǎn)，統(tǒng)計(jì)矢量方向的直方圖，以直方圖的峰值作為圖像的傾斜角；但當(dāng)數(shù)據(jù)分布不均勻時(shí)，最近鄰點(diǎn)會(huì)偏向數(shù)據(jù)密度較大的方向，從而影響聚類結(jié)果[8]。文獻(xiàn)[9]對(duì)連通域方法做了改進(jìn)，利用圖像的紋理特征對(duì)投影圖像進(jìn)行分析，用自適應(yīng)的方法選出只含有文本的區(qū)域，求出區(qū)域中心坐標(biāo)，定位文本行后擬合直線求出傾斜角度；該方法檢測(cè)速度快，且克服了圖像背景復(fù)雜的影響。文獻(xiàn)[10]先找出圖像子區(qū)域，將子區(qū)域中連通域底邊的中心作為特征點(diǎn)，利用特征點(diǎn)和文本行基線的關(guān)系，將特征點(diǎn)利用最小二乘法擬合出基線的方向，即為圖像傾斜方向；該方法提取傾斜角度速度快、準(zhǔn)確度高。基于Radon變換的方法[11]是利用Radon變換計(jì)算文本圖像沿指定方向的投影，把投影看作是二維函數(shù)在某一方向上的線積分，當(dāng)一個(gè)角度變化時(shí)，得到不同的投影值，計(jì)算最大值并得出文本圖像的角度；但該方法精度不高，不適用于對(duì)精度要求較高的場(chǎng)合。

卡片中的文本與普通文本相比，一般分為若干個(gè)字塊，且每個(gè)字塊的長(zhǎng)度較短，字塊內(nèi)部密度較高。針對(duì)卡片文本的特點(diǎn)，本文提出一種基于DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚類的傾斜角度提取方法，該方法將圖像中的文本像素點(diǎn)根據(jù)密度進(jìn)行聚類，然后通過(guò)最小二乘擬合直線求出圖像的傾斜角度，將本文方法應(yīng)用于卡片打印質(zhì)量缺陷檢測(cè)問題中取得了滿意的結(jié)果。

1 聚類算法

1.1 DBSCAN聚類算法

聚類是按照數(shù)據(jù)集中數(shù)據(jù)間的相似性進(jìn)行區(qū)分和分類的過(guò)程，其分類原則是使同一簇中的數(shù)據(jù)具有盡可能大的相似性，不同簇中的數(shù)據(jù)具有盡可能大的相異性[12]，數(shù)據(jù)集可以通過(guò)聚類劃分成一系列的子集。假設(shè)文本中的文字為橫版排列，一般情況下字塊間距和行間距均大于字間距，可通過(guò)聚類的方法對(duì)卡片中的字塊進(jìn)行聚類。本文提出用DBSCAN聚類方法對(duì)灰度圖像中文字像素點(diǎn)聚類。

卡片圖像中文字和背景的灰度值有較大的差異，因此可以設(shè)置閾值將文字和背景區(qū)分開，文字為黑色，背景為白色?？梢缘玫綀D像中文字區(qū)域像素點(diǎn)的坐標(biāo)集合P={(x,y)|I(x,y)≤T1}，I(x,y)為像素點(diǎn)(x,y)的灰度值，將集合P作為數(shù)據(jù)集。DBSCAN法是一種密度聚類算法[13]，該算法將簇定義為密度相連點(diǎn)的最大集合，把具有足夠高密度的區(qū)域劃分為簇；該算法輸入的參數(shù)為數(shù)據(jù)集P、鄰域半徑R和鄰域內(nèi)密度閾值參數(shù)MinPts。DBSCAN算法中距給定數(shù)據(jù)的距離小于R的區(qū)域稱為該數(shù)據(jù)的R鄰域；若R鄰域內(nèi)的數(shù)據(jù)樣本點(diǎn)數(shù)大于等于MinPts，則稱該數(shù)據(jù)為核心；對(duì)于數(shù)據(jù)P集中數(shù)據(jù)點(diǎn)pi和pj，若pi在pj的R鄰域內(nèi)，并且pi為核心，那么稱pi與pj直接密度可達(dá)；給定數(shù)據(jù)集P中一組數(shù)據(jù){p1,p2,…,pn}，若pi(i=1,2,…,n-1)到pi+1直接密度可達(dá)，則稱p1到pn密度可達(dá)。本文應(yīng)用DBSCAN思想對(duì)卡片二值圖中的字塊進(jìn)行聚類，其基本流程如下。

Step1：取數(shù)據(jù)集中一個(gè)未被標(biāo)記過(guò)的點(diǎn)，查看該點(diǎn)鄰域內(nèi)數(shù)據(jù)點(diǎn)的數(shù)量，若大于等于MinPts，則標(biāo)記該點(diǎn)為核心并形成一個(gè)新類，否則標(biāo)記為噪聲；

Step2：查找核心點(diǎn)密度可達(dá)的數(shù)據(jù)并合并為一類；

Step3：若數(shù)據(jù)集中所有數(shù)據(jù)均被標(biāo)記且沒有新數(shù)據(jù)加入任何類，則算法結(jié)束；否則轉(zhuǎn)到Step1。

1.2 結(jié)合降采樣的聚類算法

當(dāng)聚類的數(shù)據(jù)集較大時(shí)，上述聚類算法的計(jì)算時(shí)間較長(zhǎng)，由于文字在圖像上會(huì)形成點(diǎn)簇，因此本文使用降采樣的方法來(lái)減少聚類算法的處理時(shí)間，降采樣原理如圖1所示。

圖1 降采樣原理圖

設(shè)置每塊的像素尺寸為XW×YW，對(duì)原始圖像進(jìn)行分塊，設(shè)置塊中黑色像素點(diǎn)個(gè)數(shù)閾值T2，對(duì)降采樣圖像進(jìn)行二值化；若原始圖像的塊中黑色像素點(diǎn)的個(gè)數(shù)大于T2，則將對(duì)應(yīng)降采樣圖像中的像素點(diǎn)置“0”為黑色，否則將對(duì)應(yīng)降采樣圖像中的像素點(diǎn)置“1”為白色。若原始圖像尺寸為U×V，記降采樣后的圖像尺寸為Sx×Sy，其中，Sx=「U/XW?,Sy=「V/YW?(「·?表示向上取整)，降采樣聚類算法流程如下。

Step1：根據(jù)上述原理對(duì)圖像做降采樣處理，獲得降采樣圖像；

Step2：利用1.1節(jié)中的聚類算法對(duì)降采樣圖像進(jìn)行聚類，將數(shù)據(jù)分為P1、P2、…、PK，共K類，對(duì)應(yīng)的類別記為H1、H2、…、HK；

Step3：根據(jù)聚類結(jié)果對(duì)原始圖像進(jìn)行處理，對(duì)于降采樣圖像中的每個(gè)像素點(diǎn)(i,j)，若其所屬的類別為Hk，則將與該點(diǎn)對(duì)應(yīng)的原始圖像塊中的所有黑色像素點(diǎn)的類別也標(biāo)記為Hk。

采用以上方法可提高聚類算法的速度。圖2顯示了應(yīng)用降采樣方法進(jìn)行聚類的效果。圖2a為原始圖像的二值圖，尺寸為970×355，設(shè)置塊的尺寸為80×4，閾值T2為5。圖2b為橫縱均放大4倍后的降采樣圖。圖2c為針對(duì)降采樣圖像進(jìn)行聚類的結(jié)果，本文算法將數(shù)據(jù)點(diǎn)分成2類，深色和淺色分別表示聚類得到的兩類數(shù)據(jù)。圖2d為最終原始圖像的聚類結(jié)果?？梢钥闯霰疚姆椒傻玫綕M意的聚類結(jié)果。

圖2 聚類效果圖

2 傾斜角度計(jì)算

通過(guò)上述聚類方法得到的每一類數(shù)據(jù)Pk對(duì)應(yīng)卡片文本上的一個(gè)字塊，考慮到字塊的長(zhǎng)度大于寬度，可將字塊近似看成一條直線，于是字塊中的黑色像素點(diǎn)可看作是該直線的采樣，對(duì)于任意一點(diǎn)(xi,yi)∈Pk有

yi=ckxi+bk+εi

(1)

式中：ck和bk分別為對(duì)應(yīng)直線的斜率和截距；εi為采樣誤差?？紤]到卡片上的字塊是相互平行的，有c1=c2=…=cK，因此公式(1)可改寫為

yi=cxi+bk+εi

(2)

式中c代表所有直線的斜率，可用最小二乘法求得。為減少計(jì)算時(shí)間，將所有類別按所包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)由多到少排序，取前K*個(gè)數(shù)據(jù)點(diǎn)較多的類別(對(duì)應(yīng)較長(zhǎng)的字塊)，再求出每一類中列坐標(biāo)相同的數(shù)據(jù)的重心作為對(duì)應(yīng)直線的樣本點(diǎn)，以減少樣本點(diǎn)數(shù)量，將重心點(diǎn)代入公式(2)并寫成矩陣形式為

AX=B+ε

(3)

式中X=(cb1…bK*)T，可以求出

X=(ATA)-1(ATB)

(4)

從而獲得c值，對(duì)應(yīng)的傾角為卡片上文本的傾角。

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

3.1 DBSCAN聚類算法

為驗(yàn)證本文提出的卡片圖像傾角提取的聚類算法，選用尺寸為2350×1250的10幅卡片文本圖像，將這10幅圖像利用OpenCV在10度以內(nèi)每間隔一度做一次旋轉(zhuǎn)，共生成100幅測(cè)試圖像，取數(shù)據(jù)點(diǎn)最多的前3類數(shù)據(jù)求傾斜角度；用C++語(yǔ)言在Visual Studio 2010 環(huán)境下實(shí)現(xiàn)，測(cè)試環(huán)境為：Intel(R)Core(TM)i5 CPU；內(nèi)存6GB；操作系統(tǒng)為Windows7，與文獻(xiàn)[1]中的投影法和文獻(xiàn)[5]中的Hough變換方法作對(duì)比，求出每個(gè)角度下10幅圖像的平均提取誤差，誤差對(duì)比如圖3所示，提取時(shí)間和最大誤差的對(duì)比結(jié)果如表1所示。

圖3 平均誤差對(duì)比圖

傾斜角度檢測(cè)方法平均處理時(shí)間/秒最大誤差/度本文方法0.710.05投影法29.030.02Hough變換方法0.720.35

從圖3與表1可看出，本文方法和投影法的最大誤差均在0.05度以內(nèi)，Hough變換方法雖然可以對(duì)文本做傾斜校正，但算法精度不高，而投影法檢測(cè)文本傾斜角度精度與本文相近，但耗時(shí)較長(zhǎng)。綜合評(píng)價(jià)算法精度與耗時(shí)，本文算法取得滿意的結(jié)果。

文獻(xiàn)[4]的方法是目前針對(duì)文本傾角提取最快的方法之一，其原理是首先對(duì)圖像做邊緣檢測(cè)，然后通過(guò)邊緣估算出圖像大致的傾斜角度，再在一個(gè)較小的角度范圍內(nèi)進(jìn)行Hough變換求傾角以節(jié)省時(shí)間，但該方法不完全適用于卡片文本的傾角提取，因?yàn)榭ㄆ厦總€(gè)字塊的橫向文本可能較少，在進(jìn)行傾角估算時(shí)很可能出現(xiàn)嚴(yán)重的偏差而導(dǎo)致傾角提取錯(cuò)誤。圖4為本文方法與文獻(xiàn)[4]求得直線對(duì)比。文獻(xiàn)[4]得到的直線如圖4a所示，為近似垂直方向，顯然是錯(cuò)誤的；本文得到的直線如圖4b所示，結(jié)果正確，說(shuō)明本文方法魯棒性較好。

3.2 實(shí)際應(yīng)用

將本文方法應(yīng)用于某卡片打印質(zhì)量缺陷檢測(cè)

圖4 本文方法與文獻(xiàn)[4]求得直線對(duì)比

系統(tǒng)中，在缺陷檢測(cè)之前首先需要對(duì)待檢測(cè)圖像做文本傾斜校正。系統(tǒng)中圖像采集選用Basler acA1600-20gm工業(yè)相機(jī)，配12mm定焦鏡頭，拍照時(shí)圖像尺寸設(shè)置為1628×1236像素，缺陷檢測(cè)步驟如下。

(1)對(duì)待檢測(cè)卡片拍照獲得待檢測(cè)圖像，并進(jìn)行畸變校正；

(2)應(yīng)用本文方法對(duì)畸變校正后的圖像進(jìn)行傾角提取，根據(jù)提取結(jié)果用雙三次插值方法[14]做旋轉(zhuǎn)校正處理，再對(duì)校正后的圖像做二值化處理；

(3)從與卡片對(duì)應(yīng)的Excel數(shù)據(jù)文件導(dǎo)出字符尺寸相同的圖像作為標(biāo)準(zhǔn)模板；

(4)用模板匹配的方法將模板圖像與校正后的二值圖像最大程度對(duì)齊，然后通過(guò)圖像差分的方法找到圖像中的缺陷。

圖5為校正后圖像與結(jié)果圖像。圖5a為相機(jī)畸變校正后的圖像，其中每個(gè)文字的尺寸為50×50像素，字間距為5個(gè)像素，行間距為27個(gè)像素，可以看出校正后圖像存在一定傾斜。

設(shè)置區(qū)分文字與背景的閾值T1為40，降采樣塊的尺寸為80×4，降采樣圖像二值化閾值T2為5，降采樣圖像聚類鄰域半徑R為1，鄰域內(nèi)密度閾值參數(shù)MinPts為2，用于計(jì)算類別的數(shù)量K*為3。求出傾斜角度后，以圖像中心為旋轉(zhuǎn)中心對(duì)圖像做旋轉(zhuǎn)，傾斜校正后的二值圖像如圖5b所示，已將圖像中的文字方向校正成水平。從Excel導(dǎo)出的模板圖像如圖5c所示。傾斜校正后的二值圖像與模板圖像的差分圖像如圖5d所示。將圖5d中圖像作局部放大，效果如圖6所示?？梢钥闯觯捎诒疚乃惴▽?duì)原始卡片的傾角進(jìn)行了高精度提取，使得后續(xù)的傾斜校正與差分過(guò)程取得理想的結(jié)果。從圖6c的差分圖像可以看出，黑色像素在無(wú)缺陷區(qū)域分布稀疏，在有缺陷區(qū)域分布密集，后續(xù)可以通過(guò)統(tǒng)計(jì)黑色像素點(diǎn)的密度有效識(shí)別出缺陷區(qū)域。

圖5 校正后圖像與結(jié)果圖像

圖6 實(shí)驗(yàn)結(jié)果局部放大圖

4 結(jié)論

提出一種基于DBSCAN聚類的卡片文本圖像傾角提取方法，將足夠長(zhǎng)的文字近似看成一條直線，利用文本行間距大于字間距的性質(zhì)對(duì)字塊聚類；通過(guò)降采樣方法提高算法處理速度，對(duì)同一類別數(shù)據(jù)在列方向求重心，將重心看成對(duì)應(yīng)直線的樣本點(diǎn)，通過(guò)最小二乘法擬合直線求出卡片圖像的傾斜角度。實(shí)驗(yàn)證明該方法精度較高，適用于卡片打印質(zhì)量缺陷檢測(cè)等應(yīng)用中的文本傾斜角度提取。