第8章 模板匹配

《第8章 模板匹配》由会员分享，可在线阅读，更多相关《第8章 模板匹配（23页珍藏版）》请在金锄头文库上搜索。

1、第8章瞰匹配8.1弓I言模板匹配不同于前面讲的模式识别方法,也不同于聚类分析方法。 模板是为检测某些区域特征（形状或图案）而设计的数据阵列。 模板匹配是一个较原始和最基本最常用的的模式识别方法之一， 模板匹配用来研究某一特定图案位于整个图像中的什么位置，并 根据相似度来确定该特定图案是否存在以及确切位置，这样的方 法叫棋板匹配。模板匹配方法中使用一个参考横板，然后决定未知的测试模式与 哪个参考模式是最佳匹配。模板是由一系列的识别符号串或特征 向量（串模式）组成的。也就是说，每个都由测度参数序列（串）表示， 然后判断测试模式和哪个参考模式最佳匹配。这些参考棋板可以 是场景中的对象，也可能是模式串

2、，例如，在手写文本中组成单 词的字母，或语音文本中的单词或短语，为此：1）定义一种合理的测度和代价来测量参考模板与测试模式之 间的距离或相似度。2 手写文本的匹配问题识别一系列的单词中哪一个是指定的单词，比方说“ beauty”。 然而，由于阅读传感器的误差，指定的测试模式可能被显示为“beetv”或。角侦”。在语音识别中，如果一个特定的单词由 同一个人说很多次，每次都是不同的；有时可能说得快，则结果 模式的持续时间短；有时说得慢，则持续时间长；然而不管怎样， 它是同一个人说的同一个单词。需要确定相似的程度，因此要定义 测度，用于给出各类问题区分特性。先讨论字符串棋板匹配问题，然后讨论场景分析

3、和形状识别问题。 尽管这些任务具有同样的目的，但由于性质不同，所需要的工具 也不同。8.2基于最优路径搜索技术的测度模板匹配的种类：参考模式和测试模式 动态时间规整算法伽）定义：参考模式的特征向量序列，r (i), i =l,2,.,I,测试模式的特征向序列，t(j) , j=1,2，,J，-般 I#JO 的是找出两个序列之间的合适距离测度(并非严格数学上的距 离)，动态时间规整算法就是把时间规整(或规划)和距离测度计算 结合起来的睇性规整技术，.建立一个二维的表格(网格)：用参考棋板序列r (i)作为横坐标i轴，测试模式序列t (j)作为纵坐 标j轴，建立直角坐标虱两序列序号的关系形成一个网

4、格,网 格中的每个节点(i, j )交叉点，表示两个模式相交(两个 模式的对应关系)。8.1是1=6 , J=5(IJ)的例子。节点(3,2)表示(r,t) .代价函数d(i，j):网格中的每个节点(i, j)对应一个代价函数d(i j)，代价函 就是用于测量各自序列的模式r (i) 和 t (j)之间的距离。.路径：从网格原点()到终点(,/)的路径是一个点的有 序集:(i , j)，( i, j)，( I) (i，j )001122f f.全程代价函数D：每个路径对成一个全程代价函数D，它是 这个路径上各个节点上的代价函数d q, jk)的总和D =尸d加j)k=0其中大K代表路径中的节点

5、总数(图8.1中K = 8)小k表示节点再 号。数值到节点(i，j )的全程代价函数值为D( i, j )，假设起点到起点的 k kk k全程代价值为D(0,0)=0，并且起点的代价函数值为d(0,0)=0。如果记起点(i, j )=(0,0)，终点(i , j ) =(IJ)，则路径是完整的(从起 0 0f f始点到终止点)。测试模式与参考模式元素之间的对成8.1关系动态时间规整算法DTW就是要寻找一条从起点到达终点的最佳 路径，使得该路径上所有节点的代价函数的总和，即全程代价函 D最小。说明： 两个序列间的距离被定义为所有可能的路径中的最小D值。由 于两个序列的长度不同，最小的代价路径揭示

6、了两个序列元素 之间成对对成的最优关系。换句话说，最优路径过程使测试串 元素与参考串元素的对齐或弯折对应于最佳匹配付出不同的代 价。 方案有多种变体。例如，没有必要采用完整路径作为强约束，可以采用松弛约束，即所谓的终点约束”。另外，代价不仅与 节点有关，而且与节点之间的转移有关，有些转移代价仁:二 其它的转移。在这种情况下，节点(i, j )的代价仅依赖于特定的 转移，就是说，从哪个(i j )节点沿哪个方向到达节点(i,j ) 节点。因而，节点代价值d的表示是d (匕,j|)，完整的D = d (i , j I i , j ) k k k-1 k -1 k有些情况下，完蛔径代价还可能定义为乘

7、积形式D = n dGk，jk 注意，也有一些实例选择d是使代价最大而不是最小,必须根 据实际场合,采用合适的初始条件。)1-71-777Tnuwwra(施果fm抑曾咽(f wgiwF?UIUI,、【T【T 【T 1-7 仰门 ,（口）（ r z| r z）p+（ r 0 a uim =（ r ?） qumun冲 gumf瞄，liisusrws-w1-71-7HW罗Ki班瞩一身曜罗眼&咽中果幽调I区。毗（厂）77草触 TT g昏邮卿町8例剧翊（f ）草KO踵沥7700WWM（p瞠眼（厂腱觐任舅曰视（z）*T 眼回翊鲫蕉艇咽醐时瞄卦阿 悟咐印（）草|：俺（）草KW 脸瞄岫雁，甄洒W 孵袖匕隘暗一

8、弟碱画T）:前槊.。帷曜咐神M（）瞄隧（）覃K田旨鲫1印（）覃KISU ）煦././00田晋胡（ Z ）草K|g（ S草阳膨（理疝：$/ /0 0/ /（ ）（P .0-（P.O （）饮（八?）=（厂! ） （广？）j do:sat iremn 鲸r r !） 03七）m）jdo.顷）覃KJ睡,草SHlWHWK 孵卸tt（ f %0（ry）/r,/o o玲虹恒wanm财，）曲isu oww .s菅岫if 知仲涮皿 岫网 王S VM44liili,酮I风瞿鱼身蛔尊酮妙客蛔实ro(&tttits由节点(i ,j )到节点(i,j)的转移代价。.只能在节点(i, j )的前序节点集合中寻找代价的最小

9、值，这个过程 将遍历网格中的每个节点。但在很多情况下最优路径的搜索仅仅在节点的子集中进行，这由全局约束定义。注：如果代价函数D以乘法形式给出，或者求最大值，则式(8.1)必须做相应的修改。串匹配任务:8.2给出了递归方程(8.1)是建立完整的最优路径的过程。其中：最优化(全局约束)的节点集以黑点表示；局部约束(节点间所有允许的转移)以细线表示。寻找完整路径并假设D(O,0)=0后的步骤：第k=1步，由式(81)计算所有允许节点的代价D( i, j )设例中 仅有两个允许节点(1，1)和(1，2)。1 1第k=2步，计算三个节点(包括原点)的代价，重复这个过程 直到到达终点I,人使终点的代价D(

10、I,J)最小的转移序列就是最 小的代价路径，如图粗线表示。在图8.2的例子中，递归的每一步k仅仅涉及相同横坐标的点，这表 示采用的是局部约束，例如，节点(1，2)的下一个节点，对成横 坐标2上的(2,2(2,3)和(2,4)。一般来说并非一定如此，更一般的情况是利用拓扑陲论。但不管用什么方法，寻找最小值的理管值论是相同的。图8.2在所有可能的路径中搜索构造最优化路径，联骚gEHffi果%、蛛编 曜l:BaIIK3mF*肉也SB?lm主wsss.sshsffs ffiB目胃019宣辍粮ME4KZQO冒泰国理im&s昇p WIBUSSM 用题 A ffi、? SISK 怏愈DR XWES wfSI

11、 , 者 .者萤电 OISK 嘛着.ssss5SIs (z8) s弓+(f 二 +sw 专(9 v)erzlrYloisss IkweY wOSHS息HKME41 胃s最fioss 备la叔皆an麝SSN 8R堂曜也。曜(mam*ws屋也堂Elsll$mwi费!eOST 筑E2mmum&曜曾豪理189最#印凯.Q .simmnelsf ssf 4KCII恒要最器其华曜咪OKI ossisssssKsnwg厘其华 ossmss 。一swlls.(3* Ki_s *(.2gq=g晕YSB.(:fs= sw Bn$ *复 wttliH卷印 s SISolf .SSSWBS is . w3M z.z.

12、8,二二搜节点(0,0)的代价D(0,0)是零, 索完整路径.每个节点(i ,j )仅可以通过三个前序节点到达，即(i-1,j),(i Lj-1),(i,j 1).与上面三个转移有关的代价是：1.对角线转移。，若们=心) 】,若质)知(刃-如果对应于节点(i, j )的符号(字母)相同，则转移代价 是0 ,如图8-3(a)所示；-如果对应于节点(i, j )的符号不相同，则转移代价为1, 这个符号必须改变。如图8-30)所示。2.水平和垂直转移d (i, j I i -1, j) = d (i, j I i, j -1) = 1(转移代价均为1)-水平转移的意思是通过在符号串中插入符号，使两个

13、 模式对齐。如图8.3(a)，它的代价增加，因为局部不 匹配。-垂直转移也增加代价，因为符号需要删除，如 8.3(c)。四8-3四个图的编辑长度计算，局部约束显示在右下角(a) 插入符号;(b) 改变符号；删除符号；(d)相等由(0,0)开始计算到达网格中每个节点的最小代价，随后建立最 优路径。8.3显示了每种情况下各自的最小代价路径和编辑距离。可以 验证图8.3中任何其它路径都有更高的代价。8.3基于相关的测度主要任务：已知一段录制的数据找出一个指定的参考模式是否包含在里面， 如果在，则确定它的位置。典型场景分析，即在一个图像中寻找 一个确定的对氤这个问题出现在很多应用中，如目标探测,机 器

14、人视觉和视频编码。例如，视频编码的主要步骤就是运动估计，也就是在连续的、不 同时刻的图像画面中，确定相应的像素(被移动的相同对象)的过 程。接着是运动补偿的阶段，将补偿运动对象从一帧到另一帧地 换，然后对帧的差值进行编码e(i, j, t) = r (i, j, t) - r (i - m, j - n, t -1)其中r( i j,t )是图像帧在t时刻的像素灰度级，r( i - m, j - n, t -1) 是在前一帧t-1时刻在空间位置i-m ,j-n的像素值。这样，我们 仅仅对包含在最新帧中的新信息进行编码，避免了冗余。将一个已知的参考模式描述为MXN图像数组r( i, j ),i =0,.，M-1, j = O,.，N-1,测试模式被描述为Ix J图像数组t( i, j ) , i =0,，I-1,j =0,.J-1，其中MMI, N J的是寻找一种测度用于测量在t( i, j冲查找的MxN子图像与参 考模式r( i, j )是否最佳匹配。最后，参考图像r (i, j)叠加在测试图像上，并且平移到