基于Haar小波和形状模板的图像快速匹配算法*

白冰峰，温秀兰，张中辉

(南京工程学院 自动化学院，南京 211167)

基于Haar小波和形状模板的图像快速匹配算法*

白冰峰，温秀兰，张中辉

(南京工程学院 自动化学院，南京 211167)

针对传统的模板匹配方法在低对比度的图像中匹配不到目标物体和匹配计算量大等问题，提出一种基于离散Haar小波变换和形状模板的图像快速匹配算法。首先，使用Haar小波对图像进行分解操作，将分解的低频信号重构得到压缩图像，以减少匹配计算量；其次，使用形状模板对压缩图像进行匹配，设计出Haar小波图像压缩和形状模板匹配相结合的算法及程序。最后，经大量实验结果证实：所提出的算法不仅匹配速度快，精度高，而且匹配结果不受遮蔽、混乱和非线性光照变化等情况的影响，适宜于在复杂环境中进行图像提取、工件识别等。

小波变换；形状模板；图像匹配

0 引言

随着计算机技术的快速发展和广泛应用，计算机视觉在工业机器人控制、自主汽车或移动机器人导航、医学图像分析、制造业自动检测等领域得到众多应用。其中模板匹配是计算机视觉需要解决的关键问题，如何在干扰和遮蔽情况下进行模板匹配一直是模板匹配的关键。多年来，研究者们提出了多种图像模板匹配算法。Borgefors G提出了计算模板边缘点与离它最近的图像边缘点之间的均方差最小的方法，这种通过计算图像距离的方法提高了匹配效率，而且不受光照变化和混乱影响，但对遮挡很敏感[1]。Rucklidge提出了一种改进的Hausdorff算法，这种算法对小面积的遮挡有很好的适应性，但是计算量很大[2]。这些算法都存在一个缺点，都需要在图像中提取边缘，导致目标匹配算法只能适用于光照变化很小的情况。

本文提出了基于离散Haar小波变换和形状模板的图像快速匹配算法。首先采用Haar小波变换对图像进行压缩，然后利用canny算子获取模板图像和待搜索图像边缘信息，并计算其方向向量[3]，根据定义的相似度量[4]进行匹配。其中采用Haar小波压缩图像，匹配算法速度快，且不受遮挡、混乱和非线性光照的影响。实验表明，基于离散Haar小波变换和形状模板的图像快速匹配算法的视觉系统可以快速匹配到目标物体，并且利用相似度量进行匹配，确保了匹配的准确性。

1 小波变换和Haar小波

在整个高分辨率图像中计算相似度量也是一个计算量庞大的工程，所以提出基于Haar小波的图像压缩策略，以减少计算量，提高匹配速度。小波变换[5]的含义：将基本小波函数ψ(t)做位移τ后，再在不同尺度α下，与待分析信号X(t)做内积：

(1)

等效频域表示为：

(2)

式中X(t),ψ(w)分别是x(t),ψ(t)的傅立叶变量，α和τ分别为伸缩因子和平移因子[6]。

Haar小波在时域上是不连续的，但在图像处理中，具有图像压缩比高，处理速度快和图像分解简单等优点。通过Haar小波变换后得到低频和高频图像，因为图像特征是由低频部分决定的，所以保留低频部分，去除高频部分。此外，本文采用阈值的设置，对图像进行量化处理。然后设置不同阈值得到分解图像含“0”数目以及图像文件的大小。原始图像cameaman.tif在阈值25、85情况下1和3级分解的低频信号重构得到的图像如图1所示。

图1 Haar小波分解重构图像示例

原始图像(图1a)在阈值T=25的Haar小波1级和3级分解低频信号重构得到的图像分别为图1b和图1c，在阈值T=85的Haar小波1级和3级分解低频信号重构得到的图像分别为图1d和图1e。从图1d和图1e可以明显看出图像模糊了，使用低频信号重构图像，去除了高频信号和高频中含有噪声的部分，不仅提高了匹配效率，而且减少了噪声干扰。

2 基于形状模板的图像快速匹配

2.1 相似度量

(3)

如果图像模板中一个特征值丢失，噪声将随机生成一个方向向量，这些方向向量平均起来将不会对总和产生影响，所以相似度量不会受到遮挡和混乱的影响。

公式(1)中提供的相似度量算法并不真正能够不受光照变化的影响，因为当使用边缘提取算法计算方向向量时，方向向量的长短取决于图像的亮度，所以需要一个已经定义合适范围的相似度量指定一个阈值确定模板是否出现在图像中。下式中的相似度量可以实现这个要求：

(4)

因为将方向向量进行归一化，所有的向量长度都变为1，所以相似度量不受任意光照变化的影响。又因为如果图像中某个特征丢失，噪声将导致一个随机的方向向量，这些方向向量平均起来不会对总和造成影响，所以此相似度量不受遮挡和混乱的影响。综上所述，所求的相似度量不受遮挡、混乱以及光照变换的影响。

2.2 快速匹配原理

公式(4)和公式(5)中归一化相似度量将返回一个小于1的数作为潜在匹配对象的分值。匹配分值提供了判断数据，如果分值为1则表示模板与图像之间完美一致，如果物体有30%被遮挡，平均匹配分值不会超过0.7。在匹配图像过程，对图像中每个点进行一次全面归一化计算，计算量大，并且大量的点是无用的。所以设置用户定义的阈值smin，仅仅求出潜在匹配位置的达到用户定义阈值smin的相似度量。使用sj表示累计到模板的第j个元素时点积的总和，然后进行归一化计算，其公式如下：

(5)

2.3 图像匹配过程

从参考图像选取含目标物体的感兴趣区域生成其模板，使用Canny滤波器处理模板搜索图像,并计算出边缘上点的方向向量，构建模板并使用2×2均值滤波器平滑。对压缩处理的图像搜索进行相似性度量匹配,并返回潜在匹配点、匹配分值及其变换参数,并将模板进行相应的变换。可以通过设置匹配阈值smin，并且根据上述搜索停止标准，匹配到目标物体并终止搜索。

3 算法及程序设计

图2 算法程序流程图

4 实验与分析

根据上述原理和流程，在VC++平台下设计相应的算法程序。本次实验采用德国的basler像素为500万的工业相机进行图像采集，为了保证采集图像的清晰和完整，通过实验找到合适阈值。实验的图像大小为4922KB,阈值为5、25、45和85的1～3级Haar小波分解和不同阈值和级数分解下图像中系数含“0”数目和文件大小曲线图如图3所示。

由图3可以清楚地看出，在固定阈值时，Haar小波分解级数越大，低频信号重构得到的图像被压缩的越小；在Haar小波分解级数固定时，阈值越大，图像被压缩的越小。图像被压缩的越小，越有利于图像的传输和处理，但是随着阈值不断增大，图像中矩阵“0”的区域面积也将扩大，图像越来越模糊，可能造成图像压缩后失真。为了保证图像压缩后不失真，又尽可能地使得图像被压缩的小，需要选择合适的阈值。本文通过实验，对阈值5～40之间的值分别做了测试，阈值为5～20时，在相同的Haar小波分解级数下，图像压缩效果不明显；阈值达到35之后，图像的压缩会出现失真现象。所以本实验选择阈值为25，在固定阈值下，对图像进行Haar小波的一级、二级和三级分解。对重构得到的图像的图像进行基于形状模板的匹配，匹配结果如图4所示。

图3 Haar小波变换实验结果

(a)原图 (b)模板

(c)原图匹配 (d)一级分解重构图像匹配

(e)二级分解重构图像匹配 (f)三级分解重构图像匹配图4 匹配结果

从图4可以看出通过形状模板匹配，原图和在阈值T=25时的Haar小波分级得到的图像都可以识别出来，但是匹配所用时间相差很大，没有经过Haar小波压缩的原图匹配时间为94.3ms，接近经过Haar小波三级分解得到图像匹配所用时间的3倍。但是从图5f中明显可以看出，Haar小波三级分解重构得到的图像匹配中有些特征缺失，可能会影响匹配效果。所以本文对上述四种类型的图像做了50次匹配实验，比较它们的匹配成功率和平均匹配时间，比较结果见表1。

表1 不同类型图像的匹配结果

从表1可以看出Haar小波三级分解重构得到的图像匹配时间最短，而且原图匹配所用时间几乎为Haar小波三级分解重构得到图像匹配的3倍。但是经过Haar小波三级分解重构得到图像有些特征缺失，影响了匹配结果。所以本文为了保证匹配结果准确性，又满足快速匹配的系统要求，选择阈值T为25，分解级数为二的Haar小波变换进行压缩图像。

采集200幅图像，进行Haar小波图像压缩后，先提取标准图像的模板，然后在光照不均匀、混乱和遮蔽的情况下各做50次实验，匹配的结果如图5所示。运算结果见表2。

(a)标准图像 (b)标准图像截取的模板

(c)光照不均匀

(d)混乱 (e)遮挡

图像类型图像大小(KB)匹配次数匹配成功次数成功率(%)平均匹配时间(ms)正常505010034．3(c)50499835．6(d)50489634．5(e)505010033．6

从不同环境中匹配的结果来看，对阈值T为25，分解级数为二的Haar小波变换的压缩图像进行匹配，所用时间比没有压缩的图像匹配减少了接近3倍，而且在光照不均匀、混乱和遮蔽的情况下，图像都能被成功的匹配出来，匹配的准确度很高。

5 结论

本文针对传统模板匹配计算量大和在低对比度情况下匹配不到目标物体问题，利用Haar小波变换对图像进行压缩处理，把高分辨率的图像压缩成分辨率较低的图像，减少了匹配特征点的计算，大大提高了匹配速度。通过计算相似度量，得到匹配分值，确保匹配不受遮挡、混乱以及光照变化的影响，确保了匹配的准确性。需要指出的是，合适的阈值是通过大量的实验得到的，还需要寻找更好的方法获得合适的阈值，这将是下一步的研究方向。

[1] 张代林,陈文广,谢经明,等. 基于形状模板匹配的印刷品缺陷检测[J]. 机械与电子,2013(12): 40-43.

[2] 杨少荣,吴迪靖,段德山.机器视觉算法与应用[M]. 北京:清华大学出版社,2009.

[3] ELMUNIM H A, FARAG A A. Shape representation and registration using vector distance functions [C]//CVPRp07: Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2007: 1-8.

[4] 赵振民,彭国华,符立梅. 基于形状模板的快速高精度可靠图像匹配[J]. 计算机应用,2010,30(2): 441-444.

[5] 刘佳嘉,何小海,陈为龙. 一种结合小波变换的SIFT特征图像匹配算法[J]. 计算机仿真,2011,28(1):257-260,335.

[6] 梁忠伟,叶邦彦,刘晓初,等. 基于矩阵二阶矩和小波分解的紊流图像融合灰色关联度评价[J]. 组合机床与自动化加工技术,2011(8):1-4,8.

[7] DELMASP, FARBGG, SHORINA, et al. Robust leas-t squares image matching in the presence of outliers [C]//CAIP 2007: Proceedings of the12th International Conference on Computer Analysis of Images and Patterns, LNCS 4673. Berlin: Springer, 2007: 776-783.

(编辑 李秀敏)

Fast Image Matching Algorithm Based on Wavelet and Shape Template

BAI Bing-feng, WEN Xiu-lan, ZHANG Zhong-hui

(School of Automation，Nanjing Institute of Technology，Nanjing 211167,China)

According to these problems that the target object is not matched in low-contrast images and large matching calculation is needed in the method of traditional template matching, a fast image matching algorithm based on discrete Haar wavelet transform and shape template is proposed. Firstly, the image is decomposed by Haar wavelet, then the compressed image is reconstructed through the low frequency signal of decomposition to reduce computation cost of image matching and the compressed image is matched by shape template, the algorithm and program of Haar wavelet image compression and shape template match are designed. Finally, a large number of experimental results show that the proposed matching algorithm not only has fast speed and high accuracy, but also the matching results are not influenced by shelter, chaos, the changes of nonlinear illumination and so on. And it is applied to image matting and workpiece recognition in the complex environment.

wavelet transform; template match; image matching

1001-2265(2017)02-0037-04

10.13462/j.cnki.mmtamt.2017.02.010

2016-03-06；

2016-04-10

国家自然科学基金项目(51675259)；江苏省“333人才工程”项目资助：江苏省普通高校专业学位研究生创新计划项目(SJLx16_066)

白冰峰(1991—)，男，江苏徐州人，南京工程学院硕士研究生，研究方向为图像处理，(E-mail)842344646@qq.com；通信作者：温秀兰(1966—)，女，内蒙古丰镇人，南京工程学院教授，博士，研究方向为计量与测试技术、智能计算、机器视觉及其应用，(E-mail)zdhxwxl@njit.edu.cn。

TH161;TG506

A