OpenCV模板匹配的性能表现

Question

OpenCV模板匹配的性能表现

javaimagetemplatesopencvtemplate-matching

15

我正在尝试使用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 x 1280）和子图像（384 x 640）。这需要很长时间。使用openCV的cvMatchTemplate()函数进行模板匹配速度更快吗？

- AraZZ

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris · Accepted Answer

你会发现openCV cvMatchTemplate()比你实现的方法快得多。你所创建的是一种统计模板匹配方法。它是最常见和最容易实现的方法，但在大型图像上非常缓慢。让我们来看看基本数学知识，你有一个768x1280的图像，你循环遍历每个像素减去边缘，因为这是你的模板限制，所以(768-384) x (1280-640)即384 x 640 = 245'760次操作，其中你循环遍历模板的每个像素(另外245'760次操作)，因此在你的循环中添加任何数学运算之前，你已经有了(245'760 x 245'760) 60'397'977'600次操作。超过600亿次操作只是为了遍历你的图像，惊人的是机器可以这么快地完成这项工作。

请记住，然而，它是245'760 x (245'760 x 数学运算次数)，因此还有更多的操作。

现在cvMatchTemplate()实际上使用傅里叶分析模板匹配操作。这通过对图像应用快速傅里叶变换（FFT）来实现，其中构成像素强度变化的信号被划分为相应的波形。该方法很难解释清楚，但是图像会转换为复数的信号表示。如果您想了解更多，请在goggle上搜索快速傅里叶变换。现在将同样的操作执行在模板上，构成模板的信号用于过滤出图像中的任何其他信号。

简单地说，它抑制了图像中所有没有与您的模板具有相同特征的特征。然后使用逆快速傅里叶变换将图像转换回来，以产生高值表示匹配，低值表示相反的图像。这个图像通常被标准化，因此1表示匹配，0或其周围的值表示物体不存在。

请注意，如果对象不在图像中并且它已被标准化，则会发生错误检测，因为计算出的最高值将被视为匹配。我可以详细讲述该方法的工作原理及其可能出现的问题和好处，但是......

这种方法之所以如此快，原因在于：1）opencv是高度优化的c++代码。2）fft函数易于处理，因为大多数处理器都具备执行此操作的能力。GPU图形卡被设计用于每秒执行数百万次fft操作，因为这些计算在高性能游戏图形或视频编码中同样重要。3）所需操作的数量远远少于其他方法。

简而言之，统计模板匹配方法很慢，而opencv FFT或cvMatchTemplate()则快速且高度优化。

如果物体不存在，统计模板匹配不会产生错误，而opencv FFT除非在应用中小心处理，否则可能会出现错误。

希望这能让您基本了解并回答您的问题。

干杯

克里斯

[编辑]

进一步回答您的问题：

您好，

cvMatchTemplate可以使用CCOEFF_NORMED和CCORR_NORMED和SQDIFF_NORMED，包括这些版本的非归一化版本。这里展示了您可以期望的结果，并提供了可供使用的代码。

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

这三种方法引用广泛，很多论文可以在Google学术中获取。以下提供了一些论文，每篇使用不同的公式来找到形成模板的FFT信号和存在于图像中的FFT信号之间的相关性。在我的经验中，相关系数倾向于产生更好的结果，并且更容易找到参考文献。平方差总和是另一种可用于获得可比较结果的方法。希望这些论文能有所帮助：

缺陷检测的快速归一化交叉相关 Du-Ming Tsai; Chien-Ta Lin; 模式识别信件 2003年11月，第24卷，第15期，页2625-2631

使用快速归一化交叉相关的模板匹配 Kai Briechle; Uwe D. Hanebeck;

二维斑点跟踪技术的相对性能：归一化相关、非归一化相关和绝对值和 Friemel, B.H.; Bohs, L.N.; Trahey, G.E.; 超声波会议，1995年。1995年IEEE会议录

快速数字图像配准算法 Barnea, Daniel I.; Silverman, Harvey F.; IEEE计算机学报1972年2月

通常使用这些方法的标准化版本，因为任何等于1的东西都是匹配，但如果没有对象存在，则可能会出现误报。该方法之所以快速，是由于它在计算机语言中的实施方式。所涉及的操作非常适合处理器架构，这意味着它可以在几个时钟周期内完成每个操作，而不是在多个时钟周期内移动内存和信息。处理器多年来一直在解决FFT问题，并且像我说的那样，有内置硬件来执行此操作。基于硬件的速度总是比软件更快，而基本软件的统计模板匹配方法。关于硬件的良好阅读材料可以在这里找到：

数字信号处理器尽管是维基页面，但引用值得一看，有效地执行FFT计算的硬件。

一种新的管道FFT处理器方法何守胜; Mats Torkelson; 这是我喜欢的一种方法，因为它展示了处理器内部发生的情况。

高效的本地管道FFT处理器杨亮; 张科伟; 刘红霞; 黄进; 黄世坦;

这些论文真正展示了实现FFT时的复杂性，然而流水线处理的过程使得操作可以在几个时钟周期内完成。这就是为什么实时视觉系统使用FPGA（专门设计处理器，可以设计实现一组任务）作为平台的原因，因为它们可以在架构中设计非常并行，并且流水线更容易实现。

尽管我必须提到，对于图像的FFT，实际上使用的是FFT2，这是水平平面和垂直平面的FFT，以免您在查找参考资料时混淆。我不能说我对方程式的实现和FFT的实现有专业知识，我已经尝试找到好的指南，但是找到一个好的指南非常困难，以至于我还没有找到一个（至少我能理解的）。也许有一天我会理解它们，但现在我很好地理解了它们的工作原理以及可以预期的结果类型。

除此之外，如果您想要实现自己的版本或了解其工作原理，我无法提供更多帮助，现在是时候去图书馆了，但我警告您，opencv代码已经被优化得非常好了，您将难以提高其性能，不过谁知道您可能会找到获得更好结果的方法。祝您一切顺利，好运！

克里斯