OpenCV在模板匹配方面的性能 [英] OpenCV performance on template matching

问题描述

我正在尝试基本上在Java上进行模板匹配.我使用简单的算法来找到匹配项.这是代码:

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

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()更快地执行模板匹配?

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()?

推荐答案

您会发现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亿次操作就可以遍历您的图像.更令人惊讶的是，如此快速的机器能够做到这一点.

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.

但是请记住它的245'760 x(245'760 x数学运算)，所以还有更多的运算.

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

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

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.

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

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.

请注意，如果它们的对象不在图像中并且被规范化，则会发生错误检测，因为计算出的最大值将被视为匹配项.关于该方法的工作方式以及它可能会产生的好处或问题，我可以花很多年的时间，但...

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...

此方法之所以如此快的原因是:1)opencv是高度优化的c ++代码. 2)fft功能很容易让您的处理器处理，因为大多数功能都可以在硬件中执行此操作. GPU图形卡旨在每秒执行数百万次ftf操作，因为这些计算在高性能游戏图形或视频编码中同样重要. 3)所需的操作量要少得多.

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.

在夏季，统计模板匹配方法比较缓慢且需要一定时间，而opencv FFT或cvMatchTemplate()快速且高度优化.

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

如果不存在对象，则统计模板匹配不会产生错误，而opencv FFT会发生错误，除非在应用时小心.

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

我希望这对您有一个基本的了解并回答您的问题.

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

欢呼

克里斯

进一步回答您的问题:

cvMatchTemplate可以与CCOEFF_NORMED和CCORR_NORMED以及SQDIFF_NORMED一起使用，包括它们的非标准化版本. 此处显示了可以预期的结果并给出了要使用的代码.

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

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

这三种方法得到了很好的引用，并且可以通过 Google学者获得许多论文. .我提供了以下几篇论文.每个人只是简单地使用一个不同的方程式来查找形成模板的FFT信号与图​​像中存在的FFT信号之间的相关性，根据我的经验，相关系数往往会产生更好的结果，并且更容易找到参考.平方差之和是可以与可比较结果一起使用的另一种方法.我希望其中一些帮助:

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:

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

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

使用快速归一化互相关的模板匹配 Kai Briechle； Uwe D. Hanebeck；

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

二维斑点的相对性能-跟踪技术:归一化相关性，非归一化相关性和绝对和差 B.H.弗里梅尔； L.N. Bohs;特拉希(G.E.)； 超声学研讨会，1995年.会议论文集，1995年IEEE

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

用于快速数字图像的一类算法注册 Barnea，丹尼尔一世；西弗曼(Silverman)，哈维(Harvey F.)；
计算机，1972年2月的IEEE Transactions

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

通常首选使用这些方法的规范化版本，因为等于1的任何内容都是匹配项，但是如果不存在对象，则可能会得到误报.该方法之所以能够快速运行，完全是由于采用计算机语言来激发它的方式.所涉及的操作是处理器体系结构的理想选择，这意味着它可以在几个时钟周期内完成每个操作，而无需在多个时钟周期内转移存储器和信息.处理器解决FFT问题已经有很多年了，就像我说过的那样，内置硬件可以做到这一点.基于硬件的速度总是快于软件，并且模板匹配的统计方法基于基本的软件.可以在这里找到有关硬件的不错的阅读材料:

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:

数字信号处理器 尽管Wiki页面中的参考值得一看，但实际上这是执行FFT计算的硬件

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

管道FFT处理器的新方法 何寿生； Mats Torkelson； 我的最爱，因为它显示了处理器内部发生的事情

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

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

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

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

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，您实际上使用的是FFT2，即水平平原的FFT和垂直平原的FFT，因此当您引用它时不会感到困惑.我不能说我对方程的实现方式和FFT的实现有专业的知识，我试图找到好的指南，但是很难找到一个好的指南，以至于我还没有找到一个(我无法理解的一个指南).至少).有一天，我可能会理解它们，但是我知道他们对它们的工作方式以及可以预期的结果有很好的了解.

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.

除此之外，如果您想实现自己的版本或了解它的工作原理，我真的无法为您提供更多帮助，现在是时候访问该库了，但是我警告您，opencv代码已经过优化，您将很难提高它的性能.性能，但是谁知道您可能想出一种方法来获得更好的结果，祝您好运

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在模板匹配方面的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！