擬萬有引力定律三維激光點云數據精簡方法

鄧博文　王召巴　金永

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

關鍵詞：信號處理；三維激光點云精簡；萬有引力定律；特征點保護

文獻標志碼：A 文章編號：1674-5124（2018）05-0108-05

0引言

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

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

為實現基于實際幾何尺寸的回轉體構件的虛擬裝配，前期開發一種基于龍門結構的回轉關節臂式激光掃描系統（RAMSGL）。該測量機可以快速、精確地測量回轉體構件的表面信息，且獲取的點云數據量十分巨大。因此，本文旨在分析點云獲取方式的基礎上，開發出一種高效、準確的點云精簡算法。

1點云數據的獲取及分析

1.1點云數據獲取方式

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

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

1.2點云數據分析

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

從圖中可以看出，點云數據相當密集，平坦區域（即圖3（b）中灰度基本一致區域）有相當大的點云密度，點云中存在大量的冗余數據。

1.2.1點云數據徑向分析

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

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

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

1.2.2點云數據切向分析

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

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

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

萬有引力定律的具體表述為：任意兩個質點有通過連心線方向的力相互吸引。

本算法將質點質量替換為該點聯合曲率，并求取每點3階鄰域內引力的“合力”，如圖8所示為點“受力”簡圖。

圖中P_i為P點3階鄰域內的點，兩點間的歐氏距離為

點云數據中各點的受力為

從圖中可以清晰地看到，臺階面、圓孔以及各倒角特征被保留下來，為后續壓縮工作提供了保障。通過cloudcompare軟件對比精簡前后數據，以點之間距離誤差為顏色索引進行顯示，從藍色至淺黃，距離誤差逐漸由0增大至0.1 inln，結果如圖10所示。總精簡比為94%時，最大點間距離偏差為0.1 mm，且偏差值點均集中在非特征區域。

3結束語

針對由線激光傳感器掃描系統RAMSGL獲取的海量近似有序點云數據的精簡問題，本文提出了擬萬有引力定律的點云數據精簡方法。該方法無需求解海量點云數據的拓撲結構，節省了大量的運算時間和計算機資源。通過將萬有引力公式中各點的質量替換為該點切向、徑向“聯合曲率”參數，求取了點云數據的“引力”分布圖，該圖可以有效地將點云數據劃分為特征點和非特征冗余點兩部分，實現了對點云數據特征點的提取和保護。最終將完整的特征點和經過大比例采樣的非特征冗余點融合，實現了點云精簡。

（編輯：徐柳）