模板匹配的一种快速算法

2015-12-23戴宪策,刘昌锦

兵器装备工程学报 2015年1期

【信息科学与控制工程】

模板匹配的一种快速算法

戴宪策，刘昌锦

(新星技术研究所，合肥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)

从表达式中可以看出，直接计算相关系数需要大量的乘法和加法，模板图像和待匹配图像越大，所需加法和乘法的数量就越多，而且增长急剧。每到新的一点，相关值、平方和等参数需要重新计算，十分浪费。因此，快速算法十分必要。傅里叶变换可以将相关计算转化到频域的相乘，其快速算法能够大大减少计算量[3-5]。能量值的计算可以通过一次计算模板图像和待匹配图像的平方积分图像来减少计算量[3,6]。

1.2傅里叶变换

傅里叶变换是由法国数学家傅里叶提出的，在许多领域有着非常广泛的应用。大小为M×N的二维数字图像f(x,y) 与其傅里叶变换F(u,v)之间的关系为

快速傅里叶变换是傅里叶变换的快速算法，是由Cooley和Turkey在1965年提出的。快速傅里叶变换大大简化了傅里叶变换的所需的计算量。其核心是蝶形运算单元，其结构图1所示。

图1　第级蝶形运算单元

f(x,y) ∘h(x,y)⟺F*(u,v)H(u,v)

其中，F*(u,v)表示F(u,v)的共轭。可以利用这一关系简化计算。

1.3平方积分图像

平方积分图像是原图像像素值平方的累加图像，平方积分图像中每一点的值等于原图像自左上角开始到该点的矩形框中所有点平方和的相加，即：

平方积分图像可以由下列公式快速计算：

c(x,y)=c(x,y-1)+I2(x,y)

II(x,y)=II(x-1,y)+c(x,y)

其中，c(x,y)表示的是待匹配图像中(x,y)所在列纵坐标不大于y的点像素值的平方和。利用平方积分图像，可以很快计算待匹配图像的能量值：

II(x+i,y+j)-II(x+i,y)-II(x,y+j)

快速傅里叶变换和积分图像快速算法的应用，可以在很大程度上减少计算量，增加计算速度，但是随着图像质量越来越高，简单应用快速傅里叶变换和积分图像快速算法仍不能满足要求，因此本文提出了降采样和分块FFT的优化方法。

2算法优化

2.1降采样

现在的成像设备，如相机、手机摄像头、网络摄像头等都有很高的像素点数，成像质量高，纹理丰富，细节清晰，符合人眼视觉的需要。但是对于计算机处理却不一定是必须的。低质量、单通道的灰度图像也能进行完成匹配功能。因此，在匹配之前可以对图像进行降采样的预处理，在保证匹配正确的基础上，能够进一步缩小计算量和存储空间。

以2倍降采样为例，通过下列公式对待匹配图像I(x,y)和模板图像T(x,y)进行降采样

此时匹配时所需的存储空间是原来的1/4，快速傅里叶变换所需的计算量是原来的1/5左右。极大的缩短了计算时间。降采样的结果与准确结果之间可能存在偏差，但是根据第3部分的实验结果，产生的偏差在可接受范围内。

2.2分块傅里叶变换

一般来说，模板图像是待匹配图像中的一小部分，两幅图像尺寸上有很大的比例关系。在运用快速傅里叶变换进行相关系数计算的时候，需要对模板图像进行大量的补零操作，使其和待匹配图像的大小一致，这不仅导致了计算量的浪费，而且带来了存储空间的增加。对待匹配图像进行分块处理，在保证相关系数结果一致的基础上，不仅能够减少存储空间，而且还能够进一步提高计算速度。