圖像處理之積分圖應用三（基于NCC快速相似度比對算法）
基于Normalized cross correlation(NCC)用來比較兩幅圖像的相似程度已經是一個常見的圖像處理手段。在工業生産環節檢測、監控領域對對象檢測與識别均有應用。NCC算法可以有效降低光照對圖像比較結果的影響。而且NCC最終結果在0到1之間，是以特别容易量化比較結果，隻要給出一個門檻值就可以判斷結果的好與壞。傳統的NCC比較方法比較耗時，雖然可以通過調整視窗大小和每次檢測的步長矩形部分優化，但是對工業生産檢測然後不能達到實時需求，通過積分圖像實作預計算，比較模闆圖像與生産出電子版之間的細微差異，可以幫助企業提高産品品質，減少次品出廠率，把控品質。
一：NCC相關的數學知識
什麼是NCC - （normalized cross correlation）歸一化的交叉相關性，是數學上統計兩組資料之間是否有關系的判斷方法，貌似搞大資料分析比較流行相關性分析和計算。正常的計算公式如下：
mxn表示視窗大小，這樣的計算複雜度就為O(m x n x M x N)。從上面公式就可以看出其中均值和平方和可以通過積分圖預計算得到，對于模闆和目标圖像大小一緻的應用場景來說
NCC的計算公式可以表示為如下：
其中根據積分圖像可以提前計算出任意視窗大小和與平方和，這樣就對
上述兩個計算實作了視窗半徑無關的常量時間計算，唯一缺少的是下面計算公式
通過積分圖像建立起來視窗下面的待檢測圖像與模闆圖像的和與平方和以及他們的交叉乘積五個積分圖索引之後，這樣就完成了整個預計算生成。依靠索引表查找計算結果，NCC就可以實作線性時間的複雜度計算，而且時間消耗近似常量跟視窗半徑大小無關，完全可以滿足實時對象檢測工業環境工作條件。
二：算法步驟
1. 預計算模闆圖像和目标圖像的積分圖
2. 根據輸入的視窗半徑大小使用積分圖完成NCC計算
3. 根據門檻值得到比對或者不比對區域。
4. 輸出結果
為了減小計算量，我們可以要把輸入的圖像轉換為灰階圖像，在灰階圖像的基礎上完成整個NCC計算檢測。我們這個給出的基于RGB圖像的NCC計算完整代碼，讀者可以在此基礎上修改實作單通道圖像檢測。
三： 運作結果：
輸入的模闆圖像與待檢測圖像，左邊是模闆圖像，右邊是待檢測圖像，左上角有明顯污點。圖像顯示如下：
輸入待檢測圖像與模闆比較以及檢測計算出NCC的圖像顯示如下：
其中左側是待檢測圖像，上面有黑色污點，右側輸出的非黑色區域表明，程式已經發現此區域與标準模闆不同，越白的區域表示周圍跟模闆相同位置反差越大，越是可疑的污染點，這樣就可以得到準确定位，最終帶檢測圖像繪制最可疑紅色矩形視窗區域
四：相關代碼實作
1. 計算兩張圖像每個像素交叉乘積的積分圖代碼如下：
擷取任意視窗大小的交叉乘積的代碼如下：
2. 預計算建立積分圖索引的代碼如下：
3. 通過積分圖查找實作快速NCC計算的代碼如下：
4. 歸一化輸出NCC圖像與結果代碼如下：
相比傳統的NCC計算方法，此方法的計算效率是傳統方法幾百倍提升，而且視窗越大效率提升越明顯，有人對此作出的統計如下：
可見基于積分圖快速NCC可以極大提升執行效率減少計算時間，實作視窗半徑無關NCC比較。
最後
本文是關于積分圖使用的第三篇文章，可以說積分圖在實際圖像進行中應用十分廣泛，本人會繼續努力深挖與大家分享。希望各位頂下次文以表支援， 謝謝！本人堅持分享有用實用的圖像處理算法！需要大家多多支援。