基于快速成型技術的點云壓縮算法研究

萬程輝，程效軍，賈東峰

(1.同濟大學測量與國土信息工程系，上海200092;2.南昌工程學院水利與環境工程學院，江西南昌330099)

基于快速成型技術的點云壓縮算法研究

萬程輝1，2，程效軍1，賈東峰1

(1.同濟大學測量與國土信息工程系，上海200092;2.南昌工程學院水利與環境工程學院，江西南昌330099)

研究一種兩次分層壓縮點云數據的方法，將等高距和其允許誤差設為閾值壓縮數據。試驗證明，通過設置適當的切片厚度，該方法數據壓縮率大、算法執行效率高、特征保持較好、三維模型表面光滑，具有良好的應用價值。

快速成型技術;切片厚度;壓縮率;三維模型

一、引 言

在逆向工程和快速成型技術中，海量散亂點云的特征提取較為復雜和困難。基于點云數據的特征提取主要有以下方式:① 點云數據建立網格模型，在三角面片上提取特征點和特征線等［1-3］，其優點是算法成熟，但從總體建模來講，計算時間較長，且三角面片建立有一些缺陷;②從點云直接提取特征點，主要通過法矢或平面截取等方式獲取特征線、輪廓線和骨架線等［4-8］，特點是算法相對復雜，但計算時間較長;③由于前兩種算法計算時間都較長，可對海量點云數據先進行壓縮，再對特征線進行提取，這樣可節省計算時間［9-10］。

本文提出一種兩次分層提取數據的方法，即一種微小切片方法，用于提取特定方向的點云數據，對海量數據壓縮時可提高計算速度，且能較好地保留特征。

二、點云數據壓縮算法

1.點云壓縮的算法

點云壓縮的算法很多，不同類型的點云數據可以采取相應的壓縮方法。常用的算法有:最小距離法、均勻網格采樣法、平均距離壓縮算法、八叉樹壓縮算法等。這些算法對海量點云數據的壓縮主要考慮3個方面:①壓縮量;②數據的曲率特征保留;③算法執行效率。這些算法存在的問題是:執行效率高、壓縮量大的算法，往往特征保留少，如最小距離法、均勻采樣法等;考慮曲率特征保留，算法相對復雜，計算執行效率低，如八叉樹、自適應曲率等壓縮算法。本文通過基于快速成型技術方法，對數據進行分層，在每層中提取一定厚度的數據，切片厚度在點云之間距離范圍時，提取距離小于該厚度的數據，以達到壓縮數據的效果，并能較好地保留物體輪廓特征，且算法執行效率高，壓縮率大。

2.快速成型技術原理

快速成型技術原理是“分層制造，逐層疊加”，快速建立模型。根據模具的形狀，每次做成一個具有一定微小厚度和特定形狀的截面，稱為切片，再把切片逐層粘結起來得到立體的模具［11］。三維激光掃描得到的點云數據具有海量、散亂、線性掃描和三維算法復雜等特點，將點云數據根據物體的特征方向，進行切片提取數據，投影到平面上獲取物體的特征線［12］。為了生成等高線，點云數據用了分層平面投影的方法［5］，將Z+1和Z層之間的數據平面投影到高程平面Z上，如圖1所示。從圖1得知，分層的寬度會影響點云數據的提取。寬度過大時，點云投影過密，形成平面上的點云帶，不利于提取等高線特征，在等高線的特征細節上有差異;寬度小時，點云產生斷裂，形成不連續的數據，造成等高線的特征丟失。

圖1 分層提取的點云

三、基于快速成型技術的壓縮算法

1.點云切片的生成

根據快速成型技術，本文提出利用微小切片來提取點云進行數據壓縮的方法，以克服分層剖切造成的點云數據不均勻問題，從而控制分層的厚度，避免分層過厚或過薄，同時舍去特征線提取時的冗余數據。

點云數據經過預處理后，得到以高程方向為序的點云數據。為了快速提取所需點云數據，對其進行兩次分層。

第一次分層，算出坐標范圍為(Xmin，Ymin，Zmin)～(Xmax，Ymax，Zmax)，生成最小包圍盒，如圖2(a)所示。按Z方向高度H和等高距h，進行第一次分層，每一層大小為(Xmax－Xmin，Ymax－Ymin，h)，每層的Z坐標范圍為(Z，Z+h)，將符合要求的數據存入每層矩形包圍盒中，如圖2(b)所示。

第二次分層，在第一次分層包圍盒內的數據中，提取等高線上下允許厚度的點云數據，形成一條微小切片，帶寬大小為等高線的容許誤差Δ，微小帶狀包圍盒的大小為(Xmax－Xmin，Ymax－ Ymin，Z± Δ)，將符合要求的數據存入每層的微小切片中，如圖2(c)所示。

圖2 點云數據的分層切片

2.切片厚度設置

點云數據提取數據寬度設置在屬性允許誤差Δ內。這是一個關鍵閾值，提取的點云數據寬度與點云數據的分布密度有關，而點云數據分布密度與掃描密度設置和掃描對象的遠近相關。為了便于調節，在算法中設置范圍為等高距大小的 1/10～1/20，如圖3所示。如等高線在數字地形測量中的容許誤差為等高距的1/15，若等高距為0.5 m時，提取的范圍為Z±(0.5×1/15)的高程厚度，根據大比例尺地形圖機助制圖規范，圖根點高程中誤差不大于等高距的1/10，滿足等高線精度要求［13］。微小切片的寬度由等高距和設定的閾值兩個值組成。

圖3 等高距與閾值設置

3.算法流程

兩次分層壓縮數據的算法流程圖如圖4所示。

圖4 算法流程圖

四、實例分析

本文選取典型的點云數據，用Visual C++6.0在PC上編程實現和驗證本文算法。以三維激光掃描儀掃描的華佗雕像為例，掃描的海量點云數據總數為708 987個，整個雕像的高度為3.239 5 m。為觀察效果，截取雕像頭部數據，圖5為不同等高距獲取的壓縮點云數據，圖6為不同等高距的建模效果。

1)利用快速成型技術壓縮點云數據，兩次分層可以選取等高距h與允許誤差Δ的大小靈活改變切片厚度。為了比較壓縮效果，固定選取1/15閾值計算切片厚度，如圖5所示，不同的等高距壓縮數據，等高距與閾值的乘積使切片厚度不同，比較可知，特征保留也不同。

圖5 微小分層切片對點云的壓縮

從圖5可以看出適當的切片厚度能保持較好的特征，如0.002 m與0.005 m的等高距，壓縮數據均勻，保持較好的輪廓特征。0.001 m的等高距壓縮數據過大，特征損失也大。0.01 m與0.02 m的等高距過大，數據抽取間隔過大，數據特征損失大。

2)利用Geomagic軟件對壓縮數據進行建模。記錄建模時間，建模耗時如表1所示，閾值為等高距1/15的壓縮數據與全部數據比較，壓縮率達到85%以上，壓縮數據建模耗時少74 s。建模效果如圖6所示。

圖6 利用Geomagic建模比較

圖5(a)為用全部數據所建模型，細節詳細但數據冗余，三角面片建模復雜，耗時長，且模型不光滑，表面粗糙。

圖5(c)為0.002 m等高距壓縮數據，建模速度快，特征保持良好，模型光滑，具有較好的模型效果。

圖5(b)至圖5(e)壓縮數據量稍少，建模效果次之;圖5(f)等高距過大，建模特征效果較差。

3)圖4壓縮數據與圖5建模效果得到的微小切片的厚度是壓縮的關鍵因素。

當等高距過大時，如圖5(f)，分層切片中數據提取厚度變大，壓縮厚度也過大，物體的特征損失較多，建模效果差，需要調節閾值，如變大1/10，切片壓縮厚度變小，使點云數據更好地保留特征。

圖5(c)為0.002 m等高距，分層與壓縮間距適當，壓縮數據均勻，較好地保留了特征，本實例設置0.002 m等高距和1/15的允許誤差是壓縮數據的合適閾值。

表1 點云數據壓縮率

五、結束語

快速成型技術主要應用在模型的分層建模疊加成型方面，利用兩次分層來壓縮點云數據，設定等高距與切片厚度閾值來壓縮數據。通過不同的等高距，得到不同的壓縮數據，對數據壓縮率、建模時間和建模效果進行了比較，可知設置適當的等高距和分層閾值，可使壓縮數據保持良好的特征，壓縮數據率大，且算法簡單，執行效率高。利用快速成型技術對點云數據進行壓縮，可較好地保留整個特征，對分層提取物體的特征具有良好的應用價值。

［1］ 任自珍，岑敏儀，張同剛，等.基于等高線形狀分析的LiDAR建筑物提取［J］.西南交通大學學報，2009，44(1):83-88.

［2］ 姜琳琳，趙曉明，洪波.LiDAR數據結合特征線獲取高精度DEM及DOM［J］.黑龍江工程學院學報:自然科學版，2009，23(2):33-35.

［3］ KILIAN J，HAALA N，ENGLICH M.Capture and Evaluation of Airborne Laser scanner Data［C］∥International Archives of Photogrammetry and Remote Sensing.Vienna:［s.n.］，1996.

［4］ 王亞美，趙萍.一種基于點云數據的直接分層算法［J］.沈陽理工大學學報，2009，28(3):39-41.

［5］ 吳杭彬，劉春.激光掃描數據的等值線分層提取和多細節表達［J］.同濟大學學報:自然科學版，2009，37(2):267-271.

［6］ VERROUST A，LAZARUS F.Extracting Skeletal Curves from 3D Scattered Data［C］∥Shape Modeling International’99.Aizu Wakamatsu:［s.n.］，1999.

［7］ RIANMORA S，KOOMSAP P，HAI D P V.Selective Data Acquisition for Direct Integration of Reverse Engineering and Rapid Prototyping［J］.Virtual and Physical Prototyping，2009，4(4):227-239.

［8］ KUMBHAR V K，PANDEY P M，RAO P V M.Improved Intermediate Point Curve Model for Integrating Reverse Engineering and Rapid Prototyping［J］.Int J Adv Manuf Technol，2008(37):553-562.

［9］ 劉春，陸春.三維激光掃描數據的壓縮與地形采樣［J］.遙感信息，2005，2(2):96-102.

［10］ 徐景中，萬幼川，張圣望.LiDAR地面點云的簡化方法研究［J］.測繪信息與工程，2008，33(1):32-34.

［11］ 焦向東，佟澤民.分層制造法的材料技術及其發展［J］.中國機械工程，2000，11(5):582-584.

［12］ 王亞美，趙萍.一種基于點云數據的直接分層算法［J］.沈陽理工大學學報，2009，28(3):39-41.

［13］ 國家技術監督局.GB14912-94大比例尺地形圖機助制圖規范［S］.北京:中國標準出版社，1994.

A Point Cloud Compression Algorithm Based on Rapid Prototyping

WAN Chenghui，CHENG Xiaojun，JIA Dongfeng

0494-0911(2012)06-0010-03

P208

B

2011-07-15

國家自然基金項目(40971241)

萬程輝(1975—)，男，江西南城人，講師，博士生，主要研究方向為三維激光掃描數據處理。