擬萬有引力定律三維激光點(diǎn)云數(shù)據(jù)精簡方法

鄧博文　王召巴　金永

摘要：為對海量三維激光點(diǎn)云數(shù)據(jù)進(jìn)行精簡，提出一種擬萬有引力定律的點(diǎn)云數(shù)據(jù)精簡方法。該方法將萬有引力定律中各點(diǎn)質(zhì)量替換為點(diǎn)的切向與徑向聯(lián)合曲率表征參數(shù)，通過求解點(diǎn)云中各點(diǎn)之間的引力分布，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)平坦與特征區(qū)域的劃分，完成點(diǎn)云數(shù)據(jù)中特征點(diǎn)的提取與保護(hù)。將非特征區(qū)域點(diǎn)大比例均勻采樣，再與完整的特征點(diǎn)融合形成精簡后點(diǎn)云數(shù)據(jù)，將其與原始點(diǎn)云進(jìn)行對比，結(jié)果表明：該精簡方法在有效保留特征區(qū)域的基礎(chǔ)上可以大比例精簡點(diǎn)云，同時(shí)精簡前后點(diǎn)云點(diǎn)距離誤差較小。在總精簡比94%時(shí)，最大點(diǎn)間距離偏差值為0.1 mm，且高偏差值點(diǎn)均位于非特征區(qū)域。

關(guān)鍵詞：信號處理；三維激光點(diǎn)云精簡；萬有引力定律；特征點(diǎn)保護(hù)

文獻(xiàn)標(biāo)志碼：A 文章編號：1674-5124（2018）05-0108-05

0引言

三維激光點(diǎn)云數(shù)據(jù)是指物體經(jīng)過三維激光掃描系統(tǒng)掃描后在空間坐標(biāo)系下表征物體表面特征的海量點(diǎn)集。隨著三維激光掃描系統(tǒng)檢測精度和速度的大幅提高，點(diǎn)云數(shù)據(jù)的量級可達(dá)千萬甚至更大。一般的點(diǎn)云數(shù)據(jù)處理方法是先對其進(jìn)行網(wǎng)格化，而隨著點(diǎn)云數(shù)據(jù)量的增加，網(wǎng)格化的時(shí)間以及內(nèi)存開銷急劇增大，同時(shí)，管理、操作以及處理網(wǎng)格拓?fù)湫畔⒌膹?fù)雜程度也隨之急劇增加；此外，當(dāng)多網(wǎng)格模型在屏幕中網(wǎng)格數(shù)量大于屏幕分辨率時(shí)，用點(diǎn)作為模型數(shù)據(jù)的基本單元比多邊形網(wǎng)格有更加明顯的效率優(yōu)勢。Levoy等提出了基于點(diǎn)的點(diǎn)云數(shù)據(jù)處理概念，成為計(jì)算機(jī)圖形學(xué)的研究熱點(diǎn)。然而，海量的數(shù)據(jù)依舊會(huì)造成處理的困難，因此，研究點(diǎn)云數(shù)據(jù)的壓縮、精簡方法就具有重要的意義。

HUANG Y等通過對八叉樹結(jié)構(gòu)生成的細(xì)節(jié)層次樹進(jìn)行漸進(jìn)式編碼，在后續(xù)的研究中，F(xiàn)AN等對點(diǎn)云數(shù)據(jù)進(jìn)行一系列自下而上的聚類，生成了一顆細(xì)節(jié)層次（Level of Details）樹，對樹進(jìn)行由根到葉的遍歷，在遍歷過程中，對遍歷節(jié)點(diǎn)進(jìn)行編碼，實(shí)現(xiàn)了對原始模型的編碼壓縮。文獻(xiàn)中也使用了相似的基于八叉樹結(jié)構(gòu)的漸進(jìn)編碼技術(shù)對點(diǎn)云數(shù)據(jù)進(jìn)行編碼壓縮。楊岳湘等通過行小波編碼對三維數(shù)字高程模型（DEM）數(shù)據(jù)進(jìn)行編碼壓縮，取得了良好的壓縮效果。方芳等將散亂點(diǎn)云數(shù)據(jù)進(jìn)行切片，然后對切片后的“片點(diǎn)云”通過弦高差法逐層進(jìn)行特征點(diǎn)保留，實(shí)現(xiàn)了數(shù)據(jù)的壓縮，而在后續(xù)的研究過程中，徐工等在對散亂點(diǎn)云切片后，對其進(jìn)行小波變換，利用小波系數(shù)峰值，自適應(yīng)地保留特征信息，實(shí)現(xiàn)散亂點(diǎn)云的自適應(yīng)壓縮。楊璐璟在其碩士學(xué)位論文中提出了一種“曲率一法矢量”算法，本質(zhì)上是通過計(jì)算點(diǎn)云數(shù)據(jù)中各點(diǎn)的曲率和法矢量，在不同的曲率范圍內(nèi)采用不同的法矢量夾角閾值進(jìn)行采樣，從而達(dá)到精簡點(diǎn)云數(shù)據(jù)的目的。陳俊宇等通過設(shè)定點(diǎn)云間最大誤差值，而后對點(diǎn)云進(jìn)行統(tǒng)一采樣，實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)的有效精簡，然而該方法由于采用統(tǒng)一采樣可能會(huì)造成特征點(diǎn)的丟失。劉迎等使用KD樹對點(diǎn)云進(jìn)行劃分，在此基礎(chǔ)上使用主成分分析法求取各點(diǎn)的曲率，從而實(shí)現(xiàn)了點(diǎn)云特征的提取，而后對點(diǎn)云進(jìn)行特征點(diǎn)的精簡，該方法可以有效保護(hù)特征同時(shí)精簡點(diǎn)云，然而該方法需要遍歷海量點(diǎn)云數(shù)據(jù)，無法避免的占用大量的計(jì)算資源并且需要大量計(jì)算時(shí)間，降低了點(diǎn)云精簡的效率。類似的研究還有很多㈣。上述方法分為兩類：1）需要在三維空間中對點(diǎn)云進(jìn)行劃分，而后求取點(diǎn)云的局部拓?fù)潢P(guān)系，進(jìn)而對其微分幾何性質(zhì)進(jìn)行計(jì)算，對于本文將使用的海量點(diǎn)云數(shù)據(jù)而言，其微分幾何性質(zhì)的計(jì)算十分耗時(shí)：2）需要對點(diǎn)云數(shù)據(jù)進(jìn)行全局遍歷，用以生成八叉樹、KD樹或是LOD樹，從而在子葉節(jié)點(diǎn)上對點(diǎn)云數(shù)據(jù)進(jìn)行精簡，無疑該類方法對于本文將使用的海量點(diǎn)云來說同樣是代價(jià)巨大的。

為實(shí)現(xiàn)基于實(shí)際幾何尺寸的回轉(zhuǎn)體構(gòu)件的虛擬裝配，前期開發(fā)一種基于龍門結(jié)構(gòu)的回轉(zhuǎn)關(guān)節(jié)臂式激光掃描系統(tǒng)（RAMSGL）。該測量機(jī)可以快速、精確地測量回轉(zhuǎn)體構(gòu)件的表面信息，且獲取的點(diǎn)云數(shù)據(jù)量十分巨大。因此，本文旨在分析點(diǎn)云獲取方式的基礎(chǔ)上，開發(fā)出一種高效、準(zhǔn)確的點(diǎn)云精簡算法。

1點(diǎn)云數(shù)據(jù)的獲取及分析

1.1點(diǎn)云數(shù)據(jù)獲取方式

如圖1所示，本文的檢測對象是一個(gè)半徑l 10mm盲法蘭，法蘭盤上有高為3mm的臺階面，以及均勻分布的6個(gè)直徑8.5 mm的通孔，每個(gè)通孔都有一個(gè)0.5 mm的倒角，此外，法蘭盤外邊緣也存在一個(gè)相同尺寸的倒角。

圖2為RAMSGL獲取近似有序點(diǎn)云數(shù)據(jù)的方式簡圖，掃描部件選用基恩士公司生產(chǎn)的LV7080型二維線激光傳感器。紫色粗體線條為二維激光光線，紫色粗體虛線為轉(zhuǎn)過一定角度后的激光光線，需要指出的是，激光光線始終與直徑共線。二維激光傳感器逆時(shí)針旋轉(zhuǎn)一周，每隔0.03。采集一次數(shù)據(jù)，每條激光光線上包含800點(diǎn)數(shù)據(jù)，點(diǎn)與點(diǎn)之間間隔0.05mm。由于數(shù)據(jù)量巨大，為使結(jié)果更加清晰，選擇圖1中黑色扇形區(qū)域標(biāo)出的工件部分（點(diǎn)元數(shù)據(jù)量為2 885 229（2 837xl 017）點(diǎn)進(jìn)行后續(xù)研究，也不會(huì)影響算法的一般性。圖1中黑色扇形區(qū)域所標(biāo)出的工件的點(diǎn)云數(shù)據(jù)量為2 885 229（2 837xl 017）點(diǎn)，后文將不再強(qiáng)調(diào)該黑色扇形區(qū)域。

1.2點(diǎn)云數(shù)據(jù)分析

圖3（a）為點(diǎn)云數(shù)據(jù)原始三維圖像，由于待測法蘭的特征差異方向集中在Z軸方向，為了方便觀察，本文將該區(qū)域以一個(gè)矩形（即以點(diǎn)云矩陣的行列）方式在X-O-Y平面上進(jìn)行投影，并以Z方向數(shù)值作為灰度值進(jìn)行顯示，如圖3（b）所示。

從圖中可以看出，點(diǎn)云數(shù)據(jù)相當(dāng)密集，平坦區(qū)域（即圖3（b）中灰度基本一致區(qū)域）有相當(dāng)大的點(diǎn)云密度，點(diǎn)云中存在大量的冗余數(shù)據(jù)。

1.2.1點(diǎn)云數(shù)據(jù)徑向分析

分析點(diǎn)云數(shù)據(jù)的獲取方式可知：在每條激光光線方向（徑向）上，點(diǎn)云數(shù)據(jù)代表著被測法蘭沿半徑方向的—個(gè)截面輪廓，如圖4所示為一條分割圓孔的點(diǎn)云數(shù)據(jù)。該輪廓含有臺階面、通孔倒角、通孔以及法蘭外邊緣倒角等特征，這些特征在Z軸方向上表現(xiàn)出明顯的曲率變化。因此，本文采用Z軸方向的曲線曲率作為表征參數(shù)。

曲線曲率就是針對曲線上某個(gè)點(diǎn)的切線方向角對弧長的轉(zhuǎn)動(dòng)率，通過微分來定義，令弧長MM的切線轉(zhuǎn)角為△α，弧長為△s，M處的曲率為K=dα/ds。

根據(jù)式（1）也可求出該輪廓截面關(guān)于Z軸的徑向曲率分布，如圖5所示。圖中有3個(gè)明顯的峰值，對比圖4可知，第1個(gè)峰值出現(xiàn)在臺階面位置，后兩個(gè)峰值分別位于直徑分割圓孔的兩側(cè)，同時(shí)可以看到，圓孔兩側(cè)以及點(diǎn)云末尾存在3個(gè)小的凸起峰，這是由圓孔周邊以及法蘭外沿倒角造成的，而這些峰值所處位置正是點(diǎn)云數(shù)據(jù)壓縮時(shí)應(yīng)該保持的位置。其余平坦區(qū)域的曲率變化平緩。

1.2.2點(diǎn)云數(shù)據(jù)切向分析

在被測法蘭的切線方向上，每條點(diǎn)云數(shù)據(jù)代表著不同半徑輪廓圓的表面特征值，如圖6所示為一條穿過圓孔的輪廓圓的點(diǎn)云數(shù)據(jù)，可以看出，通孔及其倒角處，曲線的曲率發(fā)生了明顯的變化。

同理，通過式（1）求出輪廓圓關(guān)于Z軸的切向曲率分布，如圖7所示。圖中的峰值依舊出現(xiàn)在圓孔的兩側(cè)，兩側(cè)的倒角也同樣造成了小的突起峰值。但是，由于在切向，代表臺階面或法蘭外沿的點(diǎn)云曲線并不具有明顯的起伏，因此臺階面及法蘭外沿并沒有在切向曲率分布中被表征出來。由于每一點(diǎn)的切向方向與徑向方向彼此近似正交，因此，為了將各種特征都表征出來，借鑒平均曲率的概念，得到聯(lián)合曲率為

切向與徑向曲率的“聯(lián)合曲率”準(zhǔn)確地將臺階面、圓孔表征了出來。但是，卻無法明顯將臺界面倒角、圓孔倒角以及臺界面切相面識別出來，而這些點(diǎn)同樣是工件重構(gòu)的重要特征點(diǎn)，如果無法準(zhǔn)確識別，無疑會(huì)對后續(xù)的精簡的精度產(chǎn)生影響。因此，本文提出了一種擬萬有引力的壓縮方法。2擬萬有引力壓縮方法

萬有引力定律的具體表述為：任意兩個(gè)質(zhì)點(diǎn)有通過連心線方向的力相互吸引。

本算法將質(zhì)點(diǎn)質(zhì)量替換為該點(diǎn)聯(lián)合曲率，并求取每點(diǎn)3階鄰域內(nèi)引力的“合力”，如圖8所示為點(diǎn)“受力”簡圖。

圖中P_i為P點(diǎn)3階鄰域內(nèi)的點(diǎn)，兩點(diǎn)間的歐氏距離為

點(diǎn)云數(shù)據(jù)中各點(diǎn)的受力為

從圖中可以清晰地看到，臺階面、圓孔以及各倒角特征被保留下來，為后續(xù)壓縮工作提供了保障。通過cloudcompare軟件對比精簡前后數(shù)據(jù)，以點(diǎn)之間距離誤差為顏色索引進(jìn)行顯示，從藍(lán)色至淺黃，距離誤差逐漸由0增大至0.1 inln，結(jié)果如圖10所示?？偩啽葹?4%時(shí)，最大點(diǎn)間距離偏差為0.1 mm，且偏差值點(diǎn)均集中在非特征區(qū)域。

3結(jié)束語

針對由線激光傳感器掃描系統(tǒng)RAMSGL獲取的海量近似有序點(diǎn)云數(shù)據(jù)的精簡問題，本文提出了擬萬有引力定律的點(diǎn)云數(shù)據(jù)精簡方法。該方法無需求解海量點(diǎn)云數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，節(jié)省了大量的運(yùn)算時(shí)間和計(jì)算機(jī)資源。通過將萬有引力公式中各點(diǎn)的質(zhì)量替換為該點(diǎn)切向、徑向“聯(lián)合曲率”參數(shù)，求取了點(diǎn)云數(shù)據(jù)的“引力”分布圖，該圖可以有效地將點(diǎn)云數(shù)據(jù)劃分為特征點(diǎn)和非特征冗余點(diǎn)兩部分，實(shí)現(xiàn)了對點(diǎn)云數(shù)據(jù)特征點(diǎn)的提取和保護(hù)。最終將完整的特征點(diǎn)和經(jīng)過大比例采樣的非特征冗余點(diǎn)融合，實(shí)現(xiàn)了點(diǎn)云精簡。

（編輯：徐柳）