24
pyramid
图像金字塔
图像金字塔
26
在构建图像金字塔的过程中，速度是非常重要的，通常优先采用 2*2 的均值滤波器平滑图像，也就是说求2*2区域中的所有像素的平均 灰度值。
当在金字塔的最高层搜索到相应的模板实例时，将匹配点的坐标乘 以2，映射到金字塔的下一层。
此外,由于金字塔的最高层目标物体的灰度值可能发生实质性的变 化，这要求在匹配金字塔的较高层时应使用较为宽松的匹配阈值。
匹配过程
将模板沿着图像逐像素扫描，模板每移动一次 就会得到一个当前的Hausdorff距离。当模板 中的边缘点与图像中的边缘点非常接近，且图 像中的边缘点与模板中的边缘点也非常接近时， 会得到一个最小的Hausdorff距离，此时为最 优匹配。
改进
当图像中出现遮挡情况下算法效果不佳的主 要原因是由于在计算h (T, E) 时采用了最大 距离。如果用第k 大距离代替最大距离， Hausdorff距离将对100 / % k n 的遮挡可 靠，其中n表示模板边缘区域中像素点的数 量。。
������ + ������, ������ + ������
− ������������] ������
7
基于灰度值的模板匹配算法—NCC
从NCC的定义不难看出，-1≤ncc(r,c)≤1。当ncc(r,c)=±1时， 结果
图像与模板成线性关系： f(r+u,c+v)=at(u,v)+b
当 ncc(r，c)=1时，a>0，此时图像与模板的极性相同； 当 ncc(r ,c)=-1时， a<0 ，此时图像与模板的极性相反。
？
6
01 S A D : 计 算 模 板 与 图 像 之 间 差 值 的 绝 对 值 总 和
sad(r,c)=������������ σ(������,������)∋������ |������ ������, ������ − ������ ������ + ������, ������ + ������ |
欧氏距离
15
基于边缘点的模板匹配算法—Hausdorff距离
h (T, E) 表示了模板边缘点与最近图像边缘点之间的 最大距离；
h (E, T) 的定义与h (T, E) 互为对称，它表示了图像 边缘点与最近模板边缘点之间的最大距离。 Hausdorff距离是由这两个距离的最大值决定。
16
基于边缘点的模板匹配算法—Hausdorff距离
尽管改进的Hausdorff距离能够解决遮挡和混乱带来的问题，但是当遮挡部分较大时，该方法会找到较多 的错误实例。此外由于Hausdorff距离的计算量较大，这使得算法的实时性比较差，对于那些实时性要求 较高的在线系统该方法往往不能满足。
17
基于边缘点的模板匹配算法—广义霍夫变换
当图像中某边缘点的梯度角与模板中某边缘点梯度角相同 时，可以根据向量������������计算模板可能出现的位置，并在当前 位置投票，即累计数组加1。 但是模板中可能存在另一边缘点������������ ,其������������������ = ������������������ ,但是 ������������ ≠ ������������。此时需要根据向量������������计算模板可能出现的位置， 并在相应位置的累计数组加1。
������ ������������ ������(������,������)
c(r, c) t(u, v) f (r u, c v) ( u ,v )T
公式中，������������是模板灰度的平均值，������������ ������ 是模板灰度的方差，即：
������������=������������ σ(������,������)∋������ ������ ������, ������
s 这是因为梯度向量的模取决于图像的亮度：当图像较亮时，梯度向量的2模较大2；当图像2 较暗时，梯度向2量
n || d |||| e || n t u v w 的模较小。
i1 i
q p
i1 i
i
r ri ,cci
r ri ,cci
22
基于形状的模板匹配算法
由于梯度向量进行了归一化，该相似度量将返回一个小于等于1 的值。
• 受光照影响大，抗干扰性不强。
• 图像存在遮挡、部分隐藏、信息缺失、混乱时 不能正确找到目标物体。
缺点 02
Disadvantages 9
Edge matching
基于边缘的模板匹配算法
基于边缘的模板匹配算法
三种策略
11
01 使用原始边缘点或者增加每个点的一些特性。 02 将边缘分割为多个几何基元，然后匹配这些几何基元。 03 得到边缘上的突变点，然后匹配这些突变点。
5
相似度量S是一个函数，函数中的参数包括： ①模板中各点的灰度值t(r,c)； ②模板感兴趣区域移动到图像当前位置时感兴趣区域
中的灰度值f(r+u,c+v)；
然后基于这些灰度值计算一个标量值作为相似度量。
基于灰度值的模板匹配——相似度量方法—SAD,SSD（Sum of absolute/squared difference）
02 S S D : 计 算 模 板 和 图 像 之 间 差 值 的 平 方 和
ssd(r,c)=������������ σ(������,������)∋������[������ ������, ������ − ������ ������ + ������, ������ + ������ ] ������
模板匹配
典型算法原理
模板匹配-简要流程
2
01 模板w开始位置在图像f的左上角
当w的中心位于f的边界上时，围绕f的边界需要进行填充。填充通常 被限制为模板宽度的一半。
02 模板从左上角向右下角开始移动
每次移动一个像素的位置，过程中可以得到模板和图像各位置间的相似度。
03 生成结果图像
相似度量值保存 到 结果图像中. 在 结果图像中的每个位置 都包含匹配度量值。
图像中提取出边缘。 这就导致目标识别算法只能够适用于非常小范围的光照变化。如果
降低对比度，提取到的边缘点就越来越少，更多的遮蔽也会造成相似 的影响。
20
Shape-based
基于形状的模板匹配
基于形状的模板匹配算法
相似度量 S：
s

1 n
n i 1
diT eq p

1 n
n
t vi r ri ,cci
∞1 ∞ 1 01 ∞ 1∞
21 2 10 1 21 2
（三）在距离图上用上述两个掩码分别从左上到右下和右下到左上进行逐行扫描，将掩码覆盖区域中的距离值与掩码中 相应位置上的距离值求和，然后从掩码的所有计算结果中选择最小的值作为当前像素的距离值。
14
基于边缘点的模板匹配算法—距离变换
原图
街区距离
棋盘距离
（二）设定掩码。当计算4-连通距离时，������1=1且������2=∞；当计算8-连通距离时， ������1=1且������2=1；当计算欧式距离（近似） 时， ������1=3且������2=4。
������2 ������1 ������2 ������1 0
0 ������1 ������2 ������1 ������2
基于边缘点的模板匹配算法—均方距离
平移情况下的均方边缘距离可表示为：
sed(r,c)=������
������
σ(������,������)∋������ ������
������ + ������, ������ + ������
������
缺点：图像边缘有遮 挡时，返回的距离将 会非常大。
其中，T表示模板边缘区域，d(r, c) 表示边缘提取后待搜索图像背景的距离变换。
i 1Biblioteka u wi r ri ,cci
归当图一像化中后存在的遮相挡的似情度况，量遮挡S部：分像素点的梯度向量的模非常小，它与模板相应位置梯度向量的内积也
是一个非常小的值，几乎不影响总和；当图像中存在混乱的情况，混乱部分对应的模板相应位置梯度向量
1 d e 1 t v u w 的模非常小，它们的内积仍n 然不影响总iT 和q。然p而,公式提供的相n似度量仍i不能r 真ri正,c的满ci 足光照变i 化的r 情ri 况,c。ci
这就意味着，当外界光照发生线性变化时，不会影响NCC 匹配的结果。通常，NCC的绝对值越大表示模板与目标图像 越相似，反之NCC的绝对值越接近0表示二者差距越大。
8
基于灰度值的模板匹配——总结
• 基于灰度值的模板匹配方法原理简单。
01
• 在良好的光照条件下可以得到很满意的匹配
结果。
优点
Advantage s
问题
在光照保持不变的情况下，SAD和SSD相似度量的结果非常好。
当光照发生变化，甚至在图像中存在相同物体的情况下，他们都将 返回非常大的结果!
基于灰度值的模板匹配——相似度量方法—NCC(Normalized cross--
correlation)
03 N C C ： 归 一 化 互 相 关 系 数
ncc(r,c)=������
������
σ(������,������)∋������
������
������,������ −������������ ������ ������������ ������
∙
������ ������+������,������+������ −������������(������,������)