第六章影像匹配理論與算法

1、2022年6月26日1第六章第六章 影像匹配理論與算法影像匹配理論與算法第一節(jié)：影像相關(guān)的基本原理第一節(jié)：影像相關(guān)的基本原理第二節(jié)：影像相關(guān)的譜分析第二節(jié)：影像相關(guān)的譜分析第三節(jié)：影像匹配的基本算法第三節(jié)：影像匹配的基本算法第四節(jié)：最小二乘法影像匹配第四節(jié)：最小二乘法影像匹配第五節(jié)：特征匹配第五節(jié)：特征匹配相關(guān)函數(shù) 電子相關(guān)光學(xué)相關(guān)數(shù)字相關(guān) 主要內(nèi)容 第一節(jié)：影像相關(guān)的基本原理第一節(jié)：影像相關(guān)的基本原理 影像相關(guān)是利用互相關(guān)函數(shù)，評價兩塊影像的相似性以確定同名點 。示意圖 互 相關(guān) 函數(shù)相似程度同名點目標區(qū)搜索區(qū)相關(guān)函數(shù) 兩個隨機信號x(t)和y(t)的互相關(guān)函數(shù)定義為 dttytx)(Rxy

2、)()(dttytxT)(RTTxy)()(10limdttytxT)(RTxy)()(10當x(t)=y(t)時，則得到自相關(guān)函數(shù) dttxtx)(Rxx)()(dttxtxT)(RTTxx)()(10limdttxtxT)(RTxx)()(10均值估計值l自相關(guān)函數(shù)是偶函數(shù)自相關(guān)函數(shù)是偶函數(shù) 自相關(guān)函數(shù)的性質(zhì)( )()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 令則自相關(guān)函數(shù)在=0處取得最大值 abba222)()(2)()()()(txtxtxtxtxtxTTTTdttxtxTdttxtxT00)()(1lim)()(1limdtxxtxTTT)()(21lim0這個性質(zhì)極為重要，它是三種相關(guān)技術(shù)確定同名像點的依據(jù) 兩邊取時間T的平均值并取極限 )()0(RR電子相關(guān) 電子相關(guān)就是采用電子線路構(gòu)成的相關(guān)器來實現(xiàn)影像相關(guān)的功能 圖5-1-1電子相關(guān)dttytx)(Rxy)()(光學(xué)相關(guān)光的干涉和衍射-傅立葉變換特性 dxdyyvxufjyxgvuG)(2e

4、xp),(),( 相干光學(xué)計算機 相干光學(xué)相關(guān)系統(tǒng) 三個傅立葉透鏡L1，L2，L3及激光源與光電倍增管等器件組成 數(shù)字相關(guān)二維相關(guān) 數(shù)字相關(guān)是利用計算機對數(shù)字影像進行數(shù)值計算的方式完成影像的相關(guān) 目標區(qū) 搜索區(qū) 22,2222,22max0000,mkimkjjnlinliiijrc相似性測度一維相關(guān) 在核線影像上，只需要進行一維搜索 目標區(qū) 搜索區(qū) 影像的功率譜估計影像的功率譜估計 相關(guān)函數(shù)估計相關(guān)函數(shù)估計金字塔影像的建立金字塔影像的建立主要內(nèi)容 第二節(jié)：影像相關(guān)的譜分析第二節(jié)：影像相關(guān)的譜分析影像相關(guān)的譜分析 維納-辛欽定理：隨機信號的相關(guān)函數(shù)與其功率譜是一傅立葉變換對，即相關(guān)函數(shù)的傅立葉

5、變換即功率譜，而功率譜的逆傅立葉變換即相關(guān)函數(shù)：)()(fSRxyxy2)()(fXfSx)()()(*fYfXfSxy兩個隨機信號x(t)和y(t)的傅立葉變換為X(f)與Y(f)，則x(t)的自功率譜為影像功率譜x(t)與y(t)的互功率譜為 其中X*（f）為X（f）的復(fù)共軛。 影像功率譜的估計 對一些有代表性的航空影像進行功率譜估計，航空影像功率譜近似呈指數(shù)曲線狀。 fabefS)() 0()(aefSfa標準化功率譜的估計函數(shù)相關(guān)函數(shù)的估計 )0()(aefSfa 標準化功率譜估計為 影像的相關(guān)函數(shù)估計 dfeeRfjfa2)(22422121aajaja使 R(0)=1,得 22)(

6、411)(aR相關(guān)函數(shù)的估計 當a較小時，S（f）較平緩，高頻信息較豐富，此時相關(guān)函數(shù)R（）較陡峭，相關(guān)精度高，但由可能的近似位置到正確相關(guān)的點間距離（稱為拉入范圍）較小。這就要通過低通濾波獲得較大的拉入范圍。當a較大時，功率譜S（f）較陡峭，低頻信息占優(yōu)勢，因而相關(guān)函數(shù)R（）較平緩，相關(guān)精度較差，但拉入范圍較大，相關(guān)結(jié)果出錯的概率較小。金字塔影像相關(guān)（分頻道相關(guān)）從粗到精的相關(guān)策略。即先通過低通濾波，進行初相關(guān)，找到同名點的粗略位置，然后利用高頻信息進行精確相關(guān)。 對于二維影像逐次進行低通濾波，并增大采樣間隔，得到一個像元素總數(shù)逐漸變小的影像序列，將這些影像疊置起來頗像一座金字塔，因而稱之為

7、金字塔影像結(jié)構(gòu) 分頻道相關(guān)（多級相關(guān)） 分頻道可采用兩像元平均、三像元平均、四像元平均等等分若干頻道的方法 12345678910 11 12123456123123456789101112123412金字塔影像建立 每2X24個像元平均為一個像元構(gòu)成第二級影像，在第二級影像的基礎(chǔ)上構(gòu)成第三級影像。 四像元平均 九像元平均 金字塔影像層的確定方法 將原始影像稱為第零層，則第一層影像的每一像素相當于零層的（ll）l個像素，第k層影像的每一像素相當于零層的（ll）k個像素 由影像匹配窗口大小確定金字塔影像層數(shù) wINT（n/lk0.5）lw 影像長度由先驗視差確定金字塔影像層數(shù) Slpkmax最大

8、左右視差左 右 搜索距離基于像方的匹配算法 基于物方的匹配算法影像匹配的精度主要內(nèi)容 第三節(jié)：影像匹配的基本算法第三節(jié)：影像匹配的基本算法數(shù)字影像匹配基本算法影像匹配實質(zhì)上是在兩幅（或多幅）影像之間識別同名點 常見的五種基本匹配算法 同名點的確定是以匹配測度為基礎(chǔ) )(ijgG)(ijgG相關(guān)函數(shù)（矢量數(shù)積） DyxdxdyqypxgyxgqpR),(),(),(),( R（ p0, q0） R（p, q）（ pp0， qq0） 若 R（ p0, q0） R（p, q）（ pp0， qq0），則 p0, q0為搜索區(qū)影像相對于目標區(qū)影像的位移參數(shù)。對于一維相關(guān)應(yīng)有q 0。cjriminjjig

9、grcR ,11,),(),(),(00rcRrcR),(00ccrr若則c0, r0為搜索區(qū)影像相對于目標區(qū)影像的位移行、列參數(shù)。對于一維相關(guān)應(yīng)有r 0。 離散灰度數(shù)據(jù)對相關(guān)函數(shù)的估計公式為 NijiyxYXR1)(相關(guān)函數(shù)的估計值即矢量X與Y的數(shù)積 在N維空間 y1，y2，,yN中，R是y1，y2，,yN的線性函數(shù) max1NijiyxR它是N維空間的一個超平面。當N=2時 R x1yl x2y2 （X Y） |X| |Y|cos max |Y|cos max 相關(guān)函數(shù)最大（即矢量X與Y的數(shù)積最大）等價于矢量Y在X上的投影最大 協(xié)方差函數(shù)（矢量投影）DyxdxdyqypxgEqypxgyx

10、gEyxgqpC),(),(),(),(),(),(DyxdxdyyxgDyxgE),(),(1).(DyxdxdyqypxgDqypxgE),(),(1),(若C（p0, q0） C（p, q）（ pp0， qq0），則 p0, q0為搜索區(qū)影像相對于目標區(qū)影像的位移參數(shù)。對于一維相關(guān)應(yīng)有q 0。 )()(),(,11,ggggrcCcjriminjjiminjcjrircgnmg11,1minjjignmg11,1 C（c0, r0） C（c, r）（ cc0， rr0）則c0, r0為搜索區(qū)影像相對于目標區(qū)影像的位移行、列參數(shù) NiNijijiyxyyxxYXC11)()(協(xié)方差函數(shù)的估

11、計值即矢量的數(shù)積 C是Y在X的投影與X的長之積，因而協(xié)方差測度等價于Y在X上投影最大，maxC在二維空間中是平行于（或E）的一條直線 減去信號的均值等于去掉其直流分量。因而當兩影像的灰度強度平均相差一個常量時，應(yīng)用協(xié)方差測度可不受影響。相關(guān)系數(shù)（矢量夾角） ),(),(),(qpCCqpCqpggggDyxggdxdyyxgEyxgC),(2),(),(DyxggdxdyqypxgEqypxgqpC),(2),(),(),( 若（p0, q0） （p, q）（ pp0， qq0），則 p0, q0為搜索區(qū)影像相對于目標區(qū)影像的位移參數(shù)。對于一維相關(guān)應(yīng)有q 0。minjminjcrcjrijim

12、injcjrijiggggggggrc11112,2,11,)()()(),(minjcjrircgnmg11,1minjjignmg11,1相關(guān)系數(shù)的實用公式為：minjminjminjcjricjriminjjijiminjminjcjriminjjicjrijignmggnmgggnmggrc1111211,2211,21111,11,)(1)(1)( )(1)(),(coscos)( YXYXYXYX 相關(guān)系數(shù)的估計值最大，等價于矢量X與y的夾角最小 1取值范圍滿足 相關(guān)系數(shù)是灰度線性變換的不變量NiiiNiiiyyxxyyxx1221)()()(baYYNiNiiiNiiiyyxxy

13、yxx11221)()()(即灰度矢量經(jīng)線性變換后相關(guān)系數(shù)是不變的 NiNiiiNiiibyabayxxbyabayxx11221)()()()(差平方和（差矢量模） dxdyqypxgyxgqpSDyx2),(2 ),(),(),(2,11,2)(),(cjriminjjiggrcS 若S2（c0, r0） S2（c, r），則c0, r0為搜索區(qū)影像相對于目標區(qū)影像的位移行、列參數(shù)。對于一維相關(guān)應(yīng)有r 0。 NiiiNNyxyxyxyxYXS12222221122)()()()(兩影像窗口灰度差的平方和即灰度向量X與Y之差矢量 故差平方和最小等于N維空間點Y與點X之距離最小。當N2時，mi

14、n)()(2222112yxyxS二維平面上以（x1，y2）為中心、邊長為、對角線與坐標軸平行的一個正方形 二維平面上的一個圓 差絕對值和（差矢量分量絕對值和） dxdyqypxgyxgqpSDyx),(),(),(),( minjcjrijiggrcS11,),(離散灰度數(shù)據(jù)差絕對值和的計算公式為 若S（c0, r0） S（c, r）（ cc0， rr0），則c0, r0為搜索區(qū)影像相對于目標區(qū)影像的位移行、列參數(shù)。對于一維相關(guān)應(yīng)有r 0。NiiiNNyxyxyxyxS12211兩影像窗口灰度差絕對值和即灰度矢量X與Y之差矢量之分量的絕對值之和當N=2時， min2211yxyxS基于物方的

15、影像匹配（VLL法） 影像匹配的目的是提取物體的幾何 信息，確定其空間位置，能夠直接確定物體表面點空間三維坐標的影像匹配方法得到了研究，這些方法也被稱為“地面元影像匹配” 在物方有一條鉛垂線軌跡，它在影像上的投影是一直線。就是說VLL與地面交點A在影像上的構(gòu)像必定位 于 相 應(yīng) 的“投影差”上。鉛垂線軌跡法（VLLVertical Line Locus) 地面AVLL法影像匹配示意圖A?在鉛垂線上地面A那一個點正確？具體步驟給定地面點的平面坐標（X，Y） 與近似最低高程Zmin。 ZiZminiZ 高程搜索步距Z可由所要求的高程精度確定)()()()()()()()()()()()()()()

16、()()()()()()()()()(333222333111333222333111ssssssissssssissssssissssssiZZcYYbXXaZZcYYbXXafyZZcYYbXXaZZcYYbXXafxZZcYYbXXaZZcYYbXXafyZZcYYbXXaZZcYYbXXafx 計算左右像坐標（xi, yi）與（xi”，yi”）： 分別以（xi, yi）與（xi”，yi”）為中心在左右影像上取影像窗口，計算其匹配測度，如相關(guān)系數(shù)pi。 將i的值增加1，重復(fù)（2），（3）兩步，得到0，1，2，n取其最大者k： k max0，1，2，n還可以利用k及其相鄰的幾個相關(guān)系數(shù)擬合

17、一拋物線，以其極值對應(yīng)的高程作為A點的高程，以進一步提高精度，或以更小的高程步距在一小范圍內(nèi)重復(fù)以上過程。圖5-3-7 相關(guān)系數(shù)拋物線擬合 影像匹配（相關(guān)）即使在定位到整像素的情況下，其理論精度也可達到大約0.3像素的精度。影像匹配精度 影像相關(guān)是左影像為目標區(qū)與右影像上搜索區(qū)內(nèi)相對應(yīng)的相同大小的一影像相比較，求得相關(guān)系數(shù)，代表各窗口中心像素的中央點處的匹配測度 整像素相關(guān)的精度 半個像素2222)(dxxxx02,/1)(xx29. 0 x整像素相關(guān)的精度 誤差服從內(nèi)的均勻分布（為像素大小） 1222x用相關(guān)系數(shù)的拋物線擬合提高相關(guān)精度 f(s)= A BS CS2 圖6-3-7 相關(guān)系數(shù)拋

18、物線擬合CBAACBAiii11拋物線頂點k處的位置應(yīng)為 CBik2取相鄰像元3個相關(guān)系數(shù)進行拋物線擬合時 11112(2/)(iiiiiiCBA 由相關(guān)系數(shù)拋物線擬合可使相關(guān)精度達到0.150.2子像素精度 11112(2iiiiiikCBik211112(2/)(iiiiiiCBA最小二乘法影像匹配的原理 單點最小二乘法影像匹配最小二乘法影像匹配精度主要內(nèi)容 第四節(jié)：最小二乘法影像匹配第四節(jié)：最小二乘法影像匹配最小二乘影像匹配德國Ackermann教授提出了一種新的影像匹配方法最小二乘影像匹配（least Squares Image Matching）影像匹配可以達到1/10甚至1/100

19、像素的高精度優(yōu)點如下l最小二乘影像匹配中可以非常靈活地引入各種已知參數(shù)和條件，從而可以進行整體平差。 l解決“單點”的影像匹配問題，以求其“視差”；也可以直接求解其空間坐標 l同時解決“多點”影像匹配或“多片”影像匹配 l引入“粗差檢測”，從而大大地提高影像匹配的可靠性 最小二乘影像匹配原理“灰度差的平方和最小” minvv),(),(2211yxgnyxgn僅僅認為影像灰度只存在偶然誤差 ),(),(21yxgyxgv 按vvmin原則進行影像匹配的數(shù)字模型。若在此系統(tǒng)中引入系統(tǒng)變形的參數(shù)，按 vvmin的原則，解求變形參數(shù)，就構(gòu)成了最小二乘影像匹配系統(tǒng)。靈活,可靠和高精度是優(yōu)點, 缺點是，

20、如當初始值不太準時，系統(tǒng)的收斂性等問題有待解決。輻射畸變l照明及被攝影物體輻射面的方向l大氣與攝影機物鏡所產(chǎn)生的衰減l攝影處理條件的差異以及影像數(shù)字化過程中所產(chǎn)生的誤差等等影像灰度的系統(tǒng)變形有兩大類：輻射畸變；幾何畸變。幾何畸變l攝影機方位不同所產(chǎn)生的影像的透視畸變l影像的各種畸變l由于地形坡度所產(chǎn)生的影像畸變等豎直航空攝影的情況下，地形高差則是幾何畸變的主要因素。 在影像匹配中引入這些變形參數(shù)，同時按最小二乘的原則，解求這些參數(shù)，就是最小二乘影像匹配的基本思想。僅考慮輻射的線性畸變的最小二乘匹配相關(guān)系數(shù) 2221011),(),(ngyxghhnyxg)(21210ggghhv誤差方程：按v

21、vmin的原理，可得法方程式 22211220221120)()()(ggghghggghgnh)(11)(12210222212211hgggnhgngggnggh假定對g1，g2已作過中心化處理 0;0;0021hgg122121gggh即：)(21210ggghhv22212212112221222222122122122)(2)()(ggggvvgggggggggggggggvv消除了兩個灰度分布的系統(tǒng)的輻射畸變后，其殘余的灰度差的平方和為 相關(guān)系數(shù)與vv的關(guān)系 )1(221gvv22212122)(gggg相關(guān)系數(shù)2211gvvvv是噪聲的功率g12為信號的功率 以“相關(guān)系數(shù)最大”作

22、為影像匹配搜索同名點的準則，其實質(zhì)是搜索“信噪比為最大”的灰度序列 信噪比 vvgSNR212)()1 (1)(22SNR相關(guān)系數(shù)與信噪比之間的關(guān)系 影像匹配的主要目的是確定影像相對移位，傳統(tǒng)的算法采用目標區(qū)相對于搜索區(qū)不斷地移動一個整像素，搜索最大相關(guān)系數(shù)的影像區(qū)中心作為同名像點 。 在最小二乘影像匹配算法中，可引入幾何變形參數(shù)，直接解算影像移位，這是此算法的特點。 僅考慮影像相對移位的一維最小二乘匹配 假設(shè)兩個一維灰度函數(shù)g1(x), g2(x),除隨機噪聲外，g2(x)相對于g1(x)只存在零次幾何變形移位量x。)()()()(2211xnxxgxnxg)()()(12xgxxgxv誤差

23、方程式2)()()(222xgxgxg 離散的數(shù)字影像而言，灰度函數(shù)的導(dǎo)數(shù)g,2(x)可由差分代替 )()()()(212xgxgxxgxv為解求相對移位量x，需上式進行線性化 最小二乘影像匹配是非線性系統(tǒng)，必須進行迭代。迭代過程收斂的速度取決于初值。222/gggxgxgv2誤差方程式可寫為 解得影像的相對移位 單點最小二乘影像匹配 兩 個 二 維 影像 之 間 的 幾何 變 形 ， 不僅 僅 存 在 著相 對 移 位 還存 在 著 圖 形變化 x2 y2灰度畸變+幾何變形 幾何變形 經(jīng)線性化后誤差方程式gdbcdbcdbcdacdacdacdhcdhcvo281706251403121dh

24、。，dh1， da0，,db2是待定參數(shù)的改正值，它們之初值分別為 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 在數(shù)字影像匹配中，灰度均是按規(guī)則格網(wǎng)排列的離散陣列，且采樣間隔為常數(shù)，可被視為單位長度，上式中

25、的偏導(dǎo)數(shù)均用差分代替：幾何改正重采樣輻射畸變改正是否迭代計算最佳匹配的點位計算參數(shù)值結(jié)束左片右片最小二乘法匹配流程圖幾何變形改正。根據(jù)幾何變形改正參數(shù)a0, a1, a2,b0, b1, b2將左方影像窗口的影像坐標變換至右方影像陣列：重采樣。由于換算所得之坐標x2，y2一般不可能是右方影像陣列中的整數(shù)行列號，因此重采樣是必須的。ybxbbyyaxaax21022102輻射畸變改正。利用由最小二乘影像匹配所求得輻射畸變改正參數(shù)h0, h1；對上述重采樣的結(jié)果作輻射改正若相關(guān)系數(shù)小于前一次迭代后所求得的相關(guān)系數(shù)，則可認為迭代結(jié)束.也可以根據(jù)幾何變形參數(shù)是否小于某個預(yù)定的閾值。 采用最小二乘影像匹

26、配，解求變形參數(shù)的改正值dh0,dh1, da0,。 計算變形參數(shù) yxbbbaaayxiiiiii1001210210221yxbbbaaadbdbdbdadadaiiiiiiiiiiii100111001121110121110210210ybxbbyyaxaax21022102iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiidbbdbabbdbbdbabbdbbdbadbbbdabdaaaadabdaaaadabdaadaaa21211212221111111121011001002121121222111111112101100100211101021011

27、011011011ghhdhdhghhgiiiiiii11-i11-i1i1i11-i0i01-i0i0dhhhhdhhdhhh對于輻射畸變參數(shù)滿足： 計算最佳匹配的點位 .可用梯度的平方為權(quán)，在左方影像窗口內(nèi)對坐標作加權(quán)平均：2222/yyixxiggyyggxxybxbbyyaxaax21022102匹配精度取決于影像灰度的梯度 為了進一步提高其可靠性與精度，例如，附帶共線條件的最小二乘相關(guān)以及與VLL法結(jié)合的最小二乘影像匹配方法都得了廣泛的研究 最小二乘影像匹配的精度 最小二乘匹配算法，則可以根據(jù)以及法方程式系數(shù)矩陣的逆矩陣，同時求得其精度指標 2220/xg222/xggg 20220

28、vn為目標區(qū)像元個數(shù)。由于上式右邊是無偏估計，所以220/11vn2221gvxnvgSNR22221vxgn SN R信噪比方差2222)1(gvxn)1 (1)(22SNR相關(guān)系數(shù)與信噪比之間的關(guān)系 影像匹配的精度與相關(guān)系數(shù)有關(guān)，相關(guān)系數(shù)愈大則精度愈高。它與影像窗口的“信噪比”有關(guān)，信噪比愈大，則匹配的精度愈高。 可以得到一些很重要的結(jié)論： 影像匹配的精度還與影像的紋理結(jié)構(gòu)有關(guān)，即與 有關(guān)。特別是當 愈大，則影像匹配精度愈高。當 ，即目標窗口內(nèi)灰度沒有變化時，則無法進行影像匹配。)/(ggg 02 g特征匹配的概念基于特征點的影像匹配策略 跨接法影像匹配主要內(nèi)容 第五節(jié)：特征匹配第五節(jié)：特

29、征匹配特征匹配以影像的灰度分布為影像匹配的基礎(chǔ)，被稱為灰度匹配（Area Based Image Matching） 特 征 匹 配 （ F e a t u r e B a s e d Matching，在計算機界也稱為 Primitive Based Matching）。 當待匹配的點位于低反差區(qū)內(nèi)， 其匹配的成功率不高。 目的只需要配準某些點線或面 在城市中，被處理的對象主要是人工建筑物，灰度匹配難以適應(yīng) 特征匹配使用的幾種場合特征匹配步驟特征的匹配可以分為點、線、面特征匹配可分為三步： 特征提??；利用一組參數(shù)對特征作描述；利用參數(shù)進行特征匹配。 iSffijijji)(11例 如 ： 首 先 可 以 用 邊 緣 算 子（Edge Operator）從影像中提取邊緣，然后再用參數(shù)描述“邊緣”。常用-S曲線 表 達 邊緣： 基于特征點的影