第8章 模板匹配(精简)

第8章 模板匹配

8.1 引言

? 模板匹配不同于前面讲的模式识别方法,也不同于聚类分析方法。 模板是为检测某些区域特征（形状或图案）而设计的数据阵列。模板匹配是一个较原始和最基本最常用的的模式识别方法之一，模板匹配用来研究某一特定图案位于整个图像中的什么位置，并根据相似度来确定该特定图案是否存在以及确切位置，这样的方法叫模板匹配。

? 模板匹配方法中使用一个参考模板，然后决定未知的测试模式与哪个参考模式是最佳匹配。模板是由一系列的识别符号串或特征向量(串模式)组成的。也就是说，每个都由测度参数序列(串)表示，然后判断测试模式和哪个参考模式最佳匹配。这些参考模板可以是场景中的对象，也可能是模式串，例如，在手写文本中组成单词的字母，或语音文本中的单词或短语，为此：

1)、定义一种合理的测度和代价来测量参考模板与测试模式之间的距离或相似度。 2）、手写文本的匹配问题

识别一系列的单词中哪一个是指定的单词，比方说?beauty?。然而，由于阅读传感器的误差，指定的测试模式可能被显示为?beetv?或?beaut?。在语音识别中，如果一个特定的单词由同一个人说很多次，每次都是不同的；有时可能说得快，则结果模式的持续时间短；有时说得慢，则持续时间长；然而不管怎样，它是同一个人说的同一个单词。需要确定相似的程度,因此要定义测度，用于给出各类问题区分特性。 ? 先讨论字符串模板匹配问题，然后讨论场景分析和形状识别问题。尽管这些任务具有同样的目的，但由于性质不同，所需要的工具也不同。 8.2 基于最优路径搜索技术的测度

模板匹配的种类: 参考模式和测试模式

? 动态时间规整算法（DTW） ? 定义:

参考模式的特征向量序列，r(i), i =l，2，…,I 。

测试模式的特征向量序列，t(j)，j=1，2，…,J，一般I≠J。 目的是找出两个序列之间的合适距离测度（并非严格数学上的距离），动态时间规整算法就是把时间规整(或规划)和距离测度计算结合起来的非线性规整技术， ? 建立一个二维的表格(网格):

用参考模板序列r(i)作为横坐标i轴，测试模式序列t(j)作为纵坐标j轴，建立直角坐标系。两序列序号的关系形成一个网格。网格中的每个节点（i,j）－－交叉点，表示两个模式相交（两个模式的对应关系）。

图8.1是I=6，J=5(I,J)的例子。节点(3，2)表示(r(3),t(2)) ? 代价函数d(i，j):

网格中的每个节点(i,j)对应一个代价函数d(i ,j)，代价函数值就是用于测量各自序列的模式r(i)和t(j)之间的距离。 ? 路径: 从网格原点(i 序集:

(i0,j0)，(i1,j1)，(i2,j2)，…，(if,jf0,j0)到终点(if,jf)的路径是一个点的有

)

? 全程代价函数D: 每个路径对应一个全程代价函数D，它是这个路径上各个节点上的代价函数d(ik,jk)的总和

D?k?0?d(ik,jk)

K?1 其中大K代表路径中的节点总数(图8.1中K = 8),小 k表示节点序号。

到节点(ik,jk)的全程代价函数值为D(ik,jk)，假设起点到起点的全程代价值为D(0,0)=0，并且起点的代价函数值为d(0,0)=0。如果记起点(i0,j0)=(0,0)，终点(i起始点到终止点)。

f,jf) =(I,J)，则路径是完整的(从

图8.1 路径上的每个点标志着测试模式与参考模式元素之间的对应关系

? 动态时间规整算法DTW就是要寻找一条从起点到达终点的最佳路径，使得该路径上所有节点的代价函数的总和，即全程代价函数D最小。 说明：

①两个序列间的距离被定义为所有可能的路径中的最小D值。由于两个序列的长度不同，最小的代价路径揭示了两个序列元素之间成对对应的最优关系。换句话说，最优路径过程使测试串元素与参考串元素的对齐或弯折对应于最佳匹配付出不同的代价。

②方案有多种变体。例如，没有必要采用完整路径作为强约束，可以采用松弛约束，即所谓的?终点约束?。另外，代价不仅与节点有关，而且与节点之间的转移有关，有些转移代价值高于其它的转移。在这种情况下，节点(ik,jk)的代价仅依赖于特定的转移，就是说，从哪个(ik?1,jk?1)节点沿哪个方向到达节点(ik,jk )节点。因而，节点代价值d的表示是d(ik,jk｜ik?1,jk?1)，完整的路径代价是

D??d(ik,jk|ik?1,jk?1)

k有些情况下，完整路径代价还可能定义为乘积形式

D=?d(ik,jk|ik-1,jk-1)

k③注意，也有一些实例选择d是使代价最大而不是最小, 必须根据实际场合,采用合适的初始条件。)

8.2.1 Bellman最优化原理和动态规划

为了获得最优路径，若寻找所有可能的路径，则计算量太大。基于Bellman原理的动态规划算法减少计算复杂度。 ? 原点(i0,j0)到终点(if,jf)的优化路径可表示为 (i0,j0)?(if,jf) 如果(i,j)是原点(i0,j0)和终点(i(i,j)的最优化路径表示为

opt(i,j)fopt,jf)路径上的一个节点，通过节点

(i0,j0)?(if,jf) ? Bellman原理：

(i0,j0)?(if,jf)＝(i0,j0)?(i,j)?(i,j)?(if,jf)

(i,j)optoptopt? 描述：从原点(i0,j0)经过节点(i,j)到节点（i由原点(i0,j0)到节点(i(iff,jf)的最优路径是

,j,j)的最优路径与由节点(i)到终点

,jf)的最优路径的串联。

)的最优路径，则仅需要找

? 说明：

（1）可推论出一旦找到了到达节点(i到从节点(i,j,j)到节点(if,jf)的最优路径。这个原理将完整阶段的决

策过程转化为若干单个阶段的子问题而逐一决策。

（2）设已离开原点(i0,j0)，计算到达第k个节点(ik,jk)的最小代价。设转移到节点(ik,jk)必须由路径上可能的序号为第k－1的节点(ik?1,jk?1)开始。又假设网格中的每个节点都有一组前序节点，就是只能从这一组前序节点转移到这个节点，这就是局部约束。从Bellman原理容易导出

Dmin(ik,jk)?imin,jk?1k?1?D(i,j)?d(ik,jk|ik?1,jk?1)??mink?1k?1? (8.1)

上式意味着：

①.到达节点(ik,jk)的最小代价就是到达节点(ik?1,jk?1)的最小代价加