在寫爬蟲的時(shí)候難免會(huì)遇到驗(yàn)證碼識(shí)別的問(wèn)題，常見的驗(yàn)證碼識(shí)別的流程為：
- 圖像灰度化
- 圖像去噪(如圖像二值化)
- 切割圖片
- 提取特征
- 訓(xùn)練
但這種方法要切割圖片，而且破解驗(yàn)證碼的重點(diǎn)和難點(diǎn)就在于能否成功分割字符旭咽。
本文要介紹的算法不需要進(jìn)行圖片切割，也不需要進(jìn)行機(jī)器訓(xùn)練莫矗，這種方法就是模板匹配：將待識(shí)別的文字切割成一個(gè)個(gè)模板绑蔫，在待識(shí)別的圖像中去匹配模板蛔垢。
這篇文章將分為兩個(gè)部分：
第一部分介紹模板匹配的基本概念以及模板匹配的一種實(shí)現(xiàn)算法：快速歸一化互相關(guān)匹配算法嚎于；
第二部分是一個(gè)具體實(shí)例掘而。
1、模板匹配
模板匹配是在圖像中尋找目標(biāo)的方法之一于购，目的就是在一幅圖像中尋找和模板圖像最相似的區(qū)域袍睡。
模板匹配的大致過(guò)程是這樣的：通過(guò)在輸入圖像上滑動(dòng)圖像塊對(duì)實(shí)際的圖像塊和輸入圖像進(jìn)行匹配。
假設(shè)我們有一張100x100的輸入圖像肋僧，有一張10x10的模板圖像斑胜，查找的過(guò)程是這樣的：
從輸入圖像的左上角(0,0)開始控淡，切割一塊(0,0)至(10,10)的臨時(shí)圖像；
用某種方法得出臨時(shí)圖像與模板的相似度c,存放到相似度矩陣中（矩陣大小為91 x91）止潘；
切割輸入圖像從(0,1)至(10,11)的臨時(shí)圖像掺炭，對(duì)比，并記錄到相似度矩陣覆山；
重復(fù)上述步驟，直到輸入圖像的右下角泥栖。
最終得到一個(gè)相似度矩陣簇宽，找到矩陣中的最大或最小值，最大值（最小值）對(duì)應(yīng)的臨時(shí)圖像即為與模板最相似的圖像吧享。
在步驟b中魏割，求模板與圖像的相似度有多種方法，如平均絕對(duì)差算法（MAD）钢颂、絕對(duì)誤差和算法（SAD）钞它、誤差平方和算法（SSD）、歸一化互相關(guān)算法（NCC）殊鞭，本文使用的是歸一化互相關(guān)算法遭垛。
2、歸一化互相關(guān)算法
什么是歸一化互相關(guān)操灿？
從幾何圖形上來(lái)看锯仪，空間中的兩個(gè)向量，同方向平行時(shí)趾盐，歸一化互相關(guān)系數(shù)為1庶喜，表示兩個(gè)向量最相似，反方向平行時(shí)歸一化互相關(guān)系數(shù)為-1救鲤，垂直時(shí)為0久窟，表示最不相似（用互相垂直的三個(gè)向量來(lái)代表整個(gè)空間也是這個(gè)道理，垂直的向量之間不包含對(duì)方的信息本缠，相關(guān)系數(shù)為0）斥扛，存在一定夾角時(shí)處于（-1，1）丹锹，是不是跟余弦函數(shù)很像犹赖，cos(0)=1,cos(pi/2)=0,cos(pi)=-1。就是這個(gè)樣子的卷仑，相關(guān)系數(shù)可以看作是兩個(gè)向量之間夾角的cosine函數(shù)峻村。
在數(shù)學(xué)中是這么計(jì)算cosine函數(shù)的，假設(shè)兩個(gè)n維向量X,Y锡凝，對(duì)應(yīng)的坐標(biāo)分別為(x1粘昨，x2，…xn), (y1，y2张肾，…yn) 則：
（如果想要了解更多芭析，請(qǐng)參考文獻(xiàn)【2】）
但這是一維的，在模板匹配中要再加一個(gè)維度（具體算法請(qǐng)參考文獻(xiàn)【3】）吞瞪，簡(jiǎn)要說(shuō)一下文獻(xiàn)【3】的內(nèi)容：如果直接計(jì)算二維相似度的話計(jì)算復(fù)雜度會(huì)非常高馁启，文獻(xiàn)【3】利用快速傅里葉變換與積分圖像快速算法來(lái)降低計(jì)算復(fù)雜度。
接下來(lái)讓我們看一個(gè)具體的應(yīng)用芍秆。
3惯疙、具體實(shí)例
模板匹配識(shí)別驗(yàn)證碼的具體步驟為：
1. 找出圖片中所有可能出現(xiàn)的字符，制作成模板集合
2. 圖像灰度化
3. 圖片去噪（二值化）
4. 模板匹配
5. 匹配結(jié)果優(yōu)化
要識(shí)別的圖片如下妖啥，以識(shí)別圖片中的加字為例：
要從image中找到與模板最匹配的部分霉颠，Template圖像是事先從image圖像中截取的一部分。所用的為python模塊skimage中的match_template方法荆虱，match_template方法使用的是快速歸一化互相關(guān)算法【2】蒿偎。
遍歷模板圖像集合，與圖像匹配怀读，如果dist大于閾值h诉位，則認(rèn)為此模板在圖像中存在，否則不存在菜枷，繼續(xù)匹配下一個(gè)模板不从，直到遍歷完所有模板。
以模板‘加’為例犁跪，圖像大小為40x260椿息，模板大小27x27，result是一個(gè)大小為（14坷衍，234）的矩陣寝优，即上文提到的相似度矩陣，矩陣中的數(shù)值屬于[-1,1]枫耳，找到result中最大值所處的對(duì)應(yīng)位置即為與模板最匹配的圖像位置:x=66,y=11乏矾，正好對(duì)應(yīng)模板圖像在image中所處的位置。（更多內(nèi)容請(qǐng)參閱參考文獻(xiàn)【4】）
但這是比較好的情況迁杨，因?yàn)樵谄ヅ鋾r(shí)遍歷了所有的模板钻心，而一張圖片中出現(xiàn)的模板數(shù)量是有限的，比如數(shù)字’四’在圖片中是沒(méi)有的铅协，這時(shí)就要根據(jù)某種規(guī)則去掉這些在圖片中沒(méi)有出現(xiàn)的模板：程序中使用dist變量來(lái)過(guò)濾匹配結(jié)果捷沸，如果dist變量大于某個(gè)值則認(rèn)為此模板在圖像中不存在。
最后的result_list中可能仍然存在一些圖片中不存在的模板或者匹配不精確的模板狐史，比如數(shù)字‘一’在模板中不存在痒给，但仍然可以匹配到说墨，因?yàn)閿?shù)字‘二’中可以匹配到‘一’，需要進(jìn)一步優(yōu)化苍柏，優(yōu)化方法有很多尼斧，比如當(dāng)匹配到的兩個(gè)模板距離過(guò)近時(shí)，選擇較大的那個(gè)模板试吁，其余方法留給讀者自行考慮吧棺棵。
后續(xù)將會(huì)推出如何使用深度學(xué)習(xí)識(shí)別驗(yàn)證碼，敬請(qǐng)期待~
參考文獻(xiàn)：
http://www.cnblogs.com/beer/p/5672678.html
http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html
J. P. Lewis, “Fast Normalized Cross-Correlation”, Industrial Light and Magic.
http://scikit-image.org/docsjinhqin/dev/auto_examples/plot_template.html
本文作者：李暉（點(diǎn)融黑幫）熄捍，畢業(yè)于電子科技大學(xué)烛恤，現(xiàn)就職于點(diǎn)融成都Data部門，對(duì)一切新鮮事物充滿好奇治唤，對(duì)跳舞毫無(wú)抵抗力的活力女青年一枚棒动。
