虞水磊，田新宇，王金燕

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

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

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

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

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

圖1 未處理驗證碼Fig.1 Unprocessed CAPTCHA

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

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

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

圖2 二值化驗證碼Fig.2 Binarization of CAPTCHA

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

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

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

圖3中cluster0即紅色圓點代表噪聲點，從圖中可以看出，四個字符的驗證碼分為了三類，由于驗證碼的粘連特征，用DBSCAN聚類可以有效地識別出噪聲，但是難以將字符完全劃分開來，僅使用該方法進行驗證碼單字符的分割，其效果并不好。

1.3 圖像分割

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

圖4 驗證碼圖像分割圖Fig.4 CAPTCHA segmentation

2 基于聚類方法的驗證碼樣本標注

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

2.1 Kmeans聚類

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

圖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)值，使其在表決中起較小作用。

對于一個二分問題：

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

AdaBoost 算法步驟如下：

2)對第m個弱分類器，m=1,2,…,M。

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

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

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

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

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

3)得到最終分類器。

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

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

b.計算Clusterm的誤差

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

c.計算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次聚類的劃分重心拉向錯分的樣本點。因此，可能會出現(xiàn)em≥0.5的情況，在此時應(yīng)該停止迭代，或進行修正。

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

3 驗證碼識別

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

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

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

從圖6來看，當主成分個數(shù)大于15，累積貢獻率大于80%，而特征值的減小也并不顯著，因此選取15 個主成分。

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

表1 各算法識別效果
Tab.1 Results of different algorithms

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

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

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

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

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

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

4 結(jié)束語

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