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 × 1280) 和子图像 (384 x 640)。这会持续很长时间。openCV 是否使用现成的函数 cvMatchTemplate() 更快地执行模板匹配？

4

1 回答 1

45

您会发现 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；建大林；模式识别快报第 24 卷，第 15 期，2003 年 11 月，第 2625-2631 页

使用快速归一化互相关 Kai Briechle 的模板匹配；乌维·D·哈内贝克；

二维散斑跟踪技术的相对性能：归一化相关、非归一化相关和和绝对差 Friemel，BH；博斯，LN；特拉希，通用电气；超声研讨会，1995 年。论文集，1995 年 IEEE

一种用于快速数字图像配准的算法 Barnea，Daniel I.；西尔弗曼，哈维 F.；
计算机，IEEE Transactions，1972 年 2 月

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

数字信号处理器 虽然是一个 Wiki 页面，但参考资料值得一看，实际上这是执行 FFT 计算的硬件

流水线 FFT 处理器的一种新方法 Shousheng He；马茨·托克尔森；我的最爱，因为它显示了处理器内部发生的事情

一种高效的本地流水线 FFT 处理器 Liang Yang；张可伟；刘红霞；金煌；黄石滩；

这些论文确实展示了 FFT 在实现时的复杂性，但是流程的流水线是允许在几个时钟周期内执行操作的原因。这就是基于实时视觉的系统使用 FPGA（特别是设计处理器，您可以设计用于实现一组任务）的原因，因为它们可以在架构中极其并行地设计，并且流水线更容易实现。

虽然我必须提到，对于图像的 FFT，您实际上使用的是 FFT2，它是水平平面的 FFT 和垂直平面的 FFT，因此当您找到对它的引用时不会混淆。我不能说我对方程的实现方式和 FFT 的实现方式有专业知识至少）。有一天我可能会理解它们，但因为知道我对它们的工作方式以及可以预期的结果有很好的理解。

除此之外，如果您想实现自己的版本或了解它是如何工作的，我真的无法为您提供更多帮助。是时候使用库了，但我警告您，opencv 代码优化得如此之好，您将难以提高其性能，但是谁知道你可能会想出一种方法来获得更好的结果，祝你好运

克里斯

于 2011-08-31T08:43:17.373 回答