江 滔，馬 泳，黃 珺，王賀松，樊 凡

（武漢大學(xué)電子信息學(xué)院，湖北武漢430072）

引言

近年來(lái)，運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)算法(structure from motion，SfM)在文物數(shù)字化[1]、虛擬現(xiàn)實(shí)技術(shù)[2]、3D 游戲[3]、地理測(cè)量[4]等方面發(fā)揮了重要作用。根據(jù)圖像迭代計(jì)算方式，SfM 可以分為增量式和全局式兩種[5]。全局式SfM 以全局的方式同時(shí)獲取所有相機(jī)的相對(duì)運(yùn)動(dòng)，能夠避免場(chǎng)景漂移問(wèn)題，但精度較差且難以修正出現(xiàn)的錯(cuò)誤[6]。增量式SfM則是通過(guò)圖像逐個(gè)配準(zhǔn)的方式來(lái)完成整體的重建，對(duì)錯(cuò)誤匹配有很強(qiáng)的容錯(cuò)能力，總體精度較高，引起了廣泛和深入的研究，其基本流程見(jiàn)圖1。

圖1 增量式SfM 基本流程示意圖Fig.1 Pipeline of incremental SfM

如圖1所示，增量式SfM 首先通過(guò)圖像特征提取與匹配[7-10]建立一個(gè)以圖像為頂點(diǎn)、圖像對(duì)的匹配關(guān)系為邊的無(wú)向圖，稱(chēng)為視角連接圖或連接圖[5]，繼而在連接圖中確定一組匹配關(guān)系魯棒的初始種子對(duì)，這樣就能通過(guò)三角化與光束平差[11-12]構(gòu)建一個(gè)初始的三維點(diǎn)云結(jié)構(gòu)。然后再不斷地搜索下一張最佳圖像進(jìn)行三角化與光束平差，從而進(jìn)一步豐富和完整場(chǎng)景目標(biāo)的三維結(jié)構(gòu)。不難看出，初始種子對(duì)和下一張最佳圖像的選擇對(duì)增量式SfM 至關(guān)重要，它們分別決定了三維結(jié)構(gòu)的初始化以及增量式SfM 的重建順序，也是本文研究的主要內(nèi)容。

首先，在確定初始種子對(duì)時(shí)，由于增量式重建對(duì)初始化過(guò)程的誤差或者錯(cuò)誤非常敏感[13-14]，要求初始種子對(duì)的選擇必須高精度且高效。在提高精確度方面，Haner 等人[15]提出一種基于協(xié)方差傳播的種子對(duì)選擇算法，通過(guò)最小化相機(jī)協(xié)方差傳播率和重投影誤差來(lái)選擇種子對(duì)；Cui[16]等人選擇了擁有待校準(zhǔn)相機(jī)數(shù)目最多且最符合相機(jī)旋轉(zhuǎn)先驗(yàn)的圖像對(duì)作為種子對(duì)。這些算法通過(guò)為每個(gè)圖像計(jì)算額外信息的方式尋找最優(yōu)的初始種子對(duì)，精度高，但復(fù)雜度也高。在提高效率方面，Colmap[17]和VSFM[18]選擇了排除純旋轉(zhuǎn)關(guān)系且具有足夠多特征匹配對(duì)數(shù)量的圖像對(duì)作為初始種子對(duì)，效率上有了較大提升，但是忽略了在視角連接圖中種子對(duì)與相鄰頂點(diǎn)之間的關(guān)系，魯棒性差。

其次，在搜索下一張最佳圖像時(shí)，不佳的選擇不僅會(huì)污染已恢復(fù)的三維結(jié)構(gòu)，還可能導(dǎo)致連續(xù)性的圖像配準(zhǔn)錯(cuò)誤，從而導(dǎo)致重建效果下降甚至重建失敗。為此，研究者提出了大量的下一張最佳圖像的搜索方法。Degol 等人[19]通過(guò)預(yù)先在目標(biāo)場(chǎng)景中添加自定義的標(biāo)志物，選擇與已重建結(jié)構(gòu)相比標(biāo)志物最多的圖像作為下一張最佳圖像，該方法要求將標(biāo)志物置于場(chǎng)景目標(biāo)表面，通用性大大受限；Cao 等人[20]在視角連接圖中找到與已重建結(jié)構(gòu)存在最多匹配關(guān)系的圖像，作為下一張最佳圖像；Colmap[17]在Cao[20]等人的算法基礎(chǔ)上，進(jìn)一步考慮了圖像與已重建結(jié)構(gòu)的特征點(diǎn)分布的均勻程度，圖像特征點(diǎn)分布越均勻越有利于相機(jī)內(nèi)外參的求解。但是針對(duì)連接圖中頂點(diǎn)度數(shù)的不同情況，上述算法沒(méi)有采取下一張最佳圖像選擇的區(qū)別化優(yōu)先級(jí)策略，且需要在視角連接圖上全局搜索下一張最佳圖像，算法復(fù)雜度較大。

針對(duì)上述問(wèn)題，本文提出一種基于賦權(quán)連接圖的增量式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)算法，首先定義了基于圖像間立體匹配質(zhì)量的連接圖權(quán)重因子，具有定量評(píng)價(jià)雙視圖立體匹配質(zhì)量和指導(dǎo)初始種子對(duì)選擇的優(yōu)勢(shì)。在此基礎(chǔ)上提出了基于度數(shù)感知的初始種子對(duì)選擇算法，從而達(dá)到賦予高度數(shù)的頂點(diǎn)更高選擇優(yōu)先級(jí)的目的。最后提出了基于候選集的下一張圖像評(píng)分算法來(lái)搜索下一張最佳圖像，通過(guò)對(duì)搜索范圍的約束，提升了算法的效率。

1 基于賦權(quán)連接圖的增量式重建算法

本文提出的基于賦權(quán)連接圖的運(yùn)動(dòng)恢復(fù)算法的核心部分包括：1）定義圖像立體匹配質(zhì)量，創(chuàng)建賦權(quán)視角連接圖；2）在賦權(quán)連接圖中邊的權(quán)重的基礎(chǔ)上，搜索度數(shù)感知的最佳初始種子對(duì)；3）根據(jù)賦權(quán)視角連接圖中已重建頂點(diǎn)的連通性，創(chuàng)建下一張最佳圖像候選集，并提出基于頂點(diǎn)度數(shù)與特征點(diǎn)分布的圖像評(píng)價(jià)函數(shù)，對(duì)候選集中所有圖像評(píng)分，選擇評(píng)分最高的作為下一張最佳圖像。每次新得到下一張最佳圖像后，通過(guò)三角化和光束平差增量式地豐富三維結(jié)構(gòu)，圖2 是本文的算法框圖。本節(jié)將重點(diǎn)介紹上述3 個(gè)核心部分。

圖2 基于賦權(quán)連接圖的增量式重建算法流程圖Fig.2 Pipeline of weighted scene graph based incremental SfM

1.1 賦權(quán)連接圖的創(chuàng)建

增量式SfM 算法第1 步是通過(guò)圖像兩兩之間的特征點(diǎn)提取與匹配，將所有滿(mǎn)足圖像匹配關(guān)系[21]的圖像對(duì)加入匹配集M，進(jìn)而根據(jù)匹配集M中的圖像匹配關(guān)系對(duì)來(lái)構(gòu)建視角連接圖[22]，圖3(a)是視角連接圖的示意圖。

圖3 視角連接圖與賦權(quán)視角連接圖示意圖Fig.3 Schematic of scene graph and weighted scene graph

傳統(tǒng)視角連接圖通過(guò)邊來(lái)單純地反映圖像之間存在的匹配關(guān)系，但是卻沒(méi)有反映該圖像對(duì)作為初始種子以恢復(fù)初始三維結(jié)構(gòu)的優(yōu)劣。從一對(duì)圖像間恢復(fù)出三維信息的任務(wù)又稱(chēng)雙目立體視覺(jué)，雙目立體匹配關(guān)系由兩方面因素決定[23-24]：1）匹配特征點(diǎn)數(shù)量，匹配的特征點(diǎn)數(shù)量越多，越有利于計(jì)算魯棒的圖像變換關(guān)系，從而進(jìn)行三維重建；2）相機(jī)主光軸之間的相對(duì)旋轉(zhuǎn)角度，相對(duì)旋轉(zhuǎn)角度過(guò)小，目標(biāo)場(chǎng)景立體現(xiàn)象不明顯，不利于三維結(jié)構(gòu)的恢復(fù)；相對(duì)旋轉(zhuǎn)角度過(guò)大，圖像對(duì)重疊面積較小，從而導(dǎo)致存在特征點(diǎn)誤匹配的數(shù)量增多，立體匹配的誤差增大[24]。因此，為了衡量頂點(diǎn)間立體匹配關(guān)系的質(zhì)量，本文定義了一種基于匹配特征點(diǎn)數(shù)量與相對(duì)旋轉(zhuǎn)角度的權(quán)重因子w，并以此構(gòu)建賦權(quán)連接圖。圖3(b)給出了賦權(quán)連接圖的示意圖，記賦權(quán)連接圖G=(V,E,W)，其中頂點(diǎn)集代表輸入圖像集，邊集代表圖像匹配對(duì)，表示邊集E中邊元素的權(quán)重，基于匹配的特征點(diǎn)數(shù)量和相對(duì)旋轉(zhuǎn)角度的賦權(quán)連接圖權(quán)重因子wij定義為

式中：wNij表示頂點(diǎn)vi和vj間特 征點(diǎn)數(shù)量權(quán)重因子；wθi j表示頂點(diǎn)vi和vj對(duì)應(yīng)圖像間相對(duì)旋轉(zhuǎn)角度權(quán)重因子；Ni j表示頂點(diǎn)vi和vj間 匹配的特征點(diǎn)數(shù)量；θij表示相對(duì)旋轉(zhuǎn)角度；α 和 β分別是特征點(diǎn)數(shù)量權(quán)重因子和相對(duì)旋轉(zhuǎn)角度因子的歸一化系數(shù)，由于圖像對(duì)存在足夠的匹配特征點(diǎn)數(shù)量是完成圖像匹配的基礎(chǔ)，圖像相對(duì)旋轉(zhuǎn)角度是在該基礎(chǔ)上成立的，因此本文設(shè)置歸一化系數(shù)α和β的取值范圍為0 ≤β ≤0.5 ≤α ≤1。當(dāng)數(shù)據(jù)集拍攝的圖像密度大或者圖像質(zhì)量較高時(shí)，由于提取的特征點(diǎn)數(shù)量大，可以適當(dāng)減小 α并 增大 β；若數(shù)據(jù)集圖像密度低或者圖像質(zhì)量低不利于特征提取與匹配時(shí)，則應(yīng)適當(dāng)增大 α并減小 β。

特征點(diǎn)數(shù)量權(quán)重因子wNij由特征點(diǎn)數(shù)量決定，定義其歸一化的計(jì)算公式為

式中：NTMIN為圖像對(duì) (vi,vj)之間存在匹配關(guān)系的最低特征點(diǎn)對(duì)數(shù)目，當(dāng)數(shù)據(jù)集的圖像空間密度大或者圖像質(zhì)量高時(shí)，由于可以從圖像中提取到大量的特征點(diǎn)，因此應(yīng)提高NTMIN過(guò)濾掉匹配特征點(diǎn)數(shù)量少的圖像對(duì)；反之，當(dāng)圖像空間密度低或者圖像質(zhì)量低時(shí)，應(yīng)適當(dāng)減小NTMIN使得匹配特征點(diǎn)數(shù)量較少的圖像對(duì)也能參與到增量式重建。給定NTMIN的條件時(shí)，特征點(diǎn)匹配對(duì)Nij的數(shù)量越大，wNij越大，且。

相對(duì)旋轉(zhuǎn)角度權(quán)重因子wθij由相對(duì)旋轉(zhuǎn)角度θij與 最佳旋轉(zhuǎn)角度 θBEST決定，定義其歸一化的計(jì)算公式為

式中 θMIN和 θMAX分別為相對(duì)旋轉(zhuǎn)角度的最小值和最大值，θMIN<θBEST<θMAX，因此wθij∈(0,1)。在實(shí)際中 θBEST一 般用中間值 (θMIN+θMAX)/2來(lái)近似。

本文創(chuàng)建的賦權(quán)連接圖中的權(quán)重因子表征了圖像對(duì)之間的立體匹配質(zhì)量，權(quán)重因子越高，越有利于魯棒地恢復(fù)相機(jī)位姿和特征點(diǎn)三維空間位置，也越有利于構(gòu)建一個(gè)初始的三維結(jié)構(gòu)。

1.2 度數(shù)感知的初始種子對(duì)選擇

在完成權(quán)重因子計(jì)算并創(chuàng)建視角連接圖后，下一步是在連接圖中尋找初始種子對(duì)。一方面，從賦權(quán)連接圖中邊的角度，通過(guò)邊的權(quán)重因子可以找出立體匹配質(zhì)量好的圖像對(duì)；另一方面，從賦權(quán)連接圖整體的角度，由于度數(shù)大的頂點(diǎn)與其存在魯棒的立體匹配關(guān)系的頂點(diǎn)更多，在對(duì)應(yīng)位置上能進(jìn)行更多次的三角化與光束平差計(jì)算，從而獲得更完整和準(zhǔn)確的三維結(jié)構(gòu)，因此在其他條件如權(quán)重因子相似的情況下，應(yīng)當(dāng)給予度數(shù)大的頂點(diǎn)對(duì)更高的選擇優(yōu)先級(jí)。圖4 給出了度數(shù)不同的初始種子對(duì)的重建結(jié)果，圖4(a)和圖4(b)分別是在同一賦權(quán)視角連接圖中，權(quán)重因子相等但是度數(shù)不一樣的初始種子對(duì)選擇方式，在圖中使用虛線(xiàn)框出；圖4(c)和圖4(d)分別是上述低度數(shù)和高度數(shù)初始種子對(duì)對(duì)應(yīng)的重建結(jié)果，重建的目標(biāo)場(chǎng)景細(xì)節(jié)使用紅色橢圓框出。從重建結(jié)果可知，相對(duì)于低度數(shù)的初始種子對(duì)，度數(shù)高的初始種子對(duì)能獲得結(jié)構(gòu)更穩(wěn)定、空洞更少、細(xì)節(jié)更豐富的三維結(jié)構(gòu)。

圖4 不同度數(shù)的初始種子對(duì)的重建結(jié)果Fig.4 Reconstruction results of initial seed pairs with different degree

因此，本文在賦權(quán)連接圖權(quán)重因子的基礎(chǔ)上，設(shè)計(jì)了一種度數(shù)感知的初始種子對(duì)優(yōu)先級(jí)評(píng)價(jià)方法，記賦權(quán)連接圖中圖像對(duì)作為初始種子對(duì)的優(yōu)先級(jí)Pi j為

式中Dij是圖像對(duì)的歸一化度數(shù)因子，定義為

其中di和dj分別為頂點(diǎn)vi和vj的度數(shù)，滿(mǎn)足di,dj≥1，因此頂點(diǎn)對(duì)的度數(shù)和di+dj越大，Dij越接近1，否則越接近0。度數(shù)因子Dij與 權(quán)重因子wij之和越大，其作為初始種子對(duì)的優(yōu)先級(jí)Pij越大，根據(jù)(4)式找到優(yōu)先級(jí)最高的頂點(diǎn)對(duì)作為初始種子對(duì)。

1.3 基于候選集的下一張最佳圖像搜索

初始種子對(duì)在經(jīng)過(guò)三角化創(chuàng)建初始三維結(jié)構(gòu)之后，剩余的圖像就按照最有利于三維結(jié)構(gòu)恢復(fù)的順序，依次通過(guò)與該三維結(jié)構(gòu)中已有特征點(diǎn)的匹配關(guān)系，來(lái)恢復(fù)該圖像的位姿，并不斷將計(jì)算得到的新的特征點(diǎn)三維坐標(biāo)加入到現(xiàn)有三維結(jié)構(gòu)中去。在這一過(guò)程中，下一張最佳圖像的搜索是最重要的任務(wù)。該任務(wù)存在著效率和精度兩個(gè)方面的要求，分別對(duì)應(yīng)了下一張最佳圖像的搜索范圍和評(píng)價(jià)方法。

在下一張最佳圖像的搜索范圍方面，針對(duì)現(xiàn)有算法下一張最佳圖像是在所有未配準(zhǔn)圖像的全局環(huán)境下進(jìn)行，存在著搜索范圍大、搜索復(fù)雜度高的問(wèn)題，本文選擇在已重建的頂點(diǎn)集附近搜索下一張最佳圖像，通過(guò)限定搜索范圍的方式提升重建效率。如圖5所示，本文根據(jù)與已重建頂點(diǎn)的相鄰關(guān)系，構(gòu)建了下一張圖像的候選頂點(diǎn)集：

式中：Vcandidate代 表候選頂點(diǎn)集；Vcomplete代表已重建頂點(diǎn)集；V和E分別是賦權(quán)連接圖G的頂點(diǎn)集與邊集，所有與Vcomplete中的頂點(diǎn)相鄰的頂點(diǎn)的組成了下一張最佳圖像的候選頂點(diǎn)集Vcandidate，在圖5 中橙色頂點(diǎn)代表下一張最佳圖像的候選頂點(diǎn)，綠色頂點(diǎn)代表已重建頂點(diǎn)。

圖5 下一張最佳圖像候選頂點(diǎn)集示意圖Fig.5 Schematic diagram of the next best image candidate set

在下一張最佳圖像的評(píng)價(jià)方法方面，在對(duì)候選頂點(diǎn)作為下一張最佳圖像的進(jìn)行評(píng)價(jià)時(shí)，本文在考慮已恢復(fù)三維結(jié)構(gòu)在候選圖像上匹配特征點(diǎn)分布情況的同時(shí)，還考慮了候選頂點(diǎn)的度數(shù)對(duì)于下一輪迭代計(jì)算的影響。頂點(diǎn)度數(shù)高時(shí)不僅表明該頂點(diǎn)附近的視角信息豐富，而且在增量式迭代過(guò)程中，能有更多的頂點(diǎn)加入下一輪候選頂點(diǎn)集，為下一張最佳圖像提供了更大的評(píng)價(jià)與選擇空間。以圖5 為例，若度數(shù)大的v5作為下一張最佳圖像，那么下一輪迭代中，v6、v7、v8和v9都將加入候選頂點(diǎn)集，達(dá)到豐富候選頂點(diǎn)的目的。因此，對(duì)于候選頂點(diǎn)集Vcandidate中 的頂點(diǎn)vx，本文設(shè)計(jì)了一種基于頂點(diǎn)度數(shù)和特征點(diǎn)分布均勻程度的下一張配準(zhǔn)圖像評(píng)分函數(shù)Svx：

(6)式中f(vx)是的頂點(diǎn)vx的度數(shù)評(píng)價(jià)項(xiàng)，用于考察頂點(diǎn)vx對(duì) 于候選頂點(diǎn)平均度數(shù)相對(duì)大小，f(vx)定義如(7)式：

（7）式中dvx表示頂點(diǎn)vx在賦權(quán)連接圖G中的度數(shù)，記候選集中頂點(diǎn)的數(shù)量為N，則候選集頂點(diǎn)的平均度數(shù)可以表示為

(6)式中g(shù)(vx)是圖像特征點(diǎn)分布均勻程度評(píng)價(jià)項(xiàng)，為了評(píng)價(jià)已恢復(fù)結(jié)構(gòu)在圖像上匹配特征點(diǎn)的分布均勻程度，本文首先將圖像按照不同的尺度劃分成均勻的網(wǎng)格，然后統(tǒng)計(jì)每個(gè)尺度下存在特征點(diǎn)的網(wǎng)格的數(shù)量，最后再對(duì)不同尺度下的統(tǒng)計(jì)結(jié)果乘以不同的尺度系數(shù)，以此來(lái)衡量特征點(diǎn)在圖像中分布的均勻程度。g(vx)定義如（9）式：

式中：L表示對(duì)圖像進(jìn)行劃分的尺度數(shù)量，在尺度為l時(shí)，將圖像均勻劃分為 2l×2l的 網(wǎng)格；Kl表示圖像在尺度l下的尺度系數(shù)，用于反映該尺度對(duì)于圖像特征點(diǎn)分布均勻程序評(píng)價(jià)項(xiàng)的貢獻(xiàn)，本文的尺度系數(shù)定義為Kl=2l；Ml表示圖像在尺度為l時(shí)特征點(diǎn)的存在矩陣，其維度與網(wǎng)格被劃分的維度一致，因此它是一個(gè) 2l階 的方陣，若l尺度下圖像的某一個(gè)網(wǎng)格內(nèi)存在已恢復(fù)結(jié)構(gòu)與當(dāng)前圖像匹配對(duì)中的特征點(diǎn)，那么方陣對(duì)應(yīng)位置值為1，否則為0。因此尺度為l時(shí)存在特征點(diǎn)的網(wǎng)格數(shù)量可以通過(guò)Ml的L1范數(shù)‖Ml‖1表示：

表1 給出了圖5所示的賦權(quán)連接圖下，下一張最佳圖像的評(píng)分過(guò)程。圖5 中 (v3,v4)是初始種子對(duì)，此時(shí)候選頂點(diǎn)集Vcandidate={v0,v1,v2,v5}，如表1所示，給定尺度數(shù)量L=3時(shí)各個(gè)頂點(diǎn)的度數(shù)，給定視圖3D-2D 匹配對(duì)中圖像特征點(diǎn)的分布情況，根據(jù)(6)式計(jì)算出了不同的頂點(diǎn)作為下一張最佳圖像的評(píng)分。

表1 候選集中頂點(diǎn)作為下一張最佳圖像的評(píng)分Table 1 Score of candidate image as next best image

由表1 可知，在v0和v1度數(shù)相等的情況下，特征點(diǎn)數(shù)量多的頂點(diǎn)v1的 評(píng)分更高；在v1和v2頂點(diǎn)度數(shù)和特征點(diǎn)數(shù)量相等的情況下，在圖形中特征點(diǎn)分布得更均勻的頂點(diǎn)v2的評(píng)分更高；在v0和v5特征點(diǎn)數(shù)量及分布相等的情況下，度數(shù)大的頂點(diǎn)v5評(píng)分更高。綜上所述，在給定匹配特征點(diǎn)分布時(shí)，圖5所示的連接圖中評(píng)分最高的頂點(diǎn)v5將成為下一張最佳圖像。

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

為了驗(yàn)證本文算法的在重建效果和算法復(fù)雜度上的先進(jìn)性，選取了目前先進(jìn)的3 個(gè)增量式重建算法VSFM[18]、Colmap[17]、openMVG[25]與本文算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)集來(lái)自Farenzena[26]和Olsson[27]，實(shí) 驗(yàn) 環(huán) 境 為AMD Ryzen 9 5900X 12 核CPU、INVIDIAGTX1060 6 GB 的GPU以及16 GB 內(nèi)存的臺(tái)式電腦。本算法關(guān)鍵參數(shù)的取值如表2所示。

表2 本文算法的關(guān)鍵參數(shù)設(shè)置Table 2 Key parameter settings of proposed algorithm

針對(duì)不同的增量式重建算法，三維重建算法的性能通過(guò)主觀和客觀兩個(gè)方面進(jìn)行評(píng)價(jià)，主觀上通過(guò)觀察重建效果來(lái)評(píng)價(jià)，包括重建的目標(biāo)場(chǎng)景的完整程度、離群點(diǎn)的分布情況以及是否發(fā)生了場(chǎng)景漂移，即由于相機(jī)位姿恢復(fù)出現(xiàn)錯(cuò)誤或者誤差積累而導(dǎo)致重建目標(biāo)偏移實(shí)際情況的現(xiàn)象[10]；客觀上則可以通過(guò)相機(jī)校準(zhǔn)率、重建耗時(shí)、點(diǎn)云數(shù)量以及點(diǎn)云生成速率等幾個(gè)方面來(lái)進(jìn)行評(píng)價(jià)，其中相機(jī)校準(zhǔn)率指三維重建算法恢復(fù)出相機(jī)位姿的數(shù)目與數(shù)據(jù)中圖像數(shù)量的比值，該值越高表明算法對(duì)不同視角的立體信息利用率更高，抵御噪聲的能力越強(qiáng)，重建的結(jié)構(gòu)更完整；重建耗時(shí)指增量式SfM 完成對(duì)所有圖像的匹配并生成最終三維結(jié)構(gòu)的時(shí)長(zhǎng)，該值越小說(shuō)明完成重建得更快；點(diǎn)云數(shù)量指最終的三維結(jié)構(gòu)中的點(diǎn)云個(gè)數(shù)，該值越大表明結(jié)構(gòu)三維信息越豐富；點(diǎn)云生成速率即點(diǎn)云數(shù)量與重建耗時(shí)的比值，反映了單位時(shí)間內(nèi)算法恢復(fù)出的三維空間坐標(biāo)數(shù)量，用于反映各個(gè)算法的效率；

表3 給出了不同算法在公開(kāi)數(shù)據(jù)集上重建效果的表現(xiàn)。當(dāng)數(shù)據(jù)集規(guī)模較小且目標(biāo)特征點(diǎn)豐富時(shí)，如在Lund Cathedral 數(shù)據(jù)集上，4 種算法從整體來(lái)看都能對(duì)目標(biāo)的重建取得較好的效果，由于本文算法更加強(qiáng)調(diào)下一張最佳圖像在賦權(quán)視角連接圖中的相鄰性，僅存在于相鄰圖像之間的匹配特征點(diǎn)能夠得到優(yōu)先計(jì)算與重建，因此相較于其他算法，本文算法能夠還原出更多的細(xì)節(jié)，如建筑物的頂部的輪廓更加鮮明、表中所示的建筑物表面鏤空處重建得更加完整。在Gustav II Adolf 數(shù)據(jù)集上，由于目標(biāo)表面光滑以及圖像中背景天空部分較大等原因，圖像的特征點(diǎn)數(shù)量較少，此時(shí)不同算法的重建質(zhì)量出現(xiàn)了較大的差別，VSFM 和open-MVG 重建結(jié)果中都出現(xiàn)了較多的離群點(diǎn)，其中VSFM的重建結(jié)果中雕塑的頭部已無(wú)法辨認(rèn)，Colmap 和本文算法由于考慮了匹配特征點(diǎn)在圖像上分布的均勻性，能夠較好地選擇出增量式重建過(guò)程中的下一張最佳圖像，從而維持三維結(jié)構(gòu)的魯棒性；在Navona Square 和Piazza Erbe 數(shù)據(jù)集上，隨著圖像數(shù)量逐漸增多，VSFM 和Colmap 在重建過(guò)程中由于誤差的不斷積累造成了場(chǎng)景漂移，失去了對(duì)目標(biāo)進(jìn)行完整三維重建的能力，而openMVG 和本文提出的基于賦權(quán)連接圖的增量式重建算法，都保持了較好的重建效果。如表3所示，在對(duì)Navona Square 和Piazza Erbe 數(shù)據(jù)集重建時(shí)，在一些目標(biāo)有較大的角度變化的關(guān)鍵結(jié)構(gòu)處，本文算法能夠得到更多點(diǎn)云從而獲得更加豐富的細(xì)節(jié)，這是由于本文對(duì)度數(shù)更高的頂點(diǎn)在下一張最佳圖像候選集中賦予了更高的優(yōu)先級(jí)，對(duì)于一個(gè)大度數(shù)的頂點(diǎn)而言，三維結(jié)構(gòu)在該頂點(diǎn)周?chē)M(jìn)一步拓展和優(yōu)化的次數(shù)增多，從而能夠在該頂點(diǎn)周?chē)蟪潭鹊赜?jì)算出豐富和完整的三維點(diǎn)云，獲得更好的三維重建效果。綜上，本文算法在不同規(guī)模的數(shù)據(jù)集上都取得了相對(duì)更好的重建效果。

表3 各個(gè)算法在不同數(shù)據(jù)集上的重建效果Table 3 Reconstruction performance of algorithms on different datasets

圖6 給出了4 種不同算法在數(shù)據(jù)集上多次實(shí)驗(yàn)后客觀指標(biāo)的平均表現(xiàn)。由圖6(a)可知，在圖像數(shù)量少時(shí)，各個(gè)算法的相機(jī)校準(zhǔn)率相差不大，當(dāng)數(shù)據(jù)集圖像數(shù)量過(guò)百時(shí)，Colmap 和VSFM算法表現(xiàn)急劇下降，并且隨著數(shù)據(jù)集圖像數(shù)量的增多，相機(jī)校準(zhǔn)率隨之降低到不足10%，而openMVG 和本文算法能夠保持接近100%的相機(jī)校準(zhǔn)率，這說(shuō)明openMVG 和本文算法能適應(yīng)不同的數(shù)據(jù)集規(guī)模，在進(jìn)行圖像增量式重建時(shí)對(duì)于下一張最佳圖像有較強(qiáng)的搜索能力，驗(yàn)證了本文基于候選集的下一張最佳圖像評(píng)分方法的有效性。圖6(b)給出了算法在不同數(shù)據(jù)集的點(diǎn)云生成數(shù)量。隨著數(shù)據(jù)集圖像數(shù)量增多，Colmap 和VSFM 算法生成的點(diǎn)云數(shù)量反而呈現(xiàn)總體下降的趨勢(shì)，說(shuō)明了這兩種算法從多個(gè)視圖中提取出三維信息的能力有欠缺，構(gòu)建的點(diǎn)云結(jié)構(gòu)數(shù)量不足，難以完成場(chǎng)景目標(biāo)的重建任務(wù)。openMVG 和本文算法隨著數(shù)據(jù)集圖像數(shù)量的增多，始終保持了點(diǎn)云數(shù)量水平上升的趨勢(shì)，本文算法在不同數(shù)據(jù)集上都生成了最多的點(diǎn)云數(shù)量，體現(xiàn)了本文算法較強(qiáng)的魯棒性。由圖6(c)可知，不同的算法隨著數(shù)據(jù)集圖像數(shù)量的增多，重建耗時(shí)的增量不同。其中Colmap 重建耗時(shí)平均增量最高，本文算法重建耗時(shí)的平均增量最低，在各個(gè)數(shù)據(jù)集上，本文算法比重建速度最慢的Colmap 平均重建耗時(shí)減少了58%，比openMVG 平均重建耗時(shí)減少了35%，比VSFM 平均重建耗時(shí)減少了19%。圖6(d)給出了算法在不同數(shù)據(jù)集上點(diǎn)云生成速率的表現(xiàn)，其中Colmap 和VSFM 隨著數(shù)據(jù)集規(guī)模增大，其點(diǎn)云生成速率急劇下降，本文算法則始終保持了較高水平的點(diǎn)云生成速率，綜合各個(gè)數(shù)據(jù)集來(lái)看，本文比Colmap 的點(diǎn)云生成速率快了105%，比openMVG 快了25%，比VSFM 快21%，整體具有更高的重建效率。

圖6 算法在不同數(shù)據(jù)集上的客觀指標(biāo)表現(xiàn)Fig.6 Objective indicators performance of mentioned algorithm on different data sets

3 結(jié)論

本文提出了一種基于賦權(quán)連接圖的增量式運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)算法。首先為賦權(quán)連接圖設(shè)計(jì)了一種基于立體匹配質(zhì)量的權(quán)重因子；其次在初始種子對(duì)的選擇上，結(jié)合權(quán)重因子設(shè)計(jì)了一種度數(shù)感知的初始種子對(duì)優(yōu)先級(jí)選擇方法，能在全局搜索最佳的初始種子對(duì)；最后針對(duì)下一張圖像的選擇，提出了一種基于候選集的下一張最佳圖像評(píng)分算法，算法先根據(jù)頂點(diǎn)的相鄰關(guān)系獲取下一張最佳圖像的候選集，然后對(duì)候選集中的頂點(diǎn)根據(jù)其度數(shù)與匹配特征點(diǎn)分布均勻程度給予評(píng)分，并選擇評(píng)分最高的作為下一張最佳圖像。實(shí)驗(yàn)結(jié)果表明，相較于其他先進(jìn)的增量式算法，本文提出的基于賦權(quán)連接圖的增量式重建算法能夠很好地適應(yīng)不同規(guī)模的數(shù)據(jù)集，在保證了目標(biāo)重建的完整性和重建效果的同時(shí)，在算法效率上取得了明顯的領(lǐng)先優(yōu)勢(shì)。