圖索引結(jié)構(gòu)詞袋模型的無人機(jī)影像匹配對(duì)檢索

劉思康,郭丙軒,姜 三,鄢茂勝

(1. 武漢大學(xué)測(cè)繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn),湖北 武漢 430079; 2. 中國地質(zhì)大學(xué)(武漢),湖北 武漢 430074)

隨著無人機(jī)的快速發(fā)展,無人機(jī)影像已成為重要的遙感數(shù)據(jù)源,并在林業(yè)調(diào)查[1]、災(zāi)區(qū)應(yīng)急[2]、智慧城市[3]等領(lǐng)域得到廣泛應(yīng)用。運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)(structure from motion, SfM)技術(shù)成為無人機(jī)影像空中三角測(cè)量的標(biāo)準(zhǔn)方案,可直接從重疊影像恢復(fù)其位姿和場(chǎng)景三維結(jié)構(gòu)[4-5]。由于影像數(shù)據(jù)量龐大、位置參數(shù)缺失等問題,如何準(zhǔn)確、快速地檢索出重疊影像對(duì)成為提高SfM效率和穩(wěn)健性的關(guān)鍵問題。

無人機(jī)影像匹配像對(duì)的檢索目的是查詢具有空間重疊的影像對(duì)。在計(jì)算機(jī)視覺領(lǐng)域,基于視覺相似性的圖像檢索是一種常見方法[6-7]。基于詞袋模型(bag of words,BoW)檢索技術(shù)是很多開源SfM框架的首選匹配對(duì)查詢方法[8]。如Colmap首先利用尺度不變特征變換(scale invariant feature transform, SIFT)算子[9]提取影像描述子;然后采用分層K-means算法生成視覺單詞,構(gòu)建詞匯樹[10-11];最后采用詞匯樹的單詞-影像倒排索引結(jié)構(gòu),影像之間相似性采用單詞內(nèi)部描述子之間的漢明距離表示。但計(jì)算漢明距離耗時(shí)長,且引入很多錯(cuò)誤匹配。DBoW(Dorian bag of words)使用詞頻-逆向文件頻率(term frequency-inverse document frequency,TF-IDF)方法對(duì)視覺單詞進(jìn)行加權(quán),檢索相似影像[12]。該方法利用視覺單詞個(gè)數(shù)和出現(xiàn)該單詞的影像個(gè)數(shù)進(jìn)行加權(quán),在保證精度的前提下提升匹配像對(duì)查找效率。針對(duì)大規(guī)模匹配像對(duì)查找,使用TF-IDF導(dǎo)致檢索時(shí)浪費(fèi)大量時(shí)間查詢相同單詞以計(jì)算得分。最鄰近查找算法中有一系列索引結(jié)構(gòu),包括哈希表法[13]、樹狀結(jié)構(gòu)[14]、基于圖的索引結(jié)構(gòu)[15]。近年來,基于圖的搜索是高維數(shù)據(jù)最鄰近查找趨勢(shì),且基于鄰近圖的近似最鄰近搜索方法(ANNS)具有很高的査詢效率[16]。文獻(xiàn)[17—18]提出了一種基于導(dǎo)航小世界(navigable small world,NSW)的鄰近圖搜索算法。該算法通過不斷向圖中插入頂點(diǎn),從插入頂點(diǎn)出發(fā)找到圖中最鄰近的M個(gè)頂點(diǎn),建立邊作為頂點(diǎn)之間鏈接關(guān)系。隨著新頂點(diǎn)的插入,開始插入的頂點(diǎn)與最鄰近頂點(diǎn)之間的邊成為長距離邊,從而使圖具有可導(dǎo)航性質(zhì),具有更高的查詢效率。該過程存在大量高維距離計(jì)算,GPU有大量的核能夠有效地并行高維距離計(jì)算,顯著改善了其計(jì)算效率。

針對(duì)上述問題,本文提出一種基于圖索引結(jié)構(gòu)詞袋模型(graph structure bag of words,GSBoW),實(shí)現(xiàn)無人機(jī)影像匹配對(duì)的高效檢索,將訓(xùn)練好的單詞作為頂點(diǎn),邊作為頂點(diǎn)間連接關(guān)系,設(shè)計(jì)NSW圖索引結(jié)構(gòu),描述子在GPU端利用NSW圖索引結(jié)構(gòu)的最鄰近單詞查詢;提出一種TF-IDF-Match4計(jì)算方法,通過填充詞頻向量、減少訪問沖突、采用共享內(nèi)存、設(shè)計(jì)特定數(shù)據(jù)結(jié)構(gòu),顯著提升TF-IDF計(jì)算效率;利用3組無人機(jī)影像進(jìn)行試驗(yàn),以驗(yàn)證本文方案的可靠性。

1 方法原理

本文主要基于圖索引結(jié)構(gòu)的詞袋模型,實(shí)現(xiàn)無人機(jī)影像匹配對(duì)檢索。主要包含5個(gè)步驟:①訓(xùn)練數(shù)據(jù)準(zhǔn)備和SIFT特征提取;②利用分層K-means算法對(duì)訓(xùn)練描述子進(jìn)行聚類,生成詞袋模型的視覺單詞;③以視覺單詞為頂點(diǎn)、單詞鄰接關(guān)系為連接邊建立NSW圖,構(gòu)建視覺單詞的索引結(jié)構(gòu);④基于NSW圖索引結(jié)構(gòu)進(jìn)行影像描述子最鄰近查找,獲取對(duì)應(yīng)視覺單詞集合;⑤利用改進(jìn)的TF-IDF-Match4加權(quán)方式,計(jì)算查詢影像與數(shù)據(jù)庫影像的詞頻向量,通過比較詞頻向量相似性,實(shí)現(xiàn)相似影像檢索。其中步驟①—步驟③在CPU端實(shí)現(xiàn);步驟④—步驟⑤在GPU端實(shí)現(xiàn)。

1.1 離線導(dǎo)航小世界圖索引結(jié)構(gòu)構(gòu)建

為了構(gòu)建視覺單詞,采用山東省青島市城區(qū)無人機(jī)影像為訓(xùn)練數(shù)據(jù)(如圖1所示)。首先,提取數(shù)據(jù)集中23 261張影像的SIFT描述子,共得到261 709 511個(gè)特征描述子。然后,采用分層K-means聚類算法對(duì)特征描述子進(jìn)行聚類。其中,詞匯樹層數(shù)設(shè)置為3;詞匯樹分支數(shù)設(shè)置為512。建立詞匯樹后,詞匯樹的葉子節(jié)點(diǎn)即代表所生成的視覺單詞。最后,所有視覺單詞作為候選頂點(diǎn)集合V,構(gòu)建視覺單詞的NSW圖索引結(jié)構(gòu)。主要步驟包括:①從候選頂點(diǎn)V中隨機(jī)挑選一個(gè)頂點(diǎn)vi;②將頂點(diǎn)vi插入圖中,尋找圖中頂點(diǎn)vi最鄰近的f個(gè)頂點(diǎn),若鄰近頂點(diǎn)不足f個(gè),則按最大數(shù)查找;③建立vi與這些鄰近頂點(diǎn)的邊連接關(guān)系;④重復(fù)步驟①—步驟③,直至候選頂點(diǎn)集合為空。構(gòu)建過程如圖2所示。

圖1 訓(xùn)練數(shù)據(jù)集

圖2 NSW圖索引結(jié)構(gòu)構(gòu)建過程

1.2 基于NSW圖索引結(jié)構(gòu)最鄰近單詞查詢

本文基于NSW圖索引結(jié)構(gòu)的最鄰近查找算法的原理為:默認(rèn)從索引為G的單詞開始,從按照距離降序的優(yōu)先級(jí)隊(duì)列Q中提取離查詢描述子最近的單詞,按照距離降序的優(yōu)先隊(duì)列Topk中的候選單詞順序更新,并將單詞的鄰接單詞插入Q中,以便于下次查找。當(dāng)從優(yōu)先級(jí)隊(duì)列Q中提取的單詞距離比搜索到的Topk中距離最大的候選單詞更大時(shí),查找循環(huán)停止。抽象而言,算法貪婪地沿著一條路徑到達(dá)查詢描述子的最近鄰近單詞。

在CUDA并行計(jì)算架構(gòu)上,線程束是最基本的執(zhí)行單元,本文使用一個(gè)線程束查找一個(gè)描述子的最鄰近單詞,實(shí)現(xiàn)GPU端上描述子的距離計(jì)算。GPU并行計(jì)算原理如圖3所示。①選單詞定位:在構(gòu)建NSW圖索引結(jié)構(gòu)時(shí),每個(gè)頂點(diǎn)固定連接最鄰近的3個(gè)頂點(diǎn),將NSW圖索引存儲(chǔ)在GPU端,此時(shí)需要一個(gè)索引即每個(gè)頂點(diǎn)的偏移量,存儲(chǔ)固定層次圖像可消除額外的索引查找,然后乘以固定偏移量定位單詞。②批量距離計(jì)算:從候選定位單詞表中獲取對(duì)應(yīng)單詞,計(jì)算描述子到單詞的距離,一個(gè)線程束中所有的線程均參與該階段。每個(gè)線程負(fù)責(zé)一個(gè)描述子的4個(gè)維度,并行計(jì)算128維描述子到單詞的距離,最后第1個(gè)線程統(tǒng)計(jì)所有線程計(jì)算結(jié)果,并將結(jié)果輸出到共享內(nèi)存中的數(shù)組。32個(gè)線程訪問連續(xù)存儲(chǔ)器地址更容易并行。③數(shù)據(jù)結(jié)構(gòu)維護(hù):查詢過程中多次訪問距離、Q、Topk、數(shù)組,因此將它們存儲(chǔ)到共享內(nèi)存中,共享內(nèi)存是流處理器組中的高速內(nèi)存空間,流處理器訪問速度遠(yuǎn)比全局內(nèi)存快。

圖3 GPU端最鄰近查找單詞流程

1.3 TF-IDF-Match4計(jì)算

對(duì)于包含M個(gè)單詞的導(dǎo)航小世界圖,影像可以表示為單詞頻率所組成的K維向量,采用詞頻-逆文本頻率,對(duì)影像的視覺單詞進(jìn)行加權(quán)。詞頻(term frequency,TF)表示某個(gè)視覺單詞在影像中出現(xiàn)的次數(shù),出現(xiàn)次數(shù)越多代表該視覺單詞越重要;逆文本頻率(inverse document frequency,IDF)是視覺單詞的獨(dú)特性度量。若一個(gè)視覺單詞僅在幾幅影像中出現(xiàn),則說明該單詞具有較高的獨(dú)特性。假設(shè)索引影像表示為詞頻向量Vd=[(id1,t1)(id2,t2) … (idk,tk)],則詞頻向量Vd中ti的計(jì)算公式為

(1)

式中,nid表示單詞i在索引影像d中的次數(shù);nd表示索引影像d包含的總詞總數(shù);Ni表示包含單詞i的影像數(shù);N表示索引影像的總數(shù);idk表示單詞的序號(hào)。

考慮到GPU存在大量核數(shù),提出一種GPU端TF-IDF-Match4權(quán)重得分計(jì)算方法。在計(jì)算查詢影像與數(shù)據(jù)庫影像的相似性值前,假設(shè)單詞總數(shù)為M,則將影像的詞頻向量填充到M維,對(duì)于未出現(xiàn)單詞,將其權(quán)重賦值為0,其他單詞權(quán)重保持不變。將查詢影像和數(shù)據(jù)庫影像的詞頻向量拷貝到GPU端,一個(gè)線程負(fù)責(zé)計(jì)算查詢影像與數(shù)據(jù)庫中一張影像之間的得分,此時(shí)線程內(nèi)部需要循環(huán)詞頻向量進(jìn)行對(duì)應(yīng)相乘累加,即可計(jì)算相似度,省去大量重復(fù)過程,且能實(shí)現(xiàn)多線程并行處理。

TF-IDF-Match4方法同時(shí)使用了4種GPU端優(yōu)化計(jì)算得分方法:①將詞頻向量存儲(chǔ)在全局內(nèi)存中,一個(gè)線程負(fù)責(zé)計(jì)算檢索影像與數(shù)據(jù)庫中所有影像之間的得分。此時(shí)一個(gè)線程負(fù)責(zé)計(jì)算所有影像,工作量大且全局內(nèi)存訪問速度慢。②將待檢索影像詞頻向量存儲(chǔ)到共享內(nèi)存中,一個(gè)塊中的一個(gè)線程負(fù)責(zé)計(jì)算檢索影像與數(shù)據(jù)庫中一張影像之間的得分。此時(shí)共享內(nèi)存是由32個(gè)等大小的內(nèi)存塊組成的,一個(gè)塊中所有線程同時(shí)訪問同一個(gè)內(nèi)存塊不同地址時(shí),會(huì)產(chǎn)生內(nèi)存塊沖突。③將待檢索影像的詞頻向量維數(shù)加1且賦值為0,此時(shí)一個(gè)塊中所有線程同時(shí)訪問共享內(nèi)存時(shí),多個(gè)線程訪問通道錯(cuò)開,訪問的都是不同內(nèi)存塊,內(nèi)存塊沖突減少,線程等待時(shí)間大幅降低。④使用float4類型存儲(chǔ)詞頻向量,與float類型相比,多字節(jié)向量加載或存儲(chǔ)僅需要發(fā)出單個(gè)指令,每指令字節(jié)的比率更高,且特定存儲(chǔ)器事務(wù)的總指令延遲更低,減少了事務(wù)請(qǐng)求次數(shù),提高了計(jì)算效率。以上計(jì)算方式相比原有CPU端計(jì)算,速度有大幅提升。

2 試驗(yàn)與分析

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

利用3組無人機(jī)影像進(jìn)行試驗(yàn)驗(yàn)證,采用多旋翼無人機(jī)進(jìn)行數(shù)據(jù)采集。第1組數(shù)據(jù)來自江蘇省南京市雞鳴寺,包含許多低矮建筑物,共采集325張影像,影像尺寸為4000×3000像素;第2組數(shù)據(jù)來自山西省運(yùn)城市大交鎮(zhèn),存在大量裸地覆蓋,共采集1082張影像,影像尺寸為7360×4912像素;第3組數(shù)據(jù)來自湖北省宜昌市三峽大學(xué),從高層建筑物試驗(yàn)區(qū)采集4750張影像,影像尺寸為4000×6000像素。

2.2 結(jié)果與分析

為分析本文無人機(jī)影像匹配對(duì)檢索算法的效率和精度,利用3組無人機(jī)影像數(shù)據(jù)進(jìn)行試驗(yàn),并分別與Colmap詞袋模型查詢算法、DBow詞袋模型查詢算法進(jìn)行對(duì)比。采用精度、效率、匹配對(duì)數(shù)量作為算法性能的評(píng)價(jià)指標(biāo)。其中,檢索精度是得分排名前m的影像中正確影像個(gè)數(shù)n與實(shí)際參考影像個(gè)數(shù)m的比值。所有算法均采用C++實(shí)現(xiàn),且運(yùn)行在配置為英特爾i7-7700K 8核CPU、英偉達(dá)GeForce GTX1050ti GPU的臺(tái)式計(jì)算機(jī)上。為獲取影像匹配對(duì)的參考數(shù)據(jù),首先利用Smart3D商業(yè)軟件對(duì)每組數(shù)據(jù)進(jìn)行空中三角測(cè)量處理;然后將連接點(diǎn)數(shù)量大于30的影像對(duì)標(biāo)記為參考匹配像對(duì)。圖4為不同方法的檢索精度和匹配對(duì)數(shù)量。結(jié)果表明,本文檢索算法在3組數(shù)據(jù)的匹配對(duì)精度和正確匹配對(duì)數(shù)量均高于Colmap和DBoW,且最大精度可達(dá)96.51%。Colmap、DBoW算法的最大精度分別為95.5%、94.6%。進(jìn)一步分析檢索匹配對(duì)數(shù)量可知,本文算法查找出的正確匹配對(duì)數(shù)量在不同數(shù)據(jù)量上均為最高。

圖4 匹配對(duì)查找試驗(yàn)結(jié)果

檢索匹配對(duì)詳細(xì)耗時(shí)見表1。結(jié)果表明,與Colmap和DBoW使用的K-means樹索引結(jié)構(gòu)相比,本文單詞檢索時(shí)間減少一半以上,且單詞檢索速度與數(shù)據(jù)量大小無關(guān)。同時(shí),考慮到影像相似性計(jì)算時(shí)間,本文算法的計(jì)算效率有顯著提升。對(duì)于雞鳴寺數(shù)據(jù),本文算法相比Colmap、DBoW,效率分別提升41和25倍。對(duì)于大交鎮(zhèn)數(shù)據(jù),本文算法相比Colmap、BoW,效率分別提升55和30倍。對(duì)于三峽大學(xué)數(shù)據(jù),本文算法相比Colmap、DBoW,效率分別提升76和32倍。試驗(yàn)結(jié)果表明,本文提出的TF-IDF-Match4方法,隨著數(shù)據(jù)量的增大,效率提升會(huì)更加顯著。考慮整體詞袋模型查找匹配對(duì)的時(shí)間消耗,本文算法計(jì)算效率有顯著提升。對(duì)于雞鳴寺數(shù)據(jù),本文整體算法比Colmap、DBoW詞袋模型效率分別提升20和13倍;對(duì)于大交鎮(zhèn)數(shù)據(jù),效率分別提升15和30倍;對(duì)于三峽大學(xué)數(shù)據(jù),效率分別提升45和18倍。

表1 匹配對(duì)查詢耗時(shí)詳細(xì)信息 min

為進(jìn)一步分析本文無人機(jī)影像匹配對(duì)檢索方法的有效性,將影像匹配對(duì)檢索結(jié)果應(yīng)用到稀疏點(diǎn)云三維重建中。使用開源庫Colmap中的稀疏點(diǎn)云三維重建算法,并從影像入網(wǎng)張數(shù)、三維重建效率、重建點(diǎn)云數(shù)量、空中三角測(cè)量精度4個(gè)方面進(jìn)行評(píng)價(jià),統(tǒng)計(jì)結(jié)果見表2。對(duì)于入網(wǎng)張數(shù)而言,3組數(shù)據(jù)均全部入網(wǎng),說明3種方法在無GPS的情況下均能提供有效的匹配對(duì),完成空中三角測(cè)量完成構(gòu)網(wǎng)。對(duì)于點(diǎn)云數(shù)量而言,本文算法提供的匹配對(duì)生成的點(diǎn)云個(gè)數(shù)明顯高于Colmap、DBoW算法生成的點(diǎn)云個(gè)數(shù),說明提供的正確匹配像對(duì)占總體的比例更大,生成的點(diǎn)云個(gè)數(shù)更多。雞鳴寺數(shù)據(jù)上點(diǎn)云個(gè)數(shù)最大相差24 000,大交鎮(zhèn)數(shù)據(jù)最大相差18 982,峽大學(xué)數(shù)據(jù)最大相差206 932。對(duì)于稀疏點(diǎn)云重建時(shí)間和空中三角測(cè)量精度而言,本文算法最小精度達(dá)1.15像素,最大精度達(dá)1.29像素,最短重建時(shí)間為20.15 min,最長重建時(shí)間是3572 min,在不同數(shù)據(jù)上整體稀疏點(diǎn)云重建的時(shí)間和空中三角測(cè)量精度也均低于Colmap、DBoW算法,說明本文算法提供的正確匹配對(duì)更多,去除錯(cuò)誤匹配耗時(shí)更短,整體空三平差速度更快。

表2 試驗(yàn)數(shù)據(jù)詳細(xì)信息

3 結(jié) 語

本文利用單詞建立圖索引結(jié)構(gòu),將傳統(tǒng)的基于樹查找單詞轉(zhuǎn)化為基于圖查找單詞,設(shè)計(jì)了一種導(dǎo)航小世界圖索引結(jié)構(gòu)最鄰近查找單詞的算法,大幅提高了影像查找對(duì)應(yīng)單詞效率。針對(duì)詞袋模型的詞頻-逆文本頻率逆序索引結(jié)構(gòu),提出了一種TF-IDF-Match4算法,在GPU端優(yōu)化計(jì)算得分方法,大幅提升了計(jì)算匹配對(duì)得分效率。利用3組無人機(jī)影像數(shù)據(jù)進(jìn)行試驗(yàn),結(jié)果表明,本文模型查詢無人機(jī)影像匹配對(duì),顯著提高了查找初始匹配效率,比Colmap詞袋模型最高提升45倍,比DBow詞袋模型最高提升18倍;同時(shí)顯著地提高了初始匹配精度,即提供的初始匹配對(duì)在三維重建中能夠取得更高的精度。