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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第（,*,）页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,目录,7.1,基本概念,7.2,图像匹配算法分类,7.3,模板匹配算法,7.4,改进算法,7.1 基本概念,模板匹配可以分为狭义的和广义的。,狭义匹配：匹配的目标是同一样事物。,因为一个事物的自身特点总是固定的，比如颜色、大小、形状等等，即便由于环境的不同而导致获取的图片有差别，只要计算机能够分辨出这些特征就可以识别事物。,广义的匹配：匹配的是一类事物。,如，某一种动物，某一类型的汽车等。相比于前一种匹配，这种方式更为复杂，需要系统具备一定的学习和推理能力。,7.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),的大小并不能体现模板与子区域的相似程度。定义相关函数：,归一化，得：,当子区域与模板匹配时，,有最大值。当子区域与模板完全一样时，,R,0,(i,j),=1,；反之,R,0,(i,j),1,，,R,0,(i,j),的值越大，则子区域与模板相似程度越高,这种图像匹配方法计算量非常大，速度非常慢。当基准图越大时，速度越慢。,还有一种相对简单的模板匹配算法，就是简单地计算模板M与子区域 之间的误差，其公式如下：,图像矩匹配算法,在图像处理中，矩是一种统计特性，可采用不同阶次的矩来计算模板的位置、方向和尺寸变换参数。由于高阶矩对噪声和变形非常敏感，因此在实际应用中通常选用低阶来实现图像匹配，,一般采用具有平移、旋转与尺寸不变性的矩特征参数,。对于圆形窗口内的归一化矩阵，可将平移、旋转和尺度变化的模板匹配简化为一般的平移模板匹配。,这种不变矩在模式识别、图像分类和目标跟踪方面发挥着重要作用。在精确寻的中，由于实时图和基准图的获取方式、时间和空间位置都不同，因此实时图相对于基准图就会产生一定的平移、旋转和比例变化等几何失真。图像矩的几何失真不变性正好克服了这个问题,对于给定的数字图像，定义它的（,p+q,）阶混合原点矩为,相应的（,p+q,）阶混合中心矩可表示为：,其中：,用零阶中心矩对各阶中心矩进行规格化，得：,利用第二、三阶矩，可导出七个不变矩组,利用第二、三阶矩，可导出七个不变矩组：,利用上面七个式子便可求出任意一个数字地图的七个不变矩，这些不变矩反映了地图的固有特征。因此，精确寻的问题可用实时图和基准子图七个不变矩之间的相似度来解决。,令实时图和基准子图的不变矩分别为,M,i,和,N,j,则它们之间的相似度为：,在所有的试验位置,(u,v),上，,maxR(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,的大小为,(2X,1,+1)(2Y,1,+1),个像素，,B,的大小为,(2X,2,+1)(2Y,2,+1),。将,B,窗体的左上角像素与图像的左上角像素对齐，如下图所示,:,(2),计算,A,窗和,B,窗内像素的统计特性,M,A,和,M,B,(,本书使用平均值,),，然后对两值进行比较，求其比值。如果比值超过阈值,(,根据待检测目标的特性，由用户设定，为一经验值,),，则认为窗口的中心像素是属于目标区域,(,本文则认为是车牌像素点,),，置为,255,；否则认为是非车牌像素点，置为,0,。判决规则如下：,图,7-3 SCW,处理前后对比,(3),按照如上步骤扫描全图，判决所有像素点，并得到二值图。,SCW,是对原始图像进行处理的第一步，在得到的二值图中，判决为车牌的点像素值为,255,，非车牌点像素值为,0,。用,SCW,处理后的一些结果如下图所示：,连通区域分析（CCA）,原始图像经过,SCW,处理后，成为一幅二值图像。其中白色像素点代表可能的车牌区域，黑色像素点代表非车牌区域。整幅图像表现为多个子区域，例如在图（,7-3,）中，包含有车牌区域，两个车灯区域，散热器区域，以及其他区域。,接下来就需要分割区域，并分析各个区域的特点，并从中找出车牌区域。,连通区域分析,(connected component analysis,CCA),是一种图像分析算法，它分析输入图像中各像素间的连通性，并根据这种连通性，将图像分割为多个连通区域，同时还得到各个连通区域的几何特征,(,面积，方向，重心等等,),。各个区域内的像素点之间存在直接或者间接的相邻性，不同区域内的像素点之间不存在直接或者间接的相邻性。,相邻性有,4,连通或者,8,连通等不同定义。,图,7-4,欧拉数定义示意图,CCA,算法可以很容易地从图（,7-3,）中分析出车牌区域，车灯区域，散热器区域，以及其他区域，并得到这些区域的特性。为了在多个区域中区分车牌区域和其他区域，长宽比和欧拉数是最关键的区域特征。为了简便起见，下文将连通区域简称为“斑块”。,斑块的长宽比定义为该斑块的外接矩形的长宽比。牌照的长宽比处在,2,3,之间，根据这一特征，可排除不满足条件的斑块。,斑块的欧拉数定义为斑块内部所含有的闭合曲线数，也可理解为斑块内部含有的“空洞”的数目。如下图所示：,图,7-5,字符“空洞”,斑块“,A,”内部仅有一个“空洞”，其欧拉数为,1,；斑块“,B,”内部有两个“空洞”，其欧拉数为,2,。,可以看到，经过,SCW,处理后，车牌斑块由于大量字符的存在，使其内部存在与字符相对应的“空洞”，并且这些“空洞”满足一定的大小要求。如下图所示：,图,7-6,浅底深字情况的处理结果,字符“空洞”是车牌斑块最重要的特性，由图,7-5,可见，车牌斑块内部存在,7,个左右和字符大小相近的“空洞”，其欧拉数约为,7,；而其他斑块或者欧拉数太少，或者虽然有足够的欧拉数，但“空洞”太大或者太小，不符合字符特征。根据斑块欧拉数，可以准确地确定车牌区域。,问题：对于浅底深字,(,如蓝底黑字,),的情况，经过,SCW,步骤后，车牌不成为一个斑块，字符互相独立。此时经过,CCA,步骤后，得到的车牌数为,0,。如下图所示：,图,7-7,浅底深字问题解决后的效果,解决方法：将原图取反，再重复,SCW,和,CCA,步骤，即可得到车牌区域，如下图所示：,多尺度小波变换的边缘点提取,在几种特征点提取算法中，基于多尺度小波变换的边缘点提取方法，其适应性和抗噪性强，提取的特征点能有效的实现匹配，在自动配准中能广泛的适用。,缺点：小波变换是全局的变换，无法对图像作分块并行处理，计算复杂度高，对于大尺寸的图像，只能采用基于金字塔结构的方法逐层提取和映射，减少计算量，提高运算速度。,Harris,算子是基于信号的点特征提取算子，给出了与自相关函数相联系的矩阵,M,。,M,矩阵的特征值是自相关函数的一阶曲率，如果,2,个曲率值都很高，就认为该点是特征点。,Harris,算子的公式只涉及图像的一阶导数：,(7-15),角响应公式,：,式中，,是,g,x,方向的梯度，,是,g,y,方向的梯度，,G,为高斯模板，,det,为矩阵的行列式，,tr,为矩阵的直迹，,k,为默认常数。,一般做法：若,I,大于某个给定的阈值时,即认为相应局部窗口的中心点是一个角点。,Harris特征提取算子,书中方法：在实际操作中，可依次从以每个像素为中心的,33,的窗口中提取最大值，如中心点像素的值就是最大值，则该点就是特征点。,局部极值点的数目很多，可对极值点排序，根据要求选出兴趣值最大的若干点作为最后的结果。,Harris,算子计算简单，提取的点特征均匀合理，且可根据需要定量地提取特征点。在图像发生旋转、灰度发生变化、噪声影响和视点变换的情况下，,Harris,算子是最稳定的点特征提取算子。,SIFT,算法,在图像特征提取与匹配领域中，如何提取稳定的特征，提高匹配的准确度是一个关键的问题。下面介绍一种基于图像特征点提取及匹配的方法，尺度不变特征变换,(SIFT,，,Scale Invariant Feature Transform),算法。,SIFT,算法主要思想是利用多尺度变换在尺度空间中寻找极值点，提取特征点位置和方向，使其对图像缩放、旋转、光线变化甚至仿射变换保持不变。,(1),图像的多尺度表示,为了模拟人类在不同距离观察事物的过程，形成了多尺度空间方法。经研究发现高斯函数是唯一的尺度空间内核函数。,SIFT,算法定义图像尺度空间函数为,L(,x,y,),，输入图像用,I(,x,y,),表示，利用高斯内核函数对输入图像进行卷积操作，则有：,其中，,G(,x,y,),为尺度可变高斯函数，具体如下：,这里，,(,x,，,y,),为空间坐标；,为尺度坐标。采用不同的,对图像进行高斯卷积，得到高斯图像金字塔，从而增强,SIFT,算法对于图形缩放的适应能力。,SIFT算法分析,高斯差分,(DOG,，,Difference of Gaussian),函数为,其中,k,为常数。,Mikolajczyk,通过实验发现相对于其他的特征提取函数，通过求高斯拉普拉斯函数,的最大和最小值能得到最稳定的图像特征点，并且由于,所以用,DOG,函数也可以得到最稳定的图像特征点。每一个采样点要和它所有的相邻像素点进行比较，看是否为其所在图像域和尺度域的检测邻域中的极值点。从而,SIFT,算法能够获取稳定的图像特征点。,(2)求高斯差分空间极值,DOG,空间极值有对噪声敏感的低对比度点和对边缘响应敏感的边缘响应点，必须去除。,低对比度点去除：将尺度空间函数,D(,x,y,),进行,2,阶泰勒展开，求其导数并将其值设为,0,，则可以得到：,将其加到其样本点上从而得到在极值位置处的插值估计值,将,小于某一阈值的点视为低对比度点去除。,(3)去除低对比度点和边缘响应点,边缘响应点去除,一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。由于,D,的主曲率和,Hessian,矩阵,H,的特征值成正比，为了检测主曲率是否在某域值,(,为,H,阵最大特征值与最小特征值的比值,),下，只需检测,Hessian,矩阵（,2,阶导数矩阵）：,去除低对比度点和边缘响应点，可提高,SIFT,算子的抗噪声能力。,(4)赋予特征点方向信息,计算特征点,(,x,，,y,),处梯度的模值和方向。,在以特征点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。直方图的峰值代表了该特征点处邻域梯度的主方向，即作为该特征点的方向。保证了,SIFT,算法特征点提取具有旋转不变性，同时以子区域的统计特性代替单个像素作为研究对象，提高了对图像局部变形的适应能力。,赋予特征点算子描述符向量,在特征点描述符生成过程中，在处理梯度幅度时进行了类似于高斯函数的加权处理，强化了中心区域，淡化了边缘区域的影响，提高了,SIFT,算子对几何变形的适应性；最后将描述符向量长度归一化，也减小,SIFT,算子对光照变化的影响。,SIFT算法实现,SIFT,算法的实现包括,4,个步骤：,(1),检测尺度空间极值点。首先创建,DOG,金字塔多尺度空间。在,DOG,空间中，中间的检测点和它同尺度的,8,个相邻点和上下相邻尺度对应的,92,个点共,26,个点比较，以确保在尺度空间和二维图像空间都检测到极值点。通过以上方法获取的特征点称为候选特征点。,(2),精确确定极值点位置。将由式,(7-21),计算出所有,D(X),中小于,0.008,的候选特征点视为低对比度候选极值点过滤掉。取,=10,，如果主曲率间的比值大于,10,，则认为该点是位于边缘而被过滤掉，余下的则为,SIFT,特征点。,(3),为每个特征点指定方向参数。梯度直方图的范围是,0-360,，取每,10,一个柱，总共分,36,个柱进行方向直方图的统计计算，为特征点赋予方向参数。,(4),特征点描述子的生成。首先将坐标轴旋转为特征点的方向，对任意一个特征点，在其所在的尺度空间取以特征点为中心的,1616,大小的邻域，再将此邻域均匀地分为,44,个子区域，对每个子区域计算梯度方向直方图,(8,个方向,),；然后，对,44,个子区域的,8,方向梯度直方图根据位置。,每个直方图有,8,方向的梯度方向，每一个描述符包含一个位于关键点附近的四个直方图数组,.,这就导致了,SIFT,的特征向量有,128,维,.,先是一个,44,的来计算出一个直方图，每个直方图有,8,个方向。所以是,448=128,维,将这个向量归一化之后，就进一步去除了光照的影响。,7.4,改进算法,序贯相似性检测算法,基于排序的序贯相关算法,FFT,的相关算法,分层搜索的序贯判决算法,序贯相似性检测算法,模板匹配算法效率很低，实际应用价值不高。原因是模板匹配算法对基准图,S,的所有子区域一视同仁，全部都要运算检验。多数情况下，基准图,S,上与模板相似的子区域并非那么多，这样，过多的运算用在与匹配目标无关的子区域内，做了太多的无用功。,下面介绍一种快速计算方法：序贯相似性检测算法，简称,SSDA,。,SSDA,算法的基本思想是首先定义一个绝对误差值,和一个恒定阈值,。,(7-23),其中，,然后在子区域,中随机选取像素点，并计算该像素点与,T,中对应的像素点的误差值,，并将该值点同其他点对的误差值进行累加。当算术和超过,时则停止累加，并记录累加次数,r,。,由此定义,SSDA,的检测曲面为：,(7-24),接下来把,值最大的点,定为匹配点，因为在这一点上需要很多次累加才能使总误差超过,。如图,7-2,所示，图中的三条曲线分别表示在,A,、,B,、,C,三个参考点上得到的误差累加增长情况。其中,A,、,B,才考点所反映出来的累计误差,增长的结果很快超出了阈值,，这就恰恰反映了模板,T,不再匹配点上。相反，曲线,C,中的,增长较为缓慢，因此它很可能是要寻找的匹配点。,图,7-8,累计误差增长曲线,可以对,SSDA,算法做一些改进以期进一步提高计算效率，具体做法如下：,(1),对多有可能的匹配点不逐个进行匹配，即模板不一定对每点都平移到。而按一定的策略，例如可用粗细结合的均匀搜索，即先每隔,m,个点搜索一下匹配的好坏，然后在有最大匹配值的像素点的周围的局部范围内对各个可能的匹配位置求匹配，而略过匹配值较小的像素点的周围像素的匹配。这样做可以大大减少计算量，但这种策略能否不丢失真正的匹配点主要取决于误差曲面,的平滑性和单峰性。,(2),为了尽早排除掉那些非匹配点，在某个参考点,处，对模板覆盖下的,个点对的计算顺序，可用与,i,，,j,无关的随机方式计算误差。另外一个备选的方式是采用适应图像内容的方式，按模板中突出特征选取伪随机序列，由此决定计算误差的先后顺序。,不选用固定的阈值,，而采用单调增长的阈值学列。这样做可以是非匹配点用更少的计算就达到阈值而被排除掉，真正的匹配点则需要更多此的误差累计才能达到阈值，如图,7-9,所示。,图,7-9,采用阈值序列单调增加的方式改进,SSDA,算法,SSDA,算法比,FFT,的相关算法快,50,倍，是较受人重视的一种算法。,特别地，当待搜索图像为二进制图时，,SSDA,算法还可以简化，这是模板与对应子区域中的成对像素点的差值为：,(7-25),其中,表示异或运算，由此得：,(7-26),上式称作二进制的,Hamming,距离，同样当,D,越小，则子区域同模板的相似度越大。,由前面的讨论可知，任何一种匹配算法的计算量都是采用的相关算法的计算量与搜索区域数目之积来决定的，也就是说：,总计算量,=,（相关算法的计算量）,（搜索区域数目）,因此，为了减少总的计算量，除了上面介绍的匹配方法之外，我们再介绍几种其他的快速计算法。,上式称作二进制的,Hamming,距离，同样当,D,越小，则子区域同模板的相似度越大。,由前面的讨论可知，任何一种匹配算法的计算量都是采用的相关算法的计算量与搜索区域数目之积来决定的，也就是说：,总计算量,=,（相关算法的计算量）,（搜索区域数目）,因此，为了减少总的计算量，除了上面介绍的匹配方法之外，我们再介绍几种其他的快速计算法。,基于排序的序贯相关算法,这种算法的设计思想并不复杂，简单地说就是在对图像灰度进行二进制幅度排序的基础上进行序贯匹配处理，因此算法共分两步。,第一个步骤称为幅度排序预处理。把模板中的各个灰度值按幅度大小排成列的形式，并计算出各自的位置坐标,，然后对它进行二进制（或三进制）编码。编码的具体方式是逐层扫描并将每一层一分为二，分别赋值,1,或,0,，通常选择幅度大的一组赋值为,1,，幅度小的一组赋值为,0,，如果存在某一层的项目数是一个奇数，那么就将该层的中间幅度赋值为,，直到当各组所剩的元素不能再分为止。最后，根据二进位排序的诸列，把模板变换成二进制阵列的一个有序的集合,，,n=1,，,2,，,N,。,第二步是由粗到细的相关过程。顺序地将这些二进制阵列与基准图进行由粗到细的相关，直到确定匹配点为止。,下面举例说明具体的操作方式。假设存在一个,3 3,的图像，如图,XX,所示。首先将图像的幅度按大小排序填入表中，并将对应的位置也顺次填入。可见幅度最大值是,48,，它对应的像素点位置是（,1,，,1,），幅度第二的值是,41,，它对应的位置是（,3,，,3,）,然后进行分层编码。因为共有,9,个幅度值，因此中间幅度值,24,被赋为,。这样剩余的幅度选取较大的赋值为,1,，即表中前,4,位被编码为,1,，后,4,位被编码为,0,，记录层号,。然后对后,4,位的值再进行同样的编码，依次递推，最终结果如图,7-10,所示。最终得到的二进制序列分为三层，分别由,、,、,III,来表示。,图,7-10,图像的幅度排序预处理,得到二进制序列之后，便可以由此构造二进制阵列。二进制阵列是有序的集合,，,n=1,，,2,，,，,N,，其中,N,是二进制排列的分层数，在这个例子中,N=3,。,继续上面的步骤，幅度是,48,的像素点的位置是（,1,，,1,），二进制编码是,111,。因此，在构造的,3,个二进制阵列,、,、,的（,1,，,1,）位置上分别填入,1,、,1,、,1,三个编码值；幅度是,41,的像素点的位置是（,3,，,3,），二进制编码是,110,。因此，在构造的,3,个二进制阵列,、,、,的（,3,，,3,）位置上分别填入,1,、,1,、,0,三个编码值；,依次类推最终得到的结果如图,7-11,所示。,图,7-11,二进制阵列,下面是算法的第二个步骤，序贯地将得到的二进制阵列与基准图进行由粗到细的关联，直到找到匹配点为止。对于此例，首先用,阵列与基准图进行如下运算，得：,(7-27),上式的意义解释为：当,阵列放在基准图的某一搜索位置（,u,，,v,）上时，与,阵列中的,1,值相对的基准图像素值之和减去与,阵列中的,0,值相对的基准图的像素值之和，这一计算将忽略与,阵列中的,号对应的基准图像素元。,实际上是一比特量化模板与基准图的积相关函数，它反映了图像中最粗糙的图像结构的信息（即一种高低表示）与基准图的相关。,被称为基本的相关面。,上式的意义解释为：当,阵列放在基准图的某一搜索位置（,u,，,v,）上时，与,阵列中的,1,值相对的基准图像素值之和减去与,阵列中的,0,值相对的基准图的像素值之和，这一计算将忽略与,阵列中的,号对应的基准图像素元。,实际上是一比特量化模板与基准图的积相关函数，它反映了图像中最粗糙的图像结构的信息（即一种高低表示）与基准图的相关。,被称为基本的相关面。,那么，如何通过基本的相关面来减少计算量呢？方法是在基准图全区域的检索过程中，设定一个阈值,，舍弃那些,的点，这样可以很大程度地减少下一轮搜索的目标数。通过这样的操作将更多的计算时间用在更有可能接近目标的区域上，对于,的点，需要进行更加细致的相关运算：,(7-28),同理，在第二次搜索时也设定一个阈值,，并在,的点上以,为基础进行更仔细的运算：,(7-29),再设阈值,等等，依此类推，可以得到第,n,个相关面为：,(7-30),当设阈值为,时，若,的点只有一个，则匹配完成，即点（,u,，,v,）为最佳匹配点。显然，通过逐次细化，阈值将变得越来越小：,(7-31),这样相关的搜索点也会变得越来越少，这样就达到了有效减少总体计算量，并提高相关的处理速度的目的。,这种二进制位的幅度排序算法（即,BARC,算法），所需要的加法总计算量为：,(7-32),其中,k,是一个在,1,和,2,之间的常数，而,L,，,W,和,l,，,w,分别为基准图和模板的尺寸。,FFT,的相关算法,由傅里叶分析中的相关定理可知两个函数在定义域中的卷积等于他们在频域中的乘积，而相关则是卷积的一种特定形式。因此，存在着另一种计算相关函数的方法。虽然这样在时间上并没有缩短，但快速傅里叶变换技术比直接的模板匹配算法速度提高了一个数量级，因此用,FFT,进行频域相关计算是一种可行的方法。,首先把基准图和模板进行二级离散傅里叶变换（,DFT,）。对于基准图，有,(7-33),其中,u,和,v,分别表示,J,和其在方向上的频率变量，且,并假定基准图的尺寸是,M,M,维的。模板的离散傅里叶变换,y,（,u,，,v,）是用同样的方式计算得到的。然后，由相关定理可以写出离散傅里叶变换,为：,(7-34),为此，对,求傅里叶反变换，就可以得出空间域中的相关函数,为：,(7-35),由此可见，相关函数可以通过,DFT,的方法计算出来，而计算,DFT,最有效的方法就是采用,FFT,算法，这种一般在教科书上都可以找到，所以这里略去对它的讨论。,最后根据以上的关系式，我们可以画出,FFT,的相关算法流程图，如图,7-12,所示。显然，这种相关算法可以容易地推广到,FFT,的归一化算法。,如果被测试图像的像素和试验位置数越大的话，那么这种算法在时间上就更加节省了。但是要注意，由于傅里叶变换是个周期函数，因此匹配点会以周期的形式出现，所以在运算时，必须采取其他适当的措施。,图,7-12 FFT,相关算法,分层搜索的序贯判决算法,这种分层搜索算法是基于人们寻找事物的习惯而形成的，人们寻找事物是先从大范围找起，再一步步往更细的方向寻找。例如在世界地图上找我国首都北京的位置，总要先找到中国，这叫做粗相关；在这个区域内在仔细确定北京的位置，这叫做细相关。所以由这种思想形成的分层搜索算法具有相当搞的处理速度。如,BARC,算法一样，它也是由两个步骤组成的。,第一步：分层预处理。,首先，对被匹配的图像进行分层预处理。方法是将图,2 2,维的邻区域逐个网络地进行平均处理，从而得到一个分辨率更低和维数更小的图像。然后，将此图像再用同样的方法处理后，得到一个分辨率更低和维数更小的图像，依次进行下去。如果一共进行了,K,次分层处理，那么我们就可以得到,K,个处理后的图像。加上原图像便可构成一组分辨力由高到低，而维数由大到小的图像序列。这种技巧称之为分层预处理。,如果将上述分层技术应用与基准图和模板，就可以获得两个这样的图像序列：一个是基准图的，另一个是模板的。它们分别表示为：,其中,k,=0,，,1,，,，,L,，且已假设基准图是,M,M,维的，而模板是,N,N,维的。,因为原图的分辨力最高且维数最大，所以,k,=0,的图像,和,具有最高的分辨力，,k,=,L,的图像,和,则具有最低的分辨力。,如前所述，若采用先粗后细的相关方法，则可以很快地找到匹配点。所以，第一次相关搜索是从分辨力最低和维数最小的一对图像,和,（,K,=,L,）开始的。这是，由于,的像素数比较少，加上损失了一部分高频信息，所以在粗相关的过程中，正确截获率,将是不大的。所以，为了提高,应设法改善,和,的信噪比。例如：将具有较高分辨力的,（或,）通过低通滤波器以后，再以二倍于它的采样间隔进行采样，而得到的,（或,）比用直接分层法得到的具有更高的信噪比。因此，相对提高了,。显然，其他各层亦作同样的处理。这种技术称之为分层搜索预处理。,第二步：先粗后细的相关过程。,如前所述，第一次相关是从,和,开始的，为了找到可能的粗匹配位置，应将,在,的所有搜索位置上进行相关，并确定出粗匹配位置,。因为这时,和,的维数最小，所以搜索过程是很快的，但这时,值较小，可能产生若干个粗匹配位置。,第二次相关是在较高分辨力的图像,和,之间进行的。这时，因为已经知道了可能的粗匹配位置，所以,只需要在,的一个或若干个粗匹配位置附近进行相关搜索就可以找出一个或者少数几个可能性更大的匹配位置,。,在上述相关过程中，为了不丢失匹配点，应在粗匹配位置,附近增加几个补充试验位置。显然，第三次相关与第二次相关是类似的。如此进行下去，一直到最高分辨力的模板,在基准图,上找到匹配位置时为止。,由此可见，整个搜索过程是从最低分辨力到最高分辨力逐层地进行下去的，为了进一步提高处理速度，相关运算常常采用,SSDA,算法，这种技术成为分层搜索的序贯判决算法。,7.5 其它算法介绍,基于对数极坐标变换的图像匹配算法,(1),相位相关法,设两幅离散图像,和,在空间域存在简单的平移关系：,(7-39),相应的，,和,的傅里叶变换,和,是相关的：,(7-40),则它们的互功率谱为：,(7-41),这里,表示,F,复数的共轭。位移位置是在,。,相位相关法就是求上式的傅里叶反变换，然后通过找峰值的位置确定平移参数,和,。当两幅图像确实相关时，由于检测结果为一个,艿函数，存在较尖锐的检测峰值，所以能实现图像的精确匹配。而当两幅图像毫不相关时，检测结果不会有明显的峰值。因此可以利用这一点来区别两幅图像是否相关。当两幅图像间存在某一灰度差或仅有灰度反转时，这种差别在检测结果中只表现为在,艿函数加一恒量，并不影响检测结果。相位相关算法流程图如图,7-13,所示：,图,7-13,相位相关算法流程图,(2),基于对数极坐标变换的图像匹配算法,对数极坐标变换,图像对数极坐标变换是将笛卡尔坐标系转换至对数极坐标系，这样笛卡尔坐标系下的图像匹配为对数极坐标下的图像匹配，原坐标系下的尺度和旋转变换，相应地转化为平移变换，利用相位相关法可以将尺度和旋转角度检测出来。,图像 到,的对数极坐标变换定义为：,(7-42),(7-43),式中，,分别对应对数极坐标系的极径和极角，,为变换中心。对数极坐标变换关系如图,7-14,所示。,图,7-14,图像对数极坐标变换示意图,基于对数极坐标变换的相位相关法,设两幅离散图像,和,在空间域存在以,为参数的尺度变换和旋转角度为,的旋转变换：,(7-44),则经过对数极坐标变换后得到：,(7-45),从上式中可以看出，经过对数极坐标变换后，,相对于,只存在平移关系，因此可以利用相位相关法获得,和旋转角度,，从而进一步获得缩放尺度,。,基于对数极坐标变换的相位相关法流程图如图,7-15,所示：,图,7-15,基于对数极坐标变换的相位相关法流程图,不同分辨率图像的角点匹配方法,(1),图像的多尺度表示及角点检测,首先构造高分辨率图像的高斯金字塔图像，得到高分辨率图像的多尺度表示。高斯金字塔是由原图像经过连续高斯滤波和二次采样生成的一系列不同分辨率的图像组成。金字塔图像从底层到顶层尺寸连续减小，分辨率连续降低。图像尺寸的迅速减小，有利于减少后续处理中的计算量。为计算简便，高斯金字塔往往利用几幅不同尺度的图像来代替某个较大尺度范围内的所有尺度图像，在尺度量化上较为粗糙。,在得到的金字塔各尺度图像上分别提取角点。角点检测算法中比较著名的有,Harris,算子和,SUSAN,算子，实验研究证明，在角点检测稳定性上,Harris,算子要优于,SUSAN,算子，这对于图像的角点匹配非常有利，因而作者选用,Harris,算子进行角点检测。对于金字塔的第,l,层图像函数,，在点,处的自相关矩阵为：,(7-46),式中,，,为,H,的特征值。若,大于设定阈值且为邻域极大值，则将点,视为角点。,(2),角点特征的提取,为有效匹配角点，需要进一步提取角点处的局部图像特征。一种最为简单的方法是直接提取角点周围一定区域内的灰度值向量，然后进行归一化等处理，匹配时采用灰度互相关方法。这种方法要用很多像素点，导致匹配时的计算量很大，且对图像几何变形及灰度畸变比较敏感。文献中都采用高斯差分不变量作为特征描述方法，这种特征虽然计算简单，但是匹配性能不强，又容易受噪声的影响。此外，还有利用图像局部区域的矩不变量，像素点位置分布的直方图等方法。,Lowe,等在研究尺度不变特征时提出了一种称为,SIF