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

Answer 1

您会发现 openCV cvMatchTemplate() 比您实现的方法快得多。您创建的是一个统计模板匹配方法。它是最常见且最容易实现的，但在大图像上速度非常慢。让我们看一下基本的数学知识，你有一个 768x1280 的图像，你循环遍历每个像素减去边缘，因为这是你的模板限制，所以 (768 - 384) x (1280 - 640) 384 x 640 = 245'因此，在循环中添加任何数学之前，需要循环遍历模板的每个像素（另外 245'760 次操作）的 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 信号之间的相关性，根据我的经验，相关系数往往会产生更好的结果，并且更容易找到参考。平方差之和是另一种可用于获得可比结果的方法。我希望其中一些有所帮助：

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

使用快速归一化互相关进行模板匹配< /a>
凯·布里奇勒；乌韦·D·哈内贝克；

二维散斑跟踪技术的相对性能：归一化相关性、非归一化相关性和绝对差值
弗里梅尔，BH；博斯，LN；特拉希，通用电气；
超声波研讨会，1995。会议记录。，1995 IEEE

A快速数字图像配准算法类
巴尼亚，丹尼尔一世；西尔弗曼，哈维·F.；
计算机，IEEE Transactions，1972 年 2 月

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

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

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

高效的本地流水线 FFT 处理器
梁阳;张克伟;刘红霞;黄金;黄世坦;

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

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

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

克里斯