衛(wèi)春陽，喬彥友

1.中國科學院空天信息創(chuàng)新研究院國家遙感應用工程技術研究中心,北京 100101；2.中國科學院大學,北京 100049

0 引 言

圖像配準是圖像應用的關鍵步驟(Wei等，2017；Yang等，2017；Eastman等，2011；Zhao等，2020；Chen等，2015)，一般包括局部不變特征點匹配、直線匹配和區(qū)域匹配等算法(賈迪 等，2019)，以及局部不變特征與區(qū)域匹配結合等算法(Feng等，2019b；許斌 等，2018)。目前的遙感圖像匹配方法主要有基于區(qū)域和基于特征的方法及針對山地影像的光流跟蹤法(Feng等，2019a)?；谔卣鞯姆椒ㄓ捎谠诹炼茸兓⒅貜托约y理和幾何失真等復雜場景時依然顯示出較高的魯棒性，成為遙感圖像匹配研究的熱點，其中SIFT(scale invariant feature transform)(Lowe，2004)是應用最為經(jīng)典的特征描述子之一，并出現(xiàn)了很多針對耗時和精確性等方面的改進版本(耿娟 等，2016；張慶鵬和曹宇，2019)，提出了大量基于特征的圖像匹配方法。該類方法有兩個主要步驟：1)提取魯棒特征點并基于最近鄰距離比(nearest neighbor distance ratio,NNDR)(Lowe，2004)確定初始匹配；2)基于幾何模型過濾錯誤匹配。然而，由于重復紋理導致的特征模糊性，使基于NNDR的初始匹配存在大量錯誤匹配(Raguram等，2008)，因此需要額外的錯誤匹配剔除步驟(Li和Hu，2010；Ma等，2012)。按照錯誤匹配過濾方式的不同，現(xiàn)有的圖像匹配算法可分為3類：基于幾何模型的方法、基于局部空間結構的方法和基于圖結構的方法。

1)基于幾何模型的匹配算法。該方法先基于NNDR比較局部特征(如SIFT特征的相似度)，然后迭代估算幾何模型過濾外點，從而實現(xiàn)遙感圖像的匹配。初始匹配方法包括暴力(brute force)匹配、近似最近鄰(approximate nearest neighbor，ANN)搜索匹配(Agarwal等，2009；Crandall等，2011)和級聯(lián)哈希(cascade hash，CH)匹配(Strecha等，2012；Cheng等，2014)。初始匹配中一般存在較多的錯誤匹配，通常使用隨機樣本一致性算法(random sample consensus，RANSAC)(Fischler和Bolles，1981；Hartley和Zisserman，2000；Raguram等，2008；Moisan等，2012；Chum等，2003)對錯誤匹配進行過濾，首先迭代選擇隨機數(shù)據(jù)樣本估計模型，然后基于一定的閾值統(tǒng)計內(nèi)點數(shù)量，以內(nèi)點數(shù)量最多的模型為最終的圖像變換模型，以此過濾外點匹配。針對無人機影像進行特征匹配，王曉紅等人(2018)提出利用多重約束條件的外點過濾算法，首先檢測影像特征點并構建初始匹配，再計算SIFT特征尺度鄰域內(nèi)的特征主方向，最后基于RANSAC估算單應性矩陣實現(xiàn)了更精確的錯誤匹配過濾。該方法在一般的剛體變換下效果良好，但在重復紋理條件下存在大量錯誤匹配時，估算出的幾何模型不能準確反映圖像變換關系，基于該幾何模型的錯誤匹配過濾結果精度會大幅降低(Brown和Lowe，2002)。

2)基于局部空間關系的匹配算法。為了應對RANSAC的匹配方法在重復的結構場景下性能退化問題，研究人員提出了幾種基于局部空間結構一致性的算法。這些算法的基本原理在于：在查詢和目標圖像之間的轉(zhuǎn)換過程中，匹配特征點的局部空間結構幾乎保持不變，基于局部結構一致性原理可以消除圖像的錯誤匹配。Ma等人(2014)提出一種魯棒向量場一致性(vector field consensus，VFC)方法，通過在兩幅圖像之間插值一個向量場建立對應關系，采用最大后驗估計方法從初始匹配中選擇內(nèi)點匹配。Li(2015)根據(jù)地面目標點在目標圖像和查詢圖像之間位置不變性構建特征點幾何向量相似性約束，實現(xiàn)了合成孔徑雷達圖像的正確匹配。Hu等人(2015)將描述符投影到一個單應空間，根據(jù)點之間的測地距離判斷這些初始匹配的幾何一致性和空間連續(xù)性，然后基于這種一致性確立正確的圖像匹配。Yang等人(2017)通過歐幾里德距離和形狀建立高斯混合模型度量幾何結構相似性，基于能量優(yōu)化和運動一致性的幾何約束更新變換模型以過濾錯誤匹配。Bian等人(2017)通過計算相鄰匹配的數(shù)量提出一種基于網(wǎng)格的運動統(tǒng)計(grid-based motion statistics，GMS)方法。

3)基于圖結構的匹配算法。圖匹配的核心概念是在兩個圖節(jié)點之間基于一定的規(guī)則建立圖頂點的對應關系。基于此，研究人員提出了幾種相應的圖像匹配算法。Izadi和Saeedi(2012)利用圖邊之間的角度距離將特征與其最近鄰連接起來，通過迭代剔除離群值計算相似圖達到外點過濾的目的。Zhang等人(2014)利用k近鄰的三角形區(qū)域定義了仿射不變描述子獲得候選外點匹配，結合局部仿射不變描述子和全局信息消除外點匹配。為了在重復圖案、遮擋和紋理均勻的情況下獲得魯棒的圖像匹配，Yuan等人(2017)提出了一種結合幾何約束和輻射約束的邊緣加權張量的方法，構建高階圖匹配以實現(xiàn)圖像特征的匹配?；谡_匹配局部鄰域結構穩(wěn)定的認識，Ma等人(2018)提出一種基于引導的錯誤匹配過濾算法(guided locality preserving matching，GLPM)，使用較高內(nèi)點率的初始匹配引導初始匹配中的錯誤匹配過濾。為了不依賴于高內(nèi)點率的初始匹配,Ma等人(2019)提出通過搜索每個假設匹配的k近鄰構造一個近鄰點集?；诰植苦徲蚪Y構一致性檢驗消除錯誤匹配的LPM (locality preserving matching)算法，喜文飛等人(2020)提出利用圖論原理構建特征點的能量函數(shù)過濾能量較低的特征點，以減少特征匹配的粗差，再結合RANSAC 算法進行粗差剔除，獲得了更高精度的單應矩陣估算結果。

1 方 法

給定查詢圖像Iq與目標圖像It，Iq

圖1 SDC算法流程Fig.1 Flow chart of SDC algorithm

1.1 基于大尺度SIFT特征的少量初始匹配

由于同一尺度級別的特征更容易正確匹配(Wu，2013)，首先提取SIFT特征并根據(jù)SIFT尺度大小按升序排序并選擇尺度前10%的特征(本文稱之為大尺度特征)，然后對其應用暴力匹配建立初始匹配子集。使用大尺度SIFT特征提取初始匹配，是因為它們數(shù)量少、質(zhì)量高。為了提取盡可能多的正確初始匹配，將NNDR閾值設置為0.6。

圖2 基于大尺度特征的初始匹配Fig.2 Preliminary initial matching using top-scale features((a)test image A and image B;(b)SIFT feature scale histograms for image A and image B)

1.2 建立分治空間中心點對

構建分治空間中心需要知道每個子集的大致中心位置。為了確定分治空間中心點對，首先查詢圖中構建虛擬中心點(virtual center point，VCP)，稱為虛擬中心點是表示該點不一定代表提取特征點的實際位置，而只是作為分治空間的搜索中心。

構建VCP樣點的關鍵是確定采樣點間距，從而確定分治空間窗口的大小。采樣點越密集、窗口越小，反之亦然。給定一幅具有NI個特征點的遙感圖像，假設特征點均勻分布的理想情況下，若在每個窗口中有Nw個特征點，且VCP位于其中心，那么

Wnum=NI/Nw

(1)

式中，Wnum是窗口數(shù)，Nw為經(jīng)驗值。

因此，基于Wnum的方形窗口的邊長為

(2)

式中，W和H分別是圖像的寬度和高度?？梢钥闯?，Wnum越大、L越小，反之亦然。

Vt=VqA

(3)

由于圖像大小不同，并不是所有的采樣點都可以轉(zhuǎn)換成目標圖像。因此有必要在目標圖像之外刪除VCP集，得到圖像匹配的分治空間中心點對C。具體為

(4)

圖3描述了基于仿射變換獲得的C。VCP從左側(cè)的查詢圖像轉(zhuǎn)換到相同尺寸(圖3(a))和不同尺寸(圖3(b))的右側(cè)目標圖像。當圖像旋轉(zhuǎn)時，查詢圖像中的一些點會轉(zhuǎn)換為不包含特征點的黑色區(qū)域?；谑?4),在進行圖像匹配前排除了部分不會存在匹配的分治空間點集。從圖3可以看出，大多數(shù)區(qū)域并無匹配。建立分治空間點集，可以減少大量不必要的特征匹配搜索運算。

圖3 分治空間中心點對Fig.3 Pairwise VCPs obtained through affine transformations((a)the size and direction of the query image and the target image are the same;(b)the size and direction of the query image and the target image are different)

1.3 構建成對分治空間點集

確定分治空間中心點對集后，通過搜索每一對中心點附近的特征點，構建分治空間點集。

搜索近鄰特征點的方法有4種：窮舉搜索法、分維數(shù)搜索法、k-維樹(k-dimensional tree,kd-tree)法和區(qū)域樹(range-tree)法。由于區(qū)域樹 (de Berg等，2000)具有較高的搜索效率，時間復雜度為O(log2M+k)，因此本文采用區(qū)域樹進行分治空間中心點的近鄰搜索。具體來說，對于圖像中任意一點v(x,y)，假設其位于邊長為L的矩形P的內(nèi)中心，且x∈[x-L/2:x+L/2]和y∈[y-L/2:y+L/2]，將搜索矩形P范圍內(nèi)所有點集的查詢稱為“矩形范圍”查詢。該查詢方法要求數(shù)據(jù)維度正交，因此也稱為“正交范圍”查詢。本研究搜索2維圖像中一定范圍內(nèi)的近鄰坐標點，符合正交性，因此2維區(qū)域樹是近鄰點快速查詢的最優(yōu)選擇。

圖4是兩個范圍樹搜索的示意圖。圖4(a)查詢圖像與目標圖像尺寸下相同且無相對旋轉(zhuǎn);圖4(b)查詢圖像與目標圖像尺寸不同且存在相對旋轉(zhuǎn)。為了便于查看，只隨機選擇少量數(shù)據(jù)進行顯示。黃色方框代表搜索范圍，方框中心的紅點代表VCP。在左側(cè)的查詢圖像中，VCP均勻分布，間隔距離為L。綠線代表VCP匹配。可以看到兩幅圖像中的黃色方框大致位于同一個區(qū)域。利用VCP搜索相鄰特征點后，即實現(xiàn)了分治空間的構建。

圖4 分治匹配空間的構建Fig.4 Searching for neighboring feature points based on VCPs((a)query and target images of different sizes；(b)query and target images of different sizes and orientations)

1.4 分治空間內(nèi)的特征匹配

利用區(qū)域樹完成分治空間點集構建后，進行分治空間內(nèi)的特征匹配。kd-tree方法是特征匹配的常用方法，但需要額外的時間建立搜索樹，且由于圖像特征劃分在多個窗口內(nèi)，而每個窗口內(nèi)的特征數(shù)量較少，此時kd-tree方法優(yōu)勢不明顯，直接采用暴力匹配即可實現(xiàn)特征的快速匹配。

與傳統(tǒng)暴力匹配方法不同，本文算法對圖像順序有要求，即Iq

圖5 圖像順序?qū)μ卣髌ヅ溆绊慒ig.5 Impact of image order on the correspondence establishment((a)large query image and small target image;(b)small query image and large target image)

1.5 SDC算法的計算復雜度分析

查詢圖像和目標圖像中的特征點數(shù)量分別用M和N表示，M

為了便于快速搜索，區(qū)域樹必須在不同級別保存子樹索引，其空間復雜度為O(MlogM+NlogN)。當每個查詢窗口中至少有m個特征點時，需要M/m個VCP覆蓋整個查詢圖像。因此，最近鄰搜索的時間復雜度約為O((M/m)(log2M+log2N))，存儲這些最近鄰的空間復雜度為O(M+N)。假設目標窗口中有n個點，每對窗口的計算復雜度為O(mn)；所有窗口的匹配計算的時間復雜度為O(M/m)(mn)，以O(nM)表示；空間復雜度為O(K)，其中K是匹配數(shù)。

綜上所述，空間分治匹配算法的時間復雜度為O(MlogM+NlogN)+O(uv)+O(nM)+O((M/m)(log2M+log2N))。由于M?N，且u,v?M,N，因此，O(MlogM+NlogN)?2×O(NlogN)，O(uv)+O(nM)?2×O(nM)。時間復雜度可以近似為O((n+logN)N+(M/m)log2N)?？臻g復雜度為O(MlogM+NlogN)+O(M+N)+O(K)，一般為K?M?N?MlogM?NlogN，因此，空間分治匹配算法的空間復雜度可簡寫為 O(NlogN)。

2 實 驗

為驗證SDC算法的性能，在不同傳感器遙感圖像上與現(xiàn)有算法進行對比實驗。實驗在小米15.6 pro筆記本電腦上進行，軟硬件配置為ubuntu16.04操作系統(tǒng)，Intelcorei5-8250U處理器和8 GB運行內(nèi)存，SDC算法和比較算法均基于C++實現(xiàn)。

2.1 參數(shù)設置

表1 “假設窗口”中特征數(shù)對SDC算法性能的影響Table 1 Effect of numbers of features in the assumed window on SDC performance

通過以上對SDC算法的性能分析，可以看出窗口越小，匹配效率越高。實驗也表明本文算法在不同地理環(huán)境下的遙感影像匹配中表現(xiàn)良好。由于高空衛(wèi)星圖像中，地形起伏對圖像的影響可以忽略不計,因此基于單應變換估算匹配精確性具有較高精度，可作為圖像匹配質(zhì)量的判斷依據(jù)。具體來說，對于任意落在同一平面的一對匹配特征點p1(u1,v1)和p2(u2,v2),其歸一化坐標為p1=[u1,v1,1]T,p2=[u2,v2,1]T?；?個以上匹配點對可以計算存在的單應變化矩陣H，具體為

(5)

然后以H為基準，根據(jù)投影誤差ε確定匹配的正確性，其中ε=d(Pq,HPt)。當ε小于閾值τ時，認為該匹配是一個內(nèi)點匹配，否則認為是一個外點匹配。在文中，將τ設置為1。

圖6 不同遙感圖像的SDC算法匹配效果Fig.6 Matching results obtained by applying SDC algorithm to remote sensing images of various geographical environments((a)Landsat 8 band 257 synthetic images of mountains;(b)SPOT satellite images of a city;(c)ZY-3 satellite images of a plain;(d)GF-3 SAR images of city)

2.2 匹配效率比較

為驗證本文提出的SDC算法的匹配效率，選取36幅不同尺寸的遙感圖像，與現(xiàn)有最先進的RANSAC(Fischler和Bolles，1981)、VFC(Ma等，2012)、GMS(Bian等，2017)和GLPM(Ma等，2018)算法從內(nèi)點率和運行耗時兩方面進行比較。

2.2.1 初始匹配和內(nèi)點匹配數(shù)量比較

首先對各算法提取的匹配和內(nèi)點匹配的絕對數(shù)量進行比較。通常使用精確度和召回率評估圖像匹配性能。因此要計算匹配召回率，就必須確定正確匹配的數(shù)量。現(xiàn)有研究中的正確匹配是通過手動選擇計算的，而為了驗證本文算法在不同圖像大小下的性能，選擇了20對圖像進行實驗，從中提取了多達10 000個匹配項，顯然手動選擇是不可行的。參考Kurz和Himane(2011)方法，本文使用單應矩陣的投影誤差確定匹配是否正確。首先選擇少量的大尺度SIFT特征進行嚴格NNDR閾值的初始匹配，由于匹配的數(shù)量較少，因而可以直觀地檢查是否存在不正確的匹配。在沒有錯誤匹配發(fā)生的情況下，可以計算出更精確的單應矩陣H，然后根據(jù)第2.1節(jié)提到的方法對確定錯誤匹配。

表2顯示了通過各種匹配算法獲得的總匹配數(shù)和內(nèi)點數(shù)。傳統(tǒng)的基于RANSAC的匹配方法提取了最多的匹配，BF-RANSAC是基于暴力匹配(BF)的RANSAC，ANN-RANSAC是基于近似最近鄰(ANN)匹配的RANSAC，CH-RANSAC是基于級聯(lián)哈希(CH)匹配的RANSAC，其中最直接的BF-RANSAC匹配方法搜索到最多的匹配。在其他算法中，VFC提取到的匹配幾乎與BF-RANSAC相同，略微居于其次的是GMS算法。而GLPM和本文SDC算法提取的匹配數(shù)量相對較少，但是內(nèi)點的比例也很高。有兩個原因?qū)е耂DC算法獲得的匹配較少：1)SDC是一種空間分治算法，匹配點對的數(shù)目取決于分治空間的大小。此外，分治空間之間的間隙是不可避免的，因此一些特征被排除在外。2)當影像地面存在起伏時，仿射估計可能不夠精確，導致VCP變換不準確，變換后的分治空間會偏離實際應該在的位置，導致部分特征點的匹配發(fā)生在不同的分治空間內(nèi)。雖然SDC算法相對于其他算法丟失了部分匹配，然而在實時遙感匹配中通常不需要匹配所有特征。當匹配點在圖像中均勻分布時，可以估計出精確的幾何模型，而SDC算法的匹配點分布在分治空間中心的采樣時即已決定其均勻性。

表2 圖像的平均初始匹配數(shù)量和內(nèi)點匹配數(shù)量Table 2 Average numbers of putative matches and inliers

2.2.2 內(nèi)點率和運行時間的比較

圖7 不同平臺實驗影像的內(nèi)點率比較Fig.7 Comparison of inlier ratio for test images from various platforms((a)Landsat;(b)SPOT;(c)GF-3;(d)ZY-3)

圖8 不同平臺實驗影像的運行時間比較Fig.8 Comparison of runtime for test images from various platforms((a)Landsat;(b)SPOT;(c)GF-3;(d)ZY-3)

圖9 各種匹配算法的性能比較Fig.9 Performance comparison for various matching algorithms((a)inlier ratio；(b)runtime)

3 結 論