遙感影像空間分治快速匹配

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

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

0 引 言

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

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

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

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

1 方 法

給定查詢圖像Iq與目標(biāo)圖像It，Iq

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

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

由于同一尺度級(jí)別的特征更容易正確匹配(Wu，2013)，首先提取SIFT特征并根據(jù)SIFT尺度大小按升序排序并選擇尺度前10%的特征(本文稱之為大尺度特征)，然后對(duì)其應(yīng)用暴力匹配建立初始匹配子集。使用大尺度SIFT特征提取初始匹配，是因?yàn)樗鼈償?shù)量少、質(zhì)量高。為了提取盡可能多的正確初始匹配，將NNDR閾值設(shè)置為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 建立分治空間中心點(diǎn)對(duì)

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

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

Wnum=NI/Nw

(1)

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

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

(2)

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

Vt=VqA

(3)

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

(4)

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

圖3 分治空間中心點(diǎn)對(duì)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 構(gòu)建成對(duì)分治空間點(diǎn)集

確定分治空間中心點(diǎn)對(duì)集后，通過搜索每一對(duì)中心點(diǎn)附近的特征點(diǎn)，構(gòu)建分治空間點(diǎn)集。

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

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

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

與傳統(tǒng)暴力匹配方法不同，本文算法對(duì)圖像順序有要求，即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算法的計(jì)算復(fù)雜度分析

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

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

綜上所述，空間分治匹配算法的時(shí)間復(fù)雜度為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)。時(shí)間復(fù)雜度可以近似為O((n+logN)N+(M/m)log2N)。空間復(fù)雜度為O(MlogM+NlogN)+O(M+N)+O(K)，一般為K?M?N?MlogM?NlogN，因此，空間分治匹配算法的空間復(fù)雜度可簡寫為 O(NlogN)。

2 實(shí) 驗(yàn)

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

2.1 參數(shù)設(shè)置

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

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

(5)

然后以H為基準(zhǔn)，根據(jù)投影誤差ε確定匹配的正確性，其中ε=d(Pq,HPt)。當(dāng)ε小于閾值τ時(shí)，認(rèn)為該匹配是一個(gè)內(nèi)點(diǎn)匹配，否則認(rèn)為是一個(gè)外點(diǎn)匹配。在文中，將τ設(shè)置為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 匹配效率比較

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

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

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

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

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

2.2.2 內(nèi)點(diǎn)率和運(yùn)行時(shí)間的比較

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

圖8 不同平臺(tái)實(shí)驗(yàn)影像的運(yùn)行時(shí)間比較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 結(jié) 論