目錄
前言
一、基礎知識
二、NCC基本公式以及解決問題
1. NCC基本公式
2. 基本公式解讀
三、簡化分母 fuv
1. 要簡化的分母
2. 積分圖
3. 分母拆開化簡
四、簡化分子
1. 要簡化的分子
2. 模板函數的近似
3. 基函數簡單解釋
五、Fast NCC歸一化互相關值
1. 最終公式
2. 復雜性對比
3. 論文中的舉例：
總結
前言
最近在看一篇關于模板匹配的論文，里面的使用模板匹配的算法是改進版的NCC，即Fast NCC，看網上沒有關于Fast NCC的解說，就想著記錄一下自己學習的過程，寫一下自己對這個改進算法的解釋，論文的全稱是《Template Matching using Fast Normalized Cross Correlation》，有感興趣的可以自己去了解一下。（因為有的內容不好打字，下面我會用手寫圖片）
一、基礎知識
從最簡單的初高中知識開始：均值、標準差、方差、協方差、相關系數
二、NCC基本公式以及解決問題
1. NCC基本公式
本文討論的問題是確定給定模式在二維圖像中的位置。設?f(x,y) 表示圖像在點 (x,y) 處的強度值，圖像大小為 Mx × My，其中 x∈{0,…,Mx -1}，y∈{0,…,My -1}。模式由給定的模板 t 表示，模板大小為 Nx? × Ny?。計算模板匹配程度高低就是在點 (x,y) 處計算歸一化互相關值，即NCC系數，系數值越高說明越匹配，有系數基本公式：與 “一、基礎知識” 中的相關系數 r 同理
如果圖像越匹配，則圖像和模板越趨向于線性關系(一次函數)：
其中
2. 基本公式解讀
三、簡化分母 fuv
1. 要簡化的分母
由上面我們可知：
即模板所在圖像位置，那一塊模板區域圖像的均值，我們可以知道，移動一次模板就需要計算一次模板所在區域圖像的均值，計算時間需要很久，于是就提出了用積分表快速計算 fuv。(因為模板部分方差容易計算就先不管，這里主要是簡化計算圖像部分的方差)
2. 積分圖
(作圖有點粗糙看得懂就行)
即
推廣到區域積分：
就有了以下公式，只需要三次相加減就可以算出模板區域內的圖像強度均值：
3. 分母拆開化簡
NCC的分母可以拆開變成：
其中：
解釋一下其中的參數：
但是不要忘記還有：
化簡一下：
最后可得：
分母簡化完畢！！！只靠積分表就實現了計算
四、簡化分子
1. 要簡化的分子
分子原式：
可以寫成分子N(u,v)
其中：t'(x-u,y-v) 為
由于 t′ 的均值為零，因此其總和也為零，故有：
所以分子N(u,v)只剩下：
2. 模板函數的近似
將
展開成K個矩形基函數
的加權和，得到近似值
，詳細為：
?
為加權系數，
為基函數。
3. 基函數簡單解釋
基函數在這里可以暫且理解為在一些區域等于1，其他區域都為0，所以可以化簡：
舉個例子，下圖就是在6 <= x <=?14 ^ 8 <=?y <=?12區域為1，其他區域為0的基函數：
所以分子N(u,v)可以近似為：
論文中寫了確定基函數有兩種方法，第一種是手動確定，第二種是自動確定。
與上面的分母同理，這里也可以運用積分表：
也成功化簡了分子！！！只需要三次相加減就可以求得分子
五、Fast NCC歸一化互相關值
1. 最終公式
簡化完分子和分母之后，可以得到NCC歸一化的近似值：
最終式子即為：
完成了NCC算法的加速。
2. 復雜性對比
復雜性分析：
舉例說明，可以得出Fast NCC的算法復雜性最低
3. 論文中的舉例：
幾個圖的說明：
(a) 原始圖像? ? ? ? ? (b) 經過Fast NCC算法的交叉相關矩陣(u,v)
(c) 原始模板圖像? ? (d) 原始模板圖像曲面圖
(e) 基函數處理過后的模板圖像? ? ? (f) 處理過后的模板圖像曲面圖
總結
這篇文章對Fast NCC進行了一個解讀，介紹了如何簡化分母和分子，并求得近似值進行加速計算，最后得到了最終Fast NCC的算法公式，其復雜度遠低于直接計算以及FFT，但是其中的基函數還有待考究，后續學習會繼續補充。
