楊 帥, 任超鋒，趙麗華

(長(zhǎng)安大學(xué)地質(zhì)工程與測(cè)繪學(xué)院，西安 710054)

隨著航空攝影測(cè)量、計(jì)算機(jī)視覺(jué)、傳感器技術(shù)的快速發(fā)展，無(wú)人機(jī)(unmanned aerial vehicle，UAV)在獲取影像的過(guò)程中機(jī)動(dòng)靈活且成本較低[1]，能夠快速獲取高分辨率的影像[2]，在測(cè)繪地理信息、防災(zāi)減災(zāi)、農(nóng)業(yè)估產(chǎn)、水利電力、交通等方面發(fā)揮重要作用[3]。如何快速、準(zhǔn)確獲取影像具有重疊區(qū)的潛在匹配像對(duì)，成為制約無(wú)人機(jī)影像三維重建完整性及效率的瓶頸問(wèn)題。

基于內(nèi)容的圖像檢索(content-based image retrieval，CBIR)方法在信息檢索、數(shù)據(jù)查詢、語(yǔ)音識(shí)別、圖像分類、知識(shí)產(chǎn)權(quán)、視頻分析和搜索引擎等領(lǐng)域具有廣闊的應(yīng)用前景[4]。而影像匹配作為三維重建最基礎(chǔ)的環(huán)節(jié)，是實(shí)現(xiàn)無(wú)人機(jī)影像自動(dòng)化處理的前提[5-6]。在傳統(tǒng)的攝影測(cè)量數(shù)據(jù)處理流程中，必須首先已知相機(jī)的標(biāo)定參數(shù)和規(guī)則的航帶信息，以此進(jìn)一步獲取影像之間的匹配關(guān)系。而在計(jì)算機(jī)視覺(jué)領(lǐng)域，利用CBIR方法可以無(wú)須已知相機(jī)的標(biāo)定參數(shù)和航帶信息等先驗(yàn)信息，僅需要對(duì)圖像進(jìn)行處理即可獲取影像之間的匹配關(guān)系，極大地簡(jiǎn)化了對(duì)無(wú)定位定姿系統(tǒng)(positioning and orientation system，POS)數(shù)據(jù)、影像排列不規(guī)則和數(shù)據(jù)量龐大的無(wú)人機(jī)影像數(shù)據(jù)處理流程。CBIR方法因其在數(shù)據(jù)處理過(guò)程中檢索效率高、無(wú)須人工進(jìn)行干預(yù)以及自動(dòng)化處理水平高等優(yōu)勢(shì)，極大了提高航帶自動(dòng)重構(gòu)和場(chǎng)景三維重建的效率，從而能夠有效降低各種人力物力財(cái)力的投入，在滑坡地質(zhì)災(zāi)害監(jiān)測(cè)、三維城市建模、古文物建筑保護(hù)領(lǐng)域中得到廣泛應(yīng)用。

在影像匹配像對(duì)選擇方面，文獻(xiàn)[7-8]采用窮舉法，利用互聯(lián)網(wǎng)圖片數(shù)據(jù)集上對(duì)影像進(jìn)行兩兩遍歷匹配，實(shí)現(xiàn)了一日之內(nèi)構(gòu)建羅馬。窮舉法時(shí)間復(fù)雜度最為可靠，但在處理海量無(wú)人機(jī)影像數(shù)據(jù)時(shí)計(jì)算量過(guò)于龐大且大多是無(wú)效計(jì)算，不具備實(shí)用性。閆利等[9]、李勁澎等[10]、姜三等[11]利用影像的POS數(shù)據(jù)、相機(jī)姿態(tài)參數(shù)和測(cè)區(qū)地面平均高程等先驗(yàn)知識(shí)，計(jì)算每張影像投影至地面的腳印圖并粗略估計(jì)影像之間的重疊度，然后通過(guò)構(gòu)建影像之間的關(guān)系圖，獲得影像初始匹配像對(duì)。由于該類方法計(jì)算量小，且對(duì)常規(guī)數(shù)據(jù)獲取方式具有較好的適應(yīng)性，因此是目前低空無(wú)人機(jī)影像匹配像對(duì)提取的主要方法。但是，由算法原理可知，該類方法高度依賴先驗(yàn)知識(shí)的準(zhǔn)確性，必須提前獲取測(cè)區(qū)的高程信息。當(dāng)測(cè)區(qū)地形起伏較大，地形是高山、峽谷或者采用仿地、貼近飛行方式時(shí)，該類方法便無(wú)法準(zhǔn)確地計(jì)算影像之間的相關(guān)性。任超鋒等[12]利用影像初始地理位置信息，計(jì)算當(dāng)前影像與其相鄰影像的地理位置關(guān)系，進(jìn)而采用固定閾值范圍內(nèi)的像對(duì)進(jìn)行匹配，在一定程度上提高了匹配的可靠度和效率。但是，使用固定數(shù)目或固定比例的圖像選擇策略依然會(huì)導(dǎo)致大量的冗余匹配。Jiang等[13]提出了一種自適應(yīng)詞匯樹(shù)檢索算法，通過(guò)分析圖像之間的拓?fù)溥B接結(jié)構(gòu)并分析影像相似性的得分分布來(lái)獲取影像之間的匹配關(guān)系，在一定程度上解決了傾斜無(wú)人機(jī)影像的匹配像對(duì)選擇問(wèn)題。

針對(duì)上述問(wèn)題，利用提供了無(wú)人機(jī)影像位置信息的POS數(shù)據(jù)并通過(guò)對(duì)影像檢索結(jié)果的相似性得分分布進(jìn)行研究與分析，對(duì)常規(guī)的詞匯樹(shù)算法進(jìn)行相應(yīng)地改進(jìn)，提出了基于空間距離加權(quán)的詞匯樹(shù)檢索算法來(lái)實(shí)現(xiàn)有效的匹配像對(duì)選擇。

1 算法原理

1.1 算法設(shè)計(jì)流程

本文算法設(shè)計(jì)流程如圖1所示。①根據(jù)文獻(xiàn)[14]的方法，利用SiftGPU算法快速地對(duì)一組原始的無(wú)人機(jī)影像進(jìn)行尺度不變特征轉(zhuǎn)換(scale-invariant feature transform, SIFT)特征的提取并組成SIFT特征向量集合；②對(duì)SIFT特征向量集合進(jìn)行詞匯樹(shù)[15]構(gòu)建；③檢索所有影像，計(jì)算檢索影像之間的相似性得分因子；④根據(jù)影像的POS數(shù)據(jù)計(jì)算反距離權(quán)重因子然后與相似性得分因子組合計(jì)算綜合權(quán)重因子；⑤根據(jù)綜合權(quán)重因子降序排列并自適應(yīng)設(shè)置查詢深度閾值，將閾值之前的查詢影像與當(dāng)前影像組合作為最終影像匹配像對(duì)。

Vi為視覺(jué)詞匯；TF-IDF為詞頻-逆文本頻率；IS為倒排索引權(quán)重因子；C為相似因子；W為權(quán)重因子

1.2 分層詞匯樹(shù)的構(gòu)建

如圖2所示，分層詞匯樹(shù)是通過(guò)分層K-means算法構(gòu)建的樹(shù)型索引結(jié)構(gòu)。通過(guò)上述步驟得到的特征向量集合并對(duì)其進(jìn)行構(gòu)樹(shù)，即利用K-means算法將特征向量集合劃分為k個(gè)組，每組由特征向量集合中距離該組聚類中心最近的描述子組成。然后將該過(guò)程遞歸地應(yīng)用到每組描述子向量中，從而將其劃分為新的k個(gè)組，每層都重復(fù)上述過(guò)程，直至達(dá)到詞匯樹(shù)深度d。k的經(jīng)驗(yàn)值一般取10[16-17]。

圖2 分層詞匯樹(shù)示意圖

1.3 影像檢索

在詞匯樹(shù)中進(jìn)行影像檢索時(shí)，使用詞頻-逆文本頻率(TF-IDF)[15]對(duì)影像進(jìn)行加權(quán)計(jì)算。具體計(jì)算公式為

(1)

式(1)中：ti為第i個(gè)單詞的權(quán)值；詞頻(term frequency，TF)表示某個(gè)視覺(jué)單詞在影像中出現(xiàn)的次數(shù)，次數(shù)越多表示該視覺(jué)單詞越重要；逆文本頻率IDF為影像總數(shù)量和包含該單詞的影像數(shù)目比的對(duì)數(shù)，是該單詞重要性的度量；ni為查詢影像包含視覺(jué)單詞i的影像數(shù)量；n為查詢影像包含所有視覺(jué)單詞的影像數(shù)量；N為影像總數(shù)量；Ni為影像數(shù)據(jù)集中至少有一個(gè)包含視覺(jué)單詞i的圖像數(shù)量。

當(dāng)詞匯樹(shù)創(chuàng)建完成后，每張影像則可以表示為加權(quán)后不同視覺(jué)單詞的組合。為了測(cè)量?jī)蓮堄跋褚曈X(jué)單詞向量q和d之間的相似性，通過(guò)構(gòu)建檢索數(shù)據(jù)庫(kù)，采用影像檢索系統(tǒng)中的倒排索引方法，對(duì)不同的視覺(jué)單詞計(jì)算對(duì)應(yīng)權(quán)重ω，然后采用式(2)計(jì)算其相似性得分因子s(q,d)。

(2)

1.4 綜合權(quán)重因子

如圖3所示，空間距離上越近的影像具有重疊區(qū)的可能性越高，若將影像之間的空間距離作為影響因素參與評(píng)價(jià)，則可大大提高兩者之間的相關(guān)性。

圖3 反距離權(quán)重因子

(3)

(4)

1.5 查詢深度閾值

查詢深度是指以綜合權(quán)重因子為依據(jù)，在影像集合中查詢出與當(dāng)前影像相似性最高的前Q′張影像，組成待匹配像對(duì)，如圖4所示。

圖4中，查詢影像Vi與查詢深度Q共組成Q′對(duì)像對(duì)進(jìn)行匹配。實(shí)際處理過(guò)程中Q過(guò)小會(huì)造成漏檢，而Q過(guò)大則會(huì)引入大量無(wú)效匹配像對(duì)，降低匹配效率。因此。采用查詢深度閾值的方式對(duì)查詢深度進(jìn)行分割，僅將閾值前的影像與查詢影像組成匹配像對(duì)進(jìn)入匹配環(huán)節(jié)。閾值計(jì)算公式為

圖4 查詢深度閾值

(5)

式(5)中：以類間方差最大為原則，將查詢深度Q內(nèi)的影像分為前景與背景兩部分；N1為屬于閾值t之前的影像數(shù)量；w1為屬于前景的影像頻率；w2為屬于后景的影像頻率；μ1為閾值t之前影像的綜合因子平均值；μ2為閾值t之后的影像綜合因子平均值；g為前景影像與背景影像之間的類間方差。

在查詢深度內(nèi)，類間方差最大對(duì)應(yīng)的位置即為查詢深度閾值，可表示為

(6)

式(6)中：g(t*)為查詢深度因子；t為初設(shè)查詢閾值。

1.6 檢索評(píng)價(jià)指標(biāo)

通過(guò)查準(zhǔn)率Pprecision和查全率Rrecall評(píng)價(jià)該算法的準(zhǔn)確性和完整性。通過(guò)特征提取時(shí)間和影像檢索平均時(shí)間評(píng)價(jià)算法的效率。查準(zhǔn)率通過(guò)計(jì)算查詢深度內(nèi)正確的查詢影像N與查詢深度Q的比值構(gòu)成。查全率則通過(guò)計(jì)算查詢深度內(nèi)正確的查詢影像N與窮舉法匹配中得到的所有正確影像數(shù)量M比值構(gòu)成，可分別表示為

(7)

(8)

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)數(shù)據(jù)

為了檢驗(yàn)本文算法的效率與適用性，分別對(duì)不同地形地貌的無(wú)人機(jī)影像數(shù)據(jù)進(jìn)行試驗(yàn)。如表1所示，記錄了5組試驗(yàn)無(wú)人機(jī)數(shù)據(jù)集的詳細(xì)信息。

數(shù)據(jù)A為江西省黃背村的無(wú)人機(jī)影像，地形以山地丘陵地為主。數(shù)據(jù)B為貴州省雞場(chǎng)鎮(zhèn)坪地村岔溝組的山體滑坡無(wú)人機(jī)影像，數(shù)據(jù)采用變高方式獲取，地形以高山地形為主。數(shù)據(jù)C為貴州省鬃嶺鎮(zhèn)滑坡無(wú)人機(jī)影像，數(shù)據(jù)采用等高與貼近攝影兩種方式獲取，其中滑坡體采用貼近方式獲取。數(shù)據(jù)D為甘肅省鹽鍋峽鎮(zhèn)的單相機(jī)影像數(shù)據(jù)，飛行航線以折返方式模擬雙相機(jī)，地形以平原為主。數(shù)據(jù)E為陜西省高明鄉(xiāng)平羅王村的五相機(jī)傾斜影像，地勢(shì)平坦地形起伏較低。

本文算法的采用Visual Studio C++2015的OpenCV 3.2計(jì)算機(jī)視覺(jué)庫(kù)，基于Windows 10 64位操作系統(tǒng)進(jìn)行算法編寫(xiě)。電腦配置為CPU i7-8700 3.2 GHz，內(nèi)存64G DDR4，硬盤(pán)256G SSD，顯卡為NVIDIA RTX 2080 8 G。

2.2 特征提取結(jié)果分析

分別利用OpenCV SIFT算法和SiftGPU算法對(duì)4組(每組200張)不同分辨率無(wú)人機(jī)影像進(jìn)行特征提取耗時(shí)統(tǒng)計(jì)實(shí)驗(yàn)。從表2可知，經(jīng)過(guò)圖形處理器(graphics processing unit，GPU)優(yōu)化的特征提取時(shí)間有了明顯縮短，加速比達(dá)到2～36倍，且影像分辨率越高，加速比越大。原因是SIFT算法提取特征的多量性、特征向量的高維性以及算法本身的復(fù)雜度較高，在CPU上實(shí)現(xiàn)的SIFT算法處理速度慢，利用SiftGPU算法提取圖像特征則可以大大提高計(jì)算效率。同時(shí)，SIFT算法提取單張?jiān)嫉臒o(wú)人機(jī)影像特征點(diǎn)數(shù)量都超過(guò)上萬(wàn)，而過(guò)多的特征點(diǎn)必將極大增加后續(xù)構(gòu)建詞匯樹(shù)的時(shí)間，降低了影像檢索效率。

表2 不同影像分辨率SIFT特征提取平均耗時(shí)

2.3 匹配像對(duì)提取結(jié)果分析

設(shè)置每張影像提取的特征點(diǎn)數(shù)量為1 000。構(gòu)建詞匯樹(shù)每層聚類中心數(shù)量k取10，構(gòu)樹(shù)深度d取5。構(gòu)建詞匯樹(shù)的影像從數(shù)據(jù)集中隨機(jī)提取，其數(shù)量設(shè)置為影像總數(shù)的20%，且最大影像數(shù)量不超過(guò)500幅。然后依次對(duì)表1中的5組影像進(jìn)行構(gòu)樹(shù)檢索實(shí)驗(yàn)。構(gòu)樹(shù)完成后，如圖5所示，依次對(duì)5組數(shù)據(jù)集中的查詢影像進(jìn)行檢索實(shí)驗(yàn)，得到查詢影像的待匹配像對(duì)。

分辨率：1 269×842

表1 試驗(yàn)無(wú)人機(jī)數(shù)據(jù)集

圖6展示了5組數(shù)據(jù)集中部分影像檢索結(jié)果前20幅。從檢索結(jié)果來(lái)看，數(shù)據(jù)集B、數(shù)據(jù)集C和數(shù)據(jù)集E前20幅影像均為正確影像。數(shù)據(jù)集A和D中前20幅影像共檢索得到正確影像分別為14幅和12幅，錯(cuò)誤影像6幅和8幅。其中，數(shù)據(jù)集A中影像重疊率不夠?qū)е虏樵冮撝翟O(shè)置過(guò)大，故檢索出較多錯(cuò)誤影像。因SIFT算子不具備完全仿射不變性，故對(duì)數(shù)據(jù)集D(傾斜影像)的檢索結(jié)果不理想。

黃色框?yàn)椴樵冇跋瘢患t色框?yàn)殄e(cuò)誤檢索影像；其余為正確影像；分辨率：1 269×791

2.4 匹配像對(duì)提取完整性分析

如圖7、圖8所示，分別利用SIFT、SURF[16]、ORB[17]和SiftGPU算法對(duì)表1中的5組數(shù)據(jù)集進(jìn)行詞匯樹(shù)構(gòu)樹(shù)，計(jì)算查詢影像的查準(zhǔn)率和查全率。

從圖7、圖8可以看出，5組數(shù)據(jù)集查準(zhǔn)率與查全率基本呈反比關(guān)系，查準(zhǔn)率提高，則查全率下降。表1中的5個(gè)測(cè)試數(shù)據(jù)集，從數(shù)據(jù)類型方面可分為兩類：正射類型、傾斜類型。其中，數(shù)據(jù)集A、B為正射類型，數(shù)據(jù)集C、D、E可歸為傾斜類型。在對(duì)正射類型影像進(jìn)行檢索時(shí)，本文算法計(jì)算查詢影像的查準(zhǔn)率和查全率基本與SIFT算法和ORB算法相當(dāng)且均高于SURF算法。在對(duì)傾斜類型影像進(jìn)行檢索時(shí)，本文算法計(jì)算查詢影像的查準(zhǔn)率和查全率與SIFT算法依然表現(xiàn)最好，ORB算法其次，SURF算法最低。原因是SIFT算法在一定程度上對(duì)影像抗仿射不變性表現(xiàn)高于其余兩種算法。

圖7 5組數(shù)據(jù)集的查準(zhǔn)率

圖8 5組數(shù)據(jù)集的查全率

為進(jìn)一步分析影像檢索的準(zhǔn)確率與查詢深度Q的關(guān)系，從數(shù)據(jù)集C、數(shù)據(jù)集D和數(shù)據(jù)集E中各抽取一張影像進(jìn)行檢索實(shí)驗(yàn)，計(jì)算查詢深度分別為100、200時(shí)影像的查準(zhǔn)率與查全率，統(tǒng)計(jì)結(jié)果如表3所示。

通過(guò)綜合權(quán)重因子進(jìn)行影像檢索因?yàn)榭紤]到影像的空間地理位置，在不同查詢深度下計(jì)算得到的查準(zhǔn)率與查全率結(jié)果均明顯優(yōu)于相似因子。在查詢深度為100時(shí)，數(shù)據(jù)集C、數(shù)據(jù)集D和數(shù)據(jù)集E查準(zhǔn)率分別提高了20%、19%和24%，查全率分別提高了19.2%、30.9%和17.4%。

為了分析綜合權(quán)重因子與相似因子的檢索計(jì)算詳細(xì)過(guò)程，從數(shù)據(jù)集B中提取一張影像分別在綜合權(quán)重因子模式和相似因子模式下進(jìn)行檢索得到的評(píng)價(jià)因子曲線進(jìn)行說(shuō)明，結(jié)果如圖9所示。

如圖9所示，綜合權(quán)重因子曲線和相似因子曲線都能檢索出絕大部分正確影像。兩種評(píng)價(jià)因子在曲線前端具有明顯差異，后端則趨于平坦，不具有明顯的可區(qū)分性。在相同的查詢深度閾值條件下，綜合權(quán)重因子檢索得到的正確影像數(shù)量比相似因子更多。因此，采用綜合權(quán)重因子進(jìn)行檢索計(jì)算，其正確的檢索影像大部分集中在查詢曲線的前端。

2.5 算法效率分析

表4中，特征提取時(shí)間與影像數(shù)量成正比，檢索時(shí)間隨著特征點(diǎn)數(shù)量的增加而增加。窮舉法和本文算法具有相同的特征提取時(shí)間，但本文算法平均檢索耗時(shí)與窮舉法相比要低兩個(gè)數(shù)量級(jí)?？傮w而言，利用窮舉法獲取的相似影像其檢索結(jié)果和本文算法檢索結(jié)果相差不大，但檢索效率遠(yuǎn)遠(yuǎn)不如本文算法。

表4 兩種方法檢索耗時(shí)對(duì)比

3 結(jié)論

提出了一種快速提取無(wú)人機(jī)影像匹配像對(duì)的方法。通過(guò)選取5種不同類型的影像數(shù)據(jù)進(jìn)行試驗(yàn)。得出如下結(jié)論。

(1)本文算法具有較高的適用性。不需要相機(jī)參數(shù)、不受地形條件限制即可自動(dòng)完成無(wú)人機(jī)影像匹配。

(2)本文算法能有效提高查詢影像的準(zhǔn)確率。與一般的詞匯樹(shù)檢索算法相比，數(shù)據(jù)集C、數(shù)據(jù)集D和數(shù)據(jù)集E查準(zhǔn)率分別提高了20%、19%和24%，查全率分別提高了19.2%、30.9%和17.4%。

(3)本文算法具有較高的計(jì)算效率。本文算法與窮舉法相比，平均檢索耗時(shí)要低兩個(gè)數(shù)量級(jí)。尤其針對(duì)海量的無(wú)人機(jī)影像數(shù)據(jù)，本文算法具有更高的處理效率。

將進(jìn)一步通過(guò)引入其他特征提取算子或?qū)υ~匯樹(shù)算法進(jìn)行修改，使本文算法能夠更好地適應(yīng)傾斜影像。