前面有兩篇文章談到了模板匹配演算法，分別是【工程應用一】 多目標多角度的快速模板匹配演算法（基于NCC，效果無限接近Halcon中........) 以及【工程應用二】 多目標多角度的快速模板匹配演算法（基于邊緣梯度)，那么經過最近2個多月的進一步研究，也有了更多的一些心得和體會，這里也簡單分享一些在這個程序中屬于我個人的理解的一些東西，
1、在上一篇基于邊緣梯度的文章中，我曾說使用Canny算子不合適，會丟失一些弱邊緣的資訊，但是后續我感徑訓是可以的，
2、在使用Canny后，一個很好的好處就是可以不做全圖的計算了，這對速度的提高還是有很大的貢獻的，通常Canny檢測到的邊緣占全圖的像素數不會超出1/10,，
擴展一下： 如果不做 Canny，而是對全圖進行邊緣檢測后，按照邊緣點的強度進行排序，然后取強度的前1/10作為候選點，也不失為一種解決問題的方法，但是測驗發現偶爾會有丟失或誤選目標的現象，
3、對于旋轉后的邊緣問題，這個可以通過如下的方式進行解決，
旋轉后的無效的像素處，按照水平或者垂直方向的資訊，對無效的區域的像素用離其水平或垂直方向最近的有效像素填充，選擇水平方向實作最為簡單和高效，
一個簡單的代碼如下所示：
int IM_CorrectRotatedImage_Hori(HBitmap Src, HBitmap Mask) { StartEnd *Hori = (StartEnd *)malloc(Mask.Height * sizeof(StartEnd)); if (Hori == NULL) return IM_STATUS_NULLREFRENCE; IM_SimpleMaskRLE_Hori(Mask, Hori); // 獲取縮小后的水平行程 for (int Y = 0; Y < Src.Height; Y++) { if (Hori[Y].Start != -1) { memset(Src.Data + Y * Src.Stride, Src.Data[Y * Src.Stride + Hori[Y].Start], Hori[Y].Start); memset(Src.Data + Y * Src.Stride + Hori[Y].End + 1, Src.Data[Y * Src.Stride + Hori[Y].End], Src.Width - Hori[Y].End - 1); } } int Top = -1, Bottom = -1; for (int Y = 0; Y < Src.Height; Y++) { if (Hori[Y].Start != -1) { Top = Y - 1; break; } } for (int Y = Src.Height - 1; Y >= 0; Y--) { if (Hori[Y].Start != -1) { Bottom = Y + 1; break; } } if (Top != -1) { for (int Y = 0; Y <= Top; Y++) { memcpy(Src.Data + Y * Src.Stride, Src.Data + (Top + 1) * Src.Stride, Src.Stride); } } if (Bottom != -1) { for (int Y = Src.Height - 1; Y >= Bottom; Y--) { memcpy(Src.Data + Y * Src.Stride, Src.Data + (Bottom - 1) * Src.Stride, Src.Stride); } } free(Hori); return IM_STATUS_OK; }
此時，再對此圖做Canny邊緣檢測，則無效處因為填充的基本為同一像素或者近似，無效處的Canny值基本為0，在旋轉的邊緣處因為也是近似，值也約為0，即使不為0，也沒有關系，旋轉后的蒙版圖也會把這些位置給裁剪掉，因此，不會產生新的邊緣問題，如下所示：
模板圖 旋轉一定角度的模板圖 水平方向邊緣填充 Canny邊緣檢測 旋轉后對應的蒙版圖 根據蒙版裁切后的邊緣圖
對于第一個模板，因為其邊緣你基本為純色，因此擴展后的圖沒有什么問題，而第二個圖，擴展后的圖進行檢測，會看到在無效區域有一些額外的邊緣出現，但是經過蒙版裁剪這些區域就消失了，
4、對于得分公式，用 
是完全可以的，注意的事情就是，對于模板影像 ，因為提取的候選點是用Canny選出來的，估計GX和GY一般也不會為0，至少不會同是為0，因此整個式子分母中的前半部分不會為0， 那么在編程時如果遇到在原圖中的GX和Gy同時為0時，需要注意做特別處理，防止發生除以0的錯誤，即此位置的貢獻為0（分子必然為0），
擴展： 整個運算式是一個歸一化的式子，因為模板進行了Canny篩選，但是原圖對應的位置是動態的，如果在原圖中遇到那種比較光滑的地方（梯度值很小），比如GxS = 1， GyS = 2，這樣的值，無論模板對應處的梯度如何，得分都會比較高，比如GxT = 230, GyT = 100，則此時此點的匹配度為： 1*230+2*100 /(sqrt(1*1+2*2)*sqrt(230*230+100*100)) =0.76， 很明顯，我們覺得這樣的情況是不可以接受的，因此，個人覺得對于這樣的點，應該在計算分值時予以剔除（不急于得分加成中），
5、為了減少Canny檢測的噪音，可在檢測前進行適當的模糊，高斯模糊、均值模糊、保邊模糊隨你選，但是半徑不易過大，而且要注意隨著金字塔的下采樣，因為下采樣本身就是一種平均，因此模糊的半徑應該怎么樣來著？？？？？？
6、CodeProject上印度小哥的得分貪心演算法可以應用上，這個對于金字塔頂層的速度提高有較為明顯的作用，但是對于后續的向上擴展搜索加速作用有限，這個主要是因為后續的候選點得分本身就比較高了，那個貪心的要求標準也越來越難以達到，
7、演算法的速度優化上有很多方法，1個是原理上的，一個是編碼上的，
（1）原理上的，前面說的金字塔時根本，Canny檢測減少候選點是主攻，貪心演算法是甜點，另外就是在各層的新的候選點的篩選上，也應該逐層減少，操作的原則可以是： 兩個候選點的坐標位置過進，取得分大的， 候選點之間的區域重疊度過大， 可以只取得分高者等等，
（2）編碼上則八仙過海，各顯神通了，我最擅長的是SIMD指令優化，這里提幾個小的Trick，
a、梯度值的保存， 上述邊緣的梯度值Gx和Gy根據資料的范圍，很明顯最合適使用的資料型別是signed short，
b、在SIMD指令中有一個_mm_madd_epi16，其函式原型為：
extern __m128i _mm_madd_epi16(__m128i _A, __m128i _B);
我在我博客里多次提前這個函式，他可以一次性型實作8個short型別資料的乘法和4次int型別的加法，如下所示：
如果我們布局的時候，把梯度的X和Y方向資料連續布置，那么得分公式的分子和分母的四個部分乘法和加法（下面的平方也是乘法）就可以直接利用這樣的指令實作了，具體的自己好好理解吧，
c、求根號是個比較慢的計算程序，SIMD指令有_mm_sqrt_ps指令一次性實作4個浮點數的開方，那么按照上面的式子就還需要求倒數，我們首先把得分式子的分母中的兩個根號里的資料相乘，然后在開方，結果是一樣的，很明顯就少了一次開方操作， 同時，注意到SIMD里還有一個指令，即_mm_rsqrt_ps，他可以一次性的完成開方和求倒數作業，因此速度就更快了，
d、另外還有一個點，我們在向金字塔底層搜索的程序中，一般的搜索半徑為2，即搜索區域為5*5大小，對于這個尺寸，還可以一次性處理4個點，這樣就組成 6*4+1個組合，這種組合比直接計算單獨的25個點要速度快很多，因為他避免了對模板資料的多次重復讀取和計算，
8、除了速度，還有演算法穩定性問題，這個也是個比較難的問題，我目前也還遇到一些情況，比如不同的起點角度，都是慢360度的搜索方位，回傳的角度值可能有輕微的波動，還比如有些情況可能會丟失一些目標或找到了多余的目標等等，這個還需要后續繼續研究，比較增加程序中的亞像素參與等，
9、比較了下halcon的create_shape_model和find_shape_model，發現他的模型檔案都特別特別的小，只有幾十KB，而且create_shape_model的程序基本是幾豪秒殺，因此，感覺他的結構應該更為敲門，也許是用到了亞像素方面的特性，需要慢慢看有么有機遇找到這方面的資料了，
10、halcon有基于形狀的多目標、多角度、多縮放尺度的模板檢測，這個現在也在想，如何減少計算量，有點麻煩，
目前，經過一番騷操作，基于形狀的匹配在速度上有的時候居然比基于NCC的還快了不少，而且結果上也比較穩定，
如果哪位在工程實踐中有需要類似的功能，我可以提供函式介面和Demo（基于邊緣的演算法），不過唯一的要求就是提供一些實際的素材供我測驗演算法用，
這里提供一個例子供大家測驗： https://files.cnblogs.com/files/Imageshop/TemplateMatching.rar
如果想時刻關注本人的最新文章，也可關注公眾號： 
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285712.html
標籤：其他