python驗證碼切割

⑴ 驗證碼識別之模板匹配方法

在寫爬蟲的時候難免會遇到驗證碼識別的問題，常見的驗證碼識別的流程為：

- 圖像灰度化

- 圖像去噪(如圖像二值化)

- 切割圖片

- 提取特徵

- 訓練

但這種方法要切割圖片，而且破解驗證碼的重點和難點就在於 能否成功分割字元 。

本文要介紹的演算法 不需要進行圖片切割，也不需要進行機器訓練 ，這種方法就是模板匹配：將待識別的文字切割成一個個模板，在待識別的圖像中去匹配模板。

這篇文章將分為兩個部分：

第一部分介紹模板匹配的基本概念以及模板匹配的一種實現演算法：快速歸一化互相關匹配演算法；

第二部分是一個具體實例。

模板匹配是在圖像中尋找目標的方法之一，目的就是在一幅圖像中尋找和模板圖像最相似的區域。

模板匹配的大致過程是這樣的：通過在輸入圖像上滑動圖像塊對實際的圖像塊和輸入圖像進行匹配。

假設我們有一張100x100的輸入圖像，有一張10x10的模板圖像，查找的過程是這樣的：

從輸入圖像的左上角(0,0)開始，切割一塊(0,0)至(10,10)的臨時圖像；

用某種方法得出臨時圖像與模板的相似度c,存放到相似度矩陣中（矩陣大小為91 x91）；

切割輸入圖像從(0,1)至(10,11)的臨時圖像，對比，並記錄到相似度矩陣；

重復上述步驟，直到輸入圖像的右下角。

最終得到一個相似度矩陣，找到矩陣中的最大或最小值，最大值（最小值）對應的臨時圖像即為與模板最相似的圖像。

在步驟b中，求模板與圖像的相似度有多種方法，如平均絕對差演算法（MAD）、絕對誤差和演算法（SAD）、誤差平方和演算法（SSD）、歸一化互相關演算法（NCC），本文使用的是歸一化互相關演算法。

什麼是歸一化互相關？

從幾何圖形上來看，空間中的兩個向量，同方向平行時，歸一化互相關系數為1，表示兩個向量最相似，反方向平行時歸一化互相關系數為-1，垂直時為0，表示最不相似（用互相垂直的三個向量來代表整個空間也是這個道理，垂直的向量之間不包含對方的信息，相關系數為0），存在一定夾角時處於（-1，1），是不是跟餘弦函數很像，cos(0)=1,cos(pi/2)=0,cos(pi)=-1。就是這個樣子的，相關系數可以看作是兩個向量之間夾角的cosine函數。

在數學中是這么計算cosine函數的，假設兩個n維向量X,Y，對應的坐標分別為(x1，x2，…xn), (y1，y2，…yn) 則：

（如果想要了解更多，請參考文獻【2】）

但這是一維的，在模板匹配中要再加一個維度 （具體演算法請參考文獻【3】） ，簡要說一下文獻【3】的內容：如果直接計算二維相似度的話計算復雜度會非常高，文獻【3】利用快速傅里葉變換與積分圖像快速演算法來降低計算復雜度。

接下來讓我們看一個具體的應用。

模板匹配識別驗證碼的具體步驟為：

1. 找出圖片中所有可能出現的字元，製作成模板集合

2. 圖像灰度化

3. 圖片去噪（二值化）

4. 模板匹配

5. 匹配結果優化

要識別的圖片如下，以識別圖片中的加字為例：

要從image中找到與模板最匹配的部分，Template圖像是事先從image圖像中截取的一部分。所用的為python模塊skimage中的match_template方法，match_template方法使用的是快速歸一化互相關演算法 【2】 。

遍歷模板圖像集合，與圖像匹配，如果dist大於閾值h，則認為此模板在圖像中存在，否則不存在，繼續匹配下一個模板，直到遍歷完所有模板。

以模板『加』為例，圖像大小為40x260，模板大小27x27，result是一個大小為（14，234）的矩陣，即上文提到的相似度矩陣，矩陣中的數值屬於[-1,1]，找到result中最大值所處的對應位置即為與模板最匹配的圖像位置:x=66,y=11，正好對應模板圖像在image中所處的位置。 （更多內容請參閱參考文獻【4】）

但這是比較好的情況，因為在匹配時遍歷了所有的模板，而一張圖片中出現的模板數量是有限的，比如數字』四』在圖片中是沒有的，這時就要根據某種規則去掉這些在圖片中沒有出現的模板：程序中使用dist變數來過濾匹配結果，如果dist變數大於某個值則認為此模板在圖像中不存在。

最後的result_list中可能仍然存在一些圖片中不存在的模板或者匹配不精確的模板，比如數字『一』在模板中不存在，但仍然可以匹配到，因為數字『二』中可以匹配到『一』，需要進一步優化，優化方法有很多，比如當匹配到的兩個模板距離過近時，選擇較大的那個模板，其餘方法留給讀者自行考慮吧。

後續將會推出如何使用深度學習識別驗證碼，敬請期待~

參考文獻：

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」, Instrial Light and Magic.

http://scikit-image.org/docsjinhqin/dev/auto_examples/plot_template.html

本文作者 ：李暉（點融黑幫），畢業於電子科技大學，現就職於點融成都Data部門，對一切新鮮事物充滿好奇，對跳舞毫無抵抗力的活力女青年一枚。