基于形狀上下文的復雜驗證碼識別算法-

1、基于形狀上下文的復雜驗證碼識別算法賀 強,晏 立(江蘇大學計算機科學與通信工程學院,江蘇 鎮(zhèn)江 212013摘 要:使用改進的形狀上下文方法對復雜驗證碼進行識別,采用整體識別方法,不對圖片進行切割,使用半極坐標圓進行建模的方式,解決2個字符連接處像素點建模互相干擾的問題。設計并實現(xiàn)復雜驗證碼識別算法,并與簡單驗證碼進行比較。實驗結果證明,復雜驗證碼識別算法能對字符粘連的復雜驗證碼進行識別。 關鍵詞:驗證碼;形狀上下文;整體識別Recognition Algorithm of Complicated CAPTCHABased on Shape ContextHE Qiang, YAN Li(Sc

2、hool of Computer Science and Communication Engineering, Jiangsu University, Zhenjiang 212013, China計 算 機 工 程 Computer Engineering 第37卷 第2期V ol.37 No.2 2011年1月January 2011·人工智能及識別技術· 文章編號:10003428(201102020003文獻標識碼:A中圖分類號:TP391.411 概述驗證碼技術已經(jīng)廣泛應用于互聯(lián)網(wǎng),用以防止網(wǎng)絡上的惡意攻擊。由于網(wǎng)絡攻擊不斷增加,驗證碼技術也在快速改進,由以前單一

3、固定數(shù)字到現(xiàn)在粘連扭曲的字符,使攻擊者更難實現(xiàn)程序自動識別。國內(nèi)外越來越多的學者對驗證碼的設計和識別進行了研究。文獻1提出一種高效的驗證碼識別技術,能處理比較復雜的驗證碼圖片,并對驗證碼進行了分類。文獻2將形狀上下文方法用于驗證碼識別,提出了將樣本字符匹配測試字符的方法。文獻3運用統(tǒng)計學方法,提出一種加權模板匹配算法,得到了很高的識別率。但是,上述文獻研究的驗證碼都屬于簡單驗證碼,這種驗證碼的共同點是能夠對圖片上的字符進行切割,得到單個字符,然后進行匹配識別。本文研究的對象是復雜驗證碼,此類驗證碼字符粘連且有一定扭曲,沒有有效的算法能夠準確切割出單個字符,所以很難進行識別。本文提出一種形狀上下

4、文的改進方法,采用不對圖片進行切割,整體識別的方法,使用單像素跟蹤算法獲取字符的輪廓,有效減少了像素點數(shù)目,降低了形狀上下文描述的復雜度,采用半圓形式的對數(shù)極坐標建模,解決了2個字符粘連處字符建模時互相干擾的問題,準確地描述出字符特征,實現(xiàn)了對字符粘連復雜驗證碼的識別。2 基于改進形狀上下文方法的復雜驗證碼識別根據(jù)分割和識別的難易,本文將驗證碼分為以下3種:(1字符沒有粘連。這類驗證碼人和計算機程序都比較容易識別,只要有足夠多的樣本數(shù)量,識別率都能接近于100%。(2字符粘連且輕度扭曲。這類驗證碼人很容易識別,但是計算機程序比較難識別,是現(xiàn)在網(wǎng)絡上使用比較多的一種驗證碼。(3字符粘連且極度扭曲

5、。這種驗證碼人和計算機程序都很難識別。用戶體驗性比較差,國內(nèi)網(wǎng)站很少用。定義14 形狀上下文是以有限點集來表示待匹配的物體,并假設這些物體內(nèi)部或者表面輪廓上的離散點足以表征該物體的形狀信息。這些點能夠用邊界檢測器來檢測邊緣像素的位置而得到,p=p 1, p 2,p n 。這些點不需要是特殊點,比如曲率最大、變形點等,只要求這些點盡可能均勻一致分布在物體的邊緣上。本文以第(2類字符粘連的驗證碼為例進行復雜驗證碼識別。2.1 單像素輪廓的提取首先對驗證碼圖片進行預處理。預處理一般包括灰度化、二值化、平滑、去噪等。灰度化處理是指把含有亮度和色彩的彩色圖像變換成灰度圖像的過程。這里采用的是加權平均值法

6、,利用Grey =0.29×red +0.587×green +0.114×blue 算出每個像素的灰度值Grey 。根據(jù)灰度圖片的Grey 值進行二值化處理,將灰度圖轉化為黑白兩色圖。取128作為閾值,根據(jù)計算得到的Grey 值,值大于128的像素點RGB 值設置為(255, 255, 255,而值小于128的像素點設置為(0, 0, 0。示例圖片背景簡單,沒有噪點,二值化完成后就得到了基金項目:國家科技型中小企業(yè)技術創(chuàng)新基金資助項目(09C26213 203797作者簡介:賀 強(1984-,男,碩士研究生,主研方向:模式識別,圖像處理;晏 立,教授第37卷第

7、2期賀強,晏立:基于形狀上下文的復雜驗證碼識別算法 201預處理后的圖片,如圖1所示。 (a原圖 (b二值化圖 (c單像素輪廓圖圖1 預處理和取單像素輪廓效果如果直接對預處理后圖片進行形狀上下文的建模,算法的時間開銷非常大。根據(jù)定義1可以知道,只需要對字符輪廓像素點進行建模,就足夠描述出字符的特征。為減小算法復雜度,這里只對字符的輪廓點進行形狀上下文描述,舍去字符上的非輪廓點。定義2圍繞該區(qū)域生成的、區(qū)域中所有像素均在其內(nèi)部的區(qū)域輪廓,稱為區(qū)域外邊界。定義3 圍繞該區(qū)域生成的、區(qū)域中所有像素均在其外部的區(qū)域輪廓,稱為區(qū)域內(nèi)邊界。根據(jù)定義2和定義3,要分別獲取字符的外邊界和內(nèi)邊界。有的字符只有外

8、邊界,而有的字符包括外邊界和內(nèi)邊界。本文參考文獻5提出的輪廓跟蹤算法,并針對驗證碼字符特征,進行了一些改進。示例驗證碼圖片上4個字符都兩兩粘連,對于外部輪廓,只需使用帶標記信息的輪廓跟蹤算法進行獲取。從圖片左上角開始掃描,由上到下,由左至右找到第1個黑色像素點,設置為外部邊界的開始點,使用約定符號(0, 1, 2, 3, 4, 5, 6, 7對該點的8個相鄰像素點進行標號。用0和1分別表示該邊界像素點沒有被搜索和已經(jīng)被搜索。從外邊界開始點開始搜索,先找到標號的8個相鄰像素點中一個沒有被搜索的黑色像素點,并且該像素點的相鄰一個像素點為白色,即為下一個開始搜索的輪廓像素點,將該點的標記信息設置為1

9、,從該點開始接著找相鄰的未搜索過的邊界像素點。以此類推可以得到一個封閉的回路,直到搜索到第一個被標記的邊界像素點。便得到了4個字符的整個外部邊界。有的字符還有內(nèi)邊界,需要對圖片從左到右,從上到下再掃描一遍。從圖片上方到下方掃描像素點時,找到第1個有梯度變化,并且沒有被標記的黑色像素點,即為內(nèi)邊界的開始點,掃描一遍后可以得到所有內(nèi)邊界的開始點,然后使用帶標記的輪廓跟蹤算法進行處理,得到每一個內(nèi)邊界。如果沒有搜索到內(nèi)邊界的開始點,即表示驗證碼上的4個字符都沒有內(nèi)邊界。得到所有的內(nèi)邊界后,就可以得到單像素表示的字符輪廓圖。圖1中字符6有內(nèi)輪廓,而另外3個字符沒有內(nèi)輪廓。2.2 基于半極坐標圓建模的樣

10、本字符制作形狀上下文采用對數(shù)極坐標圓描述圓心像素點的特征,描述出該像素點與周圍像素點的相對分布角度與距離。然而對于字符粘連的驗證碼字符,2個字符粘連處的像素點在使用對數(shù)極坐標圓建模時,會受到另一個字符像素點的干擾,而不能準確描述出目標像素點的形狀上下文特征。為了解決兩字符粘連處像素點建?；ハ喔蓴_的問題,本文提出了半極坐標圓建模的形狀上下文方法。在制作樣本時,由于沒有算法能夠對驗證碼上字符進行自動切割,只能手工切割字符進行樣本的制作。先從單像素輪廓圖上手工切割出單個字符,然后進行特征值的提取。樣本特征值提取采用了形狀上下文方法,對每個輪廓像素點進行半極坐標圓建模。一般圖像中像素的位置可以用笛卡爾

11、坐標表示為(x, y,也可以用極坐標表示為(r,。設圓心的坐標為(x0, y0,相對于圓心坐標,圖像中其他任意一點坐標值設為(x, y,則笛卡爾坐標系轉換到極坐標系的變換過程如下: arctan(y yrx x=取坐標原點(x0, y0為(0, 0,其用復數(shù)z表示為:jz j(cos jsinex y r r=+=+=令=lnz=ln r+j,則笛卡爾坐標轉換為對數(shù)極坐標的映射方程為p(r,=ln r,q(r, =。本文的對數(shù)極坐標值被劃分為8份,而r值被劃分為3份,值取-90°90°或90°270°的半極坐標圓進行建模。這樣可以得到一個4×3

12、的矩陣。相對于坐標原點(x0, y0,根據(jù)坐標(x,y的r和值可以判定該點位于哪一個格內(nèi)。取字符寬度的一半作為對數(shù)極坐標圓的半徑值,字符左半邊的像素點只編碼右半圓的值,而右半邊的像素點只編碼左半圓的值,這樣處理有利于進行后面的字符整體識別。建模的示例如圖2所示,字符6一共有像素點115個,每個像素點都可以編碼成這樣的一個4×3的矩陣,而得到一個描述非常豐富的樣本。 圖2 半極坐標圓建模過程2.3 字符整體識別在樣本足夠多以后,就可以實現(xiàn)程序的自動識別。識別過程中不對測試驗證碼圖片進行切割,以樣本的每個字符作為匹配源字符,將樣本的每個字符到圖片上去比對,以該樣本的寬度作為直徑,對圖片上

13、的每個像素點進行左右半圓的形狀上下文建模,找出編碼結果與樣本中的點能夠匹配的點,本文設定相似度95%以上即判定為匹配成功,如果相似度沒有達到95%以上的,選擇相似度最高的進行匹配。對整個樣本庫掃描一遍之后,就可以識別出圖片上有哪幾個字符,再根據(jù)各個字符像素點在圖片上的相對位置排好順序,從而實現(xiàn)程序的自動識別。假設樣本上一個點的形狀上下文為:h i=h i(1,h i(2, h i(k,測試圖片上任意一點的形狀上下文為:h j=h j(1, h j(2, , h j(k,這里k=12。令C i,j為形狀上下文算法的Cost 值,則:2,1(1/2(k i ji jk i jh k h kCh k

14、 h k=+, k=12Cost值在01之間,Cost值越小,相似度越高,兩點的匹配度越高。本文取半圓是因為半圓就足夠對像素點形狀描述,而且202 計算機工程2011年1月20日消除了2個字符連接點附近像素點建模受到旁邊字符的干擾,半圓就能夠準確地描述出該點的形狀上下文信息。整體識別的效果如圖3所示。 (a正確匹配識別 (b錯誤識別圖3 字符整體識別效果3 算法實現(xiàn)本文基于.NET平臺,使用C#語言進行算法實現(xiàn),參考文獻6的部分代碼。輸入:網(wǎng)絡上隨機獲取驗證碼,用Bitmap 類型變量Recbmp保存。識別步驟如下:(1對Recbmp進行灰度化,取128作為閾值,使用SetPixel 類將圖片

15、設置為只有(255, 255, 255和(0, 0, 0的黑白圖。(20Recbmp.Heigh-1和0Recbmp.Width-1搜索到第1個外邊界像素點(x0, y0,將該點標記值設置為1。1從(x0,y0的8個相鄰像素點中搜索下一個邊界點(x1, y1,標記值設置為1;2重復步驟1直到搜索到邊界點(x0, y0為止,得到所有字符外邊界;3根據(jù)梯度變化,從 0Recbmp.Height-1和0Recbmp. Width-1搜索未標記的黑色像素點為內(nèi)邊界像素點開始點(x i, y j(x n, y n,使用步驟1和步驟2得到每一個內(nèi)邊界。(3取一個樣本字符,取樣本字符寬度Height作為極坐

16、標直徑r,根據(jù)樣本字符取左(右半極坐標圓建模,利用2.2節(jié)的方法,對驗證碼圖片上每一個像素點(x0, y0分別進行左(右半極坐標圓建模。(4利用2.3節(jié)的方法,根據(jù)每個像素點編碼值與測試圖片上像素點編碼值,計算樣本字符與測試圖片上像素點組成字符的相似度Cost值。(5根據(jù)當前的Cost值判定測試圖片上是否存在該樣本字符,然后接著取下一個樣本字符,重復(3和(4。(6找出Cost值最小的4個字符后,根據(jù)像素點相對位置對字符排序,完成字符識別。4 實驗與分析本文用2種方法對復雜驗證碼識別進行實驗:(1制作不同數(shù)量的樣本進行實驗,將識別率與簡單驗證碼進行比較;(2每個樣本選取不同像素點數(shù)目進行建模,

17、觀察識別率隨建模像素點數(shù)目改變情況。示例驗證碼有數(shù)字和字母,每個字符構造一個樣本,即有36個樣本,這種情況下隨機識別100張圖片,識別率為60%。本文對簡單驗證碼也進行了大量實驗,同樣只有一個樣本的情況下,普通方法對簡單驗證碼的識別率也只有46%。然而,隨著樣本數(shù)量的增加,簡單驗證碼的識別率能很快接近于100%,而復雜驗證碼的識別率最高只能到達80%左右,如表1所示。表1 不同數(shù)量字符樣本的識別率識別率/(%字符樣本數(shù)簡單驗證碼復雜驗證碼1 46 602 67 713 84 784 93 82對字符形狀上下文建模時選取不同數(shù)量的像素點數(shù)目。圖2中字符6包含有115個像素點,其實2個相鄰的像素點

18、形狀上下文基本相同。實驗時選擇全部像素點建模,相鄰的2個像素點選擇1個建模以及相鄰的3個像素點建模一個。選擇不同數(shù)量的像素點建模得到的識別率如下:(1全部像素點的識別率為78%;(21/2像素點的識別率為70%;(31/3像素點的識別率為67%。選擇不同數(shù)目的像素點進行建模,隨機識別100張圖片的結果。可以看出,減少建模的像素點數(shù)目,程序自動識別的正確率變化很小,然而程序運行速度明顯加快。通過大量的驗證碼識別實驗也總結了反識別的思想:為了防止程序自動識別,字符粘連是第1步;然而簡單的粘連還是能夠被破解,需增加干擾線以及字符適當扭曲。第3類驗證碼字符扭曲程度很大,非常難識別,但人眼識別困難,用戶體驗也比較