無序多視角點云的自主配準方法

徐思雨,祝繼華,姜祖濤,郭瑞,李垚辰

(西安交通大學軟件學院,710049,西安)

點云配準問題是在計算機視覺[1-3]和移動機器人[4]等研究領域中的基礎問題。根據待配準點云數,該問題可分為雙視角和多視角點云配準兩種類型。

雙視角配準是多視角配準的基礎,其實質是通過定義相似性測度函數,并建立兩幀點云之間點的對應關系以計算最優的變換關系。Besl等提出了基于迭代求解思想的迭代最近點(ICP)算法[5],對于解決剛體配準問題,該方法具有精度高和速度快的特點,但它不能解決缺失點云配準問題且具有局部收斂性。為了解決缺失點云配準問題,Chetverikov等提出了裁剪ICP算法[6],該方法在原始ICP算法的基礎上,通過引入重疊百分比系數去除非重疊區域以準確地計算雙視角配準結果。為了解決局部收斂問題,粒子濾波[7]和遺傳算法[8]均被用于搜索全局最優的配準結果,但這類方法的計算量較大。有的學者提出一些基于特征匹配的雙視角配準方法[9-10],此類方法通過從待配準的點云中提取并匹配特征,以快速計算雙視角點云之間的剛體變換關系。

給定多視角點云集,多視角點云配準的目標是計算各點云和基準點云之間的剛體變換關系。與雙視角點云配準問題相比,多視角點云配準問題需要求解的參數較多。解決此問題最簡單的方法是順序配準法[11],該方法通過不斷地將兩幀點云進行配準再合并以實現多視角配準結果,此方法雖然簡單但存在累積誤差問題。為了消除累積誤差,Zhu等提出逐步求精的配準方法,該方法順序遍歷基準幀以外的各幀點云,并將所遍歷的點云與其他點云構造的模型進行雙視角配準,以修正單幀點云的多視角配準參數[12];Govindu等提出了基于運動平均算法的多視角配準方法[13],該方法將所有可獲得的雙視角配準結果作為輸入,利用基于李群的運動平均算法計算多視角配準參數;Guo等給雙視角配準結果賦予代表可靠度的權值,并提出了權重運動平均方法,以提高多視角配準結果的精度[14];Arrigoni等提出了基于低秩稀疏矩陣分解的多視角配準方法[15],該方法利用雙視角配準結果構造矩陣,并利用低秩稀疏矩陣分解方法近似得到低秩矩陣,以便恢復獲得多視角點云配準結果;Georgios等將多視角配準問題轉化成聚類問題,通過利用期望最大化(EM)算法估算高斯混合模型(GMM),以實現聚類及多視角配準參數的計算[16],但該方法需要求解的參數較多,故算法的效率較低。

雖然前述方法可獲得較好的多視角點云配準結果,但它們需要外界提供可靠的多視角配準初始值。為了獲得多視角配準的初始值,Daniel等提出了全自主的多視角點云配準方法[17],該方法首先計算所有雙視角配準結果,然后通過設計相容性準則找出可靠的雙視角配準結果以分析獲得多視角配準結果,由于該方法需要計算點云集中所有雙視角點云的配準結果,故效率較低。Zhu等提出了基于生成樹的多視角點云配準方法[18],該方法基于廣度優先的搜索方式,利用所設計的判定準則尋找可靠的雙視角配準結果創建生成樹以獲得多視角配準結果,由于大部分雙視角點云之間的重疊百分比(點云重疊區域的點數占總點數的比值)較低,需進行多次雙視角配準才能創建出完整的生成樹,故基于生成樹方法的效率有待進一步提高。

針對多視角點云配準問題,本文提出了基于特征匹配的多視角點云全局配準方法。該方法選取可靠的特征描述子快速實現雙視角配準;設計合理的判定準則判別雙視角配準結果的可靠性;提出有效的模型擴展方法,利用可靠雙視角配準結果進行點云模型的擴展。通過采用交替地執行雙視角配準、配準結果判別和模型擴展的方式,實現無序多視角點云的全局配準。

1 裁剪ICP算法

給定具有非重疊區域的雙視角點云,分別包含Np個點的數據點云P和Nq個點的模型點云Q其中pi表示P中的第i個點,qj表示Q中第j個點。設Px表示重疊區域的數據點云上的點所組成的子集,重疊百分比x定義為和Np的比值,其中表示子集Px所包含的點數。定義裁剪均方誤差

(1)

式中:R與t表示剛體變換中的旋轉矩陣和平移變量;(pi,qc(i))表示模型點云和數據點云在重疊區域的具有對應關系的點對。雙視角配準問題可表示為如下的最小化問題

(2)

式中λ是預設的參數,λ=2。

給定初始剛體變換(R0,t0),裁剪ICP算法采用交替迭代的思想求解最優的配準參數,且第k次迭代包含以下步驟。

步驟1基于當前剛體變換,建立點的對應關系

i=1,2,…,Np

(3)

步驟2根據當前點對關系,計算第k次迭代中的重疊百分比xk和子集Px

(4)

步驟3更新剛體變換關系

(5)

迭代執行步驟1～3,直到迭代步數達到預設的上限K或|ψk-ψk-1|<ε(ε為任意小的正數),即可停止迭代輸出最優的配準參數(R,t)。與原始ICP算法相似,裁剪ICP算法也具有局部收斂性,但是為獲得可靠的雙視角配準結果,需要外界提供較好的配準初始值。

圖1 無序多視角點云配準方法框架圖

2 無序多視角點云全局配準

為了實現無序多視角點云的全局配準,本文提出了如圖1所示的解決方法。該方法選定基準幀作為初始模型點云,順序遍歷點云集里的每一幀點云,然后利用雙視角配準方法將所遍歷的點云與模型點云進行配準,通過設計有效的判定準則,將判別出的可靠雙視角配準結果用于模型點云擴展,直到全部點云被加入擴展模型中。

2.1 基于特征匹配的雙視角配準

為了解決雙視角配準問題,已有各種局部收斂的方法。在給定配準初始值時,這些方法可以計算出兩個點云之間最優的剛體變換。然而,在無序多視角點云配準問題中,雙視角配準初值是未知的,因此需要可實現全局配準的雙視角配準方法。

Lei等提出了基于特征匹配的雙視角全局配準方法[10],該方法先對原始點云進行降采樣,以降采樣獲得的每個點為中心定義4個具有不同半徑的圓球,接著利用球內所包含的原始點云,計算該點的4組法向量和特征值向量,并用9維的特征值差向量D和12維的法向量N作為特征描述子。由于特征值差向量具有旋轉不變形性,可基于歐氏距離最近的原則建立簡單的特征對應關系,隨后將每個特征對作為種子匹配對,通過檢驗其他特征點與種子特征點之間的距離差和法向量夾角,選取兼容的特征匹配對形成特征匹配對集。為了消除錯誤的匹配對,可進一步利用隨機一致性算法對匹配對集中的特征對進行篩選,選出可靠特征對確定雙視角配準結果。由于種子匹配對不一定可靠,因此需要遍歷全部種子匹配對,如果利用該種子點匹配對所找的相容特征匹配對數較少,則直接丟棄,否則需要采用隨機一致性算法進行后續處理以確定雙視角配準結果。最后,比較所有配準結果所對應的裁剪均方誤差選出最可靠的雙視角配準結果。

與原始點云相比,降采樣后的特征點數較少,根據特征點所計算出的雙視角配準結果精度有限。為提高配準結果精度,本文利用裁剪ICP算法對基于特征點匹配所求出的雙視角配準結果進行了修正,以獲得更好的雙視角配準結果。

2.2 配準結果評判的設計

為了獲得精確的擴展模型,需要選取可靠的雙視角配準結果,為此必須設計有效的判定準則。

在多視角點云配準問題中,每對點云之間存在非重疊區域甚至無重疊區域。對于重疊百分比較高的雙視角點云,裁剪ICP算法可準確地找出兩點云之間的重疊區域,并計算出可靠的配準參數;對于具有低重疊百分比或無重疊區域的雙視角點云,裁剪ICP算法會找出虛假的重疊區域,并計算出不可靠的配準參數。圖2給出了具有不同重疊百分比的雙視角點云配準結果,其中圖2a所示的雙視角點云具有較高的重疊百分比,圖2b所示的雙視角點云分別來源于兔子模型的正反面,具有較低的重疊百分比。由圖2可知,可靠的配準結果使得位于重疊區域的點對誤差距離較小,而不可靠的配準結果造成虛假重疊區域的點對誤差距離較大,因此可將裁剪ICP算法所確定的重疊區域內的點對誤差,即裁剪均方誤差E,作為判定配準結果可靠性的依據。

(a)可靠的配準結果 (b)不可靠的配準結果

對于相同的數據點云和配準結果,裁剪均方誤差會受模型點云點密度的影響。圖3給出了模型點云點密度對裁剪均方誤差的影響。由圖3可知,低密度的模型點云將導致裁剪均方誤差增大,高密度的模型點云有利于降低裁剪均方誤差。根據裁剪均方誤差受模型點云點密度之間影響的現象,本文給出如下雙視角配準結果的判定準則

(c) 可靠的配準結果 (d) 不可靠的配準結果的橫截面圖 的橫截面圖圖2 雙視角配準結果的橫截面圖

(6)

式中:E為雙視角配準結果所對應的裁剪均方誤差;dM為模型點云的平均密度;a為設定的常數。如果E滿足式(6),則可判定雙視角配準結果較可靠,否則為不可靠。

為了改善判定準則,當獲得一部分可靠的多視角配準結果后,可將這些配準結果所對應的均方誤差的均值加入判定準則,即

E≤max(adM,bmE)

(7)

式中mE表示可靠配準結果裁剪均方誤差E的平均值。參數a和b的選取將在實驗部分進行討論。

(a)低分辨率模型

(b)高分辨率模型圖3 模型點云的分辨率對裁剪均方誤差的影響

2.3 點云模型的擴展

根據本文所設計的判定準則可判別雙視角配準結果是否可靠,對于可靠的雙視角配準結果則需要進行模型擴展。由于模型形狀的點云密度會影響后續雙視角配準的裁剪均方誤差,為了保證判定準則的有效性,需要盡量保持模型點云密度的恒定性。為此,本文設計如圖4所示的模型擴展方法。

利用雙視角結果(R,t)將數據點云進行變換,以獲得變換后的數據點云P′

P′{Rpi+t

(8)

(a)擴展前建立的點對關系

(b)模型擴展結果圖4 模型擴展方法示意圖

可將模型點云和變換后的數據點云分解為兩部分

(9)

Q′=A∪F∪B

(10)

(11)

模型擴展時,對均勻采樣所獲得的特征同樣需要進行擴展。本文所采用的特征包含特征點和特征描述兩部分,其中特征描述分為法向量N和特征值差向量D兩部分。在進行特征擴展時,可利用裁剪ICP算法建立重疊區域特征點的對應關系,并采用處理點云的方式確定新特征的特征點。由于特征值差向量具有旋轉不變性,故新特征值差向量可由對應特征對的特征值差向量的均值所代替,即

(12)

而法向量不具有旋轉不變形性,故在求平均法向量前,需要對數據點云中特征點的法向量進行旋轉,然后再求平均

(13)

其中旋轉矩陣R由雙視角配準結果所確定。

與直接合并法相比,本文所設計的模型擴展法可有效地減少重疊區域的點云和特征的數目,從而有利于提高后續配準的效率。

2.4 多視角點云配準算法的實現

根據上述描述,結合圖1的循環過程,可給出如下無序多視角點云全局配準方法。

步驟1從點云集里隨機選出基準幀作為模型點云。

步驟2順序遍歷點云集的剩余點云,如點云集非空則轉至步驟3;否則,轉至步驟5。

步驟3視所遍歷點云Pi為數據點云,利用2.1節中的方法計算(Ri,ti)和Ex,i。

步驟4根據式(7)判定(Ri,ti)的可靠性,如滿足條件,轉至步驟5;否則,轉至步驟2。

步驟5從點云集里取出Pi,利用2.3節中的方法進行模型擴展,并更新平均值mE。

給定無序多視角點云集,利用本文方法可快速實現多視角點云配準。一般情況下,默認將點云集里的第一幀選為基準幀。

3 多視角點云配準實驗結果

3.1 參數選取

本文方法所包含的兩個自由參數α和b的取值將影響本文方法的性能。為了選取合理的值,在Bunny和Armadillo數據集上對本文方法進行了測試,采用人工的方式挑選出了可靠的雙視角配準結果,并在圖5中記錄了每次獲得可靠雙視角配準結果所對應的裁剪均方誤差E和模型點云的平均密度dM。

(a)Bunny數據集

(b)Armadillo數據集圖5 可靠雙視角配準結果所對應的E和dM

如圖5所示,對于可靠的雙視角配準結果,點云密度dM一般小于裁剪均方誤差E,且可靠雙視角配準結果所對應的E波動比較大,為了確保配準結果判定準則的有效性,a和b的取值應該大于1。理論上,a和b越大越能確保挑選出全部可靠的雙視角配準結果,但過大的a和b會引入不可靠的雙視角配準結果,從而導致多視角點云配準結果的失敗。通常情況下,不可靠的雙視角點云配準結果是由低重疊百分比而導致的。如將a和b設置得較小,本文方法會將一部分點云的雙視角配準結果誤判為不可靠,但隨著模型點云的不斷擴展,待配準點云的重疊百分比將不斷增加,前一次判定為配準失敗的點云,下一次配準所獲得的E將會變小,從而實現正確的判定,即較小的a和b僅降低了本文方法的效率,但較大的a和b值將降低本文方法的可靠性。鑒于此,可將參數a和b分別設置為a=2和b=1.5,以確保算法的可靠性。

3.2 配準算法的精度和效率

給定一組無序多視角點云,可以利用不同的多視角配準方法進行配準并進行性能對比。圖6給出了不同方法在各個測試數據集上的效率對比結果,表1給出了不同方法在各個測試數據集上的精度對比結果,其中黑體數值代表最佳結果。為了進一步對比各種配準方法的精度,圖7以橫截面形式給出了各種方法關于Dragon和Buddha數據集的配準結果。

(a)雙視角配準次數

(b)程序運行時間圖6 不同方法在4個測試數據集上的效率對比結果

由圖6a可知,本文方法需要執行的雙視角配準次數最少,算法效率最高;SurfC方法需要執行的雙視角配準次數最多,算法效率最低。為了實現多視角全局配準,SurfC方法對點云集里所有的點云對進行雙視角配準,并利用兼容性檢測出可靠的雙視角配準結果,以分析多視角配準結果。由于該方法需要執行雙視角配準的次數最多,因此程序運行時間最長。SpanT方法采用深度優先的方式,通過執行雙視角配準和尋找可靠的雙視角配準結果創建完整的生成樹。通常,雙視角點云的重疊百分比影響其配準結果的可靠性,高重疊百分比的點云更容易獲得可靠的配準結果。

在無序多視角點云集里,只有一部分點云具有高重疊百分比。為了創建完整的生成樹,SpanT方法需要執行的雙視角配準的次數較多,算法的效率較差。除執行雙視角配準和尋找可靠雙視角配準結果之外,本文方法引入了模型點云擴展步驟,利用可靠雙視角配準結果進行模型擴展,可擴大模型點云所覆蓋的區域,增加待配準雙視角點云的重疊百分比,以減少雙視角點云配準的執行次數,因此本文方法具有較高的效率。

由表1可知,本文方法配準精度最高,另外兩種方法的精度較低。由于3種方法都采用雙視角配準方法實現多視角配準,故均面臨累積誤差問題。其中SpanT和SurfC方法直接利用點云集里的原始點云對進行配準,通過不同的策略選取N-1組可靠的雙視角配準結果計算多視角配準參數。通常情況下,雙視角配準結果的精度受雙視角點云重疊百分比的影響,且重疊百分比越低,配準精度越差。在多視角點云集中,許多原始點云對之間的重疊區域較少,對應的雙視角配準結果精度有限,隨著點云數的增加,多視角配準結果的累計誤差將不斷增大,從而導致SpanT和SurfC方法配準結果的精度變低。雖然本文方法也利用雙視角配準結果實現多視角配準,但待配準的模型點云并不是點云集里的原始點云,而是不斷擴展的點云。與原始點云相比,擴展后的模型點云可增加待配準的雙視角點云重疊百分比,提高雙視角配準結果的精度,從而減少多視角配準結果的累積誤差,因此本文方法可獲得最高精度的多視角配準結果。

表1 不同方法在各個測試數據集上的誤差對比結果

(a)輸入數據(b)重建模型(c)SurfC方法(d)SpanT方法(e)本文方法圖7 以橫截面形式表示的配準結果對比

3.3 配準算法的魯棒性

以Bunny數據集為實驗對象,通過調整點云順序測試所本文提出的多視角配準方法的可靠性,并與另外兩種方法進行對比。表2給出了不同順序下的Bunny數據集的配準結果。由表2可知,3種多視角配準方法對于點云的順序都不敏感,即具有較好的可靠性。為了實現多視角配準,3種方法都設計了相應的準則,以確定可靠的雙視角配準結果計算多視角配準參數。即使調整了點云順序,這些方法仍可以選出可靠的雙視角配準結果以實現多視角配準。與其他兩種方法相似,本文方法對點云順序具有較好的可靠性,是最佳的結果。

表2 不同方法關于Bunny數據集在不同順序下的測試結果

4 結 論

針對無序多視角點云的配準問題,本文提出了基于特征匹配的全局配準方法,采用合理的特征描述算子實現雙視角配準,并設計了判斷雙視角配準結果可靠性的準則,挑選出可靠的雙視角配準結果,用于擴展模型點云。為實現多視角配準,該方法需要交替地執行雙視角配準、配準結果判別和模型點云擴展,直到所有點云被擴展至模型點云。在斯坦福大學圖形學實驗室的公開數據集上的實驗結果表明,與現有的多視角配準方法相比,本文方法具有較高的精度和效率。