基于代數(shù)曲面的殘缺點(diǎn)云數(shù)據(jù)迭代修復(fù)算法

胡少乾，周來(lái)水，閆杰瓊，文思揚(yáng)，穆冬梅

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

0 引言

隨著數(shù)字化測(cè)量技術(shù)的發(fā)展，通過(guò)三維激光掃描儀獲取的實(shí)物外形點(diǎn)云數(shù)據(jù)在逆向工程[1]領(lǐng)域有著廣泛的應(yīng)用。但由于掃描過(guò)程中光線遮擋、實(shí)物外表反射率不一致、實(shí)物殘缺等原因，獲取的點(diǎn)云數(shù)據(jù)表面難免存在著孔洞，殘缺的點(diǎn)云數(shù)據(jù)直接用于模型重建會(huì)丟失模型原有幾何信息，因此需要先修復(fù)殘缺點(diǎn)云數(shù)據(jù)，為后續(xù)逆向工程中點(diǎn)云數(shù)據(jù)的模型重建提供基礎(chǔ)。

相關(guān)學(xué)者對(duì)殘缺點(diǎn)云數(shù)據(jù)的修復(fù)算法進(jìn)行了大量研究。該方法主要分為兩類：一類基于三角網(wǎng)格[2-4]對(duì)點(diǎn)云殘缺孔洞進(jìn)行修補(bǔ)，該方法是在點(diǎn)云三角化過(guò)程中對(duì)出現(xiàn)的孔洞進(jìn)行填補(bǔ)，該算法的復(fù)雜度較高，當(dāng)點(diǎn)云數(shù)據(jù)量較大時(shí)，運(yùn)算量較大，難以取得理想的效果。另一類直接對(duì)點(diǎn)云模型進(jìn)行殘缺孔洞修復(fù)。晏海平等[5]以殘缺孔洞邊界點(diǎn)和邊界周圍的散亂點(diǎn)為依據(jù)在殘缺區(qū)域擬合曲面片，并在曲面片上采樣相應(yīng)的點(diǎn)，從而完成點(diǎn)云殘缺孔洞的修復(fù)，孔洞修復(fù)結(jié)果很大程度上受擬合曲面片的函數(shù)影響。YUMER M E等[6]基于前饋神經(jīng)網(wǎng)絡(luò)完成對(duì)殘缺孔洞的修補(bǔ)，該方法的效果受限于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練集，且訓(xùn)練集的制作是極為復(fù)雜的工作。上述現(xiàn)有算法適合對(duì)曲率變化小、殘缺孔洞面積較小的點(diǎn)云數(shù)據(jù)修復(fù)，但對(duì)缺失面積較大、曲率變化大的點(diǎn)云表面修復(fù)效果較差。

針對(duì)上述問(wèn)題，提出了一種通過(guò)迭代修復(fù)殘缺點(diǎn)云數(shù)據(jù)的算法，能對(duì)缺失十分嚴(yán)重且曲率變化較大的殘缺點(diǎn)云進(jìn)行有效修復(fù)。本文以三維激光掃描儀獲取的航空發(fā)動(dòng)機(jī)外形點(diǎn)云數(shù)據(jù)為對(duì)象，進(jìn)行了相關(guān)實(shí)驗(yàn)，驗(yàn)證了該方法的有效性。

1 算法流程

圖1 本文算法流程圖

該算法采取迭代的方式自適應(yīng)修復(fù)殘缺孔洞區(qū)域，最終得到殘缺數(shù)據(jù)修復(fù)的點(diǎn)集P′。在上述算法中對(duì)整個(gè)點(diǎn)集P和稀疏點(diǎn)集X重復(fù)應(yīng)用下采樣和上采樣，然而通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，在將點(diǎn)集X推向數(shù)據(jù)殘缺區(qū)域時(shí)，只有臨近殘缺區(qū)域邊界的點(diǎn)被推向了殘缺孔洞，對(duì)整個(gè)點(diǎn)集進(jìn)行上述處理增加了算法的復(fù)雜度。因此，為了減少冗余計(jì)算，除第一次迭代對(duì)整個(gè)點(diǎn)集進(jìn)行處理外，之后每次迭代只對(duì)新增區(qū)域的點(diǎn)集進(jìn)行處理，后續(xù)章節(jié)中介紹了自適應(yīng)選擇新增點(diǎn)集的辦法。該算法偽代碼如下所示。

偽代碼:殘缺點(diǎn)云數(shù)據(jù)的迭代修復(fù)算法1:輸入原始點(diǎn)云P,令i=0,p?pi2:對(duì)點(diǎn)云pi下采樣m個(gè)粒子,得到點(diǎn)集X,令X?X0;3:while未達(dá)殘缺修復(fù)條件do;4:令X?X∪Xi;5:使用WLOP算子使X均勻分布;6:基于APSS曲面,將點(diǎn)集Xi中的點(diǎn)推向數(shù)據(jù)殘缺區(qū)域;7:基于Voronoi圖對(duì)點(diǎn)集Xi進(jìn)行點(diǎn)插值得到上采樣點(diǎn)集γi;8:選擇點(diǎn)集γi中新增區(qū)域的點(diǎn)為活動(dòng)點(diǎn)集,令其為pi+1;9:令i?i+1,p?p∪pi;10:對(duì)點(diǎn)集pi下采樣mi個(gè)粒子,得到點(diǎn)集Xi(其中mi=2m |pi|/|p0|,|…|表示點(diǎn)集中點(diǎn)的數(shù)量);11:end while12:return輸出修復(fù)點(diǎn)云P′,結(jié)束。

2 算法實(shí)現(xiàn)

2.1 下采樣和均勻分布

2.2 基于點(diǎn)集代數(shù)曲面的排斥分布

為了完成殘缺區(qū)域的修復(fù)，本文引入了一個(gè)排斥算子將點(diǎn)移動(dòng)到點(diǎn)云殘缺的區(qū)域。從已知區(qū)域向外平滑擴(kuò)展是用來(lái)填補(bǔ)數(shù)據(jù)缺失區(qū)域的很好方式，即：從已知表面沿其切向外擴(kuò)展原有點(diǎn)集所定義的表面。為保證殘缺孔洞處的修補(bǔ)點(diǎn)能很好擬合原殘缺孔洞的幾何信息，將點(diǎn)沿點(diǎn)集的代數(shù)曲面推向殘缺孔洞區(qū)域。點(diǎn)集的排斥分布示意如圖2所示(本刊黑白印刷，相關(guān)疑問(wèn)請(qǐng)咨詢作者)。

圖2 點(diǎn)集排斥分布示意圖

在?xi∈Xi上定義的APSS曲面，通過(guò)排斥的方式將點(diǎn)沿著APSS曲面移動(dòng)。移動(dòng)方向由切向分量和投影分量?jī)刹糠纸M成。點(diǎn)xi的切向分量由通過(guò)APSS曲面的半徑r沿其過(guò)球心的軸rxi向外旋轉(zhuǎn)來(lái)確定的。為保證排斥后的點(diǎn)集能均勻分布，切向分量的公式類似WLOP算子的均勻項(xiàng)，定義如下：

(1)

式中：xi為當(dāng)前點(diǎn)；X為稀疏點(diǎn)集；wp為點(diǎn)集的類似于WLOP算子中的密度權(quán)重項(xiàng)；μ為平衡系數(shù)。

(2)

θ(r)=e-r2/(h/4)2

(3)

通常l并不垂直于在xi處的法向量nxi，因此通過(guò)計(jì)算nxi的正交向量，最終確定其切向分量為

l′=l-(l·nxi)nxi

(4)

可得旋轉(zhuǎn)角度為

(5)

在對(duì)粒子xi施加切向分量后，對(duì)其施加投影分量，將其向點(diǎn)集定義的APSS曲面投影，以確保點(diǎn)沿著APSS曲面移動(dòng)，投影分量定義為

(6)

對(duì)點(diǎn)施加切向分量和投影分量移動(dòng)后，完成排斥分布，點(diǎn)云粒子將分布于數(shù)據(jù)殘缺區(qū)域，但需要注意的是，只使用一次排斥并不能填補(bǔ)整個(gè)殘缺數(shù)據(jù)，這是因?yàn)橛葾PSS定義的曲面并不能完全表示殘缺區(qū)域。因此在后續(xù)步驟完成后需要繼續(xù)將點(diǎn)集推向殘缺區(qū)域，以完成殘缺數(shù)據(jù)的修復(fù)。

2.3 上采樣及點(diǎn)集合并

點(diǎn)集Xi為稀疏的點(diǎn)集，被排斥分布到殘缺區(qū)域后，需對(duì)其進(jìn)行上采樣，從而得到分布于殘缺區(qū)域的稠密點(diǎn)集。Voronoi圖的頂點(diǎn)位于近鄰點(diǎn)的中心，因此基于Voronoi圖的上采樣點(diǎn)能均勻分布在Xi定義的光滑表面上并且保持原有數(shù)據(jù)結(jié)構(gòu)。上采樣步驟如圖3所示，上采樣點(diǎn)是其近鄰3個(gè)點(diǎn)的外接圓的圓心，即：點(diǎn)集Voronoi圖的頂點(diǎn)。不斷重復(fù)計(jì)算新增點(diǎn)位置，得到稠密的點(diǎn)集。

圖3 基于Voronoi圖的上采樣

上采樣后點(diǎn)集為γi，選擇γi中位于新增區(qū)域的點(diǎn)為Pi+1，將其合并到點(diǎn)集P中，形成新的點(diǎn)集，令其為P，令i?i+1。由于在將點(diǎn)集排斥分布時(shí)，只有臨近殘缺區(qū)域邊界附近的點(diǎn)集被移動(dòng)到了殘缺孔洞處，新增區(qū)域點(diǎn)位于殘缺孔洞周圍。因此在計(jì)算下一次迭代時(shí)，只對(duì)新增區(qū)域的點(diǎn)進(jìn)行處理可以提高算法運(yùn)算效率并將滿足以下條件的點(diǎn)視為新增區(qū)域的點(diǎn)，合并到點(diǎn)集P中：

3 綜合實(shí)驗(yàn)

為了證明本文算法的有效性，本節(jié)對(duì)航空發(fā)動(dòng)機(jī)外形實(shí)測(cè)點(diǎn)云數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)。如圖4所示，為航空發(fā)動(dòng)機(jī)機(jī)匣表面殘缺孔洞，對(duì)其進(jìn)行20次迭代后，完成了該區(qū)域數(shù)據(jù)的修復(fù)。隨著迭代的進(jìn)行，點(diǎn)集被不斷排斥分布到殘缺區(qū)域，殘缺區(qū)域面積逐漸縮小直到完成修復(fù)。

圖4 機(jī)匣表面數(shù)據(jù)迭代修復(fù)結(jié)果

圖5所示為航空發(fā)動(dòng)機(jī)的管路點(diǎn)云數(shù)據(jù)。由于管路緊緊依附于發(fā)動(dòng)機(jī)表面，只能獲取管路一側(cè)的測(cè)量數(shù)據(jù)，管路數(shù)據(jù)殘缺十分嚴(yán)重。該算法對(duì)管路點(diǎn)云模型進(jìn)行了15次迭代，獲得了較為理想的完整點(diǎn)云模型。

圖5 管路數(shù)據(jù)迭代修復(fù)結(jié)果

圖6展示了管路的原始數(shù)據(jù)和使用本文算法修復(fù)后的數(shù)據(jù)進(jìn)行泊松重建的結(jié)果，并放大了局部細(xì)節(jié)。直接使用原始數(shù)據(jù)進(jìn)行泊松重建后模型表面發(fā)生了塌陷，而重采樣后的數(shù)據(jù)再進(jìn)行泊松重建后，模型較好地保持了管路原有特征結(jié)構(gòu)。說(shuō)明本文算法修復(fù)能夠有效修復(fù)殘缺數(shù)據(jù)，對(duì)修復(fù)后的數(shù)據(jù)進(jìn)行重建保留了實(shí)物更完整的信息。

圖6 管路數(shù)據(jù)修復(fù)前后重建結(jié)果

圖7為對(duì)比了航空發(fā)動(dòng)機(jī)外形點(diǎn)云數(shù)據(jù)使用上述算法處理的前后效果。結(jié)果顯示，該算法修復(fù)了發(fā)動(dòng)機(jī)表面殘缺區(qū)域。對(duì)原始數(shù)據(jù)和使用該算法修復(fù)后的數(shù)據(jù)進(jìn)行了泊松重建。結(jié)果顯示，原始數(shù)據(jù)泊松重建后，殘缺區(qū)域模型塌陷嚴(yán)重；對(duì)修復(fù)后的數(shù)據(jù)進(jìn)行重建，重建結(jié)果保持了發(fā)動(dòng)機(jī)表面的輪廓幾何特征。

上述實(shí)驗(yàn)說(shuō)明本文算法可以有效修復(fù)殘缺點(diǎn)云數(shù)據(jù)，恢復(fù)原有幾何信息，獲得一個(gè)完整的高質(zhì)量點(diǎn)云數(shù)據(jù)。

圖7 航空發(fā)動(dòng)機(jī)外形點(diǎn)云數(shù)據(jù)修復(fù)前后對(duì)比

4 結(jié)語(yǔ)

本文提出了基于代數(shù)曲面的殘缺點(diǎn)云數(shù)據(jù)迭代修復(fù)算法。通過(guò)迭代的方式不斷縮小點(diǎn)云殘缺區(qū)域的面積，直到修復(fù)殘缺點(diǎn)云數(shù)據(jù)。本文以航空發(fā)動(dòng)機(jī)外形點(diǎn)云數(shù)據(jù)為對(duì)象進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)表明該算法對(duì)曲率連續(xù)點(diǎn)云表面的有效性。該方法不僅能修復(fù)曲率變化不大的機(jī)匣點(diǎn)云殘缺孔洞，還對(duì)曲率變化較大的航空發(fā)動(dòng)機(jī)管路模型十分有效。使用本文方法修復(fù)的航空發(fā)動(dòng)機(jī)實(shí)測(cè)外形點(diǎn)云數(shù)據(jù)，較好地恢復(fù)了殘缺區(qū)域的幾何信息，為逆向工程中發(fā)動(dòng)機(jī)數(shù)字樣機(jī)的構(gòu)建提供了基礎(chǔ)。