基于凸優化改進的相機全局位置估計方法

謝理想　萬剛　曹雪峰　王慶賀　王龍

運動恢復結構算法(Structure from motion,SfM)是多視圖三維重建技術的關鍵內容,一直都是計算機視覺領域的基礎問題.SfM 在虛擬現實、增強現實、運動追蹤、逆向工程、城市場景建模等方面都有廣泛應用.SfM算法解決的是一個從二維圖像恢復拍攝時的相機運動和場景三維稀疏結構的問題.SfM算法通常由以下三個步驟組成:1)圖像特征匹配及相機相對位姿估計(相對平移和相對旋轉);2)相機運動估計,即根據相機相對位姿估計相機的全局旋轉和全局位置.3)利用經過最小化重投影誤差優化的相機參數進行場景稀疏結構恢復,常用光束法平差[1](Bundle adjust,BA)作為優化算法.在目前SfM算法中對第1)和第3)步驟的研究的較為成熟,出現了較為完備的理論和算法.相對而言,對第2)步驟的研究尚不夠成熟,尤其是相機全局位置估計部分,現有的位置估計方法多對外點敏感.

現有的SfM算法可大致分為兩類.一類是增量式方法[2?8](Incremental method),選取兩張圖像作為初始像對進行初始重建,然后不斷加入新的圖像以擴大重建的范圍,直到所有的圖像全部重建完畢.在這個迭代過程中,通常會進行多次BA處理以優化相機運動參數及重建的場景三維稀疏結構.另一類是全局式方法[9?11](Global method),相對于增量式方法來說,全局式方法不是一個逐漸累加的過程,而是針對所有圖像同時進行估計,一次性解算所有的相機運動參數,參數解算完畢后再進行場景三維稀疏結構的估計,最后只進行一次全局性的BA優化,最終得到相機參數和稀疏場景結構.

增量式方法首先利用初始像對估計相機運動和局部場景三維稀疏結構,后續的迭代重建是基于初始像對的重建結果進行的,最終的計算結果對初始像對選取的依賴性較高.此外,在不斷的迭代BA過程中,誤差會不斷累積,導致后續圖像重建的計算誤差大于前者,最終可能產生場景漂移現象.全局式方法對所有的圖像同時進行處理,只進行一次的BA優化.這不僅能有效地避免誤差累積,將誤差平均分配,并且省去了耗時反復的迭代BA過程.另外全局式方法中的相機運動估計和場景三維稀疏結構恢復是分開進行的,在所有相機運動全部估計完畢后再進行場景三維稀疏結構恢復,大幅減少了每次需要估計的參數個數,這也從另一方面提升了算法效率.

雖然全局式SfM算法特點突出,但現有的SfM算法中,增量式方法明顯多于全局式方法.這是由于現有的相機運動估計算法大多對外點敏感,這里的外點主要包括前文步驟1)中圖像特征匹配過程中產生的誤匹配值以及在相機運動估計過程中由于誤匹配存在產生的外點(例如相機相對平移方向估計結果中的外點).增量式方法通過反復迭代BA過程可以有效地剔除大部分的誤匹配,降低外點對估計結果的影響.而全局式方法并沒有這一剔除過程,當外點較多時估計的精度無法保證.這種情況在處理大規模、無序圖像時表現的尤為明顯.因此對外點魯棒的相機運動估計算法具有很高的研究價值,可以充分發揮全局式SfM方法的優勢,提高SfM處理效率和精度.

在全局式SfM 過程中相對運動估計分為相機全局旋轉和相機全局位置估計兩部分,通常這兩部分開進行.近20年,相機運動估計的研究取得了明顯的進展,其中相機全局旋轉估計方面已經出現不少成熟穩定的算法[12?15].然而,在相機全局位置估計方面,尤其是在處理大規模、無序圖像集時,現有的相機全局位置估計算法存在幾個問題:估計結果不穩定[7,16?17]、對相對平移方向中的外點的敏感[18?19]以及非凸方程易陷入局部最優解[11].因此,魯棒、高效并且能保證收斂于全局最優解的全局位置估計方法就顯得很重要.

早期的全局位置估計算法[16,20]是基于相機間相對平移方向構建線性方程并求取方程的最小二乘解來進行全局位置的估計.這類線性方法具有很高的計算效率,但后續研究發現通過這類方法獲取的解并不穩定,在少數位置可能會產生偏離真值的偽解(Spectral solution).文獻[7]試圖通過估計相機之間相對平移的比例來消除這種偽解,但并未有效提升估計結果的精度.文獻[11]提出Lie代數平均法,可有效解決偽解的問題,但因為采用非凸的優化方程,導致估計結果收斂到局部最優解而無法保證全局最優.文獻[18]提出了一種基于范數的擬凸優化方法.這種方法可以很好地解決局部最優解的問題,但范數通常易受外點影響,估計結果難以保證.同本文方法最相似的是文獻[10]提出的方法,文獻[10]構建了一個基于幾何距離約束的線性方程,但采用的是范數約束,導致對外點敏感.另一個和本文相關的是文獻[21]提出的基于相對平移方向構成線性方程求取最小化范數解的方法,文獻[21]通過加入約束來有效消除子偽解問題,但因相對平移方向觀測值中外點的影響,估計結果的精度會降低.另外,文獻[22]中提出了一種基于經典剛體平移理論的全局位置估計算法.同文獻[22]相比,本文采用的是平行剛體理論,使得估計方程截然不同.文獻[23]提出了一種稱為1DSfM的方法,首先通過預處理剔除相對平移方向測量中的外點,再設計一個非凸的優化方程對全局位置進行估計.

針對現有全局式SfM算法中全局位置估計存在的不足,結合平行剛體理論、凸優化方法以及極線幾何理論,本文提出一種新的高效魯棒的全局位置估計方法.并且本文方法可以很好地融合于現有的全局式SfM算法流程中.本文內容結構如下:第1節簡單介紹了全局式SfM 算法.第2節和第3節是對相機全局位置估計方法的改進.第2節闡述了一種結合極線約束的相對平移方向估計算法.第3節引入平行剛體理論,闡述一種基于凸優化的魯棒性相機全局位置估計算法.第4節是實驗部分,使用8組公開數據集對本文算法測試并和相關典型算法進行比較.

1　 全局式SfM算法簡介

由于本文工作是在全局式SfM方法基礎上對其中的相機全局位置估計部分進行了改進,所以首先對全局式SfM算法進行簡要介紹.

全局式SfM一般包含以下5個步驟:

步驟1.圖像特征提取與匹配.

步驟2.相機相對位姿估計.

步驟3.相機全局旋轉估計

步驟4.相機全局位置估計.

步驟5.光束法平差(BA).

其中相機全局位置估計步驟包含相機相對平移方向估計和基于相對平移方向的全局位置解算兩部分.由于在全局式SfM處理過程中,只進行了一次BA優化,中間過程中沒有類似增量式方法的迭代BA處理,不能有效地剔除誤匹配的影響.誤匹配的存在會直接導致相機相對平移方向估計結果中的外點產生.而相機相對平移方向估計結果中存在的外點會直接影響相機全局位置估計的最終精度,甚至導致計算結果無法收斂.

因此增加相機全局位置估計方法對外點的魯棒性,提高估計結果的精度和穩定性可以從兩個方面考慮:減少誤匹配對相機相對平移估計過程的影響,削減相機相對平移方向估計結果中的外點,以及在相對平移方向估計結果存在外點的情況下進行相機全局位置的魯棒性估計.針對這兩方面,本文對全局式SfM中的相機全局位置估計方法做出以下兩點改進:首先提出一種新的基于極線約束的相機相對平移估計方法.然后引入平行剛體理論將相機全局位置估計問題轉換為一個適定性問題并提出一種基于凸優化的能收斂到全局最優的魯棒性相機位置估計方程.并且改進后的相機全局位置估計方法可以很好地融合到傳統的全局式SfM流程中,如圖1所示.圖1中的虛線框部分為本文所做的改進.

圖1　融合本文改進的全局式SfM算法流程圖Fig.1The processing pipeline of global SfM fusion our modifying

2　基于極線約束的相對平移方向估計

相對平移方向估計指的是對全局坐標系下相機之間相對平移方向的估計.全局式SfM算法中,相機相對平移方向的估計是相機全局位置估計的基礎,相對平移方向估計的結果直接影響到了后續的全局位置估計的精度.

通常,估計相對平移方向是通過對本質矩陣Eij分解獲得相對旋轉參數Rij和平移參數tij(這里的相對平移和旋轉是在相機坐標系下的).然后相對旋轉參數Rij估算出全局旋轉Ri,繼而據此解算出相對平移方向估計值γij=Ritij/||tij||.在誤匹配存在或者匹配點過少的情況下,利用這種方法估計出的相對平移方向通常和真值存在較大偏差.全局式SfM算法中沒有同增量式方法中一樣的迭代優化過程,所以誤匹配點存在并參與運算的問題無法避免,因此使用這種估計方法對全局式SfM 過程中相對平移方向進行估計通常不能獲得一個很精確的結果,當處理大規模、無序圖像集時這種情況表現得尤為明顯.

對此,本文提出一種基于極線約束的相對平移方向估計方法,旨在當存在圖像誤匹配情況時仍能保持估計結果的魯棒性(減少估計結果中存在的外點,提高第3節中的全局位置估計精度).算法流程如圖2所示.

圖2　本文改進的相對平移方向估計算法流程Fig.2The processing pipeline of relative translation estimation based on our modifying

全局旋轉的估計會在很大程度上影響到相對平移方向的估計精度.文獻[14]提出了一種高效、對外點魯棒的全局旋轉估計算法,其主要思想是首先利用一個速度相對較慢但是高魯棒的L1范數優化方程最小化相對旋轉誤差,然后使用一個速度較快的基于L2范數的優化方程對結果進行進一步的優化.因此,為了提高相對平移方向估計的精度,本文首先用文獻[14]方法估計出全局旋轉Ri,然后結合魯棒性的估計模型解算相對平移方向值.

如圖3所示的圖像I、J之間的本質矩陣為Eij=[t]×Rij(其中Rij=(ttj?ti)分別表示圖像i,j之間的相對旋轉和相對平移,[t]×為平移向量的叉乘).

圖3　圖像之間的極線關系Fig.3　Epipolar relationship between image pairs

圖像I,J的極線約束可表示為

令=(xi,yi)T表示三維點投影到第i個像平面上的平面坐標,則(3a)可改寫為

為了獲取由相對平移方向的線性估計模型,首先對原有的極線約束方程(3)進行變形,獲得表達式(4):

將式(4)推廣到k對匹配點,得到下面的基于L1范數的線性估計模型:

對式(5)進行迭代加權最小二乘法(Iteratively reweighted least squares,IRLS)[24]處理,可以獲取符號不確定的相對平移方向估計值

具體步驟為:

步驟1.設置初始權值和最大迭代次數;

步驟2.計算約束矩陣并對矩陣分解獲取相對平移方向估計值;

步驟3.計算殘差并更新權值;

步驟4. 判斷估計結果是否收斂,若不收斂,重復步驟2和3,否則結束運算.

在迭代過程中參與計算的每對匹配點的權值是根據每次迭代結果的殘差分配的,對殘差貢獻大的匹配點分配更小的權值,反之分配更大的權值.

式中,s表示平移方向的符號.重建出來的稀疏場景點必定位于相機平面前方這一既定事實是確定符號s正負的主要依據[25].具體方法是:首先令s=+1,然后計算出位于相機平面前方的場景點個數nf,如果大于所有場景點總數的1/k,則保持符號不變(一般k取2,因為場景點有一半位于相機平面前面足以說明s符號為正);否則,令s=?1.最終獲得相對平移方向估計值γij,從而實現相對平移方向的魯棒性估計.

相對于傳統的平移方向估計算法,本文不是直接利用本質矩陣分解得到Rij,tij進而獲得相對平移方向值,而是通過由極線約束變形構造一個線性的優化方程,直接確立相對平移方向同匹配點對pi,pj及絕對旋轉Ri之間的關系.這種估計模型基于L1范數的,并且通過計算過程中更新匹配點對對應的權值可以有效降低誤匹配對估計結果的影響,減少相對平移方向估計結果中的外點,提高后續相機全局位置估計的精度.

3　基于凸優化的魯棒性全局位置估計

在全局式SfM 算法流程中,相機全局位置估計是指在全局坐標系下對參與重建的圖像所對應的相機位置的估計.為了表述方便,文中使用對極圖Gl=(Vl,El)來表示圖像拍攝時相機之間的相對關系(相機全局位置和相對平移方向),其中頂點Vl={1,2,3,···,n}對應于n個相機在全局坐標系空間位置ti(1≤i≤n),頂點之間連線的方向(i,j)∈El對應的是全局坐標系下相機之間的相對平移方向γij.

為了獲取高效、魯棒、全局最優的相機全局位置估計值,本文構建了一個基于L1約束的凸優化線性估計模型(第3.2節).由于當需要估計的框架本身不唯一時(即出現如圖5(a)所示情形時,詳見第3.1節),直接利用凸優化估計模型進行解算并不能保證獲取唯一解.因此在將已知量代入模型進行未知參數解算之前還需要做一些預處理步驟.預處理步驟的目的在于將估計問題轉換為一個適定性問題.文獻[10,26]中提出的獲取三視圖間三焦張量的方法可以有效解決這種問題,但三焦張量的計算會消耗額外的時間并增加了后續位置估計模型的復雜度.本文基于平行剛體理論提出一種新的高效預處理方法.

圖4　相對平移方向和相機全局位置Fig.4　Relative translation direction and cameras′global position

圖5　平行剛體示例Fig.5　An example of parallel rigid

3.1　平行剛體

平行剛體理論在基于方位測量的(Bearingbased)傳感器網絡定位、機器人自主定位與導航、目標跟蹤等方面有很多應用[27?32].本文首次將其引入到全局式SfM算法的相機全局位置估計研究中.

針對相機位置的全局估計,首先考慮以下問題:已知相機之間的相對平移方向γij時,能否唯一確定所有相機的位置ti(1≤i≤n)(這里的唯一性不考慮全局的平移和縮放,如圖2所示)?當對極圖有什么樣的屬性時,可唯一確定相機位置?如果不能唯一確定相機的位置,是否可以從對極圖中提取出子圖,從而唯一確定所有相機的全局位置?

上述幾個問題符合平行剛體理論所研究的內容:已知圖G中所有邊的方向,當G是平行剛體時,能唯一確定圖中所有頂點的位置;當G不是平行剛體時,通過提取G中的最大平行剛體成分可唯一確定圖中所有頂點的位置.因此可將相機全局位置估計同平行剛體理論有效結合起來,從而將相機全局位置估計轉換為一個適定性問題.

以下為確定平行剛體存在性的定理:

定理 1[28].已知圖G=(V,E),令(d?1)E表示E的d?1個備份,當且僅當非空集合D?(d?1)E且存在|D|=d|V|?(d?1)時G為平行剛體.D的子集D′?D滿足下面的不等式:

式中,V(D′)表示D′所對應的頂點,|?|表示?中元素的個數.

對于定理1,可以結合圖5進行理解.當d=2時,即在二維情形下,此時D=E,要滿足定理1中的情形必須存在|D|=2|V|?3.圖5(a)中|D|=6,|V|=5顯然不滿足條件.圖5(b)為從圖5(a)中提取出的子圖|D|=3,|V|=3,滿足該條件.圖5(c)中|D|=7,|V|=5,滿足該條件.所以當d=2時,圖5(b)和(c)中描述的情形為平行剛體,而圖5(a)則為非平行剛體.

平行剛體與解唯一的一致性還可以從圖5中直觀的理解,在圖5(a)中已知圖G=(V,E)中的頂點和頂點間連線的方向.對于圖5(a)中的情形可以獲得多個獨立的解,例如{t1,t2,t3,t4,t5}和{t1,t2,t3,}. 而圖 5(b) 和 (c) 中的情形只會得到唯一的解.

由定理1衍生了一系列檢測平行剛體的算法.文獻[33]介紹了一種時間復雜度為O(n2)的Pebble game變種算法檢測平行剛體是否存在以及文獻[34]介紹了一種算法用來從非平行剛體結構中提取出其中的最大平行剛體成分,其時間復雜度為多項式時間.

當無外點的情況下(相機相對平移方向觀測值均為真值),結合平行剛體理論和基本的位置估計模型(式(8))可準確地恢復相機的全局位置.但對于真實的圖像,外點是普遍存在的,尤其是面對大規模、無序圖像時(因為誤匹配難以避免).平行剛體理論應用于相機全局位置估計的意義在于將原本的估計問題轉換成一個適定性問題,消除由于待估計框架不唯一帶來的估計結果歧義性,保證相機位置估計的穩定性.

將平行剛體理論引入到全局式SfM 中,進行相機全局位置估計基本思路是首先確定對極圖Gl=(Vl,El)是否平行剛體,如果是則直接進行魯棒性的相機全局位置估計(第3.2節),否則提取出其中最大平行剛體成分(利用文獻[32]中算法),然后再進行相機全局位置的魯棒性估計.

3.2　魯棒性全局位置估計

當相對平移方向估計結果中無外點時,可以從對極圖Gl=(Vl,El)中提取出最大的平行剛體,然后通過下式精確恢復出相機全局位置.

式中,γij表示相機i,j之間的相對平移方向(相機相對平移方向的魯棒性估計見第2節),ti,tj表示相機i,j的全局位置.

然而由于外點的普遍存在,直接利用式(8)進行全局位置估計的結果通常與真值有很大偏差.如何在外點存在的情況下魯棒的估計相機全局位置是個很重要的問題,這也是本節探討的內容.

當已知相機i,j之間的相對平移方向觀測值為γ

ij,同真值之間的差值為εij時,對于每個γij滿足如下等式:為了誤差εij存在的情況下能快速魯棒估計出相機的全局位置,將式(9)改寫為如下線性形式:

式中,為了簡化計算、提高計算效率,令λij=||ti?tj||.且使用相機間的距離值誤差來代替相對平移方向誤差εij,最終組成一個由,ti,tj,λij,γij構成的線性方程.相機之間的距離誤差和相對平移方向誤差εij成線性關系(=?λijεij),所以最小化相對平移方向誤差εij的問題可以轉化為最小化相機間距離誤差的問題.為了提高對外點的魯棒性,本文基于L1范數約束對距離誤差進行最小化.

由此可以獲得如下的基于約束的估計模型:

式(11)中估計模型是非線性且非凸的,直接使用該模型進行相機全局位置的估計會存在解算復雜度高,求解困難的問題.因此舍棄非凸約束λij=||ti?tj||,將λij作為獨立的參數求解(此時λij表示的是對應于每個相機對的未知尺度因子).這種處理策略一方面可以將式(11)中估計模型線性化(這種線性化方法廣泛應用于相機全局位置估計過程中,文獻[10,17,20]等均采取這種策略直接將λij作為一個獨立的未知尺度因子,其中文獻[20]首次提出利用線性估計模型進行相機全局位置的估計).另一方面可以將式(11)中的估計模型轉換為具有凸屬性的估計模型.

通過上述舍棄非凸約束的策略將式(11)中估計模型從非凸非線性估計模型轉換為具有凸屬性的線性估計模型,能夠提高估計過程的效率和精度.如果使用原始的非凸非線性模型即使在數據量很小的情況下也會出現計算復雜度過高的問題.

在相機全局位置估計過程中有大量的多余觀測(Redundance data),根據式(11)可以列出多個同相機i相關的約束參與迭代解算(約束個數等于與i相關的相機對的總數,例如相機對i,j、i,j+k、i,j+n·,理論上最多可列N?1個約束,其中N為參與估計的相機總數).在這種情況下將λij作為一個獨立的未知尺度因子可以降低參數之間的耦合性,簡化計算,并不會降低最終估計的精度.

最終獲得如下基于L1約束的凸優化線性估計模型:

對于上述結構的凸優化估計模型,通常使用二次規劃(Quadratic programing,QP)求解.為了提高估計結果的魯棒性,本文結合迭代加權最小二乘(Iteratively reweighted least squares,IRLS)對模型進行求解.

IRLS主要思想是:對目標模型進行迭代求解,在每次迭代過程中更新觀測值權重.權重的大小取決于上一次迭代結果的殘差,對殘差貢獻小的觀測值給于更高的權重,反之更低.當應用于本節中相機全局位置估計問題時,如下式(13)所示.=0和λij≥c分別是為了消除

對殘差貢獻小的相對平移方向值觀測值給予更大的權重.這種方式可有效地提高算法對外點的魯棒性.

主要算法步驟如下:

步驟1.設置QP和IRLS的迭代次數以及初始權重.

步驟2.根據式(12)計算約束矩陣A.

步驟3.使用QP求解矩陣方程.

步驟4.計算殘差并更新權重.

步驟5.重復步驟4和5直至達到迭代次數的上限.

同文獻[10]方法相比,本文使用了基于L1范數而不是L∞范數的估計模型,對外點更具有魯棒性.同文獻[23]1DSfM方法相比,本文使用了線性的而不是非線性的優化方程,在計算效率方面更高,并且本文使用的是凸優化估計模型能夠保證收斂到全局最優,而1DSfM只能收斂到局部最優.

4　實驗

實驗數據為文獻[23]提供的8組公開圖像數據集.這8組數據都具有大規模、無序的特點.為了驗證本文算法的效率和精度,對這8組數據進行處理并同文獻[20,23]的實驗結果進行比較.下面給出實驗結果及結果分析

4.1　實驗結果

實驗結果分為兩部分,第一部分是全局位置估計精度的比較(見表1),第二部分是處理時間的比較(見表2),另外給出了利用本文算法對8組數據處理獲取的場景三維稀疏結構(圖11).

為了控制其他因素的影響,保證實驗所采用的特征提取與匹配、相對運動估計等算法同文獻[20,23]保持一致,采用文獻[23]給出的相對運動估計結果作為本文算法的輸入.為了保證公平性,程序只使用了單線程進行處理.

表1　本文方法同1DSfM、文獻[20]處理精度比較Table 1　Comparison of accuracy:our method、1DSfM and[20]

表2　本文方法同1DSfM、文獻[20]、Bundler處理時間比較Table 2　Comparison of efficiency:our method、1DSfM、Bundler and[20]

增量式Bundler方法[3]作為處理大規模無序圖像的經典算法,在相機位置估計精度方面比較可靠.因此,同文獻[23]一樣,為了對實驗結果的精度進行量化比較,使用Bundler的處理結果作為參考(該結果從文獻[23]給出的網站獲取),分別比較估計值同參考值的差值的平均值、中位數(采用了一種基于RANSAC(Random sample consensus)的絕對定位方法,將實驗結果對齊到參考框架中從而獲取平均值和中位數).選擇平均值和中位數作為比較量的原因在于:平均值反映的是全體數據的平均水平,平均值的大小易受極端值得影響,因此可以反映算法對外點的魯棒性;中位數反映的是全體數據的集中趨勢,不受少數極端值影響,中位數的大小可以反映估計結果的普遍精度.

表2中比較了本文方法同1DSFM、文獻[20]、及傳統的增量式Bundler方法的處理時間(單位為秒).表中TR表示絕對旋轉所需的時間,TO表示對相對平移方向進行優化所需時間,TS表示全局位置估計所需的時間,TBA表示進行BA所需的時間,∑表示各個階段時間的總和.

4.2　結果分析

數據處理精度方面,從表1可以看出,本文方法在BA優化之前的平均值比1DSfM方法經過BA優化后平均值更低,在本文方法經過BA優化后兩者的差距進一步擴大.其中Vienna和Alamo兩個數據的中位數更是相差了2E3、1E7倍(圖7,從圖6中也可以看出對于數據Alamo使用本文方法只有少量點偏離參考值相對較大).這表明了本文實驗結果中具有更少的偏離參考值的極端值,充分反映了本文方法對外點的魯棒性.并且同1DSfM相比,在BA優化前后本文方法都具有與前者近似或者更低的中位數(圖9和圖10).同文獻[20]相比,本文方法顯然具有更低的中位數(圖8).這表明了本文方法精度方面的可靠性.

圖6　相機全局位置散點圖(數據Vienna,相機個數821)Fig.6　Global location of cameras represented by scatter diagram

圖7　BA優化后本文同1DSfM實驗結果平均值比較圖Fig.7　Comparison result of mean between our method and 1DSfM after BA

圖8　BA優化后本文同文獻[20]實驗結果中位數比較圖Fig.8　Comparison result of median between our method and[20]after BA

圖9　BA優化前本文同1DSfM實驗結果中位數比較圖Fig.9　Comparison result of median between our method and 1DSfM before BA

數據處理的效率方面,從表2可以看出,相比較傳統的增量式方法,本文方法有6～10倍加速;相比1DSfM,具有接近于2倍的提速.對于大部分實驗數據,本文處理速度不低于文獻[20]方法.因此,本文的方法在處理效率上優于或者接近于現有的典型方法.

圖10　BA優化后本文同1DSfM實驗結果中位數比較圖Fig.10　Comparison result of median between our method and 1DSfM after BA

綜上,實驗結果表明:本文方法對外點具有更好的魯棒性,并且處理結果的普遍精度和處理效率都不低于典型方法,通過本文方法可以高效、魯棒地進行相機全局位置估計.

5　結論

針對現有全局式SfM 算法流程中的相機全局位置估計部分存在的不足,本文提出一種改進的相機全局位置估計方法.本文工作主要體現在兩個方面:1)結合極線約束,提出一種新的對誤匹配魯棒相對平移方向估計算法;2)引入平行剛體理論將全局位置估計轉換為一個適定性問題并提出一種基于約束的凸優化線性估計模型.實驗結果表明本文改進的相機全局位置估計方法對外點具有更好的魯棒性,并且在計算效率和估計結果的普遍精度方面也具有一定優勢.

圖11　利用本文算法對8組公開數據集處理獲取的場景三維稀疏結構Fig.11　The experimental result with 8 groups of datasets based on our method

在實驗過程中我們發現魯棒性BA對實驗結果也有很重要的影響,所以下一步的研究工作是嘗試將本文的估計方法和魯棒性BA結合以獲取更好的估計結果.

1 Triggs B,McLauchlan P,Hartley R I,Fitzgibbon A W.Bundle adjustment–a modern synthesis.Vision Algorithms:Theory and Practice:Lecture Notes in Computer Science.Berlin,Heidelberg:Springer,1999.298?372

2 Zhang Z Y,Shan Y.Incremental Motion Estimation Through Local Bundle Adjustment.Technical Report MSRTR-01-54,Microsoft Research,Redmond,WA,2001.

3 Snavely N,Seitz S M,Szeliski R.Photo tourism:exploring photo collections in 3D.ACM Transactions on Graphics,2006,25(3):835?846

4 Snavely N,Seitz S M,Szeliski R.Skeletal graphs for efficient structure from motion.In:Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition.Anchorage,USA:IEEE,2008.1?8

5 Havlena M,Torii A,Knopp J,Pajdlat.Randomized structure from motion based on atomic 3D models from camera triplets.In:Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami,USA:IEEE,2009.2874?2881

6 Furukawa Y,Curless B,Seitz S M,Szeliski R.Towards internet-scale multi-view stereo.In:Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco,USA:IEEE,2010.1434?1441

7 Sinha S N,Steedly D,Szeliski R.A multi-stage linear approach to structure from motion.In:Proceedings of the 11th European Conference on Trends and Topics in Computer Vision.Berlin,Heidelberg:Springer,2010.267?281

8 Kneip L,Chli M,Siegwart R Y.Robust real-time visual odometry with a single camera and an IMU.In:Proceedings of the 22nd British Machine Vision Conference.Scotland,UK:BMVA,2011.

9 Tomasi C,Kanadet.Shape and motion from image streams under orthography:a factorization method.International Journal of Computer Vision,1992,9(2):137?154

10 Moulon P,Monasse P,Marlet R.Global fusion of relative motions for robust,accurate and scalable structure from motion.In:Proceedings of the 2013 IEEE International Conference on Computer Vision.Sydney,AU:IEEE,2013.3248?3255

11 Govindu V M.Lie-algebraic averaging for globally consistent motion estimation.In:Proceedings of the 2004 IEEE Conference on Computer Vision and Pattern Recognition.Washington,USA:IEEE,2004.684?691

12 Martinec D,Pajdlat.Robust rotation and translation estimation in multiview reconstruction.In:Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition.Minnesota,USA:IEEE,2007.1?8

13 Hartley R,Aftab K,Trumpf J.L1 rotation averaging using the Weiszfeld algorithm.In:Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Providence,USA:IEEE,2011.3041?3048

14 Fredriksson J,Olsson C.Simultaneous multiple rotation averaging using lagrangian duality.In:Proceedings of the 11th Asian Conference on Computer Vision.Berlin,Heidelberg:Springer,2012.245?258

15 Chatterjee A,Govindu V M.Efficient and robust large-scale rotation averaging.In:Proceedings of the 2013 IEEE International Conference on Computer Vision.Sydney,AU:IEEE,2013.521?528

16 Brand M,Antone M,Teller S.Spectral solution of largescale extrinsic camera calibration as a graph embedding problem.In:Proceedings of the 8th European Conference on Computer Vision.Berlin,Heidelberg:Springer,2004.262?273

17 Arie-Nachimson M,Kovalsky S Z,Kemelmacher-Shlizerman

I,Singer A,Basri R.Global motion estimation from point matches.In:Proceedings of the 2nd International Conference on 3D Imaging,Modeling,Processing,Visualization and Transmission.Zurich,Switzerland:IEEE,2012.81?88

18 Sim K,Hartley R.Recovering camera motion usingL∞minimization.In:Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.New York,NY,USA:IEEE,2006.1230?1237

19 Kahl F,Hartley R.Multiple-view geometry under theL∞-norm.IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(9):1603?1617

20 Govindu V M.Combining two-view constraints for motion estimation.In:Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Kauai,HI,USA:IEEE,2001.218?225

21 Tron R,Vidal R.Distributed image-based 3-D localization of camera sensor networks.In:Proceedings of the 48th IEEE Conference on Decision and Control.Shanghai,China:IEEE,2009.901?908

22 Lih D.Multi-view structure computation without explicitly estimating motion.In:Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco,CA:IEEE,2010.2777?2784

23 Wilson K,Snavely N.Robust global translations with 1DSfM.In:Proceedings of the 13th European Conference on Computer Vision.Berlin,Heidelberg:Springer,2014.61?75 24 Daubechies I,Devore R,Fornasier M,G¨unt¨urk C S.Iteratively reweighted least squares minimization for sparse recovery.Communications on Pure and Applied Mathematics,2010,63(1):1?38

25 Andrew A M.Multiple view geometry in computer vision.Kybernetes,2001,30(9?10):1333?1341

26 Jiang N J,Cui Z P,Tan P.A global linear method for camera pose registration.In:Proceedings of the 2013 IEEE Conference on Computer Vision.Sydney,NSW:IEEE,2013.481?488

27 Whiteley W.A matroid on hypergraphs,with applications in scene analysis and geometry.Discrete&Computational Geometry,1989,4(1):75?95

28 Whiteley W.Parallel redrawing of con fi gurations in 3-space.1986.

29 Servatius B,Whiteley W.Constraining plane con fi gurations in computer-aided design:combinatorics of directions and lengths.SIAM Journal on Discrete Mathematics,1999,12(1):136?153

30 Erent,Whiteley W,Belhumeur P N.Using angle of arrival(bearing)information in network localization.In:Proceedings of the 45th IEEE Conference on Decision and Control.San Diego,CA:IEEE,2006.4676?4681

31 Erent,Whiteley W,Morse A S,Belhumeur P N,Anderson B D O.Sensor and network topologies of formations with direction,bearing,and angle information between agents.In:Proceedings of the 42nd IEEE Conference on Decision and Control.Maui,HI:IEEE,2003.3064?3069

32 Jackson B,Jord′ant.Graph theoretic techniques in the analysis of uniquely localizable sensor networks.2009.

33 JacobsDJ,HendricksonB.Analgorithmfortwodimensional rigidity percolation:the pebble game.Journal of Computational Physics,1997,137(2):346?365

34 Kennedy R,Daniilidis K,Naroditsky O,Taylor C J.Identifying maximal rigid components in bearing-based localization.In:Proceedings of the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems.Vilamoura-Algarve,Portugal:IEEE,2012.194?201