模板匹配的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数学运算),所以还有更多的操作.

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

简单来说,它会抑制图像中与模板功能不同的所有功能.然后使用快速傅里叶逆变换将图像转换回来以产生图像,其中高值意味着匹配而低值意味着相反.这个图像经常被归一化,所以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; Uwe D. Hanebeck;

二维散斑跟踪技术的相对性能:归一化相关,非归一化相关和和 - 绝对差 Friemel,BH; Bohs,LN; Trahey,GE; Ultrasonics Symposium,1995.Proceedings.,1995 IEEE

一种用于快速数字图像配准 Barnea 的算法,Daniel I.Silverman,Harvey F.;
计算机,IEEE交易于1972年2月

通常倾向于使用这些方法的规范化版本,因为等于1的任何东西都是匹配,但是如果不存在对象,则可以得到误报.该方法由于其在计算机语言中的激发方式而简单快速地工作.所涉及的操作对于处理器架构来说是理想的,这意味着它可以在几个时钟周期内完成每个操作,而不是在几个时钟周期内移动存储器和信息.处理器多年来一直在解决FFT问题,并且就像我说有内置硬件这样做.基于硬件总是比软件更快,模板匹配的统计方法基于基本软件.可以在这里找到良好的硬件阅读:

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

一种新的流水线FFT处理器 Shousheng He; Mats Torkelson; 我最喜欢的,因为它显示了处理器内部发生的事情

一种高效的局部流水线FFT处理器 梁洋; 张可伟; 刘红霞; 金煌; 石潭黄;

这些论文真实地展示了FFT实现时的复杂程度,但是该过程的管道衬里允许在几个时钟周期内执行操作.这就是基于实时视觉的系统利用FPGA(特别是您可以设计用于实现设定任务的设计处理器)的原因,因为它们可以在架构中设计得非常平行,并且管道衬里更容易实现.

虽然我必须提到,对于图像的FFT,你实际上使用的是FFT2,它是水平平面的FFT和垂直平面的FFT,所以当你找到它的参考时就没有混淆了.我不能说我对方程如何实现以及FFT的实现有专业知识我试图找到好的指南但找到一个好的指南是非常困难的,我还没有找到一个(我不能理解一个最小).有一天,我可能会理解他们,但是因为知道我对他们的工作方式以及可以预期的结果有了很好的理解.

除此之外,如果您想要实现自己的版本或了解它是如何工作的,我无法帮助您更多时间来访问库但我警告您opencv代码已经过如此优化,您将难以提高其性能但是谁知道你可能找到一种方法来获得更好的结果和祝你好运

克里斯