第六章影像匹配理论与算法

1、2022年6月26日1第六章第六章 影像匹配理论与算法影像匹配理论与算法第一节：影像相关的基本原理第一节：影像相关的基本原理第二节：影像相关的谱分析第二节：影像相关的谱分析第三节：影像匹配的基本算法第三节：影像匹配的基本算法第四节：最小二乘法影像匹配第四节：最小二乘法影像匹配第五节：特征匹配第五节：特征匹配相关函数 电子相关光学相关数字相关 主要内容 第一节：影像相关的基本原理第一节：影像相关的基本原理 影像相关是利用互相关函数，评价两块影像的相似性以确定同名点 。示意图 互 相关 函数相似程度同名点目标区搜索区相关函数 两个随机信号x(t)和y(t)的互相关函数定义为 dttytx)(Rxy

2、)()(dttytxT)(RTTxy)()(10limdttytxT)(RTxy)()(10当x(t)=y(t)时，则得到自相关函数 dttxtx)(Rxx)()(dttxtxT)(RTTxx)()(10limdttxtxT)(RTxx)()(10均值估计值l自相关函数是偶函数自相关函数是偶函数 自相关函数的性质( )()RR01lim( ) ()TTR( )x t x tdtT01( ) ()( ) ()limTTTTx t x tdtx t x tdtT000,1()lim( ) ()1lim() ( )1lim( ) ()( ) ()1lim( ) ()( )TTTTTTTTttRx t

3、 x tdtTx tx t dtTx t x tdtx t x tdtTx t x tdtRT 令则自相关函数在=0处取得最大值 abba222)()(2)()()()(txtxtxtxtxtxTTTTdttxtxTdttxtxT00)()(1lim)()(1limdtxxtxTTT)()(21lim0这个性质极为重要，它是三种相关技术确定同名像点的依据 两边取时间T的平均值并取极限 )()0(RR电子相关 电子相关就是采用电子线路构成的相关器来实现影像相关的功能 图5-1-1电子相关dttytx)(Rxy)()(光学相关光的干涉和衍射-傅立叶变换特性 dxdyyvxufjyxgvuG)(2e

4、xp),(),( 相干光学计算机 相干光学相关系统 三个傅立叶透镜L1，L2，L3及激光源与光电倍增管等器件组成 数字相关二维相关 数字相关是利用计算机对数字影像进行数值计算的方式完成影像的相关 目标区 搜索区 22,2222,22max0000,mkimkjjnlinliiijrc相似性测度一维相关 在核线影像上，只需要进行一维搜索 目标区 搜索区 影像的功率谱估计影像的功率谱估计 相关函数估计相关函数估计金字塔影像的建立金字塔影像的建立主要内容 第二节：影像相关的谱分析第二节：影像相关的谱分析影像相关的谱分析 维纳-辛钦定理：随机信号的相关函数与其功率谱是一傅立叶变换对，即相关函数的傅立叶

5、变换即功率谱，而功率谱的逆傅立叶变换即相关函数：)()(fSRxyxy2)()(fXfSx)()()(*fYfXfSxy两个随机信号x(t)和y(t)的傅立叶变换为X(f)与Y(f)，则x(t)的自功率谱为影像功率谱x(t)与y(t)的互功率谱为 其中X*（f）为X（f）的复共轭。 影像功率谱的估计 对一些有代表性的航空影像进行功率谱估计，航空影像功率谱近似呈指数曲线状。 fabefS)() 0()(aefSfa标准化功率谱的估计函数相关函数的估计 )0()(aefSfa 标准化功率谱估计为 影像的相关函数估计 dfeeRfjfa2)(22422121aajaja使 R(0)=1,得 22)(

6、411)(aR相关函数的估计 当a较小时，S（f）较平缓，高频信息较丰富，此时相关函数R（）较陡峭，相关精度高，但由可能的近似位置到正确相关的点间距离（称为拉入范围）较小。这就要通过低通滤波获得较大的拉入范围。当a较大时，功率谱S（f）较陡峭，低频信息占优势，因而相关函数R（）较平缓，相关精度较差，但拉入范围较大，相关结果出错的概率较小。金字塔影像相关（分频道相关）从粗到精的相关策略。即先通过低通滤波，进行初相关，找到同名点的粗略位置，然后利用高频信息进行精确相关。 对于二维影像逐次进行低通滤波，并增大采样间隔，得到一个像元素总数逐渐变小的影像序列，将这些影像叠置起来颇像一座金字塔，因而称之为

7、金字塔影像结构 分频道相关（多级相关） 分频道可采用两像元平均、三像元平均、四像元平均等等分若干频道的方法 12345678910 11 12123456123123456789101112123412金字塔影像建立 每2X24个像元平均为一个像元构成第二级影像，在第二级影像的基础上构成第三级影像。 四像元平均 九像元平均 金字塔影像层的确定方法 将原始影像称为第零层，则第一层影像的每一像素相当于零层的（ll）l个像素，第k层影像的每一像素相当于零层的（ll）k个像素 由影像匹配窗口大小确定金字塔影像层数 wINT（n/lk0.5）lw 影像长度由先验视差确定金字塔影像层数 Slpkmax最大

8、左右视差左 右 搜索距离基于像方的匹配算法 基于物方的匹配算法影像匹配的精度主要内容 第三节：影像匹配的基本算法第三节：影像匹配的基本算法数字影像匹配基本算法影像匹配实质上是在两幅（或多幅）影像之间识别同名点 常见的五种基本匹配算法 同名点的确定是以匹配测度为基础 )(ijgG)(ijgG相关函数（矢量数积） DyxdxdyqypxgyxgqpR),(),(),(),( R（ p0, q0） R（p, q）（ pp0， qq0） 若 R（ p0, q0） R（p, q）（ pp0， qq0），则 p0, q0为搜索区影像相对于目标区影像的位移参数。对于一维相关应有q 0。cjriminjjig

9、grcR ,11,),(),(),(00rcRrcR),(00ccrr若则c0, r0为搜索区影像相对于目标区影像的位移行、列参数。对于一维相关应有r 0。 离散灰度数据对相关函数的估计公式为 NijiyxYXR1)(相关函数的估计值即矢量X与Y的数积 在N维空间 y1，y2，,yN中，R是y1，y2，,yN的线性函数 max1NijiyxR它是N维空间的一个超平面。当N=2时 R x1yl x2y2 （X Y） |X| |Y|cos max |Y|cos max 相关函数最大（即矢量X与Y的数积最大）等价于矢量Y在X上的投影最大 协方差函数（矢量投影）DyxdxdyqypxgEqypxgyx

10、gEyxgqpC),(),(),(),(),(),(DyxdxdyyxgDyxgE),(),(1).(DyxdxdyqypxgDqypxgE),(),(1),(若C（p0, q0） C（p, q）（ pp0， qq0），则 p0, q0为搜索区影像相对于目标区影像的位移参数。对于一维相关应有q 0。 )()(),(,11,ggggrcCcjriminjjiminjcjrircgnmg11,1minjjignmg11,1 C（c0, r0） C（c, r）（ cc0， rr0）则c0, r0为搜索区影像相对于目标区影像的位移行、列参数 NiNijijiyxyyxxYXC11)()(协方差函数的估

11、计值即矢量的数积 C是Y在X的投影与X的长之积，因而协方差测度等价于Y在X上投影最大，maxC在二维空间中是平行于（或E）的一条直线 减去信号的均值等于去掉其直流分量。因而当两影像的灰度强度平均相差一个常量时，应用协方差测度可不受影响。相关系数（矢量夹角） ),(),(),(qpCCqpCqpggggDyxggdxdyyxgEyxgC),(2),(),(DyxggdxdyqypxgEqypxgqpC),(2),(),(),( 若（p0, q0） （p, q）（ pp0， qq0），则 p0, q0为搜索区影像相对于目标区影像的位移参数。对于一维相关应有q 0。minjminjcrcjrijim

12、injcjrijiggggggggrc11112,2,11,)()()(),(minjcjrircgnmg11,1minjjignmg11,1相关系数的实用公式为：minjminjminjcjricjriminjjijiminjminjcjriminjjicjrijignmggnmgggnmggrc1111211,2211,21111,11,)(1)(1)( )(1)(),(coscos)( YXYXYXYX 相关系数的估计值最大，等价于矢量X与y的夹角最小 1取值范围满足 相关系数是灰度线性变换的不变量NiiiNiiiyyxxyyxx1221)()()(baYYNiNiiiNiiiyyxxy

13、yxx11221)()()(即灰度矢量经线性变换后相关系数是不变的 NiNiiiNiiibyabayxxbyabayxx11221)()()()(差平方和（差矢量模） dxdyqypxgyxgqpSDyx2),(2 ),(),(),(2,11,2)(),(cjriminjjiggrcS 若S2（c0, r0） S2（c, r），则c0, r0为搜索区影像相对于目标区影像的位移行、列参数。对于一维相关应有r 0。 NiiiNNyxyxyxyxYXS12222221122)()()()(两影像窗口灰度差的平方和即灰度向量X与Y之差矢量 故差平方和最小等于N维空间点Y与点X之距离最小。当N2时，mi

14、n)()(2222112yxyxS二维平面上以（x1，y2）为中心、边长为、对角线与坐标轴平行的一个正方形 二维平面上的一个圆 差绝对值和（差矢量分量绝对值和） dxdyqypxgyxgqpSDyx),(),(),(),( minjcjrijiggrcS11,),(离散灰度数据差绝对值和的计算公式为 若S（c0, r0） S（c, r）（ cc0， rr0），则c0, r0为搜索区影像相对于目标区影像的位移行、列参数。对于一维相关应有r 0。NiiiNNyxyxyxyxS12211两影像窗口灰度差绝对值和即灰度矢量X与Y之差矢量之分量的绝对值之和当N=2时， min2211yxyxS基于物方的

15、影像匹配（VLL法） 影像匹配的目的是提取物体的几何 信息，确定其空间位置，能够直接确定物体表面点空间三维坐标的影像匹配方法得到了研究，这些方法也被称为“地面元影像匹配” 在物方有一条铅垂线轨迹，它在影像上的投影是一直线。就是说VLL与地面交点A在影像上的构像必定位 于 相 应 的“投影差”上。铅垂线轨迹法（VLLVertical Line Locus) 地面AVLL法影像匹配示意图A?在铅垂线上地面A那一个点正确？具体步骤给定地面点的平面坐标（X，Y） 与近似最低高程Zmin。 ZiZminiZ 高程搜索步距Z可由所要求的高程精度确定)()()()()()()()()()()()()()()

16、()()()()()()()()()(333222333111333222333111ssssssissssssissssssissssssiZZcYYbXXaZZcYYbXXafyZZcYYbXXaZZcYYbXXafxZZcYYbXXaZZcYYbXXafyZZcYYbXXaZZcYYbXXafx 计算左右像坐标（xi, yi）与（xi”，yi”）： 分别以（xi, yi）与（xi”，yi”）为中心在左右影像上取影像窗口，计算其匹配测度，如相关系数pi。 将i的值增加1，重复（2），（3）两步，得到0，1，2，n取其最大者k： k max0，1，2，n还可以利用k及其相邻的几个相关系数拟合

17、一抛物线，以其极值对应的高程作为A点的高程，以进一步提高精度，或以更小的高程步距在一小范围内重复以上过程。图5-3-7 相关系数抛物线拟合 影像匹配（相关）即使在定位到整像素的情况下，其理论精度也可达到大约0.3像素的精度。影像匹配精度 影像相关是左影像为目标区与右影像上搜索区内相对应的相同大小的一影像相比较，求得相关系数，代表各窗口中心像素的中央点处的匹配测度 整像素相关的精度 半个像素2222)(dxxxx02,/1)(xx29. 0 x整像素相关的精度 误差服从内的均匀分布（为像素大小） 1222x用相关系数的抛物线拟合提高相关精度 f(s)= A BS CS2 图6-3-7 相关系数抛

18、物线拟合CBAACBAiii11抛物线顶点k处的位置应为 CBik2取相邻像元3个相关系数进行抛物线拟合时 11112(2/)(iiiiiiCBA 由相关系数抛物线拟合可使相关精度达到0.150.2子像素精度 11112(2iiiiiikCBik211112(2/)(iiiiiiCBA最小二乘法影像匹配的原理 单点最小二乘法影像匹配最小二乘法影像匹配精度主要内容 第四节：最小二乘法影像匹配第四节：最小二乘法影像匹配最小二乘影像匹配德国Ackermann教授提出了一种新的影像匹配方法最小二乘影像匹配（least Squares Image Matching）影像匹配可以达到1/10甚至1/100

19、像素的高精度优点如下l最小二乘影像匹配中可以非常灵活地引入各种已知参数和条件，从而可以进行整体平差。 l解决“单点”的影像匹配问题，以求其“视差”；也可以直接求解其空间坐标 l同时解决“多点”影像匹配或“多片”影像匹配 l引入“粗差检测”，从而大大地提高影像匹配的可靠性 最小二乘影像匹配原理“灰度差的平方和最小” minvv),(),(2211yxgnyxgn仅仅认为影像灰度只存在偶然误差 ),(),(21yxgyxgv 按vvmin原则进行影像匹配的数字模型。若在此系统中引入系统变形的参数，按 vvmin的原则，解求变形参数，就构成了最小二乘影像匹配系统。灵活,可靠和高精度是优点, 缺点是，

20、如当初始值不太准时，系统的收敛性等问题有待解决。辐射畸变l照明及被摄影物体辐射面的方向l大气与摄影机物镜所产生的衰减l摄影处理条件的差异以及影像数字化过程中所产生的误差等等影像灰度的系统变形有两大类：辐射畸变；几何畸变。几何畸变l摄影机方位不同所产生的影像的透视畸变l影像的各种畸变l由于地形坡度所产生的影像畸变等竖直航空摄影的情况下，地形高差则是几何畸变的主要因素。 在影像匹配中引入这些变形参数，同时按最小二乘的原则，解求这些参数，就是最小二乘影像匹配的基本思想。仅考虑辐射的线性畸变的最小二乘匹配相关系数 2221011),(),(ngyxghhnyxg)(21210ggghhv误差方程：按v

21、vmin的原理，可得法方程式 22211220221120)()()(ggghghggghgnh)(11)(12210222212211hgggnhgngggnggh假定对g1，g2已作过中心化处理 0;0;0021hgg122121gggh即：)(21210ggghhv22212212112221222222122122122)(2)()(ggggvvgggggggggggggggvv消除了两个灰度分布的系统的辐射畸变后，其残余的灰度差的平方和为 相关系数与vv的关系 )1(221gvv22212122)(gggg相关系数2211gvvvv是噪声的功率g12为信号的功率 以“相关系数最大”作

22、为影像匹配搜索同名点的准则，其实质是搜索“信噪比为最大”的灰度序列 信噪比 vvgSNR212)()1 (1)(22SNR相关系数与信噪比之间的关系 影像匹配的主要目的是确定影像相对移位，传统的算法采用目标区相对于搜索区不断地移动一个整像素，搜索最大相关系数的影像区中心作为同名像点 。 在最小二乘影像匹配算法中，可引入几何变形参数，直接解算影像移位，这是此算法的特点。 仅考虑影像相对移位的一维最小二乘匹配 假设两个一维灰度函数g1(x), g2(x),除随机噪声外，g2(x)相对于g1(x)只存在零次几何变形移位量x。)()()()(2211xnxxgxnxg)()()(12xgxxgxv误差

23、方程式2)()()(222xgxgxg 离散的数字影像而言，灰度函数的导数g,2(x)可由差分代替 )()()()(212xgxgxxgxv为解求相对移位量x，需上式进行线性化 最小二乘影像匹配是非线性系统，必须进行迭代。迭代过程收敛的速度取决于初值。222/gggxgxgv2误差方程式可写为 解得影像的相对移位 单点最小二乘影像匹配 两 个 二 维 影像 之 间 的 几何 变 形 ， 不仅 仅 存 在 着相 对 移 位 还存 在 着 图 形变化 x2 y2灰度畸变+几何变形 几何变形 经线性化后误差方程式gdbcdbcdbcdacdacdacdhcdhcvo281706251403121dh

24、。，dh1， da0，,db2是待定参数的改正值，它们之初值分别为 h0 = 0； h1 = 1；a0 = 0；a1 = 1；a2 = 0； b0 = 0；b1 = 0； b2 = 1)()(LCXCCTTLCXVyyyxxxxgybyygcgxbyygcgbyygcgyaxxgcgxaxxgcggaxxgcgcc2222812227022262222512224202223221)(1), 1(), 1(21),()1,() 1,(21),(2222JIgJIgJIggJIgJIgJIggIxJy 在数字影像匹配中，灰度均是按规则格网排列的离散阵列，且采样间隔为常数，可被视为单位长度，上式中

25、的偏导数均用差分代替：几何改正重采样辐射畸变改正是否迭代计算最佳匹配的点位计算参数值结束左片右片最小二乘法匹配流程图几何变形改正。根据几何变形改正参数a0, a1, a2,b0, b1, b2将左方影像窗口的影像坐标变换至右方影像阵列：重采样。由于换算所得之坐标x2，y2一般不可能是右方影像阵列中的整数行列号，因此重采样是必须的。ybxbbyyaxaax21022102辐射畸变改正。利用由最小二乘影像匹配所求得辐射畸变改正参数h0, h1；对上述重采样的结果作辐射改正若相关系数小于前一次迭代后所求得的相关系数，则可认为迭代结束.也可以根据几何变形参数是否小于某个预定的阈值。 采用最小二乘影像匹

26、配，解求变形参数的改正值dh0,dh1, da0,。 计算变形参数 yxbbbaaayxiiiiii1001210210221yxbbbaaadbdbdbdadadaiiiiiiiiiiii100111001121110121110210210ybxbbyyaxaax21022102iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiidbbdbabbdbbdbabbdbbdbadbbbdabdaaaadabdaaaadabdaadaaa21211212221111111121011001002121121222111111112101100100211101021011

27、011011011ghhdhdhghhgiiiiiii11-i11-i1i1i11-i0i01-i0i0dhhhhdhhdhhh对于辐射畸变参数满足： 计算最佳匹配的点位 .可用梯度的平方为权，在左方影像窗口内对坐标作加权平均：2222/yyixxiggyyggxxybxbbyyaxaax21022102匹配精度取决于影像灰度的梯度 为了进一步提高其可靠性与精度，例如，附带共线条件的最小二乘相关以及与VLL法结合的最小二乘影像匹配方法都得了广泛的研究 最小二乘影像匹配的精度 最小二乘匹配算法，则可以根据以及法方程式系数矩阵的逆矩阵，同时求得其精度指标 2220/xg222/xggg 20220

28、vn为目标区像元个数。由于上式右边是无偏估计，所以220/11vn2221gvxnvgSNR22221vxgn SN R信噪比方差2222)1(gvxn)1 (1)(22SNR相关系数与信噪比之间的关系 影像匹配的精度与相关系数有关，相关系数愈大则精度愈高。它与影像窗口的“信噪比”有关，信噪比愈大，则匹配的精度愈高。 可以得到一些很重要的结论： 影像匹配的精度还与影像的纹理结构有关，即与 有关。特别是当 愈大，则影像匹配精度愈高。当 ，即目标窗口内灰度没有变化时，则无法进行影像匹配。)/(ggg 02 g特征匹配的概念基于特征点的影像匹配策略 跨接法影像匹配主要内容 第五节：特征匹配第五节：特

29、征匹配特征匹配以影像的灰度分布为影像匹配的基础，被称为灰度匹配（Area Based Image Matching） 特 征 匹 配 （ F e a t u r e B a s e d Matching，在计算机界也称为 Primitive Based Matching）。 当待匹配的点位于低反差区内， 其匹配的成功率不高。 目的只需要配准某些点线或面 在城市中，被处理的对象主要是人工建筑物，灰度匹配难以适应 特征匹配使用的几种场合特征匹配步骤特征的匹配可以分为点、线、面特征匹配可分为三步： 特征提取；利用一组参数对特征作描述；利用参数进行特征匹配。 iSffijijji)(11例 如 ： 首 先 可 以 用 边 缘 算 子（Edge Operator）从影像中提取边缘，然后再用参数描述“边缘”。常用-S曲线 表 达 边缘： 基于特征点的影