模板匹配

典型算法原理模板匹配01模板w开始位置在图像f的左上角当w的中心位于f的边界上时，围绕f的边界需要进行填充。填充通常被限制为模板宽度的一半。02模板从左上角向右下角开始移动每次移动一个像素的位置，过程中可以得到模板和图像各位置间的相似度。03生成结果图像相似度量值保存到结果图像中.在结果图像中的每个位置都包含匹配度量值。04找到匹配位置根据所用的匹配算法不同，对结果图像进行处理分析，找到匹配位置。2模板匹配-简要流程基于灰度值的模板匹配算法。基于边缘的模板匹配算法基于形状的模板匹配算法3模板匹配算法分类基于灰度值的模板匹配Gray-Value-BasedTemplateMatching5基于灰度值的模板匹配—基本概念相似度量相似度量S是一个函数，函数中的参数包括：①模板中各点的灰度值t(r,c)；②模板感兴趣区域移动到图像当前位置时感兴趣区域中的灰度值f(r+u,c+v)；然后基于这些灰度值计算一个标量值作为相似度量。01SAD:计算模板与图像之间差值的绝对值总和sad(r,c)=𝟏𝒏|𝒕𝒖,𝒗−𝒇𝒓+𝒖,𝒄+𝒗|(𝒖,𝒗)∋𝑻02SSD:计算模板和图像之间差值的平方和ssd(r,c)=𝟏𝒏[𝒕𝒖,𝒗−𝒇𝒓+𝒖,𝒄+𝒗]𝟐(𝒖,𝒗)∋𝑻问题在光照保持不变的情况下，SAD和SSD相似度量的结果非常好。当光照发生变化，甚至在图像中存在相同物体的情况下，他们都将返回非常大的结果!6基于灰度值的模板匹配——相似度量方法—SAD,SSD（Sumofabsolute/squareddifference）？03NCC：归一化互相关系数ncc(r,c)=𝟏𝒏𝒕𝒖,𝒗−𝒎𝒕𝒔𝒕𝟐𝟐∙𝒇𝒓+𝒖,𝒄+𝒗−𝒎𝒇(𝒓,𝒄)𝒔𝒇𝟐𝟐(𝒓,𝒄)(𝒖,𝒗)∋𝑻7基于灰度值的模板匹配——相似度量方法—NCC(Normalizedcross--correlation)公式中，𝒎𝒕是模板灰度的平均值，𝒔𝒕𝟐是模板灰度的方差，即：𝒎𝒕=𝟏𝒏𝒕𝒖,𝒗(𝒖,𝒗)∋𝑻𝒔𝒕𝟐=𝟏𝒏[𝒕𝒖,𝒗−𝒎𝒕]𝟐(𝒖,𝒗)∋𝑻与之类似，𝒎𝒇是与模板ROI区域对应的目标图像中当前位置区域内灰度的平均值，𝒔𝒇𝟐是该区域灰度的方差，即：𝒎𝒇=𝟏𝒏𝒇𝒓+𝒖,𝒄+𝒗(𝒖,𝒗)∋𝑻𝒔𝒇𝟐=𝟏𝒏[𝒇𝒓+𝒖,𝒄+𝒗−𝒎𝒇]𝟐(𝒖,𝒗)∋𝑻(,)(,)(,)(,)uvTcrctuvfrucv结果从NCC的定义不难看出，-1≤ncc(r,c)≤1。当ncc(r,c)=±1时，图像与模板成线性关系：f(r+u,c+v)=at(u,v)+b当ncc(r，c)=1时，a0，此时图像与模板的极性相同；当ncc(r,c)=-1时，a0，此时图像与模板的极性相反。这就意味着，当外界光照发生线性变化时，不会影响NCC匹配的结果。通常，NCC的绝对值越大表示模板与目标图像越相似，反之NCC的绝对值越接近0表示二者差距越大。8基于灰度值的模板匹配算法—NCC•基于灰度值的模板匹配方法原理简单。•在良好的光照条件下可以得到很满意的匹配结果。Advantages9基于灰度值的模板匹配——总结优点Disadvantages缺点•受光照影响大，抗干扰性不强。•图像存在遮挡、部分隐藏、信息缺失、混乱时不能正确找到目标物体。0102基于边缘的模板匹配算法Edgematching11基于边缘的模板匹配算法010203使用原始边缘点或者增加每个点的一些特性。将边缘分割为多个几何基元，然后匹配这些几何基元。得到边缘上的突变点，然后匹配这些突变点。三种策略12基于边缘点的模板匹配算法—均方距离sed(r,c)=𝟏𝒏𝒅𝒓+𝒖,𝒄+𝒗𝟐(𝒖,𝒗)∋𝑻平移情况下的均方边缘距离可表示为：其中，T表示模板边缘区域，d(r,c)表示边缘提取后待搜索图像背景的距离变换。缺点：图像边缘有遮挡时，返回的距离将会非常大。13基于边缘点的模板匹配算法—距离变换街区距离--4连通欧氏距离棋盘距离—8连通14基于边缘点的模板匹配算法—距离变换在实际应用中，按照距离的定义去计算，是非常耗时的。书中给出了距离变换的快速算法，其具体算法如下：（一）将距离图像初始化。边缘上的距离值设定为最大距离值，即2𝑏-1，其中b为距离图像的像素位数，其余区域的距离设为0。（二）设定掩码。当计算4-连通距离时，𝑑1=1且𝑑2=∞；当计算8-连通距离时，𝑑1=1且𝑑2=1；当计算欧式距离（近似）时，𝑑1=3且𝑑2=4。𝑑2𝑑1𝑑2𝑑100𝑑1𝑑2𝑑1𝑑2（三）在距离图上用上述两个掩码分别从左上到右下和右下到左上进行逐行扫描，将掩码覆盖区域中的距离值与掩码中相应位置上的距离值求和，然后从掩码的所有计算结果中选择最小的值作为当前像素的距离值。∞1∞101∞1∞21210121215基于边缘点的模板匹配算法—距离变换原图街区距离棋盘距离欧氏距离16基于边缘点的模板匹配算法—Hausdorff距离h(T,E)表示了模板边缘点与最近图像边缘点之间的最大距离；h(E,T)的定义与h(T,E)互为对称，它表示了图像边缘点与最近模板边缘点之间的最大距离。Hausdorff距离是由这两个距离的最大值决定。匹配过程将模板沿着图像逐像素扫描，模板每移动一次就会得到一个当前的Hausdorff距离。当模板中的边缘点与图像中的边缘点非常接近，且图像中的边缘点与模板中的边缘点也非常接近时，会得到一个最小的Hausdorff距离，此时为最优匹配。改进当图像中出现遮挡情况下算法效果不佳的主要原因是由于在计算h(T,E)时采用了最大距离。如果用第k大距离代替最大距离，Hausdorff距离将对100/%kn的遮挡可靠，其中n表示模板边缘区域中像素点的数量。。17基于边缘点的模板匹配算法—Hausdorff距离尽管改进的Hausdorff距离能够解决遮挡和混乱带来的问题，但是当遮挡部分较大时，该方法会找到较多的错误实例。此外由于Hausdorff距离的计算量较大，这使得算法的实时性比较差，对于那些实时性要求较高的在线系统该方法往往不能满足。18基于边缘点的模板匹配算法—广义霍夫变换当图像中某边缘点的梯度角与模板中某边缘点梯度角相同时，可以根据向量𝒓𝒊计算模板可能出现的位置，并在当前位置投票，即累计数组加1。但是模板中可能存在另一边缘点𝒆𝒋,其𝛁𝒇𝒋=𝛁𝒇𝒊,但是𝒓𝒋≠𝒓𝒊。此时需要根据向量𝒓𝒋计算模板可能出现的位置，并在相应位置的累计数组加1。R-Table该表使用梯度角∅𝑗作为索引，每个条目中记录着该梯度角∅𝑗对应所有偏移向量的集合𝑟𝑗。梯度角∅𝑗使用固定间隔∆∅离散，以提高检索效能。19基于边缘点的模板匹配算法—广义霍夫变换上面所说的所有基于边缘的算法都存在一个缺陷，就是它们都需要在图像中提取出边缘。这就导致目标识别算法只能够适用于非常小范围的光照变化。如果降低对比度，提取到的边缘点就越来越少，更多的遮蔽也会造成相似的影响。缺陷总结20基于边缘点的模板匹配算法基于形状的模板匹配Shape-based22基于形状的模板匹配算法相似度量S：,,222211,,11||||||||iiiiiiiiTnniirrccrrcciqpiiiqpiirrccrrcctvuwdesndentuvw归一化后的相似度量S：,,1111iiiinnTiqpirrccirrcciisdetvuwnn当图像中存在遮挡的情况，遮挡部分像素点的梯度向量的模非常小，它与模板相应位置梯度向量的内积也是一个非常小的值，几乎不影响总和；当图像中存在混乱的情况，混乱部分对应的模板相应位置梯度向量的模非常小，它们的内积仍然不影响总和。然而,公式提供的相似度量仍不能真正的满足光照变化的情况。这是因为梯度向量的模取决于图像的亮度：当图像较亮时，梯度向量的模较大；当图像较暗时，梯度向量的模较小。结果由于梯度向量进行了归一化，该相似度量将返回一个小于等于1的值。当s=1时，说明模板与图像之间一一对应；当图像中目标物体的50%被遮挡时，该相似度量将不会超过0.5。因此，它可以让用户选择一个直观的阈值来决定具体的匹配对象。23基于形状的模板匹配算法对基于形状的模板匹配算法测试后显示基于形状的模板匹配算法在存在严重遮挡、混乱或非线性光照变化的情况下实现了非常高的识别率。优点总结24基于形状的模板匹配算法图像金字塔pyramid26图像金字塔在构建图像金字塔的过程中，速度是非常重要的，通常优先采用2*2的均值滤波器平滑图像，也就是说求2*2区域中的所有像素的平均灰度值。当在金字塔的最高层搜索到相应的模板实例时，将匹配点的坐标乘以2，映射到金字塔的下一层。此外,由于金字塔的最高层目标物体的灰度值可能发生实质性的变化，这要求在匹配金字塔的较高层时应使用较为宽松的匹配阈值。27模板匹配算法TheEnd