模板匹配上的 OpenCV 性能

image templates java opencv template-matching

2022-09-03 08:54:30

我正在尝试基本上在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 x 640）。这持续了很长时间。openCV是否使用现成函数cvMatchTemplate（）更快地执行模板匹配？

答案 1

你会发现 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）来工作，其中构成像素强度变化的信号被分割成每个相应的波形。该方法很难很好地解释，但图像被转换为复数的信号表示。如果您想了解更多信息，请在护目镜上搜索快速傅里叶变换。现在，在模板上执行相同的操作，形成模板的信号用于从图像中过滤掉任何其他信号。

简单来说，它隐含图像中与模板不具有相同功能的所有特征。然后使用逆快速傅里叶变换将图像转换回来，以生成高值表示匹配，低值表示相反的图像。此图像通常被归一化，因此 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信号之间的相关性，根据我的经验，相关系数往往会产生更好的结果，并且更容易找到参考。平方差的总和是另一种可用于可比较结果的方法。我希望其中一些有所帮助：

用于缺陷检测的快速归一化互相关蔡杜明;林建塔;《模式识别信》第 24 卷，第 15 期，2003 年 11 月，第 2625-2631 页

使用快速归一化互相关的模板匹配凯·布里切尔;Uwe D. Hanebeck;

二维斑点跟踪技术的相对性能：归一化相关、非归一化相关和绝对差弗里梅尔;博斯;特拉希;超声波研讨会，1995年。会议记录，1995年IEEE

一类用于快速数字图像配准的算法巴内亚、丹尼尔一世;西尔弗曼、哈维·
计算机，IEEE事务，1972年2月

通常倾向于使用这些方法的规范化版本，因为任何等于1的东西都是匹配的，但是如果没有对象存在，您可能会得到误报。该方法工作速度很快，仅仅是因为它在计算机语言中被激发的方式。所涉及的操作非常适合处理器架构，这意味着它可以在几个时钟周期内完成每个操作，而不是在几个时钟周期内移动内存和信息。处理器多年来一直在解决FFT问题，我知道，就像我说的，有内置的硬件可以做到这一点。基于硬件总是比软件快，模板匹配的统计方法是基于基础软件的。硬件的良好阅读可以在这里找到：

数字信号处理器虽然Wiki页面的引用值得一看，但这是执行FFT计算的硬件

流水线 FFT 处理器的新方法何秀生;马茨·托克尔森;我最喜欢的，因为它显示了处理器内部发生的事情

高效的本地流水线FFT处理器梁洋;张克伟;刘红霞;黄金;黄石潭;

这些论文确实显示了FFT在实现时有多复杂，但是该过程的管道衬里允许在几个时钟周期内执行操作。这就是基于实时视觉的系统利用FPGA（特别是设计处理器，您可以设计它来实现设定的任务）的原因，因为它们可以在架构中设计得非常并行，并且管道衬砌更容易实现。

虽然我必须提到，对于图像的FFT，您实际上是使用FFT2，它是水平平原的FFT和垂直平原的FFT，因此当您找到对它的引用时不会造成混淆。我不能说我对方程如何实现和FFT的实现有专业知识，我试图找到好的指南，但找到一个好的指南非常困难，所以我还没有找到一个（至少我不能理解一个）。有一天，我可能会理解它们，但我知道我对它们的工作原理以及可以预期的结果有很好的理解。

除此之外，如果你想实现自己的版本或了解它是如何工作的，我真的不能帮助你更多，现在是时候打这个库了，但我警告你，opencv代码已经优化得很好，你将很难提高它的性能，但是谁知道你可能会找到一种方法来获得更好的结果，祝你好运

克里斯

答案 2