虞水磊，田新宇，王金燕

(中南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖南 長(zhǎng)沙 410083)

隨著互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，網(wǎng)絡(luò)安全問(wèn)題層出不窮，驗(yàn)證碼技術(shù)應(yīng)運(yùn)而生。 Aboufadel等[1]提出了扭曲估計(jì)的算法，并將之應(yīng)用于識(shí)別 EZ-Gimpy的驗(yàn)證碼。 Moy等[2]應(yīng)用 Harr 小波濾波識(shí)別驗(yàn)證碼。Zhang等[3]用KNN(K近鄰)算法破解了4個(gè)銀行網(wǎng)站的驗(yàn)證碼。王曉鵬[4]針對(duì)可分離的驗(yàn)證碼，采用 BP 神經(jīng)網(wǎng)絡(luò)和遺傳算法進(jìn)行了識(shí)別。王曉波等[5]利用基于 MODI(Microsoft Office Document Image,微軟辦公文檔圖像處理庫(kù))對(duì)CSDN、QQ、Yahoo、網(wǎng)易等網(wǎng)站的驗(yàn)證碼進(jìn)行識(shí)別,對(duì)于具有背景噪聲、字體工整且易于分割的驗(yàn)證碼如CSDN等有良好的識(shí)別效果,而對(duì)于QQ、Yahoo等加入多種干擾、字符變形大的識(shí)別率偏低。殷光等[6]對(duì)驗(yàn)證碼分割后用SVM分類的識(shí)別方法。王璐[7]釆用分割后用卷積神經(jīng)網(wǎng)絡(luò)識(shí)別驗(yàn)證碼。但是帶有噪聲及粘連的驗(yàn)證碼識(shí)別仍是值得深入探究的問(wèn)題。本文對(duì)帶有噪聲與粘連的驗(yàn)證碼進(jìn)行識(shí)別技術(shù)研究。

1 數(shù)據(jù)獲取與預(yù)處理

1.1 數(shù)據(jù)獲取

利用Python爬蟲(chóng)技術(shù)對(duì)某網(wǎng)站的驗(yàn)證碼進(jìn)行爬取，總共獲取350個(gè)驗(yàn)證碼，其大小為70×20像素。獲取的驗(yàn)證碼如圖1所示。

圖1 未處理驗(yàn)證碼Fig.1 Unprocessed CAPTCHA

1.2 數(shù)據(jù)預(yù)處理

1.2.1 數(shù)據(jù)二值化

首先將圖片讀取為RGB三維數(shù)組，對(duì)圖片中背景與干擾線段取色，經(jīng)過(guò)多次實(shí)驗(yàn)設(shè)定閾值，將處于該閾值范圍內(nèi)像素點(diǎn)的值設(shè)為1，其余設(shè)為0，二值化結(jié)果如圖2所示。

圖2 二值化驗(yàn)證碼Fig.2 Binarization of CAPTCHA

1.2.2 數(shù)據(jù)去噪

從圖2可以明顯地看出，二值化后的數(shù)據(jù)仍包含一些噪聲點(diǎn)，將二值化后的數(shù)據(jù)中為0值的點(diǎn)取出，采用DBSCAN聚類方法將噪聲點(diǎn)刪去。DBSCAN[8](Density-Based Spatial Clustering of Applications with Noise)是一個(gè)典型的基于密度的聚類算法。其核心思想為：從某個(gè)選定的核心點(diǎn)出發(fā)，不斷向密度可達(dá)的區(qū)域擴(kuò)展，從而得到一個(gè)包含核心點(diǎn)和邊界點(diǎn)的最大區(qū)域，區(qū)域中任意兩點(diǎn)密度相連。與層次聚類方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，其優(yōu)點(diǎn)在于事先不用給定聚類的類數(shù)，同時(shí)也可以發(fā)現(xiàn)任意形狀的簇類，對(duì)于去除數(shù)據(jù)中的噪聲有很好效果。其步驟是，提取值為0的點(diǎn)的橫縱坐標(biāo)，做基于密度的聚類，將聚類結(jié)果中類別為0的點(diǎn)的值賦為1。DBSCAN聚類結(jié)果如圖3所示。

圖3 DBSCAN 聚類結(jié)果Fig.3 Results of DBSCAN cluster

圖3中cluster0即紅色圓點(diǎn)代表噪聲點(diǎn)，從圖中可以看出，四個(gè)字符的驗(yàn)證碼分為了三類，由于驗(yàn)證碼的粘連特征，用DBSCAN聚類可以有效地識(shí)別出噪聲，但是難以將字符完全劃分開(kāi)來(lái)，僅使用該方法進(jìn)行驗(yàn)證碼單字符的分割，其效果并不好。

1.3 圖像分割

為獲取單字符圖像數(shù)據(jù)，采用豎直投影法對(duì)驗(yàn)證碼圖像進(jìn)行分割。為使所獲得的圖像規(guī)模相同，將所有驗(yàn)證碼圖像二值化矩陣進(jìn)行列求和，并對(duì)列和求取均值，繪制圖4所示的線圖，在波谷處選取分割橫坐標(biāo)。因?yàn)檫M(jìn)行了去噪處理，分割效果較好。如圖4所示，將原驗(yàn)證碼圖像矩陣(70×20)分割為4個(gè)12×20的單字符圖像矩陣，其分割范圍分別為1～12，13～24，26～37，39～50。

圖4 驗(yàn)證碼圖像分割圖Fig.4 CAPTCHA segmentation

2 基于聚類方法的驗(yàn)證碼樣本標(biāo)注

為實(shí)現(xiàn)對(duì)驗(yàn)證碼識(shí)別，需要構(gòu)建帶有標(biāo)簽的訓(xùn)練樣本數(shù)據(jù)，而對(duì)驗(yàn)證碼進(jìn)行標(biāo)注需要大量人力，本文提出采用半監(jiān)督的聚類方法對(duì)無(wú)標(biāo)簽驗(yàn)證碼數(shù)據(jù)集進(jìn)行標(biāo)注。首先，人工標(biāo)注50個(gè)驗(yàn)證碼，即200個(gè)分割后的圖像樣本，并將標(biāo)注后的樣本與1000個(gè)未標(biāo)注的樣本進(jìn)行聚類，根據(jù)聚類結(jié)果進(jìn)行標(biāo)注。

2.1 Kmeans聚類

通過(guò)觀察，分割后的圖像僅包含1、2、3、n、m、v、c、b、z、x 十個(gè)類別，因此從標(biāo)注的樣本中隨機(jī)選取對(duì)應(yīng)類別的樣本作為聚類的初始中心，進(jìn)行Kmeans 聚類，其中1、2、3、v、c、b、z、x 的分類正確率為100%，而n 和m 的誤分率達(dá)到了50%以上，這是由于豎直投影法的分割方法，使得m 和n 的 樣本數(shù)據(jù)差異不大，這從相似系數(shù)的結(jié)果圖 5便可以看出。而且一般的Kmeans聚類為無(wú)監(jiān)督的方式，對(duì)已標(biāo)注數(shù)據(jù)的先驗(yàn)信息使用較少，因此本文提出了基于AdaBoost方法的半監(jiān)督Kmeans聚類算法，用少量標(biāo)注樣本的信息來(lái)改善聚類結(jié)果，并用于樣本的批量標(biāo)記。

圖5 各類別相似系數(shù)圖Fig.5 Correlation coefficients of all clusters

2.2 基于AdaBoost方法的半監(jiān)督Kmeans聚類

AdaBoost是一種集成學(xué)習(xí)方法，其基本思想是加權(quán)多數(shù)表決，加大分類誤差率小的弱分類器的權(quán)值，使其在表決中起較大作用，減小分類誤差率大的弱分類器的權(quán)值，使其在表決中起較小作用。

對(duì)于一個(gè)二分問(wèn)題：

輸入的訓(xùn)練數(shù)據(jù)集T={(x1,y1),(x2,y2),…，(xN,yN)}，xi∈χ?Rn,yi∈{-1,+1},最終輸出為G(x)。

AdaBoost 算法步驟如下：

2)對(duì)第m個(gè)弱分類器，m=1,2,…,M。

a.在權(quán)值Dm下訓(xùn)練數(shù)據(jù)集，得到弱分類器Gm(x):χ→{-1,+1}

b.計(jì)算Gm的訓(xùn)練誤差

c.計(jì)算Gm的系數(shù)

d.更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布

Dm+1=(wm+1,1,…,wm+1,i,…,wm+1,N)

3)得到最終分類器。

AdaBoost算法能夠在訓(xùn)練過(guò)程中不斷減小誤差，而對(duì)于無(wú)監(jiān)督聚類問(wèn)題來(lái)說(shuō)，誤差是難以度量的。在半監(jiān)督問(wèn)題中，可以使用帶有標(biāo)簽的部分樣本數(shù)據(jù)進(jìn)行誤差度量，并賦予標(biāo)簽數(shù)據(jù)新的權(quán)重進(jìn)行聚類。對(duì)類別數(shù)為2的Kmeans聚類，其算法步驟如下：

2)對(duì)第m次聚類，m=1,2,…，M。

b.計(jì)算Clusterm的誤差

em=P(Clusterm(xi)≠yi)=

c.計(jì)算Clusterm的系數(shù)

d.更新訓(xùn)練數(shù)據(jù)集Λ的權(quán)值分布

Dm+1=(wm+1,1,…，wm+1,i,…,wm+1,N)

3)得到最終聚類結(jié)果。

值得注意的是Kmeans 聚類并不能保證em的降低，只能將第m次聚類的劃分重心拉向錯(cuò)分的樣本點(diǎn)。因此，可能會(huì)出現(xiàn)em≥0.5的情況，在此時(shí)應(yīng)該停止迭代，或進(jìn)行修正。

使用基于AdaBoost方法的半監(jiān)督Kmeans聚類，對(duì)Kmeans無(wú)法分別的m與n類的數(shù)據(jù)重新進(jìn)行聚類，其在樣本集Λ上的誤分率僅為5.56%，整體誤分率為0.015%，相比較于傳統(tǒng)Kmeans算法51.8%的誤分率以及10%的整體誤分率有極大的改善。

3 驗(yàn)證碼識(shí)別

本部分采用聚類批量標(biāo)注過(guò)的1 200個(gè)單字符樣本作為訓(xùn)練數(shù)據(jù)，并對(duì)剩余的50個(gè)驗(yàn)證碼(200 個(gè)單字符)進(jìn)行人工標(biāo)注，將其作為測(cè)試數(shù)據(jù)。分別使用線性判別法Fisher判別分析(FDA)以及K近鄰(KNN)、支持向量機(jī)(SVM)、神經(jīng)網(wǎng)絡(luò)(NNET)、隨機(jī)森林(RF)等算法，在訓(xùn)練樣本上訓(xùn)練，并對(duì)測(cè)試集進(jìn)行識(shí)別，以對(duì)各算法的識(shí)別效果與適用性進(jìn)行比較。

由于驗(yàn)證碼圖像數(shù)據(jù)相關(guān)程度很高，且部分像素點(diǎn)值為常數(shù)，故導(dǎo)致協(xié)方差矩陣奇異，不能求逆，導(dǎo)致判別函數(shù)無(wú)法求解。為處理協(xié)方差陣奇異的問(wèn)題，可以更改優(yōu)化的目標(biāo)函數(shù)，從而利用優(yōu)化算法迭代求解；或是應(yīng)用主成分分析進(jìn)行降維處理，提取對(duì)驗(yàn)證碼識(shí)別影響較大的成分。本文采用的是主成分分析法進(jìn)行處理。

圖6 主成分碎石圖Fig.6 Scree plot of principal components

從圖6來(lái)看，當(dāng)主成分個(gè)數(shù)大于15，累積貢獻(xiàn)率大于80%，而特征值的減小也并不顯著，因此選取15 個(gè)主成分。

對(duì)降維后的數(shù)據(jù)實(shí)施Fisher判別，原始數(shù)據(jù)實(shí)施機(jī)器學(xué)習(xí)的算法，各種方法的識(shí)別效果見(jiàn)表1。

表1 各算法識(shí)別效果
Tab.1 Results of different algorithms

算法FDAKNNSVM線性核高斯核NNETRF正確率/%98.59293929393.5

所進(jìn)行判別的樣本數(shù)據(jù)空間χ={0，1}240，即Rn空間中以零點(diǎn)為頂點(diǎn)，邊長(zhǎng)為1 的方體的頂點(diǎn)，其數(shù)量為2240，而樣本類別僅有10類，所取得樣本數(shù)據(jù)僅占有樣本空間極少部分的頂點(diǎn)，在這種樣本數(shù)據(jù)極其稀疏情況下，樣本往往是線性可分的，即可以找到Rn中的超平面G，使得，G(x(s))*G(x(t))<0,x(s)、x(t)為類別為s、t的樣本數(shù)據(jù)。因此，F(xiàn)isher 線性判別方法取得了很好的效果，而SVM 方法中線性核的判別效果也好于非線性的高斯核。同時(shí)，由于訓(xùn)練樣本的標(biāo)注為聚類的結(jié)果，其中可能存在錯(cuò)誤標(biāo)記導(dǎo)致的異常數(shù)據(jù)的干擾，但是從判別的結(jié)果來(lái)看，F(xiàn)isher判別法在這種情形下，有更好的魯棒性，更加穩(wěn)健。

從表2 Fisher 判別的識(shí)別結(jié)果來(lái)看,即使采用簡(jiǎn)單的豎直投影分割方法，識(shí)別依然有較高的正確率，而這也反映出使用半監(jiān)督Kmeans聚類進(jìn)行訓(xùn)練樣本標(biāo)記的正確率較高。當(dāng)然，識(shí)別的高準(zhǔn)確率也表明驗(yàn)證碼并不安全。

表2 Fisher 判別結(jié)果
Tab.2 Results of Fisher discrimination analysis

原始圖像識(shí)別結(jié)果原始圖像識(shí)別結(jié)果nnxvb2v2xvnzvzvb11nbxnbnx2bxvnzmz2bbzzzxnbcvncnc3v3cccb2cnvzx2czvn2vx1b1m2v23113

這種驗(yàn)證碼并不是一種很好的驗(yàn)證碼形式,這不僅體現(xiàn)在其能被較高的識(shí)別率破解,還因?yàn)樗挠脩趔w驗(yàn)較差。觀察驗(yàn)證碼圖片,部分m、n粘連的字符即使人眼都難以區(qū)分。這些字符的形狀從圖片上來(lái)看大都相像,人類都很難辨別,而最終識(shí)別錯(cuò)誤的大都是這些難以辨別的字符。

4 結(jié)束語(yǔ)

針對(duì)網(wǎng)站上的驗(yàn)證碼數(shù)據(jù)，采用 DBSCAN 與豎直投影法對(duì)驗(yàn)證碼圖像進(jìn)行去噪與分割處理，具有很好去噪聲效果，而分割后的圖像也易于識(shí)別。對(duì)于分割后的單個(gè)字符圖像的樣本批量標(biāo)注問(wèn)題，提出了基于AdaBoost方法半監(jiān)督Kmeans聚類算法，該算法的標(biāo)注結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)Kmeans方法的，在樣本標(biāo)注上極大節(jié)約了人力成本，具有理論與現(xiàn)實(shí)意義。在驗(yàn)證碼的識(shí)別效果上，比較了經(jīng)典的Fisher判別與隨機(jī)森林、K近鄰、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等機(jī)器學(xué)習(xí)方法的識(shí)別效果。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，這些方法都有較高的單字符識(shí)別正確率，而Fisher判別的正確率最高，可以認(rèn)為在這種線性可分的數(shù)據(jù)集下，經(jīng)典的多元統(tǒng)計(jì)方法Fisher判別可能比機(jī)器學(xué)習(xí)方法更為適合。而所識(shí)別的網(wǎng)站的驗(yàn)證碼并不完善，其在安全性和用戶體驗(yàn)上都較差，亟待改善。