【信息科学与控制工程】

模板匹配的一种快速算法

戴宪策，刘昌锦

(新星技术研究所，合肥230031)

摘要：图像匹配是计算机视觉中的重要应用之一，常用的算法是基于归一化相关系数的模板匹配算法；针对原有算法计算量大，匹配时间长的问题，提出了基于降采样和分块快速傅里叶变换(FFT)的方法，对原始算法进行了改进，并设计了两组对比实验进行验证；结果证明算法不仅匹配准确，对外界条件具有良好的适用性，而且匹配时间缩短为原始算法的1/5，提高了匹配速度。

关键词：模板匹配；降采样；分块FFT

收稿日期：2014-07-10

作者简介：戴宪策(1990—)，男，硕士研究生，主要从事立体视觉研究。

doi:10.11809/scbgxb2015.01.031

中图分类号：TP391.4

文章编号：1006-0707(2015)01-0111-04

本文引用格式：戴宪策，刘昌锦.模板匹配的一种快速算法[J].四川兵工学报，2015(1):111-113.

Citationformat:DAIXian-ce,LIUChang-jin.FastTemplate-MatchingAlgorithm[J].JournalofSichuanOrdnance,2015(1):111-113.

FastTemplate-MatchingAlgorithm

DAIXian-ce,LIUChang-jin

(NewStarInstituteofAppliedTechnology,Hefei230031,China)

Abstract:Image matching is one of the important applications in computer vision. Common algorithm of template-matching is based on normalized correlation coefficient. However, the origin algorithm had the problem of large amount of calculation and long matching time. In order to optimize it, a new method based on down sampling and blocking FFT was proposed. Two experiments were designed for comparison. The results show that the new algorithm not only has an accurate matching result and a fine flexibility of the environment, but also can reduce the matching time by 4/5.

Keywords:templatematching;downsampling;partitioningFFT

根据已知模板图像，在另外一幅图中寻找子图像的过程称为图像匹配[1]。图像匹配是计算机视觉中的一个重要组成部分，在图像拼接、目标检测与跟踪、视频稳定、视频监控等领域具有广泛的应用。匹配算法中的重要性能指标是结果的准确性和算法的速度，基于归一化相关系数的模板匹配是一种常用的算法，结果准确，稳定性好。但是在当前图像质量越来越高，像素点数越来越多的情况下，算法在匹配速度方面还有待提高。本文据此提出了基于降采样和分块FFT的快速匹配算法。

1算法原理与实现

1.1算法原理

(1)

从表达式中可以看出，直接计算相关系数需要大量的乘法和加法，模板图像和待匹配图像越大，所需加法和乘法的数量就越多，而且增长急剧。……