基于廣義霍夫變換的粘連字符驗(yàn)證碼的識(shí)別

汪志華

(集美大學(xué)計(jì)算機(jī)工程學(xué)院，福建 廈門 361021)

0 引言

驗(yàn)證碼最初是一種用于區(qū)分用戶是計(jì)算機(jī)還是人的測試程序，它通過生成測試并對(duì)用戶作答進(jìn)行評(píng)判,后來，逐漸發(fā)展成為網(wǎng)站防范攻擊的一種安全技術(shù)而受到廣泛的應(yīng)用。按照內(nèi)容劃分，驗(yàn)證碼主要分為字符驗(yàn)證碼、圖像驗(yàn)證碼、聲音驗(yàn)證碼等。字符驗(yàn)證碼具有生成成本低、答案比較確定、對(duì)用戶友好等優(yōu)點(diǎn)，目前被大多數(shù)網(wǎng)站采用。由于普通字符驗(yàn)證碼容易被程序自動(dòng)識(shí)別，為提高網(wǎng)站安全性，在生成字符驗(yàn)證碼時(shí)，可以通過增加干擾線條、扭曲字符、粘連字符、旋轉(zhuǎn)字符、混合不同字體的字符等方法，增大驗(yàn)證碼自動(dòng)識(shí)別的難度。本文研究的對(duì)象即為此類具有粘連字符、旋轉(zhuǎn)字符的驗(yàn)證碼。

粘連字符驗(yàn)證碼的識(shí)別難度較大，對(duì)于粘連字符驗(yàn)證碼的識(shí)別，大多數(shù)研究者主要采用字符分割、特征提取、字符識(shí)別等流程。如：王璐等[1]基于局部極小值和最小投影值的方法來分割字符，然后采用卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練和識(shí)別，但對(duì)于粘連字符驗(yàn)證碼的識(shí)別率只有38%；張亮等[2]采用水平和垂直投影進(jìn)行字符分割，然后通過遞歸神經(jīng)網(wǎng)絡(luò)進(jìn)行識(shí)別，對(duì)不同測試集識(shí)別率在20%～60%之間；唐海濤[3]提出一種基于PNN-SOINN-RBF網(wǎng)絡(luò)構(gòu)建的自組織增量神經(jīng)網(wǎng)絡(luò)模型對(duì)驗(yàn)證碼進(jìn)行識(shí)別，該方法的識(shí)別率在60%～85%之間，對(duì)于一些測試集可以達(dá)到95%；汪洋等[4]采用輪廓差投影法與水滴算法對(duì)驗(yàn)證碼進(jìn)行字符切割，然后利用KNN算法進(jìn)行字符識(shí)別，識(shí)別率為81%；陳以山等[5]利用傳統(tǒng)的數(shù)字圖像形態(tài)學(xué)處理技術(shù)對(duì)可分割字符的驗(yàn)證碼進(jìn)行識(shí)別，識(shí)別率約為60%；尹龍等[6]提出基于密集尺度不變特征變換和隨機(jī)抽樣一致性算法的識(shí)別方法，能夠較好地處理一般性的粘連字符，其識(shí)別率為88%，并對(duì)于扭曲粘連較嚴(yán)重的驗(yàn)證碼也取得了一定的實(shí)驗(yàn)成果；Wang Ye等[7]提出基于自適應(yīng)的算法來對(duì)驗(yàn)證碼圖像進(jìn)行去噪和分割，并利用OCR和模板匹配的方法來識(shí)別分割后的字符；Garg Geetika等[8]利用CNN和RNN組建深度神經(jīng)網(wǎng)絡(luò)來對(duì)文本驗(yàn)證碼進(jìn)行識(shí)別，對(duì)于字符數(shù)確定和不確定的驗(yàn)證碼識(shí)別率分別達(dá)到99.8%和81%。

驗(yàn)證碼的識(shí)別需要綜合數(shù)字圖像處理、機(jī)器學(xué)習(xí)、人工智能等學(xué)科知識(shí)。研究驗(yàn)證碼的識(shí)別可以發(fā)現(xiàn)驗(yàn)證碼設(shè)計(jì)的漏洞，有助于改進(jìn)驗(yàn)證碼的設(shè)計(jì)，提高網(wǎng)站的安全性，防范惡意批量操作和暴力破解數(shù)據(jù)庫等行為。同時(shí)驗(yàn)證碼的識(shí)別技術(shù)也可以用于車牌識(shí)別、光學(xué)字符識(shí)別、手寫字識(shí)別等領(lǐng)域。目前大部分識(shí)別方法對(duì)于可分割的驗(yàn)證碼識(shí)別效果較好，但在處理粘連字符時(shí)由于無法準(zhǔn)確地進(jìn)行字符分割，使系統(tǒng)的識(shí)別正確率受到影響。因此，研究驗(yàn)證碼的識(shí)別特別是粘連字符驗(yàn)證碼的識(shí)別具有一定的理論和實(shí)踐意義。

1 基于廣義霍夫變換的驗(yàn)證碼識(shí)別

本文提出一種基于廣義霍夫變換(generalized Hough transform,GHT)的識(shí)別方法。首先將驗(yàn)證碼圖片和模板圖像進(jìn)行預(yù)處理和骨架化，對(duì)模板圖像中的圖像邊緣像素點(diǎn)提取兩個(gè)局部特征(重心夾角和重心距離)作為參考表中的內(nèi)容，再對(duì)驗(yàn)證碼圖片中的每個(gè)像素根據(jù)其與參考表的匹配情況進(jìn)行投票，從而確定驗(yàn)證碼中是否存在模板圖像，進(jìn)而達(dá)到字符識(shí)別的目的，最后通過干擾分析，來剔除形狀類似的字符對(duì)識(shí)別結(jié)果的干擾。系統(tǒng)的識(shí)別結(jié)構(gòu)如圖1所示。

圖1 驗(yàn)證碼識(shí)別結(jié)構(gòu)圖

1.1 預(yù)處理

驗(yàn)證碼圖片一般為彩色圖像，為降低計(jì)算復(fù)雜度，需要將其灰度化，并轉(zhuǎn)換成二值圖像進(jìn)行處理?；叶然D(zhuǎn)換公式為Y=0.3R+0.59G+0.11B。圖像轉(zhuǎn)換成灰度圖后，采用最大類間方差法(Otsu)將圖像分為前景和背景兩部分。在Otsu算法中用類間方差作為標(biāo)準(zhǔn)來衡量前景和背景，類間方差越大，說明兩者的差別就越大，錯(cuò)分的概率也就越小[9]。設(shè)圖像的總像素?cái)?shù)為N，前景的像素點(diǎn)數(shù)為N0，前景所占總像素的比例為P0，且P0=N0/N，前景的平均灰度值為U0，背景的像素點(diǎn)數(shù)為N1，背景所占總像素的比例為P1，且P1=N1/N，背景的平均灰度值為U1，則圖像的總體平均灰度值U=P0U0+P1U1，類間方差δ2=P0(U-U0)2+P1(U-U1)2。因此，分割閾值T就是使得δ2取得最大值的閾值。圖像預(yù)處理的結(jié)果如圖2所示。

1.2 骨架化

骨架由曲線及弧線構(gòu)成，它是物體的中軸，是對(duì)物體形狀特征的一個(gè)描述方法。骨架一般寬度為單個(gè)像素，它接近圖像的位置中心，對(duì)邊緣噪聲不敏感，可以表達(dá)出人對(duì)物體形狀描述的視覺特征。本文采用Zhang快速并行細(xì)化算法[10]來尋找字符的骨架，該算法具有運(yùn)算速度快，細(xì)化后的曲線保持連通性等優(yōu)點(diǎn)。

設(shè)二值圖像中，目標(biāo)點(diǎn)標(biāo)記為1，背景點(diǎn)標(biāo)記為0，則定義邊界點(diǎn)標(biāo)記為1且其8-連通鄰域中至少有1個(gè)標(biāo)記為0的點(diǎn)。圖3所示為二值圖像中像素P1的8-連通鄰域。

算法對(duì)邊界點(diǎn)進(jìn)行以下兩次迭代[10]：

大渡河長河壩礫石土心墻堆石壩壩高240 m，建于覆蓋層最大厚度79.3 m的地基上，處于高地震烈度區(qū)，100年超越概率2%基巖水平峰值加速度為0.359 g。該工程采用兩道全封閉混凝土防滲墻，在主防滲墻頂設(shè)置了城門洞型式的廊道與心墻連接，如圖1(a)、圖1(b)所示，廊道內(nèi)部尺寸3 m×4 m，側(cè)墻厚2 m，底板厚3 m。該廊道在河床段沿縱向不設(shè)結(jié)構(gòu)縫，原設(shè)計(jì)在基巖覆蓋層分界線處分縫與兩岸灌漿平洞連接，但采用類似結(jié)構(gòu)的蹺磧及瀑布溝等工程均出現(xiàn)了廊道開裂及止水破壞的現(xiàn)象[3-4]。經(jīng)深入研究后，壩基廊道改為深入基巖1 m與兩岸灌漿平洞有縫連接[5]，如圖1(c)所示。

1)第一次迭代，若P1滿足下列4個(gè)條件，則進(jìn)行標(biāo)記。①2≤N(P1)≤6，N(P1)表示P1非0鄰點(diǎn)的個(gè)數(shù)；②S(P1)=1，S(P1)表示按P2,P3,…,P9排列時(shí)，出現(xiàn)01模式的個(gè)數(shù)；③P2×P4×P6=0；④P4×P6×P8=0。當(dāng)?shù)瓿珊螅宄袠?biāo)記了的點(diǎn)。

2)第二次迭代，標(biāo)記滿足條件的點(diǎn)P1。P1也需要滿足4個(gè)條件，前兩個(gè)條件即第一次迭代的條件①和條件②，第三個(gè)條件為P2×P4×P8=0，第四個(gè)條件為P2×P6×P8=0。當(dāng)?shù)瓿珊?，清除所有?biāo)記了的點(diǎn)。

重復(fù)上面兩次迭代，直到?jīng)]有點(diǎn)滿足標(biāo)記條件，則剩下的點(diǎn)就是目標(biāo)的骨架。對(duì)圖2c應(yīng)用Zhang快速并行細(xì)化算法[10]進(jìn)行處理的效果如圖4所示。

1.3 廣義霍夫變換

當(dāng)圖像被處理成骨架后，可以把字符看成具有一定形狀的物體，因而可以通過廣義霍夫變換來搜索在驗(yàn)證碼圖片中是否出現(xiàn)了某個(gè)字符及其出現(xiàn)的位置。

1.3.1 廣義霍夫變換的原理

在廣義霍夫變換[11]中，任意形狀可以定義為：

ω(θ,b,λ,ρ)=b+λR(ρ)ν(θ),

(1)

其中：ν表示模板的曲線定義，b=(x0,y0)是平移向量，λ是尺度因子，R(ρ)是旋轉(zhuǎn)矩陣。因此，形狀的位置由式(2)給出：

b=ω(θ)-λR(ρ)ν(θ)，

(2)

假設(shè)稱ωi=(ωxi，ωyi)為圖像上的點(diǎn)，那么：

b=ωi-λR(ρ)ν(θ),

(3)

式(3)定義了1個(gè)具有4個(gè)未知量的方程系統(tǒng)，將圖像點(diǎn)映射到累加器空間，通過檢查圖像點(diǎn)與模板圖像的特征是否匹配，從而收集獲得目標(biāo)形狀的證據(jù)。

廣義霍夫變換的幾何定義如圖5所示，其映射函數(shù)的極坐標(biāo)方程可以表示為：

b=ω(θ)-reα，

(4)

其中，Φ(θ)=arctan(y(θ)/x(θ))，α=Φ(θ)+ρ，r=λΓ(θ)，Γ(θ)=sqrt(x(θ)×x(θ)+y(θ)×y(θ))。

1.3.2 模板圖像的R-表結(jié)構(gòu)

由于模板圖像為任意的形狀，沒有簡單的曲線方程能夠描述，在廣義霍夫變換中采用了建立R-表(參考表)來描述參考點(diǎn)和邊緣點(diǎn)的關(guān)系。本文選取模板字符的重心作為參考點(diǎn)，將邊緣像素點(diǎn)的重心夾角和重心距離記錄到參考表中。重心夾角指模板圖像邊緣像素點(diǎn)與模板圖像重心連線形成的向量的方向角，即圖5中的α。重心距離指模板圖像邊緣像素點(diǎn)與模板圖像重心之間的距離，即圖5中的r。重心夾角與重心距離具有平移和旋轉(zhuǎn)的不變性，但不具有尺度不變性，因此選取的特征無法處理縮放字符的識(shí)別。參考表的結(jié)構(gòu)如表1所示。

表1 參考表的結(jié)構(gòu)Tab．1 StructureofR?table重心夾角Angleofthegravitycenter重心距離DistancetothegravitycenterΔθr11，r12，…，r1n12Δθr21，r22，…，r2n2??mΔθrm1，rm2，…，rmnm

1.3.3 證據(jù)收集算法

對(duì)骨架化后的驗(yàn)證碼圖像上的目標(biāo)像素點(diǎn)，根據(jù)模板圖像的R-表進(jìn)行評(píng)價(jià)，得到參考點(diǎn)的坐標(biāo)，然后對(duì)累加器數(shù)組進(jìn)行累加投票，最后將投票的極大值輸出即得該模板圖像的參考點(diǎn)(重心)位置。 設(shè)骨架化后的驗(yàn)證碼圖像和模板圖像記為I和Q，I的大小為M×N，Q的參考表記為RTable，重心夾角記為A，投票累加器數(shù)組記為a，大小為M×N，累加器閾值記為T，該閾值表示在I中與Q相似的目標(biāo)點(diǎn)數(shù)量的最小值，如果累加器的數(shù)值超過此閾值，可以認(rèn)為在I中存在Q。證據(jù)收集的算法如下：

1) 順序取出模板圖像Q以及它的參考表RTable；

2) 投票累加器數(shù)組a清零；

3) 對(duì)驗(yàn)證碼圖像I中的所有目標(biāo)點(diǎn)(x,y)，遍歷所有的重心夾角A(0≤A<2π，增量為Δθ)，計(jì)算參考點(diǎn)的坐標(biāo)(x0,y0)；

4) 如果(x0,y0)合法，則a[x0,y0]增1；

5) 掃描累加器數(shù)組，如果a[i,j]為極大值，且a[i,j]≥T，則(i,j)即為模板圖像Q的重心，輸出該模板對(duì)應(yīng)的字符、重心坐標(biāo)(i,j)以及投票累加器的值a[i,j]。

基于廣義霍夫變換對(duì)驗(yàn)證碼圖像進(jìn)行檢索的結(jié)果如圖6所示。圖6a為骨架化后的驗(yàn)證碼圖像，圖6b為骨架化后字符模板圖像，圖6c為使用模板圖像在驗(yàn)證碼圖像中進(jìn)行檢索后得到的投票累加器，該累加器在(27,16)具有極大值且累加器的數(shù)值大于閾值T，說明在驗(yàn)證碼中出現(xiàn)了字符E，且重心坐標(biāo)為(27,16)。

1.4 干擾分析

由于字符之間的相似性，在驗(yàn)證碼圖像中檢索目標(biāo)字符時(shí)會(huì)產(chǎn)生重復(fù)識(shí)別的情況。例如，如果驗(yàn)證碼中含有字母“B”，則廣義霍夫變換也會(huì)檢測出字母“P”，因此需要對(duì)這種相似性導(dǎo)致的識(shí)別干擾進(jìn)行排除。當(dāng)兩個(gè)字符的距離很近時(shí)，這時(shí)就出現(xiàn)了干擾，此時(shí)需判斷兩者的累加器數(shù)值，累加器數(shù)值大的獲勝，因?yàn)檫@意味著有更多的目標(biāo)點(diǎn)類似于該模板圖像。

干擾分析的算法如下：

1)將廣義霍夫變換識(shí)別的結(jié)果按照重心x坐標(biāo)從小到大排列。

2)遍歷上述數(shù)組，如果某字符c1與緊鄰的字符c2重心之間的橫向距離d=|x1-x2|

3)按重心x坐標(biāo)從小到大輸出對(duì)應(yīng)的字符，此即為驗(yàn)證碼識(shí)別結(jié)果。

2 實(shí)驗(yàn)結(jié)果

本文采用自主測試集，測試集包括200張驗(yàn)證碼圖像，圖像中以英文大寫字母和數(shù)字0～9為字符集，每個(gè)圖片包含4個(gè)字符，每個(gè)字符隨機(jī)旋轉(zhuǎn)1個(gè)角度，旋轉(zhuǎn)角度介于-40°到+40°之間，每個(gè)字符顏色隨機(jī)。部分識(shí)別結(jié)果如表2所示，其中字符的下劃線表示該字符識(shí)別錯(cuò)誤。

表2 部分識(shí)別結(jié)果

從實(shí)驗(yàn)結(jié)果來看，本文提出的方法能夠正確識(shí)別具有字符旋轉(zhuǎn)、字符輕微粘連的驗(yàn)證碼，但如果字符粘連嚴(yán)重，則鄰近字符的干擾增大，導(dǎo)致識(shí)別正確率下降。由于在GHT中，需要對(duì)驗(yàn)證碼圖像中的所有目標(biāo)點(diǎn)根據(jù)公式(4)計(jì)算參考點(diǎn)的坐標(biāo)，如果字符粘連嚴(yán)重，則相鄰的目標(biāo)像素就會(huì)對(duì)累加器數(shù)組進(jìn)行累加計(jì)數(shù)，影響正確的參考點(diǎn)的坐標(biāo)，從而導(dǎo)致字符的識(shí)別錯(cuò)誤。

表3 識(shí)別效果對(duì)比Tab．3 Comparisonofrecognitionresults識(shí)別算法Recognitionalgorithm正確識(shí)別數(shù)量/個(gè)Numberofcorrectrecognition識(shí)別率/%Recognitionrate等間距分割Equidistantsegmentation2311．5最大類間方差Otsu4824．0本文方法Thismethod17386．5

作為對(duì)比，本文選用等間距字符分割法和最大類間方差法兩種傳統(tǒng)的字符分割方法與本文方法一起對(duì)驗(yàn)證碼圖像進(jìn)行分割，再用ABBYY FineReader OCR軟件來識(shí)別分割后的字符。實(shí)驗(yàn)對(duì)比結(jié)果如表3所示，其中測試集為200張驗(yàn)證碼圖像。從結(jié)果可以看出，傳統(tǒng)方法的實(shí)驗(yàn)識(shí)別率較低，原因主要有3點(diǎn)：1)由于驗(yàn)證碼中的每個(gè)字符都有1個(gè)隨機(jī)的旋轉(zhuǎn)變換(旋轉(zhuǎn)角度-40°～+40°)，經(jīng)過等間距分割或類間最大方差分割后，沒有對(duì)字符進(jìn)行傾斜糾正，而直接由該OCR軟件識(shí)別，因此識(shí)別率較低；2)由于驗(yàn)證碼中字符的旋轉(zhuǎn)導(dǎo)致一些字符粘連在一起，無論等間距分割或類間最大方差分割都無法將字符正確分割開，因而導(dǎo)致該OCR軟件無法正確識(shí)別；3)驗(yàn)證碼的識(shí)別是需要將圖片中4個(gè)字符都成功識(shí)別，才算成功，只要有1個(gè)字符識(shí)別錯(cuò)誤，則判定為錯(cuò)誤。如果字符正確地進(jìn)行了分割，該OCR軟件對(duì)單個(gè)字符的識(shí)別率可以達(dá)到90%以上，但對(duì)僅輕微旋轉(zhuǎn)或受擾的字符的正確識(shí)別率大概只有50%～75%。在驗(yàn)證碼分割中由于字符的粘連，總有個(gè)別字符識(shí)別效果很差，從而使得整體的識(shí)別率非常低。因此傳統(tǒng)字符分割再識(shí)別的方法無法適應(yīng)粘連字符驗(yàn)證碼的識(shí)別，而本文方法則比較有效。

3 結(jié)束語

針對(duì)粘連字符驗(yàn)證碼，本文提出了一種基于廣義霍夫變換的識(shí)別方法，該方法通過對(duì)字符模板和驗(yàn)證碼圖片進(jìn)行二值化和骨架化，通過對(duì)字符模板的每個(gè)目標(biāo)點(diǎn)像素抽取局部特征建立參考表。對(duì)于驗(yàn)證碼圖片，采用像素逐點(diǎn)匹配和投票的方式進(jìn)行廣義霍夫變換，最后對(duì)相鄰字符間的干擾進(jìn)行分析，排除干擾字符。由于采取重心夾角和重心距離等局部特征具有平移和旋轉(zhuǎn)不變性，因此本算法能夠處理字符局部形變和字符旋轉(zhuǎn)。并且廣義霍夫變換不需要對(duì)驗(yàn)證碼圖片進(jìn)行分割，它能夠適應(yīng)并有效處理字符輕度粘連的情況，具有一定的抗干擾性。但本算法中選擇的局部特征不具備尺度不變性，因此本方法不適用于字符具有縮放、形變或粘連嚴(yán)重的驗(yàn)證碼識(shí)別。

[1]王璐,張榮,尹東,等.粘連字符的圖片驗(yàn)證碼識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(28):150-153.

[2]張亮,黃曙光,石昭祥,等.基于LSTM型RNN 的CAPTCHA識(shí)別方法[J].模式識(shí)別與人工智能,2011,24(1):40-47.

[3]唐海濤.自組織增量神經(jīng)網(wǎng)絡(luò)的驗(yàn)證碼識(shí)別模型與算法[D].廣州: 廣東工業(yè)大學(xué),2016.

[4]汪洋,許映秋,彭艷兵.基于KNN 技術(shù)的校內(nèi)網(wǎng)驗(yàn)證碼識(shí)別[J].計(jì)算機(jī)與現(xiàn)代化,2017(2):93-97.

[5]陳以山,張勇.基于字符的圖片驗(yàn)證碼識(shí)別算法的設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù),2017,13(1):190-192.

[6]尹龍,尹東,張榮,等.一種扭曲粘連字符驗(yàn)證碼識(shí)別方法[J].模式識(shí)別與人工智能，2014,27(3):235-241.

[7]WANG YE,LU MI.A self-adaptive algorithm to defeat text-based CAPTCHA[C]//2016 IEEE International Conference on Industrial Technology.Taipei:IEEE,2016:720-725.DOI:10.1109/ICIT.2016.7474839.

[8]GARG GEETIKA,POLLETT CHRIS.Neural network CAPTCHA crackers[J].IEEE Conference Proceedings,2016,FCT:853-861.

[9]瞿中.基于改進(jìn)的最大類間方差算法的圖像分割研究[J].計(jì)算機(jī)科學(xué),2009,36(5):276-278.

[10]章毓晉.圖像工程：中冊(cè) 圖像分析[M].2版.北京：清華大學(xué)出版社,2005:222-223.

[11]MARK S NIXON,ALBERTO S AGUADO.特征提取與圖像處理[M].2版.李實(shí)英，楊高波,譯.北京:電子工業(yè)出版社,2010:179-185.