模板匹配的OpenCV性能

Question

我想基本上在java上做模板匹配。我用直接的算法來找到匹配。這裏是代碼：

minSAD = VALUE_MAX; 
// loop through the search image 
for (int x = 0; x <= S_rows - T_rows; x++) { 
    for (int y = 0; y <= S_cols - T_cols; y++) { 
     SAD = 0.0; 

     // loop through the template image 
     for (int i = 0; i < T_rows; i++) 
      for (int j = 0; j < T_cols; j++) { 

       pixel p_SearchIMG = S[x+i][y+j]; 

       pixel p_TemplateIMG = T[i][j]; 

       SAD += abs(p_SearchIMG.Grey - p_TemplateIMG.Grey); 
      } 
    } 

    // save the best found position 
    if (minSAD > SAD) { 
     minSAD = SAD; 
     // give me VALUE_MAX 
     position.bestRow = x; 
     position.bestCol = y; 
     position.bestSAD = SAD; 
    } 
} 

但這是非常緩慢的做法。我測試了2張圖像（768×1280）和子圖像（384×640）。這持續了很長時間。 是否openCV執行模板匹配更快或沒有準備好的功能cvMatchTemplate（）？

Answer 1

你會發現openCV cvMatchTemplate（）比你實現的方法快得多。你創建的是統計模板匹配方法。這是最常見和最容易實現的，但對大型圖像來說非常緩慢。讓我們看看你有一個圖像的基本數學是768x1280你通過每個像素減去邊緣循環，因爲這是你的模板限制所以（768 - 384）×（1280 - 640）384×640 = 245'因此，在循環中添加任何已有的數學（245'760 x 245'760）60'397'977'600操作之前，您需要循環執行760次操作（其中包含245'760次操作）。超過60億次操作只是爲了循環顯示圖像更快意識的機器可以做到這一點更令人驚訝。

但請記住它的245'760 x（245'760 x數學運算），所以有更多的操作。

現在cvMatchTemplate（）實際上使用傅立葉分析模板匹配操作。這是通過對組成像素的信號強度變化的圖像應用快速傅里葉變換（FFT）來分割成每個相應的波形。該方法很難很好地解釋，但圖像被轉換成複數的信號表示。如果您想了解更多信息，請在護目鏡上搜索fast fourier transform。現在在模板上執行相同的操作，形成模板的信號用於濾除圖像中的任何其他信號。

簡而言之，它會取消圖像中與模板不具有相同功能的所有功能。然後使用快速傅里葉逆變換將圖像轉換回來，以產生高值表示匹配的圖像，低值表示相反。這個圖像通常是標準化的，所以1代表匹配，0代表或在那裏表示物體不在附近。

儘管如果它們的對象不在圖像中並且它被標準化，但會被警告，因爲計算出的最高值將被視爲匹配，所以會發生錯誤檢測。我可以繼續關於該方法如何工作以及它可能發生的好處或問題的年齡，但...

此方法如此之快的原因是：1）opencv是高度優化的C++代碼。 2）fft功能對於處理器來說非常簡單，因爲大多數處理器都可以在硬件中執行此操作。 GPU圖形卡每秒鐘執行數百萬次fft操作，因爲這些計算在高性能遊戲圖形或視頻編碼中同樣重要。 3）所需的操作量要少得多。

總結統計模板匹配方法很慢並需要時間，而opencv FFT或cvMatchTemplate（）可以快速高度優化。

統計模板匹配不會產生錯誤，如果一個對象不存在，而opencv FFT可以除非在應用程序中注意。

我希望這給你一個基本的瞭解，並回答你的問題。

乾杯

克里斯

[編輯]

爲了進一步回答您的問題：

嗨，

cvMatchTemplate可以CCOEFF_NORMED和CCORR_NORMED和SQDIFF_NORMED包括非工作這些的標準化版本。 Here顯示你可以期待的結果的種類，並給你的代碼玩。

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

的三種方法以及引用和許多論文都可以通過Google scholar。我已經提供了幾篇論文。每一個簡單地使用一個不同的方程來找到形成模板的FFT信號和圖像內存在的FFT信號之間的相關性，相關係數往往會產生更好的結果，並且更容易找到參考。平方差的和是另一種可以與可比較的結果一起使用的方法。我希望其中的一些幫助：

Fast normalized cross correlation for defect detection Du-Ming Tsai;林建林; 模式識別快報 第24卷，第15期，2003年11月，頁2625至2631年

Template Matching using Fast Normalised Cross Correlation 凱Briechle; Uwe D. Hanebeck;

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-difference Friemel，B.H。; Bohs，L.N .;特拉伊，G.E。 Ultrasonics Symposium，1995. Proceedings。，1995 IEEE

A Class of Algorithms for Fast Digital Image Registration Barnea，Daniel I .;西爾弗曼，哈維。
電腦，在1972年2月

IEEE交易它通常青睞使用這些方法的任何等於1的歸一化版本匹配但是如果沒有對象存在，你可以得到誤報。該方法的運行速度很快，只是由於它在計算機語言中的煽動方式。所涉及的操作對於處理器架構來說是理想的，這意味着它可以用幾個時鐘週期完成每個操作，而不是在幾個時鐘週期內移動存儲器和信息。處理器已經解決了多年的FFT問題，並且像我說的那樣有內置硬件。基於硬件總是比軟件更快，模板匹配的統計方法基於基礎軟件。對於硬件良好的閱讀可以在這裏找到：

Digital signal processor 儘管Wiki頁面中的引用是值得期待的有效這是執行FFT計算

A new Approach to Pipeline FFT Processor 手生了他的硬件; Mats Torkelson; 我的最愛，因爲它顯示處理器內部發生了什麼

An Efficient Locally Pipelined FFT Processor 梁洋;張可偉;劉紅霞;金黃;石Huang煌;

這些文件確實顯示了FFT的實現過程有多複雜，但流程的管道內容允許在幾個時鐘週期內執行操作。這就是基於實時視覺的系統採用FPGA（專門設計可以設計來實現設定任務的處理器）的原因，因爲它們可以在架構中非常平行地設計，並且管線更容易實現。

雖然我必須提到，對於圖像的FFT，您實際上使用的是FFT2，它是水平平原的FFT和垂直平原的FFT，所以當您找到參考時不會有任何混淆。我不能說我對如何實現方程式和實現FFT具有專業知識我試圖找到好的嚮導，但找到一個好的嚮導非常困難，我還沒有找到一個（我沒有一個能理解的最小）。有一天，我可以理解他們，但要知道我對他們的工作方式以及可以預期的結果有很好的理解。

除此之外，如果您想要實現自己的版本或瞭解它是如何工作的，我無法真正地幫助您更多時間打開庫，但我警告您opencv代碼如此優化，您將難以增加它的性能但是誰知道你會想出一個辦法，以獲得更好的結果一切順利，祝你好運

克里斯