萬程輝，程效軍，賈東峰

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

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

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

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

研究一種兩次分層壓縮點云數(shù)據(jù)的方法，將等高距和其允許誤差設(shè)為閾值壓縮數(shù)據(jù)。試驗證明，通過設(shè)置適當(dāng)?shù)那衅穸?，該方法?shù)據(jù)壓縮率大、算法執(zhí)行效率高、特征保持較好、三維模型表面光滑，具有良好的應(yīng)用價值。

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

一、引 言

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

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

二、點云數(shù)據(jù)壓縮算法

1.點云壓縮的算法

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

2.快速成型技術(shù)原理

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

圖1 分層提取的點云

三、基于快速成型技術(shù)的壓縮算法

1.點云切片的生成

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

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

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

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

圖2 點云數(shù)據(jù)的分層切片

2.切片厚度設(shè)置

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

圖3 等高距與閾值設(shè)置

3.算法流程

兩次分層壓縮數(shù)據(jù)的算法流程圖如圖4所示。

圖4 算法流程圖

四、實例分析

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

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

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

從圖5可以看出適當(dāng)?shù)那衅穸饶鼙３州^好的特征，如0.002 m與0.005 m的等高距，壓縮數(shù)據(jù)均勻，保持較好的輪廓特征。0.001 m的等高距壓縮數(shù)據(jù)過大，特征損失也大。0.01 m與0.02 m的等高距過大，數(shù)據(jù)抽取間隔過大，數(shù)據(jù)特征損失大。

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

圖6 利用Geomagic建模比較

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

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

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

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

當(dāng)?shù)雀呔噙^大時，如圖5(f)，分層切片中數(shù)據(jù)提取厚度變大，壓縮厚度也過大，物體的特征損失較多，建模效果差，需要調(diào)節(jié)閾值，如變大1/10，切片壓縮厚度變小，使點云數(shù)據(jù)更好地保留特征。

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

表1 點云數(shù)據(jù)壓縮率

五、結(jié)束語

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

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

［2］ 姜琳琳，趙曉明，洪波.LiDAR數(shù)據(jù)結(jié)合特征線獲取高精度DEM及DOM［J］.黑龍江工程學(xué)院學(xué)報:自然科學(xué)版，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］ 王亞美，趙萍.一種基于點云數(shù)據(jù)的直接分層算法［J］.沈陽理工大學(xué)學(xué)報，2009，28(3):39-41.

［5］ 吳杭彬，劉春.激光掃描數(shù)據(jù)的等值線分層提取和多細節(jié)表達［J］.同濟大學(xué)學(xué)報:自然科學(xué)版，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］ 劉春，陸春.三維激光掃描數(shù)據(jù)的壓縮與地形采樣［J］.遙感信息，2005，2(2):96-102.

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

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

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

［13］ 國家技術(shù)監(jiān)督局.GB14912-94大比例尺地形圖機助制圖規(guī)范［S］.北京:中國標(biāo)準出版社，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—)，男，江西南城人，講師，博士生，主要研究方向為三維激光掃描數(shù)據(jù)處理。