java OpenCV 在模板匹配上的表现

OpenCV performance on template matching

提问by AraZZ

I'm trying to do template matching basically on java. I used straightforward algorithm to find match. Here is the code:

我正在尝试基本上在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;
    }
}

But this is very slow approach. I tested 2 images (768?×?1280) and subimage (384 x 640). This lasts for ages. Does openCV perform template matching much faster or not with ready function cvMatchTemplate()?

但这是非常缓慢的方法。我测试了 2 张图像 (768?×?1280) 和子图像 (384 x 640)。这持续了很多年。openCV 是否使用就绪函数 cvMatchTemplate() 更快地执行模板匹配？

回答by Chris

You will find openCV cvMatchTemplate() is much mush quicker than the method you have implemented. What you have created is a statistical template matching method. It is the most common and the easiest to implement however is extremely slow on large images. Lets take a look at the basic maths you have a image that is 768x1280 you loop through each of these pixels minus the edge as this is you template limits so (768 - 384) x (1280 - 640) that 384 x 640 = 245'760 operations in which you loop through each pixel of your template (another 245'760 operations) therefore before you add any maths in your loop you already have (245'760 x 245'760) 60'397'977'600 operations. Over 60 billion operations just to loop through your image It's more surprising how quick machines can do this.

您会发现 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 亿次操作仅用于遍历您的图像 更令人惊讶的是机器可以执行此操作的速度之快。

Remember however its 245'760 x (245'760 x Maths Operations) so there are many more operations.

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

Now cvMatchTemplate() actually uses the Fourier Analysis Template matching operation. This works by applying a Fast Fourier Transform (FFT) on the image in which the signals that make up the pixel changes in intensity are segmented into each of the corresponding wave forms. The method is hard to explain well but the image is transformed into a signal representation of complex numbers. If you wish to understand more please search on goggle for the fast fourier transform. Now the same operation is performed on the template the signals that form the template are used to filter out any other signals from your image.

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

In simple it suppresses all features within the image that do not have the same features as your template. The image is then converted back using a inverse fast fourier transform to produce an images where high values mean a match and low values mean the opposite. This image is often normalised so 1's represent a match and 0's or there about mean the object is no where near.

简单来说，它会抑制图像中与模板不具有相同特征的所有特征。然后使用逆快速傅立叶变换将图像转换回以生成图像，其中高值表示匹配而低值表示相反。该图像通常被标准化，因此 1 表示匹配，而 0 或大约表示对象不在附近。

Be warned though if they object is not in the image and it is normalised false detection will occur as the highest value calculated will be treated as a match. I could go on for ages about how the method works and its benefits or problems that can occur but...

但是请注意，如果它们的对象不在图像中并且归一化，则会发生错误检测，因为计算出的最高值将被视为匹配项。我可以继续谈论该方法的工作原理及其好处或可能出现的问题，但是......

The reason this method is so fast is: 1) opencv is highly optimised c++ code. 2) The fft function is easy for your processor to handle as a majority have the ability to perform this operation in hardware. GPU graphic cards are designed to perform millions of fft operations every second as these calculations are just as important in high performance gaming graphics or video encoding. 3) The amount of operations required is far less.

这种方法如此之快的原因是：1）opencv 是高度优化的 C++ 代码。2) fft 函数对于您的处理器来说很容易处理，因为大多数处理器都能够在硬件中执行此操作。GPU 显卡旨在每秒执行数百万次 fft 操作，因为这些计算在高性能游戏图形或视频编码中同样重要。3）所需的操作量要少得多。

In summery statistical template matching method is slow and takes ages whereas opencv FFT or cvMatchTemplate() is quick and highly optimised.

在总结中，统计模板匹配方法很慢并且需要很长时间，而 opencv FFT 或 cvMatchTemplate() 快速且高度优化。

Statistical template matching will not produce errors if an object is not there whereas opencv FFT can unless care is taken in its application.

如果对象不存在，统计模板匹配不会产生错误，而 opencv FFT 可以，除非在其应用中小心。

I hope this gives you a basic understanding and answers your question.

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

Cheers

干杯

Chris

克里斯

[EDIT]

[编辑]

To further answer your Questions:

进一步回答您的问题：

Hi,

你好，

cvMatchTemplate can work with CCOEFF_NORMED and CCORR_NORMED and SQDIFF_NORMED including the non-normalised version of these. Hereshows the kind of results you can expect and gives your the code to play with.

cvMatchTemplate 可以与 CCOEFF_NORMED 和 CCORR_NORMED 和 SQDIFF_NORMED 一起使用，包括这些的非规范化版本。此处显示了您可以预期的结果类型，并提供了您可以使用的代码。

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

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

The three methods are well cited and many papers are available through Google scholar. I have provided a few papers bellow. Each one simply uses a different equation to find the correlation between the FFT signals that form the template and the FFT signals that are present within the image the Correlation Coefficient tends to yield better results in my experience and is easier to find references to. Sum of the Squared Difference is another method that can be used with comparable results. I hope some of these help:

这三种方法都被很好地引用了，很多论文都可以通过谷歌学者找到。我在下面提供了一些文件。每个人都简单地使用不同的方程来找到形成模板的 FFT 信号与图像中存在的 FFT 信号之间的相关性，根据我的经验，相关系数往往会产生更好的结果，并且更容易找到参考。平方差和是另一种可用于比较结果的方法。我希望其中一些有帮助：

Fast normalized cross correlation for defect detectionDu-Ming Tsai; Chien-Ta Lin; Pattern Recognition Letters Volume 24, Issue 15, November 2003, Pages 2625-2631

用于缺陷检测的快速归一化互相关Du-Ming Tsai；林建大；模式识别快报第 24 卷，第 15 期，2003 年 11 月，第 2625-2631 页

Template Matching using Fast Normalised Cross CorrelationKai Briechle; Uwe D. Hanebeck;

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

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-differenceFriemel, B.H.; Bohs, L.N.; Trahey, G.E.; Ultrasonics Symposium, 1995. Proceedings., 1995 IEEE

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

A Class of Algorithms for Fast Digital Image RegistrationBarnea, Daniel I.; Silverman, Harvey F.;
Computers, IEEE Transactions on Feb. 1972

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

It is often favoured to use the normalised version of these methods as anything that equals a 1 is a match however if not object is present you can get false positives. The method works fast simply due to the way it is instigated in the computer language. The operations involved are ideal for the processor architecture which means it can complete each operation with a few clock cycles rather than shifting memory and information around over several clock cycles. Processors have been solving FFT problems for many years know and like I said there is inbuilt hardware to do so. Hardware based is always faster than software and statistical method of template matching is in basic software based. Good reading for the hardware can be found here:

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

Digital signal processorAlthough a Wiki page the references are worth a look an effectively this is the hardware that performs FFT calculations

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

A new Approach to Pipeline FFT ProcessorShousheng He; Mats Torkelson; A favourite of mine as it shows whats happening inside the processor

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

An Efficient Locally Pipelined FFT ProcessorLiang Yang; Kewei Zhang; Hongxia Liu; Jin Huang; Shitan Huang;

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

These papers really show how complex the FFT is when implemented however the pipe-lining of the process is what allows the operation to be performed in a few clock cycles. This is the reason real time vision based systems utilise FPGA (specifically design processors that you can design to implement a set task) as they can be design extremely parallel in the architecture and pipe-lining is easier to implement.

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

Although I must mention that for FFT of an image you are actually using FFT2 which is the FFT of the horizontal plain and the FFT of the vertical plain just so there is no confusion when you find reference to it. I can not say I have an expert knowledge in how the equations implemented and the FFT is implemented I have tried to find good guides yet finding a good guide is very hard so much I haven't yet found one (Not one I can understand at least). One day I may understand them but for know I have a good understanding of how they work and the kind of results that can be expected.

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

Other than this I can't really help you more if you want to implement your own version or understand how it works it's time to hit the library but I warn you the opencv code is so well optimised you will struggle to increase its performance however who knows you may figure out a way to gain better results all the best and Good luck

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

Chris

克里斯