1. FFT與圖像最大互相關演算法
圖像 互相關演算法 就是計算 兩幅圖像 相關系數 的 方法，常用於圖像匹配。例如同一目標物，被拍了兩張照片，要把兩張照片「對齊",可以給出不同的對位，計旅野算相關系數，相關系數最大的對位就是最佳對齊。
相關系數計算和褶積計算可以用到傅里葉變換。
FFT 是快速傅里葉變換。FFT 要求 離散 點 為 2 的 整次方點，例如1024，2048....,它利用系數的對稱性，省去大量計算時間。
關於圖像匹配互相關演算法，網上好像很多。FFT 是老技術，程序也能找到。
（隨便找了一談鎮敗篇）圖像匹配最大互相關演算法的專用ASIC硬體實現方式研究 見含顫參考資料。
2. 驗證碼識別之模板匹配方法
在寫爬蟲的時候難免會遇到驗證碼識別的問題，常見的驗證碼識別的流程為：
- 圖像灰度化
- 圖像去噪(如圖像二值化)
- 切割圖片
- 提取特徵
- 訓練
但這種方法要切割圖片，而且破解驗證碼的重點和難點就在於 能否成功分割字元 。
本文要介紹的演算法 不需要進行圖片切割，也不需要進行機器訓練 ，這種方法就是模板匹配：將待識別的文字切割成一個個模板，在待識別的圖像中去匹配模板。
這篇文章將分為兩個部分：
第一部分介紹模板匹配的基本概念以及模板匹配的一種實現演算法：快速歸一化互相關匹配演算法；
第二部分是一個具體實例。
模板匹配是在圖像中尋找目標的方法之一，目的就是在一幅圖像中尋找和模板圖像最相似的區域。
模板匹配的大致過程是這樣的：通過在輸入圖像上滑動圖像塊對實際的圖像塊和輸入圖像進行匹配。
假設我們有一張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部門，對一切新鮮事物充滿好奇，對跳舞毫無抵抗力的活力女青年一枚。