java - 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' 760 次操作，其中循环遍历模板的每个像素(另外 245'760 次操作)，因此在您在循环中添加任何数学之前，您已经拥有 (245'760 x 245'760) 60'397'977'600 次操作。超过 600 亿次操作仅用于遍历您的图像 更令人惊讶的是机器可以执行此操作的速度之快。

但是请记住它的 245'760 x (245'760 x Maths Operations) 所以还有更多的运算。

现在 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
蔡杜明；林建大；
模式识别字母
第 24 卷，第 15 期，2003 年 11 月，第 2625-2631 页

Template Matching using Fast Normalised Cross Correlation
凯·布里切尔；乌维·D·哈内贝克；

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-difference
弗里梅尔，B.H.； Bohs, L.N.; Trahey, G.E.；
超声波研讨会，1995 年。 session 录。，1995 年 IEEE

A Class of Algorithms for Fast Digital Image Registration
巴尼亚，丹尼尔一世；西尔弗曼，哈维 F.；
计算机，IEEE Transactions，1972 年 2 月

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

Digital signal processor
尽管 Wiki 页面上的引用资料值得一看，但实际上这是执行 FFT 计算的硬件

A new Approach to Pipeline FFT Processor
何寿生；马茨·托克尔森；
我的最爱，因为它显示了处理器内部发生的事情

An Efficient Locally Pipelined FFT Processor
梁阳;张可伟;刘红霞;金煌;黄石潭；

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

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

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

克里斯