郭瑞科，王立，朱飛虎，吳云

北京控制工程研究所，北京 100190

?

空間非合作目標(biāo)的多視角點(diǎn)云配準(zhǔn)算法研究

郭瑞科，王立*，朱飛虎，吳云

北京控制工程研究所，北京 100190

為了提高相鄰視角間稀疏掃描點(diǎn)云數(shù)據(jù)配準(zhǔn)的速度和精度，實(shí)現(xiàn)多視角點(diǎn)云精確配準(zhǔn)，提出一種基于KD-Tree點(diǎn)云均勻采樣簡(jiǎn)化算法，并且對(duì)傳統(tǒng)四點(diǎn)算法(4-Points Congruent Sets Algorithm, 4PCS)中的閾值參數(shù)進(jìn)行了統(tǒng)一，確定了各誤差閾值參數(shù)和點(diǎn)云密度之間的關(guān)系，通過(guò)基于姿態(tài)校正的方法有效解決了對(duì)稱視角點(diǎn)云引起的誤配準(zhǔn)問(wèn)題。仿真結(jié)果表明，該方法能夠快速、有效地實(shí)現(xiàn)衛(wèi)星稀疏點(diǎn)云的配準(zhǔn)。

非合作目標(biāo)；多視角；點(diǎn)云數(shù)據(jù)；配準(zhǔn)；四點(diǎn)算法

空間非合作目標(biāo)的在軌服務(wù)技術(shù)可實(shí)現(xiàn)對(duì)目標(biāo)航天器的在軌維護(hù)、空間垃圾碎片清理、抓捕或破壞敵方軍事衛(wèi)星等，具有很高的民用意義和軍事價(jià)值。在這些在軌服務(wù)任務(wù)中，服務(wù)航天器在跟蹤、接近和抓捕目標(biāo)時(shí)，需要實(shí)現(xiàn)航天器和目標(biāo)間的相對(duì)位置和姿態(tài)測(cè)量。相比較于傳統(tǒng)的合作目標(biāo)，非合作目標(biāo)上沒(méi)有光標(biāo)線或者角反射器等配合標(biāo)志，無(wú)法提供顯著、可靠的參考信息，這就給非合作航天器的準(zhǔn)確位姿測(cè)量帶來(lái)了極大的挑戰(zhàn)。特別是對(duì)于完全未知的空間目標(biāo)，需要首先在軌建立三維模型，然后利用所重構(gòu)的三維模型實(shí)現(xiàn)六自由度位姿估計(jì)和特征識(shí)別。因而如何對(duì)未知目標(biāo)進(jìn)行三維重構(gòu)，便成為了非合作在軌服務(wù)的一項(xiàng)關(guān)鍵技術(shù)。

激光掃描敏感器通過(guò)獲取目標(biāo)表面的點(diǎn)云數(shù)據(jù)，得到目標(biāo)三維模型，具有精度高、不受光照影響的優(yōu)點(diǎn)。由于敏感器視場(chǎng)角的限制，要得到目標(biāo)完整的三維模型，需要從多個(gè)視角對(duì)目標(biāo)進(jìn)行掃描，將不同視角得到的點(diǎn)云數(shù)據(jù)配準(zhǔn)到同一坐標(biāo)系下，因而需要研究多視角點(diǎn)云的配準(zhǔn)。點(diǎn)云配準(zhǔn)一般包括全局配準(zhǔn)和精確配準(zhǔn)兩個(gè)步驟，全局配準(zhǔn)縮小兩片點(diǎn)云之間的旋轉(zhuǎn)和平移錯(cuò)位，為精確配準(zhǔn)提供比較好的初值。對(duì)于多視角點(diǎn)云數(shù)據(jù)的配準(zhǔn)，某些視角需要多次旋轉(zhuǎn)平移才能配準(zhǔn)到統(tǒng)一坐標(biāo)系下，實(shí)現(xiàn)整體配準(zhǔn)，進(jìn)而重構(gòu)出目標(biāo)點(diǎn)云模型。

Wolfson等[1]提出的幾何哈希算法，可以用于點(diǎn)云數(shù)據(jù)的全局配準(zhǔn)，但是需要建立哈希表，占用內(nèi)存空間比較大，不適合空間應(yīng)用。Rusu等[2]提出的FPFH基于局部幾何特征的全局配準(zhǔn)方法，計(jì)算速度快，但是依賴點(diǎn)云的鄰域特征，導(dǎo)致稀疏點(diǎn)云數(shù)據(jù)估計(jì)曲率等特征誤差較大。Guo等[3]提出一種外形生長(zhǎng)的多視角點(diǎn)云配準(zhǔn)算法，選擇一個(gè)種子外形，迭代地進(jìn)行兩兩點(diǎn)云配準(zhǔn)，進(jìn)而實(shí)現(xiàn)模型重構(gòu)，該算法過(guò)于依賴兩兩配準(zhǔn)的精度，運(yùn)算量較大。

本文針對(duì)空間目標(biāo)需要內(nèi)存占用小、宜使用稀疏點(diǎn)云進(jìn)行配準(zhǔn)的特點(diǎn)，采用基于改進(jìn)四點(diǎn)算法的全局配準(zhǔn)方法，具有速度快的優(yōu)點(diǎn)，可以得到滿足精度的全局配準(zhǔn)結(jié)果。將全局配準(zhǔn)的結(jié)果作為精確配準(zhǔn)的初值，保證收斂精度的同時(shí)，提高配準(zhǔn)的效率。通過(guò)引入航天器姿態(tài)連續(xù)變化的約束條件，可以有效處理對(duì)稱視角點(diǎn)云誤配準(zhǔn)的問(wèn)題,使用連續(xù)變換的方法實(shí)現(xiàn)多視角點(diǎn)云的配準(zhǔn)。

1　點(diǎn)云數(shù)據(jù)的簡(jiǎn)化

激光掃描敏感器的測(cè)量精度高，尤其是在近距離掃描時(shí)，采用高效的李薩茹掃描方式(圖1)，獲取的單幅掃描數(shù)據(jù)點(diǎn)數(shù)多達(dá)數(shù)萬(wàn)到數(shù)十萬(wàn)。這樣大的數(shù)據(jù)量對(duì)于星載計(jì)算機(jī)有限的存儲(chǔ)空間和計(jì)算能力帶來(lái)了比較大的挑戰(zhàn)。從圖1可以看到邊緣點(diǎn)云密度高于中間部分，而且點(diǎn)云都集中在掃描線上，因而并不是所有的點(diǎn)都可用于配準(zhǔn)。其中冗余的點(diǎn)云數(shù)據(jù)如果都參與配準(zhǔn)，不僅會(huì)降低計(jì)算速度，增加內(nèi)存使用，而且點(diǎn)越多，越難從中找到符合特征的點(diǎn)對(duì)，影響配準(zhǔn)的精度。

圖1　李薩茹掃描方式Fig.1　Lissajous scan pattern

為了解決上述問(wèn)題，必須對(duì)測(cè)量的點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，以提高計(jì)算速度，減少存儲(chǔ)空間，提高配準(zhǔn)精度等。考慮到所處理的對(duì)象為衛(wèi)星點(diǎn)云，在空間模型重建中對(duì)時(shí)效性要求較高，本文提出一種基于KD-Tree點(diǎn)云均勻采樣算法對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)。

KD-Tree是三維數(shù)據(jù)中常用的一種數(shù)據(jù)格式，可以快速實(shí)現(xiàn)K最近鄰域的搜索[4]。在基于KD-Tree點(diǎn)云均勻采樣算法中，首先利用KD-Tree對(duì)點(diǎn)云數(shù)據(jù)建立空間拓?fù)浣Y(jié)構(gòu)，搜索點(diǎn)集中每個(gè)點(diǎn)的K最近鄰域，計(jì)算該點(diǎn)與K個(gè)最近鄰點(diǎn)的重心，用該重心代替這點(diǎn)，最后對(duì)所得到的點(diǎn)集均勻采樣，可以得到簡(jiǎn)化的稀疏點(diǎn)云。

圖2是從一個(gè)視角掃描得到的單幅原始衛(wèi)星模型點(diǎn)云，包含10 171個(gè)數(shù)據(jù)點(diǎn)，采用上述簡(jiǎn)化算法，K取4，采樣率設(shè)置為7%。圖3是簡(jiǎn)化后的點(diǎn)云，數(shù)據(jù)點(diǎn)數(shù)為710，可以看到數(shù)據(jù)得到精簡(jiǎn)，衛(wèi)星模型的特征也可以比較好地保留。

圖2　原始點(diǎn)云Fig.2　Original point cloud

圖3　簡(jiǎn)化后的點(diǎn)云Fig.3　Simplified point cloud

2　基于改進(jìn)四點(diǎn)算法的全局配準(zhǔn)　 算法

對(duì)于兩片三維點(diǎn)云的配準(zhǔn)，至少需要從各自點(diǎn)云中選取對(duì)應(yīng)不共線的三點(diǎn)，才能計(jì)算出二者的剛體變換矩陣。若待配準(zhǔn)兩片點(diǎn)云P(Data數(shù)據(jù)集)、Q(Model數(shù)據(jù)集)分別有m、n個(gè)點(diǎn)，在P、Q中選取對(duì)應(yīng)的三點(diǎn)計(jì)算旋轉(zhuǎn)平移矩陣，時(shí)間復(fù)雜度可達(dá)O(m3n3)。Irani等[5]采用基于隨機(jī)采樣一致性(Random Sample Consensus，RANSAC)的方法配準(zhǔn)，可以降低復(fù)雜度到O(n3lg n)，然而對(duì)于空間應(yīng)用，時(shí)間復(fù)雜度還是太高?？紤]在P點(diǎn)云中選取更多的共面點(diǎn)(5個(gè)或者以上)，則在Q點(diǎn)云中能成功選擇到正確的對(duì)應(yīng)點(diǎn)集的概率急劇降低，難以實(shí)現(xiàn)配準(zhǔn)[6]。

四點(diǎn)算法(4-Points Congruent Sets Algorithm，4PCS)是Aiger等[7]于2008年提出的一種基于RANSAC法則的全局配準(zhǔn)算法，可成功用于三維點(diǎn)云數(shù)據(jù)的配準(zhǔn)，時(shí)間復(fù)雜度只有O(n2)。本文針對(duì)原始四點(diǎn)算法中閾值參數(shù)比較多的情況，通過(guò)點(diǎn)云密度對(duì)閾值參數(shù)進(jìn)行了統(tǒng)一，簡(jiǎn)化了多視角點(diǎn)云配準(zhǔn)時(shí)的閾值參數(shù)設(shè)置；針對(duì)該算法處理對(duì)稱點(diǎn)云時(shí)成功率低的問(wèn)題，提出了基于姿態(tài)連續(xù)變化來(lái)校正對(duì)稱引起誤配準(zhǔn)的方法，有效提高了點(diǎn)云配準(zhǔn)的成功率。

2.1四點(diǎn)算法

四點(diǎn)算法在每次的迭代中，在P數(shù)據(jù)集中隨機(jī)尋找不在同一條直線上的共面4點(diǎn)，根據(jù)共面4點(diǎn)的兩條對(duì)角線交點(diǎn)將線段所分的比例r1、r2在剛體變換中的不變性(見(jiàn)圖4)，在Q數(shù)據(jù)集中選取對(duì)應(yīng)的共面4點(diǎn)(見(jiàn)圖5)，這兩對(duì)共面4點(diǎn)組成一致共面4點(diǎn)集，利用該一致共面4點(diǎn)集可以計(jì)算出旋轉(zhuǎn)矩陣R和平移矩陣T。4點(diǎn)算法不需要計(jì)算復(fù)雜的幾何特征，速度快，對(duì)噪聲具有比較高的魯棒性。

圖4　P中所選的共面4點(diǎn)[7]Fig.4　Four (approximately) coplanar points extracted formP

圖5　Q中對(duì)應(yīng)的共面一致4點(diǎn)Fig.5　Affine invariant congruent 4 points extracted formQ

四點(diǎn)算法中，Q點(diǎn)集中候選點(diǎn)對(duì)可以用共面4點(diǎn)長(zhǎng)度來(lái)篩選：

(1)

式中：δ1為尋找近似長(zhǎng)度相等線段a′b′與ab的誤差閾值。根據(jù)不變量r1、r2可以確定可能的交點(diǎn)e′：

(2)

式中： q1、q2是從點(diǎn)集Q找到的長(zhǎng)度符合線段對(duì)應(yīng)的候選共面4點(diǎn)。近似相等交點(diǎn)所對(duì)應(yīng)的點(diǎn)對(duì)即組成Q點(diǎn)集中的共面一致4點(diǎn)。利用點(diǎn)集(a,b,c,d)和(a′,b′,c′,d′)可以計(jì)算對(duì)應(yīng)的歐氏變換矩陣，用所得到的歐氏變換矩陣作用與點(diǎn)集P，驗(yàn)證在一定閥值下，P點(diǎn)集中成功配準(zhǔn)到Q點(diǎn)集的點(diǎn)數(shù)目，即一致性度量。

2.2四點(diǎn)算法的閾值參數(shù)設(shè)置方法

文中所配準(zhǔn)的點(diǎn)云數(shù)據(jù)是從完全非合作目標(biāo)掃描所得到的，全局配準(zhǔn)中沒(méi)有點(diǎn)云數(shù)據(jù)的先驗(yàn)知識(shí)，同時(shí)四點(diǎn)算法中涉及的誤差閾值參數(shù)眾多，這給算法中的閾值參數(shù)設(shè)置帶來(lái)了挑戰(zhàn)。在軌模型重建中需要多次點(diǎn)云配準(zhǔn)，每次配準(zhǔn)的兩幅點(diǎn)云特征都有所差別，如果分別設(shè)定這些閾值參數(shù)，可能會(huì)費(fèi)時(shí)費(fèi)力，甚至?xí)?dǎo)致不能成功配準(zhǔn)。

點(diǎn)云數(shù)據(jù)密度是稀疏點(diǎn)云的關(guān)鍵幾何特征，待配準(zhǔn)點(diǎn)云的密度τ，本文通過(guò)計(jì)算點(diǎn)云中所有點(diǎn)K最近鄰域距離的平均值來(lái)確定，該值越小，表示點(diǎn)云密度越大，反之則越小。一般三維散亂點(diǎn)云的最近鄰域點(diǎn)數(shù)可設(shè)置為6，即前后左右上下6個(gè)方向，這樣可以比較好地保持點(diǎn)云的三維特征，準(zhǔn)確確定它的局部幾何特征。本文中待配準(zhǔn)的點(diǎn)云是經(jīng)過(guò)簡(jiǎn)化的衛(wèi)星點(diǎn)云，衛(wèi)星太陽(yáng)翼和本體部分以平面特征為主，因而最近鄰域點(diǎn)數(shù)設(shè)置為4，即只選取沿平面方向的4個(gè)點(diǎn)，能比較好地保留衛(wèi)星點(diǎn)云特征，準(zhǔn)確估計(jì)點(diǎn)云數(shù)據(jù)密度。本文通過(guò)確定點(diǎn)云密度與各誤差閾值參數(shù)的關(guān)系，對(duì)誤差閾值參數(shù)進(jìn)行了統(tǒng)一。

上述四點(diǎn)算法中涉及的參數(shù)有：在Q點(diǎn)集中篩選候選對(duì)應(yīng)點(diǎn)對(duì)時(shí)的誤差閾值δ1；選取近似相等交點(diǎn)時(shí)的誤差閾值，‖e1-e2‖<δ2；一致性度量時(shí)的距離誤差閾值δ3。

本文通過(guò)仿真試驗(yàn)確定了各誤差閾值δi與點(diǎn)云密度τ之間的關(guān)系，有效提高了配準(zhǔn)算法的穩(wěn)定性和自動(dòng)化程度：

(3)

2.3對(duì)稱視角的校正

對(duì)于衛(wèi)星等對(duì)稱性比較高的航天器，某些視角的點(diǎn)云是對(duì)稱的，配準(zhǔn)時(shí)會(huì)出現(xiàn)沿某個(gè)本體軸翻轉(zhuǎn)180°的情況，這就為正確配準(zhǔn)帶來(lái)了挑戰(zhàn)?？紤]到相鄰視角的點(diǎn)云姿態(tài)變換角度不會(huì)太大，根據(jù)配準(zhǔn)得到的旋轉(zhuǎn)矩陣可以計(jì)算出相鄰視角點(diǎn)云間的相對(duì)姿態(tài)，對(duì)于姿態(tài)角過(guò)大的情況進(jìn)行識(shí)別、校正，就可以有效解決對(duì)稱情況下配準(zhǔn)偏差的問(wèn)題。

多視角點(diǎn)云配準(zhǔn)中，每對(duì)相鄰視角點(diǎn)云之間都存在旋轉(zhuǎn)矩陣R，據(jù)此可以定義P數(shù)據(jù)集所在視角測(cè)量坐標(biāo)系相對(duì)Q數(shù)據(jù)集所在視角測(cè)量坐標(biāo)系的姿態(tài)。常用的姿態(tài)描述方式有歐拉軸/角式，有4個(gè)參數(shù)，轉(zhuǎn)軸的單位矢量在參考坐標(biāo)系中的3個(gè)方向余弦ex、ey、ez及繞此軸的轉(zhuǎn)角Φ；歐拉角式，采用3-1-2旋轉(zhuǎn)順序，轉(zhuǎn)角分別是ψ、φ、θ。上述姿態(tài)參數(shù)與旋轉(zhuǎn)矩陣存在如下關(guān)系[7]：

(4)

(5)

設(shè)Vo、Vb分別是矢量V在觀測(cè)坐標(biāo)系和本體坐標(biāo)系的值，存在轉(zhuǎn)換矩陣R，繞x軸的基元旋轉(zhuǎn)記為Rx，誤配準(zhǔn)的旋轉(zhuǎn)矩陣記為Rw。Vo=RVb，

(6)

對(duì)繞本體x軸翻轉(zhuǎn)180°的誤配準(zhǔn)情況，有Vo=R·Rx(π)·Vb，因而Rw=R·Rx(π)，其中

可以得到誤配準(zhǔn)的姿態(tài)角，ψw=-ψ，φw=φ，θw=θ，即姿態(tài)角只有符號(hào)變化，絕對(duì)值大小沒(méi)有變化，對(duì)于繞y軸或者z軸的翻轉(zhuǎn)有類似的結(jié)果，這個(gè)特點(diǎn)可以用到校正中。

設(shè)校正后的歐拉軸/角參數(shù)是exc、eyc、ezc、Φc，旋轉(zhuǎn)矩陣是Rcorrection，σ是角度閾值，誤配校正算法如下：

1)判斷歐拉轉(zhuǎn)角是否大于閾值，如果Φ>σ則需校正，執(zhí)行下一步；

3)找到最大的三軸歐拉角對(duì)應(yīng)的旋轉(zhuǎn)軸，記為k，令ekc=ek；

4)找到最小的三軸歐拉角對(duì)應(yīng)的旋轉(zhuǎn)軸，記為j，令ejc=ej；第三個(gè)轉(zhuǎn)軸eic=ei；

6)使用校正的旋轉(zhuǎn)矩陣Rcorrection更新點(diǎn)云數(shù)據(jù)，作為精確配準(zhǔn)的初值。

3　基于ICP算法的精確配準(zhǔn)算法

Besl和McKay于1992年提出了點(diǎn)到點(diǎn)的迭代最近點(diǎn)(Iterated Closest Points，ICP)算法，ICP算法是在兩個(gè)點(diǎn)集中搜索最近的點(diǎn)對(duì)，以這些最近點(diǎn)對(duì)作為控制點(diǎn)來(lái)估算旋轉(zhuǎn)變換矩陣和平移變換矩陣，并將這個(gè)坐標(biāo)變換作用到待配準(zhǔn)點(diǎn)集上，迭代進(jìn)行這一操作過(guò)程，直到正確匹配[9]。

由于待配準(zhǔn)的兩幅點(diǎn)云只有部分區(qū)域是重合的，在搜索最近點(diǎn)對(duì)的時(shí)候，不可避免地會(huì)存在錯(cuò)誤的匹配點(diǎn)對(duì)。為了消除這些錯(cuò)誤匹配點(diǎn)對(duì)對(duì)精確配準(zhǔn)結(jié)果的影響，需要剔除這些錯(cuò)誤匹配點(diǎn)對(duì)。點(diǎn)云數(shù)據(jù)密度是稀疏點(diǎn)云的關(guān)鍵幾何特征，全局配準(zhǔn)時(shí)已經(jīng)估計(jì)過(guò)點(diǎn)云的密度。對(duì)于部分重疊的兩片點(diǎn)云，只有使用重疊區(qū)域的最近點(diǎn)對(duì)，才能準(zhǔn)確計(jì)算出兩者之間的變換矩陣，而非重疊區(qū)域的最近點(diǎn)對(duì)距離偏大。本文采取距離閾值的方法來(lái)剔除錯(cuò)誤匹配點(diǎn)對(duì)，即認(rèn)為搜索的最近點(diǎn)距離大于點(diǎn)云密度一定倍數(shù)的點(diǎn)對(duì)為錯(cuò)誤匹配點(diǎn)對(duì)。

4　多視角點(diǎn)云的配準(zhǔn)

分析多個(gè)視角點(diǎn)云的配準(zhǔn)方法：直接將相鄰兩個(gè)視角點(diǎn)云依次配準(zhǔn)，每次配準(zhǔn)后都去除重疊部分，合并成一幅點(diǎn)云，直到配準(zhǔn)到最后一個(gè)視角,見(jiàn)圖6。經(jīng)過(guò)實(shí)際配準(zhǔn)試驗(yàn)發(fā)現(xiàn)，隨著已配準(zhǔn)點(diǎn)云幅數(shù)的增加，合并起來(lái)的視角所組成的點(diǎn)云數(shù)目增大，重疊率降低，配準(zhǔn)精度并沒(méi)有提高，反而難以配準(zhǔn)，花費(fèi)時(shí)間過(guò)大。

圖6　多視角掃描Fig.6　Multiple-view scan

考慮這樣的方法：每次都只配準(zhǔn)相鄰的兩個(gè)視角，再用所得到的變換矩陣計(jì)算得到最終的配準(zhǔn)結(jié)果。具體說(shuō)明如下：

1)假設(shè)試驗(yàn)相鄰視角相差45°，共有8幅點(diǎn)云需配準(zhǔn)成完整的點(diǎn)云模型，分別是0°、45°、90°、135°、180°、225°、270°、315°視角下的點(diǎn)云數(shù)據(jù)，最終所有視角點(diǎn)云都配準(zhǔn)到0°視角。

2)記315°視角點(diǎn)云配準(zhǔn)到270°視角下的變換矩陣為R1、T1，270°視角點(diǎn)云配準(zhǔn)到225°視角下的變換矩陣為R2、T2，依次類推，45°配準(zhǔn)到0°的變換矩陣為R7、T7。記315°、270°、225°、45°、0°視角下的點(diǎn)云數(shù)據(jù)分別為X315、X270、X225、X45、X0，有X270=R1X315+T1，X225=R2X270+T2，…，X0=R7X45+T7，即45°視角點(diǎn)云經(jīng)過(guò)一次變換R7、T7，就可以變換到0°視角；

3)315°視角的點(diǎn)云變換到0°視角可以由下式計(jì)算得到:

(7)

其他視角點(diǎn)云變換到0°視角由類似的公式可以得到。

所有視角點(diǎn)云都統(tǒng)一到0°視角之后，采用文獻(xiàn)[10]中的平差方法，降低整體誤差，再合并重合部分的點(diǎn)云，就可以得到完整的點(diǎn)云模型。

5　試驗(yàn)仿真

本文仿真試驗(yàn)使用某衛(wèi)星仿真點(diǎn)云數(shù)據(jù)，點(diǎn)云相鄰視角間隔分為45°數(shù)據(jù)為0°、45°、90°、135°、180°、225°、270°、315°這8個(gè)視角下的點(diǎn)云。不同視角下的點(diǎn)云數(shù)目有所變化，測(cè)試算法的有效性和魯棒性。在主頻為3.20 GHz，內(nèi)存為4 GB，WINXP操作系統(tǒng)的PC機(jī)上，以7.8.0版本的Matlab為平臺(tái)進(jìn)行算法仿真。配準(zhǔn)誤差定義為均方根誤差(Root Mean Square Error，RMSE)：

(8)

式中：N為兩塊待配準(zhǔn)點(diǎn)云重疊部分點(diǎn)數(shù)目；pi、qj分別為點(diǎn)云中重疊區(qū)域的點(diǎn)。

5.1相鄰視角的配準(zhǔn)效果

對(duì)于相鄰視角點(diǎn)云的配準(zhǔn)，選取90°和45°視角下的點(diǎn)云數(shù)據(jù)，分別作為Model點(diǎn)云和Data點(diǎn)云，相應(yīng)的數(shù)據(jù)點(diǎn)數(shù)1 136、1 204。

圖7(b)所示為粗配準(zhǔn)的點(diǎn)云，藍(lán)色為Model點(diǎn)云，紅色為Data點(diǎn)云，二者有部分重疊區(qū)域。可以看到兩幅點(diǎn)云基本配準(zhǔn)，沿滾轉(zhuǎn)軸方向仍有偏差，配準(zhǔn)誤差為0.138 9。為了近一步提高點(diǎn)云配準(zhǔn)精度，使用改進(jìn)的ICP算法進(jìn)行優(yōu)化，可以看到兩片點(diǎn)云已經(jīng)重合，配準(zhǔn)誤差降低到0.093 8。

圖7　90°視角點(diǎn)云配準(zhǔn)向45°視角結(jié)果Fig.7　Pair-wise registration result

5.2對(duì)稱視角配準(zhǔn)的校正

本體點(diǎn)云對(duì)稱，誤配準(zhǔn)如圖8(b)所示，Data點(diǎn)云繞本體軸旋轉(zhuǎn)了180°，采用算法校正之后，可以得到圖8(c)所示的正確配準(zhǔn)結(jié)果。

對(duì)所有兩兩相鄰視角點(diǎn)云進(jìn)行配準(zhǔn)，圖9所示為未采用校正算法和采用校正算法后，配準(zhǔn)成功率的比較，可以看到有對(duì)稱視角點(diǎn)云(45°和225°視角點(diǎn)云)的配準(zhǔn)成功率均有明顯提高，整體成功率平均提高31.52%。

圖8　對(duì)稱點(diǎn)云誤配準(zhǔn)的校正Fig.8　Mis-registration correction of symmetry point cloud

圖9　各視角的配準(zhǔn)成功率Fig.9　Success rate of adjacent point cloud registration

5.3噪聲對(duì)配準(zhǔn)誤差的影響

對(duì)上述90°和45°視角下的點(diǎn)云數(shù)據(jù)添加均值為零、方差變化的高斯噪聲，驗(yàn)證算法在噪聲影響下的有效性，如圖10所示?？梢钥吹浇?jīng)改進(jìn)的四點(diǎn)算法在噪聲標(biāo)準(zhǔn)差小于0.15 m時(shí)能保證配準(zhǔn)誤差小于0.14 m，且整體精度優(yōu)于原4PCS算法。然而在噪聲過(guò)大(超過(guò)0.15 m)時(shí)，兩種算法配準(zhǔn)誤差都變大。

圖10　噪聲對(duì)配準(zhǔn)誤差的影響Fig.10　RMSE under variable noise

5.4整體配準(zhǔn)結(jié)果

嘗試對(duì)多個(gè)相鄰視角進(jìn)行了配準(zhǔn)，無(wú)噪聲情況下，從圖11可以看到文中改進(jìn)的配準(zhǔn)算法精度都高于4PCS算法。不同相鄰視角誤差有所變化，是因?yàn)椴煌噜徱暯堑狞c(diǎn)云密度有所不同，都在比較小的區(qū)域里面波動(dòng)。

將所有視角點(diǎn)云統(tǒng)一到同一個(gè)視角中，由于相鄰視角點(diǎn)云存在重疊部分，這樣直接得到的點(diǎn)云模型存在大量重疊部分。需要合并重疊部分，才能用于后續(xù)的曲面重建等處理。對(duì)比圖12和圖13，可以看到點(diǎn)云數(shù)目從11 060降低到3 532，點(diǎn)云得到了簡(jiǎn)化，同時(shí)模型的特征也較好地保存下來(lái)。

圖11　相鄰視角的配準(zhǔn)誤差Fig.11　RMSE of adjacent point cloud registration

圖12　統(tǒng)一到同一坐標(biāo)系下，未去除重疊部分Fig.12　Multiple-view point cloud in a global coordinate system with overlap section

圖13　去除重疊部分點(diǎn)云Fig.13　Removing the point cloud of overlap section

6　結(jié)束語(yǔ)

兩幅點(diǎn)云的配準(zhǔn)是多幅點(diǎn)云配準(zhǔn)的基礎(chǔ)和關(guān)鍵。針對(duì)空間非合作目標(biāo)，點(diǎn)云的配準(zhǔn)算法要兼顧精確性、快速性和內(nèi)存占用大小等因素。本文針對(duì)衛(wèi)星掃描點(diǎn)云數(shù)據(jù)，提出基于KD-Tree點(diǎn)云均勻采樣簡(jiǎn)化算法，在保持衛(wèi)星特征的情況下較好地實(shí)現(xiàn)了點(diǎn)云簡(jiǎn)化。對(duì)于衛(wèi)星稀疏點(diǎn)云數(shù)據(jù)，使用基于改進(jìn)四點(diǎn)算法進(jìn)行全局配準(zhǔn)，將全局配準(zhǔn)結(jié)果作為精確ICP配準(zhǔn)的初值，實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的配準(zhǔn)。對(duì)于四點(diǎn)算法中誤差閾值參數(shù)多的情況，給出了誤差閾值參數(shù)與點(diǎn)云數(shù)據(jù)密度之間的關(guān)系，有效提高算法的穩(wěn)定性。提出根據(jù)衛(wèi)星姿態(tài)變化的連續(xù)性，解決衛(wèi)星點(diǎn)云中存在對(duì)稱視角導(dǎo)致誤配的問(wèn)題。對(duì)多視角點(diǎn)云進(jìn)行了配準(zhǔn)，實(shí)現(xiàn)了衛(wèi)星點(diǎn)云模型重構(gòu)。

References)

[1]WOLFSON H, RIGOUTSOS I. Geometric hashing: an overview[J]. IEEE Computer Science and Engineering, 1997, 4(4):10-21.

[2]RUSU R B. Fast point feature histograms (FPFH) for 3D registration[C]∥Robotics and Automation, 2009.ICRA 09.IEEE International Conference, Kobe, May 12-17, 2009:3212-3217.

[3]GUO Y L, SOHEL F, BENNAMOUN M. An accurate and robust range image registration algorithm for 3D object modeling[J]. IEEE Transactions on Multimedia, 2014, 16(5): 1377-1390.

[4]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975, 18(9): 509-517.

[5]IRANI S, RAGHAVAN P. Combinatorial and experimental results for randomized point matching algorithms[J]. Computational Geometry, 1999, 12(1-2): 17-31.

[6]YAO L,RUGGERI,TADDEI P, et al. Robust surface registration usingN-points approximate congruent sets[J]. EURASIP Journal on Advances in Signal Processing, 2011(1): 72.

[7]AIGER D, NILOY M J. 4-Points congruent sets for robust pairwise surface registration[J].ACM Transactions on Graphics (TOG), 2008, 27(3): 85-94.

[8]呂振鐸, 雷擁軍. 衛(wèi)星姿態(tài)測(cè)量與確定[M]. 北京: 國(guó)防工業(yè)出版社, 2013: 30-35.

[9]BESL P J, MCKAY N D. A method for registration of 3D shape[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[10]李彩林, 郭寶云, 季錚. 多視角三維激光點(diǎn)云全局優(yōu)化整體配準(zhǔn)算法[J]. 測(cè)繪學(xué)報(bào), 2015, 44(2): 183-189.

LI C L, GUO B Y, JI Z. Global optimization and whole registration algorithm of multi-view 3D laser point cloud[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(2): 183-189(in Chinese).

(編輯：高珍)

Research on registration algorithm of multiple-view point cloud for non-cooperative spacecraft

GUO Ruike, WANG Li*, ZHU Feihu, WU Yun

Beijing Institute of Control Engineering, Beijing 100190, China

The point cloud data registration is one of the key technical aspects of three-dimensional reconstruction for non-cooperative spacecraft. To solve the pair-wise registration issue of sparse point cloud, and align the multiple-view point cloud accurately,an optimization registration method was presented. A novel point cloud simplification algorithm using uniform sampling was proposed based on KD-Tree and the uniform relation of the threshold parameters in the 4PCS(4-Points Congruent Sets) algorithm was established via the density of the point cloud. By using the mis-registration correction method based on attitude,the mis-registration problem of the symmetry point cloud was solved.The results show that the proposed algorithm can effectively achieve good alignments of the sparse point cloud of the satellite, besides, the stability and the success rate of the algorithm is also improved.

non-cooperative spacecraft; multiple-view;point cloud data; registration;4-points congruent sets

10.16708/j.cnki.1000-758X.2016.0055

2016-03-28；

2016-05-20；錄用日期：2016-08-22；

時(shí)間：2016-09-2113:41:18

http:∥www.cnki.net/kcms/detail/11.1859.V.20160921.1341.003.html

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973)(2013CB733100)

郭瑞科(1989-)，男，碩士研究生，ruikeguo@163.com,研究方向?yàn)榭臻g圖像處理

王立(1977-)，男，研究員，bheart@263.net，研究方向?yàn)榭臻g圖像處理、模式識(shí)別以及視覺(jué)導(dǎo)航

V391.41

A

http:∥zgkj.cast.cn

引用格式：郭瑞科,王立,朱飛虎,等. 空間非合作目標(biāo)的多視角點(diǎn)云配準(zhǔn)算法研究[J].中國(guó)空間科學(xué)技術(shù), 2016,36(5)：

32-39.GUORK,WANGL,ZHUFH,etal.Researchonregistrationalgorithmofmultiple-viewpointcloudfornon-cooperativespacecraft[J].ChineseSpaceScienceandTechnology, 2016,36(5)：32-39(inChinese).