模板匹配的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代码如此优化，您将难以增加它的性能但是谁知道你会想出一个办法，以获得更好的结果一切顺利，祝你好运

克里斯