数字视频图像处理与通信-图像匹配讲义.ppt

第7章 图像匹配,目录,7.1 基本概念7.2 图像匹配算法分类7.3 模板匹配算法7.4 改进算法,7.1 基本概念,模板匹配可以分为狭义的和广义的 狭义匹配：匹配的目标是同一样事物 因为一个事物的自身特点总是固定的，比如颜色、大小、形状等等，即便由于环境的不同而导致获取的图片有差别，只要计算机能够分辨出这些特征就可以识别事物 广义的匹配：匹配的是一类事物 如，某一种动物，某一类型的汽车等相比于前一种匹配，这种方式更为复杂，需要系统具备一定的学习和推理能力7.2 图像匹配算法分类,直接利用原始图像的灰度进行匹配利用图像的物理形状特征进行匹配使用高级特征的算法进行匹配,直接利用原始图像的灰度进行匹配,直接利用图像的信息区分不同对象，处理的信息量大，计算复杂度高 对图像之间的微小差别非常敏感，一个细微的变化(比如光照条件的微小变化而导致的图像灰度值的细微变化)就会对匹配算法的计算结果产生大的影响，甚至可能导致匹配的失败 结论：抗噪声、抗干扰的能力比较差，只能适用于2幅图像具有相同外界条件的情况下作精细的匹配利用图像的物理形状特征进行匹配,利用图像的物理特征，如边缘、骨架线条、角点等进行匹配，需要相关计算的像素点明显减少，并具有更强的适应能力。

对细微的干扰不太敏感，而是依赖于提取的图像特征，其关键是寻找易于识别和区分的特征，通过基于特征集间的相似性度量来找到模板在图像中的匹配位置,使用高级特征的算法进行匹配,基于约束的树搜索，可利用深度优先搜索策略，依靠解释树寻找局部一致的匹配 基于多尺度特征作特征匹配，则是对图像信息引入多种级别的抽象，遵循先轮廓后细节，先宏观后微观，先易于辨认部分后较为模糊部分的人类视觉匹配规律，能提高图像匹配的可靠性,7.3 模板匹配算法,ABS算法归一化互相关匹配算法图像矩匹配算法基于图像特征点的匹配算法,ABS算法,ABS(Absolute Balance Search)算法是基于定义的最原始的方法它的思路就是将模板在被搜索图上移动，逐一比较其覆盖的区域，在所有比较过的情况中，选取查找最相似的区域相似的程度用相关系数来描述 设待匹配图像为F(x，y)，而模板图像为G(x，y)，并且待匹配图像大小为L×W ，模板图像大小为l×w，则在待匹配图像中共有(L—l+1)×(W—w+1)个可能的匹配点存在，每个可能的匹配点对应1个l×w的搜索窗口因此匹配也可以是大小等于模板图像的搜索窗口在待匹配图像上按照某一顺序滑动，每滑动1次就进行1次模板图像和搜索窗口间的计算，以此来判断当前的搜索窗口是否匹配。

如果差别小于预定的阈值，则可认为匹配成功；否则，就认为匹配失败匹配准则,3种匹配准则：实现方便，但如果待匹配图像或是模板图像之一的灰度值发生线性变换，就无所适从了不同的图像和模板有着不同的背景灰度值和不同的搜索窗口，所需的阈值也各不相同，很难事先选定阈值，因而误匹配率很高这种算法只适用于待匹配图是模板图像中部分的情况,,,归一化互相关匹配算法,归一化互相关匹配算法是一种经典的统计算法，通常写为NC(Normalized Correlation)算法这种算法通过计算模板和待匹配图像的互相关值来确定匹配的程度互相关值最大时的搜索窗口位置决定了模板图像在待匹配图像中的位置互相关的定义一般有如下2种形式：,设模板为M(l×w )，其中l、w是M的长和宽；搜索的基准图为S(L×W )，其中L、W是S的长和宽将模板M在基准图S上平移，模板覆盖下的区域为子区域 定义i和j是模板M的左上角像素在基准图中的坐标，那么需要搜索的范围，即坐标(i,j)的范围就是： 1≤i≤W-w 1≤j≤L- l,图7-1 模板与基准图,根据以上的描述，将模板M与子区域 进行比较，在众多的子区域中寻求相似性最大化的那个作为匹配。

定义相似性关系函数为：上式的意义并非是看二者的相似程度，相反，它是看二者相差了多少相似程度越高， 的值反而越小 将上式展开可以得到：,,,D(i, j) 的大小并不能体现模板与子区域的相似程度定义相关函数：归一化，得：当子区域与模板匹配时， 有最大值当子区域与模板完全一样时，R0(i,j) =1；反之 R0(i,j) <1， R0(i,j)的值越大，则子区域与模板相似程度越高,,,,,,,,,这种图像匹配方法计算量非常大，速度非常慢当基准图越大时，速度越慢 还有一种相对简单的模板匹配算法，就是简单地计算模板M与子区域 之间的误差，其公式如下：,图像矩匹配算法,在图像处理中，矩是一种统计特性，可采用不同阶次的矩来计算模板的位置、方向和尺寸变换参数由于高阶矩对噪声和变形非常敏感，因此在实际应用中通常选用低阶来实现图像匹配，一般采用具有平移、旋转与尺寸不变性的矩特征参数对于圆形窗口内的归一化矩阵，可将平移、旋转和尺度变化的模板匹配简化为一般的平移模板匹配这种不变矩在模式识别、图像分类和目标跟踪方面发挥着重要作用在精确寻的中，由于实时图和基准图的获取方式、时间和空间位置都不同，因此实时图相对于基准图就会产生一定的平移、旋转和比例变化等几何失真。

图像矩的几何失真不变性正好克服了这个问题,对于给定的数字图像，定义它的（p+q）阶混合原点矩为相应的（p+q）阶混合中心矩可表示为：其中：用零阶中心矩对各阶中心矩进行规格化，得：利用第二、三阶矩，可导出七个不变矩组,,,,,,,,,,,利用第二、三阶矩，可导出七个不变矩组：利用上面七个式子便可求出任意一个数字地图的七个不变矩，这些不变矩反映了地图的固有特征因此，精确寻的问题可用实时图和基准子图七个不变矩之间的相似度来解决令实时图和基准子图的不变矩分别为Mi和Nj, 则它们之间的相似度为：在所有的试验位置(u,v)上，max{R(u*,v*)} 所对应的位置 即为匹配点该算法称为图像矩算法，这种方法对图像噪声敏感，而且对图像的质量要求较高基于图像特征点的匹配算法,图像特征提取是图像匹配和三维信息提取的基础，是影像分析与图像处理技术领域中最重要的任务之一有效的特征提取算法是影像分析与处理的关键 在基于点特征的图像配准中，特征点的提取是图像配准的关键步骤 常用的点特征提取方法有：Moravec算子、Harri算子、SUSAN算子、Foratner算子等,特征点提取方法,多尺度小波变换法提取边缘点 SUSAN角点提取法 仿射不变Harris特征提取算子 Forstner兴趣算子 Moravec兴趣算子,,多尺度小波变换法提取边缘点,小波变换法提取边缘点比传统的边缘检测方法具有更好的抑制噪声效果，因为如Sobel，Laplacian算子等采用较小的掩模，容易受零星的椒盐噪声的干扰。

小波的多分辨率特性使之可以在不同的尺度上检测边缘小波变换法还能提供边缘的方向信息，这使得可以有效地构建链码缺点是计算量较大，对内存和磁盘空间的需求较大 基于小波变换的边缘提取算法中，小波系数的选取是关键B样条小波是一种实用的最基本的小波，其特点是函数形式简单，具有最小的支集，且易于软、硬件实现此外B样条函数具有非常好的局部特性，可以很方便地控制样条曲线的零交叉点及形状等最常用的是三次B样条小波对图像作多尺度小波变换，在尺度上根据小波变换模的局部极大值提取数量适中的物体边缘点作为特征点,SUSAN角点提取法,角点：两条直线边缘的接合点 图像的角点检测方法： 1. 先将图像分割为区域，用链码表示目标边界，然后通过方向变化确定角点这种方法的主要缺点是角点检测的结果依赖于前面的图像分割的结果 2. 直接对图像灰度级进行操作，这些方法主要利用梯度和曲率度量检测角点Smith等人提出的SUSAN算法为第二类方法 SUSAN算法：用圆形模板在图像上移动，若模板内像素的灰度与模板中心像素灰度的差值小于一定阈值，则认为该点与核具有相同的灰度，由满足这样条件的像素组成 的局部 区域称为“USAN”根据 USAN的尺寸、质心和二阶矩，可检测边缘、角点等特征。

SUSAN角点提取法不涉及图像的求导运算，具有简单直观、特征定位比较准确等优点,仿射不变Harris特征提取算子,Harris算子是C.Harris和M.J.Stephens于1998年提出的基于信号强度的点特征提取算子，具体如下: 1. 构造一个与自相关函数相联系的矩阵A，A阵的特征值是自相关函数的一阶曲率 2. 如果两个曲率值都高，则认为该点是特征点 Harris算子中只用到灰度的一阶差分以及滤波，计算简单同时，由于Harris算子特征点的检测不需设置阈值，可以满足检测自动化的要求Forstner兴趣算子,Forstner算子是从影像中提取点（角点、圆点等）特征的一种较为有效的算子 Forstner算子通过计算各像素的Robert梯度和以像素（c，r）为中心的一个窗口的灰度协方差矩阵，在影像中寻找具有尽可能小而且接近圆的点作为特征点，它通过计算各影像点的兴趣值并采用抑制局部极小点的方法提取特征点Moravec兴趣算子,Moravec于1977年提出利用灰度方差提取点特征的算子Moravec算子是在四个主要方向上，选择具有最大—最小灰度方差的点作为特征点： 第一步，计算各像元的兴趣值IV（interest value）。

第二步，给定一经验阈值，将兴趣值大于该阈值的点（即兴趣值计算窗口的中心点）作为候选点阈值的选择应以候选点中包括所需要的特征点，而又不含过多的非特征点为原则 第三步，选取候选点中的极值点作为特征点近些年应用较多的一种方法是： 首先利用边缘提取方法提取整个图象的边缘轮廓，然后在此轮廓内利用以上特征点提取方法提取特征点 下面以滑动同心窗结合连通区域分析的定位方法为例，说明这种方法在车牌识别中的应用滑动同心窗原理（SCW）,目标检测，是指在一幅或多幅图像中检测用户所感兴趣的区域车牌定位也是目标检测的一种滑动同心窗（sliding concentric windows, SCW）是一种常用的图像分割方法，用于检测用户所感兴趣的各种区域用户可根据待检测目标的特征，定义SCW的参数，实现正确检测 直观上，车牌区域在整幅图像中具有其独自的特征最明显的就是其纹理的不规则，导致其统计特性的急剧变化由于牌照的规格一致，字体的规格也一致，导致这种统计上的变化又具有某些不变的特征SCW可以很好地描述这种“不规则”，它统计父窗口和子窗口中所有像素的均值或者标准差，并根据两者的比值大小，反映窗口区域中像素的变化情况,图7-2 父窗体和子窗体的建立,其算法步骤如下： (1) 建立两个同心窗A和B，A嵌套在B内，称A为子窗口，B为父窗口。

A的大小为(2X1+1)×(2Y1+1)个像素，B的大小为(2X2+1)×(2Y2+1)将B窗体的左上角像素与图像的左上角像素对齐，如下图所示:,,(2) 计算A窗和B窗内像素的统计特性MA和MB (本书使用平均值)，然后对两值进行比较，求其比值如果比值超过阈值(根据待检测目标的特性，由用户设定，为一经验值)，则认为窗口的中心像素是属于目标区域(本文则认为是车牌像素点)，置为255；否则认为是非车牌像素点，置为0判决规则如下：,图7-3 SCW处理前后对比,(3) 按照如上步骤扫描全图，判决所有像素点，并得到二值图 SCW是对原始图像进行处理的第一步，在得到的二值图中，判决为车牌的点像素值为255，非车牌点像素值为0用SCW处理后的一些结果如下图所示：,连通区域分析（CCA）,原始图像经过SCW处理后，成为一幅二值图像其中白色像素点代表可能的车牌区域，黑色像素点代表非车牌区域整幅图像表现为多个子区域，例如在图（7-3）中，包含有车牌区域，两个车灯区域，散热器区域，以及其他区域 接下来就需要分割区域，并分析各个区域的特点，并从中找出车牌区域 连通区域分析(connected component analysis, CCA)是一种图像分析算法，它分析输入图像中各像素间的连通性，并根据这种连通性，将图像分割为多个连通区域，同时还得到各个连通区域的几何特征(面积，方向，重心等等)。

各个区域内的像素点之间存在直接或者间接的相邻性，不同区域内的像素点之间不存在直接或者间接的相邻性 相邻性有4连通或者8连通等不同定义。