復(fù)雜型面約束的點(diǎn)云配準(zhǔn)序列確定方法

林 偉，孫殿柱，李延瑞，沈江華

1(山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255049)2(西安交通大學(xué) 機(jī)械工程學(xué)院，西安 710049)

E-mail：1578964766@qq.com

1 引 言

由于光學(xué)三維掃描設(shè)備的限制，每次掃描只能獲取被測物體一個視角的掃描數(shù)據(jù)，為得到完整的數(shù)據(jù)模型，需要對被測物體進(jìn)行多次掃描，然后將掃描得到的多視角掃描數(shù)據(jù)進(jìn)行配準(zhǔn)[1]；配準(zhǔn)是后續(xù)曲面重建的基礎(chǔ)，也是逆向工程領(lǐng)域的研究重點(diǎn)和難點(diǎn).

現(xiàn)有多視角掃描數(shù)據(jù)的配準(zhǔn)方法主要為順序配準(zhǔn)，即按照掃描順序?qū)⑺@得的掃描數(shù)據(jù)進(jìn)行逐次配準(zhǔn).其中最具有代表性的為Chen等[2]提出的全局剛性配準(zhǔn)算法，該方法首先將其中一個視角的掃描數(shù)據(jù)所在的坐標(biāo)系確定為基準(zhǔn)坐標(biāo)系，然后根據(jù)順序依次添加新的掃描數(shù)據(jù)進(jìn)行配準(zhǔn)，直到獲得完整的數(shù)據(jù)模型.Bergevin等[3]將掃描數(shù)據(jù)先進(jìn)行兩兩配準(zhǔn)，并迭代此過程直到配準(zhǔn)誤差被均勻分配到每次配準(zhǔn)過程中，避免了配準(zhǔn)誤差的累積但配準(zhǔn)效率大大降低.Mateo等[4]在通過期望最大化算法將多視圖點(diǎn)云配準(zhǔn)問題嵌入到貝葉斯框架中，同時考慮雙視圖的對應(yīng)關(guān)系及噪聲影響，最后進(jìn)行后驗(yàn)判斷，提高了配準(zhǔn)的整體精度及穩(wěn)健性.Evangelidis等[5]提出一種期望最大化算法，該方法將掃描數(shù)據(jù)中的每個點(diǎn)都視為從高斯混合模型中抽取的樣本點(diǎn)，從而將多視角掃描數(shù)據(jù)的配準(zhǔn)問題轉(zhuǎn)化為聚類分析問題，通過期望最大化方法計算計算掃描數(shù)據(jù)間的變換矩陣，提高了整體的配準(zhǔn)精度.徐思雨等[6]提出一種逐步求精的多視角掃描數(shù)據(jù)配準(zhǔn)方法，首先構(gòu)建初始配準(zhǔn)模型，然后按照雙視角配準(zhǔn)算法計算配準(zhǔn)參數(shù)并調(diào)整配準(zhǔn)模型，以便求解后續(xù)配準(zhǔn)參數(shù)，通過迭代求解配準(zhǔn)參數(shù)并調(diào)整配準(zhǔn)模型可最終實(shí)現(xiàn)全局配準(zhǔn).

隨著三維掃描設(shè)備精度的提高，單次掃描所獲得點(diǎn)云的密度越來越大，點(diǎn)云數(shù)據(jù)量急劇增多，利用順序配準(zhǔn)不但配準(zhǔn)效率較低且會產(chǎn)生誤差累計現(xiàn)象，嚴(yán)重影響整體配準(zhǔn)精度.因此，為實(shí)現(xiàn)大數(shù)據(jù)量多視角點(diǎn)云的快速配準(zhǔn)，本文提出一種三維掃描系統(tǒng)中復(fù)雜型面約束的多視角點(diǎn)云配準(zhǔn)序列確定方法，通過主成分分析度量點(diǎn)云的局部形貌平坦程度，分割平坦區(qū)域點(diǎn)云并提取距離質(zhì)心最近點(diǎn)作為保留點(diǎn)進(jìn)行自適應(yīng)簡化；結(jié)合平坦區(qū)域子集的樣點(diǎn)規(guī)模及子集中所有樣點(diǎn)到擬合平面的偏差均值量化待配準(zhǔn)點(diǎn)云的形貌復(fù)雜度，并通過形貌復(fù)雜度確定配準(zhǔn)序列.實(shí)驗(yàn)結(jié)果表明，本文算法能夠在維持點(diǎn)云原始形貌的情況下有效簡化待配準(zhǔn)點(diǎn)云，在多視角點(diǎn)云配準(zhǔn)過程中可避免累積誤差的產(chǎn)生，有效提高多視角點(diǎn)云的整體配準(zhǔn)精度.

2 形貌自適應(yīng)聚類簡化

為保證點(diǎn)云配準(zhǔn)精度，對參與配準(zhǔn)的任一點(diǎn)云P的簡化應(yīng)當(dāng)在盡量維持其原始形貌的前提下進(jìn)行.如果能夠?qū)分割為足夠多的子集，且其中任一子集來自P上足夠平坦的子域，那么每個子集只需貢獻(xiàn)少量采樣點(diǎn)，由這些采樣點(diǎn)構(gòu)成的P′即可作為點(diǎn)云的保形簡化結(jié)果.對于點(diǎn)云P，設(shè)C={C1,C2,…,CK}為其分割結(jié)果，即Ci∈P，且Ci∩Cj=φ，i={1,2,…,K}，j={1,2,…,K}，i≠j，采用k均值聚類算法[7]可以獲得C，且能保證任一子集Ci來自P的一個子域.

對于P中的任意一點(diǎn)xi，利用k均值聚類算法將其歸類到任意子集的過程可表示為i=A(xi).要保證xi會被正確的歸類到Ck中而不是其他的子集，需要衡量任意兩個點(diǎn)xi與xj的相異度.d(xi,xj).d(xi,xj)的值越大，表示點(diǎn)xi與xj越相異，反之則表示二者越相似.若xi與Ck中所有點(diǎn)的相異度的總和小于其他子集，便可以斷定xi屬于子集Ck.將P分割為{C1,C2,…,CK}的過程，本質(zhì)上是令函數(shù)：

(1)

最小化，即令每個子集內(nèi)的點(diǎn)之間的相異度之和最小.A(xi)定義為：

(2)

其中ck為Ck的中心點(diǎn)即Ck中所有點(diǎn)的均值點(diǎn).

Ck在原曲面上對應(yīng)區(qū)域的平坦程度可基于主元分析法[8]予以量化.設(shè)Ck={xi|i=1,2,…,ni}，則構(gòu)造Ck的協(xié)方差矩陣為：

(3)

(4)

對C(Ck)進(jìn)行特征值分解：

(5)

設(shè)最小特征值為λ1，對應(yīng)的特征向量v1即為Ck的擬合平面的法向量，λ1為Ck中的樣點(diǎn)在v1方向上的偏離程度，因此可用λ1來度量Ck的平坦程度，將其定義為平坦度.顯然，可通過設(shè)定平坦度閾值ζ來判定Ck的形貌平坦與否，即若λ1<ζ，可將Ck的形貌視為平坦，否則為非平坦.因此，基于ζ可實(shí)現(xiàn)P中平坦區(qū)域與特征區(qū)域的劃分.

若P的分割結(jié)果中存在子集Ck，該子集在原曲面上對應(yīng)區(qū)域的平坦度不足，即Ck所對應(yīng)λ1>ζ，可繼續(xù)采用k均值聚類算法對Ck進(jìn)行分割.由此對P可形成一個遞歸分割過程，使得最終所得分割結(jié)果中任何一個子集在原曲面上對應(yīng)區(qū)域的平坦度都滿足要求，這種遞歸分割方法稱為多層形貌分割.

1)輸入待簡化數(shù)據(jù)P.

2)對P進(jìn)行聚類數(shù)目為2的k均值聚類直到聚類誤差平方和E收斂，獲得C1={C1,C2}.

3)k←1，r←1.

4)根據(jù)式(3)-式(5)計算Ck的平坦度λ1.

5)當(dāng)λ1<ζ跳過，當(dāng)λ1≥ζ時，則將Ck作為輸入數(shù)據(jù)，重復(fù)步驟2)，獲得Cr+1.

6)k←k+1.

7)重復(fù)步驟4)-步驟6)，直至k=2.

8)r←r+1.

9)重復(fù)步驟4)-步驟8)，直到所有子集均有λ1<ζ，獲得二叉樹結(jié)構(gòu)的多層形貌分割域F.

10)對于最底層葉結(jié)點(diǎn)子集計算質(zhì)心并析取距離質(zhì)心最近點(diǎn)作為保留點(diǎn)，合并保留點(diǎn)得到P的簡化點(diǎn)集P′.

步驟2)中的聚類誤差平方和可用以下函數(shù)度量：

(6)

其中xij表示第k個子集的第j個點(diǎn)，ck為Ck的子集中心，nk為Ck中的樣點(diǎn)數(shù)量.

3 點(diǎn)云形貌復(fù)雜度

對于多視角點(diǎn)云{P1,P2,…,PN}，現(xiàn)有的初始配準(zhǔn)算法大多通過對P檢測特征點(diǎn)，然后通過計算相應(yīng)的特征描述符來匹配特征點(diǎn)進(jìn)行配準(zhǔn).例如Rusu等[9]提出的快速點(diǎn)特征直方圖(Fast Point Feature Histograms，F(xiàn)PFH)，即是通過計算特征點(diǎn)與其鄰域點(diǎn)之間的空間幾何關(guān)系，構(gòu)造一個33維的直方圖對特征點(diǎn)進(jìn)行描述，通過比較直方圖之間的差異完成特征點(diǎn)的匹配.而P′中的樣點(diǎn)大多位于特征區(qū)域，對于其中任一點(diǎn)xm，其構(gòu)造的特征描述符相較于平坦區(qū)域樣點(diǎn)更具有識別性，因此特征區(qū)域相較于平坦區(qū)域更有助于點(diǎn)云初始配準(zhǔn)，所以可通過量化待配準(zhǔn)點(diǎn)云所包含的特征情況來提高點(diǎn)云配準(zhǔn)效率.

設(shè)F={C1,C2,…,Cm}為待配準(zhǔn)點(diǎn)云P的多層形貌分割域.P包含越多特征，其形貌越復(fù)雜，需要分割的次數(shù)越多，F(xiàn)的層數(shù)越大，其最下層數(shù)所對應(yīng)的葉結(jié)點(diǎn)中的樣點(diǎn)規(guī)模ni越小，因此ni在一定程度上可反映點(diǎn)云形貌復(fù)雜度.

(7)

計算P中全部樣點(diǎn)到擬合平面的偏差距離，則其偏差均值χ(P)可有效度量P的形貌復(fù)雜程度.

基于上述分析，定義點(diǎn)云形貌復(fù)雜度為φ，其計算公式為：

(8)

其中χ(P)為：

(9)

聯(lián)立以上方程可得：

(10)

點(diǎn)云復(fù)雜度φ綜合考慮了葉結(jié)點(diǎn)子集樣點(diǎn)規(guī)模ni和偏差均值χ(P)，對待配準(zhǔn)點(diǎn)云P完整形貌復(fù)雜度的表達(dá)更加的合理、準(zhǔn)確.

4 確定配準(zhǔn)序列

點(diǎn)云形貌復(fù)雜度較大的待配準(zhǔn)點(diǎn)云其形貌更為復(fù)雜，包含更多的特征，在初始配準(zhǔn)過程中可對特征點(diǎn)構(gòu)造高識別度的特征描述符，有利于保證配準(zhǔn)的正確性，不易陷入局部最優(yōu)，因此可根據(jù)φ值確定點(diǎn)云配準(zhǔn)序列.

1)輸入多視角點(diǎn)云{P1,P2,…,PN}，i←1.

4)i←i+1.

5)重復(fù)步驟3)-步驟4)，直至i=N.

5 實(shí)驗(yàn)分析

為驗(yàn)證本文算法的有效性，以下實(shí)驗(yàn)均在硬件配置為Inter(R)Xeon CPU 2.5GHz，4GB內(nèi)存，操作系統(tǒng)為GNU/Linux，測試程序?yàn)镃++的環(huán)境中進(jìn)行.實(shí)驗(yàn)數(shù)據(jù)采用dawei點(diǎn)云模型和train點(diǎn)云模型，其中dawei點(diǎn)云模型由12個視角點(diǎn)云組成，將其分別命名為D1-D12，train點(diǎn)云模型由9個視角點(diǎn)云組成，將其分別命名為T1-T9，如圖1所示.

本文算法在計算多視角點(diǎn)云形貌復(fù)雜度之前需對其進(jìn)行簡化[11]，以D1、T1為例，簡化結(jié)果如圖2所示.可以看出簡化后的點(diǎn)云特征區(qū)域樣本點(diǎn)相較于平坦區(qū)域更為密集，可在減少樣本點(diǎn)數(shù)量的同時有效維持原始形貌.

統(tǒng)計實(shí)驗(yàn)數(shù)據(jù)的形貌復(fù)雜度，其結(jié)果如表1所示.可以看出，在D1-D12中D11的形貌復(fù)雜度最大，在T1-T9中T4的形貌復(fù)雜度最大，因此分別將其作為第一輪配準(zhǔn)序列中的固定點(diǎn)云，并根據(jù)本文算法確定其配準(zhǔn)序列.

為驗(yàn)證本文算法的有效性，分別采用順序配準(zhǔn)算法、文獻(xiàn)[4]算法和本文算法進(jìn)行配準(zhǔn)，配準(zhǔn)精度如表2所示，其中均勻誤差表示相鄰兩視角誤差均值，首尾誤差表示第一固定點(diǎn)云與最后添加點(diǎn)云之間的誤差，配準(zhǔn)結(jié)果如圖3所示，可以看出，本文算法與順序配準(zhǔn)算法相比能夠有效降低首尾誤差[12，13]，與文獻(xiàn)[4]算法配準(zhǔn)精度類似，但由于本文使用簡化后的點(diǎn)云進(jìn)行配準(zhǔn)，可有效減少配準(zhǔn)過程中的計算量，因此配準(zhǔn)效率高于文獻(xiàn)[4]算法.

圖1 實(shí)驗(yàn)數(shù)據(jù)Fig.1 Experimental data

圖2 簡化結(jié)果Fig.2 Simplified results

表1 實(shí)驗(yàn)數(shù)據(jù)形貌復(fù)雜度Table 1 Shape complexity of experimental data

表2 實(shí)驗(yàn)數(shù)據(jù)配準(zhǔn)精度(MSE/mm)Table 2 Registration accuracy of experimental data

調(diào)整實(shí)驗(yàn)數(shù)據(jù)樣點(diǎn)規(guī)模，統(tǒng)計配準(zhǔn)所用時間如圖4所示.可以看出，相較于順序配準(zhǔn)算法與文獻(xiàn)[4]算法，本文算法可有效縮短點(diǎn)云時間，且隨著實(shí)驗(yàn)數(shù)據(jù)中樣點(diǎn)數(shù)量的增加，與其他兩種配準(zhǔn)算法之間的差距越來越大.

圖3 配準(zhǔn)結(jié)果Fig.3 Registration results

圖4 配準(zhǔn)時間對比Fig.4 Registration time comparison

6 結(jié) 論

針對多視角點(diǎn)云采用順序序列配準(zhǔn)會產(chǎn)生較大的累計誤差的問題，提出一種形貌復(fù)雜度約束的點(diǎn)云配準(zhǔn)序列確定方法.該方法具有以下特點(diǎn)：

1)通過主成分分析判定點(diǎn)云形貌，基于形貌約束將點(diǎn)云進(jìn)行迭代分割并提取每個子集中距離質(zhì)心最近的樣點(diǎn)作為保留點(diǎn)，可實(shí)現(xiàn)點(diǎn)云的保形簡化.

2)對子集進(jìn)行擬合平面并計算子集中所有樣點(diǎn)到平面的偏差均值，結(jié)合子集樣點(diǎn)規(guī)模計算點(diǎn)云的形貌復(fù)雜度，可有效刻畫待配準(zhǔn)點(diǎn)云的整體形貌的復(fù)雜程度.

3)基于待配準(zhǔn)點(diǎn)云的形貌復(fù)雜度確定固定點(diǎn)云及浮動點(diǎn)云，進(jìn)而確定點(diǎn)云配準(zhǔn)序列，可將配準(zhǔn)誤差分布于每輪配準(zhǔn)之中，避免了最終累計誤差的產(chǎn)生.