模板匹配问题的动态规划算法实现

荣昕萌+傅博

摘要：模板匹配方法是图像检索、分割、拼接、检测等图像问题在关键区域匹配过程中常采用的处理方法，匹配结果的优劣将直接影响后续算法的结果。传统图像处理方法在采用模板匹配方法时，往往面临时间复杂度过高的问题。基于动态规划的程序设计策略是一种重要的算法设计策略，为存在最优子结构性质的实际问题提供了一种重要的解决途径。针对图像处理中的模板匹配问题进行分析，给出相应的动态规划解法，并对所给算法的复杂度进行分析和讨论。实验结果验证了所提方法的有效性。

关键词：动态规划；模板匹配；特征距离矩阵

DOIDOI：10.11907/rjdk.171142

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）06-0037-03

0 引言

在计算机领域，常需要将实验数据与预先设定好的模板进行匹配。图像处理领域中的图像检索、图像分割、图像拼接、图像检测、视频编码等，就需要运用到模板匹配技术。模板匹配技术在图像处理领域的具体应用可以简单分为两大类：基于特征点的匹配技术、基于像素灰度的匹配。基于特征点的匹配往往被更高级的机器视觉类任务采用，而在图像处理中，基于特征的匹配方法由于抽取的点、线、特征子等特征容易受到视角变换、遮挡等问题的干扰，会影响到最终匹配结果的质量，同时特征抽取方法的时间复杂度较高，对于实时性是一个挑战。基于像素灰度的模板匹配方法，只需要设定好匹配的模板尺寸与遍历方式，算法简洁、稳定性高，适合图像处理与计算机视觉问题中的底层预处理。但其也存在一些缺点，如噪声、光照引起的灰度变化，且运算数据量大，基于像素灰度的匹配算法也无法避免图像数据与模板匹配过程可能带来的高复杂度问题。

迄今为止，模板匹配技术已经被广泛应用到图像处理的实际问题中，并取得了一系列成果。例如，王倩倩[1]将模板匹配问题应用到藻类图像的识别问题中，李厚军[2]将模板匹配问题应用到眉毛的识别问题中，陈莹[3]将模板匹配方法用于增强微光图像，王正等[4]将模板匹配引入到图像编码中的调色板更正上，提高了图像编码效率，王志衡，郭超等[5]将模板匹配方法应用到了新闻图像字母行切分之中，张盼盼[6]等将模板匹配方法应用到了数字识别过程中，陈宁等[7]将该方法应用到集装箱识别与匹配的问题中。然而，采用上述方法在面临大数据量的数据时，也存在复杂度较高的问题。因此，如何进一步优化模板匹配问题有待进一步研究解决。

动态規划方法（Dynamic Programming）早期诞生于运筹学，是一种迭代求解最优的方法。近年来，动态规划方法作为算法设计策略中求解最优子结构的一种重要思想，被广泛引入到计算机问题求解之中。动态规划求解计算机问题的基本思想是，将待求解问题分解成若干个结构相同的子问题，在求解过程中保存已求解子问题的答案并在后续求解过程中，有效利用之前求解的答案协助当前问题求解。由于后续问题在求解过程中已经遇到了需要之前已经求过的子问题，因此大大提高了求解效率[8-11]。可以简单地将动态规划算法分为基于线性的动态规划算法、基于树形的动态规划算法、基于区域的动态规划算法、基于背包的动态规划算法。具体采用何种动态规划方法应针对具体问题作具体分析，例如，有学者[12-13]在语音识别与动作识别等具体领域尝试采用动态规划算法尝试优化求解。但往往只是将动态规划算法应用到某一具体问题，尚未对图像处理中的模板匹配问题进行动态规划算法实现。

综上，鉴于动态规划方法的自身特性及当前图像处理在解决模板匹配问题上的不足，本文提出了一种采用动态规划解决模板匹配的方法，首先给出图像数据与模板的匹配问题，并对该问题进行符号化和相应的理论分析，此后采用动态规划的方法解决模板匹配问题，并对传统动态规划解决方法在时间复杂度上进行改进。相较于传统模板匹配方法，采用本文提出的方法可以将时间复杂度减少一个数量级。

1 问题分析与解决

图像模板匹配算法的过程可以简单归纳为：首先采用某一尺度的模板遍历所有数据（例如整幅图像），此后计算模板与模板在整个图像中所对应区域的匹配程度，最后在数据中找到与模板匹配程度最高的区域。对于一幅图像数据S而言，若图像的尺寸大小为H*W，模板T的尺寸为P*P，模板匹配算法需要在图像数据上进行遍历，并计算模板与模板覆盖区域的匹配程度，将模板覆盖到一个图像区域并计算匹配度的过程约定为一个动作。设有一组试验动作序列：V=（V0，V1，…，VM） 和一组模板动作序列T=（T0，T1，…，TN），（M>N），两组序列都满足动作的时间顺序，这里试验动作数据中的每个动作都必须出现在匹配路径中，而模板动作序列不做此要求。计算模板与图像对应位置的匹配程度，可以根据需求采取不同的度量方式，如欧式距离、光度距离与几何距离等。模板的移动可以采用Zigzag的方式实现。则上述模板匹配可以得到有效的距离矩阵，可以在该距离矩阵的基础上设计动态规划优化解决方案。这里，假设试验动作数为M=15，模板动作数为N=10。

1.1 问题符号化及分析

为了方便地表达该问题，采用3个矩阵进行存储和计算，如图1所示。一个是矩阵A，用来存放原始数据；一个是矩阵B，用来存放计算过程的局部最优值；一个是矩阵R，用来记录局部最优值所对应的路径。

1.2 问题解决

1.2.1 局部最优值计算

对于上述问题，采用动态规划思想进行解决，其基本思路如下：首先，试验动作从V0开始，由于它是第一个试验动作，前面没有其它动作，因而无论它选择哪一个模板，都可看成是当前的最优值；然后，考查第二个试验动作V1，如果V1选择的模板动作是T0，那么试验动作V0选择的模板只能是T0，这时它的最小值为a0，0+a1，0，同时在矩阵R中r0，0位置记录该局部最优值所对应的模板序号；如果V1选择的模板动作为T1，那么试验动作V0可以选择的模板是T0或T1，显然，只有取a0，0和a0，1中的最小值，与a1，1相加后可得V1在选择模板动作T1时的最优值，同时在矩阵R中r0，1位置记录该局部最优值所对应的模板序号；如果V1选择的模板动作为T2，那么试验动作V0可以选择的模板就可以是T0、T1或T2，这时，需要取a0，0、a0，1、a0，2中的最小值，与a1，2相加后可得V1在选择模板动作T2时的最优值，同时在矩阵R中r0，2位置记录该局部最优值所对应的模板序号；如果V1选择的模板动作为Tj，j=3，…9，则依次类推。

其中，k的最大值是第M层叶结点的个数。度为p的树中第i层至多有pi-1个节点（i>1），该问题求解的树的度p=3，则第M=15层至多有3M-1=315-1个结点，试验中k的最大值为16，通过分析可以得出该问题的时间复杂度为O（16*M）。

综上分析，文中给出的算法在求模板匹配的最优解时，其对应的时间复杂度为O（MN）+O（KM），即max（O（MN），O（KM））。若从p叉树的生成角度考虑，算法的时间复杂度为O（MN）+O（nodes），即max（O（MN），O（nodes））。

3 结语

针对传統模板匹配算法在应用图像处理问题时遇到的时间复杂度过高等问题，对数据与模板匹配的过程进行优化，提出了一种基于动态规划算法加以实现的方法，算法的时间复杂度为max（O（MN），O（KM））。利用本算法，可以将模板匹配过程的复杂度大大减小，也不需要对数据进行过多处理，而且程序编写简单，各方面比原算法和目前已有文献中提到的改进算法都有很大提高。

可以看出，未来无论是计算机处理领域的模板匹配问题，还是日常生活生产中经常遇到的“试验数据和事先存储好的模板动作进行匹配”及类似问题，本文所提出的算法都具有一定应用前景。

参考文献：

[1]王倩倩.基于聚类的模板匹配显微细胞图像分割算法的研究[D].重庆：重庆大学，2015.

[2]李厚军.快速模板匹配方法及其在眉毛识别中的应用[D].北京：北京工业大学，2015.

[3]陈莹.基于FPGA的微光图像增强和模板匹配研究[D].北京：中国科学院大学，2014.

[4]王正，陶品，冯立新，温江涛，杨士强.基于模板的调色板方法[J].计算机辅助设计与图形学学报，2016，28（7）：1146-1151.

[5]王志衡，郭超.基于模板匹配的新闻图像字幕行切分算法[J].北京邮电大学学报，2016，39（3）：49-53.

[6]张盼盼，张颖颖.模板匹配与八邻域分析法在数字细化预处理中的应用及比较[J].软件导刊，2016，15（5）：210-211.

[7]陈宁，王胜，黄正文.基于特征匹配的集装箱识别与定位技术研究[J].图学学报，2016，37（4）：530-536.

[8]THOMAS H CORMEN，CHARLES E LEISERSON.Introduction to algorithms[M].Second Edition.Massachusetts：The MIT Press，2001.

[9]王晓东.计算机算法设计与分析[M].第2版.北京：电子工业出版社，2005.

[10]徐孝凯，贺桂英.数据结构（C语言描述）[M].北京：清华大学出版社，2004.

[11]唐策善，李龙澍，黄刘生.数据结构——用C语言描述[M].北京：高等教育出版社，2003.

[12]魏星，周萍.改进型蚁群算法的语音动态规划研究[J].仿真应用研究，2011，228（5）：402-409.

[13]傅颖，郭晶云.基于动态时间规整的人体动作识别方法[J].电子测量技术，2014，37（3）：69-72.

（责任编辑：孙 娟）